EE380 Assignment 3

This is the sample solution.

1. 50% 50% This (now familiar) MIPS/SPIM program includes a subroutine called myadd that performs x=y+z;. In the space below, replace the myadd subroutine with one named mymul that will compute x=y*z;. (Hint: use addu because add detects overflow.) You should test your routine using SPIM before you submit it. Although there are many ways to do a multiply, here's C code for one of them that you might want to use:

   extern int x, y, z;
   
   void
   mymul(void)
   {
        /* do z = x * y the hard way... */
        int t0 = x;
        int t1 = y;
        int t2 = 0;
        int t3 = 1;
   
        while (t3 != 0) {
             if ((t0 & t3) != 0) {
                  t2 += t1;
             }
             t1 += t1;
             t3 += t3;
        }
   
        z = t2;
   }
   

   
   #### # # Multiply routine: # # z = x * y # .text .globl mymul mymul: la $t0, x # t0 = x lw $t0, 0($t0) la $t1, y # t1 = y lw $t1, 0($t1) or $t2,$0,$0 # t2 = 0 ori $t3,$0,1 # t3 = 1 while: beq $t3,$0,elihw if: and $t4,$t0,$t3 beq $t4,$0,fi addu $t2,$t2,$t1 # t2 += t1 fi: addu $t1,$t1,$t1 # t1 += t1 addu $t3,$t3,$t3 # t3 += t3 j while elihw: la $t4, z # z = t2 sw $t2,0($t4) jr $ra # return
2. 50% 50% The sgn(x), or signum, function returns -1, 0, or 1 respectively, for negative, zero, or positive values of X. Using only MIPS integer instructions, write a function that will make y = sgn(x) where x and y are floating-point numbers. Your function only needs to handle ordinary float values correctly, not NaN, etc. Hint: MIPS uses IEEE format floats; the value -1.0 is the bit pattern 0xbf900000, 0.0 is 0x00000000, and 1.0 is 0x3f900000.

   
   

   #### # # Float signum # # y = sgn(x) # .text .globl mysgn mysgn: la $t0, x # t0 = &x lw $t1,0($t0) # t1 = x beq $t1,$0,done # done if x == 0.0 li $t2,0x80000000 # sign bit and $t1,$t1,$t2 li $t2,0x3f900000 # 1.0 or $t1,$t1,$t2 # combine with sign bit done: la $t0, y # y = sgn(x) sw $t1,0($t0) jr $ra # return

3. 100% In mathematics, both addition and multiplication are associative -- regrouping using parenthesis does not change the value computed. Is this true for 32-bit 2's complement binary integers? Is it true for 32-bit single-precision IEEE-format floating-point values? Briefly explain your answer.
   Float addition very commonly violates associativity. The first step in addition of floats is the denormalization of the value with the smaller exponent, which causes loss of bits from the mantissa. Adding similar values that differ in sign also can cause loss of accuracy by cancellation. Integer operations are associative, and float multiply is usually ok if intermediate values don't bump into range limits.

4. 100% In multiplying an integer, X, by 14 using the basic shift-and-add algorithms discussed in class and in the book, what is the minimum number of addition/subtraction operations that must be performed? Show the values that are added or subtracted (hint: use (X<<Y) to represent the value of X shifted by Y bit positions).
   14 in binary is 1110. Thus, X*14 is (X*2)+(X*4)+(X*8), or (X<<1)+(X<<2)+(X<<3). However, we can do better using Booth's algorithm. X*14 is also (X*16)-(X*2), or just (X<<4)-(X<<1).
5. 100% The speculative carry adder discussed in class can be viewed as an example of tuning architecture to make the expected cases more efficient. In am empirical study of various unix programs some years ago, Prof. Dietz found that nearly all integer multiplies are by either +1 or -1 rather than by arbitrary integers. This is because the compiler used converted multiplies by constants into shift-and-add sequences; the multiply by a variable which is either +1 or -1 occurs within atoi() and scanf(), which are very commonly used library functions. Does this suggest a way to make a faster integer multiplier? Explain.
   Multiply by +1 just returns the other operand, and by -1 returns the negative of the other operand. It would be trivial to make the circuit recognize these cases and bypass the usual logic... it would take just one cycle, not multiple shift-and-add cycles. Of course, Booth's algorithm also can do this, but requires more circuitry than a dumb multiplier + special case logic for +/-1.