Assignment 8, due Mar 27

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 (usually Friday). 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: In C, Java or Python, you can write expressions like 1<<i where the shift count is a constant. In contrast, the Hawk architecture (like many other computers) only has constant shift counts in its shift instructions. If you wanted to compute 1<<i on the Hawk, with the result in R3 and the unsigned variable i in R4, you could do it with the following simple iterative solution:

           LIS     R3,1
           TESTR   R4
           BZS     DONE
   LOOP:   SL      R3,1
           ADDSI   R4,-1
           BZR     LOOP
   DONE:
   

   Here is a clever alternative solution:

           LIS     R3,1
           BITTST  R4,0
           BBR     SKIP0
           SL      R3,1
   SKIP0:  BITTST  R4,1
           BBR     SKIP1
           SL      R3,2
   SKIP1:  BITTST  R4,2
           BBR     SKIP2
           SL      R3,4
   SKIP2:  BITTST  R4,3
           BBR     SKIP3
           SL      R3,8
   SKIP3:  BITTST  R4,4
           BBR     SKIP4
           SL      R3,16
   SKIP4:
   

   a) Assuming all instructions take the same amount of time, what is the smallest shift count (in R4) for which the clever alternative is faster? (0.4 points)

   b) Under the same assumptions, what is the largest shift count (in R4) for which the simple iterative solution is faster? (0.4 points)

   c) How many shift (or shift-add) instructions are included in the clever alternative solution? (Hint: You will probably have to look things up in the Hawk manual to find out which of the instructions are shift instructions. (0.2 points)

2. A problem:

   Give the fastest Hawk code you can to multiply by 2015. (1.0 points)

3. Background: Consider the first version of TIMESUL given in section 14.3 of the Hawk manual. This returns the low 32 bits of the unsigned product of two 32-bit numbers in R3.

   A problem: Modify this code so it returns the low 32 bits of the product in R3 and the high 32 bits of the product in R4. (1.0 points)

   Hint: Study how to do 64-bit shifts, a subject discussed in the section on Division in Chapter 9 of the notes and also in Section 10 of the Hawk manual. You should also look at which bits of R4 contain useful information as TIMESUL performs successive iterations.