Futhark가 부호 있는 정수의 최솟값을 `-1` 로 나눌 때 생성된 C 코드에서 발생하는 정의되지 않은 동작을 수정함

원문 발행 2026. 10. 20. 23:02원문 언어 한국어GeekNews 원문 보기

요약

Futhark 언어가 부호 있는 정수의 최솟값을 -1로 나눌 때 C 코드에서 발생하는 정의되지 않은 동작(Undefined Behavior)을 수정했습니다. 이 문제는 2의 보수 표현 방식과 관련되며, 정확성을 위해 제수가 -1인지 검사하고 부호 없는 연산으로 반전하는 로직이 추가되었습니다.

핵심 포인트

Futhark가 C 코드를 생성할 때 발생하는 정의되지 않은 동작(UB)을 수정함.
최솟값을 -1로 나눌 경우, 2의 보수 표현에서 오버플로 및 CPU 예외 발생 가능성이 있음.
정확성 확보를 위해 제수가 -1인지 검사하는 로직이 추가되었으나, 이로 인해 CUDA 등 GPU 환경에서는 성능 저하가 관찰됨.

Futhark가 부호 있는 정수의 최솟값을 -1

로 나눌 때 생성된 C 코드에서 발생하는 정의되지 않은 동작을 수정함. 32비트 정수 입력 조합 2⁶⁴개 중 하나에 해당하지만, x86에서는 CPU 예외로 프로그램이 종료될 수 있음
수정된 구현은 나눗셈마다 제수가 -1

인지 검사 하고, 해당하면 부호 없는 정수 연산으로 부호를 반전함. Futhark의 래핑 동작을 유지하는 대신 분기 비용이 추가됨
일반 GPU 벤치마크에서는 측정 가능한 성능 영향이 없었으며 , 나눗셈을 반복하는 인위적 벤치마크도 CPU에서는 유의미한 차이가 없었음
같은 반복 나눗셈 벤치마크의 CUDA 실행 시간은 5,548μs에서 12,592μs로 증가 함. 수정 전에는 연속된 나눗셈 명령이 배치됐지만, 수정 후에는 그 사이에 여러 분기가 들어갔음
정확성을 위해 수정은 유지 하며, 음수가 절대 없음을 아는 경우에는 부호 없는 나눗셈으로 이 비용을 피할 수 있음. 일반적인 벤치마크에서는 사실상 영향이 없어 보이지만 더 저렴한 해결책은 여전히 필요함
2의 보수와 나눗셈의 예외
거의 모든 현대 컴퓨터가 사용하는 2의 보수 는 표현 범위가 비대칭임
부호 있는 8비트 정수는 최솟값이 -128

, 최댓값이 127

이므로 최솟값에 대응하는 양수가 없음
따라서 x / -1

의 수학적 결과인 -x

는 x

가 최솟값일 때 같은 정수 타입으로 표현할 수 없음
32비트 정수 를 기준으로 이 문제는 가능한 입력 쌍 2⁶⁴개 중 하나에 해당함
제목의 0.000000000000000000542%

는 이 조합 비율이며, 실제 프로그램에서 관측한 발생 빈도는 아님
C 코드 생성의 장점과 의미적 불일치
Futhark의 주요 백엔드는 C 코드를 생성 하며, 이 방식에는 세 가지 실용적 장점이 있음
생성 코드를 사람이 읽고 수정하기 쉬워 디버깅이 편리함
대부분의 시스템에 C 컴파일러가 있거나 쉽게 설치할 수 있어 의존성이 적고 이식성이 높으며, 네이티브 코드 생성기를 함께 배포할 필요가 없음
C API를 통해 다른 언어에서 Futhark를 호출 할 수 있음
반면 코루틴, 꼬리 호출, 가비지 컬렉션 같은 기능은 C로 표현하거나 효율적으로 구현하기 어려움
Futhark는 의미 체계가 비교적 단순 해 이 제약의 영향은 크지 않지만, 미묘하게 잘못된 C 코드를 생성하는 문제는 반복해서 겪음
주된 어려움은 포인터나 버퍼 크기보다 정의되지 않은 동작(undefined behaviour) 에 있음
Futhark 자체는 메모리 안전하며 생성 코드에 범위 검사를 체계적으로 넣기 쉬움. 다만 GPU의 범위 검사 는 더 복잡함
C 컴파일러는 정의되지 않은 동작이 발생하지 않는다고 가정할 수 있고, 실제로 발생하면 어떤 결과도 보장하지 않음
범위 밖 배열 접근이나 해제한 메모리 사용 외에도 여러 조건이 있으며, C99에서는 소스 파일 끝의 개행 누락도 이에 해당함
핵심 충돌은 부호 있는 정수 오버플로 임
C에서는 정의되지 않은 동작이므로 컴파일러가 x+1>x

