Futhark의 나눗셈 예외 처리가 GPU 실행을 늦췄다

모든 나눗셈을 늦춰 0.000000000000000000542%의 버그를 고치다

2026년 10월 14일 게시

현대 컴퓨터 대부분은 정수를 2의 보수(two’s complement)로 표현한다. 이 방식은 가장 작은 음수에 대응하는 양수가 없다는 비대칭성을 지닌다. 예를 들어 부호 있는 8비트 정수에서 가장 작은 값은 -128이고 가장 큰 값은 127이다. 이 특징은 여러 상황에서 문제가 되지만, 여기서는 부호 있는 정수 나눗셈을 살펴본다. 수학적으로 x/-1은 -x가 되어야 하지만, x가 가장 작은 정수라면 결과를 표현할 수 없다.

32비트 정수가 가장 흔하다고 임의로 가정하면, 가능한 입력 2⁶⁴개 가운데 하나는 올바르게 표현할 수 없다. 이 글에서는 Futhark 컴파일러에서 최근 수정한 문제를 언어 구현 관점에서 설명하고, 해결 방법과 성능 비용을 살펴본다. 주된 독자는 다른 언어 구현자지만, 저수준 문제에 관심 있는 사람도 이해할 수 있도록 개념을 설명한다.

C에서 생기는 문제

Futhark 컴파일러에는 여러 백엔드가 있지만, 가장 중요한 백엔드는 C 코드를 생성한다. 생성된 코드를 읽고 직접 수정하기 쉬우며, 대부분의 시스템에는 C 컴파일러가 있거나 쉽게 설치할 수 있어 의존성과 이식성 측면에서 유리하다. Futhark를 C API로 제공하면 다른 언어에서도 Futhark를 호출할 수 있다. 반면 코루틴, 꼬리 호출, 가비지 컬렉션 같은 고급 기능은 C로 표현하기 어렵거나 효율적으로 구현하기 어렵다. 또 생성된 C 코드가 미묘하게 잘못되기 쉽다는 문제도 있다.

Futhark는 메모리 안전성을 보장하므로, 생성 코드에 경계 검사를 체계적으로 넣으면 배열 범위 초과 같은 문제는 막을 수 있다. 더 큰 문제는 정의되지 않은 동작(undefined behavior)이다. C에서는 부호 있는 정수 오버플로가 정의되지 않은 동작이다. 고정 크기 정수 연산에서는 오버플로가 자연스럽게 일어난다고 생각하기 쉽고 실제 컴퓨터도 그렇게 동작하지만, C 컴파일러는 오버플로가 일어나지 않는다고 가정할 수 있다. Futhark에서는 정수 오버플로가 순환하는 동작으로 정의되어 있어, 원하는 동작과 C로 표현할 수 있는 동작이 어긋난다.

C는 부호 없는 정수의 오버플로를 정의된 동작으로 규정한다. 그래서 Futhark의 C 코드 생성기는 모든 정수형을 부호 없는 C 정수형으로 표현한다. 예를 들어 i64는 uint64_t가 된다. 2의 보수 표현에서는 대부분의 산술 연산이 비트 수준에서 부호 없는 정수 연산과 같기 때문이다. 비교 연산은 예외로, 비교 전에 부호 있는 형식(예: int64_t)으로 변환한다. 비트 표현은 바뀌지 않고 컴파일러가 <= 같은 연산에 내보내는 명령만 달라지므로 변환 비용은 없다.

나눗셈에서는 부호가 중요하다. x/-1에서 나누는 값이 작은 음수인지, 아니면 -1의 2의 보수 비트 패턴을 부호 없는 정수로 해석한 값인지에 따라 결과가 달라진다. 따라서 Futhark는 부호 있는 정수 나눗셈에 부호 있는 C 나눗셈을 생성한다. 하지만 x가 가장 작은 정수일 때 x/-1을 계산하면 결과인 -x를 부호 있는 정수로 표현할 수 없다. 이는 부호 있는 정수 오버플로이며, C에서는 정의되지 않은 동작이다.

Futhark에서 정의되지 않은 동작을 일으키는 것은 원칙적으로 허용할 수 없다. x86에서는 이런 나눗셈이 실제로 CPU 예외를 일으켜 프로그램이 중단될 수도 있다. 해결 방법 자체는 간단하다. Futhark 런타임의 32비트 부호 있는 나눗셈은 다음과 같이 정의되어 있다.

int32_t squot32(int32_t x, int32_t y) { return x / y; }

정의되지 않은 동작이 발생하는 0.000000000000000000542%의 경우를 피하는 버전은 다음과 같다.

int32_t squot32(int32_t x, int32_t y) { return y == -1 ? (int32_t)(0 - (uint32_t)x) : x / y; }

이 함수는 제수가 -1인지 확인하고, 그렇다면 정의된 동작인 부호 없는 산술로 부호를 반전한다. 그 대가로 모든 나눗셈에 분기 하나가 추가된다. 결과는 여전히 구현에 따라 달라질 수 있지만, Futhark가 대상으로 삼는 기계에서는 올바른 결과를 낸다.

