第5章算術(shù)邏輯單元-英文

1、Chapter 5Chapter 5The arithmetic logic unitThe arithmetic logic unitComputer OrganizationChapter 5 The arithmetic logic unit5.1 The von Neumann computer model5.2 Parallel fast adders5.3 Analysis of the design of a commercial ALU Chip5.4 Summary5.1 The von Neumann computer modelvThe vast majority of

2、computer systems used today are constructed on the van Neumann computer model.vA computer is viewed as a stored program computer.vA program is a sequence of instructions, each of which performs a basic operation.vBefore execution, the program is stored in memory along with data to be manipulated.vWh

3、en executed, the instructions in it are retrieved from memory, one after another, and brought into the processing unit. Decodes instruction, retrieve data, perform operation, stores result in register or memory.v Typically consists of 3 functional blocks: a central processing unit (CPU), main memory

4、, an input/output system (I/O).Control unitregistersALUCPUMainmemoryInput/OutputExternalBus The basic organization of a stored-program computer5.1 The von Neumann computer modelInternal Bus 5.2 Parallel fast addersvAn arithmetic unit (ALU) is the heart of the CPUvThe ALU usually has a binary adder v

5、The performance of the ALU is mainly determined by its adder.vWe need to design a fast adder to get rid of the excessive carry-propagation time of the ripple-carry adder.vDesign of full adder Full adder with the carry bit Cn-1. Fn and Cn are given as below:FnXnYnCn-1+ XnYnCn-1 + XnYnCn-1+ XnYnCn-1Cn

6、 XnYnCn-1+ XnYnCn-1 + XnYnCn-1+ XnYnCn-15.2 Parallel fast addersvDesign of full adderLogic maps:FnXnYnCn-1+ XnYnCn-1 + XnYnCn-1+ XnYnCn-1Cn XnYnCn-1+ XnYnCn-1 + XnYnCn-1+ XnYnCn-1Formed by two half addersFn : add result of Xn、Yn and Cn-1Fn=XnYnCn-15.2 Parallel fast addersvDesign of full adder A n bi

7、t adder can be produced by connecting n full adders Carry is transferred serially, and Fi is calculated when Ci-1 is coming. Time consumed is determined by number of bits.5.2 Parallel fast addersvDesign of a fast adder How to improve the speed of adder? Change the pathway of one by one carry bitsCn

8、XnYnCn-1+ XnYnCn-1 + XnYnCn-1+ XnYnCn-1 (Xn+Yn) Cn-1+ XnYn The carry of the full adder of the Ci depends on the Ci-1 Although n full adders work in parallel, the carry signals are generated and propagated in sequential. The worst-case of carry propagation occurs when a carry signal propagates from C

9、0 to Cn all the way along the carry propagation circuit.5.2 Parallel fast addersvCarry look-ahead（超前進位） It reduces significantly the carry creation time by generating the carry signals for all the bits at once directly from the input carry C0vThe nature of carry propagation C1 is generated as long a

10、s one of these two conditions is meeting：(1) Both of X1，Y1 are“1”；(2) Either of X1，Y1 is“1”，and C0 is“1”。 Then C1 can be expressed ：C1=X1Y1+(X1+Y1)C05.2 Parallel fast addersvThe nature of carry propagation C2 is generated as long as one of the following conditions is satisfied：(1) Both of X2 and Y2

11、are“1”；(2) Either of X2 and Y2 is“1”，and X1 and Y1 are“1”；(3) Either of X2 and Y2 is“1”，and either of X1 and Y1 is“1”，with C0 is“1” Then C2 can be expressed ：C2=X2Y2 +(X2+Y2)X1Y1 +(X2+Y2)(X1+Y1)C05.2 Parallel fast addersvThe nature of carry propagation Similarly，C3 and C4 can be calculated：C3=X3Y3 +

12、(X3+Y3)X2Y2 +(X3+Y3)(X2+Y2)X1Y1 +(X3+Y3)(X2+Y2)(X1+Y1)C0C4=X4Y4 +(X4+Y4)X3Y3 +(X4+Y4)(X3+Y3)X2Y2 +(X4+Y4)(X3+Y3)(X2+Y2)X1Y1 +(X4+Y4)(X3+Y3)(X2+Y2)(X1+Y1)C05.2 Parallel fast addersvThe nature of carry propagation Carry propagate function Pi and carry generate function Gi：Gi=XiYicarry generate functio

13、nPi=Xi+Yicarry propagate function Gi：when Xi and Yi are“1”，no matter whether there is low-order carry bit，the current carry bit is generated. Pi：when either of Xi and Yi is 1，if there exist low-order carry bit, then Ci-1 is propagated to high-order carry bit5.2 Parallel fast addersvThe nature of car

14、ry propagation Put P1, G1 into C1C4：C1=G1+P1C0 （low-order bit）C2=G2+P2G1+P2P1C0C3=G3+P3G2+P3P2G1+P3P2P1C0C4=G4+P4G3+P4P3G2+P4P3P2G1+P4P3P2P1C05.2 Parallel fast addersvThe nature of carry propagation Since the input variables take inverted values, its output generates the inverted variables, “NAND ”,

15、 “NOR” . “AND-OR-NOT” can be readjusted as:Gi=XiYi Gi=XiYi =Xi+Yi carry generate Pi=Xi+Yi Pi=Xi+Yi = XiYicarry propagateGiPi = (Xi+Yi) XiYi = XiYi =PiC1 = G1+P1C0C1 = G1+P1C0 =G1P1C0 =G1(P1+C0) = G1P1+G1C0 = P1+G1C05.2 Parallel fast addersvThe nature of carry propagation C1=P1+G1C0C2=P2+G2P1+G2G1C0C

