Assignment 8, due Jul 10Solutions
Part of
the homework for CS:2630, Summer 2018

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!
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.
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 32bit 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 logarithmictime solutions instead of linear ones. The above code is linear, the time taken to shift n bits is proportional to n. A logarithmictime 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 logarithmictime 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