ALU 는 어떻게 생겼나 - 1비트 셀에서 캐리 선행과 실리콘 위의 띠까지

CPU 구조도에서 실행 유닛 칸에 "정수 ALU ×4" 라고 적었다. 이 글은 그 ALU 하나를 열어본다.

결론부터 말하면 ALU 는 덧셈기 하나에 스위치 몇 개 다. 뺄셈도 비교도 그 덧셈기로 하고, 논리 연산은 옆에서 같이 계산해두었다가 골라 쓴다. 그리고 실리콘 위에서는 같은 셀이 32줄 반복된 좁은 띠로 생겼다.

밖에서 본 ALU

회로도에서 ALU 는 이 V자 기호로 그린다. 들어가는 건 숫자 두 개(A, B)와 연산 선택 신호 몇 비트, 나오는 건 결과 하나와 플래그 몇 비트다.

연산 목록이 생각보다 짧다. AND, OR, XOR, NOR 같은 논리 연산, 덧셈, 뺄셈, 크기 비교, 시프트 정도다. 곱셈과 나눗셈은 훨씬 크고 느려서 보통 별도 유닛으로 빼고, 부동소수점도 따로다. "정수 ALU" 라고 부를 때는 이 짧은 목록을 말한다.

1비트 셀의 안쪽

ALU 의 기본 단위는 1비트 셀이다. 앞 글에서 만든 게이트들이 그대로 들어간다.

구조가 의외로 단순하다. AND, OR, XOR, 전가산기 네 개가 같은 A, B 를 받아서 전부 동시에 계산한다. 그리고 선택기(MUX)가 그중 하나를 출력으로 통과시킨다. "연산을 고른다"는 건 회로를 바꾸는 게 아니라, 이미 나와 있는 네 답 중 하나를 고르는 것이다.

B 앞에 인버터와 선택기가 하나 더 있다. B 를 그대로 쓸지 뒤집어 쓸지 고르는 스위치다. 이게 뺄셈용인데 아래에서 본다.

32비트로 늘린다

이 셀을 32개 복사해서 옆으로 늘어놓으면 32비트 ALU 다. 연산 선택 신호와 B 반전 신호는 32개 셀에 똑같이 들어간다.

셀끼리 연결된 선은 딱 하나, 캐리다. AND, OR, XOR 은 비트마다 독립이라 옆 셀을 볼 필요가 없다. 덧셈만 아랫자리에서 올라오는 캐리가 필요하다. 그래서 ALU 의 속도는 결국 캐리가 32자리를 얼마나 빨리 건너가느냐 로 정해진다.

뺄셈은 덧셈이다

ALU 에 뺄셈 회로는 없다. B 를 비트 단위로 뒤집고 캐리 입력에 1 을 넣어 더하면 A − B 가 나온다. 2의 보수다.

왜 되는지는 그림 오른쪽에 있다. 4비트에서 ¬B + 1 은 16 − B 와 같다. 그러니 A + ¬B + 1 = A − B + 16 이고, 16 은 다섯 번째 비트로 넘쳐서 사라진다. 32비트면 2³² 이 사라진다.

셀 안에 있던 "B 반전" 스위치와 캐리 입력 하나가 이 일을 한다. 인버터 32개 값으로 뺄셈이 생긴 셈이다.

크기 비교도 뺄셈이다. A < B 인지 알고 싶으면 A − B 를 해서 부호만 본다. 음수면 참이다. 그래서 if (a < b) 는 CPU 안에서 뺄셈 한 번이다.

플래그 — 결과 옆에 따라 나오는 4비트

ALU 는 결과 32비트 말고 플래그라는 1비트짜리 신호 몇 개를 같이 낸다. 보통 넷이다.

• Z (Zero): 결과가 0 인가. 결과 32비트 전부를 NOR 한 것이다.
• N (Negative): 결과가 음수인가. 최상위 비트 그대로다. 배선 하나.
• C (Carry): 마지막 자리에서 캐리가 나왔는가. 덧셈기의 마지막 캐리 출력 그대로다.
• V (Overflow): 부호 있는 정수로 봤을 때 넘쳤는가. 마지막 캐리와 그 아래 캐리를 XOR 한 것이다. 두 값이 다르면 부호 비트로 캐리가 들어갔거나 나갔다는 뜻이고, 그게 오버플로다.

