CS147 Computer Architecture Project 1

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.

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.

E. 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’sshown here as 64 bits to highlight the evolution from Figure 3.3.)

F. 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 111100₂ (60₁₀) and divisor is 010001₂ (17₁₀). Again, your program must display numbers with exactly n bits. You could lose 5pt if your program cannot work for different value of n.

FIGURE 3.8 First version of the division hardware. The Divisor register, ALU, and Remainder register are all 64 bits wide, with only the Quotient register being 32 bits. The 32-bit divisor starts in the left half of the Divisor register and is shifted right 1 bit each iteration. The remainder is initialized with the dividend. Control decides when to shift the Divisor and Quotient registers and when to write the new value into the Remainder register.

Figure 3.9. A division algorithm, using the hardware in Figure 3.8. If the remainder is positive, the divisor did go into the dividend, so step 2a generates a 1 in the quotient. A negative remainder after step 1 means that the divisor did not go into the dividend, so step 2b generates a 0 in the quotient and adds the divisor to the remainder, thereby reversing the subtraction ofstep 1. The final shift, in step 3, aligns the divisor properly, relative to the dividend for the next iteration. These steps are repeated 33 times.

G. 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 111100₂ (60₁₀) and divisor is 010001₂ (17₁₀). 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,

FIGURE 3.11 An improved version of the division hardware. The Divisor register, ALU, and Quotient register are all 32 bits wide, with only the Remainder register left at 64 bits. Compared to Figure 3.8, the ALU and Divisor registers are halved and the remainder is shifted left. This version also combines the Quotient register with the right half of the Remainder register. (As in Figure 3.5, the Remainder register should really be 65 bits to make sure the carry out of the adder is not lost.)

---

MIPS Project Answer

---

Multiplication

Start with long-multiplication approach

Starter Code

ex.3.12:
 sw $ra, ($sp)
 addi $sp, $sp, 4
 move $t0, $a0 # A = multiplicand
 move $t1, $a1 # B = multiplier
 move $t7, $a2 # N = number of bits for display, assume N <= 16
 li $t6, 0
loop:
 beq $t7, $0, done # if $t1==0 quit loop
 andi $t4, $t1, 1 # t4 = right most bit of multiplier t1.
 beq $t4, 0, ZERO # if t4 == 0, then jump to ZERO
ONE:
 addu $t6, $t6, $t0 # otherwise, t1 is one, so we do t6 += t0 (multiplicand)
ZERO :
 sll $t0, $t0, 1 # shift t0 (multiplicand) 1 bit to the left
 srl $t1, $t1, 1 # shift t1 (multiplier) 1 bit to the right
 addi $t7, $t7 -1
 j loop

Optimized Multiplier

Perform steps in parallel: add/shift

Product is 64-bit long, stored in two registers

Starter Code

ex.3.13:
 sw $ra, ($sp)
 addi $sp, $sp, 4
 move $t0, $a0 # t0 = multiplicand
 move $t6, $a1 # t6 = multiplier.
 move $t7, $a2 # number of bits,
 move $t1, $a2 # loop count
loop:
 beq $t1, $0, done # if $t1==0 quit loop
 addi $t1, $t1, -1 # t1 --;
 andi $t4, $t6, 1 # t4 = right most bit of multiplier t6.
 beq $t4, 0, ZERO # if t4 == 0, jump to ZERO
ONE:
 sllv $t5, $t0, $t7
 addu $t6, $t6, $t5 #
ZERO :
 srl $t6, $t6, 1 # shift t6 1 bit to the right
 j loop

Print Rightmost N Bits

display.bits: # display the rightmost n bits of the number x in a0,
#where n is specified in $a2
 li $t2, 32
 sub $t2, $t2, $a2 # t2 = 32 - n
 sllv $t3, $a0, $t2 # t3 = x << (32-n)
 move $t2, $a2 # t2 = n
L1:move $a0, $t3 # a0 = t3
 srl $a0, $t3, 31 # a0 = t3 >> 31
 li $v0, 1 # print MSB as an integer
 syscall
 sll $t3, $t3, 1 # t3 = x << 1
 addi $t2, $t2, -1 # n--
 beq $t2, $0, return #
 j L1

Print Rightmost 6 Bits of a Number

# print the right most 6 bits of integer x in 32-bit register $t0 (001010)
00000000 00000000 00000000 00001010 # t0 = 001000101000 00000000 00000000 00000000 # t1 = t0 << 26 (32-6)
00000000 00000000 00000000 00000000 # t2 = t1 >> 31, (MSB of t0)
print t2 # print 0 (MSB of x)
01010000 00000000 00000000 00000000 # t1 = t1 << 1
00000000 00000000 00000000 00000000 # t2 = t1 >> 31, (2nd MSB of t0)
print t2 # print 0 (2nd MSB of x)
10100000 00000000 00000000 00000000 # t1 = t1 << 1
00000000 00000000 00000000 00000001 # t2 = t1 >> 31, (3rd MSB of t0)
print t2 # print 1 (3rd MSB of x)
01000000 00000000 00000000 00000000 # t1 = t1 << 1
00000000 00000000 00000000 00000001 # t2 = t1 >> 31, (4th MSB of t0)
print t2 # 0 (4th MSB of t0)
# repeat 2 more times

Integer Division Hardware

Fig 3.11 An Improved Division Hardware

The Divisor register, ALU, and Quotient register are all 32 bits wide, with only the Remainder register left at 64 bits. Compared to Figure 3.8, the ALU and Divisor registers are halved and the remainder is shifted left.