Midterm Exam

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

Exam Score Distributions

Mean =   11.61
Median = 11.3
                                         X   X         X                   X
0 . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10. 11. 12. 13. 14. 15. 16. 17. 18.
               C C       + + - -       B B       + + - -       A A       + + 

Overall Score Distributions including Homeworks 1-6

Mean =   38.80
Median = 40.4
                             X     X  
       X       X             X X   X X
26. 28. 30. 32. 34. 36. 38. 40. 42. 44. 46. 48. 50.
     C C C + + - - B B B B + + - - A A A A + +


  1. Background: The microinstruction format for the Xerxes 150 (a mythical computer) is as follows:
        ___ ________ ___ _________ _________ _________ _________
       | r |  rmux  | c |  next0  |  next1  |  next2  |  next3  |
    r - 4 bits specifying a destination register
    rmux - 8 bits to control multiplexors and function selects
    c - 4 bits to select which 2-bit conditon to test
    nexti - 12-bits for each next address

    Part a) What aspects of this microinstruction format resemble horizontal microcode?

    The 64-bit microword is typical of horizontal microcode, as is the inclusion of multiple next-state addresses in each word.

    5 did well here, 7 earned half credit. Among the wrong answers, a surprisingly common one seemed to involve the idea that this microinstruction format somehow allows parallelism. Nowhere in the wording of this problem is there any hint that this could be so.

    Part b) What aspects of this microinstruction format resemble vertical microcode?

    The fact that each microinstruction can clock only one register is typical of vertical microcode.

    9 did well here, 3 earned half credit. Several were distracted by the c field, thinking that it was characteristic of horizontal or vertical code! All approaches to microprogramming allow conditionals to be tested, and for all but the purest forms of Moore machine, there will be some part of the microword that selects the condition or conditions to be tested.

    Part c) Is the microengine that executes this microcode closer to the Moore or Mealy formalism?

    It is basically a Moore formalism because the r and rmux fields, the outputs of the control unit, are not conditioned on the condition selected by c, but depend only on the current state.

    6 did well here, 6 earned half credit.

  2. Background:
                   A               B   B
                   |             __|___|__
         Bsel _____|_____________\ 0   1 /
         Bdis _____|______________\disab/  SN74157
                   |_________      \___/
                   |   _____ | ______|
                  _|__|_    _|_______|_
                 | nand |  |   adder   |____ Cin
                 |______|  |___________|
          SN7400     |___     ___|       SN7483
         Rsel _________\ 0   1 /
                     0__\disab/  SN74157

    Problem: This ALU has 4 function select inputs; complete the 16-row table of operations.

    RselBdisBselCin function
    0 0 0 0 not(A&B)
    0 0 0 1
    0 0 1 0 not(A) | B
    0 0 1 1
    0 1 0 0 all ones
    0 1 0 1
    0 1 1 0
    0 1 1 1
    1 0 0 0 A + B
    1 0 0 1 A + B + 1
    1 0 1 0 A - B - 1
    1 0 1 1 A - B
    1 1 0 0 A
    1 1 0 1 A + 1
    1 1 1 0 A
    1 1 1 1 A + 1

    6 did well here; 3 earned no credit, and the remainder made a variety of errors; the most common was to misevaluate not(A&0) in rows 4 through 7, frequently arriving at all zeros. Remarkably few made an attempt to simplify the logic or arithmetic functions, but this was only penalized in the case of rows 4 to 7.

  3. Background The alternative to the VAX proposed in the study questions had no branch, conditional branch or call instructions. Assume that the program counter is one of the machine's 15 general purpose registers, and that the COND c instruction causes the next 8-bit instruction to be skipped if c holds.

    Part a) What sequence of instructions for this fictional machine comes close to the equivalent of a PC-relative branch with an 8-bit displacement?

    MAR pc; DISB disp; RMA pc

    3 got this exactly, 2 had longer instruction sequences centered on ADDI, 5 had sequences that could be repaired with a bit of work for partial credit, and 2 more had answers no better than slightly relevant. It should be noted that the ADDI-based sequences received full credit here but were extremely difficult to fix for part b.

    Part b) If you wanted to take your sequence of instructions from part a and modify it to become a conditional branch, where would you insert the COND instruction?

    MAR pc; DISB disp; COND c; RMA pc

    6 had good answers here, while 3 more had a slight penalty because they put the COND in the right place in an ADDI based instruction sequence, not noticing that the conditions tested for such a branch are extremely likely to be destroyed or reset by the ADDI; 6 more inserted COND instructions too soon in their instruction sequences, so that the final store to the PC would always occur, but some part of the arithmetic on this would be omitted, leading to very strange results.

  4. Background The proposed alternative to the VAX has limited support for autoincrement addressing, in that the memory address register is incremented by operand load and result store operations.

    Part a) Give a sequence of instructions for our proposed machine that does a post-increment autoincrement load of an operand relative to some register R.

    MAR r; OPMx; RMA r;

    4 did well, and one more had a long and strange but correct solution that avoided using the built-in autoincrement mechanism; 3 gave store or otther memory reference instructions instead of the assigned load, and 3 more made no memory reference but were otherwise correct.

    Part b) Explain why your answer to part a will not work when R is the program counter.

    The problem is, the value of PC that is used for autoincrement addressing is the value sampled by the MAR r instruction, so the value loaded will be likely to begin with the OPMx instruction and not with any useful immediate value; furthermore, if we used OPMB, the RMA r instruction will set PC to the address of the RMA r instruction itself, leaving the processor hanging in a tight loop. Repaired instruction sequences that use PC-relative autoincrement loads to fetch operands are at least 2 instructions longer, plus the operand itself. expected are difficult to construct

    11 did well here, only one received partial credit.

  5. Provocative statement: When a VAX instruction is mapped to the proposed architecture, each microinstruction on the VAX becomes one instruction in the proposed architecture.

    Question: Criticize the above provocative statement!

    Some of the instructions listed for the example architecture, for example, the floating point operations and memory reference operations, are likely to take more than one control-unit cycle on any machine; on a microcoded VAX, they will take multiple microcycles, yet they are single instructions on our machine.

    Also, if a VAX is microcoded using horizontal microcode, as all of the high-end VAXen were, then one VAX microinstruction might perform register transfers in parallel that require a sequence of instructions on the proposed architecture.

    Finally, there are holes in the proposed architecture, as hinted at by the autoincrement example in the previous question. There is simply no way to easily emulate autodecrement addressing on the proposed machine, and there are probably other missing features as well.

    If, however, we ignore floating point and other VAX features with no parallel in this machine, assume a fast main memory, and assume we're only comparing with a low-performance microcoded VAX using vertical microcode, then the provocative statement is not entirely misleading.

    5 did well here, 2 did fairly well, and 9 more earned at least some partial credit. Only a few earned no credit.