조건 분기는 전부 이 플래그를 본다. "같으면 점프"는 Z 를, "작으면 점프"는 N 과 V 를 본다. 앞 절의 "비교는 뺄셈" 이 여기서 완성된다. 뺄셈을 하고 플래그를 남기면 그게 비교다.

캐리를 미리 계산한다

셀을 그냥 이어 붙이면 캐리가 32단계를 차례로 지난다. 전가산기 하나가 게이트 두 단 정도니 64단이다. 사이클 하나에 끝내기엔 길다.

해법은 캐리를 기다리지 않고 미리 계산하는 것이다. 각 자리에서 두 신호를 먼저 만든다. g = A·B 는 "이 자리가 스스로 캐리를 만드는가", p = A⊕B 는 "아랫자리에서 온 캐리를 위로 통과시키는가" 다. 그러면 c1 = g0 + p0·c0, c2 = g1 + p1·g0 + p1·p0·c0 처럼 모든 캐리를 g, p, c0 만으로 쓸 수 있다. 전부 두 단짜리 논리식이다.

식이 자리마다 길어지니까 4비트씩 블록으로 묶고, 블록의 g 와 p 를 또 묶는 식으로 트리를 만든다. 32비트가 로그 규모, 게이트 열 단 정도로 끝난다. 대신 게이트 수는 두세 배다. 실제 CPU 의 ALU 는 이 계열(Kogge-Stone, Brent-Kung 같은 이름이 붙은 변형들)을 쓴다.

실리콘 위에서는 띠다

마지막으로 물리적 모습이다.

1970년 텍사스 인스트루먼트가 만든 74181 은 4비트 ALU 가 통째로 칩 하나였다. 게이트 75개쯤, 핀 24개. 이걸 8개 이어 붙여서 32비트 ALU 를 만들었고, PDP-11 과 VAX 같은 미니컴퓨터가 이걸로 계산했다.

지금 ALU 는 코어 안의 좁은 띠다. 그리고 그 띠의 배치가 앞에서 본 회로도를 그대로 닮았다. 1비트 셀이 위아래로 32줄 반복 되고, 각 줄이 비트 하나다. 데이터는 가로로 레지스터 파일에서 나와 시프터, ALU, 결과 선택기를 지나 다시 레지스터 파일로 돌아간다. 연산 선택 같은 제어 신호는 세로로 32줄을 한꺼번에 관통한다.

이런 배치를 비트 슬라이스 데이터패스라고 부른다. 셀 하나를 정성껏 설계하고 32번 찍어내면 되니까 설계와 검증이 단순하고, 같은 비트끼리 선이 짧아서 빠르다. 회로도의 "셀 32개를 나란히" 가 실리콘에서도 문자 그대로 셀 32개를 나란히 놓은 것이다.

정리

ALU 를 다시 한 줄로 쓰면 덧셈기 하나, 인버터 한 줄, 선택기 한 줄 이다.

논리 연산은 비트마다 독립이라 게이트 몇 개면 되고, 뺄셈과 비교는 덧셈기를 재활용하고, 플래그는 이미 있는 신호를 뽑아 쓴다. 회로가 커지는 이유는 딱 하나, 캐리를 기다리지 않으려고 미리 계산하는 데 게이트를 더 쓰기 때문이다. 그리고 그 회로도가 실리콘 위에 32줄짜리 띠로 그대로 찍혀 있다.

이어서

이 ALU 가 코어 안 어디에 놓이고 어떻게 먹이를 받는지는 CPU 는 어떻게 생겼나에 정리했다. 셀 안의 게이트와 전가산기는 트랜지스터로 논리 게이트 만들기에서, 게이트를 이루는 스위치는 트랜지스터는 어떻게 생겼나에서 다뤘다.

참고

• Arithmetic logic unit - Wikipedia — ALU 의 입출력, 연산 목록, 플래그
• Two's complement - Wikipedia — B 반전과 캐리 입력으로 뺄셈하는 원리
• Carry-lookahead adder - Wikipedia — 생성·전파 신호와 캐리 선행 식
• Kogge–Stone adder - Wikipedia — 실제 CPU 에서 쓰는 병렬 프리픽스 덧셈기
• 74181 - Wikipedia — 최초의 단일 칩 4비트 ALU 와 채용 사례
• Bit slicing - Wikipedia — 비트 슬라이스 구조
• Patterson & Hennessy, Computer Organization and Design — 1비트 ALU 셀과 32비트 확장 (4장)