🔢 mathematics

Performance evaluation of branch-free fused multiply-add algorithms for multi-component-type multiple-precision floating-point arithmetic

본 논문은 조건부 분기를 제거함으로써 기존 방식보다 더 높은 성능 향상을 달성함을 입증하며, 더블 워드, 트리플 워드 및 쿼드러플 워드 다중 정밀 산술을 위한 새로운 분기 없는 융합 곱셈-누산 알고리즘을 제안하고 벤치마킹한다.

원저자: Tomonori Kouya

게시일 2026-07-14

📖 4 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Tomonori Kouya

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 오직 표준적인 기성품 레고 브릭만을 사용하여 초정밀 계산기를 만들려고 한다고 상상해 보십시오. 이 브릭들은 당신의 컴퓨터가 사용하는 일반적인 부동 소수점 숫자들입니다. 보통, 이 브릭들을 쌓아 "더블 워드(double-word, 두 개의 브릭)", "트리플 워드(triple-word, 세 개의 브릭)", 또는 "쿼드러플 워드(quadruple-word, 네 개의 브릭)" 숫자를 만들 때, 당신은 브릭을 쌓는 동안 끊임없이 부품의 크기를 확인해야 합니다. 만약 부품이 너무 크거나 작으면, 당신은 멈춰서, 잠시 쉬었다가, 스택을 다시 재배치해야 합니다. 컴퓨터 칩의 세계에서 이러한 "멈춤"은 **분기(branches)**라고 불립니다.

당신이 한 번에 수백만 개의 스택을 동시에 만들려고 할 때(현대적인 그래픽 카드나 강력한 프로세서처럼), 이러한 멈춤은 악몽이 됩니다. 이것은 마치 모든 자동차가 움직이기 전에 서로 다른 표지판을 확인하기 위해 멈춰 서야 하는 교통 체증과 같습니다. 어떤 차는 왼쪽으로 가고, 어떤 차는 오른쪽으로 가면서 전체 행렬이 멈춰버립니다. 이것을 "레인 다이버전스(lane divergence, 경로 이탈)"라고 하며, 이는 성능을 저하시킵니다.

위대한 발견: "멈춤 없는" 고속도로
Tomonori Kouya의 논문은 절대 "표지판을 확인하기 위해 멈추지 않는" 새로운 방식으로 스택을 만드는 방법을 소개합니다. 이것은 "분기 없는(branch-free)" 알고리즘입니다. "이 부품이 충분히 큰가?"라고 묻고 답을 기다리는 대신, 이 새로운 방법은 부품이 어떤 모습이든 완벽하게 작동하는 영리하고 미리 계획된 경로를 사용합니다.

이 논문은 이 새로운 경로가 모든 표준 컴퓨터 형식에 대해 안전하고 정확하다는 것을 초지능 로봇 수학자(FPANVerifier라는 SMT 솔버)를 사용하여 증명합니다. 핵심적인 발견은 이러한 "멈춰서 확인하는" 과정을 제거함으로써 컴퓨터가 훨씬 더 빠르게 계산할 수 있다는 것입니다.

마법의 기술: 동작의 융합
이 논문은 **Fused Multiply-Add (FMA)**라고 불리는 특정 동작에 집중합니다. 곱셈을 한 뒤에 덧셈을 해야 하는 상황을 상상해 보십시오. 보통, 당신은 이를 두 단계로 수행합니다:

곱셈 (그리고 아마도 결과를 수정하기 위해 잠시 멈춤)
덧셈 (그리고 아마도 다시 잠시 멈춤)

저자는 이 두 가지를 하나의 매끄러운 동작으로 수행하는 "융합된(Fused)" 버전을 제안합니다. 마치 닌자가 칼을 던지고 동시에 받는 것과 같습니다.

더블 워드 (2개의 브릭): 기존 방식은 29단계가 걸렸습니다. 새로운 방식은 단 17단계가 걸립니다.
트리플 워드 (3개의 브릭): 기존 방식은 96단계가 걸렸습니다. 새로운 방식은 66단계가 걸립니다.
쿼드러플 워드 (4개의 브릭): 기존 방식은 209단계가 걸렸습니다. 새로운 방식은 146단계가 걸립니다.

