0.000000000000000000542%의 버그를 고치려 모든 나눗셈을 느리게 만들기

Futhark 컴파일러가 signed integer division의 오버플로를 피하도록 고치자 CUDA 성능이 특정 벤치마크에서 5,548μs에서 12,592μs로 느려졌습니다. 일반 벤치마크에서는 차이가 측정되지 않았지만, 모든 나눗셈에 추가된 분기 때문에 GPU 코드 생성이 달라지는 사례를 보여줍니다.

주제: 컴파일러 GPU 언어

에디터 노트

이 수정은 드문 입력을 위한 분기 하나가 GPU에서 특정 코드의 실행 시간을 두 배 이상 늘릴 수 있음을 보여줍니다. CUDA 벤치마크에서 분기 삽입과 PTX 명령 배치 변화가 함께 나타났고, CPU와 일반 GPU 벤치마크에서는 측정 가능한 차이가 없었습니다. 따라서 이 수치를 모든 Futhark 프로그램의 성능 저하로 확대할 수는 없습니다. 반대로 일반 벤치마크에서 차이가 없다는 결과도 나눗셈 처리량이 병목인 코드의 비용을 설명하지 못합니다. C의 정의되지 않은 동작을 없애야 한다는 원저자의 판단은 구체적입니다. 현재 해법의 GPU 비용을 줄일 방법은 글에서 제시하지 않았으며, 댓글은 C의 안전성을 비꼬는 농담과 그에 대한 동의에 그칩니다.

AI 요약

2의 보수(two's complement) 정수 표현에서는 가장 작은 음수의 절댓값을 같은 비트 폭의 양수로 나타낼 수 없습니다. 예를 들어 32비트 정수에서 -2^31을 -1로 나누면 수학적으로 2^31이 나오지만, signed 32비트 정수 범위에는 들어가지 않습니다. 이 경우 C의 signed integer overflow는 정의되지 않은 동작(undefined behavior)입니다. Futhark는 정수 오버플로를 래핑 연산으로 정의하므로 C 코드 생성 때 의미가 어긋납니다. 32비트 입력 쌍 가운데 문제가 생기는 경우는 하나뿐이라 제목의 비율은 2^64분의 1입니다.

C 코드 생성과 나눗셈 수정

Futhark 컴파일러는 정수 연산을 C의 unsigned 타입으로 생성합니다. C에서 unsigned 오버플로는 정의되어 있고, 2의 보수 기계에서는 덧셈과 뺄셈 같은 연산이 비트 수준에서 signed 연산과 같습니다. 비교는 signed 타입으로 변환해 수행하지만, 나눗셈은 피연산자의 부호가 결과를 바꾸므로 signed C 나눗셈을 씁니다. 따라서 최솟값을 -1로 나누는 경우에는 C의 정의되지 않은 동작이 남습니다. x86에서는 CPU 예외가 발생해 프로그램이 종료될 수도 있습니다.

수정한 런타임 함수는 제수가 -1인지 먼저 검사합니다. 이때 피제수를 uint32_t로 바꿔 0에서 빼면 unsigned 래핑 연산으로 결과 비트를 만듭니다. 나머지 입력은 기존 signed 나눗셈으로 처리합니다. 결과를 int32_t로 변환하는 동작은 구현에 따라 달라질 수 있지만, 글에서는 대상 기계에서 원하는 결과를 낸다고 설명합니다. 이 방식은 나눗셈마다 분기를 추가합니다. Futhark에는 음수 나눗셈을 내림 방향으로 처리하는 연산자와 0 방향으로 처리하는 연산자가 있으며, 제시한 함수는 C와 같은 0 방향 나눗셈입니다.

성능 측정

GPU의 일반 Futhark 벤치마크에서는 수정 전후 차이를 측정하지 못했습니다. signed 나눗셈이 드물고, 인덱스 계산에서 나눗셈을 하더라도 뒤따르는 메모리 접근 지연이 비용을 가릴 수 있다고 설명합니다. 별도로 나눗셈 처리량에 집중하도록 만든 프로그램에서는 CPU C 백엔드 실행 시간이 수정 전 3,390,148μs, 수정 후 3,389,215μs로 사실상 같았습니다. CPU에서는 예측하기 쉬운 분기를 추측 실행(speculative execution)이 처리하기 때문이라고 봅니다.

CUDA 벤치마크에서는 수정 전 5,548μs, 수정 후 12,592μs가 나왔습니다. 생성된 PTX를 보면 수정 전 코드는 네 개의 나눗셈 명령을 한 기본 블록에 연속 배치했지만, 수정 후에는 각 나눗셈 사이에 분기가 들어갔습니다. AMD GPU의 HIP 백엔드에서도 비슷한 성능 저하를 관찰했지만 영향은 더 작았습니다. 저자는 정의되지 않은 동작을 남길 수 없어 현재 수정 방식을 유지하며, 음수가 없다고 확신하는 프로그램은 unsigned 나눗셈을 사용할 수 있다고 덧붙입니다.

Lobsters 반응

@dtgriscom — C는 물론 매우 안전하고 쓰기 쉬운 언어로 유명하죠. C 프로그래머는 코딩 실수를 절대 하지 않으니까요. 드디어 제 작업을 알아주는 사람이 있네요.
- @olliej — 저도 그 댓글이 좋았습니다.

원문: Futhark 블로그 / 번역·요약: Trawling

원문 보기 ↗토론 보기 ↗