펜티엄에는 3을 곱하는 복잡한 전용 회로가 있었음

 (righto.com)
3P by GN⁺ | ★ favorite | 댓글 1개
  • 1993년 Intel Pentium은 부동소수점 곱셈을 빠르게 처리하기 위해 3배 값을 만드는 전용 ×3 회로를 포함했고, 이 작은 회로만 수천 개 트랜지스터를 사용함
  • Pentium은 64비트 곱셈에서 더할 항을 64개에서 22개로 줄이기 위해 radix-8 곱셈을 쓰지만, 이 방식에서는 ×3 배수를 빠르게 만들어야 함
  • ×3 계산 자체는 x + 2x 덧셈이지만, 나머지 곱셈 단계가 이 결과를 기다리기 때문에 carry lookahead와 Kogge-Stone 같은 고속 가산기 기법이 필요함
  • 회로는 8비트 블록 8개와 상위 lookahead를 결합한 계층형 구조이며, 오버플로와 반올림을 위해 실제 출력은 69비트로 넓어짐
  • 약 9000개 트랜지스터가 ×3 회로 하나에 쓰인다는 점은 Pentium 세대에서 성능을 위해 얼마나 복잡한 하드웨어 최적화가 투입됐는지 보여줌

Pentium이 ×3 회로를 따로 둔 이유

  • Pentium의 부동소수점 곱셈기는 두 64비트 수를 radix-8 방식으로 곱함
    • 일반 이진 곱셈은 각 비트마다 0 또는 피승수를 더하므로 64비트 곱셈에서 64개 항이 필요함
    • radix-8 방식은 승수를 3비트씩 묶어 0~7 중 하나를 곱하므로 더할 항이 22개로 줄어듦
  • 0~7 배수 중 일부는 하드웨어에서 비교적 간단히 만들 수 있음
    • ×2는 1비트 왼쪽 시프트로 처리됨
    • ×4는 2비트 왼쪽 시프트로 처리됨
    • ×6과 ×7은 Booth 곱셈 알고리듬으로 다음 radix-8 자리의 +1과 현재 자리의 뺄셈을 조합해 처리 가능함
    • ×5는 ×8에서 ×3을 빼는 방식으로 얻을 수 있음
  • 결국 까다로운 배수는 ×3이며, Pentium은 이를 부동소수점 곱셈기 내부의 전용 회로로 해결함

단순 덧셈이 병목이 되는 지점

  • 3배 값은 입력값과 한 비트 왼쪽으로 민 입력값을 더해 만들 수 있음
    • 구조만 보면 x + 2x 덧셈임
  • 병목은 덧셈 과정의 carry 전파에서 생김
    • 리플 캐리 가산기는 하위 비트에서 생긴 carry가 상위 비트까지 순차적으로 전달되어야 함
    • ×3 결과가 준비되기 전에는 나머지 곱셈 과정이 시작될 수 없어 지연을 줄여야 함
  • Pentium은 carry를 순차 전파하지 않고 병렬 계산하기 위해 carry-lookahead adder를 사용함
    • 각 비트에서 carry generate와 carry propagate 신호를 만듦
    • generate는 해당 위치가 carry를 생성하는 경우를 나타냄
    • propagate는 들어온 carry가 밖으로 전달되는 경우를 나타냄
    • carry가 병렬로 계산되면 sum 비트도 병렬로 계산 가능함