이 논문은 다른 연구자들이 제안한 "지름길(shortcut)" 방법(6단계 방법)에 대해서도 논의합니다. 결정적으로, 이 지름길은 일반적으로 유효하지 않습니다. 그것은 숫자들이 이미 특정한 방식으로 완벽하게 배치되어 있을 때(구체적으로, 더해지는 숫자가 곱의 결과보다 최소 2배 이상 클 때)만 작동하는 고속 도구입니다. 만약 당신이 이 지름길을 나눗셈이나 제곱근처럼 숫자의 배치가 보장되지 않는 일반적인 수학 문제에 사용하려고 한다면, 정확도가 심각하게 떨어집니다. 저자의 새로운 방법은 특별한 배치 없이도 모든 숫자에 대해 작동하며, 따라서 일반적인 고정밀 수학을 위한 진정한 "드롭인(drop-in)" 대체제 역할을 합니다.

우리는 얼마나 확신하는가?
저자들은 매우 확신하고 있으며, 단순히 추측하는 것이 아니라 강력한 증거로 이를 뒷받침합니다.

기계 검증: 그들은 단순히 코드를 작성하고 희망을 품은 것이 아닙니다. 그들은 컴퓨터 프로그램을 사용하여 새로운 방법의 오차가 매우 작다는 것( $u$ 가 단일 숫자의 미세한 반올림 오차일 때, $34u^2$ , $184u^3$ , $812u^4$ 와 같은 공식으로 제한됨)을 수학적으로 증명했습니다.
어디서나 테스트됨: 그들은 이 새로운 알고리즘을 두 가지 매우 다른 슈퍼컴퓨터인 **Arm 기반 칩(GB10)**과 **Intel 기반 칩(H100)**에서 실행했습니다.
결과:
- Arm 칩에서, 새로운 방법은 나눗셈 및 제곱근 계산에서 1.5 ~ 2.1배 더 빨랐습니다.
- Intel 칩에서, 새로운 방법은 나눗셈 및 제곱근 계산에서 1.2 ~ 1.6배 더 빨랐습니다.
- 행렬 곱셈(GEMM)과 같은 큰 수학 작업의 경우, Arm 칩에서의 속도 향상은 더욱 극적이었으며, 트리플 워드 숫자에 대해 최대 2.0배 더 빨라졌습니다.

"정확한" 대안
이 논문은 이 기술의 더 정밀한 버전인 Exact FMA에 대해서도 언급합니다. 이 버전은 훨씬 더 정밀하지만, 무거운 대가를 치러야 합니다: 이 방식은 제안된 새로운 방법보다 6 ~ 11배 더 느립니다. 저자들은 최고 수준의 정확도가 반드시 필요한 경우에만 이 "Perfect" 버전을 사용할 것을 권장합니다. 그 외의 거의 모든 경우에는 "분기 없는(branch-free)" 방식이 승자입니다.

"옛날" 방식은 어떠했는가?
이 논문은 이전 연구 버전의 실수 하나를 바로잡기도 합니다. 이전에 저자들은 자신들의 새로운 방법을 매우 느리고 비효율적인 "완전히 증류된(fully distilled)" 옛날 방식과 비교했습니다. 그들은 그것이 공정한 대결이 아니라는 것을 깨달았습니다. 새로운 방법을 실제 "분기 없는(branch-free)" 표준 방식(이미 꽤 빠른 방식)과 비교했을 때, 새로운 방법이 여전히 승리했지만 속도 향상은 더 완만했습니다 (약 1.3 ~ 1.7배 더 빠름). 이것은 여전히 거대한 승리이지만, 더 현실적인 결과입니다.

