Exam 3: Final

Solutions and Commentary

Part of the homework for 22C:60 (CS:2630), Fall 2011
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Grade Distributions

Final Exam

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 

Midterms plus Final

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

Machine Problems 1 - 6

                                                               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

Top 10 out of 11 Homework Assignments

                                                         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

Total Scores

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    + 

Solutions and Commentary

  1. Background: Consider a machine with a subset of the Hawk architecture where the only instructions were 16 bits each. The machine has LIS but not LIL, it has LOADS but not LOAD, and it has JUMPS but not JUMP. Your job here is to translate code that contains 32-bit Hawk instructions into substitute code that is limited to using only 16-bit instructions -- assume that R1 is available for use as a temporary register:

    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

      _F _F _F _C

      __ __ __ __

  2. A Problem: Show the machine code for L: JUMP L in the blanks to the right as a sequence of 16-bit halfwords in hex. (1 point)

    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
    

  3. A Problem: You inherited the code shown to the right from a programmer who was careless about writing any comments. What does it do? A correct answer will give an overall explanation of what this this code does, and not a line-by-line commentary. (2 points)

    __subroutine_to_shift_R3__________________

    __left_the_number_of_bits_________________

    __given_in_R4_bits_0_to_3_________________

    __________________________________________

    __________________________________________

    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.

  4. A Problem: Consider this uncommented 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.

  5. Background: Consider this subroutine to convert integers to floating point numbers in a familiar 8-bit floating point format:
            ;  |_|_|_|_|_|_|_|_| 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.

  6. Some Question:

    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."

  7. Background: Consider the code for an trap handler. Inside the trap handler, R2 points to the register save area, and the identifier svPC is the displacement into the register save area of the saved program counter. The program counter is also R0, so svR1 is the same as svPC+4 and svR2 is the same as svPC+8, etc. The identifier svPSW is the displacement into the register save area of the saved PSW.

    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.

  8. A problem: Suppose R3 and R4 contain a 64 bit quantity (the least significant 32 bits in R3. Write code to shift the double word 8 places left (this multiplies it by 256). It can be done in 5 instructions. Think about which bits of which original register get put in which bits of the result. (2 points)
                    _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.