2^51 진법 트릭 (2017)

 (chosenplaintext.ca)
1P by GN⁺ | ★ favorite | 댓글 1개
  • 큰 정수 덧셈은 보통 64비트 limb로 쪼개 처리하지만, 자리올림 전파가 생기면 현대 CPU의 병렬 실행 이점을 제대로 쓰기 어려움
  • x86의 adc는 이전 연산의 carry flag에 의존해 명령 체인을 직렬화하므로, Intel Haswell처럼 여러 add를 병렬 실행할 수 있는 구조에서도 병목이 됨
  • radix 2^51 표현은 256비트 값을 네 개의 2^64 자리 대신 다섯 개의 2^51 자리로 나눠, 각 limb의 남는 상위 비트를 중간 자리올림 저장 공간으로 활용함
  • 자리올림을 제거하는 방식은 아니며, 여러 번의 덧셈 동안 전파를 지연한 뒤 마지막 정규화 단계에서 한꺼번에 처리함
  • Haswell에서의 간단한 벤치마크에서는 변환 비용을 포함해도 세 번의 덧셈부터 radix 2^64 방식보다 빨랐고, 반복 횟수가 늘수록 이점도 커짐

큰 정수 덧셈에서 자리올림이 병목이 되는 이유

  • 종이에 하는 긴 덧셈은 1의 자리부터 오른쪽에서 왼쪽으로 진행함
    • 각 자리의 결과가 오른쪽 자리에서 넘어오는 자리올림에 의존하기 때문임
    • 왼쪽부터 더하면 나중에 발생한 자리올림 때문에 이미 계산한 앞자리 결과를 다시 고쳐야 함
  • 큰 정수 덧셈도 같은 제약을 가짐
    • 256비트 정수 x와 y를 네 개의 64비트 limb로 나누면 같은 위치의 limb끼리 더할 수 있음
    • 낮은 limb에서 오버플로가 나면 그 1을 더 높은 limb로 넘겨야 함
  • x86의 adc는 이 전파를 처리하는 명령임
    • 이전 연산의 오버플로 여부를 보고 필요한 경우 1을 더함
    • 올바른 256비트 덧셈은 최하위 limb부터 add, adc, adc, adc 순서로 이어짐

adc가 현대 CPU에서 느려지는 구조

  • adc는 대체로 일반 add보다 실행 비용이 큼
    • adc는 carry flag라는 세 번째 입력을 사용하므로 add보다 복잡함
    • add보다 덜 자주 쓰이기 때문에 CPU 설계자가 adc 성능 최적화에 칩 면적을 투입할 유인이 작음
  • 더 큰 문제는 명령 의존성임
    • Intel Haswell에서 단일 add는 실행에 1사이클이 걸림
    • 이상적인 조건에서는 Haswell이 한 사이클에 최대 4개의 add를 실행할 수 있음
    • Haswell에는 8개의 실행 포트가 있고, 그중 4개가 정수 add를 실행할 수 있음
  • 독립적인 add 네 개는 병렬 실행되기 쉬움
    • 반면 adc 체인은 각 명령이 이전 명령의 carry flag 출력에 의존함
    • CPU는 이 명령들을 병렬화하지 못하고 순서대로 실행해야 함
  • SIMD에서는 손실이 더 커짐
    • vpaddq는 네 개의 64비트 덧셈을 동시에 수행함
    • Haswell은 한 사이클에 두 개의 vpaddq를 실행할 수 있음
    • 자리올림 처리를 위해 이 병렬성을 포기하면 성능 이점이 줄어듦

종이 덧셈으로 보는 자리올림 지연

  • 10진 자리값은 유지하되, 각 자리에 들어갈 수 있는 문자를 넓히면 자리올림을 늦출 수 있음
    • 일반 0-9 대신 A-Z, *까지 더해 총 37개 문자를 사용함
    • 하지만 진법 자체는 37진법이 아니라 여전히 10진 자리값을 유지함
  • 한 자리가 9를 넘어도 즉시 자리올림할 필요가 없어짐
    • 29 + 1은 30으로 쓸 수도 있지만 2A, 1K, U처럼도 표현 가능함
    • 두 수의 각 자리가 모두 9 이하로 정규화되어 있다면 덧셈 중 자리올림을 미룰 수 있음
  • 모든 입력에 항상 적용되지는 않음
    • 9 + W처럼 이미 큰 자릿값이 들어 있으면 자리올림이 필요함
    • 정규화된 수끼리는 최대 네 개까지 더해도 자리올림 없이 표현 가능함
  • 마지막에는 다시 일반 10진 표현으로 정규화해야 함
    • 오른쪽부터 각 자리에서 몇 개의 10이 들어 있는지 계산함
    • 그만큼을 현재 자리에서 빼고 다음 자리로 넘김
  • 핵심은 자리올림 전파를 없애는 것이 아니라, 중간 계산 동안 저장해 두고 마지막에 한 번 전파하는 데 있음