핵টি 요점
이 논문은 고정밀 수학에서 "멈춰서 확인하는" 분기를 제거함으로써, 정확도를 잃지 않고도 컴퓨터를 훨씬 더 빠르게 만들 수 있음을 보여줍니다. 이것은 마치 모든 교차로에서 멈춰야 하는 자동차에서 교차로 위를 날아다닐 수 있는 자동차로 업그레이드하는 것과 같습니다. 저자들은 이것이 작동함을 증명했고, 실제 하드웨어에서 테스트했으며, 차세대 초고속 계산기를 위해 준비되었음을 보여주었습니다.

기술 요약: 다중 컴포넌트 유형 다중 정밀도 부동 소수점 산술을 위한 분기 없는 융합 곱셈-덧셈(FMA) 알고리즘의 성능 평가

1. 문제 정의

다중 컴포넌트 다중 정밀도 산술(예: Double-Word/DW, Triple-Word/TW, Quadruple-Word/QW)은 표준 binary64(또는 binary32) 컴포넌트를 묶고 오차 없는 변환(Error-Free Transformations, EFTs)을 통해 캐리를 정확하게 처리함으로써 높은 성능을 달나합니다. 그러나 이러한 알고리즘의 재정규화(renormalization) 단계는 일반적으로 중간 값의 크기에 의존하는 if-분기(branch)에 의존합니다. 이러한 분기는 SIMD 및 GPU 구현에서 레인(lane) 또는 워프(warp) 발산(divergence)으로 인한 상당한 성능 저하를 유발합니다.

Zhang과 Aiken이 이전에 DW/TW/QW 덧셈 및 곱셈을 위한 분기 없는 알고리즘을 제안했지만, 이러한 별도의 분기 없는 연산들을 합성하는 방식은 여전히 최적화되지 않은 상태입니다. 구체적으로, 분기 없는 곱셈과 분기 없는 덧셈을 순차적으로 합성하여 융합 곱셈-덧셈(FMA) 연산 $z \leftarrow x \cdot y + c$ 를 수행하는 것은 높은 연산 횟수(예: DW의 경우 29 flops, TW는 96, QW는 209)와 중복된 재정규화 단계를 초래합니다.

2. 방법론

본 논문은 DW, TW, QW 산술(및 그 단정밀도 기반 변형인 DS, TS, QS)을 위한 새로운 분기 없는 융합 곱셈-덧셈(FMA) 알고리즘을 제안합니다. 핵심 방법론은 다음과 같습니다:

알고리즘 구조: 제안된 FMA는 별도의 곱셈과 덧셈을 합성하는 대신, 단일 융합 단계에서 $z \leftarrow x \cdot y + c$ $z \leftarrow x \cdot y + c$ 를 계산합니다. 이 과정은 다음을 포함합니다:
1. 곱 연산 확장(Product Expansion): TwoProd를 사용하여 성분들의 곱을 분해합니다.
2. 가중치별 누적(Weight-wise Accumulation): TwoSum 체인을 사용하여 동일한 2의 거듭제곱 위치에 도달하는 항들을 모읍니다.
3. 재정규화(Renormalization): 결과를 $K$ 개의 겹치지 않는 컴포넌트로 재구성합니다.
게이트 선택 및 검증: 핵심 설계 원칙은 기계적으로 검증 가능한 전제 조건에 기반한 재정규화 게이트의 선택입니다. 알고리즘은 모든 정밀도 $p$ 에 대해 SMT 솔버 z3와 FPANVerifier 도구를 통해 $\text{exp}(a) \ge \text{exp}(b)$ 라는 전제 조건을 기계적으로 증명할 수 있는 곳에서만 FastTwoSum(3 flops)을 사용합니다. 전제 조건을 증명할 수 없는 곳에서는 정확성을 보장하기 위해 TwoSum(6 flops)을 사용합니다.
교환 법칙(Commutativity): 피연산자 교환( $x \leftrightarrow y$ ) 시 비트 단위 일치를 보장하기 위해, 대각 합(diagonal sums)을 재결합하여 전치된 쌍(예: $P_{ij}$ 와 $P_{ji}$ )이 먼저 처리되도록 합니다. 이는 연산 횟수를 늘리지 않고 달성됩니다.
정확한 변형(Exact Variant): 참조용으로 "증류(distillation)" 변형(Exact FMA)도 구현되었습니다. 이는 완전한 오차 없는 확장을 수행한 후, 결과 상대 오차 범위를 달取得하기 위해 여러 번의 TwoSum 스윕을 수행하지만, 계산 비용은 훨씬 높습니다.

