Exam 3: Final

Solutions and Commentary

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

Grade Distributions

Final Exam

mean   = 6.84
median = 6.6            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. 11. 12. 13. 14

Total of Exams 1 to 3

mean   = 18.72              X       X            
median = 18.7               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 . 4 . 6 . 8 . 10. 12. 14. 16. 18. 20. 22. 24. 26. 28. 30. 32

Total of Machine Problems 1 to 6

mean   = 21.01                            X
median = 21.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_
   0 . 2 . 4 . 6 . 8 . 10. 12. 14. 16. 18. 20. 22. 24. 26. 28. 30

Total of Top 10 Scores from Homeworks 1 to 12

mean   = 21.53                                      X
median = 22.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_______
   0 . 2 . 4 . 6 . 8 . 10. 12. 14. 16. 18. 20. 22. 24. 26. 28. 30

Total of Exam, Machine Problem and Top 10 Homework Scores

mean   = 61.27
median = 63.4                   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________
       28. 32. 36. 40. 44. 48. 52. 56. 60. 64. 68. 72. 76. 80. 84
Grade Scale  |-    D    +|-    C    +|-    B    +|-    A    +|

Exam Soltuions and Commentary

  1. Background: The code fragment to the right is taken from the body of the trap handler at the heart of the solution to MP6. On entry, this assumes that R3 points to the trap save area (see section 9.3 of the Hawk manual):

            LOAD    R4,R3,svPC
            LOADS   R5,R4
            EXTH    R5,R5,R4
            MOVE    R6,R5
            SR	R6,8
    A:      TRUNC	R6,4
            MOVE    R7,R5
    B:      TRUNC   R7,4
            LIL     R1,#F0F0
    C:      AND     R5,R1
    
            LEA     R1,R3,svPC
            ADDSL   R7,R1,2
    D:      LOADS   R7,R7
    
    a) Describe what Line A puts in R6. (0.5 points)

    __the SRC field of instruction that trapped__
    

    About 14 got this right, 4 more said DST for partial credit.

    b) Describe what Line B puts in R7. (0.5 points)

    __the DST field of instruction that trapped__
    

    About 15 got this right, 4 more said DST for partial credit.

    c) Describe what Line C puts in R5. (0.5 points)

    __the opcode of the instruction______________
    

    About 15 got this right. Among those with problems, a significant number seemed unable to grapple with the masking of the SRC and DST fields.

    d) Describe what Line D puts in R7. (1 point)

    __the contents of the saved DST register_____
    

    4 got this right, 5 got partial credit for saying something involving the destination register such as a pointer to it.

  2. Background: Consider the Hawk keyboard input driver given to the right:

    KBDGET:
            LIW     R3,KEYBOARD
    KBDPOLL:
            LOAD    R4,R3,KBDSTAT
            BITTST  R4,KBDRDY
            BCR     KBDPOLL
            LOAD    R3,R3,KBDDATA
            JUMPS   R1
    
    a) Why use LIW instead of LIL to load R3? (0.5 points)

    __The constant KEYBOARD is more than 24 bits_
    

    15 got this.

    b) What are KBDSTAT and KBDDATA? (0.5 points)

    __Displacements into the keyboard interface__
    

    10 got this. 14 got partial credit for addresses of keyboard interface registers.

    c) Which instructions in this code require that the cache be turned off? (0.5 points)

    __Both LOAD instructions_____________________
    

    12 got this.

    d) What would happen if the cache was left on during these? (1 point)

    __The KBDPOLL loop would never exit__________
    

    14 gave good answers.

  3. Background: Consider the mystery code to the right. Each step in this code takes a value in R3 as input and produces a result in R3, using R4 and R5 as scratch registers in the process.

            MACRO   STEP,mask,count
            LIW     R4,mask
            LIW     R5,(mask << count)
            AND     R4,R3
            AND     R5,R3
            SRU     R5,count
            ADD     R3,R4,R5
            ENDMAC
    
            STEP    #55555555,1
            STEP    #33333333,2
            STEP    #0F0F0F0F,4
            STEP    #00FF00FF,8
            STEP    #0000FFFF,16
    
    a) How many halfwords does this code occupy? (1 point)

    __50__(5 uses of STEP at 10 halfwords each)__
    

    This was difficult. 12 earned no credit at all. Many miscounted the 3 halfwords in the LIW macro (giving either 4 or 2 for partial credit). Many gave answers for STEP (for partial credit) forgetting that the 5 calls to step are the ones that actually assemble code into memory.

    b) The final step in this code can be optimized by replacing one LIW and one AND instruction by a MOVE followed by a TRUNC. Give the full TRUNC instruction below. (1 point)

    __MOVE R4,R3/TRUNC R4,16_____________________
    

    This was difficult, 8 earned no credit at all. The most common error was to give COUNT as the bitcount -- but if the final STEP is optimized, it won't be a macro, it will be written out separately, and COUNT, at that time, should be replaced by 16. On the other side, at least one student noticed that TRUNC R3,16/ADD R3,R3,R5 was an even better optimization.

    c) What does the final step do (this is the easiest step to understand)? (1 point)

    __Sum the high and low halfwords of R3_______________________________
    
    _____________________________________________________________________
    

    1 got this right. 11 gave explanations of the final instruction in STEP instead of the final call to STEP. 4 gave elaborate long textual descriptions of the algorithm that included no hint that they understood what the algorithm did.

    d) What does the entire 5-step sequence do? (1.5 points)

    __It counts the one bits in R3_______________________________________
    
    _____________________________________________________________________
    

    Nobody got this, but one gave a garbled description hinting at potential understanding and 1 more at least understood the sequence of masks involving runs of 1, 2, 4, 8 and 16 bits.

    mystery circuit

  4. Background: Consider the mystery circuit to the left. It is some kind of flipflop, but it is up to you to figure out how it works.
     

    a) Complete the following timing diagram for this circuit: (2.0 point)

            |    _____________               _____________              ___
         a  |___|             |_____________|             |____________|
            |          _________           _________           _________
         b  |_________|         |_________|         |_________|         |__
            | __ _______________.         ._______________    .____________
         c  |?__|     .         |_________|         .     |___|         .
            | __ _____.         .         .         ._____    .         .__
         d  |?__|     |_____________________________|     |_____________|
            | __ _______________.         .         ._____    .         .__
         e  |?__|     .         |___________________|     |_____________|
            | __ _______________.         .         ._____    .         .__
         f  |?__|     .         |___________________|     |_____________|
            | __ _____.___________________.         .         .         .
         g  |?__ _____|         .         |________________________________
            |_______________________________________________________________
                                     >>> time >>>
    

    17 got line c, 14 got line d, 8 got line e, 7 got line f and 3 got line g. The R-S flipflops that make up this flipflop were covered as an example in class, including a timing diagram on the blackboard.

    b) Label the points a, b and g in the above circuit diagram with the appropriate conventional labels for these inputs and outputs to a flipflop (eg, things like Q, Q, etc). (1 point)

    a is D, b is C and g is Q.

    9 got this. Partial credit was given for getting some of the inputs right, and credit was subtracted for wrong answers involving wrong labels. The most popular wrong answer involved exchanging C and D, probably inspired by the inverter on the C input and the fact that, for more symmetrical flipflops, D gets inverted. It is the and-or assymetry of this flipflop that forces C to be inverted and eliminates the need to invert D.

    c) What change in the clock input allows the output of this flipflop to change? (1 point)

    __it is a leading-edge triggered flipflop____________________________
    
    _____________________________________________________________________
    

    1 got this right. Answers that drew conclusions that were inconsistent with the output given on line g of the timing diagram were considered incorrect. The most common wrong answer was to conclude that it was a trailing-edge triggered flipflop, probably because the flipflop on exam 2 was trailing-edge triggered.

  5. Background: A display list contains a null-terminated list of items. Each item contains a pointer to the next item in the display list a pointer to the parameterless display_me() method for that item, and additional data that depends on the item's class.

    a) Give appropriate SMAL code to declare the structure of a generic item record. You might need to read ahead to parts b) and c) before rushing to answer this. (1 point)

    __; structure of one generic item in the display list________________
    
    __NEXT    =        0       ; pointer to the next item________________
    
    __DISPLAY_ME =     4       ; pointer to the display-me method________
    
    __ADDITIONAL_DATA = 8      ; start of subclass-specific information__
    
    _____________________________________________________________________
    
    _____________________________________________________________________
    

    2 did well here. At least 8 included a return-address and over 10 used ARSIZE (the activation record size) to indicate the record size, There were significant penalties for these and other irrelevant fields, as well as significant penalties allocating other than a word for each pointer.

    b) Give appropriate SMAL code to call the display_me() method for the item pointed to by R3. It is parameterless, but you should assume that the caller has local variables on the stack. (1 point)

    __________LOAD    R1,R3,DISPLAY_ME___________________________________
    
    __________ADDI    R2,R2,ARSIZE_______________________________________
    
    __________JSRS    R1,R1______________________________________________
    
    __________ADDI    R2,R2,-ARSIZE______________________________________
    
    _____________________________________________________________________
    
    _____________________________________________________________________
    

    Nobody did perfectly. Over 11 had difficulty loading the address of the display_me() method, many who got this wrong either assumed that it was a statically known method (contrary to explicit wording in the problem statement) or assumed some kind of complex linkage through a class descriptor (again, contrary to explicit wording in the problem statement). Looking in the lecture notes for cookbook code never substitutes for reading the problem statement carefully! The other very popular error was to omit code to push and pop the activation record, despite the explicit final clause in the question.

    c) Given that R3 points to the first item in the a display list, write code to count the elements in the display list, returning that count in R4. (1.5 points)

    __________LIS     R4,0_______________________________________________
    
    __LP:________________________________________________________________
    
    __________TESTR   R3_________________________________________________
    
    __________BZS     QT_________________________________________________
    
    __________LOAD    R3,R3,NEXT_________________________________________
    
    __________ADDSI   R4,1_______________________________________________
    
    __________BR      LP_________________________________________________
    
    __QT:________________________________________________________________
    

    1 gave a good answer. This was intended as a simple little programming problem un related to part b and almost disconnected from part a. A good answer could be written based only on the background statement. At least 8 students had otherwise correct code that did not handle empty lists properly. At least 4 students had difficulty with loading the next pointer. As many as 9 students earned no credit for madly irrelevant code involving such things as procedure calls.

  6. Background: Your new glyptometer outputs a digital data stream where each byte encodes one measurement of the glyptographic coefficient. According to the manual, the data format is seeemmmm, where s is the sign bit, eee are three bits of exponent, biased so that the value 000 represents -4, and mmmm are the mantissa bits, a pure binary fraction, so that 1000 represents one half. (0.5 points each)

    a) Give the decimal equivalent of the smallest positive normalized value.

    __0 000 1000 = 1/32 = .03125_____________

    At least 5 got this right, 9 more gave 1/16 for partial credit. Minimal partial credit was given for merely giving the correct binary representation.

    b) Give the decimal equivalent of the smallest positive non-normalized value.

    __0 000 0001 = 1/256 = .00390625_________

    At least 2 got this right, while at least 16 got it entirely wrong.

    c) Give decimal equivalent of the most extreme negative value.

    __1 111 1111 = 15/16 * 8 = 15/2 = 7.5____

    At least 6 got this right, while t least 14 got it entirely wrong

    d) Give the binary representation of -1.0

    __1 101 1000 = -1/2 * 2__________________

    At least 12 got this right, single bit errors earned some partial credit.

    e) Given a number in this format in R3, write Hawk code to negate that number. R1 is available as a scratch register. (1.0 point)

    __________LIL     R1,#80_____________________________________________
    
    __________XOR     R3,R1______________________________________________
    
    _____________________________________________________________________
    
    _____________________________________________________________________
    
    _____________________________________________________________________
    

    Only 1 got this right, while at least 14 earned no credit. This was intended as a simple programming problem. The problem is to flip just one bit in R3 while leaving all other bits unchanged. A common wrong answer, worth partial credit, was to use ADDI R3,#80. This flips the sign bit of the 8-bit glyptographic coefficient, but it also propagates carries into higher bits. Following this with TRUNC would fix that, but nobody did. Another common approach that invariably led nowhere was to do an if-then-else control structure, first testing the sign and then trying to set it correctly. None of the students who tried this managed to set the sign bits correctly on the two branches of the if-then-else.