[논리회로] 캐리 예측 가산기 및 곱셈기

https://dev-dx2d2y-log.tistory.com/204

[논리회로] 수의 표현과 가산기, 리플 캐리 가산기 및 래딕스-컴플리먼트 기법을 통한 감산기 설

저번에는 가산기에 대해서 알아보았다.

 

가감산기는 이렇게 생겼으며, /Add / Sub 제어신호에서 덧셈을 0, 뺄셈을 1로 신호를 주어 가산 또는 감산을 진행한다.

그리고 ADDER의 구조는 리플-캐리 가산기를 사용하여 위와 같이 생겼다. FA가 연쇄적으로 연결된 형태를 띄고 있으며, FA는 전가산기이다.

그리고 전가산기는 이렇게 생겼다. 저 회로를 도출하는 과정은 이전 게시글에 있으므로 생략

 

이전에도 다뤘지만 리플 캐리 가산기는 연산에 n * (지연시간)이 필요하다고 했다. 또한, Add/Sub 제어신호에 따라 XOR 게이트가 추가되었으므로 지연시간이 더욱 추가된다. 저번 게시글의 예시는 단순히 8비트, 5비트, 7비트 정도의 예시를 들었으나, 현대 컴퓨터처럼 32비트나 64비트의 수의 연산은 리플 캐리 가산기는 너무 느려서 사용할 수 없다.

 

따라서 리플 캐리 가산기에 기초한 몇 가지 성능 개선 방안들이 있다.

---

고속 가산기

캐리 예측 가산기

리플 캐리 가산기에서 시간지연이 발생하는 이유는 올림수인 c를 계산하는 시간 때문에 발생한다. 따라서, 이 올림수 계산시간을 줄이기 위해서 이전 단계에서 넘어오는 올림수를 빠르게 확인할 수 있다.

 

이전에 리플 캐리 가산기에서 다음 자리수에 올라갈 올림수 c(i+1)은 xiyi + xici + yici라고 했다.

 

그림과 같이 식을 간략화하고 gi와 pi를 통해 c(i+1) = gi + pici로 나타낼 수 있다.

 

gi는 xi와 yi의 AND 연산이므로 반드시 xi와 yi가 1일 때 1의 값을 갖는다. 이럴 경우 gi와 pici가 OR 연산이므로 반드시 ci 단계에서는 올림수가 발생한다. 왜냐하면 c(i+1)은 gi가 1이라 반드시 1이기 때문에. 이 때문에 gi를 생성함수(generate function)이라고도 한다.

 

pi는 xi와 yi의 OR연산이므로 둘 중 하나만1이면 1의 값을 가진다. 또한 ci와는 AND 연산이므로 (xi+yi)와 ci가 모두 1이어야 올림수를 갖는다. 따라서 pi 때문에 c(i+1)에 올림수가 발생하면, 이전단계에서 넘어온 올림수를 다음단계로 넘기는 것과 같으므로 pi를 전파함수(propagate function)이라고 칭한다.

 

여기서 pi와 곱해진 ci는 다시 p(i-1)과 g(i-1), c(i-1)로 나타내어질 수 있다. 따라서 위의 식은 i번째 항에서 시작해서 i-1, i-2 ... 0 단계까지 내려가서 식을 얻은 결과다.

 

그래서 리플 캐리 가산기를 다시 살펴보면 위와 같은 구조를 갖는데, (여기서 Add/Sub 제어신호는 제외됨) 약간의 달라진 점이 있다면, 이전에는 xiyi + xici + yici 연산을 수행했지만, pi와 gi를 나타내기 위해서 회로 구조가 약간 바뀌었다.

 

xiyi = xiyi + ci(xi+yi)이므로 이에 맞게 회로를 약간 수정한 것 뿐이고, 이외에는 이전과 동일하다.

 

앞서 구한 ci+1 = gi + pigi-1 + pipi-1gi-2 + ... + pipi-1 ... p2p1g0 + pipi-1...p1p0c0 의 식을 따라서 만든 가산기이다. 이 식에 근거하여 동작하는 가산기를 캐리 예측 가산기(carry-lookahead adder)라고 칭한다.

 

