Radix 2^51 림브는 캐리를 지연시켜 캐리 전파 덧셈 체인을 앞선다

64비트보다 넓은 수를 더하는 일은 쉬워야 한다. 각 256비트 정수를 64비트 조각 네 개로 나누고, 더한 뒤, 넘치는 부분을 위로 전파하면 된다. 문제는 그 오버플로다. 캐리 없이는 답이 틀리므로, 올바른 버전은 최하위 림브부터 x86의 캐리 포함 덧셈 명령(adc)을 연쇄시킨다. 현대의 비순차 실행 CPU에서는 그 연쇄가 잘못된 병렬 코드보다 느리다. adc는 더 무거운 명령이고, 각각이 이전 명령이 만든 캐리 플래그에 의존하기 때문이다. Haswell CPU는 사이클당 최대 네 개의 독립적인 덧셈을 발행할 수 있지만, 연쇄된 adc는 직렬로 실행된다.

암호학 문헌에서 radix 2^51 표현으로 알려진, 직관에 반하는 해법은 각각 레지스터보다 작은 림브를 더 많이 쓰는 것이다. 명백한 접근이 256비트를 기수 2^64 자릿수 네 개로 나누는 반면, 이 접근은 기수 2^51 자릿수 다섯 개로 나눈다. 각 64비트 림브는 여전히 자기 자릿수를 담지만, 상위 12–13비트는 캐리가 쌓일 수 있는 공간으로 비어 있다. 그 여유 덕분에 정규화된 값을 더하면 여유 비트가 찰 때까지, 대략 2^13번의 덧셈까지는 캐리가 전혀 생기지 않으므로 모든 덧셈이 독립적이고 프로세서가 이를 병렬로 스케줄한다.

캐리는 제거되는 것이 아니라 지연될 뿐이다. 여유가 소진되면 한 번의 정규화 패스가 각 림브의 오버플로를 위 림브로 옮기고 여유분을 비우며, 뺄셈도 림브를 부호 있는 값으로 취급하여 여유 비트 하나를 대가로 같은 방식으로 동작한다. 저자가 Haswell 머신에서 수행한 간단한 벤치마크에 따르면, radix-2^51 덧셈은 그 표현으로 변환하고 다시 변환하는 비용을 포함해도 단 세 번의 덧셈만으로 이미 radix-2^64 덧셈보다 빨랐고, 덧셈이 더 쌓일수록 절감 효과는 커졌다.

이 글은 먼저 종이 위에서 직관을 세운다. 기수 10에서 각 자릿수의 범위를 넓혀 9를 넘어 셀 수 있게 하면 정규화된 수 여러 개를 어떤 자릿수도 넘치기 전에 더할 수 있고, 정규화 패스 한 번으로 결과를 되돌린다. 이를 이진 레지스터로 옮기면 같은 원리가 이 표현이 암호학에서 표준인 이유이며, 직관에 반하게도 수를 더 많은 레지스터에 분산하고 더 많은 명령을 발행하는 것이 산술을 더 빠르게 만드는 이유이기도 하다. 2017년에 처음 발표된 이 글은 2020년 5월 Hacker News에 게시되어 518점과 댓글 83개를 받았다.

림브를 51비트로 줄여 여유 비트가 캐리를 흡수하게 한다. 덧셈은 독립적이고 병렬로 유지되며, 정규화는 끝에서 한 번만 일어난다

캐리가 의존성이다. 연쇄된 adc 명령은 각각 이전 캐리 플래그를 기다리므로 직렬화되는 반면, 독립적인 일반 덧셈은 Haswell에서 사이클당 네 개까지 발행될 수 있다.

비어 있는 여유가 핵심이다. 64비트 레지스터 안의 51비트 자릿수는 12–13비트를 비워 두므로, 어떤 캐리도 전파되어야 하기 전에 대략 2^13번의 덧셈이 일어난다.

지연된 한 번의 패스가 즉시 수행하는 여러 번보다 낫다. 끝에서의 정규화는 모든 연산마다 캐리 의존성을 지는 대신 고정된 한 번의 훑기다.

추가 림브는 그 비용을 스스로 상쇄한다. 다섯 번의 일반 덧셈은 변환 비용을 계산에 넣어도 단 세 번의 덧셈만으로 네 번의 adc 연쇄를 앞선다.

직렬 의존성을 끊으려면 나중에 갚을 여유를 더하라. 여유를 확보해 핫 연산이 자유롭게 실행되게 하고, 지연된 작업은 한 번의 패스로 정산하라.

2017년에 발표되어 2020년 5월 Hacker News에 게시되었으며, 518점과 댓글 83개를 받았다. 실무자들은 이 기법을 실제 코드에 연결했다. 댓글 작성자들은 Curve25519의 체 산술이 2^255−19를 법으로 동작하므로 값이 51비트 림브에 들어가며, 32비트 CPU에서는 radix-2^25.5 변형이 쓰인다고 지적했다. 다른 이들은 Broadwell의 ADCX/ADOX 명령과 부분 레지스터 스톨을 논했고, 한 사람은 글의 최상위 림브 설명에 있는 오류를 지적했다. 이 기법은 글에서 부른 그대로 남았다. 암호학에서 표준적인 radix-2^51 표현이며, 체 산술이 빠르고 상수 시간이어야 하는 곳에서 쓰인다.