Assignment 8, due Jul 10

On every assignment, write your name legibly as it appears on your University ID card! Homework is due on paper at the start of class on the day indicated (Tuesday or Thursday). Exceptions will be made only by advance arrangement (excepting "acts of God"). Late work must be turned in to the TA's mailbox (ask the CS receptionist in 14 MLH for help). Never push homework under someone's door!

1. Background: Compare the code of the TIMESU routine in the Hawk monitor with the different versions of the MULTIPLY routine given in the first third of Chapter 9.

   a) Which of the MULTIPLY routines from the notes is most similar to TIMESU? (0.3 points)

   TIMESU routine in the Hawk monitor seems closest to the version captioned Faster binary multiplication on the Hawk (the second of 3 versions given).

   b) What difference is there, if any, between TIMESU and the most similar version of MULTIPLY? Ignore cosmetic differences such as labels, indenting, or comment text. (0.4 points)

   i) TIMESU takes parameters in R4 and R5 instead of R3 and R4.

   ii) TIMESU uses a definite loop instead of an indefinite loop.

   iii) the body of the loop in TIMESU has been unrolled one step.

   iv) the product is shifted instead of the multiplicand.

   v) the partial products are computed most significant first so the multiplier is shifted left instead of right.

   c) What is the benefit of this difference, if any? (0.3 points)

   i) this saves one MOVE instruction.

   ii) this allows loop unrolling but at the cost of extra iterations for small values of the multiplier.

   iii) unrolling saved 1 instruction per iteration of the original loop.

   iv) no obvious benefit but this seems to be a consequence of change v).

   v) no obvious benefit.

2. Background: The Hawk shift instructions allow you to write machine code equivalent to the C (or Python or Java) expression x << c for small constant values of c. There is no simpe machine instruction on the Hawk to do x << y for arbitrary variable values of y. If C only allowed constant shift counts, you could write a subroutine like this to solve the general case:

   int leftshift( int a, int b ) {
           while (b > 0) {
                   a = a << 1;
                   b = b - 1;
           }
           return a;
   }
   

   The above subroutine is far from optimal. Consider a call to leftshift(x,1000) on a computer with a 32-bit word. After the first 32 iterations, a will not change, yet the loop will continue for hundreds of additional useless iterations.

   Computer scientists are well known for looking for logarithmic-time solutions instead of linear ones. The above code is linear, the time taken to shift n bits is proportional to n. A logarithmic-time solution can be written that tests each bit of the shift count b, shifting a one place if b is odd, two places if the next bit is set, three places if the next bit, and so on.

   a) Translate the C code given above into well commented SMAL Hawk code. Note that you should be able to solve this with just 6 machine instructions. (1 point)

   LEFTSHIFT: ; given   R3 = a -- the number to shift
              ;         R4 = b -- the shift count
              ; returns R3 = a << b
              ; uses    R4
           TESTR   R4
           BZS     LSQUIT  ; if (b > 0) {
   LSLOOP:                 ;   loop {
           SL      R3,1    ;     a = a << 1
           ADDSI   R4,-1   ;     b = b - 1
           BZR     LSLOOP  ;   } until (b == 0)
   LSQUIT:                 ; }
           JUMPS   R1      ; return a
   

   b) Write SMAL Hawk code for a logarithmic-time solution. Ignore the problem of shift counts greater than 31. Note that this can be solved with only 16 instructions, a return instruction plus 5 groups of 3 instructions, one group per bit of the shift count. (1 point)

   LEFTSHIFT: ; given   R3 = a -- the number to shift
              ;         R4 = b -- the shift count
              ; returns R3 = a << b
              ; uses    R4
           SR      R4,1    ; b = b >> 1
           BCR     LSBIT1  ; if (b used to be odd) {
           SL      R3,1    ;   a = a << 1
   LSBIT1:                 ; }
           SR      R4,1    ; b = b >> 1
           BCR     LSBIT2  ; if (b used to be odd) {
           SL      R3,2    ;   a = a << 2
   LSBIT2:                 ; }
           SR      R4,1    ; b = b >> 1
           BCR     LSBIT4  ; if (b used to be odd) {
           SL      R3,4    ;   a = a << 4
   LSBIT4:                 ; }
           SR      R4,1    ; b = b >> 1
           BCR     LSBIT8  ; if (b used to be odd) {
           SL      R3,8    ;   a = a << 8
   LSBIT8:                 ; }
           SR      R4,1    ; b = b >> 1
           BCR     LSBIT16 ; if (b used to be odd) {
           SL      R3,16   ;   a = a << 16
   LSBIT16:                ; }
           JUMPS   R1      ; return a