컴퓨터에서의 radix 2^51 표현

  • 256비트 값을 네 개의 2^64 limb로 나누면 각 limb는 0부터 2^64−1까지 값을 가질 수 있음
    • 각 limb를 2^64 진법의 자리로 보는 방식임
  • 하드웨어의 64비트 정수 범위는 넓힐 수 없으므로 진법의 크기를 줄임
    • 256비트 값을 네 개의 2^64 자리 대신 다섯 개의 2^51 자리로 나눔
    • 각 limb는 여전히 64비트 정수로 저장되지만 실제 값은 51비트 또는 52비트만 사용함
  • 남는 상위 비트는 중간 자리올림 저장 공간이 됨
    • 각 limb에는 원래 숫자의 51비트 또는 52비트가 들어감
    • 나머지 12비트 또는 13비트가 계산 중 발생한 자리올림을 담음
  • 이 기법은 암호학 문헌에서 radix 2^51 representation으로 불림
  • 정규화된 수라면 2^64개의 가능한 limb 값 안에서 최대 2^13개를 더하기 전까지 상위 13비트 오버플로를 걱정하지 않아도 됨

52비트 최상위 limb와 정규화

  • 최상위 limb에는 52비트를 할당함
    • 나머지 limb는 51비트를 사용함
    • 최상위 limb의 자리올림은 무시해 2^256−1을 넘는 경우 감싸도록 처리함
    • 이는 C의 일반 크기 unsigned 정수 덧셈이 오버플로 시 감싸는 방식과 같음
  • radix 2^51 덧셈 코드는 adc 체인을 쓰지 않고 다섯 개의 add를 독립적으로 실행함
    • 네 개의 2^64 limb 방식보다 add 수는 4개에서 5개로 늘어남
    • 대신 carry flag 의존성이 없어 병렬 실행이 가능함
  • 정규화 단계에서는 각 limb의 상위 비트를 꺼내 다음 상위 limb에 더함
    • shr 51로 carry 부분을 추출함
    • and 0x0007FFFFFFFFFFFF로 51비트 아래만 남김
    • 최상위 limb는 and 0x000FFFFFFFFFFFFF로 정리함
  • 정규화는 지연해 둔 자리올림 전파를 마지막에 수행하는 단계임
    • 중간 덧셈에서는 carry flag 의존성을 만들지 않음
    • 최종적으로 각 limb를 다시 허용 범위 안으로 맞춤

