▲

2^51 진법 트릭 (2017)

 (chosenplaintext.ca)
1P by GN⁺ 5일전 | ★ favorite | 댓글 1개
  • 큰 정수 연산에서 발생하는 carry(자리 올림) 문제는 연산 병렬화를 어렵게 만드는 주요 원인임
  • x86 아키텍처에서는 carry 처리를 위한 adc 명령이 일반 add 명령보다 느리고, 연속 carry 처리는 병렬 실행을 제한함
  • Radix 2^51 표현법을 사용하면 carry 전파를 지연시켜 더 많은 덧셈을 빠르게 수행할 수 있음
  • 각 limb(부분 값)에 51 또는 52 비트만 할당하여, 나머지 상위 비트 공간을 carry 임시 저장소로 사용함
  • 이 테크닉은 추가적인 레지스터 사용과 변환 비용에도 불구하고, 실제로 2^64 진법보다 더 나은 성능을 제공함

빠른 덧셈과 뺄셈: carry 문제

  • 큰 정수 덧셈에서는 인간이 손으로 자리수 단위로 carry를 처리하는 것처럼, 컴퓨터도 carry 때문에 덧셈 알고리듬을 병렬화하기 어려움
  • 기본적으로 우리는 오른쪽(하위 자리)부터 하나씩 더하면서, 각 자리에서 발생하는 carry를 왼쪽(상위 자리)으로 올려줌
  • 만약 왼쪽부터 덧셈을 시작하면 이전 carry가 다음 자리 연산에 영향을 주기 때문에, 연산 순서를 병렬화할 수 없음

컴퓨터에서의 carry 처리

  • 컴퓨터는 64비트 정수 단위로 덧셈을 처리함
  • 256비트 정수를 64비트 limb 4개로 쪼개서 덧셈을 병렬로 처리할 수 있을 것처럼 보이나, 실제로는 overflow(carry)를 처리해야 올바른 결과가 만들어짐
  • x86에는 carry 처리를 자동으로 해주는 adc(add with carry) 명령어가 있음

성능 저하의 원인

  • adc 명령은 carry flag라는 추가 입력값을 필요로 해, 단순한 add에 비해 성능이 떨어짐
  • Haswell 아키텍처 기준으로, add는 여러 포트에서 병렬 실행 가능한 반면 adc는 직렬(순차) 실행이 불가피함
  • 특히 SIMD 명령(vpaddq 등)을 사용할 때 carry 없는 병렬 덧셈이 훨씬 빠름

carry를 지연시키는 아이디어 (종이 위 예시)

  • carry를 줄이기 위해, 자릿수 범위를 확장해 (예: 0-9에서 0-9, A-Z, *까지 총 37자리) 임시로 carry 없이 여러 수를 더할 수 있음
  • 이렇게 하면 carry 전파 없이 여러 덧셈을 진행하고, 마지막에 한 번에 carry를 정리(normalization)할 수 있음
  • 이 개념은 carry 누적과 전파를 분리해 최종 단계에서만 carry 처리를 하도록 함
  • 실제 연산에서는 자릿수 기준 값 이상의 값이 나왔다면, 오른쪽부터 차례로 carry를 누적 반영함

carry 지연의 컴퓨터 적용 (Radix 2^51 트릭)

  • 컴퓨터에서 carry 전파를 줄이기 위해 radix 2^51 표현 사용
  • 256비트를 64비트 4개 limb가 아니라, 51~52비트씩 5개 limb로 분할
    • 각 limb의 상위 12~13비트는 carry 임시 저장소로 기능
  • 이 방식에서는 limb마다 2^64 값 범위를 유지한 채, 실제 연산 시 carry가 쉽게 발생하지 않아서, 여러 연산을 carry 없이 병렬적으로 수행 가능
  • 약 2^13개의 연속 연산 후 한 번에 normalization(정규화) 필요
  • Haswell CPU 기준, radix 2^51 적용 후 carry 없는 단순 덧셈만 여러 번 수행하여 일반 radix 2^64보다 성능이 크게 향상됨
  • normalization을 위한 carry propagation은 마지막에 한 번만 수행

코드 예시

  • 5개 레지스터에 값을 나눠 담아, carry 없는 덧셈 가능
  • normalization은 각 limb의 상위 비트를 추출해 옆 limb에 더하고, 자신의 carry 값을 0으로 만드는 방식 반복

뺄셈에의 확장

  • 뺄셈도 비슷한 방식으로 적용 가능
  • 이때 carry는 음수도 되므로, limb를 signed integer로 취급
  • limb의 가장 높은 비트가 부호 비트로 할당되어, 덧셈에 비해 한 번에 처리 가능한 연산 횟수가 소폭 줄어듦