리플 캐리 가산기에서 올림수를 표현하기 위해서는 y0 -> p0 -> g0과 p0의 OR 연산 게이트 -> p1과의 AND 연산게이트 -> g1과의 OR 연산 게이트를 통과해야 겨우 c2에 도달하기 때문에, 올림수를 판단하는 과정에서 많은 시간지연이 일어났다. n비트 가산기에서 각 자리수마다 2개의 게이트를 통과하고 처음에 Add/Sub XOR 게이트까지해서 총 2n + 1의 시간지연이 일어난다.

 

반면 캐리 예측 가산기에는 이러한 경로가 없다. 대신 gi와 pi, 그리고 ci까지 모든 신호가 다음 자리수 연산에 관여한다.

식에 따라서 gi, pigi-1, pipi-1gi-2, pipi-1pi-2gi-3, ... pipi-1pi-2pi-3...p2p1g0 + pipi-1pi-2pi-3...p2p1p0c0 까지 연산에 참여한다.

 

따라서 회로를 잘 보면, 두 번째 단계에서는 c2 = g1 + p1g0 + p1p0c0이고, c2 연산에 3개의 게이트를 통과해 마지막 OR 게이트를 통과한다.

 

그래서 세 번째 단계에서는 c3 = g2 + p2g1 + p2p1g0 + p2p1p0c0일 것이고, 따라서 두 번째 단계에서 넘겨준 g1, p1, 이전단계에서 넘어온 g0, p0, c0, 세 번째 단계에서 계산된 g2, p2로 계산할 것이다.

 

가장 긴 시간지연을 알아보자면 g0, g1, p0, 01을 만드는데 1게이트 지연, c1, c2를 만드는데 2게이트의 지연, 처음에 붙는 XOR 게이트까지 추가로 4게이트 지연이 발생한다.

---

그런데, 보통의 컴퓨터에서 쓰이는 32비트나 64비트 가산기를 만든다고하면, 식이 아주 복잡해지고, 회로도 아주 복잡해진다. 자리수가 하나씩 커질 때마다 pi, gi, ci+1 총 3개의 회로가 필요하므로 가장 마지막 비트의 연산에는 96개, 또는 192개의 회로가 필요하다. 따라서 이런 복잡도를 피하기 위해 계층적(hierarchical) 방법으로 대규모 가산기를 설계할 수 있다.

 

32비트 가산기를 만든다고할 때, 32비트 가산기를 8비트 블록 4개로 나눈다. 각각 0번부터 7번비트까지, 8번부터 15번비트까지.. 이런 식으로. 그리고 각 블록에서 연산을 수행한 후에 이를 합쳐야하는데, 합치는 방법에는 두 가지가 있다.

 

첫 번째는 각 블럭을 네 개의 리플 캐리 가산기로 연결한다. 32비트 전체를 리플-캐리 가산기로 설계하는 것보다는 빠르지만, 그래도 리플 캐리 가산기이니만큼 다소 느리다.

 

캐리 신호를 신속히 처리하기 위해서 계층적으로 캐리 예측 가산기를 설계할 수 있다. 이러한 '계층적 캐리 예측 가산기'는 우선 8비트 캐리 예측 가산기로 이루어져 있다.

 

각 블럭 내에서 MSB는 캐리 신호 c를 만들어내는게 아니라, 전체 블럭에 적용될 수 있는 신호 G와 P를 만들어낸다. 그래서 여기서 Gj와 Pj를 j번째 블럭의 생성신호와 전파신호라고하면, 두 번째 예측 가산기(그림에서 Second-level lookahead)에서 캐리 예측 신호의 입력으로 사용할 수 있다.

 

