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

1. Full adder

1. Full adder

 

2. Ripple carry adder

2. Ripple carry adder

예) 32-bit ripple carry adder

• Carry delay: 하나의 stage마다 2 gate delays
• Total delay: (2*32) gate delays = 64 gate delays

 

3. Carry lookahead adder

3. Carry lookahead adder

예) 32-bit carry lookahead adder

• 4-bit 단위로: 1 gate delay + 2 gate delays
  : 4-bit 단위로 gi, pi 계산 (1 gate delay) + C0가 도착한 후 gi, pi를 이용하여 C1~C4 동시에 계산 (2 gate delay)
• Total delay = 3*(32/4) gate delays = 24 gate delays

 

4. Ripple/Lookahead Adder

4. Ripple/Lookahead Adder

예) 32-bit ripple/lookahead adder

• 1 gate delay
  4-bit 단위로: 2 gate delays
• Total delay = 1 + 2*(32/4) gate delays = 17 gate delays

 

5. Group Carry-Lookahead

5. Group Carry-Lookahead

예) 32-bit group carry-lookahead adder

• Generating pi, gi: 1 gate delay
• Generating Pi, Gi: 2 gate delays
• Generating C4: 2 gate delays

--> Total delay = 5 gate delays

 

---

ALU (Arithmetic Logic Units)

ALU (Arithmetic Logic Units)

 

Constructing ALU - First Cut

Constructing ALU - First Cut

▶ Full Adder (FA) - INVERT B

: Ai ? Bi ? Ci = Ci+1

• Ai: 그대로 들어간다.
• Bi: INVERT B 값에 따라 그 값이 바뀌어서 들어간다.
  (INVERT B == 0이면 B, INVERT B == 1이면 !B)
• Ci: carry-in
• Ci+1: carry-out
• Si: Full Adder 계산 결과

 

▶ MUX - SELECT

: SELECT bit에 의해 Ai와 Bi에 대해 어떤 연산을 할 지 결정한다.

• SELECT == 00(0) --> A*B
• SELECT == 01(1) --> A+B
• SELECT == 10(2) --> FA 값; Si
• SELECT == 11(3)

 

ALU Design

ALU Design

: ALU 여러 개를 붙여서 하나의 ALU를 만든다.

 

 

Overflow Detection in ALUs

Overflow Detection  in ALUs

: ALU31에서 C(i+1) =/= Ci이면, overflow가 발생한 것이다.

• OFLO: C(i+1) XOR Ci
  - OFLO == 0: overflow 발생x
  - OFLO == 1: overflow 발생o

 

 

Supporting the MIPS slt Instruction

slt  $s0, A, B     # if(A < B), $s0 = 1; else, $s0 = 0;

slt 연산에서는 (A < B)인지 아닌지를 확인해야 한다.

(A - B) 뺄셈 연산을 통해 확인할 수 있다.

• A - B = A + (2's complement of B)

Supporting the&nbsp; MIPS slt Instruction

▶ Lessi

: 32-bit 중 LSB를 통해 A<B인지 아닌지를 결정한다.

• Set "Lessi" to "00...01" when (A - B < 0) --> Bit 0 = 1;

▶ MUX - SELECT

: SELECT bit에 의해 Ai와 Bi에 대해 어떤 연산을 할 지 결정한다.

• SELECT == 00(0) --> A*B
• SELECT == 01(1) --> A+B
• SELECT == 10(2) --> FA 값; Si
• SELECT == 11(3) --> slt A, B

Supporting the&nbsp; MIPS slt Instruction

• Set: A-B의 MSB
  --> Set = 1이면, A-B<0이라는 뜻! --> Lessi = 00...01로 설정한다.

▷ 결론: A<B이면, Set = 1, Lessi = 00...01이다.

 

 

Final Result: ALU Function

Final Result: ALU Function

• ALU Operation (ALU control input): 어떤 연산을 할 지 결정하는 bit

--> 결과:

• Result: 정상 계산
• Overflow: overflow가 발생하면, Overflow = 1;
• Zero: 계산 결과가 0이면, Zero = 1;

 

---

Multiplication

Multiplication

 

Multiplier Hardware

• Sequential (이것만 배웁니다.)
• Combinational

 

Sequential Multiplier - 1st Version

Sequential Multiplier - 1st Version

 

Sequential Multiplier - 2nd Version

Sequential Multiplier - 2nd Version

 

Sequential Multiplier - 3rd Version

Sequential Multiplier - 3rd Version

 

Multiply Instructions in MIPS

▶ MIPS adds new registers for product results:

• Hi: upper 32 bits of product
• Lo: lower 32 bits of product

▶ MIPS multiply instructions:

mult  $s0, $s1
multu $s0, $s1

▶ Accessing Hi, Lo registers:

mfhi  $s1    # Hi
mflo  $s1    # Lo

 

---

SBY 6-2

1. What are the delays estimates for
1) 16-bit ripple carry adder
2) 16-bit ripple/lookahead adder (stringing together 4-bit carry-lookahead adder)
3) 16-bit group-lookahead adder?

1) 2 gate delays/bit --> 32 gate delays

2) 1 gate delay + 2 gate delays/4 bits --> 1 + 2*(16/4) = 9 gate delays

3) (1 + 2 + 2) gate delays = 5 gate delays