16、3=P3+G3G2+ G3G2P1+G3G2G1C0C4=P4+G4P3+G4G3P2+G4G3G2P1+ G4G3G2G1C05.2 Parallel fast adders5.2 Parallel fast addersvThe four-bit carry look-ahead adder5.2 Parallel fast addersvThe block carry look-ahead circuit Theoretically speaking, expression C1C4 can be expanded to higher order bits up to n-1 for n

17、4. However, as the bit number increases, the number of product terms and maximum number of literals in a product term in the expression would increase proportionally. So we limit the fan-in of an AND gate or an OR gate to 5. The maximal allowable size of a single-stage carry look-ahead circuit is 4

18、bits.5.2 Parallel fast addersvThe block carry look-ahead circuit5.2 Parallel fast addersvThe block carry look-ahead circuitG= G3+P3G2+P3P2G1+P3P2P1G0P= P3P2P1P074182 G3P3 G2P2 G1P1 G0P0 G P C3 C2 C1C0vThe result of carry generate function of 74181 G is “1” as long as one of these conditions satisfie

19、d：(1) Both of X3 and Y3 are“1”，that is G3=1；(2) Either of X3 and Y3 is “1”，and X2 andY2 are all“1”，that is P3G2=1(3) Either of X3 and Y3 is “1”，and one of X2 andY2 is“1”， and both of X1 and Y1 are“1”，that is P3P2G1=1；(4) One of X3 and Y3 is “1”，and one of X2 and Y2 is “1”，and one of X1 andY1is “1”，a

20、nd both X0 and Y0 are “1”，that is P3P2P1G0=1。Therefore：G=G3+P3G2+P3P2G1+P3P2P1G05.2 Parallel fast addersvThe requirements to meet group carry propagate function of 74181 P equals 1 is： Either X3 or Y3 is “1”， Either X2 orY2 is “1”， Either X1 or Y1 is “1”， Either X0 or Y0 is “1”。vTherefore：P=P3P2P1P0

21、5.2 Parallel fast addersv Let Cn1, Cn2, Cn3(C3,C7,C11) be the carrys of chip 0 to chip 1, chip 1 to chip 2 and chip 2 to chip 3. Replace G1, G2 and G3 by GN0, GN1, GN2. Replace P1, P2, P3 by PN0, PN1, PN2. Replace C0 by Cn. Then Cn+x, Cn+y, Cn+y can be gained as follows:u 5.2 Parallel fast addersvTh

22、e block carry look-ahead circuitadderA15A12B15B1274182adderA11A8B11B8adderA7A4B7B4adderA3A0B3B0C0F3F0G4 P4 C3 G3 P3 C2 G2 P2 C1 G1 P1F7F4F11F8F15F12G PC05.2 Parallel fast adders5.3 Analysis of the design of a commercial ALU chipvALU can implement basic arithmetic operations and logical operations. v

23、This section analyze the design process of the commercial 4-bits ALU chip SN74181.vSN74181Logic maps and function table of 4-bits ALUS3S2S1S0Positive logicM=HLogic opM=L arithmetic operationCn=1Cn=0LLLLAAA add 1LLLHA+BA+B(A+B) add 1LLHLABA+B(A+B) add 1LLHH“0”Sub 1“0”LHLLABA add (AB)A add(AB)add 1LHL

24、HB(AB) add (A+B)(AB)add(A+B)add1LHHLABA sub B sub 1A sub BLHHHAB(AB) sub1A5.3 Analysis of the design of a commercial ALU chipvSN74181S3S2S1S0Positive logicM=HLogic opM=L arithmetic operationCn=1Cn=0HLLLA+BA add(AB)A add(AB)add 1HLLHA BA add BA add B add 1HLHLB(AB)add(A+B)(AB)add(A+B)add 1HLHHAB(AB)s

25、ub1ABHHLL“1”A add AA add A add 1HHLHA+BA add (A+B)A add (A+B)add 1HHHLA+BA add (A+B)Aadd(A+B)add 1HHHHAA sub 1A 5.3 Analysis of the design of a commercial ALU chipLogic maps and function table of 4-bits ALU1111000000000000000000G0 = A0+B0 = A0 B0 P0 = A0 B0 = A0+B0G0 P0 = G0P0 + G0P0 = (A0+B0)(A0+B0

26、) + (A0 B0)(A0B0) = 0+A0B0 + A0B0 + 0+0 = A0 B000000000A0B0 C0A1B1 C1vSN741815.3 Analysis of the design of a commercial ALU chipv16-bits ALU Four 74181 circuits can forms 16-bits ALU Fast carry in chip, and one by one between chips. So it would take relative long time to generate F0F1516-bits ALU fo

27、rmed by 4 ALU chips5.3 Analysis of the design of a commercial ALU chip5.3 Analysis of the design of a commercial ALU chipv16-bits ALU Take 4 bits as a group. Using method like “4-bit carry look-ahead adder” to implement 16-bits ALU (formed by 4 ALU chips)，a 16-bit fast ALU can be gained. 74181 ALU c

28、an generate Gn，Pn，then 16-bit fast ALU can be implemented by AND OR NOT gates and 4 ALU chips 74182 (Look-ahead carry extender) can be gained by implementing logic circuit of Cn1、Cn2、Cn3v16-bits fast ALU74181A15A12B15B127418274181A11A8B11B874181A7A4B7B474181A3A0B3B0C0F3F0G4 P4 C3 G3 P3 C2 G2 P2 C1 G1 P1F7F4F11F8F15F12G PC05.3 Analysis of the design of a commercial ALU chipv32-bits fast ALU Two 16-bit 74182 and eight 74181 can form a 32-bit ALU circuit5.3 Analysis of the design of