14:332:331Computer Architecture and Assembly LanguageSpring 2006Week 7 ALU DesignHead’s UpReview: MIPS Arithmetic InstructionsReview: A 32-bit Adder/SubtractorMinimal Implementation of a Full AdderLogic OperationsA Simple ALU CellAn Alternative ALU CellThe Alternative ALU Cell’s Control CodesTailoring the ALU to the MIPS ISAModifying the ALU Cell for sltModifying the ALU for sltModifying the ALU for ZeroReview: Overflow DetectionModifying the ALU for OverflowExample:Example: cont’dExample: cont’dExample: cont’dBut What about Performance?Fast carry using “infinite” hardware (Parallel)Hierarchical Solution IFirst Level: Propagate and generateHierarchical Solution I (16 bit)Hierarchical Solution IIHierarchical Solution IIFast Carry using the second level abstractionShift OperationsShift Operations, con’tMultiplicationMIPS Multiply InstructionReview: MIPS ISA, so farReview: MIPS ISA, so far con’tReview: MIPS ISA, so far con’t331 W07.1 Spring 200614:332:331Computer Architecture and Assembly LanguageSpring 2006Week 7 ALU Design[Adapted from Dave Patterson’s UCB CS152 slides andMary Jane Irwin’s PSU CSE331 slides]331 W07.2 Spring 2006Head’s Up This week’s materialz MIPS logic and multiply instructions- Reading assignment – PH 3.1-3.4z MIPS ALU design- Reading assignment – PH B.5, B.6331 W07.3 Spring 2006Review: MIPS Arithmetic InstructionsR-type:I-Type:31 25 20 15 5 0op Rs Rt Rd functop Rs Rt Immed 16Type op funct ADD 00 100000ADDU 00 100001SUB 00 100010SUBU 00 100011AND 00 100100OR 00 100101XOR 00 100110NOR 00 100111Type op funct00 10100000 101001SLT 00 101010SLTU 00 10101100 1011000 add1 addu2sub3 subu4 and5or6xor7 norasltbsltuz expand immediates to 32 bits before ALUz10 operations so can encode in 4 bits323232m (operation)resultABALU4zeroovf11331 W07.4 Spring 2006Review: A 32-bit Adder/Subtractoradd/subt1-bit FAS0c0=carry_inc11-bit FAS1c21-bit FAS2c3c32=carry_out1-bit FAS31c31. . . Built out of 32 full adders (FAs)A0A1B0B1A2B2A31B311 bit FAABScarry_incarry_outS = Axor Bxor carry_incarry_out = A∧B v A∧carry_in v B∧carry_in(majority function)Small but slow!331 W07.5 Spring 2006Minimal Implementation of a Full Adder Gate library: inverters, 2-input nands, or-and-invertersarchitecture concurrent_behavior of full_adder issignal t1, t2, t3, t4, t5: std_logic;begint1 <= not A after 1 ns;t2 <= not cin after 1 ns;t4 <= not((A or cin) and B) after 2 ns;t3 <= not((t1 or t2) and (A or cin)) after 2 ns;t5 <= t3 nand B after 2 ns;S <= not((B or t3) and t5) after 2 ns;cout <= not(t1 or t2) and t4) after 2 ns;end concurrent_behavior;Can you create the equivalent schematic? Can you determine worst case delay (the worst case timing path through the circuit)?331 W07.6 Spring 2006Logic Operations Logic operations operate on individual bits of the operand.$t2 = 0…0 0000 1101 0000$t1 = 0…0 0011 1100 0000and $t0, $t1, $t2 $t0 =or $t0, $t1 $t2 $t0 =xor $t0, $t1, $t2 $t0 =nor $t0, $t1, $t2 $t0 = How do we expand our FA design to handle the logic operations - and, or, xor, nor ?331 W07.7 Spring 2006A Simple ALU Cell1-bit FAcarry_incarry_outadd/subtadd/subtresultopAB331 W07.8 Spring 2006An Alternative ALU Cell1-bit FAcarry_ins2s1s0resultABcarry_out331 W07.9 Spring 2006The Alternative ALU Cell’s Control Codess2 s1 s0 c_in result function0 0 0 0 A transfer A0 0 0 1 A + 1 increment A0010A + Badd0 0 1 1 A + B + 1 add with carry0 1 0 0 A –B –1 subt with borrow0 1 0 1 A – B subtract0 1 1 0 A – 1 decrement A0 1 1 1 A transfer A100xA or Bor101xA xor Bxor1 1 0 x A and B and1 1 1 x !A complement A331 W07.10 Spring 2006Tailoring the ALU to the MIPS ISA Need to support the set-on-less-than instruction (slt)z remember: slt is an arithmetic instructionz produces a 1 if rs < rt and 0 otherwisez use subtraction: (a - b) < 0 implies a < b Need to support test for equality (beq)z use subtraction: (a - b) = 0 implies a = b Need to add the overflow detection hardware331 W07.11 Spring 2006Modifying the ALU Cell for sltcarry_in1-bit FAadd/subt opAresultBlesscarry_outadd/subt331 W07.12 Spring 2006Modifying the ALU for sltA0+A1B1result1less+B0less+A31B31First perform a subtraction Make the result 1 if the subtraction yields a negative result Make the result 0 if the subtraction yields a positive resultresult0less. . .result31331 W07.13 Spring 2006Modifying the ALU for Zero+A1B1result1less+A0B0result0less+A31B31result31less. . .0add/subtop First perform subtraction Insert additional logic to detect when all result bits are zero0set331 W07.14 Spring 2006Review: Overflow Detection Overflow: the result is too large to represent in the number of bits allocated Overflow occurs whenz adding two positives yields a negative z or, adding two negatives gives a positivez or, subtract a negative from a positive gives a negativez or, subtract a positive from a negative gives a positive On your own: Prove you can detect overflow by:z Carry into MSB xor Carry out of MSB11011001110011+7301–6110111001011+–4–5710331 W07.15 Spring 2006Modifying the ALU for OverflowA0+result1less+B0A1B1result0less+A31B31result31less. . .00set Modify the most significant cell to determine overflow output setting Disable overflow bit setting for unsigned arithmeticzero. . .add/subtopoverflow331 W07.16 Spring 2006Example:When do the result outputs settle at their final values for the inputs:add/subt = 0op = 000A = 1111B = 0001op+A1B1result1less+A0B0result0less+A3B3result3less00setzeroadd/subtoverflow+A2B2result2less0op+A1B1result1less+A0B0result0less+A3B3result3less00setzeroadd/subtoverflow+A2B2result2less00123452+2+6+4+8+8+8+8+6op+A1B1result1less+A0B0result0less+A3B3result3less00setzeroadd/subtoverflow+A2B2result2less0op+A1B1result1less+A0B0result0less+A3B3result3less00setzeroadd/subtoverflow+A2B2result2less00123452+2+6+4+8+8+8+8+6331 W07.17 Spring 2006Example: cont’dWhen do the result outputs settle at their final values for the inputs:add/subt = 0op = 100A = 1111B = 0001op+A1B1result1less+A0B0result0less+A3B3result3less00setzeroadd/subtoverflow+A2B2result2less0op+A1B1result1less+A0B0result0less+A3B3result3less00setzeroadd/subtoverflow+A2B2result2less00123452+2+6+4+8+8+8+8+6op+A1B1result1less+A0B0result0less+A3B3result3less00setzeroadd/subtoverflow+A2B2result2less0op+A1B1result1less+A0B0result0less+A3B3result3less00setzeroadd/subtoverflow+A2B2result2less00123452+2+6+4+8+8+8+8+6331 W07.18 Spring 2006Example: