정수 제곱근 명령어를 구현한 프로세서가 있나요?

 (retrocomputing.stackexchange.com)
1P by GN⁺ | ★ favorite | 댓글 1개
  • 쟁점은 흔한 부동소수점 sqrt가 아니라 정수 제곱근을 CPU 명령이나 하드웨어 기능으로 제공한 사례가 있었는지이며, Nintendo DS의 divider/square-rooter는 유사하지만 네이티브 명령은 아님
  • Harris RTX 2000 Forth CPU와 군용급 RTX 2010은 다단계 square root 명령을 제공한 사례로 꼽히며, RTX 2000은 setup 1회와 step 15회로 결과를 얻는 구조였음
  • 더 오래된 사례인 ENIAC은 1946년에 divider/square-rooter unit으로 decimal integer accumulator를 제어해 초당 최대 40회 나눗셈 또는 3회 제곱근 연산을 수행했음
  • 정수 제곱근은 빠른 정수 곱셈기와 충분한 정밀도가 필요해 역사적 CPU에는 부담이 컸고, ARMv8의 frsqrte/frsqrts처럼 추정과 반복을 나눠 정확도·속도를 조절하는 방식도 있음
  • Quake식 inverse square root는 현대 하드웨어에서 더 이상 일반적인 성능 우위가 없으며, 테이블 조회·보간·Halley 계열 반복·고정소수점 분할 정복 등은 구현 환경에 따라 선택지가 달라짐

질문의 범위와 Nintendo DS 사례

  • 질문은 정수 제곱근 명령어를 실제로 구현한 프로세서가 있었는지를 다룸
  • 부동소수점 square root 명령은 흔하지만, 정수 전용 square root 명령은 질문자가 본 적이 없다는 전제에서 출발함
  • Nintendo DS에는 메모리 매핑된 integer divider/square rooter가 있었음
    • ARM 프로세서에 FPU나 하드웨어 divider가 없어 3D 계산에 도움이 됨
    • 다만 네이티브 프로세서 명령어가 아니라는 점이 질문의 주요 단서임

Harris RTX 2000과 RTX 2010

  • Harris RTX 2000 Forth CPU는 다단계 square root 명령을 제공한 사례로 언급됨
  • 군용급 sibling인 RTX 2010도 같은 계열의 기능을 제공함
  • 관련 자료로 Stack Computers: RTX 2000가 연결됨
  • RTX2000 Family Programmer’s Reference Manual에 따르면 이 기능은 반복형 square root에 가까우며, setup 명령 1개와 step 명령 15개를 실행해 최종 값을 얻는 방식임
  • Ken Lyons의 “A Fast Method for Finding an Integer Square Root”도 RTX2000 계열의 하드웨어 구현과 프로그래밍 예시를 다룬 자료로 언급됨

ENIAC의 divider/square-rooter unit

  • 1946년 ENIAC도 정수 제곱근 하드웨어 사례에 해당함
  • 인용된 설명에 따르면 ENIAC은 accumulator 4개를 특수 multiplier unit으로 제어해 초당 최대 385회 곱셈을 수행함
  • accumulator 5개는 특수 divider/square-rooter unit으로 제어되어 초당 최대 40회 나눗셈 또는 3회 제곱근 연산을 처리함
  • ENIAC의 accumulator는 decimal integer로 동작했음

정수 제곱근 구현이 까다로운 이유

  • 한 답변은 Newton-Raphson 반복으로 역제곱근을 구한 뒤 원래 값과 곱하는 방식을 square root 계산의 효율적 방법으로 설명함
  • 이 방식은 “Quake method”로 알려져 있으며, 현대 CPU와 GPU에서는 초기 추정 명령과 반복 명령으로 일반화된 사례가 있음
  • 이 접근의 핵심 제약은 빠른 multiplier가 필요하다는 점임
    • 부동소수점 sqrt에는 빠른 FP multiplier가 필요하고, FPU는 이를 갖고 있음
    • 정수 sqrt에는 빠른 integer multiplier가 필요하지만, 역사적으로 대부분의 CPU에는 그런 하드웨어가 없었다는 설명임
    • 충분한 정밀도를 내려면 입력 폭의 두 배 폭을 가진 빠른 multiplier가 필요하다는 조건도 붙음
  • 정밀도 요구가 항상 같지는 않기 때문에, frsqrte와 frsqrts처럼 추정과 반복을 나누면 원하는 속도·정확도 절충에 맞춰 반복 횟수를 조정할 수 있음