Kogge-Stone과 2단계 carry lookahead

  • carry lookahead를 단순하게 직접 구현하면 비트 수가 커질수록 회로와 배선 부담이 커짐
    • 비트 위치가 올라갈수록 논리가 복잡해짐
    • 입력이 많은 게이트는 전기적 이유로 느려짐
  • Pentium은 8비트 단위의 Kogge-Stone 병렬 프리픽스 가산기를 사용함
    • Kogge-Stone은 propagate/generate 신호를 범위 단위로 병합해 carry를 병렬 계산함
    • 중간 결과를 재사용해 지연과 회로량을 관리함
  • 64비트 전체를 하나의 Kogge-Stone으로 처리하지 않고 2단계 계층 구조로 나눔
    • 하위 계층은 8개의 8비트 Kogge-Stone 회로로 각 블록 내부 carry를 계산함
    • 상위 계층은 각 8비트 블록을 하나의 단위처럼 보고 블록 간 carry를 계산함
    • 두 계층을 결합해 64비트 합에 필요한 carry를 빠르게 제공함
  • 회로는 64비트용으로 볼 수 있지만, 실제로는 오버플로 방지와 반올림용 여분 비트를 포함해 69비트 출력을 만듦

carry-select로 기다리는 시간을 줄임

  • 각 8비트 블록에는 carry-select adder가 들어감
    • carry-in이 0인 경우와 1인 경우의 합을 미리 둘 다 계산함
    • 상위 lookahead 회로가 실제 carry-in을 알려주면 멀티플렉서가 올바른 결과를 선택함
  • 이 방식은 하드웨어를 더 쓰는 대신 시간을 아낌
    • 두 개의 adder와 결과 선택용 멀티플렉서가 필요함
    • 합 계산과 carry 계산을 겹쳐 전체 지연을 줄임
  • 가장 낮은 8비트 블록은 carry-in이 없어 carry-select 회로가 필요 없음
    • 이 블록의 출력 비트는 XNOR 게이트로 계산됨

8비트 블록 안에서 일어나는 일

  • ×3 회로의 각 8비트 블록은 입력선을 왼쪽 adder와 오른쪽 경로로 나눔
    • 이 분기 구조가 입력값과 한 비트 왼쪽으로 민 입력값을 더해 ×3을 구현함
  • 블록 상단은 propagate/generate 신호를 만드는 회로로 구성됨
    • 이 신호들은 8비트 Kogge-Stone lookahead 회로로 들어감
    • Kogge-Stone 부분은 비트 위치마다 복잡도가 달라 반복 블록처럼 보이지 않고 불규칙하게 보임
  • 블록 하단은 carry-select adder 영역임
    • 두 합을 미리 계산하고 carry-in에 따라 멀티플렉서가 선택함
    • carry-select adder 블록은 주변 회로보다 좁게 배치되어 상위 Kogge-Stone 회로 일부가 들어갈 공간을 만듦
  • 각 블록은 출력 비트를 다음 곱셈기 회로로 보내기 전 드라이버 회로로 증폭함

XNOR 게이트와 트랜지스터 수준 구현

  • 낮은 비트 영역의 XNOR 게이트는 Pentium에서 멀티플렉서로 구현됨
    • Intel 386은 XOR을 AND-NOR 게이트로 구현했고, Z-80은 패스 트랜지스터를 사용했지만 Pentium의 접근은 다름
  • 해당 XNOR 회로는 네 개의 인버터와 패스 트랜지스터 멀티플렉서로 구성됨
    • 입력 B가 멀티플렉서의 두 입력 중 입력 A 또는 반전된 A를 선택함
    • 그 결과 XNOR 함수가 만들어짐
  • 칩 사진 분석에서는 상위 두 금속층을 제거해 하단 금속층 M1과 도핑된 실리콘 영역을 관찰함
    • 폴리실리콘 선이 도핑 실리콘을 가로지르는 지점이 트랜지스터 게이트가 됨
    • CMOS 회로는 위쪽 NMOS와 아래쪽 PMOS 트랜지스터로 구성됨

