Final Exam Solutions and Commentary

Part of materials for 22C:40, Fall 2003
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Grade Distributions

Total Scores

Mean   = 64.29
Median = 64.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_X_X_______X_X_X________
 30. . . . 40. . . . 50. . . . 60. . . . 70. . . . 80. . . . 90. . . . 100
 F F        D D D D        C C C C        B B B B        A A A A

Total Exam Scores

Mean   = 22.96
Median = 23.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_X___X_X_X_X_X_X_X_X_X_X_____X_X_X____
 5 . . . . 10. . . . 15. . . . 20. . . . 25. . . . 30. . . . 35. . . .

Final Exam Scores

Median = 9.1    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_____
 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10. 11. 12. 13. 14. 15. 16. 17. 18. 19

Mean = 22.96

Exam Solutions

An old game in computer architecture is to try to construct the world's simplest instruction set. The solutions are all machines with just one instruction, so they have zero bits of opcode; attempts to write programs for these machines are awful, but they are excellent examples to use on examp questions. Here is the fetch execute cycle of one such machine:
```
	for (;;) { /* an infinite loop */
	   /* fetch */      /* an instruction is two words */
	   addr = M[pc];    /* first an operand address */
	   dst = M[pc+1];   /* then a destination address */
	   pc = pc + 2;
	   /* execute */    /* subtract and branch if negative */
	   ac = M[addr] - ac;
	   M[addr] = ac;
	   if (ac < 0) pc = dst;
	}
```
Memory for this machine is word addressable, and the processor has only two registers, a one word accumulator and a program counter. We can use the SMAL assembler to assemble code for this machine using only W directives, and we can write a macro for the one instruction, subtract and branch if negative, as follows:
```
	MACRO SBN =addr,=dst
	   W addr
	   W dst
	ENDMAC
```
a) (1 point) Flesh out the following macro that will set both the accumulator and the contents of a memory location to zero:
```
	MACRO ZERO =addr
	   SBN __ addr,.+2 ______________________
	   SBN __ addr,.-. ______________________
	ENDMAC
```
In the above, I have used the notation .-. to indicate a value that is never used.
One student had a good answer, and two more had reasonable ideas that involved the right idea but inccrrect expressions for the control structure. Many had reasonable ideas for the first operands (the address fields) but had real problems with the control structure (the dst fields). About half the class gave nonsense answers that indicated no understanding of the problem.

b) (1 point) Flesh out the following macro that will load the accumulator with the contents of a memory location (here, we assume that TMP is the address of a location that holds a temporary variable, the value of which never matters):
```
	MACRO LOAD =addr
	   ZERO TMP
	   SBN __ addr,.+2 ______________________
	ENDMAC
```
One student had a good answer, and two more had reasonable ideas that involved the right idea but inccrrect expressions for the control structure. 16 clearly did not understand the control structure, and half the class did not express any understanding of the problem.

c) (1 point) Flesh out the following macro that will get a value from memory location src, negate it, and store the result in both dst and the accumulator.
```
	MACRO NEG =src,=dst 
	   ZERO dst
	   SBN __ src,.+2 _______________________
	   SBN __ dst,.+2 _______________________
	ENDMAC
```
Two students had a good answers here, and two more had reasonable ideas. Again, half of the class showed no understanding of the problem.
The C and Java languages allow shifts of the form i<<j, where i and j are both variables. The Hawk shift instructions, on the other hand, require that the shift count be a constant. Consider the problem of shifting R3 left R4 places, where both R3 and R4 hold variables and R4 is guaranteed to non-negative and less than 32. There are three solutions:
a) (3 points) use a loop, shifting R3 one place left per iteration while decrementing R4. Write Hawk code to do this:
```
       __ LOOP: ADDSI  R4,-1 _____________________________________
       ________ BNS    LEXIT _____________________________________
       ________ SL     R3,1  _____________________________________
       ________ BR     LOOP  _____________________________________
       __ LEXIT: _________________________________________________
```
The above is only one of many possible solutions to this problem.
Five had good solutions; The most common error was to write a post-test loop that would produce the wrong answer for a shift count of zero; 15 had this error, for a 1/3 penalty. Inefficient code was given a small penalty. Everyone got some credit here.

b) (2 points) use a BTRUNC instruction to jump into an array of 31 one-bit shift instructions. The setup code for this is the most interesting part, so write it (you may need to use R1 as a temporary register):
```
       _______  LIS     R5,31  ___________________________________
       _______  SUB     R4,R5,R4  ________________________________
		BTRUNC	R4,5
		SL	R3,1	; branch here to shift 31 places
		SL	R3,1	; branch here to shift 30 places
		...
		SL	R3,1    ; branch here to shift 2 places
		SL	R3,1    ; branch here to shift 1 place
```
Again, there were several other solutions, only one being shown.
Four solved this well, while several had partial solutions, typically involving inefficiencies (for example, LIW or LIL instead of LIS). Half the class gave answers that suggested that they did not understand the BTRUNC instruction, and an additional quarter of the class left this blank.

