CS147_S2: Computer Architecture
Project #2
Simulation of Multiplication and Division Hardware
Student ID: _______________
Student Name: _______________
Points out of 100: _______________
• This document may be updated with more information and/or hints as needed.
• The provided codes may contain bugs and may be updated accordingly.
• More test cases or starter programs may be provided later.
• Purpose
MIPS has instructions for (integer) multiplication and division. In the project, we will study the hardware designs how to implement multiplication and division with the basic shift, addition and subtraction operations. We will write MIPS programs to simulate the operations of the hardware designs at each step. Two versions of the multiplication and division hardware will be used.
• Submission and grading criteria
• Program to simulate the first version of the multiplication hardware. (30%)
• Program to simulate the refined version of the multiplication hardware (30%)
• Program to simulate the first version of division hardware (30%)
• Two Essay Questions (10%)
• Your program will get 0 credit if any MIPS multiplication or division instructions are used.
• (Optional) program to simulate the improved version of the division hardware (30% bonus point)
To submit your work, compress all your work as a zipped file with file name project.2.zip.
• Program to simulate the first version of multiplication hardware (30%)
(Source: Exercise 3.12 in the textbook)
Write a MIP program, named ex.3.12.asm, to simulate the multiplication performed by the hardware described in Figure 3.3, for two unsigned n-bit integers A and B, where 1 n 32, and A, B < 2n. Your program should show the contents of each registers and their operations at each step similar to the example shown below, where A and B are both 6-bit unsigned integers 1100102 and 0010102 (5010 and 1010), respectively. The inputs to the program are two unsigned n-bit integers A and B in $a0 and $a1, and the number of bits (n) in $a2. Note that your program must display numbers with exactly n bits for each number. You could lose 5pt if your program cannot work for different value of n.
A starter program for 32-bit numbers is provided along with this assignment in Canvas.
FIGURE 3.3 First version of the multiplication hardware. The Multiplicand register, ALU, and Product register are all 64 bits wide, with only the Multiplier register containing 32 bits. (Appendix B describes ALUs.) The 32-bit multiplicand starts in the right half of the Multiplicand register and is shifted left 1 bit on each step. The multiplier is shifted in the opposite direction at each step. The algorithm starts with the product initialized to 0. Control decides when to shift the Multiplicand and Multiplier registers and when to write new values into the Product register.
•
Step
Action
Multiplier
Multiplicand
Product
0
Initial Vals
001 010
000 000 110 010
000 000 000 000
1
lsb=0, no op
001 010
000 000 110 010
000 000 000 000
Lshift Mcand
001 010
000 001 100 100
000 000 000 000
Rshift Mplier
000 101
000 001 100 100
000 000 000 000
2
Prod=Prod+Mcand
000 101
000 001 100 100
000 001 100 100
Lshift Mcand
000 101
000 011 001 000
000 001 100 100
Rshift Mplier
000 010
000 011 001 000
000 001 100 100
3
lsb=0, no op
000 010
000 011 001 000
000 001 100 100
Lshift Mcand
000 010
000 110 010 000
000 001 100 100
Rshift Mplier
000 001
000 110 010 000
000 001 100 100
4
Prod=Prod+Mcand
000 001
000 110 010 000
000 111 110 100
Lshift Mcand
000 001
001 100 100 000
000 111 110 100
Rshift Mplier
000 000
001 100 100 000
000 111 110 100
5
lsb=0, no op
000 000
001 100 100 000
000 111 110 100
Lshift Mcand
000 000
011 001 000 000
000 111 110 100
Rshift Mplier
000 000
011 001 000 000
000 111 110 100
6
lsb=0, no op
000 000
110 010 000 000
000 111 110 100
Lshift Mcand
000 000
110 010 000 000
000 111 110 100
Rshift Mplier
000 000
110 010 000 000
000 111 110 100
FIGURE 3.4 The first multiplication algorithm, using the hardware shown in Figure 3.3. if the least significant bit of the multiplier is 1, add the multiplicand to the product. If not, go to the next step. Shift the multiplicand left and the multiplier right in the next two steps. These three steps are repeated 32 times.
• (30%) Program to simulate the refined multiplication hardware
(Source: Exercise 3.13 in the textbook)
Write a program, named ex.3.13.asm, that will simulate the refined version of the multiplication hardware described in Figure 3.5 and display the numbers as shown in the table below.
A starter program for 32-bit numbers is provided along with this assignment in Canvas.
Figure 3.5: Refined version of the multiplication hardware. Compare with the first version in Figure 3.3. The Multiplicand register, ALU, and Multiplier register are all 32 bits wide, with only the Product register left at 64 bits. Now the product is shifted right. The separate Multiplier register also disappeared. The multiplier is placed instead in the right half of the Product register. These changes are highlighted in color. (The Product register should really be 65 bits to hold the carry out of the adder, but it’s shown here as 64 bits to highlight the evolution from Figure 3.3.)
Step
Action
Multiplicand
Product/Multiplier
0
Initial Vals
110 010
000 000 001 010
1
lsb=0, no op
110 010
000 000 001 010
Rshift Product
110 010
000 000 000 101
2
Prod=Prod+Mcand
110 010
110 010 000 101
Rshift Mplier
110 010
011 001 000 010
3
lsb=0, no op
110 010
011 001 000 010
Rshift Mplier
110 010
001 100 100 001
4
Prod=Prod+Mcand
110 010
111 110 100 001
Rshift Mplier
110 010
011 111 010 000
5
lsb=0, no op
110 010
011 111 010 000
Rshift Mplier
110 010
001 111 101 000
6
lsb=0, no op
110 010
001 111 101 000
Rshift Mplier
110 010
000 111 110 100
• (30%) Program to simulate the first version of the division hardware
(Source: Exercise 3.18 in the textbook)
Repeat the process similar to the previous work, but this time write the program, named ex.3.18.asm, to simulate the division hardware as described in Figure 3.8. Your program should show the contents of each registers and their operations at each step similar to the example shown below, where the dividend is 1111002 (6010) and divisor is 0100012 (1710). Again, your program must display numbers with exactly n bits. You could lose 5pt if your program cannot work for different value of n.
Step
Action
Quotient
Divisor
Remainder
0
Initial Vals
000 000
010 001 000 000
000 000 111 100
1
Rem=Rem–Div
000 000
010 001 000 000
101 111 111 100
Rem<0,R+D,Q<<
000 000
010 001 000 000
000 000 111 100
Rshift Div
000 000
001 000 100 000
000 000 111 100
2
Rem=Rem–Div
000 000
001 000 100 000
111 000 011 100
Rem<0,R+D,Q<<
000 000
001 000 100 000
000 000 111 100
Rshift Div
000 000
000 100 010 000
000 000 111 100
3
Rem=Rem–Div
000 000
000 100 010 000
111 100 101 100
Rem<0,R+D,Q<<
000 000
000 100 010 000
000 000 111 100
Rshift Div
000 000
000 010 001 000
000 000 111 100
4
Rem=Rem–Div
000 000
000 010 001 000
111 110 110 100
Rem<0,R+D,Q<<
000 000
000 010 001 000
000 000 111 100
Rshift Div
000 000
000 001 000 100
000 000 111 100
5
Rem=Rem–Div
000 000
000 001 000 100
111 111 111 000
Rem<0,R+D,Q<<
000 000
000 001 000 100
000 000 111 100
Rshift Div
000 000
000 000 100 010
000 000 111 100
6
Rem=Rem–Div
000 000
000 000 100 010
000 000 011 010
Rem>0,Q<<1
000 001
000 000 100 010
000 000 011 010
Rshift Div
000 001
000 000 010 001
000 000 011 010
7
Rem=Rem–Div
000 001
000 000 010 001
000 000 001 001
Rem>0,Q<<1
000 011
000 000 010 001
000 000 001 001
Rshift Div
000 011
000 000 001 000
000 000 001 001
• (10%) Questions
3.14 (7%) Calculate the time necessary to perform a multiply using the approach given in Figures 3.3 and 3.4 if an integer is 8 bits wide and each step of the operation takes 4 time units. Assume that in step 1a an addition is always performed—either the multiplicand will be added, or a zero will be. Also assume that the registers have already been initialized (you are just counting how long it takes to do the multiplication loop itself). If this is being done in hardware, the shifts of the multiplicand and multiplier can be done simultaneously. If this is being done in software, they will have to be done one after the other. Solve for each case.
3.16 (3%) Calculate the time necessary to perform a multiply using the approach given in Figure 3.7 if an integer is 8 bits wide and an adder takes 4 time units.
• (Bonus 30%) Program to simulate the improved version of the division hardware
(Source: Exercise 3.19 in the textbook)
Similar to the previous work, write a program, named ex.3.19.asm to simulate the improved version the division hardware as described in Figure 3.11. Your program should show the contents of each registers and their operations at each step similar to the example below, where the dividend is 1111002 (6010) and divisor is 0100012 (1710). Again, your program must display numbers with exactly n bits. You could lose 5pt if your program cannot work for different value of n.
Note that this algorithm requires a slightly different approach than that shown in Figure 3.9. You will want to think hard about this, do an experiment or two, or else go to the web to figure out how to make this work correctly.
Hint: one possible solution involves using the fact that Figure 3.11 implies the remainder register can be shifted either direction.
Hint: In these solutions a 1 or a 0 was added to the Quotient if the remainder was greater than or equal to 0. However, an equally valid solution is to shift in a 1 or 0, but if you do this you must do a compensating right shift of the remainder (only the remainder, not the entire remainder/quotient combination) after the last step.
Step
Action
Divisor
Remainder/Quotient
0
Initial Vals
010 001
000 000 111 100
1
R<<
010 001
000 001 111 000
Rem=Rem–Div
010 001
111 000 111 000
Rem<0, R+D
010 001
000 001 111 000
2
R<<
010 001
000 011 110 000
Rem=Rem–Div
010 001
110 010 110 000
Rem<0,R+D
010 001
000 011 110 000
3
R<<
010 001
000 111 100 000
Rem=Rem–Div
010 001
110 110 110 000
Rem<0,R+D
010 001
000 111 100 000
4
R<<
010 001
001 111 000 000
Rem=Rem–Div
010 001
111 110 000 000
Rem<0,R+D
010 001
001 111 000 000
5
R<<
010 001
011 110 000 000
Rem=Rem–Div
010 001
111 110 000 000
Rem>0,R0=1
010 001
001 101 000 001
6
R<<
010 001
011 010 000 010
Rem=Rem–Div
010 001
001 001 000 010
Rem>0,R0=1
010 001
001 001 000 011