CS152 Computer Architecture and Engineering Lecture 7 ALU Continued Designing a Single Cycle Datapath February 19 2003 John Kubiatowicz www cs berkeley edu kubitron lecture slides http inst eecs berkeley edu cs152 2 19 03 UCB Spring 2003 CS152 Kubiatowicz Review Unsigned Combinational Multiplier 0 0 0 A3 A3 A3 A3 P7 P6 A2 A2 A1 P5 A2 A1 A2 A1 A1 0 A0 B0 A0 B1 A0 B2 A0 P4 B3 P3 P2 P1 P0 Stage i accumulates A 2 i if Bi 1 Q How much hardware for 32 bit multiplier Critical path 2 19 03 UCB Spring 2003 CS152 Kubiatowicz Review MULTIPLY HARDWARE Version 3 32 bit Multiplicand reg 32 bit ALU 64 bit Product reg shift right 0 bit Multiplier reg Multiplican d 32 bits 32 bit ALU HI LO Shift Right Product Multiplier 64 bits 2 19 03 Control Write UCB Spring 2003 CS152 Kubiatowicz Review Booth s Algorithm Alternate representation end of run middle of run beginning of run 0 1 1 1 1 0 Current Bit Bit to the Right Explanation Example Op 1 0 Begins run of 1s 0001111000 sub 1 1 1 Middle of run of 1s 0001111000 none 0 0 1 End of run of 1s 0001111000 add 1 0 0 Middle of run of 0s 0001111000 none 0 Examples 8 bits 3 11111101 00000 1 1 1 4 2 1 14 00001110 000100 1 0 16 2 23 00010111 001 1 100 1 32 16 8 1 2 19 03 UCB Spring 2003 CS152 Kubiatowicz Review Radix 4 Modified Booth s Once admit new symbols i e 1 can have multiple representations of a number Current Bits Bit to the Right 00 0 Middle of zeros 00 00 00 00 00 00 0 01 0 Single one 00 00 00 01 00 01 1 10 0 Begins run of 1s 00 01 11 10 00 10 2 11 0 Begins run of 1s 00 01 11 11 00 01 1 00 1 Ends run of 1s 00 00 11 11 00 01 1 01 1 Ends run of 1s 00 01 11 11 00 10 2 10 1 Isolated 0 00 11 10 11 00 01 1 11 1 Middle of run 00 11 11 11 00 00 2 19 03 Explanation UCB Spring 2003 Example Recode 0 CS152 Kubiatowicz Review DIVIDE HARDWARE Version 3 32 bit Divisor reg 32 bit ALU 64 bit Remainder reg 0 bit Quotient reg Divisor 32 bits 32 bit ALU HI LO Shift Left Remainder Quotient 64 bits Control Write Multiplication and Division can use same hardware 2 19 03 UCB Spring 2003 CS152 Kubiatowicz Review Divide Algorithm Version 3 example 7 2 Remainder 0000 0111 0 0000 1110 1 1110 1110 2 0000 1110 3 0001 1100 1 1111 1100 2 0001 1100 3 0011 1000 1 0001 1000 2 0001 1000 3 0011 0001 1 0001 0001 2 0001 0001 3 0010 0011 E 0001 0011 2 19 03 Divisor 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 Initial Shift Try to subtract Can t Add back Shift in 0 Try to subtract Can t Add back Shift in 0 Try to subtract Success Shift in 1 Try to subtract Success Shift in 1 Correct remainder UCB Spring 2003 CS152 Kubiatowicz Non restoring version Remainder 0000 0111 0 0000 1110 1 1110 1110 3 1101 1100 1 1111 1100 3 1111 1000 1 0001 1000 3 0011 0001 1 0001 0001 3 0010 0011 E 0001 0011 Divisor 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 Initial Shift Try to subtract Negative Shift in Try to add neg Negative Shift in Try to Add Positive Shift in Try to subtract Positive Shift in Correct remainder 0 0 1 1 Insight Divisor 2 Divisor Divisor 2 19 03 UCB Spring 2003 CS152 Kubiatowicz MIPS logical instructions Instruction Example Meaning Comment and and 1 2 3 1 2 3 3 reg operands Logical AND or or 1 2 3 1 2 3 3 reg operands Logical OR xor xor 1 2 3 1 2 3 3 reg operands Logical XOR nor nor 1 2 3 1 2 3 3 reg operands Logical NOR and immediate andi 1 2 10 1 2 10 Logical AND reg constant or immediate ori 1 2 10 1 2 10 Logical OR reg constant xor immediate xori 1 2 10 1 2 10 Logical XOR reg constant shift left logical sll 1 2 10 1 2 10 Shift left by constant shift right logical srl 1 2 10 1 2 10 Shift right by constant shift right arithm sra 1 2 10 1 2 10 Shift right sign extend shift left logical sllv 1 2 3 1 2 3 Shift left by variable shift right logical srlv 1 2 3 1 2 3 Shift right by variable shift right arithm srav 1 2 3 1 2 3 Shift right arith by variable 2 19 03 UCB Spring 2003 CS152 Kubiatowicz Shifters Two kinds logical value shifted in is always 0 0 msb lsb 0 arithmetic on right shifts sign extend msb lsb 0 Note these are single bit shifts A given instruction might request 0 to 32 bits to be shifted 2 19 03 UCB Spring 2003 CS152 Kubiatowicz Combinational Shifter from MUXes A B Basic Building Block sel 1 0 D 8 bit right shifter A7 A6 A5 A4 A3 A2 A1 S2 S1 S0 A0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 R7 R6 R5 R4 R3 R2 R1 R0 What comes in the MSBs How many levels for 32 bit shifter What 2 19 03 if we use 4 1 Muxes UCB Spring 2003 CS152 Kubiatowicz General Shift Right Scheme using 16 bit example S0 0 1 S1 0 2 S2 0 4 S3 0 8 If added Right to left connections could support Rotate not in MIPS but found in ISAs 2 19 03 UCB Spring 2003 CS152 Kubiatowicz Funnel Shifter Instead Extract 32 bits of 64 Y X Shift Right Shift A by i bits sa shift right amount Logical R Y Y 0 X A sa i 32 Arithmetic Y X sa Rotate UCB Spring 2003 32 Shift Right Y X sa Left shifts Y X sa 2 19 03 X 32 R CS152 Kubiatowicz Barrel Shifter Technology dependent solutions transistor per switch SR3 SR2 SR1 SR0 D3 D2 A6 D1 A5 D0 A4 2 19 03 A3 A2 A1 UCB Spring 2003 A0 CS152 Kubiatowicz Recall What is in a number What can be represented in N bits Unsigned 0 to 2N 1 2s Complement 2N 1 to 2N 1 1 1s Complement 2N 1 1 to 2N 1 1 Excess M 2 M E e M to 2 N M 1 BCD 0 10N 4 1 to But what about very large numbers 9 349 398 989 787 762 …
View Full Document
Unlocking...