CS274: Computer Architecture - Computer Arithmetic: Multiplication and Division

Activity Goals

The goals of this activity are:
  1. To be able to multiply and divide integers using a basic algorithm
  2. To optimize those algorithms for speed

Supplemental Reading

Feel free to visit these resources for supplemental background reading material.

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: Multiplication with a Simple Algorithm

Multiplication with a Simple Algorithm

Questions

  1. Using only shift and add instructions, multiply a value in a register $t0 by 3.
  2. Multiply 0010 by 0011 using this algorithm. What does it remind you of?
  3. Why does this algorithm require double the number of bits required for the input values to store the answer? In other words, why does 4-bit multiplication require an 8-bit result, and why does 32-bit multiplication require a 64-bit result?
  4. How might the MIPS architecture handle this 64-bit requirement, given that it only uses 32-bit registers?
  5. How might the MIPS architecture perform these additions, given that it uses a 32-bit adder? Hint - do you ever add more than 4 bits at a time in the example above?

Model 2: An Improved Multiplication Algorithm Using a 32-bit ALU

Multiplication using a 32-bit ALU

Questions

  1. Draw the updated flow chart and hardware diagram for this algorithm.
  2. How does this algorithm take advantage of unused hardware to simplify the hardware requirements?

Model 3: An Improved Multiplication Algorithm Using a 32-bit ALU and Reduced Hardware

Multiplication using a 32-bit ALU and Reduced Hardware

Questions

  1. Draw the updated hardware diagram for this algorithm. What components are consolidated, and were they previously unused?

Model 4: Division

Division with a Simple Algorithm

Questions

  1. Draw the hardware diagram and flowchart for this algorithm.
  2. Where do you initialize the divisor and dividend for this algorithm?
  3. Divide 0110 by 0011 using this algorithm.
  4. The quotient and remainder are each 4-bit values (or 32-bit values for 32-bit division). Where does MIPS store these results?
  5. What MIPS instructions support multiplication and division?
  6. What MIPS instructions support manipulating the low and high register components?

Model 5: Improved Division Using a 32-bit ALU and Reduced Hardware

Division using a 32-bit ALU and Reduced Hardware
Hardware for a Binary Division Circuit
Algorithm Flowchart for a Binary Division Circuit

Questions

  1. Draw the updated hardware diagram for this algorithm.
  2. How do these improvements compare to those you saw with the multiplier circuit and algorithm?

Model 6: Key Formulas and Concepts Recap

A quick-reference recap of the key rules from this activity. Try to reproduce each one from memory before peeking!

Key Rules and Formulas
  • Result sizes: multiplying two n-bit values needs up to 2n bits (e.g. 1111 * 1111 = 15 * 15 = 225 = 1110 0001, 8 bits); division of n-bit values yields an n-bit quotient and an n-bit remainder. MIPS holds these 64 bits in the hi/lo register pair.
  • Shift-and-add multiplication: for each bit of the multiplier from LSB to MSB: (1) if the bit is 1, add the multiplicand to the product; (2) shift the multiplicand left (or, in the improved version, shift the product right); (3) shift the multiplier right. Repeat n times.
  • Multiply/divide by powers of two with shifts: x << k = x * 2^k and x >> k = x / 2^k. Micro-example: x * 3 = (x << 1) + x.
  • Restoring division: repeatedly subtract the divisor from the remainder; if the result is negative, add the divisor back (restore) and shift a 0 into the quotient, otherwise shift in a 1; shift the divisor right (or remainder left) and repeat.
  • Division sanity check: dividend = quotient * divisor + remainder, with 0 <= remainder < divisor. Micro-example: 0110 / 0011: 6 = 2 * 3 + 0, so quotient 0010, remainder 0000.
  • Hardware improvement idea: a 32-bit ALU suffices for 64-bit products because each step only ever adds 32 bits; shifting the product register right lets the multiplier share the product register's unused half.
  • MIPS instructions: mult/multu and div/divu compute into hi (upper product bits / remainder) and lo (lower product bits / quotient); mfhi/mflo move the results into general-purpose registers; sll/srl shift.

Worked Step Table: 0010 x 0011 (2 x 3) by shift-and-add 
Step | Multiplier | Multiplicand | Action                  | Product
 0   |    0011    |  0000 0010   | initialize              | 0000 0000
 1   |    0011    |  0000 0010   | LSB=1: add multiplicand | 0000 0010
     |    0001    |  0000 0100   | shift both              |
 2   |    0001    |  0000 0100   | LSB=1: add multiplicand | 0000 0110
     |    0000    |  0000 1000   | shift both              |
 3-4 |    0000    |     ...      | LSB=0: shift only       | 0000 0110
Result: 0000 0110 = 6.  Correct: 2 x 3 = 6!

Glossary
TermMeaning
MultiplicandThe value being multiplied (added repeatedly)
MultiplierThe value whose bits decide whether to add at each step
ProductThe result register, up to 2n bits wide
DividendThe value being divided
DivisorThe value divided by
Quotient / RemainderThe whole-number result and what is left over
Restoring divisionDivision that adds the divisor back after a subtraction goes negative
hi / loMIPS registers holding the upper/lower product halves, or remainder/quotient
Booth's algorithmA signed multiplication algorithm that recodes runs of 1s (see additional reading)

Questions

  1. Without looking, multiply 0011 by 0101 with the step table method, then check your answer in decimal (3 x 5 = 15).

Submission

I encourage you to submit your answers to the questions (and ask your own questions!) using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section. You can find the link to the class notebook on the syllabus.

For Additional Practice

Feel free to visit these resources for additional practice exercises.