가령 c8은 위와 같은 형태로 나타낼 수 있는데, 만약 식의 마지막 항에서 여덟개의 전파함수가 전부 1이라면 c0은 전체 블럭에 전파된다. 따라서 P0 = p7p6p5p4p3p2p1p0으로 나타낼 수 있다. 그리고 이를 제외한 나머지 식들을 G0이라고 한다면,

 

으로 나타낼 수 있다. 따라서 Second-level lookahead에서는 G0과 P0을 받아서 이 연산을 수행해 올림수 c8을 결정한다. 이 과정은 각 캐리 예측 가산기에서 캐리 신호를 만들어내는 과정과 동일하다.

 

다른 블럭의 캐리 신호는 이렇게 구할 수 있다.

 

따라서 정리해보면, 32비트 연산의 경우에는 4개의 8비트 블럭으로 나눠서 계산을 하게된다. 각 블럭에서는 캐리 예측 가산기를 통해 연산을 수행하는데, 마지막에 다음 연산에 영향을 줄 캐리 신호를 뽑아내는 것이 아니라, G신호와 P신호를 뽑아서 Second-level lookahead로 넘긴다.

 

Second-level lookahead에서는 받은 G신호와 P신호를 통해서 캐리신호를 계산한다. 그 후에 캐리신호를 다음 블럭에게 넘기는 방향으로 블럭4개에 대한 32비트 연산이 진행된다.

 

캐리신호 계산에 2게이트, G와 P를 얻는데 3게이트의 지연이 필요하므로 총 5게이트, 그리고 각 블럭의 내부 캐리 산출을 위한 2게이트 지연과 XOR 게이트 한 개가 더 필요해서 총 8게이트의 지연이 발생한다.

 

이를 리플 캐리 가산기로 계산하려면 32비트이므로 총 65게이트 지연이 발생한다. 즉, 8배 빠르다.

---

하지만 현실적인 성능문제로인해 게이트의 입력의 수는 제한되어야한다.

 

지금까지 다룬 내용은 AND 게이트에 최대 9개의 입력을 받는 것이었지만, 만약 AND 게이트에 입력값을 4개 밖에 주지 못한다면, 위와 같이 식을 재작성해야한다. 따라서 이런 제약은 캐리 예측 가산기의 속도를 저하시키기 때문에, 이를 잘 고려해야한다.

---

곱셈

베릴로그 실습 부분이 있는데 여기는 수업 들으면서 할 것도 남겨놔야 수업시간에 안 잘 것 같아서 패스

 

곱셈을 하기 전에, 2의 제곱수만큼 곱하거나 나누는 경우는 아주쉽다. 2^k를 곱하고 싶다면 수의 비트를 왼쪽으로 k만큼 옮기면 된다. 반대로 나누는 경우도 오른쪽으로 옮기면 된다. 무부호 수라면 모두 옮기고, 부호 수라면 부호를 뺀 부분부터 옮겨야한다. 그러니까 MSB부터 옮기라는 뜻.

---

무부호 수에 대한 어레이 곱셈

그림을 보면 알 수 있듯이, 4비트 곱셈에서 가산기는 3번 사용된다. 그리고 LSB는 연산결과에 그대로 반영되고, 다음 덧셈에 영향을 끼치지 않는다.

 

무부호 수의 곱셈에는 이러한 기법이 사용되는데,

4비트 곱셈연산에서 M * Q = P 라고하며, P를 승수(multiplier) M을 피승수(multiplicand) P를 계산값이라고한다. M = m3m2m1m0, Q = q3q2q1q1, P = p7p6p5p4p3p2p1p0이라고한다.

 

이렇게 구할 수 있다. 각 비트의 곱셈은 논리곱 AND 연산과 같다. 하나라도 0이면 계산값은 0.

그래서 M과 p0의 AND 연산으로 PP0를 구하고, M과 p1의 AND 연산을 시프트 한 후 PP0에 더하여 PP1을 구한다. 즉, 가산기와 AND 게이트만으로 곱셈을 구현할 수 있다. 이 때는 리플 캐리 가산기가 사용되며, 성능 향상을 위해서 다른 종류의 가산기를 사용해도 무방하다.

 

