부동소수점 덧셈에는 결합법칙이 성립하지 않습니다. Half precision에서 0.5, 512, 512.5를 묶는 순서에 따라 1025 또는 1024가 나올 수 있습니다. Parallel library는 이 자유를 이용해 vectorization과 분할 reduction을 수행합니다. API가 sum이나 matrix multiplication을 약속해도 어떤 partial value를 먼저 합칠지는 명시하지 않을 수 있습니다.
Software를 CPU, BLAS backend, GPU generation, compiler 사이에서 옮기면 이 누락된 순서가 reproducibility 문제가 됩니다. Proprietary hardware와 optimized binary는 source inspection으로 알 수 없고 병렬 fused operation의 runtime trace도 해석하기 어렵습니다. Microsoft Research의 FPRev는 implementation을 black box로 두고 numerical output만으로 accumulation tree를 추론합니다[1].
도구의 목적은 더 정확한 값을 만드는 것이 아닙니다. 기존 답을 재현하거나 두 implementation을 비교하는 데 필요한 정확한 evaluation structure를 드러냅니다. Safety-critical, scientific, database, machine-learning code를 이전하기 전에 undocumented behavior를 testable specification으로 바꿀 수 있습니다.
두 leaf의 만남을 드러내는 상쇄
(n)개 값을 더하는 reduction을 생각할 수 있습니다. FPRev는 입력을 1로 채우고 위치 (i)를 큰 양수 (M), 위치 (j)를 (-M)으로 바꿉니다. Ordinary one을 두 큰 값에 더해도 값이 변하지 않을 만큼 magnitude를 고릅니다. (M)과 (-M)이 마침내 만나 상쇄된 뒤에 더해진 one만 output에 남습니다.
남은 integer는 위치 (i)와 (j)의 lowest common ancestor 아래에 leaf가 몇 개 있는지 알려 줍니다. 선택한 pair에 시험을 반복하면 hidden reduction tree 안의 distance를 얻습니다. Basic algorithm은 모든 pair를 열거해 bottom-up으로 tree를 만들고 FPRev는 모호한 subtree만 recursive하게 풀어 중복 probe를 줄입니다.
Security target이 없는 numerical side channel과 비슷한 구조입니다. Rounding behavior가 operation sequence의 structural information을 누출합니다. Public API만 사용하며 binary instrumentation이나 성능 계수기가 필요하지 않습니다. Behavior 자체를 관측하므로 compiler transformation과 hardware scheduling 결과도 포함됩니다.
Deterministic implementation이 전제입니다. 같은 입력이 실행마다 다른 reduction tree를 사용하면 하나의 inferred tree로 설명할 수 없습니다. FPRev는 fixed order의 diagnostic이며 nondeterministic atomic을 쓰는 runtime이 stable bit를 돌려 준다는 증명은 아닙니다.
Multi-term fusion을 표현하는 tree model
일반 addition과 fused multiply-add는 binary tree로 표현할 수 있습니다. Matrix accelerator는 여러 항을 align 및 truncate한 뒤 하나의 fused operation에서 누적할 수 있습니다. 이런 behavior에는 자식이 두 개보다 많은 node가 필요합니다. FPRev는 recovered subtree가 현재 node의 sibling인지 multiway parent인지 구분하도록 construction을 확장합니다.
논문은 tested operation cost를 (t(n))으로 둘 때 Ω((n t(n))) lower bound와 (O(n^2 t(n))) upper bound를 제시합니다. Basic method는 Θ((n^2 t(n)))이고 brute-force enumeration은 exponential하게 증가합니다. 실제 효율은 tree 형태에 따라 달라지며 어떤 구조는 적은 probe로 큰 subtree를 드러냅니다.
Low-precision format은 crafted value를 제한합니다. FP8은 긴 one list를 가릴 만큼 (M)의 dynamic range가 크지 않을 수 있고 float32 accumulator는 큰 모든 integer를 정확히 표현하지 못합니다. Modified algorithm은 one을 더 작은 exact term으로 바꾸고 완료한 subtree를 압축합니다. Cancellation relation은 유지하지만 arithmetic format마다 다시 검증해야 합니다.
출력으로 확인한 NumPy와 PyTorch 구조
FPRev는 Intel Xeon E5-2690 v4, AMD EPYC 7V13, Intel Xeon Silver 4210에서 NumPy 1.26을 시험했습니다. Single-precision sum은 세 CPU에서 같은 order를 사용했습니다. 8개 미만은 sequential, 8개에서 128개까지는 stride-eight partial sum과 pairwise combination을 쓰는 8-lane 구조였고 더 큰 입력은 parallelism을 늘렸습니다.
다른 NumPy operation은 BLAS implementation에 의존해 CPU 사이에서 같지 않았습니다. 8×8 matrix-vector 사례에서 24-vCore CPU 두 개는 output마다 product 32개를 2-way로 누적했지만, 40-vCore Intel system은 sequential하게 누적했습니다. Library name만으로 numerical behavior를 규정할 수 없다는 뜻입니다.
NVIDIA V100, A100, H100의 PyTorch 2.3에서도 같은 구분이 나왔습니다. Single-precision sum은 평가 device에서 같은 order였지만 BLAS 기반 operation은 달랐습니다. Half-precision Tensor Core matrix multiplication은 V100 5-way, A100 9-way, H100 17-way tree를 보였습니다. Volta, Ampere, Hopper의 4+1, 8+1, 16+1-term fused accumulation과 맞는 구조입니다.
논문에서 reproducibility에 안전하다는 표현은 시험한 hardware와 버전에서 equivalent했다는 뜻입니다. Future release, 다른 형태와 자료형, distributed collective에 대한 API guarantee가 아닙니다. Production qualification은 revealed tree와 함께 library, driver, compiler, device, operation, 형태, dtype metadata를 저장해야 합니다.
Regression test를 가능하게 하는 실행시간
16개 summand에서 brute force는 24시간을 넘을 수 있지만 BasicFPRev와 FPRev는 0.01초 아래에서 끝났습니다. 8,192개에서는 BasicFPRev가 100초를 넘고 FPRev는 약 1초가 걸렸습니다. Hardware 및 software compatibility matrix에서 실행할 수 있는 diagnostic이 된 것입니다.
시험한 NumPy system의 (n=256) 조건에서 FPRev는 BasicFPRev보다 dot product 13.0배, matrix-vector multiplication 32.3배, matrix multiplication 82.1배 빨랐습니다. Operation이 비쌀수록 피한 probe의 가치가 커집니다. Experiment는 실행시간이 1초를 넘으면 (n) 증가를 멈췄고 point마다 열 번 평균을 냈으므로 application speedup이 아니라 tool-runtime comparison입니다.
Output은 regression artifact로 쓸 수 있습니다. Vendor update가 tolerance를 만족하면서 bitwise result를 바꿀 수 있습니다. Tree comparison은 downstream application이 발견하기 전에 structural change를 알려 줍니다. Equivalence가 필요하면 새 backend가 old tree를 재현할 수 있고 bounded error만 중요하면 차이가 생긴 이유를 설명합니다.
따라서 qualification record에는 inferred structure와 probe condition이 함께 있어야 합니다. Masking magnitude, input length, tensor dimension, arithmetic type, warm-up policy, repetition count가 무엇을 관측했는지 결정합니다. Diagram만 저장하면 나중의 mismatch가 kernel 변경인지 다른 dispatch path 선택인지 구분할 수 없습니다. 일반 정확도 metric도 보존해야 합니다. Structural difference가 application error budget 안에서는 무해할 수 있고, 같은 tree라도 rounding mode가 달라졌을 수 있기 때문입니다.
Accumulation order 밖의 numerical behavior
FPRev 하나로 arithmetic implementation 전체를 규정할 수는 없습니다. Rounding mode, intermediate precision, denormal handling, contraction, overflow도 결과에 영향을 줍니다. 저자들은 Tensor Core accumulator precision과 rounding을 위한 추가 crafted experiment를 제안합니다. Tree가 같아도 node arithmetic이 다르면 bit는 달라질 수 있습니다.
Distributed reduction에는 계층이 하나 더 있습니다. Local kernel이 deterministic해도 AllReduce가 rank count, message size, runtime state에 따라 topology를 고를 수 있습니다. FPRev는 predetermined collective order를 검사할 수 있지만 dynamic communication library는 configuration마다 반복해야 합니다. Network nondeterminism이 하나의 tree가 아니라 tree distribution을 만들 수도 있습니다.
과거 order를 재현하면 성능을 잃을 수 있습니다. 한 SIMD width나 Tensor Core generation에 최적화한 tree는 다른 device를 충분히 쓰지 못합니다. Engineering은 bitwise identity, numerical tolerance, peak throughput 중 실제 contract를 정해야 합니다. FPRev는 판단 근거를 제공하지만 trade를 대신 결정하지 않습니다.
이 구분은 세 가지 deployment gate로 이어집니다. Bitwise-sensitive checkpoint는 같은 tree와 node arithmetic을 요구합니다. Numerical tolerance를 허용하는 inference는 task-level 정확도와 worst-case error 시험을 통과하면 바뀐 tree를 받아들일 수 있습니다. Exploratory workload는 release를 막지 않고 변경 사실만 기록할 수 있습니다. Gate를 나누면 diagnostic result가 자동 거부 조건이 되는 일을 피하면서도 silent kernel substitution을 model, simulation, database owner에게 드러낼 수 있습니다.
일반화할 insight는 black-box numerical testing으로 implementation structure를 복원할 수 있다는 점입니다. 세심하게 고른 value가 rounding difference를 ancestry query로 바꾸고 efficient recursive algorithm이 query를 tree로 만듭니다. Heterogeneous AI 및 HPC system에서 이 tree는 mathematical operation과 실제 hardware-specific program 사이에 빠진 interface가 됩니다.
출처와 저작권 안내
이 글은 Silicon & Systems가 작성한 편집 분석으로, algorithm과 case study, 한계를 우리 표현으로 다시 썼습니다. 원문의 문장, 표, 도판은 재수록하지 않았고 도판은 이 글을 위해 새로 만들었습니다. FPRev는 open source이며 전체 논문은 USENIX ATC 2025 발표 페이지에서 확인할 수 있습니다. 저작권은 저자에게 있습니다. 2025.