Exam 3: Final

Solutions and Commentary

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

Grade Distributions

Final Exam

                          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

Sum of All Exams

Mean   = 21.81                                          X
Median = 23.3                       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. 32. 34

Sum of All Machine Problems

Mean   = 21.14
Median = 21.4                                                   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

Sum of the Top 10 out of 12 Homework Scores

Mean   = 21.84
Median = 22.3
                                          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 the Above Scores

Mean   = 62.39                            X
Median = 61.4                             X
                                          X
___X________________X_______X_X_____X_X___X_X_____X_X___X_____X_X___X_____X___
  8 . 12 ... 32. 36. 40. 44. 48. 52. 56. 60. 64. 68. 72. 76. 80. 84. 88. 92.
Rough Grades    D     + +|- -    C    + +|- -    B    + +|- -    A    + +

Exam Solutions

Background: The Hawk has 16 and 32-bit instructions. Under some circumstances, it might be the case that 32-bit instructions are undesirable. In that case, you could have to rewrite your programs to use only short instructions.

a) Write a sequence of short Hawk instructions that is equivalent to LIL R3,1500. (2 points)

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

b) What is the worst case number of short instructions required to load an arbitrary 32-bit constant into a register on the Hawk? (1 point)

________________________________________________________

c) Write a sequence of short Hawk instructions that is equivalent to L: LEA R3,L. The new version will, of course, take more than one instruction; it should load R3 with the address of the first instruciton in the sequence. If you need a temporary register, use R1. (2 points)

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

Background: Hawk conditional branches can only take displacements within a range of 256 halfwords. Suppose your program contained BGT L and when you assembled it, you got an error message saying that L was too far away. Provide an equivalent sequence of instructions that goes to L under the right circumstances, assuming L is under 32K bytes away. (2 points)
```
     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________
```

Background: A common problem in building a computer system is the design of a priority interrupt hardware. Consider a Hawk computer with 3 external devices, each of which may request interrupts (perhaps a keyboard, a modem and a disk).

inputs outputs
I₁ I₂ I₃ I_out E₁ E₀

Each device has an interrupt request line, I₁, I₂, and I₃. The priority encoder has 3 outputs, I_out, which is one if any of the inputs are 1, and <E₁, E₀>, a 2-bit code indicating which interrupt request should be acknowledged. E is unspecified if no interrupt is being requested. If just interrupt request I_i is true, E = i. In cases where multiple interrupt requests are true, E will be set to the lowest of the pending interrupts, so for example, if I₁ is true, then E = 1 regardless of the others.

a) Complete the truth table for this circuit in the table to the right (2 points)

Gate-level schematic

b) Give the logic diagram for I_out as a function of I₁, I₂ and I₃ in the space below. (1 points)

c) Complete this logic diagram for E₁ and E₀ as a function of I₁, I₂ and I₃ by adding appropriate dots to the figure at the right.

Note: Only seven and gates are provided because the output is unspecified for the input combination 000. This omission helped to fit the figure on the page! (2 points)

Background According to Chapter 12 of the notes, to raise an exception on the Hawk, R2 must be loaded with the handler's activation record pointer, and then the program counter must be set to the handler's entry. These were loaded from a two-word global structured as follows:

EXHAND  =       0       ; one word, the address of the handler
EXAR    =       4       ; one word, the handler's activation record
EXSIZE  =       8       ; the total size of an exception record

Consider the following alternative model. The global variable is just one word, a pointer to the exception description record (still defined as above), perhaps declared as:

        COMMON  PCONSTRAINT_ERROR, 4  ; pointer to the exception record
PPCONER:W       PCONSTRAINT_ERROR     ; pointer to the pointer!

a) Write code to raise constraint error using this new model. This code will only resemble the code given for the general case in Chapter 12. (2 points)

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

b) Consider a subroutine that installs an exception handler using this new data structure. What fields must be included in the activation record of this subroutine? For each field, briefly describe its use! (1 point)

________________________________________________________

________________________________________________________

________________________________________________________

Background: Recall that the high 4 bits of the processor status word are the level field, and that the CPUGET R,PSW and CPUSET R,PSW instructions can be used to get and set the PSW. Also, recall that when the level field is 1xxx₂, the memory management unit is enabled; entry to the trap service routine always sets the level field to 0000₂, and other bits in the level field enable various input-output device interrupts.
a) What value should the level field have inside the memory management unit trap service routine if that trap service routine requires the completion of input-output data transfers that are accomplished using interrupts? (1 point)
```
________________________________________________________
```
b) Write code, suitable for inclusion in the MMU trap-service routine right after all the registers have been saved, to set the level field to the value you have suggested in part a). (2 points)
```
     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________
```
Background: Consider the 8-bit floating point number representation for storing sound samples using the 8-bit floating point format discussed in class:
```
|___|___|___|___|___|___|___|___|
|___|___________|_______________|
  S      EXP           MANT
```
S -- the sign of the signed-magnitude mantissa
EXP -- the exponent, a 3-bit biased integer
MANT -- the mantissa, a 4-bit fixed point fraction

There are no hidden bits and the bias is the natural bias on 3-bits. The maximum positive value in this system is 15/16 x 2³ = 7.5 while the smallest nonzero value is 1/16 x 2^-4 = 1/256. A fixed-point number system representing this range of values would take at least 12 bits per sample (including sign), with 8 bits of fraction.
The fastest way to convert from these 8-bit floating point values to the equivalent fixed point values is to use a table lookup. Assume that the table is called CONVERT and that it is in ROM with the program:
```
CONVERT: H #0000 ; +0.00 in hex
         H #0001 ; +0.01
         ...     ; the table goes on for 256 entries
```
The Problem: Given a floating point number, in this format, in R3, convert it to the corresponding fixed point binary value, leaving the result in R3. Don't forget to sign-extend the result to 32 bits! (2 points)
```
     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________

     ____________  ____________  ;  _________________________________________
```