Futhark 병렬 합산, MI100서 1억 개 더할 때 기본 reduce가 고정 트리보다 거의 3배 빨라

Futhark 블로그에 2026년 11월 4일 게시된 글은 병렬 부동소수점 합산에서 실행 환경에 따라 결과가 달라지는 이유와 계산 순서를 고정하는 데 드는 비용을 설명했습니다. 글에 소개된 빠른 실험에서는 1억 개 숫자를 더할 때 AMD MI100 GPU의 기본 reduce (+) 0가 직접 작성한 sum_tree보다 거의 3배 빨랐습니다. 이 수치는 해당 입력 크기와 GPU에서 나온 결과입니다.

Futhark는 배열 연산을 데이터 병렬로 실행하는 언어입니다. 배열의 모든 값을 더할 때는 원소를 여러 부분으로 나눠 동시에 합산한 뒤 부분합을 모을 수 있습니다. 이 과정에서 덧셈 순서가 달라집니다. 부동소수점 연산은 각 단계에서 반올림하므로 (0.1 + 0.2) + 0.3과 0.1 + (0.2 + 0.3)의 결과가 다를 수 있습니다. 병렬 합산 결과가 순차적인 왼쪽부터의 합산보다 수치적으로 더 나쁘다고 볼 근거는 없지만, 계산 순서가 바뀌면 결과도 달라질 수 있습니다.

글은 Michael Haddon이 Lane 언어를 대상으로 발표한 부동소수점 재현성 유형의 용어를 사용합니다. Exact는 매번 같은 결과가 보장되는 경우, Replay는 같은 실행 일정에서는 결과가 같지만 다른 장비에서는 달라질 수 있는 경우입니다. Approx는 결과가 비결정적일 가능성이 있는 경우를 가리킵니다. 부분합을 원자 연산으로 모으는 구현에서는 처리 순서가 실행마다 달라질 수 있어 Approx에 해당할 수 있습니다.

Futhark의 reduce는 구체적인 연산 순서를 정하지 않습니다. C 백엔드는 입력 배열을 왼쪽부터 순회하고, GPU 백엔드는 입력을 여러 덩어리로 나눠 각각 합산한 뒤 부분합을 결합합니다. GPU에서 덩어리를 나누는 방식은 입력 크기와 실행 중 확인하는 하드웨어 구성, 사용자가 지정한 튜닝 매개변수에 영향을 받습니다. 현재 구현에서는 같은 시스템에서 같은 reduction을 반복하면 결과가 일관되게 재현됩니다. Futhark 언어는 이를 보장하지 않으며, 같은 시스템에서의 재현성은 현재 구현의 동작입니다.

결과 순서를 고정하는 예로 글은 sum_tree를 제시합니다. 설명의 예시는 원소 수가 2의 거듭제곱인 배열입니다. 배열을 절반으로 나누고 서로 대응하는 원소를 더한 뒤, 배열에 값 하나만 남을 때까지 같은 과정을 반복합니다. 이 구조는 연산 순서를 고정하므로 C와 CUDA 백엔드에서 같은 결과를 냅니다. 순차적인 foldl (+) 0과는 계산 순서가 달라, 두 방식의 결과값도 달라질 수 있습니다. 글은 조금 더 복잡한 구현으로 이 방식을 임의 크기의 배열과 비가환 연산자로 확장할 수 있다고 설명합니다.

이 재현성에는 속도 비용이 따릅니다. 글의 빠른 실험에서 기본 reduce (+) 0는 MI100 GPU로 1억 개 숫자를 더할 때 sum_tree보다 거의 3배 빨랐습니다. 블로킹으로 필요한 GPU 커널 수를 줄이면 격차를 좁힐 수 있지만, 가장 빠른 reduction 방식은 하드웨어의 세부 구성에 따라 달라질 수 있습니다. 글은 다른 연산에도 비슷한 비용 문제가 있다고 덧붙였습니다. 컴파일러의 scan 구현은 Futhark로 직접 작성한 구현보다 빠르며, reduce_by_index를 완전히 결정적으로 구현하려면 정렬과 구간별 reduction을 거쳐야 해 원자 연산을 사용하는 컴파일러 구현보다 훨씬 느려진다고 설명합니다.

글은 부동소수점 반올림에 따른 결과 차이와 프로그래머가 언어의 조건을 지키지 않아 생기는 문제도 구분합니다. scatter는 지정된 인덱스에 병렬로 값을 쓰는 연산입니다. 인덱스가 중복되지 않아야 하며, 중복될 경우 같은 인덱스에 대응하는 값도 같아야 합니다. Futhark는 이 조건을 실행 중 검사하지 않습니다. 조건을 어기면 어느 쓰기가 남을지 예측하기 어렵고, 최악의 경우 서로 다른 값의 일부가 섞인 결과가 생길 수 있습니다.

reduce 연산자는 결합법칙을 만족해야 하며, 일부 연산에서는 교환법칙도 필요합니다. Futhark는 이 조건도 실행 중 검사하지 않습니다. 부동소수점 덧셈은 반올림 때문에 엄밀히 결합법칙을 만족하지 않지만, Futhark는 이를 실용적인 합산에 사용하도록 허용하고 입력 원소에 연산자를 적용하는 순서를 정하지 않습니다. 따라서 백엔드와 하드웨어에 따른 합산 순서의 차이로 결과가 달라질 수 있습니다. 이 현상은 scatter의 쓰기 조건이나 결합법칙을 지키지 않는 연산자를 사용했을 때 생기는 문제와 원인이 다릅니다.