BiCMOS 출력 드라이버

  • ×3 회로의 출력은 높은 전류를 필요로 함
    • 각 ×3 신호는 부동소수점 곱셈기 안에서 최대 22개 항을 구동할 수 있음
    • 목적지 회로가 ×3 회로에서 멀리 떨어져 있을 수 있음
    • 긴 배선과 많은 트랜지스터 게이트 때문에 정전용량이 커지고, 신호를 빠르게 바꾸려면 큰 전류가 필요함
  • Pentium은 같은 칩에 bipolar transistor와 CMOS를 결합한 BiCMOS 공정을 사용함
    • Pentium은 신호 지연을 최대 35% 줄이기 위해 BiCMOS 회로를 광범위하게 사용함
    • Intel은 Pentium Pro, Pentium II, Pentium III, Xeon에도 BiCMOS를 사용함
    • 칩 전압이 낮아지면서 bipolar transistor의 이점이 줄어들어 BiCMOS는 결국 사용되지 않게 됨
  • ×3 회로의 드라이버는 BiCMOS 드라이버가 다시 두 번째 BiCMOS 드라이버를 구동하는 구조임
    • 고전류 인버터의 트랜지스터 게이트가 커서 이를 구동하기 위한 중간 단계가 필요함
    • 작은 신호를 여러 단계로 키우면 전체 지연을 줄일 수 있음
  • BiCMOS 드라이버의 NPN 트랜지스터는 일반 MOS 트랜지스터와 달리 큰 상자 모양으로 보임
    • 인버터는 PMOS로 출력을 높이고 NMOS로 출력을 낮추는 표준 CMOS 구조를 사용함
    • 일부 인버터는 강한 high 또는 강한 low 출력을 내도록 비대칭 전류 특성으로 설계됨