성능 결과와 뺄셈 확장

  • 간단한 벤치마크에서 radix 2^51 덧셈은 Haswell CPU에서 더 빠른 결과를 보임
    • radix 2^51 표현으로의 변환과 복귀 비용까지 포함함
    • 세 번의 덧셈만으로도 radix 2^64 덧셈보다 빨랐음
    • 덧셈 횟수가 늘수록 절감 효과도 함께 커짐
  • 같은 아이디어는 뺄셈에도 확장할 수 있음
    • 뺄셈에서는 자리올림이 음수 carry가 됨
  • 뺄셈을 지원하려면 limb를 unsigned가 아니라 signed 정수처럼 다룸
    • 각 자리값은 양수 또는 음수가 될 수 있음
    • 각 limb는 양수 carry와 음수 carry를 모두 저장할 수 있음
  • 이 변경에는 비용이 따름
    • 각 limb의 최상위 비트가 부호 비트로 예약됨
    • 정규화 사이에 수행 가능한 연산 수가 2^13에서 2^12로 줄어듦
  • 데이터를 더 많은 레지스터에 나누고 연산 수가 늘어나더라도, 자리올림 의존성을 줄이면 전체 성능이 개선될 수 있음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 최상위 limb를 64비트로 두고 나머지 네 limb를 각각 48비트로 두면 안 되는지 궁금함
    정규화 전 더 많은 덧셈을 누적할 수 있고, 명령어 집합에 유용한 기능이 있다면 분할·정규화 때 워드 정렬도 활용할 수 있으며, 오버플로 특성도 같아 보임

    • 목표 중 하나가 64비트 레지스터 5개로 256비트 연산을 하는 것이라면, 각 워드에 256/5 = 51.2비트를 쓰는 셈이라 어느 정도 이상적인 배치로 보임
      범용 큰 정수 라이브러리라면 최적은 아닐 수 있고, 예전에는 임의 비트 시프트를 효율적으로 하는 배럴 시프터가 없어서 캐리에 정확히 1바이트를 남기고 64비트 중 56비트를 쓰는 식이 좋았을 것임
      RISC-V는 플래그가 없기 때문에 이 논의가 꽤 관련 있음
    • 두 인코딩된 숫자의 최상위 limb를 더하면 너무 빨리 오버플로남
      예를 들어 둘 다 2^63이면 바로 넘치고, 래핑 산술에는 괜찮을 수 있지만 일반적인 경우에는 맞지 않음
    • 그렇게 하면 256비트 값을 담는 데 원문 방식의 5워드가 아니라 6워드가 필요하고, 따라서 덧셈 명령도 더 많아짐

  • AVX512, 그리고 어느 정도는 AVX2로도 256비트 덧셈을 꽤 효율적으로 구현할 수 있고, 레지스터에 더 많은 숫자를 담는 장점도 있음
    _mm256_add_epi64, 비교 마스크, 캐리 마스크를 조합하는 식이며 처리량도 더 좋아 보임: https://godbolt.org/z/e7zETe8xY
    512비트 덧셈으로 바꾸는 것도 간단하고, 그때는 개선 폭이 더 클 것임

  • 충분히 최신 x86 CPU, 예를 들어 Intel Broadwell이나 AMD Ryzen에서는 ADX를 쓸 수도 있고, radix 2^51 표현이 전통적으로 유리했던 Curve25519 같은 상황에서도 요즘은 더 빠를 수 있음
    [1] https://en.wikipedia.org/wiki/Intel_ADX

  • 관련 글로는 예전의 radix 2^51 trick 스레드들이 있음
    The radix 2^51 trick - https://news.ycombinator.com/item?id=33706153 - 2022년 11월
    The radix 2^51 trick (2017) - https://news.ycombinator.com/item?id=23351007 - 2020년 5월

  • 핵심은 연산 수가 더 많아도 대체로 독립적이면 병렬 실행이 가능해서 더 빠를 수 있다는 것임
    반대로 연산 수가 적어도 데이터 의존성 때문에 직렬로 실행해야 하면 더 느릴 수 있고, 이 아이디어는 긴 정수 연산보다 훨씬 넓게 적용됨

    • 다른 접근으로는 일반적인 64비트 조각을 쓰되, 각 덧셈을 캐리 있는 경우와 없는 경우로 병렬 추측 실행한 뒤 낮은 자리 덧셈의 캐리 결과에 따라 올바른 쪽을 선택할 수 있음
      덧셈 횟수는 두 배가 되지만 캐리 전파 시간을 선형이 아니라 log(bits)로 줄일 수 있음
    • 이해가 잘 안 됐던 부분은, 여기서 보인 기법이 N개 값을 더할 때 ripple carry가 N-1번이 아니라 한 번만 일어나게 하는 데 초점이 있어 보인다는 것임
      캐리 연산은 더 복잡하지만 실제 덧셈을 병렬화할 수 있음
      그런데 애초에 입력 숫자를 5개 레지스터 묶음으로 나눠야 하니, 전체적으로 이득을 보려면 그 분할도 병렬화 가능해야 하는 것 아닌가 싶음
    • Nvidia가 그 일반 아이디어를 파고들고 있고, 몇몇 분야에서 꽤 유망한 결과를 내는 것처럼 보임
    • 이 규칙은 멀티 노드 슈퍼컴퓨터나 클라우드까지 확장됨
      10,000개 코어를 동원할 수 있으면 오버헤드는 무시할 만함

  • x86_64만으로 작업한 사람이 RISC-V가 캐리 플래그를 생략한 게 틀리지 않았다는 점을 아주 잘 보여줌

    • 64비트 limb를 유지하면서도 다른 방식으로 할 수 있음
      핵심 통찰은 특정 limb 위치의 합이 전부 1이 아닌 한, 그 위치에서 나가는 캐리는 들어오는 캐리에 의존하지 않고 원래 그 위치의 덧셈이 캐리를 만들었는지에만 의존한다는 것임
      합이 전부 1이면 나가는 캐리는 들어오는 캐리와 같음
      이를 거의 항상 not-taken으로 예측되는 조건 분기로 표현하면, 여러 조건 분기를 같은 클럭 사이클에 not-taken으로 예측할 수 있다는 전제에서 각 명령 블록이 완전히 병렬로 실행될 수 있음
      2^64번에 한 번은 매우 느리게 실행됨
      4-wide 머신에서 4-limb 숫자라면 adc보다 이점이 없지만, 8-wide 머신에서 8-limb 숫자라면 이득이 커지기 시작함
      현재 x86_64에는 별 도움이 안 될 수 있으나, M1도 8-wide인 Apple M 시리즈에서는 가능성이 있고 Arm ISA 때문에 우회가 까다로울 수 있음
      Tenstorrent의 8-wide RISC-V Ascalon이 올해 말이나 2026년 초에 나오면 Ventana, Rivos, XiangShan 등과 함께 실제로 확인할 수 있을 것임
      빠른 1-lane shift가 있다면 넓은 SIMD에서도 더 잘 동작하며, RISC-V에서는 이를 slideup이라고 부름
    • carry-save addition이 add-with-carry보다 나쁜 흔한 경우가 아직 많음
      두 가지 다중 워드 덧셈 알고리즘은 서로를 대체할 수 없고 용도가 다르므로, 괜찮은 ISA에는 ADC/SBB 명령이 들어가며 추가 비용도 미미함
      전용 플래그 레지스터가 꼭 필요한 것도 아니고, 어떤 ISA는 필요할 때 캐리·빌림 플래그를 범용 레지스터에 저장함
      RISC-V에서 캐리가 없는 것은 최악의 특징은 아니며, 더 나쁜 건 정수 오버플로 플래그가 없다는 점임
      안전하게 작성됐다고 주장하는 프로그램에는 정수 오버플로 감지가 필수인데, 이를 소프트웨어로 우회하면 캐리 부재 우회보다 달성 가능한 성능을 훨씬 더 낮춤
    • 이 흐름은 결국 C가 캐리 플래그를 생략한 데서 내려온 결과이고, 현실에서는 캐리 용도로 거의 쓰이지 않게 됨
    • 캐리 플래그가 어차피 느리다면 “RISC-V GMP 논란이 대체 뭐였지?”라는 생각을 한 사람이 나뿐만은 아니었음

  • 이 radix trick은 자료구조에도 적용됨
    Okasaki의 책 『Purely Functional Data Structures』에 좋은 예시가 있음

  • 몇 달 전에 이 글을 봤더라면 좋았을 것 같음
    임의의 진법으로 버퍼를 인코딩·디코딩하려다, 캐리가 버퍼 끝까지 전파될 수 있고 그 때문에 알고리즘이 크게 느려진다는 결론에 너무 늦게 도달했음
    결국 해결책도 이 트릭과 비슷한 점이 있었는데, 버퍼를 청크로 나누고 캐리를 처리할 여유 공간을 남겨뒀음
    정확히 같지는 않고, 약간의 낭비 비트를 두어 저장 공간이나 네트워크 대역폭을 아주 조금 더 쓰는 대신 계산을 줄였음
    이런 식으로 캐리를 모아뒀다가 나중 단계에서 해소하면 두 마리 토끼를 잡을 수 있을지 궁금하지만, 희망사항일 수도 있음

  • HN 가이드라인상 제목을 편집하지 말라는 건 알지만, 작은 주장을 너무 넓게 부풀리는 클릭베이트 제목은 별로임
    이 글 제목은 “일부 x86 아키텍처에서 캐리 의존성 때문에 파이프라인을 늦추지 않고 64비트 정수를 병렬로 더하는 radix 2^51 트릭” 정도였어야 함

답변달기