Exam 3: FinalSolutions and Commentary
Part of
the homework for 22C:60 (CS:2630), Fall 2011
|
Mean = 7.10
Median = 7.0
X X X
X X X X
X X X X X X X X X X X X
_____X_X_X_X_X_X_X_X_X_X_X_X___X_X_X_X_X_X___X_X_X_X_________X________
1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10. 11. 12. 13. 14. 15. 16. 17
Mean = 21.67 X
Median = 21.2 X X
X X X
X X X X X X
X X X X X X X X X X
_______________X___X_X___X_X_X_X___X_X_X_X_X_X_X_X_X_X_X___X___X______
4 . 6 . 8 . 10. 12. 14. 16. 18. 20. 22. 24. 26. 28. 30. 32. 34. 36
X
Mean = 21.83 X
Median = 24.0 X
X X
X X X X X X
X X X X X X X X X
_____________X_X___X_____X_X_X_X___X_X_X_X_X_X_X_X_X_X_X_X_X_X_X__
0 . 2 . 4 . 6 . 8 . 10. 12. 14. 16. 18. 20. 22. 24. 26. 28. 30
X
Mean = 22.76 X X X X
Median = 24.9 X X X X X X X
X X X X X X X X X X X X
___________________________X_X_X_X_X_X___X_X_X_X_X_X_X_X_X_X_X_X__
0 . 2 . 4 . 6 . 8 . 10. 12. 14. 16. 18. 20. 22. 24. 26. 28. 30
Mean = 66.26
Median = 70.2
X
X X X X
X X X X X X X X X X X X X
_______X_X___X_X_X___X_X___X_X_X___X_X_X_X_X_X_X_X_X_X___X_X_X_X______
32. 36. 40. 44. 48. 52. 56. 60. 64. 68. 72. 76. 80. 84. 88. 92. 96
D + | - C + | - B + | - A +
a)
You find LOAD R3,R2,LOCALVAR in the Hawk code.
Rewrite this using only 16-bit instructions.
(1 point)
_______LIS_____R1,LOCALVAR__________________
_______ADD_____R1,R2________________________
_______LOADS___R3,R1________________________
____________________________________________
Only 1/20 got this right. 1/3 earned no credit. For some reason 1/4 left out the ADD instruction, converting a local variable reference indexed on R2 into a global variable reference. 1/7 used ADDSI to do the indexing, a solution that only works ifn LOCALVAR is less than 9. Since local variables are typically word-aligned this only works for offsets 4 and 8 in the activation record, a very limited range. Many subroutines require more than 2 local variables, so a small penalty was assessed for this solution.
The LOAD instruction has a 16-bit displacement for indexed addressing, while the solution given here using LOADS only has an 8-bit displacement. This is unlikely to be a problem, since an 8-bit displacement is good for activation records containing up to 64 words, and there are vanishingly few subroutines with that many local variables. If more local variables happen to be needed, ORIS instructions can be used to construct larger displacements.
b)
You find LIL R3,#123456 in the Hawk code.
Rewrite this using only 16-bit instructions.
(1 point)
_______LIS_____R3,#12_______________________
_______ORIS____R3,#34_______________________
_______ORIS____R3,#56_______________________
____________________________________________
1/5 did well here. 1/3 earned no credit. 1/3 made the mistake of dividing the constant into #123 and #456. These pieces require 9 and 11 bits, respectively, so cannot be loaded using the 8-bit immediate constants in the LIS and ORIS instructions. 1/5 used incorrect shift counts, for example, counting hex digits instead of bits. Other errors included use of AND to combine the pieces or forgetting to combine the pieces.
c)
(1 point)
You find JSR R1,PLACE in the Hawk code.
Rewrite this using only 16-bit instructions.
(1 point)
_______LIS_____R1,(PLACE>>8)&#FF____________
_______ORIS____R1,(PLACE___)&#FF____________
_______JSRS____R1,R1________________________
____________________________________________
1/14 got this. 1/3 earned no credit. 1/4 did not learn from part b) and tried to use LIS to load PLACE, something that is unlikely to work except for those programs that fit within the first 127 halfwords of memory. (The solution given here works for code that fits in the first 32K halfwords, something that is true of all the programs assigned for this course. Adding one additional ORIS would work for programs up to 8 megabytes, and adding two of them would make it work for any program.)
|
_3 _0 _F _0
|
1/20 got this right. 1/3 earned no credit. 1/6 gave a branch displacement of zero. The problem is, on the Hawk, the program counter is incremented as the instruction is fetched, so the displacement needs to be -4 in order to get back to the start of a 4-byte instruction. 1/8 omitted the second word (the branch displacement), and as many gave a third word.
SUBR: LIS R5,3
SUB R5,R5,R4
BTRUNC R5,2
SL R3,1
SL R3,1
SL R3,1
SR R4,2
LIS R5,3
SUB R5,R5,R4
BTRUNC R5,2
SL R3,4
SL R3,4
SL R3,4
JUMPS R1
|
1 got this right. 1/2 earned no credit. 1/5 recognized that R3 was being shifted left some amount. Many gave stunningly incomprehensible line by line commentary (squeezed into the blanks provided), and some guessed wild but not totally implausible things like exponentiation or multiplication. This was the hardest problem on the exam, being based on what is, in fact, very tricky code.
ROUTINE:
STORES R1,R2
TESTR R3
BZS LABEL ; _if_(p1!=0)_{_____________________
STORE R4,R2,OFFSET
ADDI R4,R3,-1 ; -- parameter _p1-1________________
LOAD R3,R2,OFFSET ; -- parameter _p2__________________
ADDI R2,R2,ARSIZE
JSRS R1,R1,ROUTINE ; call _p1=routine(p2,p1-1)_________
ADDI R2,R2,-ARSIZE
LOAD R4,R2,OFFSET
ADD R3,R3,R4 ; _p1=p1+p2_________________________
LOADS R1,R2
LABEL:
JUMPS R1 ; _}_return_p1______________________
a) Write appropriate high-level comments in the blanks above. (1.0 point)
Failure to mention the parameters to the recurisive call, failure to distinguish between values returned from the recursive call and parameters to this call, and failure to mention the return value were all causes to serious problems among more than half of the students.
The biggest high-level problems people had involved failure to abstract away from registers to things like local variable names, or focus on control structures at the expense of variables. Figuring out the code required doing both, and it is not siurprising, therefore, that many students failed to understand this bit of code.
b) What is the correct value for ARSIZE (0.5 point) __8__________
There is the return address and the very stupidly named local variable OFFSET.
1/2 did well here, 1/10 earned no credit.
c) What is the correct value for OFFSET (0.5 point) __4__________
1/2 did well here, 1/6 earned no credit.
d)
Suppose it is called with R3=3, R4=4, R5=5, etc.
How many calls are made before it returns (including the first).
(1.0 point)
__7_____________________________________________________________________
1/10 gave correct answers. 1/6 gave 6 (for a small penalty), 1/5 gave 5 (for half credit).
e)
What does it do? There is a concise short answer.
(1.0 point)
__integer_multiply_R3=R3*R4_____________________________________________
________________________________________________________________________
1/10 got this right. 1/2 earned no credit. 1/14 said multiplication but did not specify the operand or result registers, for a small penalty. Some partial credit went to those who said things like "repeated addition" or "something until zero." A little credit was given for wild speculation about such things as computing Fibonacci numbers or exponentiation.
; |_|_|_|_|_|_|_|_| s = mantissa sign
; |s| e | m | e = exponent, 111: not a number
; 100: represents zero
; 000: not normalized
; m = mantissa, 0.XXXX if exponent = 000
; 1.XXXX for other exponents
ITOFLT: MOVECC R4,R3 ; sign = n -- and also test n
BZS ITOFZ ; if (n != 0) {
BNR ITOFP1 ; if (n < 0) {
NEG R3,R3 ; n = -n
ITOFP1: ; }
LIS R5,EXP ; exp = EXP
CMP R3,MAX
BGT ITOFNAN ; if (n <= MAX) {
ITOFLP:
BITTST R3,BIT
BBS ITOFOK ; while ((mant & (1 << BIT) == 0) {
SL R3,1 ; n = n << 1
ADDSI R5,-1 ; exp = exp - 1
BR ITOFLP ; }
ITOFNAN: ; } else {
LIS R3,NAN ; n = NAN
ITOFOK: ; }
SL R5,BIT
OR R3,R5 ; n = (exp << BIT) | man
TESTR R4
BNR ITOFP2 ; if (sign < 0) {
LIL R4,2#10000000
OR R3,R4 ; n = n | 010000000
ITOFP2: ; }
ITOFZ: ; }
JUMPS R1 ; return
a) What is the correct value for the constant NAN? __01111111_____ (0.5 points)
1/4 got this, 1/2 earned no credit. Partial credit was given for a few that specified odd values in the mantissa field such as 01110011 or who specified negative values such as 11111111. (The answer 01110000 was acceptable with no penalty).
b) What is the correct value for the constant MAX? __7____________ (0.5 points)
1/8 got this. More than half earned no credit. A few earned partial credit for giving 8 (an off-by-one error).
The key to understanding this problem is to note that the absolute value of the integer has been taken at this point, but it is still an integer. Therefore, the correct answer is the maximum integer value that can be represented in this floating point format.
c) What is the correct value for the constant BIT? __4____________ (0.5 points)
1/4 got this while more than half earned no credit. 3, an off-by-one error, earned some credit.
d) What is the correct value for the constant EXP? __8____________ (0.5 points)
Onluy 1 got this right. Half earned no credit. Wrong answers earning partial credit included 7 (an off-by-one error), 4 (off by one in a different sense), and 6 (the maximum permitted exponent).
There is something tricky going on here! The correct answer is greater than the maximum permitted exponent because the maximum permitted value is such that there are guaranteed to be at least 2 shifts during the normalization process, decrementing this initial value by at least 2.
As it turns out, there is an error in the above code -- a TRUNC instruction was omitted righjt before the OR. This omission does not seem to have bothered anyone.
e)
Why not use an LIS instruction instead of the LIL instruction?
(0.5 points)
__LIS_R4,#10000000_would_load_-128_(a_negative_value)___________________
1/2 got this right. 1/4 earned no credit.
f)
Which registers are used for the parameter and result?
(0.5 points)
__R3_is_used_for_both___________________________________________________
1/2 got this right. Strangely, 1/6 said that R4 was also a parameter, perhaps because of the initial MOVECC instruction.
g)
Which registers are used for "local variables"?
(0.5 points)
__R4_and_R5_____________________________________________________________
1/3 got this right.
a)
What event sets the ready bit on an input device status register?
(0.5 points)
__New_input_is_available_in_the_input_data_register_____________________
1/7 got this. 1/2 earned no credit. Many students earned a slight penalty for saying "when the last action is complete." an answer that is so generic that it could as easily be an answer to part b).
b)
What event sets the ready bit on an output device status register?
(0.5 points)
__The_value_in_the_output_data_register_has_been_consumed_______________
Only 1/20 got this. 2/3 earned no credit. The remainder gave generic answers such as "when the last action is complete."
c)
What event resets the ready bit on an input device status register?
(0.5 points)
__Reading_the_input_data_register_______________________________________
1/5 got this right. 1/2 earned no credit. The vague answer "when the next action is started" earned a slight penalty, since it would apply equally to part d).
d)
What event resets the ready bit on an output device status register?
(0.5 points)
__Writing_new_data_in_the_putput_data_register__________________________
Only 1 got this right. 3/4 earned no credit. The remainder gave the generic "when the next action is started."
a) Write code to increment the saved program counter so it points to the next consecutive halfword. Use R3 and up as temporaries, if needed. (1 point)
_LOAD_ _R3,R2,svPC_
_ADDSI _R3,2_______
_STORE _R3,R2,svPC_
______ ____________
1/7 got this right. 1/4 earned no credit. The most common error earning partial credit involved adding 4 (a whole word) instead of 2 (a halfword). A common bit of nonsense among those who earned no credit was to try to get the instruction to which the saved program counter points, using EXTH. Nothing about this question suggests the need to do that.
All parts of this question were intimately related to MP6 and to HW11. Students who failed to pay adequate attention to those assignments were at a clear disadvantage here.
b) Given that R3 contains a register number i, write code to increment the saved value of register Ri. Use R4 and up as temporaries, if you need them. (1.5 points)
_LEA__ _R4,R2,svPC_
_ADDSL _R3,R4,2____
_LOADS _R4,R2______
_ADDSI _R4,1_______
_STORES _R4,R2______
Only 1/20 got this right. 1/3 earned no credit. 1/7 left off all of the address computation code. 1/5 invented addressing modes that the Hawk does not have, for example, using the symbol Ri as a register number or using two index registers in one instruction.
_MOVE_ _R5,R3______ R4 R3
[aaa|bbb|ccc|ddd][eee|fff|ggg|hhh]
_SRU__ _R5,12______ / / / / / /
[bbb|ccc|ddd|eee][fff|ggg|hhh| 0 ]
_SRU__ _R5,12______
_SL___ _R3,8_______
_ADDSL _R4,R5,8____
______ ____________
1/10 got this right (most with longer solutions). 1/3 earned no credit.
1/7 earned significant partial credit but failed to notice that the Hawk
cannot do a 24-bit shift with just one instruction.
1/7 earned some partial credit by shifting both
R3 and R4 left 8 bits without doing anything to
carry the high bits of R3 into R4.
In general, those students who
gave a diagram showing the flow of data as suggested above did much better.