곱셈기 회로.

각 부분을 보면 m0q0의 곱이 그대로 p0으로 반영, 나머지는 곱연산을 진행한 후 M과 q1의 덧셈으로 PP1을 구성한다. 각 덧셈값과 M과 q2의 곱을 더하는 것을 반복하며, 마지막 전가산기에서 나오는 올림수는 m3*pi와 같이 더한다. PP1을 구성할 때에는 가산기를 사용하지 않았으므로 m3*pi에 0을 더한다.

---

부호 수 곱셈

승수(곱할 수)가 양수라면 무부호 수와 같은 방법을 사용하면 된다. 곱셈기에서의 승수의 각 비트 하나하나를 보면서, 비트가 1이면 피승수를 적절히 시프트하여 각 Partial Product에 더한다. 0이라면 그냥 0으로 채워서 PP에 더하면 된다.

 

피승수를 시프트하기 때문에 연산에 개입하는 수가 정확히 표시되는지 확인해야한다. 승수의 오른쪽 두 개 비트가 1이라면 PP1 = M + 2M(M을 왼쪽으로 한 칸 시프트함, M은 피승수)이 된다. M = m(n-1)m(n-2)m(n-3)...m1m0이라면 2M = m(n-1)m(n-2)...m1m00이다.

 

PP1은 m(n-1)m(n-2)...m1m0 + m(n-1)m(n-2)...m1m00이다. 즉, n비트 수 M과 M을 왼쪽으로 한 칸 시프트해 n+1비트의 수 2M을 더해야 PP1이 나온다는 뜻. 가산기는 동일한 길이의 비트에서의 연산을 수행하므로 M 역시 확장해야한다. 확장 시에는 부호 비트를 새로운 가장 왼쪽 비트로 복제하여 n+1 비트로 표현한다. 그래서 M = m(n-1)m(n-1)m(n-2)...m1m0으로 사용한다.

 

곱셈예

PP1을 구하는 과정에서 시프트가 일어났다. 계산결과가 01110이고, 자리수를 맞추기 위해서 01110 + 01110에 시프트한 값을 계산하기 위해 01110 + 001110()을 더한다. 01110은 자리수 맞추려고 0을 통해 확장.

 

음의 피승수로 PP1을 만드는 과정도 마찬가지. 계산결과가 10010이고, 1110010 + 110010()으로 확장해야한다. 원칙상과 논리상으로는 110010 + 10010()이 맞지만, 가산기 비트 폭을 맞추기 위해서 임의의 값으로 값을 추가한 것이다.

 

승수가 음수인 경우에는 승수와 피승수의 값을 2의 보수로 바꿔서 계산할 수 있다. 즉, 2 * (-3)이라면 이를 계산하는게 아니라 (-2) * 3으로 바꿔서 계산한다는 뜻.

 

이렇게 비교적 간단한 부호 수 곱셈 과정도 있지만, 더 복잡하면서도 효율적인 과정이 있다고한다.

 

C.Hamacher, Z. Vranesic, S. Zaky and N. Manjikian, Computer Organization and Embedded Systems, 6th ed. (McGraw-Hill: New York, 2011) 이 책인데, 생각보다 논리회로와 컴퓨터구조를 잘 연결시킬 수 있을 것 같다. 그러니까 논리회로에서 연결해나가며 컴구를 듣는거랑(bottom-up) top-down 방식으로 컴구를 공부하는 거랑 두 개로 나눠서 컴구를 공부해볼 수 있겠다. 아마 시간 많을 때 하나씩 읽어보면 될 듯하다만

 

문제는 번역본을 못 구하겠음;; 아무튼 컴구 2단계에서는 저 책을 읽어보는걸로 한다. 원래 방학기간에 전공책은 2~4일에 1개 챕터 읽는 것을 목표로하는데 번역본을 못 구하면 좀 더 길게 잡아야겠지 재밌겠으니까 빨리 혼공컴구부터 읽어야함 그전에 자바도 해야하고 백엔드도 해야하는데

 

