Exam 3: Final

Solutions and Commentary

Part of the homework for 22C:60, Fall 2007
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Grade Distributions

Exam 3

Median = 8.8
Mean   = 9.27                                 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

Exams 1 to 3

Median = 24.2
Mean   = 23.00                  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

Homeworks, top 10 out of 12

Median = 24.6                                           X
Mean   = 22.59                                    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

Machine Problems 1 to 5

Median = 16.0
Mean   = 17.17                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

Total Scores

Median = 62.2
Mean   = 62.76

     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_____
  28. 32. 36. 40. 44. 48. 52. 56. 60. 64. 68. 72. 76. 80. 84. 88. 92. 96
   + + +|- - - C C C C + + +|- - - B B B B + + +|- - - A A A A + + +
     x x   x         x               x                   o o o o   o

In the bottom line above,
-- x marks scores of some who did not submit MP4 and MP5
-- o marks scores of some with partially correct MP5 solutions
Also note that these distributions only include students who took all three exams.

Exam and Solutions

Background: Consider the problem of going to the label THERE on the Hawk.
a) Consider using HERE: BR THERE. What is the necessary relationship between HERE and THERE? The answer can be expressed as an inequality: (1 point)

__ -129 < (THERE - (HERE+2))/2 < 128 ____

Nobody did perfectly, but 1/3 gave answers that were just short of perfect, missing only the +2 to account for the fact that the PC is incremented before adding the branch displacement. Another 1/3 earned no credit.

b) Consider using HERE: JUMP THERE. What is the necessary relationship between HERE and THERE? (1 point)

__ -32769 < (THERE - (HERE+4)) < 32768 __

Again, nobody had perfect scores, but 1/3 gave answers that were just short of perfect, missing the +4 that accounts for the fact that PC is incremented after the instruction fetch and displacement fetch. Similarly, 1/3 earned no credit.

c) Consider using HERE: LIL R1,THERE, followed by JUMPS R1. What are the constraints on THERE in this case? (1 point)

__ ~-8,000,000 < THERE < ~8,000,000 _____

1 had a perfect score, while about 1/2 earned half credit for answers that said 24 bits or similar relevant things.

d) Consider using HERE: LIW R1,THERE, followed by JUMPS R1. What are the constraints on THERE in this case? (1 point)

__ THERE must be an absolute constant ___

3 did perfectly, the remainder earned no credit, apparently assuming that there were no limits on this solution.

e) There are some values of THERE for which none of the above solutions will work. Give a universal solution that always works: (1 point)

__________ LOAD R1,PTHERE _______________

__________ JUMPS R1 ______________________

__ PTHERE: W THERE ___________________

____________________________________________

Most earned no credit here, either copying the given code from parts c) or d), or leaving it blank. 1/6 earned partial credit, giving solutions that typically missed the final line in the above.
A Problem: This code was released into the public domain by an unscrupulous company that did everything they could to to make their C++ code unreadable. What does it do? (1 point)
```
                x = ((x << 2) + x) << 1;
                x = ((x << 2) + x) << 1;
```
____ x = x * 100 ___________________________

1/2 did well, 3 earned partial credit, and the remainder earned no credit.
A Problem: Consider this comment-free code to traverse a tree and do something at every node:
```
        TRAVERSE:
                STORES  R1,R2
                STORE   R3,R2,NODE
                LOADCC  R3,R3,LEFT
		BZS	TRAVNOL
                ADDSI   R2,R2,ARSIZE
                JSR     R1,TRAVERSE
                ADDSI   R2,R2,-ARSIZE
        TRAVNOL:
                LOAD    R3,R2,NODE
                LOAD    R1,R3,DOIT
                ADDSI   R2,R2,ARSIZE
                JSRS    R1,R1
                ADDSI   R2,R2,-ARSIZE
                LOAD    R3,R2,NODE
                LOADCC  R3,R3,RIGHT
		BZS	TRAVNOR
                ADDSI   R2,R2,ARSIZE
                JSR     R1,TRAVERSE
                ADDSI   R2,R2,-ARSIZE
        TRAVNOR:
                LOADS   R1,R2
                JUMPS   R1
```
a) Give appropriate declarations for the activation record of TRAVERSE. (1 point)

__ ;RETAD = 0 _______________________

__ NODE = 4 _______________________

__ ARSIZE = 8 _______________________

____________________________________________

1/2 did well, 1/4 earned no credit. Typical problems here involved confusion between the fields of an activation record and the fields of a tree node.

b) For each parameter to TRAVERSE, how is it passed, what is it, and what preconditions must it meet before the call? (1 point)

__ R3 is a non null pointer to a node ______

____________________________________________

____________________________________________

1/4 did well here. Just under 1/2 earned no credit. The most common error was failing to note that the parameter must not be null. Several of the answers that earned no credit included longwinded explanations of the algorithm that typically failed to convey much understanding.

c) TRAVERSE uses several fields in each node of the binary tree it visits. Identify these fields and describe their contents. (1 point)

__ LEFT points to the left child node ______

__ RIGHT points to the right child node ____

__ DOIT points to the code of a method _____

____________________________________________

