Exam 2: Midterm

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 II

                        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

Total Exams I and II

                    X
Mean   = 14.18      X
                    X   X   X       X
                    X X X   X       X
 ___________X_X_X___X_X_X_X_X___X_X_X______________
   9 . 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20

Machine Problems 1 to 3

mean   = 12.50              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

Homeworks 1 to 10

mean  = 18.80                       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   = 45.47                                        X
                                    X     X   X       X
__X_________X_______X_____X___X_X___X_X_X_X___X_____X_X_____X___X___X_____X_
 . 26. 28. 30. 32. 34. 36. 38. 40. 42. 44. 46. 48. 50. 52. 54. 56. 58. 60.
     D         |         C         |         B         |         A         |

Solutions and Commentary

    mystery circuit
  1. Consider the mystery circuit to the left. It is some kind of flipflop. Don't try to work out its behavior in detail! It's complicated! Instead, focus on issues of symmetry and complexity to try to answer the following: (0.4 points each)

    a) Is it edge triggered (master-slave)? _____Yes________

    By inspection, the diagram contains at least 3 simple RS flipflops, so it is fair to guess that it must be something like a master-slave flipflop.

    About 3/4 of the class guessed this.

    b) Which output is the Q output? ________c___________

    This requires guessing how data gets into the flipflop. The input a seems to have equal influence over the outputs c and d, so it is a decent candidate for a clock input but not for a data input. In contrast, the b input is very assymetric, being an input to just one of the two RS flipflops on the input side of this beast. Therefore, it is fair to guess that it is a data input of some kind.

    Tracing through nand gates from the b input following various paths through the circuit, there are always an odd number of inversions on paths to the d output and an even number of inversions on paths to the c output. Therefore, we can tentatively conclude that the c output is most likely to be Q.

    Half the class got this.

    c) Which input is the clock input ________a___________

    See the comments above.

    Half the class got this.

    d) What clock change changes the output __leading edge______

    There are only 4 possibilities: A latch could be either positive pulse triggered or negative pulse triggered, and a master-slave flipflop could be either positive edge triggered or negative edge triggered. Once you guess that the flipflop is a master-slave device, this reduces the options to one or the other form of edge triggering. To go farther requires looking at its behavior.

    If the a input is low, the two inputs to the slave flipflop are forced high, so the slave (the rightmost RS) flipflop is remembering the value while the a input is high. In this state, the b input can flow through the bottom nand gate (in inverted form) to the inputs of the gates at the top and second to from the bottom. In contrast, when a is high, one or the other of the left RS flipflops must be remembering. Collectively, they must act like a master stage. Therefore, the low to high transition of a must be the transition that can change the output.

    Only 1 in 7 got this right. Given that 3/4 of the class guessed that this was a master-slave device, about 1 in 3 ought to have guessed correctly by a random guess. This was a hard problem!

    e) What kind of flipflop is it _edge triggeered D__

    This is just the assembly of all of the above reasoning. In fact, this is the most common design for a edge-triggered D flipflop used commercially.

    Half the class got this.

  2. Consider this horrible little binary floating point representation:
      _ _____ _______  s - 1 bit, the sign of the signed-magnitude mantissa
     |_|_____|_______| exp - 3 bits, the exponent, biased so 100 = 0
     |s| exp |  man  | man - 4 bits, the mantissa, with no hidden bit
    

    The normalization rules are as usual, but some of the following values are not necessarily normalized. What is the value of each of the following, both in algebraic and fixed point decimal form? (0.4 points each)

    a) 00000001 = __0.625___ x 2_-4_ = _0.00390625____

    b) 11111111 = _-.9375___ x 2__3_ = _-7.5__________

    c) 01010101 = _0.3125___ x 2__1_ = _0.625_________

    d) 10101010 = _-.625____ x 2_-2_ = _-0.15625______

    e) 11001000 = _-.5______ x 2__0_ = _-0.5__________

    1 in 3 did perfectly here. Parts c) and e) were somewhat easier than the others. The most common problems involved a failure to present a reasonable decimal approximation of the value, and the strange interpretaition of the mantissa as a binary number in the form 0.000.

  3. Here is a code fragment from the file mp4demo.a distributed as part of the assignment for MP4. Initially, R8 points to the screen object (call it S), R3 holds the screen height, R4 holds the screen width.
            MOVE    R5,R4
            SR      R5,1      ; p1 = width/2
            MOVE    R4,R3
            SR      R4,1      ; p2 = height/2
            MOVE    R3,R8
    A:      LOADS   R1,R3     ; ?a?
    B:      LOAD    R1,R1,AT  ; ?b?
            JSRS    R1,R1     ; screen.putat(p1, p2) 
    

    a) What does line A do? (1 point) _make R1 point to the method table of the object S______

    1 in 4 got this. 1 in 2 said "get the address of the screen object", but the object S is pointed to by R8, so we already have its address.

    b) What does line B do? (1 point) _make R1 point to the AT (or putat) method of S_________

    1 in 2 got this. 1 in 4 missed the word "pointer" and said that this puts the method in R1, for partial credit.

    c) What is missing that you would need to add if this code was part of a subroutine? (1 point)

    _it needs to push and pop the activation record__________________

    1 in 3 got this. A few more mentioned the activation record for partial credit. 1 in 4 mentioned the need to do something with the return address, apparently missing the fact that this is a code fragment out of context. Whatever the subroutine containing this fragment does with its return address, it is fair to guess that it happens outside this fragment, so it is not missing from this fragment.

     

  4. Fill in the missing values and comments in the following code. Your answers should make the code workable and should explain what it does and how it does it. Your comments should be in the form of high-level language or pseudocode equivalent to the assembly language. (3 points)
    X       =       __4____ the partial product
    
    ARSIZE  =       __8____
    IN:     ; on entry
            ;       R3 = _a__multiplicand___
    
            ;       R4 = _b__multiplier (a >= 1)
            ; on exit
            ;       R3 = _the product a x b_
            STORES  R1,R2
            CMPI    R4,1
            BLEU    OUT        ; if ( _b > 1____ ) {
    
            STORE   R0,R2,X    ;     _x = 0____________________
    
            SR      R4,1       ;     _b = b >> 1_______________
    
            BCR     ON         ;     if ( _b was odd___ ) {
    
            STORE   R3,R2,X    ;         _x = a____________________
    ON:                        ;     }
            SL      R3,1       ;     _a = a << 1_______________
            ADDI    R2,ARSIZE
            JSR     R1,IN      ;     _product = in(a,b)________
            ADDI    R2,-ARSIZE
            LOAD    R4,R2,X 
            ADD     R3,R3,R4   ;     _product = product + x____
    OUT:                       ; }
            LOADS   R1,R2
            JUMPS   R1         ; return _product__________
    

    Stop and think: This problem is designed to take 10 minutes and use of scratch paper is recommended before messing up your exam paper. Be prepared to erase and erase again before getting it right. Note: We have studied the above algorithm in class!

    Few did perfectly here. Common errors included: Forgetting about the return address in the activation record -- giving ARSIZE=4, failing to understand the shift operations, and failing to identify the underlying algorithm as a recursive multiplication algorithm. Many students just said "recursive call" for the JSR instruction. It is important to understand that there are parameters passed to this call and a result returned. Without this, it is hard to figure out what the routine does.