<top-down 방식으로 알아보는 컴퓨터구조> <논리회로에서부터 알아보는 컴퓨터구조>...?

---

기타 수 표현 방법

여기가 이제 고정 소수점과 부동 소수점에 대해서 다루고 있는데, 

https://dev-dx2d2y-log.tistory.com/77

[CS] 자바의 정석 독서 #3 - float, double, 부동소수점, 그리고 오차

이건 이미 예전에 한 번 다룬 적이 있어서 패스

---

2진화 10진수 표현

디지털화 시스템에서 10진수의 각 자리를 2진수 형식으로 인코딩하여 표현할 수 있다. 그러니까 0에서부터 9를 2진수에 대응시키고, 10이라하면 원래 2진수 1010으로 표현하는게 아니라, 0001 0000 으로 표현한다는 뜻. 이를 2진화 10진수, BCD(Binary-Coded Decimal number)라고 칭한다.

 

그래서 BCD에서는 10진수 한 개 자리수를 4비트 2진수에 대응시켜서 표현하는데, 나타낼 수 있는 16개의 값 중 0부터 9까지 총 10개만 나타낼 수 있다. 나머지 6개의 경우는 나타나서는 안된다.

 

BCD는 숫자를 간단히 디스플레이에 나타내려고할 때 용이하다. 1010보다는 0001 0000이 훨씬 더 직관적이니까. 반면 산술연산 회로가 복잡하며, 메모리를 최대한 아껴야할 때 아까운 4비트 6개 패턴을 날려먹는다는 단점이 있다.

 

BCD 덧셈하기

X = x3x2x1x0, Y = y3y2y1y0이 주어지고 결과가 S라고한다. X + Y가 9보다 작거나 같은 경우에는 그냥 연산을 수행하면된다. 9보다 큰 경우에는 BCD 두 자리가 필요하다. 0101 (5) + 1000 (8) = 1101 이 아니라, 0001 0011 이다.

 

9보다 큰 경우는 두 가지 경우가 있다.

 

1. 합이 9보다 크지만 4비트를 사용하면 올림수가 생성되지 않는 경우

5 + 8 = 13이지만 올림수가 발생하지 않는다. 올바른 덧셈을 위해서 캐리 1과 S = 3을 생성해야한다. 4비트는 16개의 숫자를 돌면 다시 원래대로 돌아오지만 (모듈로-16) 10진수는 10개의 숫자를 돌면 다시 원래대로 돌아온다. (모듈로-10)

 

따라서 이럴 경우 계산결과에 6을 더해줘 올림수가 발생하도록한다. 따라서 0101 + 1000 = 1101에서 0110 (6)을 더해주어 10011이 되도록한다. 올림수 1이 발생했으므로 이를 분리해 0001 0011, 즉 BCD로 13이 되도록한다.

 

2. 합이 15보다 큰 경우

9 + 8 = 17 (2진수 10001). 이 경우에도 6을 더해주면 된다. 그러면 10111이 되고, 올림수가 발생했으므로 0001 0111, BCD 17로 수를 구할 수 있다.

 

BCD 연산회로. 이렇게 생겼다. 4비트 가산기에서 올림이 발생했거나, z3 = 1이고 z2 또는 z1 (또는 둘 다) 1일 경우 중간합이 9를 초과함을 알 수 있다. (9는 2진수로 1001)

 

따라서 z3과 z1이 1인지 여부와 z3과 z2가 1인지 여부를 각각 AND 게이트를 통해 조사하고, 이 두 경우와 4비트 가산기에서 올림이 발생했는지 여부를 OR 게이트로 조사해 올림수의 여부를 판단한다.

 

2비트 가산기 쪽은 올림이 발생했을 때 6을 더하는 것과 같은 역할을 수행한다.

---

암튼 가산기가 끝났고, 5장이 레지스터, 그리고 4장이 그 사이의 완충지대(?) 정도가 될 수 있겠다. 아자아자화이자!