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
Hardware for a Shift and Add Multiplier
Algorithm Flowchart for a Shift and Add Multiplier

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
Division Flowchart

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?

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.