div가 아니라 quot를 사용하는 이유는 Futhark에 나눗셈 연산자가 두 개 있기 때문이다. 하나는 음의 무한대 방향으로 반올림하고, 다른 하나는 C처럼 0 방향으로 반올림한다. 위 함수는 코드가 더 간단한 C의 동작을 따르는 연산자에 해당하지만, 문제는 두 연산자 모두에서 같다.

성능 비용

정확성을 포기할 수는 없지만, 실제로 거의 일어나지 않을 특수한 경우를 처리하려고 모든 정수 나눗셈에 분기를 추가해야 한다는 점은 부담스럽다. 그렇다면 비용은 어느 정도일까?

GPU에서 Futhark 벤치마크 모음을 측정했을 때 영향은 확인되지 않았다. 부호 있는 정수 나눗셈이 상대적으로 드물고, 그런 연산도 대개 인덱스 계산에 쓰여 결과를 기다리는 메모리 읽기의 지연이 나눗셈 비용을 가리기 때문일 가능성이 있다.

분기가 추가됐을 때의 최악에 가까운 비용을 보기 위해 부호 있는 나눗셈 처리량이 병목이 되도록 만든 프로그램도 시험했다. 프로그램은 정수 k와 정수 배열 두 개를 받고, 각 배열에서 대응하는 두 값 x와 y를 k번 나눈다. //는 squot32 함수를 사용하며, #[unsafe]는 0으로 나누는 검사를 제거한다.

-- == -- random input { 1000000 [1000]i32 [1000]i32 }
entry main [n] (k: i32) (xs: [n]i32) (ys: [n]i32) : [n]i32 =
  map2 (\x y ->
          loop z = x
          for _i < k do
            #[unsafe]
            z // y)
       xs
       ys

대부분의 k 값에서는 나눗셈을 반복하면 결과가 빠르게 0이 되지만, 컴파일러는 이를 가정할 수 없으므로 실제로 나눗셈을 수행해야 한다. 반복문 처리에는 정수 덧셈과 비교도 필요하므로 이 프로그램이 나눗셈만으로 병목이 생기는 것은 아니다. 다만 나눗셈을 길게 풀어 쓴 프로그램을 쓰는 것보다는 이 방법이 더 설득력 있다.

futhark bench 도구로 squot32 구현이 고정된 컴파일러를 비교했다(관련 풀 리퀘스트). 먼저 c 백엔드로 순차 코드를 측정했다.

$ futhark-old-and-busted bench divisions.fut
...

divisions.fut (no tuning file):
100000i32 [10000]i32 [10000]i32: 3390148μs (95% CI: [ 3387613.7, 3396498.1])

$ futhark-new-hotness bench divisions.fut
...

divisions.fut (no tuning file):
100000i32 [10000]i32 [10000]i32: 3389215μs (95% CI: [ 3387626.2, 3391036.4])

측정 가능한 차이는 없었다. 예측하기 쉬운 분기가 있는 프로그램이라면 분기 예측과 추측 실행을 지원하는 최신 CPU에서 예상할 수 있는 결과다.

GPU에서는 어떨까? if 하나를 분기 없는 조밀한 코드 열 줄로 바꾸려는 학생들이 흔히 “GPU는 분기에 약하다”고 말한다. Futhark의 cuda 백엔드로 다시 측정한 결과는 다음과 같다.

$ futhark-old-and-busted bench --backend=cuda divisions.fut
...

divisions.fut (no tuning file):
100000i32 [10000]i32 [10000]i32: 5548μs (95% CI: [ 5546.4, 5552.2])

$ futhark-new-hotness bench --backend=cuda divisions.fut
...

divisions.fut (no tuning file):
100000i32 [10000]i32 [10000]i32: 12592μs (95% CI: [ 12563.5, 12622.1])

차이는 컸다. 생성된 PTX(CUDA 기계 코드)를 보면 기존 버전은 하나의 기본 블록 안에 div.s32 명령 네 개가 연속되도록 일부 펼쳐졌다. 수정된 컴파일러도 반복문 펼치기를 수행했지만, 나눗셈 사이에 여러 분기가 들어갔다. hip 백엔드를 사용한 AMD GPU에서도 비슷한 결과를 관찰했지만 영향은 조금 더 작았다.

결론

극히 드문 나눗셈 사례를 처리하는 비용은 실제로 발생하며 아쉽지만, 더 저렴한 해결책을 원한다. 그래도 생성된 코드에서 정의되지 않은 동작을 허용할 수는 없으므로 당분간은 이 비용을 감수해야 한다. 인위적으로 만든 벤치마크가 아닌 일반적인 벤치마크에서는 영향이 사실상 없는 것으로 보인다. 음수가 절대 나오지 않는다고 확신하는 프로그래머라면 부호 없는 나눗셈을 사용할 수 있다.

기억하는 한, 이번 수정으로 Futhark가 생성하는 C 코드에서 정의되지 않은 동작은 모두 제거됐다. 다만 정수 비트 폭보다 큰 수만큼 비트를 이동하는 코드 생성에는 구현에 따라 달라지는 동작이 적어도 하나 남아 있으며, 이를 고칠 용기는 아직 내지 못했다.