Quake 기법과 현대 sqrt 구현 논쟁

  • 다른 답변은 Quake trick이 가장 효율적이라는 주장이 오래전부터 맞지 않았고, 특정 하드웨어에서 낮은 품질의 float 결과를 얻을 때만 해당한다고 반박함
  • 현대 칩에서는 네이티브 sqrt 명령이 훨씬 빠르며, 종종 몇 클럭 사이클 수준이라고 설명함
  • 더 빠른 방법으로는 비균등 간격 값 테이블을 저장하고, 두 값을 빠르게 가져와 보간한 뒤, base-2 exponent를 shift하고 필요하면 Newton-Raphson보다 나은 반복을 한 번 적용하는 방식이 제안됨
  • Halley 계열과 여러 반복법은 Newton-Raphson보다 더 빠르게 수렴할 수 있지만, 실제 속도는 각 연산의 비용에 좌우됨
  • 정수 전용 범위, 예를 들어 2^32라면 같은 아이디어를 고정소수점으로 적용할 수 있음
    • 하드웨어용 단순 방법으로 divide and conquer가 제시됨
    • 각 8비트를 256개 고정소수점 값 테이블로 매핑하고 병렬 조회한 뒤, 3번의 곱셈 중 2번을 병렬로 수행해 32비트 값을 얻고 truncate할 수 있음
  • sqrt 최적화 연구는 계속되고 있으며, INRIA HAL 자료가 예시로 제시됨

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • AArch64 NEON에는 URSQRTE 명령이 있어서 원래 질문에 생각보다 가까움
    32비트 값을 소수부 32비트의 고정소수점 정수로 보면, 표현 범위는 0부터 1-ε까지 균등 간격이고 ε=2^-32임
    URSQRTE는 근사 역제곱근을 계산한 뒤 절반으로 나누고, 결과를 0부터 1-ε 범위로 클램프함
    고정소수점 정수는 엄밀한 정수는 아니고 근사 역제곱근도 제곱근은 아니지만, 꽤 가까운 지점까지 갈 수 있음
    관련된 FRSQRTE는 훨씬 일반적인 명령으로 32비트 부동소수점에 대해 근사 역제곱근을 제공함

    • 그런 복잡한 명령이 더 단순한 명령들로 쉽게 나눌 수 있는데도 AArch64에 들어갈 만큼 이득을 주는 작업이 뭔지 궁금함

  • 단일 클럭 사이클에 가능하냐면, 아주 큰 조회 테이블이 있으면 가능함
    클럭 사이클 안에서 직렬 논리 게이트를 얼마나 실행할 수 있느냐에 따라 크기를 줄일 수도 있을 것 같음
    예를 들어 10000의 이진 제곱근은 100의 제곱근과 꽤 비슷하고, 0의 개수만 다르다고 볼 수 있음

    • 부동소수점 역제곱근 추정 명령(frsqrte)은 보통 그런 식의 테이블 조회로 구현되며, 가수의 일부 비트와 지수의 최하위 비트로 인덱싱함
      정밀도는 대체로 bf16(ARM, RISC-V)이나 fp16(x86)과 비슷한 수준이라, 더 높은 정밀도가 필요하면 이후에 Newton-Raphson 반복을 몇 번 수행하는 식임
    • 입력의 비트 수가 n일 때, 정수 제곱근은 시프트와 덧셈만으로 n/2번 반복해서 계산할 수 있음
      각 단계에서 결과 n_old에 새 비트를 세워야 하는지 n2_new = (n_old + (1 << bit))^2 = n2_old + (n_old << (bit + 1)) + (1 << (bit*2))로 계산함
      그다음 원래 피연산자와 비교해서 크거나 같으면 1) 결과에 비트를 세우고 2) n2_old를 n2_new로 갱신함
      적절한 마이크로코드 명령 집합과 ALU가 있으면 n/2 또는 어쩌면 n 클럭 사이클에 가능하고, 더 최적화하면 n을 피연산자에서 가장 왼쪽에 켜진 비트의 인덱스까지 줄일 수 있음
    • 멍청한 질문일 수 있는데, 큰 테이블 조회가 실제로도 한 클럭 사이클에 끝나는 경우가 있나?
      큰 조회 테이블이라면 메모리에서 가져와야 할 텐데, 그러면 캐시와 메모리 계층 지연이 생기지 않나 싶음
    • 그렇게 보면 세상의 어떤 알고리즘도 1클럭 사이클에 실행할 수 있을 것처럼 들림
    • 정수 제곱근은 생각보다 나쁘지 않아서, 크다/작다 조회 테이블에 N^0.5개 항목만 저장하면 됨
      모든 답 N에 대해 N^2를 저장하는 식임
      16비트 정수에는 실현 가능하고, 32비트도 어쩌면 가능하지만, 64비트에는 무리임

  • “프로세서”의 정의를 전기기계 장치까지 넓히면, Friden SRQ는 모터 외에는 전자 부품 하나 없이 덧셈과 시프트만으로 제곱근을 계산할 수 있었음
    소수점 위치를 수동으로 맞춰야 했으니, 기술적으로는 정수 연산이라고도 할 수 있음
    영상: https://youtu.be/o44a1ao5h8w

  • 1 + 3 + 5 + ... + 2k + 1 수열을 이용하면 어떤 정수의 정수 제곱근도 구할 수 있지 않나?
    기본적으로 그 수열에서 내 수보다 작거나 같은 가장 가까운 항의 k를 찾는 방식임

    • 아이디어를 설명해 줄 수 있나?
      정의상 알고리즘은 맞지만, 순진하게 구현하면 32비트 수에서도 매우 느림
      이 정도면 그냥 이진 탐색하는 편이 훨씬 빠름
    • 더 나은 방법은 (x+y)^2=x^2+2xy+y^2 전개와, 어떤 진법에서도 2n자리 수의 제곱근은 최대 n자리라는 관찰을 함께 쓰는 것일 수 있음
      펜과 종이로 제곱근을 손으로 계산하는 흔한 방법과 같음
      이걸 8비트씩 처리하면 8비트 수의 제곱근에 대한 조회 테이블만 있으면 됨
    • 그 수열을 쭉 반복하겠다는 뜻이면, 입력 비트 길이에 대해 지수 시간이 걸림
    • 이건 전형적인 난처할 정도로 병렬화하기 쉬운 작업 중 하나임

  • 아래쪽 답변의 이 부분이 웃겼음:

    My implementation of square root using binary search, that doesn't depend on a multiplier. Only basic ALU instructions are used. It is vigorously undocumented. I have no idea what I wrote but it seems to work.
    똑똑한 코드를 쓰면 나중에 그 코드가 어떻게 돌아가는지 기억 못 할 가능성이 높다는 좋은 reminder임

  • 조금 내려가서 읽어야 하지만, 답이 ENIAC인 건 정말 웃김

    • 많은 사람이 자기가 학교에 들어가기 전의 모든 것이 원시적이고 겨우 굴러갔다고 생각함 :)
      조금만 읽어봐도 정반대임
      오늘날의 똑똑한 아이디어 대부분은 이미 1940~60년대 컴퓨터에서 쓰였고, 새 반도체 칩에서 재활용되고 있음
      파이프라이닝, 비순차 실행, 다중 코어 같은 것들이 그렇다
      옛날 하드웨어는 좀 “투박”했을지 몰라도, 아키텍처에는 매우 영리한 기법들이 쓰였음

  • 2 ^ (1/2 * Log2(X)) = sqrt(X)
    Log2(x)를 선행 0 개수 세기로 바꾸면 정말 거친 근삿값을 얻을 수 있음
    Log(2)를 더 잘 근사하면 답에 더 가까워질 수 있음

  • 가장 가까운 정수까지 정확한 답이 아니라 매우 거친 근삿값이면, 가장 앞의 1 비트 위치의 절반만큼 오른쪽 시프트하면 됨
    거의 모든 프로세서에는 시프트 명령이 있고, FLO(Find Leading One)나 FFS(Find First Set) 같은 명령도 얼마나 없는지 잘 모르겠을 만큼 흔해 보임
    어떤 용도에서는 이런 아주 거친 근사도 정확한 답만큼 유용할 수 있음
    예를 들어 이후 Newton-Raphson 반복을 위한 적당한 시작값만 필요할 때가 그렇다
    물론 오른쪽 시프트 트릭은 더 정확한 제곱근 계산의 초기값으로도 괜찮음 :P

    • 여기서 DOOM 얘기가 나오는 건가?
      이제는 꽤 유명한 인터넷 이야기인데, Carmack과 마법 같은 32비트 숫자가 등장함
    • 재미있는 사실로, FFS와 그 일반화인 FNS는 CUDA에 있음: https://docs.nvidia.com/cuda/cuda-math-api/index.html#group_...
      개인적으로 좋아하는 또 다른 CUDA 하드웨어 내장 함수는 log2임

  • 기억이 맞다면 대부분, 어쩌면 모든 고정소수점 DSP에는 제곱근 명령이나 보조 명령이 있음

  • 6502 팬에게 반쯤 관련 있고 흥미로울 만한 제곱근 알고리즘 전수 분석: https://github.com/TobyLobster/sqrt_test

답변달기