결론

  • carry 저항(지연) 테크닉은 limb 개수 증가와 변환 작업 추가에도 불구하고 전체 연산 성능을 실제로 크게 향상시킴
  • Radix 2^51 트릭은 대규모 정수 연산, 암호학 등 높은 성능을 요구하는 분야에서 널리 활용됨
  • 이 테크닉은 실제 하드웨어/알고리듬 성능을 최적화하는 중요한 아이디어임
▲
GN⁺ 5일전  [-]
Hacker News 의견

  • 2^51이라는 숫자를 보고 처음엔 double 타입에 정수 저장 관련 얘기인 줄 알았지만, 실제로 Integer를 double로 정확히 담을 수 있는 값은 2^53-1임을 깨달음

  • AVX512(그리고 AVX2도 어느 정도)에서 256비트 추가 연산을 상당히 효율적으로 구현할 수 있는 환경 제공, 더 많은 숫자를 레지스터에 담을 수 있다는 장점도 있음
    직접적인 예시는 아래 코드처럼 동작

__m256i s = _mm256_add_epi64(a, b);
const __m256i all_ones = _mm256_set1_epi64x(~0);
int g = _mm256_cmpgt_epu64_mask(a, s);
int p = _mm256_cmpeq_epu64_mask(s, all_ones);
int carries = ((g << 1) + p) ^ p;

__m256i ret = _mm256_mask_sub_epi64(s, carries, s, all_ones);

처리량까지도 개선되는 모습을 보여서 실제 코드 예시는 godbolt.org에서 볼 수 있음
이 논리를 512비트 덧셈까지 확장하는 것도 매우 단순함

  • 특히 특정 인텔 CPU 아키텍처에서는 AVX512 명령어 사용만으로도 전체 프로세서 클럭이 다운되어 일관되지 않거나 오히려 느린 전체 성능으로 이어질 수도 있다는 점 지적
    관련 참고는 stackoverflow 링크에서 확인할 수 있음

  • “13비트 말고 12비트를 쓰면 안되나?”라는 의문에 대해, 여기서는 가장 상위 비트(림)의 캐리 처리를 무시해서 오버플로우 시 wraparound 형식으로 동작하게끔 함
    그 결과 가장 상위 림에는 52비트를 할당함으로써, 다른 림보다 더 빨리 공간이 모자라지는 단점이 있지만, C 언어에서 무부호 정수 합산과 비슷하게 작동함
    그렇다면 최상위 림엔 64비트, 나머지 네 림엔 48비트씩 할당하는 방식은 어떤지 제안
    이러면 정규화 전 더 많은 연산 누적이 가능하고, 워드 정렬 등의 이점이 있음
    오버플로우 처리 특성도 동일함

    • 최상위 림만 64비트 할당할 경우, 두 숫자의 림을 더하면 너무 빨리 오버플로우가 발생
      예를 들어 둘 다 2^63값이면 바로 오버플로우
      wraparound 산술 연산에서야 상관없지만 일반적인 경우엔 무리임

    • 이런 구조라면 OP에서처럼 5개가 아닌 6개의 워드가 필요
      명령어도 더 많이 필요하게 됨

    • 목표가 256비트 수학을 5개의 64비트 레지스터로 해결하는 것에 있음
      즉, 각 워드마다 256/5 = 51.2비트 분배가 이상적
      이게 256비트 한정이라면 괜찮지만 범용 big-int 라이브러리엔 최적은 아님
      예전엔 캐리 하나에 정확히 1바이트를 쓰려고 했던 배경이 있었고, 바렐 쉬프터가 없었던 시절이면 정렬을 위해 64 중 56비트만 활용하는 걸 선호
      RISC-V에서는 하드웨어적으로 플래그가 없기 때문에 이런 논의가 더욱 중요

  • 현대 x86 CPU(예: Intel Broadwell, AMD Ryzen)에서는 Intel ADX 명령어를 활용해 2^51 radix 표현이 전통적으로 강세였던 상황(예: Curve25519)에서도 더 빠를 수 있음

  • 관련 논의 자료로

  • 핵심 교훈은, 연산들이 상호 독립적일 경우 연산을 더 많이 병렬로 실행시키는 쪽이 오히려 더 빠를 수 있음
    반면, 의존성으로 인해 순차적으로 실행해야만 한다면 오히려 연산이 적어도 느릴 수 있음
    이 아이디어는 긴 정수 연산뿐 아니라 다양한 영역에 적용 가능

    • 64비트 청크로 분할해 캐리 여부에 따라 두 가지 경우를 미리 병렬 실행하고, 이후 실제 캐리 결과에 따라 옳은 연산을 선택하는 방식 제안
      이 방식은 덧셈 횟수가 두 배가 되지만 전파 속도가 log(bits) 수준으로(선형이 아닌) 빨라짐

    • 이 기법을 잘 이해 못했던 부분은, 이 방법이 본질적으로 ripple carry가 N값을 더할 때 N-1번 실행되는 걸 한 번만 실행하도록 한 점
      캐리 처리 자체는 복잡해지지만 덧셈은 병렬화 가능
      단, 입력 숫자를 5개 레지스터 단위로 나누는 작업 자체도 병렬화되어야 전체 효율이 의미 있음

    • 이 규칙은 노드 수 만 단위를 가지는 슈퍼컴퓨터나 클라우드 레벨까지 확장 가능
      많은 코어를 쓸 수 있으면 오버헤드는 무시할 만한 수준

    • 이 아이디어는 NVidia도 관심을 갖고 있고 여러 영역에서 좋은 결과를 내고 있음

  • 제목에 의견을 추가하면 안 된다는 HN 가이드라인은 있지만, 너무 과장된 클릭 유도형 제목들을 선호하지 않음
    “일부 x86 아키텍처에서 carry 의존성 없이 64비트 정수 병렬 덧셈이 가능한 radix 2^51 트릭” 정도로 제한하는 게 더 정확하다고 생각

  • 이 글을 몇 달만 일찍 읽었어도 도움이 됐을 거라는 아쉬움
    버퍼를 임의의 진수로 인코드/디코드하는 과정에서 캐리가 버퍼 전체로 파급되어 알고리즘이 크게 느려지는 경험을 했음
    최종적으로는 '여유 공간'을 남겨 chunk로 분할해 캐리를 처리했는데, 이 트릭과 유사점이 있는 듯
    실제론 일부 비트를 낭비하는 대신 연산량이나 네트워크 대역폭을 절약하는 방법 선택
    이와 같은 캐리 처리 역시 후처리로 묶을 수 있을지 궁금함
    사실상 모든 이점을 가져갈 수 있는 구조가 되는지 희망사항임

  • x86_64 환경만 쓰던 경험을 통해서, RISC-V에서 carry flag가 없어도 꼭 잘못된 접근은 아니라는 점을 명확히 보여줌

    • 이 방식 외에도 64비트 림을 유지하면서 모두 uint64_t 변수로 carry-safe 덧셈을 하는 방법 설명
      아래와 같은 흐름
    s0 += a0;
