수학 공식을 비틀어 성능을 쥐어짜는 법: ILP와 Estrin's Scheme

대부분의 개발자들은 컴파일러를 맹신하는 경향이 있습니다. “-O3 플래그를 켰으니 알아서 최적화해주겠지”라고 생각하죠. 하지만 고성능 컴퓨팅, 렌더링 엔진, 혹은 HFT(고빈도 매매) 바닥에서 구르다 보면, 컴파일러가 놓치는 미세한 병목들이 눈에 밟히기 시작합니다.

최근 Hacker News에서 아주 흥미로운 글을 하나 읽었습니다. PSRayTracing 프로젝트를 진행하는 한 개발자가 아크사인(asin()) 함수의 근사치를 최적화하면서 겪은 과정인데, 단순히 수학 공식을 다른 방식으로 전개하는 것만으로 최신 CPU의 성능을 극한으로 끌어올린 사례입니다.

15년 넘게 C++ 코드를 프로파일링하며 밤을 새워본 엔지니어로서, 이런 종류의 마이크로 최적화(Micro-optimization)는 언제 봐도 즐겁습니다. 오늘은 이 글을 바탕으로 Instruction-Level Parallelism(ILP) 과 Estrin’s Scheme 이 어떻게 코드를 더 빠르게 만드는지 딥다이브 해보겠습니다.

Horner의 방법: 연산량은 줄였지만 파이프라인은 막혔다

그래픽스 프로그래밍에서 표준 라이브러리의 std::asin()은 종종 지나치게 무겁습니다. 그래서 보통 오차를 감수하더라도 다항식을 이용한 근사 함수(Approximation)를 사용하죠. 원작자는 처음에 Cg의 minimax 다항식 근사를 구현했습니다.

double asin_cg(const double x) {
    constexpr double a0 = 1.5707288;
    constexpr double a1 = -0.2121144;
    constexpr double a2 = 0.0742610;
    constexpr double a3 = -0.0187293;

    const double abs_x = abs(x);

    // Horner's method를 사용한 다항식 평가
    double p = a3 * abs_x + a2;
    p = p * abs_x + a1;
    p = p * abs_x + a0;

    const auto x_diff = sqrt(1.0 - abs_x);
    const double result = (Pi / 2.0) - (x_diff * p);

    return copysign(result, x);
}

여기서 주목할 부분은 p를 계산하는 과정입니다. 이는 수학 시간에 배운 Horner’s Method 입니다. 곱셈과 덧셈의 횟수를 최소화하는 우아한 방법이죠. 수식으로 풀면 다음과 같습니다.

p = ((a3 * x + a2) * x + a1) * x + a0

하지만 하드웨어 관점에서 이 코드는 치명적인 단점이 있습니다. 바로 데이터 의존성(Data Dependency) 입니다.

두 번째 줄의 p를 계산하려면 첫 번째 줄의 p 계산이 완전히 끝나야 합니다. 세 번째 줄 역시 마찬가지죠. 의존성 체인(Dependency chain)의 길이가 3입니다. 최신 CPU들은 Out-of-Order(OoO) 실행을 통해 여러 명령어를 동시에 처리할 수 있는 슈퍼스칼라(Superscalar) 아키텍처를 가지고 있지만, 이런 식으로 이전 결과값에 종속되어 있으면 CPU의 실행 유닛(ALU)들은 앞선 연산이 끝날 때까지 손가락만 빨고 기다려야 합니다.

Estrin’s Scheme: CPU에게 병렬 처리의 자유를 주다

원작자는 이 의존성 체인을 끊기 위해 공식을 다시 전개합니다. 이 기법을 Estrin’s Scheme 이라고 부릅니다.

// 원래 공식
p = ((a3 * x + a2) * x + a1) * x + a0

// 전개 및 재묶음
p = (a3 * x^3 + a2 * x^2) + (a1 * x + a0)
p = (a3 * x + a2) * x^2 + (a1 * x + a0)

이걸 코드로 옮기면 다음과 같이 변합니다.

const double x2 = abs_x * abs_x;
const double p = (a3 * abs_x + a2) * x2 + (a1 * abs_x + a0);

수학적으로 결과값은 100% 동일합니다. 연산 횟수는 곱셈이 하나 더 늘었죠. 하지만 성능은 오히려 빨라집니다. 왜 그럴까요?

