CDA 3101 Spring 2001 Introduction to Computer Organization

CDA 3101 Summer 2007 Introduction to Computer Organization Division 14 June 2007 Review Multiplication can be implemented using simple shift and add hardware Algorithm is similar to the grade-school method Booths algorithm for twos complement Handles all cases of positive/negative operands More efficient than conventional algorithm 2n + 2n-1 + 2n-2 + + 2k = 2n+1 - 2k Further optimization is possible MIPS multiply instructions ignore overflow Multu: Hi = 0 Mult: Hi = replicated sign of Lo Division Long division of unsigned binary integers 00001101 Divisor Partial remainders 1011 10010011 1011 Quotient Dividend

001110 1011 001111 1011 100 Remainder Dividend = Quotient x Divisor + Remainder Unsigned Division M Divisor Q Dividend Count n, A START 0 Shift left: A, Q A A-M No Q0 A < 0? Yes 1 A Count No Q0 0

A+M Count - 1 Count = 0? Yes END Quotient in Q Remainder in A Division Hardware Divisor M31 M0 32-bit ALU 4 Add 2 Subtract 4 write 0 4 write 1 Control 1 SLL 3 ... A31 ... A0 Q31

... Dividend Q0 Examples 7/3: A 0000 0000 1101 0000 0001 1110 0001 0011 0000 0000 0001 1110 0001 Q M = 0011 0111 Initial values 1110 1110 1110 1100 1100 1100 1000 1000 1001 0010 0010 0010

Shift A=A-M A=A+M 1 Shift A=A-M A=A+M 2 Shift A=A-M Q0 = 1 3 Shift A=A-M A=A+M 4 Signed Division Simplest solution Negate the quotient if the signs of divisor and dividend disagree Remainder and dividend must have the same signs Remainder = (Dividend Quotient * Divisor) (+7) / (+3): Q = 2; R = 1 (-7) / (+3): Q = -2; R = -1 (+7) / (-3): Q = -2; R = 1 (-7) / (-3): Q = 2; R = -1 Signed Division Algorithm A, Q Dividend M

Divisor, Count START Shift left: A, Q A31, Count Count - 1 S A A+M No No Restore A No n M31 = A31? S = A31? A A-M Yes Yes A=0 and Q=0 ? No Yes

Count = 0? Yes Q0 END 1 Quotient in Q Remainder in A Examples (1/2) A 0000 0000 1101 0000 0001 1110 0001 0011 0000 0000 0001 1110 0001 Q M = 0011 0111 Initial values 1110 Shift Subtract Restore 1

1110 Shift 1100 Subtract 2 Restore 1100 1000 1001 0010 Shift Subtract Q0 = 1 Shift Subtract Restore 0010 (7) / (3) 3 4 A 0000 0000 1101 0000 0001 1110 0001 0011 0000 0000 0001 1110 0001 Q M = 1101

0111 Initial values 1110 1110 1100 1100 1000 1001 0010 Shift Add Restore 1 Shift Add Restore 2 Shift Add Q0 = 1 3 Shift Add Restore 4 0010 (7) / (-3) Examples (2/2) A 1111 1111

0010 1111 1110 0001 1110 1100 1111 1111 1111 0010 1111 Q M = 0011 1001 Initial values 0010 0010 0100 0100 1000 1001 0010 Shift Add Restore Shift Add Restore Shift Add Q0 = 1 Shift Add Restore 0010 (-7) / (3) 1

2 3 4 A 1111 1111 0010 1111 1110 0001 1110 1100 1111 1111 1111 0010 1111 Q M = 1101 1001 Initial values 0010 0010 0100 0100 1000 1001 0010 Shift Subtract Restore 1 Shift Subtract Restore

2 Shift Subtract Q0 = 1 3 Shift Subtract Restore 4 0010 (-7) / (-3) MIPS Multiply and divide use existing hardware ALU and shifter Extra hardware: 64-bit register able to SLL/SRA Hi contains the remainder (mfhi) Lo contains the quotient (mflo) Instructions Div: Divu: signed divide unsigned divide MIPS ignores overflow ? Division by 0 must be checked in software MIPS Processor Registers 32

0 Sign extend 16 1 IR: M Sub ALU Operation Control Unit Zero Overflow 0 1 Hi 2 Memory address Lo SLL/SRA Have a Great Weekend!!