Midterm Solutions

22C:122, Fall 1999

Douglas W. Jones

Grade Distribution

Mean    8.6
Median  9.5

 ______X_______X_X_______X_________X_X_____X_X_____________X____
  . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10. 11. 12. 13. 14. 15. 16. 
 - - C C C C C C + + - - B B B B B B + + - - A A A A A A + +
This grade scale should not be taken too seriously. The grade distribution for the total score in the course is more useful for an indication of performance as of mid-semester:
Mean   34.9
Median 34.5
                          X
 ___X_______X_____________X_________X_____X_______________X_X___________X_
 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43.
  - - - C C C C C C + + + - - - B B B B B B + + + - - - A A A A A A + + +

Solutions and Commentary

  1. A Question: Any computer system can be described at 3 levels of abstraction, known by the abbreviations RT, ISP and PMS. Give a one sentence definition of each.
    The register transfer (RT) level describes a digital system in terms of the registers making up the system, the data paths linking the registers, and the finite state control unit that evokes transfers of data from one register to another along these data paths.

    The instruction set processor (ISP) level describes a computer system in terms of the instruction set of the machine and the instruction execution algorithm executed by the processor.

    The processor memory switch (PMS) level describes a computer system in terms of the interconnection of top-level components such as processors, memory units and switching systems or busses.

    6 did well, 2 had weak definitions, and 1 had a very weak definition.

  2. Part A: In detail, what signals, and traveling in what direction, would you expect on the interface between ALU and indexing unit for this design.
    If the indexing unit holds private copies of the ALU registers, whenever the ALU stores a value in a register, it must inform the indexing unit of that fact. Therefore, we need the following:
    • 16 lines to hold the value being stored in the register
    • 4 lines to indicate what register is being updated
    • 1 line to indicate when the register is being updated (strobe)
    All these go from the ALU to the indexing unit.

    2 had good answers. 4 forgot the clock line. 2 had no useful answer.

    Part B: As part A suggested, there is another design alternative for the data path between the ALU and the indexing unit. Describe this alternative. Design details are not required!

    If the indexing unit has no private copy of the ALU registers, it must ask the ALU for the value of a register each time it needs it. Thus, the indexing unit must be able to present a register number to the ALU, and the ALU must be able to give the indexing unit the value of that register. Unlike the first alternative, information flows both ways in this interconnection scheme.

    2 did well her; some others gave eccentric but possibly functional alternatives.

    Part C: Give an RT-level diagram of the logic required to implement the indexing unit.

    What follows is one design. It is also possible to put a 2-input mux after the adder, and the design given below can be modified to replace the multiplexor with some clever circuitry to directly force the constants 0000 and F000.
                       12 lsbs                         ___
    	Address |==/==============================|   |
    	in ===/=|          __________        |\   |   | 16
                 16 |         |          |  0000=|01  | + |=/= 
                    |  4 msbs | register |16     |  | |   |   
                    |--/-o----|  values  |=/=====|00|=|___|
                         |    |          |       |  |
                         |    |__________|  F000=|10
                         |    _____              |/|
                         o---|=1111|---------     ||
                         |   |_____|         |    ||
                         |    _____           ---- |
                          ---|=0000|---------------
                             |_____| 
    
    2 did well here; most of the problems students had here involved ignoring, frequently in an extreme way, the PMS-level diagram that was given on the exam. As a result, many of the proposed indexing units were entirely unable to support any kind of indexed addressing!

    Part D: On power-up, the PC register is zero and all RAM and other registers hold random or unknown bit patterns. Give (using reasonable notation) code you would put in ROM to jump to the first location in RAM after the code in ROM finishes loading a program in RAM.

    The following assembly code, assumed to reside in ROM, will jump to an arbitrary address A in RAM:
    	     MOVE CA,R5
    	     MOVE CX5,PC
    	CA:  WORD A
    	CX5: WORD #5000
    
    The above assembly code is intended to be equivalent to the following code. Here, it is assumed that we're assembling the code into 010016, but any consecutive addresses in ROM will do so long as the address constants in the code are relocated to match:
    	0100: 0104  \ move the contents of location 104 to R5
    	0101: FF05  /
    	0102: 0105  \ move the contents of location 105 to PC
    	0103: FFFF  /
    	0104:  A    - the destination address
    	0105: 5000  - if this is put in the PC, R5 will do indexing
    
    2 gave good answers for a machine with no indexing unit, 5 gave incomprehensible or non answers. Several used assembly notations that bore little resemblance to anything appropriate for this machine. Most, apparently, didn't understand something that should have been obvious from the PMS diagram at the top of the page. All addresses issued by the CPU pass through the indexing unit on their way to RAM or the ALU.

    Part E: Suggest a modification to the indexing unit that would allow programs to contain 12-bit immediate constants in source operands.

    The obvious modification is to pick some 4-bit register number, for example, 1110, and use this as a prefix on a 12 bit constant.

    2 gave this answer. Several managed to assume that, because 50% of all source operands are constants, 1 bit should be used to distinguish between constants and other operands. In an ideal world, perhaps, but if the constant is specified as 12 bits, 1 + 12 is 13, leaving 3 unused bits in a 16 bit word. This is foolish. Most answers were very vague.

    Part F: Would the extension to allow source operands containing 12-bit immediate constants solve the awkward structure of branch instructions on the Ultimate RISC with this indexing unit added? Explain briefly why or why not.

    No! The reason is, aside from addresses in ROM (the first 4K addresses), all interesting addresses require more than 12 bits.

    1 person gave a good answer, 2 more gave an unsubstantiated no, while the remainder received no credit.