3. 주요 기여

3.1 최소 분기 없는 FMA 구성

본 논문은 다음과 같은 연산 횟수(융합 FMA 명령어를 1로 계산)를 갖는 최소한의, 기계 검증된 분기 없는 FMA 알고리즘을 제시합니다:

DW (K=2): 17 flops (합성된 분기 없는 mul+add의 29 대비).
TW (K=3): 66 flops (96 대비).
QW (K=4): 146 flops (209 대비).

이 수치들은 모든 FastTwoSum 전제 조건이 기계적으로 검증된 최소 구성임을 나타냅니다.

3.2 기계 검증된 오차 범위

FPANVerifier를 사용하여, 저자들은 모든 정밀도에 대해 $(|xy| + |c|)$에 대한 오차 범위를 인증합니다:

DW: $34 u^2 (|xy| + |c|)$
TW: $184 u^3 (|xy| + |c|)$
QW: $812 u^4 (|xy| + |c|)$
모든 FastTwoSum 전제 조건의 유효성과, 증명된 변형과 (전제 조건 증명 여부와 상관없이 꼬리 부분에 FastTwoSum을 배치한) 나이브한 변형 사이의 비트 단위 일치가 확인되었습니다.

3.3 교환 법칙

제안된 알고리즘은 6가지 유형 모두(DD/TD/QD/DS/TS/QS)에 대해 $x$ 와 $y$ 에 대한 비트 단위 교환 법칙을 만족합니다. 이는 일반적인 덧셈의 결합 순서를 대칭화함으로써, 연산 횟수를 늘리지 않고 $fma(x, y, c) \equiv fma(y, x, c)$ 를 보장함으로써 달성됩니다.

3.4 나눗셈 및 제곱근을 위한 특화된 변형

본 논문은 나눗셈 및 제곱근 알고리즘의 중간 잔차(residual)가 표준 FMA 증명에 필요한 비중첩 가정을 충족하지 않을 수 있음을 식별했습니다. 이에 따라, 매 사용 맥락마다 전체 구조를 재검증하지 않고도 정확성을 보장하기 위해, 증명되지 않은 FastTwoSum 게이트를 TwoSum으로 격하시키는 "안전한(safe)" 변형(DW 20 / TW 69 / QW 149 flops)을 제안합니다.

4. 실험 결과

알고리즘은 두 플랫폼에서 평가되었습니다:

Arm: NVIDIA GB10 (Grace-Blackwell, Cortex-X925 CPU, Blackwell GPU).
x86: H100 노드 (Intel Xeon Gold 6526Y CPU, H100 GPU).
구현: Scalar, AVX2, AVX-512, NEON, SVE, CUDA.

4.1 선형 대수 커널 (AXPY, GEMV, GEMM)

속도 향상: 제안된 FMA는 계산 집약적인 시나리오에서 분기 없는 베이스라인(BF)을 일관되게 능가합니다.
- AVX2 (x86): GEMM에서 $\times 1.49$ (DD), $\times 1.32$ (TD), $\times 1.47$ (QD)의 속도 향상을 보였습니다.
- NEON (Arm): GEMM에서 $\times 1.40$ (DD), $\times 1.42$ (TD), $\times 1.47$ (QD)의 속도 향상을 보였습니다.
- SVE2: 동일한 레인 너비에서 NEON과 유사한 성능을 보였으며, QD GEMM은 BF 대비 $\times 1.62$ 의 속도 향상에 도달했습니다.
- GPU (GB10): 계산 집약적인 배정밀도 유형의 경우, 제안된 FMA는 이론적 FLOP 비율( $\times 1.71$ (DD), $\times 1.46$ (TD), $\times 1.40$ (QD))과 일치하는 속도 향상을 보였습니다. 대역폭 제한 워크로드(단정밀도 또는 H100)에서는 속도 향상이 $\times 1.00$ 에 가깝습니다.
정확도: 제안된 FMA는 기존 분기 없는 방법(Q/BF)과 대등한 작업 정확도를 유지합니다. 상쇄(cancellation) 시나리오에서도 에러 동작은 베이스라인과 수치적으로 동일합니다. Exact FMA는 더 우수한 결과 상대 정확도를 제공하지만 2.5~5.0배 느립니다.