같은 성질에 기반해 최적화할 수 있음
Futhark에서는 오버플로가 래핑되도록 정의되어 있어, 목표 언어인 C의 의미와 맞지 않음
부호 없는 연산으로 해결되지 않았던 나눗셈
Futhark는 C의 부호 없는 정수 오버플로 가 정의되어 있다는 점을 활용해 모든 정수 타입을 부호 없는 C 타입으로 표현함
예를 들어 i64

는 uint64_t

가 되며, 대부분의 산술 연산은 2의 보수에서 부호 유무와 관계없이 비트 수준 동작이 같음
비교 연산에서는 int64_t

같은 부호 있는 타입으로 변환함. 비트 표현을 바꾸지 않으므로 변환 자체에는 비용이 없고, 컴파일러가 선택하는 비교 명령만 달라짐
나눗셈은 부호에 따라 결과가 달라지므로 부호 있는 C 나눗셈을 생성해야 함
-1

의 비트 패턴을 부호 없는 값으로 해석하면 전혀 다른 제수가 됨
최솟값을 -1

로 나누면 부호 있는 오버플로가 발생하며, x86에서는 CPU 예외로 프로그램이 종료될 수 있음
이 버그는 약 10년간 남아 있었음
수정된 squot32

는 기존의 return x / y;

대신 return y == -1 ? (int32_t)(0 - (uint32_t)x) : x / y;

를 사용함
제수가 -1

이면 정의된 부호 없는 산술로 부호를 반전하고, 그렇지 않으면 기존 나눗셈을 수행함
나눗셈마다 분기가 추가되며, 여전히 구현 정의 동작(implementation-defined behaviour) 에 의존하지만 대상 컴퓨터에서는 원하는 결과를 냄
Futhark에는 음의 무한대 방향으로 내리는 나눗셈 과 C처럼 0 방향으로 버리는 나눗셈이 모두 있음
squot32

는 후자에 해당하며, 최솟값을 -1

로 나누는 문제는 두 방식 모두에 존재함
일반 벤치마크와 반복 나눗셈 실험
GPU에서 Futhark 벤치마크 모음 을 실행했을 때는 수정의 영향을 측정할 수 없었음
부호 있는 나눗셈이 드물고, 발생하더라도 주로 인덱스 계산에 쓰여 뒤따르는 메모리 읽기의 지연이 나눗셈 비용을 숨기기 때문일 가능성이 있음
최악에 가까운 비용을 확인하기 위해 divisions.fut

에서 두 정수 배열의 대응 원소마다 나눗셈을 k

번 반복함
//

로 squot32

를 사용하고, #[unsafe]

로 0으로 나누기 검사를 제거함
반복 나눗셈은 대체로 빠르게 0에 도달하지만, 컴파일러가 이를 가정할 수 없어 연산을 수행해야 함
반복문 관리에도 덧셈과 비교 비용이 들므로 순수하게 나눗셈만으로 병목이 생기는 프로그램은 아님
futhark bench

를 사용해 수정 사항이 포함된 풀 리퀘스트 의 구현과 기존 구현을 비교함
실제 측정 입력은 반복 횟수 100000

, 길이 10000

인 두 i32

배열임
순차 실행하는 c

백엔드는 수정 전 3,390,148μs , 수정 후 3,389,215μs 로 측정 가능한 차이가 없었음
분기를 쉽게 예측할 수 있고 현대 CPU가 추측 실행을 수행한다는 점에서 예상 가능한 결과임
GPU에서는 분기 비용이 드러남
같은 실험의 cuda

백엔드는 수정 전 5,548μs , 수정 후 12,592μs 로 실행 시간이 크게 늘어남
생성된 PTX 코드 에서는 반복문 펼치기 이후의 명령 배치가 달라졌음
기존 구현은 하나의 기본 블록 안에 div.s32

명령 네 개를 연속 배치함
수정 구현도 반복문을 펼쳤지만, 나눗셈 명령 사이에 여러 분기가 들어감
AMD GPU의 hip

백엔드 에서도 비슷한 결과가 나타났지만, 영향은 조금 더 작았음
정확성 유지와 남은 과제
드문 예외를 처리하는 비용은 실제로 존재하지만, 생성 코드의 정의되지 않은 동작을 허용할 수는 없으므로 현재 수정은 유지함
인위적이지 않은 벤치마크에서는 사실상 영향이 없어 보임
음수를 사용하지 않는다는 보장이 있다면 부호 없는 나눗셈 을 선택할 수 있음
이번 문제는 개발자가 기억하는 범위에서 Futhark가 생성하는 C 코드의 마지막 정의되지 않은 동작 사례임
다만 정수의 비트 폭보다 큰 수만큼 비트 시프트 하는 코드 생성에는 적어도 하나의 구현 정의 동작이 남아 있으며, 아직 수정하지 못했음
댓글과 토론

AI 자동 생성 콘텐츠

원문 바로가기