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 덧셈을 하는 방법 설명
아래와 같은 흐름
관건은, 덧셈 결과(림)이 모두 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' 책에도 흥미로운 예시 존재
Hacker News 의견
2^51이라는 숫자를 보고 처음엔 double 타입에 정수 저장 관련 얘기인 줄 알았지만, 실제로 Integer를 double로 정확히 담을 수 있는 값은 2^53-1임을 깨달음
AVX512(그리고 AVX2도 어느 정도)에서 256비트 추가 연산을 상당히 효율적으로 구현할 수 있는 환경 제공, 더 많은 숫자를 레지스터에 담을 수 있다는 장점도 있음
직접적인 예시는 아래 코드처럼 동작
처리량까지도 개선되는 모습을 보여서 실제 코드 예시는 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가 없어도 꼭 잘못된 접근은 아니라는 점을 명확히 보여줌
아래와 같은 흐름
관건은, 덧셈 결과(림)이 모두 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' 책에도 흥미로운 예시 존재