이제 컴파일러와 CPU는 (a3 * abs_x + a2) 부분과 (a1 * abs_x + a0) 부분을 완전히 독립적으로 계산할 수 있습니다. 의존성 체인의 길이가 3에서 2로 줄어든 겁니다. CPU 내의 여러 ALU가 동시에 이 두 개의 항을 병렬로 계산(ILP)한 뒤, 마지막에 합치기만 하면 됩니다. 곱셈 한 번의 비용보다 파이프라인 스톨(Pipeline stall)을 방지해서 얻는 이득이 훨씬 큰 것이죠.

벤치마크와 아키텍처의 차이

원작자가 측정한 벤치마크 결과는 더욱 흥미롭습니다. CPU 아키텍처에 따라 이 최적화가 먹히는 정도가 달랐기 때문입니다.

  • Intel Core i7 (구형): 기존 대비 약 1.17배 속도 향상 (1.54x -> 1.80x)
  • AMD Ryzen 9: 속도 향상 거의 없음
  • Apple M4: Clang에서만 약간의 향상, 전체적으로 큰 차이 없음

개인적으로 이 결과는 매우 납득이 갑니다. 최신 Apple M4나 AMD Ryzen 아키텍처는 이미 거대한 ROB(Reorder Buffer)와 엄청나게 넓은 실행 포트(Execution Port) 대역폭을 가지고 있습니다. 즉, 하드웨어 자체가 워낙 깡패라서 짧은 의존성 체인 정도는 다른 명령어들을 섞어 실행하며 레이턴시를 숨겨버릴 수 있다는 뜻입니다. 반면, 리소스가 상대적으로 제한적인 구형 Intel 칩에서는 개발자가 명시적으로 ILP를 챙겨주는 것이 엄청난 차이를 만듭니다.

실제 레이 트레이서 렌더링 테스트에서는 전체 시간의 약 3% 속도 향상 을 얻었다고 합니다. “겨우 3%?”라고 생각할 수 있지만, 프로덕션 레벨의 렌더러에서 함수 하나 살짝 고쳐서 전체 성능을 3% 올렸다면 당장 PR 날리고 팀원들에게 박수받을 일입니다.

메모리 레이턴시 vs ALU 연산: LUT의 함정

Hacker News 댓글을 보면 “그냥 sin이나 asin 값들을 미리 계산해서 Look-Up Table (LUT)로 만들면 훨씬 빠르지 않냐?”라는 의견이 꼭 나옵니다. 원작자도 이를 테스트해 보았으나 오히려 느렸다고 언급했습니다.

이 의견에 저는 200% 동의합니다. 과거 90년대나 2000년대 초반에는 수학 연산이 비싸서 LUT가 진리였던 시절이 있었습니다. 하지만 2024년 현재, 메모리 접근은 죄악입니다.

L1 캐시 히트가 나더라도 3~4 사이클이 소모되는데, 그 시간이면 최신 CPU는 FMA(Fused Multiply-Add) 명령어를 이용해 부동소수점 연산을 몇 번이나 끝낼 수 있습니다. 캐시 미스라도 나는 날에는 수백 사이클이 날아가죠. 현대의 고성능 프로그래밍에서는 메모리 대역폭을 아끼고 ALU를 혹사시키는 것이 훨씬 유리합니다. “Math > Memory”는 이제 업계의 불문율입니다.

결론 (Verdict)

이런 종류의 마이크로 최적화가 모든 웹 백엔드나 CRUD 앱에 필요한 것은 절대 아닙니다. 하지만 게임 엔진, 물리 시뮬레이션, 렌더링, 혹은 퀀트 트레이딩 시스템처럼 핫 루프(Hot loop) 가 존재하는 도메인에서는 이야기가 다릅니다.

우리는 종종 코드를 짤 때 논리적인 연산 횟수(Big-O)에만 집착합니다. 하지만 진짜 성능을 쥐어짜야 할 때는 코드가 하드웨어 위에서 어떻게 스케줄링될지, 데이터 의존성은 없는지, CPU 파이프라인을 낭비하고 있지는 않은지 고민해야 합니다.

컴파일러는 훌륭한 도구지만, 마법사는 아닙니다. 결국 최상의 성능은 하드웨어의 특성을 이해하고 수학적 센스를 발휘하는 엔지니어의 손끝에서 완성됩니다.

References: