程序代写代做 algorithm go computer architecture CS147_S2: Computer Architecture

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