Assignment 8, due Mar 27

Part of the homework for CS:2630, Spring 2015
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

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

    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

    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.