[컴퓨터구조] 3. Arithmetic for Computers (2)

1. Full Adder
2. Ripple Carry Adder
3. Carry Lookahead Adder
4. Combine 4-bit Carry Lookahead Adders
   - Ripple/Lookahead
   - Group-Lookahead

 

---

Binary Addition (Full Adder)

Full Adder

▶ Si

= Ci XOR Ai XOR Bi (1-gate delay)

 

▶ C(i+1)

= Ai*Bi + Ai*Ci + Bi*Ci (2 gate delay)

 

 

Multi-Bit Adders (Ripple Carry Adder)

Ripple Carry Adder

: Full Adder를 여러 개 연결한 것

--> C-out으로 인한 delay ↑

 

 

Designing an Adder/Subtractor

Designing an Adder/Subtractor

▶ Addition: XOR gate에 0을 넣는다. --> ? XOR 0 = ? (값이 그대로 나옴)

▶ Subtraction: XOR gate에 1을 넣는다.

• ? XOR 1 = !? (Bit flipping)
• Carry에 1 들어감 --> 2's complement: 뒤집고, +1

 

---

Overflow in Addition & Subtraction

▶ Overflow occurs when not enough bits are available to represent the result.

 

---

Delay in Adders (Ripple Carry Adder)

▶ Full Adder

• Sum(S) = a XOR b XOR Cin
• Carry(C-out) = a*b + a*Cin + b*Cin

Ripple Carry Adder에서의 delay

▶ Delay estimate: 32-bit ripple carry adder

• Carry delay - each stage: 2 gate delays
• Total delay: 64 gate delays (TOO HIGH!)

 

Q. 32-bit ripple carry adder에서 총 delay가 64 gate delay가 되는 이유?

저는 만약 이 그림처럼 full adder 4개가 연결되어 ripple carry adder가 생긴다면, carry로 인한 delay는 3번(6 gate delay)가 발생하고, 총 delay인 S3에서는 이러한 6 gate delay에 sum으로 인한 delay를 더해야 한다고 생각했습니다. 그리고 따라서 총 delay는 sum으로 인한 delay를 알지 못한다면 구할 수 없다고 생각했습니다.

A. 좋은 질문입니다.

사실 sum은 Si를 계산하기 위해 XOR을 통해서 1 gate만에 나오고, 이에 비해 C(i+1)은 Ci가 들어온 이후에 반드시 2 gate delay를 거쳐야만 나옵니다. 즉, 여기서 중요한 delay가 결정되는 path는 sum이 아니고 carry입니다. Carry 계산하는 부분이 각 비트별로 오래 걸리는 것이기에, sum, carry가 동시에 계산을 시작했을 때 sum의 delay는 carry의 delay보다 작으므로, carry 계산이 끝난 시점이 중요합니다.

따라서 4-bit를 계산하기 위해서는 2*4 gate delay가 소요되고(sum은 훨씬 전에 끝나있음),

32-bit를 계산하기 위해서는 2*32 gate delay가 소요되겠지요.

 

 

Speeding up Carry (Carry Lookahead Adder)

▶ Key idea: Ripple Carry Adder에서의 delay를 낮춘다.

• 장점: Faster addition
• 단점: Much more logic

 

▶ Define two signals for each adder stage:

• Generate (gi) = ai * bi (AND: Adder i will always generate a carry if ai, bi both true(1))
• Propagate (pi) = ai + bi (OR: Adder i will propagate a carry input if either or both ai, bi true(1))

 

▶ Now, rewrite Carry Output as function of ai, bi, gi(Generate), pi(Propagate)

 

▶ "Flatten" carry function in terms of gi, pi

 

Q. Ripple Carry Adder vs. Carry Lookahead Adder

Carry lookahead adder에서는 gi와 pi를 도입하여 식을 간단하게 만들었다는 점은 이해를 했는데, 이렇게 식을 간단하게 만들어도 결국 delay는 변하지 않는 것 아닌가요? 저는 Carry lookahead adder에서도 delay를 계산하려면 결국 다시 gi와 pi를 ai와 bi의 형태로 바꿔야 하고, 따라서 delay가 변하지 않게 된다고 생각했는데, 혹시 제가 어떤 부분에서 잘못 이해를 한 것인지 궁금합니다.

A. gi, pi를 결국 다시 ai와 bi로 해서 계산하는 것이 아니냐고 했는데, 그 부분이 잘못 이해한 부분입니다.

Ripple carry adder에서는 ci가 들어올 때까지 기다려야만 c(i+1)을 계산할 수 있습니다.

Carry lookahead adder에서는 4-bit 단위로 gi, pi를 우선 계산해놓고, 그 다음에는 한꺼면에 c1, c2, c3, c4를 2 gate delay를 거쳐서 할 수 있습니다.

위 식에서 주목할 점은 c0-->c1, c0-->c2, c0-->c3, c0-->c4가 계산되기까지 각각 2 gate delay만 소요되었다는 점입니다. 

동시에 시작해서 우선 a, b --> p, g 계산 (1 gate delay)하고,

c0가 도착한 후 위의 p, g를 이용하여 c1, c2, c3, c4를 동시에 계산 (2 gate delay)하면,

즉, 4-bit Carry Lookahead Adder는 (1+2) gate delay만 있으면 carry가 모두 한꺼번에 계산됩니다.

 

Using Carry Lookahead

▶ Cost a limiting factor

• Practical computation for 4-bit adders, but...
• Too expensive for 16 bits or 32 bits!

▶ Alternative: Combine 4-bit Carry-Lookahead Adders (A Hierarchical Carry-Lookahead Adder)

• Ripple/Lookahead: String CLA(Carry Lookahead Adder)s together
• Group-Lookahead: Add another level of CLA(Carry Lookahead Adder)

 

 

Combine 4-bit Carry-Lookahead Adders

Ripple/Looahead Adder

 

Group Carry-Lookahead

Group Carry-Lookahead

 

---

SBY 6-1

1. Can you show full adder equations for
1) sum
2) carry
and draw them?

 

 

2. If you implement 1 byte ripple adder, what is the delay estimate?

8-bit ripple carry adder delay = 16 gate delay

 

 

3. Explain how the Carry Lookahead Adder reduces gate delays compared to the Ripple Adder.

▶ Ripple adder: Ci가 들어올 때까지 기다려야만 C(i+1)을 계산할 수 있다. --> 2*n gate delay

 

▶ Carry lookahead adder: 

1) 4-bit 단위로 gi, pi를 우선 계산해놓고(1 gate delay)

2) C0가 도착한 후 gi, pi를 이용하여 C1, C2, C3, C4를 동시에 계산한다. (2 gate delay)

--> (1+2) gate delay만에 4-bit carry를 한꺼번에 계산할 수 있다.

--> (n/4)*3 gate delay