1/4 did well, 1/5 earned no credit. Half credit was available to those who named the fields but did not explain them (1/6) and those who gave the left and right fields but not the DOIT field (1/6). Poor explanations of the nature of the DOIT field were common (1/4).
A Problem: Under what circumstances could a virtual machine operating system running on the Hawk change the definition of the CPUGET and CPUSET instructions? (1 point)

__ LEVEL = 1111 (unprivileged) _____________

1/8 did well, over 1/2 earned no credit. Half credit was available to anyone who vaguely mentioned either the level field of the PSW or the issue of privileged instructions.
Background: Consider the following code from the Hawk monitor:
```
        KBGETC:
                LIW     R4,KBDBASE+KBDSTAT
        KBPOLL:
                LOADSCC R3,R4
                BZS     KBPOLL
                LIW     R4,KBDBASE+KBDDATA
                LOADS   R3,R4
                JUMPS   R1	
```
a) Which instructions in the code above require the cache to be turned off? (1 point)

__ the LOAD instructions ___________________

Over 1/2 did well here. 1/4 earned no credit, the remainder mentioned one or the other of the two load instructions, but not both.

b) How would the code fail if the cache was not turned off for the appropriate instructions? (1 point)

__ the polling loop would not terminate ____

____________________________________________

____________________________________________

Over 1/2 did well here, 1/4 earned no credit.

c) Is there a specific range of physical memory addresses that should never be cached? If so, give the range of addresses. (1 point)

__ #FF000000 to #FFFFFFFF __________________

1/4 did well, 1/4 earned half credit by giving much narrower ranges of addresses, for example, excluding only the keyboard interface registers from the cache -- while leaving all other device registers cached. 1/3 earned no credit.
Background: The following double-shift-left macro can be used instead of the DSL virtual machine implementation from MP5, but it works very differently.
```
                MACRO   DSL r,c
                  MOVE    R1,r
                  SRU     R1,15         ; (alternatively SRU R1,16)
                  SRU     R1,17-c       ; (alternatively SRU R1,16-c)
                  SL      r,c
                  ADDSL   r+1,R1,c
                ENDMAC
```
a) This macro does not require or enforce one constraint required by MP5. Which one? (1 point)

__ the constraint that r be even ___________

Just under 1/2 did well, while just over 1/2 earned no credit.

b) The parenthesized alternative may be clearer, but it sometimes fails. When? (1 point)

__ it fails when c = 16 ____________________

Just under 1/2 did well, 1/2 earned no credit, and a few earned half credit for identifying the problem case as c = 0.

c) Substituting the above macro into a program that worked correctly under MP5 sometimes causes unexpected errors on nearby branch instructions. Why? (1 point)

__ it is 5 halfwords long, not 1 ___________

1/4 did well here, just under 1/2 earned no credit. 1/5 earned half credit for noticing that the condition codes will not be set by this code the same way as they are by a trap service routine; this is right, but it doesn't explain the symptom for "nearby" branches, as opposed to immediately following conditional branches.
A Problem: Give a single line of SMAL code for the Hawk equivalent to W #01234567 but using a single B directive. (1 point)

__ B #67,#45,#23,#01 _______________________

1/2 did well, 1/3 earned no credit. Partial credit was available to those who flipped the byte order properly but used just a single 32-bit operand on the B directive or who broke the operand into 4 bytes without addressing the byte order.
Background: Suppose that the symbols svPC, svR1, svR2, svR3 and so on up to svR15 are defined as displacements to consecutive words of the register save area of an interrupt or trap service routine. Assume that the trap service routine has saved the correspoonding registers in these words, that R3 points to the register save area, and that R4 and up are available. Do not assume that svPC is the first word of the register save area.
a) Give SMAL Hawk code to load R4 with the instruction halfword pointed to by the saved PC. (1 point)

__ LOAD R5,R3,svPC ______________________

__ LOADS R4,R5 ___________________________

__ EXTH R4,R4,R5 ________________________

____________________________________________

____________________________________________

2/3 did well here, 1/8 earned no credit. 1/3 earned partial credit for missing EXTH instruction. Some entirely wrong answers involved extensive use of CPUSET or similar special instructions, apparently mislead by the trap-handler context from understanding that this is a mundane data structure and array indexing problem.

b) Given that R4 holds an instruction halfword fetched from memory, give code to extract the destination field from that instruction and put it in R5. (1 point)

__ LIS R5,#F ___________________________

__ AND R5,R4 ___________________________

____________________________________________

____________________________________________

____________________________________________

2/3 did well here, 1/4 earned no credit. Partial credit was available to those who made mistakes with byte order or forgot to truncate the result to 4 bits. Among wrong answers, several gave complex and inscrutible code.

c) Given that R5 holds the destination field of an instruction, give code to get the value of the saved destination register and put it in R6. (1 point)

__ LEA R6,R3,SVPC ______________________

__ ADDSL R5,R6,2 _________________________

__ LOADS R6,R5 ___________________________

____________________________________________

____________________________________________

1/5 did well. Just under 1/2 earned no credit. 1/5 forgot the admonition from the instructions that svPC is not at displacement zero. These students omitted the LEA instruction.