# 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!!

## Recently Viewed Presentations

• Corpus Juris of Islamic Law. Qur'an - direct uncreated revelation. Tafsīr - commentary on the Quran. Sīrah. Rasūl. Allāh - usual habits and practices of Muhammad or the biography of the Messenger. Hadith - narration on the words and deeds....
• Ghana's location was ideal. It was just north of the rich gold fields. By about A.D. 800, Ghana was a major trading kingdom. Ghana's capital, KumbiSaleh, was divided into 2 cities. One was the center of trade. The other was...
• Person-centered care means that nursing home residents are supported in achieving the level of physical, mental and psychosocial well-being that is individually practicable. This goal honors the importance of keeping the person at the center of the care planning and...
• Quantitative Questions 1) A 100 kg wooden crate is at rest on a level stone floor. Let .(a) What is the minimum horizontal force needed to start the crate moving? (b) What is the minimum horizontal force needed to keep...
• HPLC Analysis of Ionic Compounds Nicholas H. Snow Seton Hall University HPLC of Ionic Compounds Ion Suppression Ion Exchange Chromatography (IEX or IEC) Ion Pair Chromatography (IPC) Weak Acid Equilibrium LeChatelier Principle Ion Suppression Weak acid - Use pH 2-3...
• Changed from 7-12 Business Certification with areas of specialization, Accounting, Data Processing, Office Technology etc. to K-12 Business, Computer and Information Technology (BCIT) This recommendation has 5 parts as follows: Add 2 semesters (1 year) of Visual Basic course to...
• Network Systems Security ... Allied Hagelin, Japanese Purple Implement a very complex, varying substitution cipher Use a series of cylinders, each giving one substitution, which rotate and change after each letter was encrypted With 3 cylinders, have 263=17576 alphabets History...
• The Tonghak Rebellion 1892-1895. Koreans responded to the opening of their country in two ways: there were some attempts at reform but there was also violent protests and rebellions. The Tonghak Rebellion was a huge revolutionary peasant movement that was...