Exam 1: MidtermSolutions and Commentary
Part of
the homework for CS:2630, Spring 2015
|
X
X
X X
Mean = 7.13 X X X
Median = 7.5 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_X_X_X_X_X_X______
0 . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10
X
X
Mean = 14.97 X
Median = 16.1 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_X___X_X_X___X_X_X_X_X_X_
2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10. 11. 12. 13. 14. 15. 16. 17. 18
X
etc
Mean = 9.46 etc
Median = 10.0 X
X
X X
X X X
X X X X X
___X___________________X_____X___X_X_____X_X__
0 . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10
X
X
X
Mean = 31.40 X
Median = 32.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_X_________X_X_X_X_X_X_X_X_X_X_X_X_X____
6 . 8 . 10. 12. 14. 16. 18. 20. 22. 24. 26. 28. 30. 32. 34. 36. 38
A very tentative grade scale: F | D | C | B | A
There were two versions of this question:
Bit Pattern x 011000 010110 110111 000101 101111 Unsigned decimal ___24___ ___22___ ___55___ ___5____ ___47___ 1's complement of x _100111_ _101001_ _001000_ _111010_ _010000_ (binary) 2's complement of x _101000_ _101010_ _001001_ _111011_ _010001_ x as a 1's comp num ___24___ ___22___ ___-8___ ____5___ __-16___ (signed decimal) x as a 2's comp num ___24___ ___22___ ___-9___ ____5___ __-17___
Bit Pattern x 001100 001011 100010 011011 110111 Unsigned decimal ___12___ ___11___ ___34___ ___27___ ___55___ 1's complement of x _110011_ _110100_ _011101_ _100100_ _001000_ (binary) 2's complement of x _110100_ _110101_ _011110_ _100101_ _001001_ x as a 1's comp num ___12___ ___11___ __-29___ ___27___ ___-8___ (signed decimal) x as a 2's comp num ___12___ ___11___ __-30___ ___27___ ___-9___
Regardless of the version of the exam, only scattered people had any difficulty with the first three rows of the table. In contrast, all of the conversions to signed decimal caused problems for from for about 1/7 of the class. Typical problems included giving negative answers where the number was positive, giving positive answers when the number was negative, and giving answers off by one.
There were two versions of this question:
. = 0 || Address 3 2 1 0
A: H #2345 || |----|----|----|----|
B #01 || 000000: | | 01 | 23 | 45 |
B: ; solved to here || |----|----|----|----|
ALIGN 4 || 000004: | 00 | 42 | 00 | 0A |
H #A,"B" || |----|----|----|----|
ALIGN 2 || 000008: | 00 | 00 | AB | CD |
W #ABCD || |----|----|----|----|
C: B D,C,B,A || 00000C: | 00 | 03 | 0C | 10 |
ALIGN 4 || |----|----|----|----|
D: H #C,D || 000010: | 00 | 10 | 00 | 0C |
END || |----|----|----|----|
. = 0 || Address 3 2 1 0
D: H #2345 || |----|----|----|----|
B #01 || 000000: | | 01 | 23 | 45 |
C: ; solved to here || |----|----|----|----|
ALIGN 4 || 000004: | 00 | 42 | 00 | 0A |
H #A,"B" || |----|----|----|----|
ALIGN 2 || 000008: | 00 | 00 | AB | CD |
W #ABCD || |----|----|----|----|
B: B D,C,B,A || 00000C: | 10 | 0C | 03 | 00 |
ALIGN 4 || |----|----|----|----|
A: H #C,D || 000010: | 00 | 00 | 00 | 0C |
END || |----|----|----|----|
Regardless of the version of the exam, the biggest problems fell into the following categories
Byte or Halfword order — 1/10 of the class made consistent errors about this. Worse, a few used inconsistent orders, reversing some fields but not others.
W #ABCD — 1/7 of the class assumed that, despite the W directive, this should assemble as a halfword, evidently because only 4 hex digits were given.
Label values – Almost everyone had trouble with the second label (B in the first solution above, C in the second). The problem was the ALIGN directive immediately after the label; the assembler is not smart enough to look ahead to this directive and have it change the value of the label, but most students assumed it would do so, giving the label the value 4.
Labels confused – Almost 1/3 of the class made significant errors in the value of one or more labels other than the one discussed above.
Labels confused with ASCII – A significant but small number of students confused the label A with the ASCII character "A". It is hard to fathom how an experienced programmer can confuse an identifier with a quoted string.Only one student had a perfect score on this problem, but most students did reasonably well.
There were two versions of this question that differed in the registers used. Here is one of them:
SMAL Hawk code || Scratch space || Addr: 0 1
|| ||
F: MOVE R6,R3 || || 1000: _F6_ _F3_
LIS R3,0 || ||
LIS R4,1 || || 1002: ____ ____
A: ADDSI R6,-1 || ||
BLT B || || 1004: ____ ____
ADD R5,R3,R4|| ||
MOVE R3,R4 || || 1006: ____ ____
MOVE R4,R5 || ||
BR A || || 1008: ____ ____
B: JUMPS R1 || ||
|| || ...
Here are assembly listings for both versions; note that the order of the bytes of the object code in the assembly listings is exactly to the order requested by the blanks in the problem statement shown above.
+00000000: F6 F3 3 F: MOVE R6,R3 +00000002: D3 00 4 LIS R3,0 +00000004: D4 01 5 LIS R4,1 +00000006: 16 CF 6 A: ADDSI R6,-1 +00000008: 05 04 7 BLT B +0000000A: 35 34 8 ADD R5,R3,R4 +0000000C: F3 F4 9 MOVE R3,R4 +0000000E: F4 F5 10 MOVE R4,R5 +00000010: 00 FA 11 BR A +00000012: F0 B1 12 B: JUMPS R1
+00000000: F4 F3 3 F: MOVE R4,R3 +00000002: D3 00 4 LIS R3,0 +00000004: D5 01 5 LIS R5,1 +00000006: 14 CF 6 B: ADDSI R4,-1 +00000008: 05 04 7 BLT A +0000000A: 36 35 8 ADD R6,R3,R5 +0000000C: F3 F5 9 MOVE R3,R5 +0000000E: F5 F6 10 MOVE R5,R6 +00000010: 00 FA 11 BR B +00000012: F0 B1 12 A: JUMPS R1
1/6 of the class did perfectly here while 1/10 of the class earned no credit at all. Among those earning partial credit, by far the most difficult problem involved PC-relative branch instructions. Forward branches were slightly easier than backward branches, and off-by-one errors were common, but many students had wild answers verging on random. 1/10 of the class switched the order of all of the bytes, and an additional 1/10 did worse, switching the order of some bytes but not others.
b) It is a function. If F is called with the integer 3 in R3, what value is returned? (0.5 points)
___2_____________________________________________________
The sequence is 0 1 1 2 3 5 8, etc., the Fibonacci series, where zero is the zeroth element.
Over 1/3 of the class got this, and close to 1/2 of the class gave off-by-one answers, mostly 1 but also 3.
There were two versions of this question that differed only in the order and labeling of the two versions of the code. Only one version of the question is given here:
; ----- VERSION 1 -----
LEA R8,R3,CHILDREN ; c = *p->children
TRAVLP:
LOADSCC R3,R8
BZS TRAVQT ; while (*c != NULL) { -- note: *c is in R3
JSR R1,TRAVERS ; travers( *c )
ADDSI R8,4 ; c++
BR TRAVLP
TRAVQT: ; }
; ----- VERSION 2 -----
LEA R8,R3,CHILDREN ; c = *p->children
LOADSCC R3,R8
BZS TRAVQT ; if (*c != NULL) { -- note: *c is in R3
TRAVLP: ; do {
JSR R1,TRAVERS ; travers( *c )
ADDSI R8,4 ; c++
LOADSCC R3,R8
BZR TRAVLP ; } while (*c != NULL)
TRAVQT: ; }
a) Which version is faster? (0.4 points)
__Version 2 is faster____________________________________
Over 1/2 of the class got this right.
b) Briefly explain why (but merely saying "one is shorter" is not sufficient). (0.6 points)
__The loop body of version 2 has one less instruction____
__(an unconditional branch has been eliminated)__________
1/10 got this right, while another 1/10 embedded right answers in larger statements containing significant errors. Among those with wrong answers for part a), 1/10 of the class earned a bit of credit here for giving clear static analysis supporting their wrong answer by the assertion that Version 1 contains one less instruciton.
1/3 of the class made a serious error, asserting that Version 2 did redundant computations. In fact, both versions execute exactly the same number of LOADSCC instructions for any particular tree node, and exactly the same number of conditional branch instructions test the condition codes.
c) What register must be saved before either block of code and restored after in order to conform to our standard Hawk calling sequence? (0.5 points)
__R8 must be saved and restored__________________________
1/5 got this right. Some credit was given for the 1/5 who focused on R1, since it is usually saved and restored during subroutine calls, but the conventional boilerplate calling sequences save it by default, while R8 is not included in our boilerplate methodology.
Almost 1/2 of the class focused on R3. In fact, in a preorder traversal, there would be no need to save and restore R3 in the above code, but token credit was given for this answer. No credit was given for those who asserted that R2 needed to be saved and restored. None of the calling sequences we have studied operate by saving and restoring R2.
d) What other optimization was done that moved key code out of the loop to places before and after this? (0.5 points)
__Pushing and popping the activation record______________
1/6 of the class got this right. Token credit was given for those who said something about moving the address of the children out of the loop, since a pure array addressing approach to the problem would have included subscript calculation inside the loop instead of simply advancing a pointer by 4. 1/2 of the class gave answers that repeated things that had already been discussed in parts a) and b).