Superoptimizing an FPU emulator
FPU 에뮬레이터를 슈퍼최적화하기
저자는 부동소수점 값의 비트 표현에서 최하위 비트에 해당하는 값을 구하는 분기문을 없애려고, 후보 수식을 열거하고 테스트 사례로 검증하는 슈퍼최적화기를 만들었습니다. 검색기는 사람이 쉽게 떠올리기 어려운 비트 연산 조합을 찾아냈고, 저자는 이를 개발 중인 FPU 에뮬레이터에 적용했습니다.
- 주제
에디터 노트
이 사례에서 설득력 있는 부분은 후보 생성과 중복 제거를 결합해 사람이 놓친 비트 연산 재작성을 찾았다는 점입니다. 다만 정확성 검사는 대표 입력에 기대며, 반례를 보태 반복하는 방식입니다. 본문은 후보가 어떻게 나왔는지 설명하지만 전체 연산 집합이나 테스트 입력 수, 모든 입력에 대한 증명은 제시하지 않습니다. 따라서 발견한 수식의 영리함과 보편적 정확성은 구분해야 합니다. 댓글의 LC-3 경험은 탐색 공간을 줄이는 일이 실용화의 난점임을 짚고, FFTW 비교는 후보를 실제 하드웨어에서 측정해 선택하는 접근을 떠올립니다. 이 글은 수식 검색과 테스트 기반 검증을 다루며 성능 측정 결과까지 제시하지는 않습니다. 에뮬레이터 코드에 반영한 선택이 실제 실행 시간에서도 이득인지 판단할 근거는 자료에 없습니다.
AI 요약
컴파일러는 기계적인 코드 변환에는 능숙하지만, 문제를 푸는 새로운 알고리즘을 찾아내지는 못하는 경우가 많습니다. 저자는 부동소수점 계산 라이브러리를 만들면서 비트 표현을 이용해 특정 값을 계산하는 함수를 구현했습니다. 처음에는 비트 표현에서 최하위 set bit를 제거한 값과 원래 값을 빼는 방식으로 처리했지만, 2의 거듭제곱에서는 별도 분기가 필요했습니다. 이 분기가 흔한 경우의 실행을 늦추고 잘못 예측될 수도 있어, 분기 없이 같은 결과를 내는 수식을 찾고자 했습니다.
수식 후보를 열거하고 검증하기
저자는 가능한 수식을 직접 찾는 대신, loop-free 연산 수식을 무차별 탐색하는 슈퍼최적화기를 작성했습니다. 정리 증명기로 모든 후보의 정확성을 확인하기에는 느리다고 보고, 대표 입력 몇 개에서 후보를 평가하는 방식을 택했습니다. 반례가 나오면 입력 목록에 추가하고 검색을 다시 수행합니다. 따라서 테스트 입력에 맞는 후보를 찾는 과정이지, 그 자체로 모든 부동소수점 입력에 대한 정확성을 증명하는 과정은 아닙니다.
검색은 연산 개수별로 수식을 구성합니다. 더 작은 수식 두 개를 골라 연산 하나로 결합하고, 각 입력 테스트 사례에서 나온 결과를 수식의 값으로 저장합니다. 같은 결과 벡터를 내는 수식은 중복으로 제거합니다. 마지막 단계에서는 메모리와 시간을 아끼기 위해 중복 제거를 건너뛰고 조건에 맞는 후보를 출력합니다. 검색 공간이 커지는 문제를 테스트 결과의 중복 제거로 줄이는 구조입니다.
비트 연산 조합이 만든 후보
검색 결과에는 지수 마스크를 이용한 수식이 여럿 나왔습니다. 저자는 그중에서도 부분식을 재사용해 연산 하나를 줄이는 수식에 놀랐다고 설명합니다. 먼저 a를 원래 비트 표현에서 가수부를 지운 값으로 둡니다. 이어 a - x.to_bits()로 가수부 비트의 음수에 해당하는 값을 만들고, 이를 x.to_bits()와 AND 연산합니다. 그 결과를 a와 비교해 최종 값을 계산합니다. 저자는 이 조합이 x & 가수부 마스크를 별도로 계산하는 대신, 뺄셈과 부호 반전을 결합해 연산을 절약한다고 풀이합니다.
이 후보는 2의 거듭제곱에서 부호 비트를 뒤집는 방식으로 동작하지만, 저자가 구현하는 함수에서는 그 차이가 문제가 되지 않는다고 합니다. 해당 코드는 작업 중인 FPU 에뮬레이터에 들어갔습니다.
Lobsters 반응
- @kneeawn — 저도 LC-3 어셈블리를 슈퍼최적화하려고 시도해 봤는데, 의미 있는 결과를 얻으면서 탐색 트리를 가지치기하는 방법을 찾기가 꽤 어렵습니다. 조합의 수가 정말 빠르게 커지네요. 언젠가 STOKE가 어떻게 작동하는지 더 살펴보고 싶습니다.
- @stip — 예전 FFTW가 여러 FFT 커널을 생성한 다음 하드웨어에서 직접 벤치마크해 가장 빠른 것을 골랐던 방식이 떠오릅니다.
원문: PurpleSyringa / 번역·요약: Trawling