4.2 나눗셈 및 제곱근

나눗셈: 제안된 FMA는 특히 고정밀도에서 긴 나눗셈을 크게 가속화합니다.
- NEON/SVE2: $\times 1.54$ 에서 $\times 2.11$ 의 속도 향상을 보였습니다 (QD 나눗셈은 두 개의 직렬 정규화 체인을 하나로 통합함에 따라 연산 횟수 비율인 1.51을 초과하여 $\times 2.11$ 에 도달).
- GB10 (계산 전용): $\times 1.25$ 에서 $\times 1.61$ 의 속도 향상을 보였습니다.
제곱근: 제안된 FMA는 베이스라인과 비교하여 정확도 손실 없이 $\times 1.51$ 에서 $\times 1.61$ 의 속도 향상을 달성했습니다. 이는 뉴턴 반복법(Newton iteration)이 반올림 단위(rounding unit)보다 훨씬 낮은 수준까지 수렴하기 때문에, 최종 에러가 모든 방법에서 공통적인 마지막 곱셈에 의해 지배되기 때문입니다.

4.3 단정밀도 기반 (DS/TS/QS)

알고리즘은 단정밀도 컴포넌트로 성공적으로 확장되었으며, 작업 정확도를 유지하면서 BF 베이스라인 대비 $\times 1.37$ 에서 $\times 1.83$ 의 속도 향상을 달성했습니다.

5. 의의 및 주장

본 논문은 제안된 분기 없는 융합 FMA가 기존의 분기 없는 곱셈과 덧셈의 두 단계를 단일 연산으로 성공적으로 통합한 최소한의, 기계 검증된 구성임을 주장합니다.

성능: 연산 횟수를 줄이고 의존성 체인을 단축함으로써 실질적인 속도 향상(나눗셈에서 최대 $\times 2.11$ , GEMM에서 GPU 기준 $\times 1.71$ )을 제공하며, 특히 고정밀도(TW/QW)에서 유리합니다.
정확성: 알고리즘은 엄격하게 검증되었습니다. 에러 범위와 FastTwoSum 전제 조건은 모든 정밀도에 대해 기계적으로 증명되었으며, 스칼라, SIMD, GPU 구현 간의 비트 단위 일치가 200,000회 이상의 테스트를 통해 확인되었습니다.
범용성: 이 접근 방식은 선형 대수에 국한되지 않습니다. MAC 연산에 크게 의존하는 나눗셈 및 제곱근 알고리즘을 효과적으로 가속화합니다.
교환 법칙: 일부 기존 분기 없는 접근 방식과 달리, 제안된 FMA는 병렬 리덕션에서의 재현성에 중요한 속성인 비트 단위 교환 법칙을 보존합니다.

저자들은 본 연구를 별도의 분기 없는 연산을 합성하는 것을 대체할 수 있는 실용적인 방안으로 제시하며, 정확성이나 증명 가능성을 희생하지 않고 다중 컴포넌트 산술 라이브러리에 "드롭인(drop-in)" 방식으로 가속을 제공한다고 강조합니다. 향후 연구로는 기계 검증 가능성을 유지하면서 연산 횟수를 더 줄이기 위해 Priest 스타일의 다른 재정규화 구조를 탐색하는 것이 제안되었습니다.