흔한 CPU 관련 뉴스를 보면 항상 언급되는 것이 슈퍼파이 값인데

측정 결과가 올라오면 하는 소리들이 파이 값은 별로 의미가 없다는 것인데요.

저는 이 말이 그다지 옳지 않다고 생각합니다...

슈퍼파이는 1995년쯤에 나왔으니, 당시라면 기껏해봤자 펜티엄 시리즈가 최고이던 시절입니다.

뭐, 기껏해야 지원되는건 내장된 FPU뿐이고, SIMD 명령도 기껏해야 MMX가 고작이었지요. 자 이제 본론으로 들어가겠습니다.

긴 자리의 정수/부동소수점 연산에서 가장 중요한 것은, 덧셈? 뺄셈? 곱셈? 나눗셈? 정답은 곱셈입니다.

덧셈, 뺄셈은 충분히 빠르디 빠르기 때문에 왠만큼 오래된 CPU라도 1사이클 정도면 가볍게 완료합니다. 하지만 곱셈, 나눗셈은 얘기가 다르죠.

게다가 긴 자리의 정수/부동소수점 연산은 일반적인 데이터타입을 쓰기도 어렵기 때문에 자료구조(혹은 긴 자리 타입 클래스)를 직접 만드는 방법을 써야 합니다.

수학적으로 곱셈 알고리즘을 이용하면 나눗셈 알고리즘을 구현할 수 있습니다.(Newton's Method) 그리하여 곱셈 알고리즘이 빠르다면 나눗셈 또한 덩달아 빨라집니다. 일단 몇가지 나열해 보면..

1. basecase 곱셈 : 학교에서 배운 곱셈법이라 하여 schoolbook 곱셈이라고도 합니다. 가장 효율은 좋지 않으나, 자릿수가 매우 짧다면 잔여계산이 필요하지 않으므로 많이 사용되는 방법입니다. 시간 복잡도는 O(n^2)

2. Karatsuba 곱셈 : 러시아 수학자 Karatsuba가 만든 곱셈으로, 시간 복잡도가 O(n^2)보다 작은 곱셈 알고리즘들 중 최초로 발견된 알고리즘입니다. 통상적인 긴 자릿수 곱셈을 완료하기 위해선 곱셈 연산이 4번에 걸쳐서 수행되지만 Karatsuba 곱셈은 곱셈을 3번만 하고 덧셈연산을 더 많이 함으로써 시간 복잡도가 O(n^1.58)정도로 떨어집니다. 곱셈 한번 할 시간을 덧셈 몇 번하는 시간으로 떼우겠다는 걸로 생각하면 되겠습니다. 다만 덧셈연산이 많아지므로 제법 큰 수로 수행해야 효과가 있습니다.

3. Schönhage–Strassen 곱셈 : 곱셈에 이산 푸리에변환과, 역 이산 푸리에변환을 적용시켜 큰 수의 곱셈을 매우 빠르게 수행할 수 있는 알고리즘입니다. 시간 복잡도는 O(n log n * log (log n)). 몇 만자리 계산 이상부터는 보통 이 알고리즘이 적용됩니다.

아무래도 보통은 100만 자리이상 계산이 수행되다보니 3번 알고리즘이 많이 수행됩니다. 푸리에 변환을 곱셈에 이용하기 위해서 당연히 FFT를 통해 알고리즘이 구현됩니다. FFT를 구현하려면 결국 사용되는건 FPU겠지요. 실제로 슈퍼파이를 디버그 프로그램으로 분석해봐도 ST 레지스터가 매우 활발히 돌고 있음을 볼 수 있습니다.

물론 슈퍼파이는 한 물 간 프로그램이 맞습니다. 요즘 나온 최신기술을 사용하지 않으니깐요. 하지만 그렇다고 해서 현 세대 프로세서의 성능 측정에 부적합한 물건은 아닙니다. 아직까지 FPU의 성능은 중요합니다. 게임이든 멀티미디어 프로그램이든 스칼라 연산이 여전히 빈번하기 때문이죠.

영상이나 그림파일 처럼 embarrassingly parallel하다면 모를까.. 실제 프로그래밍시에 SSE 같은 확장 명령을 적용하는게 그리 쉬운 일이 아닙니다. 알고리즘 구조도 SSE에 맞게 변경 해야하고(첨부터 딱 맞게 떨어지면 모를까...), 유지보수가 어려워집니다. 이식에서도 불리해집니다. 물론 요즘은 컴파일러가 SSE 명령을 잘 활용해서 번역해주는 편이긴 하지만 아직은 손으로 짠 것만 못한 수준이긴 하죠.

그래도 제 말에 뭔가 찝찝한 구석이 있다면 y-cruncher라는 프로그램을 추천합니다. 멀티 쓰레드를 통한 파이 계산을 지원하며, 푸리에 변환을 위해 내부적으로 SSE 및 AVX까지 빡빡하게 사용한 무시무시한 놈이니깐요. 아마 한 번 써보시면 파이값은 의미없다는 소리 더이상 못하실걸요?