s1 += a1;
s2 += a2;
s3 += a3;
c0 = s0 < a0; // RISC-V sltu
c1 = s1 < a1;
c2 = s2 < a2;
if (s1 == -1) goto propagate0;
check_s2:
if (s2 == -1) goto propagate1;
add_carries:
s1 += c0;
s2 += c1;
s3 += c2;
goto done;
propagate0: c1 = c0; goto check_s2;
propagate1: c2 = c1; goto add_carries;
done:

    관건은, 덧셈 결과(림)이 모두 1이 아닐 때, 해당 림의 캐리 아웃은 캐리 인에 의존하지 않고 단순히 원래 값을 더한 결과에만 의존함
    반면 값이 모두 1이면 캐리 아웃=캐리 인
    예측이 거의 불필요한 분기 구조라면 완벽히 병렬 실행 가능
    확률적으로 2^64분의 1에만 느려지지만, 4-와이드 머신 등에선 큰 이득 없음
    8-와이드 머신 또는 8-림 구조에서는 의미 있는 성능향상
    x86_64엔 안 맞지만 Apple M* 시리즈처럼 8-와이드 머신이면 활용 가능성
    Tenstorrent의 8-와이드 RISC-V Ascalon 프로세서, Ventana, Rivos, XiangShan 등에서 미래가 기대
    SIMD 구조, 빠른 1-lane shift(slideup) 명령 있는 구조에선 효과 극대화

    • 캐리-세이브 덧셈이 항상 add-with-carry보다 뛰어난 게 아님
      두 종류의 multi-word addition 알고리즘은 상호 대체 불가, 각자 장단점이 있음
      그러므로 ADC/SBB 명령은 ISA에 기본 포함, 레지스터 기반 플래그 저장도 가능
      RISC-V에서 더 심각한 단점은 integer overflow flag가 없다는 점
      오버플로 감지를 위한 SW 우회가 필요할 때 성능 하락이 carry 비트 우회보다 훨씬 큼

    • RISC-V에서 carry flag가 없는 건 C 언어가 바이너리 carry flag를 무시한 것에서 파생
      실제로는 carry flag 활용 빈도가 많이 낮음

    • 나만 “carry flag가 어차피 느리면 risc5 gmp 논란은 왜 있었나?”라는 생각한 게 아니었음

  • 'Radix trick'은 데이터 구조에도 적용 가능
    Okasaki의 'Purely Functional Data Structures' 책에도 흥미로운 예시 존재

답변달기