Exam 2: Midterm

Comments and Solutions

Part of the homework for 22C:60, Fall 2008
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_X_X_X_X_X_X_X___X_X_________
   0 . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10

Exam II Solutions

mystery circuit

Consider the mystery circuit to the left. It is some kind of flipflop.
a) Complete the following timing diagram for this circuit: (1.0 point)
```
	|          _________           _________           ____________
     a  |_________|         |_________|         |_________|
	|    _____________               _____________              ___
     b  |___|             |_____________|             |____________|
	| __       _____________________________                    ___
     c  |?__|_____|          a-------a          |__________________|
	| ________________ ___________________________
     d  |?________________|                           |________________
	|_______________________________________________________________
                                 >>> time >>>
```
3 did well, 4 left the entire diagram blank, 5 gave nonsense answers. The area marked with a--a above created significant problems for those with partial credit.
It is noteworthy that this flipflop is based directly on Problem 2 from Homework 11. The biggest difference is a simple matter of redrawing the flipflops in the master and slave stages.

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

point a is the D input
point b is the C input
point d is the Q output
Many students felt compelled to label point c. It is the Q output of the master stage, but it was not asked for in the question!

c) The output of this flipflop changes when the clock input ___Negative________________
(0.5 points)

This question was graded in terms of the timing diagram, so there were significant demerits of part a) line d did not agree with part c).
1 / 127773₁₀ = 0.0000 0000 0000 0000 0100 0001 1010 0111 0₂
This question asks about efficient algorithms for dividing R3 by 127773.
a) How many partial products we we need to add to compute this quotient by reciprocal multiplication? __7______ (0.5 points)

6 students correctly counted the number of one bits in the reciprocal. 6 more were off by one.

b) How many shift operations are required? __7______ (0.5 points)

6 students understood this. 7 more were off by one.
This problem was based on Homework 9 problem 1 and on Machine problem 5.

c) Which way should the result be shifted after each add? __right__ (0.5 points)

10 got this.

d) What Hawk instruction combines these add and shift operations? __ADDSR__ (0.5 points)

12 got this (graded in the context of the answer given to part c)

Consider this historic binary floating point representation used by the Modcomp IV computer:

00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

S exponent mantissa

The exponent has the natural bias (256) and the mantissa is a pure fraction, with the point between bits 9 and 10 and no hidden bit.

Give the binary floating-point representations of the positive integers from 1 to 4, inclusive. (0.3 points each)

a) 0,1 0 0 0 0 0 0 0 1,1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

b) 0,1 0 0 0 0 0 0 1 0,1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

c) 0,1 0 0 0 0 0 0 1 0,1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

d) 0,1 0 0 0 0 0 0 1 1,1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

10 to 14 students got each of the above right. Among those earning partial credit, the most common error involved the most significant bit of the exponent -- 8 set this bit to zero, but it must be one in the biased number system.

The Modcomp floating point representation, discussed in the previous problem, used an eccentric approach to negating numbers. To negate a floating point number, use the 2's complement integer negate operation. First, give the representation of -1 on this machine: (0.3 points)
a) 1,0 1 1 1 1 1 1 1 0,1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Only 3 got this right. It was always graded in the context of the answer given to problem 3a).

b) If two numbers in this format are compared using an integer compare instruction, is the result valid? (0.5 points) __yes________

On the whole, most people guessed no, but the answers looked fairly random. In fact, about the only redeeming characteristic of this representation is clever in that it allows fast integer comparison of floating point operands.
Here is a code fragment from the solution to MP4, mp4.a distributed on line.
```
1        ADDI    R2,R2,ARSIZE
2        JSR     R1,ODDH         ;   oddh( x - offset, y, o - 1, neww, h );
3        ADDI    R2,R2,-ARSIZE
4
5        LOAD    R3,R2,X
6        LOAD    R4,R2,Y
7        LOAD    R5,R2,O
8        LOAD    R6,R2,NEWW
9        LOAD    R7,R2,H
10       LOAD    R1,R2,OFFSET
11
12       ADD     R3,R3,R1        ;   -- fix x parameter
13       ADDSI   R5,-1           ;   -- fix o parameter
14       ADDI    R2,R2,ARSIZE
15       JSR     R1,ODDH         ;   oddh( x + offset, y, o - 1, neww, h );
16       ADDI    R2,R2,-ARSIZE
```
a) Where are the variables referenced on lines 5 to 10 stored? (1 point)
____in the activation record____________________________

7 got this right. 7 more got half credit for answering "on the stack".

b) To eliminate lines 3 and 14, what change do we need to make on lines 5 to 10? (1 point)
____Append -ARSIZE to each of these lines_______________

7 got this while 3 got half credit for subtracting ARSIZE from the register number instead of from the stack displacement.

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

Lots of things are missing: The receiving sequence, the return sequence, the declarations of the identifiers giving offsets into the activation record, the code to initialize the values of the variables in the activation record, and of course, the code to display part of the H tree.
2 students got full credit, listing two or more of these. Partial credit waws offered for any one of these, and partial partial credit for parts of one of these (for example, storing the return address as suggested by 16 students, which is part of the receiving sequence).

Here is a parallel-port-put routine from a solution to Homework 11, Your job is to briefly complete the comments in the blanks to the right that make it clear that you understand what this code does. (2 points)

PPPUT:  ; on entry
        ;       R3 = ch -- the byte to put out
        LIL     R4,PPDATA          ; get address of data register
PPPBU:                             ; do {
        LOADS   R5,R4
        BITTST  R5,PPBSYBIT
        BCS     PPPBU              ; } while ( __parallel port busy_________ )
        TRUNC   R3,8
        SL      R3,PPDATBIT
        LIL     R6,1 << PPSTRBIT
        OR      R6,R3              ; R6 = ___new output data and strobe bit___
        LIL     R7,#FF << PPDATBIT
        NOT     R7
        AND     R5,R7              ; R5 = ___ppdata with old data cleared_____
        OR      R5,R6
        STORES  R5,R4              ; ppdata = __R5 or R6______________________
PPPNB:                             ; do {
        LOADS   R5,R4 
        BITTST  R5,PPBSYBIT
        BCR     PPPNB              ; } while ( __parallel port not busy_____ )
        LIL     R7,(#FF << PPDATBIT) + (1 << PPSTRBBIT)
        NOT     R7
        AND     R5,R7              ; R5 = __ppdata with clear data and strobe_
        OR      R5,R6
        STORES  R5,R4              ; ppdata = __R5 or R6______________________
        JUMPS   R1                 ; return

Stop and think: This problem is designed to take 10 minutes.

2 gave really good answers. 10 left the entire problem blank. In general, the polling loop comments were fairly easy, while the hardest problem many faced was with the logical operations and or and not -- many wrote comments that simply missed noticing these.
The second major problem area was in level of abstraction. Comments that stay at the machine level are extraordinarily uninformative and don't suggest any useful understanding of the code.