c) (2 points) test successive bits of R2 in series, skipping shift instructions if each bit is zero: Write the missing Hawk code to do this:
```
       		BITTST	R4,0
		BCR	TRY1
       _______  SL      R3,1  ____________________________________
       TRY1:	BITTST	R4,1
		BCR	TRY2
       _______  SL      R3,2  ____________________________________
       TRY2:	BITTST	R4,2
		BCR	TRY3
       _______  SL      R3,4  ____________________________________
       TRY3:	BITTST	R4,3
		BCR	TRY4
       _______  SL      R3,8  ____________________________________
       TRY4:	BITTST	R4,4
		BCR	DONE
       _______  SL      R3,16  ____________________________________
       DONE:
```
Close to half the class did well here, and a quarter of the class got partial credit for solutions that shifted the right register by the wrong shift count (Typically, replacing the sequence of shift counts, 1248, with the sequence 1234 or even 1111). About one in 8 students showed no understanding here.

d) (1 point) for each of the above, how many instructions are executed in the best case and the worst case?

a) ___ 2 ____ _126-154__

b) __ 3-4 ___ _ 34-35 __

c) ___ 10 ___ ___ 15 ___

15 gave good answers here. Most did surprisingly well considering the problems students had with the details of the code.
Suppose for some reason (such as an arbitrary restriction imposed for the sake of an exam question) you had to rewrite a Hawk program to eliminate any use of 32-bit instructions. This means, instead of using indexed addressing, you'd be stuck using short-indexed addressing.
a) (2 points) in the original program, you found LOAD R3,R2,LOCAL1. Rewrite this under the rules outlined above.
```
       __  LIS    R3,LOCAL1  _____________________________________
       __  ADD    R3,R2,R3  ______________________________________
       __  LOADS  R3,R3  _________________________________________
```
There are many possible correct solutions.
3 gave good answers here. 12 earned no credit. Common errors involved such things as using LEA or ADDI to compute the address, when these instructions have the same 32-bit format as the original LOAD instruction. Partial credit was given for instructions with the wrong number of operands where the intent was clear, such as a two-operand ADD or a 3 operand ADDSI.

b) (1 point) What constraint does your code above place on the value of the symbol LOCAL1? Would this be likely to cause any problems?
```
       __  For the solution given above, -129 < LOCAL1 < 128 _____
       __  Since R2 is the AR pointer, and most activation records _____
       __  are small, this constraint is unlikely to pose any problem. _
```
1 in 4 did well here; half the class got no credit, and the remainder typically identified the constraint correctly but failed to address the question of whether that constraint was likely to pose problems.

c) (1 point) in the original program, you found LIL R3,#56789A. Rewrite this under the rules outlined above (there are several good ways to do this).
```
       __  LIS  R3,#56  __________________________________________
       __  ORIS R3,#78  __________________________________________
       __  ORIS R3,#9A  __________________________________________
```
1 in 4 did well here; 1 in 3 earned no credit. Between these extreams, common errors involved such problems as imagining that the LIS and ORIS instrucitons can be used with 12-bit immediate constants.
Consider this floating point format:
```
     _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
    |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
    |s|   exponent    |                  mantissa                   |
```
Here, s is the sign of the mantissa (a signed magnitude fraction), and the exponent is stored as biased 8 bit number in the range -128 to +127 (using a bias of 128). The point of the mantissa is between the sign and the magnitude, and the mantissa is normalized to have its most significant bit equal to 1 (no hidden bits).
a) (1 point) Give, in binary, the maximum positive value in this number system and the minimum nonzero positive value.
```
       __  0111 1111 1111 1111 1111 1111 1111 1111  ______________
       __  0000 0000 0100 0000 0000 0000 0000 0000  ______________
```
6 did well here; common errors included failure to bias the exponent and failure to normalize the mantissa. 1 in 6 had real difficulty.

b) (2 points) Given a number in this format in R3, get the exponent, as a two's complement binary integer, into R4.
```
       __  MOVSL  R4,R3,1  _______________________________________
       __  SRU    R4,12    _______________________________________
       __  SRU    R4,12    _______________________________________
       __  ADDI   R4,-128  _______________________________________
```
There are, of course, many solutions to this problem. Some students had really ingenious ideas (using EXTB, for example).
3 had good solutions. By far, the most common error was to attempt a shift of more than 16 places in one instruciton (the shift count field is only 4 bits). One in 3 did poorly here.
Suppose we had a programmable real-time clock as a Hawk peripheral. This has a single count register that is decremented by one, by the hardware, every microsecond, and when it reaches zero, the ready bit RD is set in the clock status register. Ignoring interrupts, here is the interface:
```
               _ _ _ _._ _ _ _._ _ _ _._ _ _ _
    FF100020  |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|  clock count register
                              ._ _ _ _._ _ _ _
    FF100024                  |_|_|_|_|_|_|_|_|  clock data register
                               IE            RD
```
a) (1 point) What is the maximum time this timer can measure, in seconds, without the help of auxiliary software.
```
       __  65535 µs = 65.535 ms = 0.065535 s  ____________________
```
1 in 4 did well here, 2 in 5 had worthless answers. Common problems worth partial credit included being off by a factor of 1000 or by a factor of two. The number of students who did not know the meaning of the standard metric-system prefixes milli and micro is alarming.

b) (1 points) Explain how to use this timer to delay the execution of the application program for one millisecond. Don't write code, just explain.
```
       __ To wait, first load a count of 1000 (one millisecond) __

       __ in the count register, then poll the RD bit until it ___

       __ is set.  _______________________________________________
```
1 in 4 did well here, 2 in 5 had real trouble. Common errors leading to partial credit included extra (and unneeded) operators such as substituting a for loop for simple polling loop, and use of an inappropriate count.

a)	`___ 2 ____`	`_126-154__`

b)	`__ 3-4 ___`	`_ 34-35 __`

c)	`___ 10 ___`	`___ 15 ___`