Exam 1 Solutions and Comments

22C:122/55:132, Spring 2001

Grade Distribution

Average = 6.7
Median  = 7.2
                          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
 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10. 11. 12. 13. 14. 15. 16. 17. 18. 19 .20
                       |- original expected range -|

CS students only:

X                         X                 X
X_X_____X___X_X_____X___X_X_X_X_X___X_X_____X__________________________________
 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10. 11. 12. 13. 14. 15. 16. 17. 18. 19 .20

ECE students only:

      X
____X_X_______X_____X_____X_X_X___________________X___________________________X
 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10. 11. 12. 13. 14. 15. 16. 17. 18. 19 .20

Solutions

One of the locations in the small RAM inside the processor is used as the program counter for this microprocessor. Give a sequence of micro control words that will increment the PC register.
```
    |    mem    |          alu             |  bus   |
    |___________|__________________________|________|
... |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__| ...
    |  MA |CM|RM|BN XE AE BE CE CI|CA|CB|RS|LA RD SD|
    |     |  |  |                 |     |  |        |

      0  0  0  1  -  -  -  -  -  -  1  0  0  0  0  0  A = RAM[PC]
      0  0  1  0  0  1  1  0  1  1  0  0  1  0  0  0  RAM[PC] = A+1
```
3 students solved this well and 3 completely failed to understand the question. The remainder had scores distributed widely. Of the common errors, 9 were penalized for using the bus field -- these bits had no defined function until much later in the exam, and they were certainly not relevant to problem 1 in the context of the given data flow diagram. 7 students somehow spread this simple operation into 3, 4 or even more microinstructions.
We can left-shift any quantity by adding it to itself. Give a clearly justified estimate of the number of microcycles this system would require to do a double-precision left-shift of the AC|MQ register.
1: A = B = RAM[MQ]
2: RAM[MQ] = A + B, goto 5 if add sets C
3: A = B = RAM[AC]
4: RAM[AC] = A + B + 0, goto next (whatever is next)
5: A = B = RAM[AC]
6: RAM[AC] = A + B + 1, goto next (whatever is next)
So, it takes 4 microcycles to execute, and it takes 6 microinstructions. The conditional mechanism is needed to propagate the carry out from shifting MQ into the carry in for shifting AC.
5 did well here, and 5 earned no credit. 7 presented pseudocode of one kind or another with no accounting for register transfers.
a) What features (if any) are missing from this architecture that you would need if you wanted to microcode a multiply instruction?
The classical multiply algorithm using an accumulator and a multiplier-quotient register (as suggested by the names AC and MQ) operates by testing the least significant bit of MQ, doing a right-shift on the double-register, and then adding the multiplicand to MQ if the bit that was tested was one. Of the above operations, we are missing both the ability to easily test the least significant bit of a register and the ability to do a right-shift.
As problem 2 demonstrates, we can do a left shift, so if we want to do a truly stupid implementation, we can do a 15 bit left shift to bring the least significant bit into the sign bit for testing, but this is awful!
10 had full credit here, 4 earned no credit. 4 unambiguously pointed out the missing shift operation, and 7 more made ambiguous references to a missing shift operation (not mentioning the direction of the shift, or suggesting that this architecture had no support at all for shifts, an odd answer in the light of problem 2).

b) What features (if any) are missing from this architecture that you would need if you wanted to microcode a divide instruction?
The classical divide algorithm using an accumulator and a multiplier-quotient register (as suggested by the names AC and MQ) operates by attempting to subtract the divisor from the high end of the dividend in AC, doing so only if the result was non-negative, and then left shifting the double register, shifting in a one if the subtraction was done, and shifting in a zero if not. All of the above operations can be done on this architecture with no modification, using the left-shift algorithm suggested in the statement of problem 2 and the information from the note to control the subtraction.
8 had full credit, while 14 earned none, typically by writing lengthly enumerations of missing features that were, in fact, not missing at all! A very few earned some partial credit.

a) Give a block diagram of the structure of an 8K RAM module with 3 auxiliary inputs that the user is expected to hard-wire to set the address of the module.

Bus -----/---o----------------------o------o----------------
         16  |                      |      |
LA  --o------|----------------------|------|----------------
RD  --|------|--------o-------------|------|----------------
SD  --|------|------o-|-------------|------|----------------
      |   ___|___   | |   ___       |      |
       --|>__MA__|  |  --|   |      |     / \
             |      |    |AND|------|----/___\