곱셈 하드웨어가 보여주는 복잡도 증가

  • 컴퓨터 곱셈 하드웨어의 역사는 1950년대까지 거슬러 올라감
    • Booth 곱셈 기법은 1951년에 설명됨
    • 병렬 곱셈기는 1960년대 중반 Wallace와 Dadda가 제안함
  • 초기 마이크로프로세서는 하드웨어 곱셈 지원이 제한적이었음
    • 6502 같은 프로세서는 곱셈 하드웨어가 없어 사용자가 시프트와 덧셈으로 소프트웨어 구현을 해야 했음
    • Intel 8086은 마이크로코드로 느린 shift-and-add 루프를 수행함
    • 386은 multiply unit을 포함했지만 곱셈 명령이 최대 41클록 사이클 걸렸음
  • Pentium 시점에는 수백만 개 트랜지스터를 담을 수 있어 더 복잡한 성능 최적화가 가능해짐
    • Pentium의 부동소수점 곱셈은 3클록 사이클이 걸리고, 곱셈 회로는 그중 2사이클 동안 사용됨
    • 정수 곱셈 MUL은 11사이클로 훨씬 느림
    • 2008년 Nehalem 마이크로아키텍처는 부동소수점 곱셈 시간을 1사이클로 줄임
  • Pentium의 ×3 곱셈기는 약 9000개 트랜지스터를 포함함
    • 이는 1976년 Z80 마이크로프로세서 전체보다 조금 더 많음
    • ×3 회로는 Pentium의 부동소수점 유닛 안에 있는 부동소수점 곱셈기의 작은 일부에 불과함

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 아주 곁가지이긴 한데, 오래전에 삼진 컴퓨터 에뮬레이션 작업을 하면서 3의 거듭제곱으로 나누는 연산을 비트 시프트와 덧셈의 급수로 바꾸는 닫힌형 변환을 찾는 귀여운 요령을 쓴 적이 있음
    먼저 1/3 - 1/2 = 2/6 - 3/6, 즉 1/3 = 1/2 - 1/2 (1/3)임을 보면 됨
    이 식을 우변에 무한히 대입하면 1/3 = -(-1/2)^N 형태가 나오고, N은 1..inf 범위임
    2와 3의 거듭제곱 쌍뿐 아니라 다른 진법에서도 비슷하게 할 수 있음
    의미는, 2의 거듭제곱에 가까운 값에 대해서는 덧셈기와 뺄셈기만으로 고정 시간 상수 나눗셈 회로를 꽤 쉽게 만들 수 있다는 것

    • 놀랍다. 삼진 컴퓨터는 삼상태 논리에 기반했을 텐데, 이게 이진 상태를 인코딩하는 트랜지스터나 심지어 진공관보다 신뢰성이 낮았다고 이해해도 맞는지 궁금함

  • Cinematronics 아케이드 게임 프로세서에는 12비트 누산기가 두 개 있음
    곱셈 명령은 이 둘을 하나의 24비트 값처럼 오른쪽으로 시프트하고, 최하위 비트에서 1이 나오면 메모리 내용을 더함
    그래서 상위 절반을 지우고, 하위 절반에 한 값을 로드하고, 다른 피연산자의 메모리 주소를 어떻게 설정했는지는 잊었지만, 1비트 곱셈을 여러 번 연속 실행함
    이렇게 24비트 곱을 얻을 수 있지만, 내가 본 코드는 대부분 8번 곱셈을 이어서 썼고, 가장 흔한 용도는 게임 오브젝트 좌표 회전을 위한 2x2 행렬 곱셈이었음
    1970년대 중반 기성 7400 시리즈 부품으로 만든 것이고 최고 처리량은 5MIPS였음

    • 곱셈 하나가 정확히 한 사이클은 아니었던 것 같음. 그러면 5MIPS도 금방 소모됐을 것임
      지난 20년 동안 고정소수점 연산을 해야 했던 적이 몇 번 있는데, 이전 세대 프로그래머들에 대한 존경심이 커졌음

  • carry lookahead, Kogge-Stone addition 같은 기법을 들어봤을 수 있다는 대목에 덧붙이면, 여기서 Kogge는 Peter Kogge임
    Stanford에서 박사 작업을 했고, 우주왕복선 관련 일을 했으며, IBM Fellow이고, 최초의 멀티코어 CPU를 발명한 인물임

    • 그가 많은 업적을 남긴 건 분명하지만, 최초의 멀티코어 CPU를 발명했다는 식의 표현은 빼도 충분히 사실이고, 세상은 그런 표현 없이 더 나을 것 같음
      “멀티코어 CPU” 자체는 엄밀히 말해 하나의 발명이라기보다 아이디어에 가까움. 반도체 역사에서 어느 시점에 이르면 꽤 명백하고 사소한 아이디어이기도 함
      멀티코어 CPU를 실제로 동작하게 만드는 것은 사소하지 않지만, 그것도 단일 발명은 아니고, 그 시점에는 개발팀 규모가 워낙 커져서 한 사람이 모든 문제를 혼자 해결했다고 말하는 건 오히려 모욕적임
      Kogge가 최초 멀티코어 CPU 개발을 이끌었을 수 있고, 다른 사람들이 가능하다고 보기 전에 밀어붙인 선구자였을 수도 있지만, 어느 쪽이든 그가 혼자 발명한 것은 아님
    • 최초의 멀티코어 CPU 팀은 Kunle Olukotun이 이끌었다고 알고 있었음
    • 또 하나 덧붙이면, Peter Kogge는 초기 슈퍼컴퓨터 벡터 프로세서가 어떻게 설계됐는지 배우고 싶을 때 읽을 만한 파이프라인 마이크로아키텍처 초기 교과서를 썼음: The Architecture of Pipelined Computers (1981)
    • Peter는 예전에 우리 연구실과 자문·협업을 했음. 그는 원격 탐사 계산을 센서에 더 가깝게 옮기는 접근, 요즘 말로 엣지 컴퓨팅을 지지했음
      이 접근은 지적으로 충분히 설득 가능함. 중앙 컴퓨팅으로 데이터를 옮기는 데 지연이나 비용이 있으면 타당하고, 우리 경우에는 우주 기반 센서라서 그런 논리를 세울 수 있었음
      다만 내가 알기로 이런 처리 방식이 우주 기반 처리 시스템에 체계적으로 채택된 적은 없고, 레이더 같은 많은 시스템이 센서 가까운 하드웨어에서 임시적인 데이터 축소를 하긴 함
      그 연결고리를 알려줘서 고마움

  • 글쓴이임. 질문이 있으면 답하겠음

    • 이후 기계들에서는 전용 3배 곱셈기가 어떻게 됐는지 궁금함. 어떤 형태로든 계속 남았는지, 아니면 전술이 바뀌어 쓸모없어졌는지?
    • Ken, 이제 책을 낼 때가 된 것 아닌가?
    • 기본적인 질문일 수 있는데, 이건 부동소수점 곱셈용인가? 지수도 더해야 하니 실제로 곱해지는 부분은 64비트보다 작은 것 아닌가?
    • 이해가 희미해서 너무 바보 같은 질문이면 무시해도 되는데, “×3을 계산할 수 있으면 ×8에서 빼서 ×5를 얻을 수 있다”면 왜 x4를 x7에서 빼서 x3을 얻는 식으로는 못 하는지 궁금함

  • 빠뜨린 게 있는 것 같음
    ×2는 6x = 8x - 2x를 이용할 수 있을 정도로 쉽게 계산할 수 있고, ×4도 4x = 4x로 쉽게 계산할 수 있다면, 왜 3x를 2x + 1x의 합이나 4x - 1x의 차로 계산하는 게 그보다 더 어려운지 모르겠음
    또 ×6을 어떤 방식으로든 쉽게 계산할 수 있다면, 그 값을 오른쪽 시프트해서 ×3을 만들면 안 되는 이유도 궁금함. 추가 단계이긴 하지만 그 추가 단계는 시프트임

    • 64비트 곱셈에서는 8진수 각 자리마다 하나씩, 총 22개 항을 더하게 됨. 초등학교식 곱셈을 떠올리면 됨
      각 항은 계산이 사소해야 해서, 항을 얻기 위해 시프트나 부호 반전은 할 수 있지만 또 다른 덧셈은 할 수 없음
      핵심은 ×3을 한 번 미리 계산해 두면, 이후 필요한 22개 항 어디에든 그냥 넣을 수 있다는 것임
      항 안에서 ×2와 ×1을 넣어 ×3을 만들 수는 없음. 그러려면 모든 항마다 또 다른 덧셈기가 필요함
      다시 말해 원하는 것은 ×3을 계산하는 회로 하나이지 22개의 회로가 아님
      ×6 질문의 경우, 이 값은 항에 음수 ×2를 넣고, 개념적으로 다음 자리 숫자에 1을 더해 ×8을 얻는 식으로 계산됨. 이 ×8 값은 완전히 다른 항의 일부라서 오른쪽 시프트할 수 없음
      숫자와 합이 많이 오가서 복잡하지만, 이렇게 보면 말이 될 것임

  • 3배 곱셈은 실제로 흔한 연산이고, 특히 주소 계산에서 시프트와 덧셈으로 인덱스에 3을 곱하는 경우가 많음
    순진하게 구현하면 지연 시간이 꽤 늘어남. 하지만 이 회로를 쓰면 LEA(Load Effective Address) 명령이 한 사이클에 처리할 수 있으니, 여기에 그 정도 트랜지스터 예산을 쓰는 건 충분히 좋은 선택이었음

    • 이 회로가 정말 거기에 쓰이나? 글을 이해한 바로는 이 회로는 부동소수점 곱셈의 일부임
    • 무슨 말인지 모르겠음
      LEA는 주소 지정 모드가 계산한 주소를 그 주소에서 데이터를 옮기는 대신 출력 피연산자에 넣는 명령일 뿐이고, LEA가 할 수 있는 주소 계산은 MOV 명령도 모두 할 수 있음
      x86에서 MOV나 LEA가 쓰는 인덱스 주소 지정 모드는 스케일 계수 3을 지원하지 않고, 1, 2, 4, 8 같은 2의 거듭제곱만 지원함. 그래서 주소 생성에는 3배 곱셈을 쓸 곳이 없음
      글은 3배 곱셈기가 부동소수점 곱셈기의 일부라고 명확히 밝히고 있음

  • “이 ×3 곱셈기는 대략 9000개의 트랜지스터를 포함하며, 이는 Z80 마이크로프로세서 전체(1976)보다 조금 더 많다. ×3 곱셈기는 Pentium의 부동소수점 장치 안에 있는 부동소수점 곱셈기의 작은 일부라는 점을 기억하라. 즉, 한 기능의 작은 조각이 17년 전의 전체 마이크로프로세서보다 더 복잡하며, 이는 프로세서 복잡도가 얼마나 엄청나게 증가했는지 보여준다.”
    이런 성능 성장 속도가 오늘날 소프트웨어 비대화를 낳았음. 내년의 성능 향상이 알고리즘과 데이터 흐름 맥락·지역성을 비판적으로 생각하지 않은 죄를 대부분 덮어줄 수 있었기 때문임
    오늘날은 내가 읽은 바로는 실리콘 반도체 기술과 현재 물리 이해로 합리적으로 할 수 있는 것의 실질적 한계에 도달해 있음. 이제 추는 반대로 움직여야 하고, 컴퓨터는 더 세게가 아니라 더 똑똑하게 일해야 함

    • “현재 물리 이해로 가능한 실질적 한계”에는 수십 년 전부터 도달해 있었음
    • 소프트웨어 비대화가 하드웨어 개선 속도를 따라잡는 현상은 Wirth의 법칙으로 알려져 있음: https://en.wikipedia.org/wiki/Wirth%27s_law
      다만 소프트웨어 비대화가 더 빠르게 커지고 있다고 봄
    • 반대로 곱셈기는 Z80보다 구조가 훨씬 규칙적임. Pentium의 데이터 경로도 몇 배 더 넓음
    • 함수 호출의 역사: goto/jmp로 명령어 이동 → vtable 조회 → 딕셔너리에서 해시 및 조회 → 대형 언어 모델 실행
    • 다행히 대부분의 애플리케이션에는 아직 개선 여지가 많음

  • “7을 곱하는 대신 숫자의 8배를 더하고 숫자를 빼서 7배를 얻는다. 두 단계가 필요해 보일 수 있지만, 왼쪽 자리에서 1을 더 곱하는 요령으로 추가 단계 없이 8배 계수를 얻는다.”
    이 말은 주 곱셈기 부분에 숫자를 넣기 전에 “다음 자리”에 1을 더하는 덧셈기가 있다는 뜻인가? 그 자체도 자리올림 예측 회로와 비슷해 보임
    언제 이게 필요한지도 생각하게 됨: 7 = 8-1, 6 = 8-2, 5 = 8-3, 4 = 8-4
    마지막 경우는 글에서 한다고 하지는 않았지만, 3비트 값의 최상위 비트로 다음 자리에 1을 더해야 하는지 판단하면 게이트 몇 개를 아낄 수 있을 것 같음

  • ×3 회로가 필요한 기수 8 Booth 곱셈기를 선택한 점이 흥미로움. 최대 주파수를 끌어올리기 위한 면적/성능 절충처럼 보이고, 같은 일은 더 많은 파이프라이닝으로도 가능했을 테니 지연 사이클 제약이 있었던 듯함

    • 맞음, 절충임. 당시 다른 많은 부동소수점 장치는 추가 ×3 회로를 피할 수 있어서 기수 4를 썼음
      파이프라이닝은 까다로운데, 곱셈 배열을 둘로 나누기에 좋은 위치가 없기 때문임

  • https://github.com/EI2030/Low-power-E-Paper-OS/blob/master/P...
    8086: 29,000
    386: 275,000
    486: 120만
    Pentium: 310만
    내가 기억하기로 NSA는 2000년 이후 어느 시점에 이 판에 들어왔음

답변달기