CS152 Computer Architecture and Engineering Lecture 6 Divide Floating Point Pentium Bug Feb 10 1999 John Kubiatowicz http cs berkeley edu kubitron lecture slides http www inst eecs berkeley edu cs152 2 10 99 UCB Spring 1999 CS152 Kubiatowicz Outline of Today s Lecture Recap of Last Lecture and Introduction of Today s Lecture 4 min Divide 20 min Questions and Administrative Matters 2 min Floating Point 25 min Questions and Break 5 min Pentium Bug 25min 2 10 99 UCB Spring 1999 CS152 Kubiatowicz Recap of Last Lecture Summary Intro to VHDL entity symbol architecture schematic signals wires behavior can be higher level x boolean expression A B C D On line Design Notebook Open a window with editor or our tool cut paste Multiply successive refinement to see final design 32 bit Adder 64 bit shift register 32 bit Multiplicand Register Booth s algorithm to handle signed multiplies There are algorithms that calculate many bits of multiply per cycle see exercises 4 36 to 4 39 in COD Shifter Best implemented with technology specific methodologies What s Missing from MIPS is Divide Floating Point Arithmetic Next time the Pentium Bug 2 10 99 UCB Spring 1999 CS152 Kubiatowicz Recap VHDL combinational example ENTITY nandnor is GENERIC delay TIME 1ns PORT a b IN VLBIT x y OUT VLBIT END nandnore ARCHITECTURE behavioral OF nandnor is BEGIN x a NOR b AFTER delay y a NAND x AFTER delay END behavioral 2 10 99 UCB Spring 1999 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 10 99 Control Write UCB Spring 1999 CS152 Kubiatowicz Review Booth s Algorithm Insight 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 Middle of run of 1s 0001111000 none 0 1 End of run of 1s 0001111000 add 0 0 Middle of run of 0s 0001111000 none Originally for Speed when shift was faster than add Replace a string of 1s in multiplier with an initial subtract when we first see a one and then later add for the bit after the last one 2 10 99 UCB Spring 1999 1 10000 01111 CS152 Kubiatowicz Radix 4 Modified Booth s Algorithm Current Bits Bit to the Right Explanation Example Recode 00 0 Middle of zeros 00 00 00 00 00 01 0 Single one 00 00 00 01 00 10 0 Begins run of 1s 00 01 11 10 00 11 0 Begins run of 1s 00 01 11 11 00 1 00 1 Ends run of 1s 00 00 11 11 00 1 01 1 Ends run of 1s 00 01 11 11 00 2 10 1 Isolated 0 00 11 10 11 00 1 11 1 Middle of run 00 11 11 11 00 0 1 2 0 1 10000 01111 Same insight as one bit Booth s simply adjust for alignment of 2 bits Allows multiplication 2 bits at a time 2 10 99 UCB Spring 1999 CS152 Kubiatowicz Review Combinational Shifter from MUXes A B Basic Building Block 1 sel 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 if we use 4 1 Muxes 2 10 99 UCB Spring 1999 CS152 Kubiatowicz Funnel Shifter Instead Extract 32 bits of 64 Y X Shift Right Shift A by i bits sa shift right amount Logical Y 0 R Y X A sa i Arithmetic Y Sign X A sa i Rotate Y A Left shifts Y A 2 10 99 X 32 Shift Right X A sa i X 0 sa 32 i UCB Spring 1999 32 32 R CS152 Kubiatowicz Barrel Technology dependent solutions transistor per switch Shifter SR3 SR2 SR1 SR0 D3 D2 A6 D1 A5 D0 A4 A3 2 10 99 A2 A1 UCB Spring 1999 A0 CS152 Kubiatowicz Divide Paper Pencil 1001 Quotient Divisor 1000 1001010 Dividend 1000 10 101 1010 1000 10 Remainder or Modulo result See how big a number can be subtracted creating quotient bit on each step Binary 1 divisor or 0 divisor Dividend Quotient x Divisor Remainder Dividend Quotient Divisor 3 versions of divide successive refinement 2 10 99 UCB Spring 1999 CS152 Kubiatowicz DIVIDE HARDWARE Version 1 64 bit Divisor reg 64 bit ALU 64 bit Remainder reg 32 bit Quotient reg Shift Right Divisor 64 bits Quotient 64 bit ALU Remainder 32 bits Write 64 bits 2 10 99 Shift Left UCB Spring 1999 Control CS152 Kubiatowicz Divide Algorithm Version 1 Takes n 1 steps for n bit Quotient Rem Remainder Quotient Divisor 0000 0111 0000 0010 0000 Start Place Dividend in Remainder 1 Subtract the Divisor register from the Remainder register and place the result in the Remainder register Remainder 0 2a Shift the Quotient register to the left setting the new rightmost bit to 1 Test Remainder Remainder 0 2b Restore the original value by adding the Divisor register to the Remainder register place the sum in the Remainder register Also shift the Quotient register to the left setting the new least significant bit to 0 3 Shift the Divisor register right1 bit n 1 repetition No n 1 repetitions Yes n 1 repetitions n 4 here 2 10 99 UCBDone Spring 1999 CS152 Kubiatowicz Observations on Divide Version 1 1 2 bits in divisor always 0 1 2 of 64 bit adder is wasted 1 2 of divisor is wasted Instead of shifting divisor to right shift remainder to left 1st step cannot produce a 1 in quotient bit otherwise too big switch order to shift first and then subtract can save 1 iteration 2 10 99 UCB Spring 1999 CS152 Kubiatowicz Divide Paper Pencil Divisor 0001 01010 Quotient 00001010 00001 0001 0000 0001 0001 0 00 Dividend Remainder or Modulo result Notice that there is no way to get a 1 in leading digit this would be an overflow since quotient would have n 1 bits 2 10 99 UCB Spring 1999 CS152 Kubiatowicz DIVIDE HARDWARE Version 2 32 bit Divisor reg 32 bit ALU 64 bit Remainder reg 32 bit Quotient reg Divisor 32 bits Quotient 32 bit ALU Shift Left 32 bits Shift Left Remainder 64 bits 2 10 99 Control Write UCB Spring 1999 CS152 Kubiatowicz Divide Algorithm Version 2 Remainder Quotient Divisor 0000 0111 0000 0010 Start Place Dividend in Remainder 1 Shift the Remainder register left 1 bit 2 Subtract the Divisor register from the left half of the Remainder register place the result in …
View Full Document
Unlocking...