aux hard  ___|___   |  --|___|   ___|___   |
wired  |   |   |    | |         |   in  |  |
address|   |    -/--|-|---------|addr   |  |
      3/  3/     13 | |   ___   |  RAM  |  |
      _|___|_        -|--|   |  | 8Kx16 |  |
     |compare|        |  |AND|--|>      |  |
     |_______|        o--|___|  |__out__|  |
         |            |             |      |
          ------------               ------

3 had good answers, 13 earned no credit. The most common thoroughly wrong answer involved drawing a rectangle with the label 8K by 16 RAM, with absolutely no hint of how this abstraction could be connected to the processor in question. The most common error on answers that earned partial credit involved adding various extra gates, sometimes quite a few, but frequently oddly complex address decoding or extra gates in the bus interface. Other common errors include: Omission of the memory address register, suggesting significant misunderstanding, and passing a 16 bit address to an 8K RAM, a strong indication of general confusion.

b) Show the sequence of microinstructions required to load the AC register with the contents of the memory location addressed by the A register. micro control words that will increment the PC register.

    |    mem    |          alu             |  bus   |
    |___________|__________________________|________|
... |__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__| ...
    |  MA |CM|RM|BN XE AE BE CE CI|CA|CB|RS|LA RD SD|
    |     |  |  |                 |     |  |        |

      x  x  0  0  0  0  1  0  0  x  0  0  1  1  0  0  MA = A
      0  1  1  0  x  x  x  x  x  x  0  0  0  0  1  0  AC = M[MA]

3 had good answers here; 8 earned no credit. 6 earned only 1/3 credit, 4 earned higher partial credit; a major deduction was made for extra microcycles, and errors within a microcycle were penalized individually.

a) Suggest an appropriate addition to the register transfer logic given at the head of the exam to simplify the use of the different fields of the instruction word.
When fetching an instruction, we need a destination register, the instruction register. While it may seem reasonable to use address 11 in the small RAM inside the CPU, this is ruled out by the need to add a way to break out the fields of the instruction register, in conjunction with the single-bus internal structure of this CPU. Therefore, we must add a new register and logic to aid in instruction decoding.
```
Bus ----o--/--------o-----------o----------------
        |  16       |           |
        |        ___|___        |
        | CI ---|>__IR__|      / \       extension to
        |           |    RI --/___\      microinstruction
      __|__    _____|_____   ___|___
       | |      |  |    |     |   |      | IR  |
      4/ /12   4/  /2   /10  5/   /10    |_____|
       |           |    |     |   |  ... |__|__| ...
OP <---            |    |     0   |      |CI RI|
                   |    |         |      |     |
M  <---------------      ---------
```
Only 2 gave good answers. 2 more suggested adding an instruction register, and 3 earned at least some partial creidt for answers that were relevant but largely disconnected from the problem specification. All of the remainder earned no credit! The most common problem appears to have been a complete misunderstanding of the question, in which the instruction format was related to the microinstruction format, with the understanding that each instruction would be executed in one microcycle, a very unlikely interpretation on a microcoded low-performance machine.

b) Evaluate your suggestion by estimating the number of microinstructions it would take to decode and execute an instruction to load an immediate constant in the AC register, assuming that the previous microinstruction has set up the memory address from which the instruction will be fetched, so that your first microinstruction is the fetch itself.
0: MA = ... (establishes the precondition we're given)
1: IR = M[MA], 16-way branch on OP field of IR
...
-- first microinstruction of load opcode
2: A = IR(low 10 bits), 4-way branch on M field
...
-- first microinstruction for immediate mode load
3: RAM[AC] = A(low 10 bits)
If high performance were the issue, different harware would allow the above to be shortened to 2 instructions, a 64 way branch on the combined OP and M fields of the instruction, followed by assigning the immediate constant. The code given uses a 2-stage instruction decode, with the opcode decoded first, and then the address mode. All address modes begin with the address constant in the A register, ready to use for indirection or indexing, but the use of A does nothing for the immediate mode question assigned here.
Only 1 student got this, 1 more had an answer that was only slightly flawed, and 1 more had a major flaw; the remainder received no credit. In light of the number who had problems with part a, the small fraction receiving credit on part b is not really surprising.