Midterm Exam

Part of material for 22C:122/55:132, Spring 2004
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Note: This is an open-book, open-notes exam. Please write your answers in the exam booklet supplied. Leave blank lines between your answers to different questions, and leave a margin down the side of each page. Please write your name in the form it appears on your university ID card; write your name in the blank provided on the front cover. This exam is worth 20 points! Allocate about 2.5 minutes per point.

Background

The instruciton set of the example 16-bit computer can be compactly summarized as follows:
   Register 0 is the program counter!

  15___ _______ _______ ___________0
   |_._|_._._._|_._._._|_._._|_._|_|
   |op |r1     |r2     |op'  |sk |st

    0 0  operate      result = ALU( R[r1], R[R2], op' )
                      if SKIP(result, sk) then PC = PC + 1
                      if st then R[r1] = result

    ALU operations include a+b, a-b, b-a, a&b, a|b, and a^b
    SKIP tests are: no skip (00), <0 (01), =0 (10), and >0; (11)
		
  15___ _______ _______ ___________0
   |_._|_._._._|_._._._|_._._._._._|
   |op |r1     |r2     |dd         |
               |ea = R[r2]+dd      |

    0 1  load         R[r1] = M[ea]
    1 0  store        M[ea] = R[r1]
    1 1  load address R[r1] = ea

Questions

  1. Given that a single-port edge-triggered register file is used to implement the CPU, what is the minimum number of clock cycles required to execute an operate instruction that both skips and saves its result? Start your count from the moment the instruction is in the instruction register ready for execution. Document your answer by showing, for each clock cycle, the operations done on the register file, making reasonable assumptions about auxiliary registers and data paths that may be required. (You ought to be able to do this with one or two lines of documentation per cycle!) (4 Points)

  2. The register transfer logic for my implementation of the example architecture has the following outputs to the control unit:
    op
    the 2-bit opcode from IR15-14

    skip
    a one-bit input formed as a function of the sign of the ALU output, whether the alu output is zero, and the sk field, IR2-1

    a) Give the truth table for the skip tests, as a function of IR2, IR1, ALU<0 and ALU=0 (in that order). (2 Points)

    b) Given that no microinstruction needs to test both the op and skip outputs from the register-transfer logic, propose a sensible way to allow the microcode to control wich condition is tested and to allow unconditional execution where no condition needs testing. (2 Points)

    c) The st bit, IR0, is not listed here because it can be anded with the register-clock line inside the data half of the system. Similarly, the ALU function select lines can be handled this way, being derived directly from IR5-3. The problem is, we also need to use the ALU for indexed addressing. Therefore the microinstruction has a 1-bit field indicating whether the ALU should add or use IR5-3 as its operation. Draw a register-transfer level logic diagram that explains how this output from the control unit is used to make this selection. (2 Points)

  3. The indexed addressing facilities of this machine could be implemented using either unsigned arithmetic, so index displacements run from 0 to 63, or using signed displacements, so index displacements run from -32 to +31. Given that we can't do both, you must select one or the other. Explain your reasoning in making this selection, with reference to each of the following issues: Data structure sizes, PC-relative addressing, the need for efficient ways to load small constants, and the need for fast addressing of global variables. Your answer should take the form of a brief essay. (4 points)

  4. Give that A is an arbitrary fixed 16-bit memory address.

    a) How would you encode a jump to the code at this address? It's easy to give the answer to this question in binary! (2 points)

    b) How would you load this address into a register? This question is a bit harder because it's harder to find a good place to put A in order to load it; as a result, your answer will involve more English and less binary! (2 points)

    c) Compare the efficiency of the instruction encodings you explored in parts a and b with the efficiency of the instruction encodings for these same operations on the PDP-11. What you remember from doing assignment 6 ought to suffice as background for this problem. (Space and time efficiency are reasonable grounds for comparison.) (2 points)