Homework 11

22C:122/55:132, Spring 2001

Due Friday Apr 20, 2001, in class

Douglas W. Jones

Background: Consider a machine with variable-length instructions based on an 8-bit (1 byte) instruction syllable. The first 2 bits of the first byte of each instruction encode the instruction length: 

 _______________ __
|___|___________|__ ...
| L |   other   |     optional
       information  additional bytes

L = 00 -- length 1
L = 01 -- length 2
L = 10 -- length 2
L = 11 -- length 3

  1. Problem: If the entire first byte is the opcode, how many opcodes does this machine machine allocate for each instruction size.

  2. More background: Our machine has a 2-way superscalar pipelined implementation, both pipelines are equally able to execute all instructions. Each pipeline has a stall signal that is presented to the instruction fetch stage. The pipeline will execute an instructin if: a) it is not stalled, and b) enough valid bytes are available to make up one instruction.

    The following naming convention may be useful: The first pipe is P1, the second is P2. The first byte of the instruction fed into P1 is P1B1. The multiplexor used to select the third byte input to the second pipe is P2B3mux, and this name is also used for the control input to the multiplexor. Bits of the instruction register are (from left to right) I1B1 to I1B8 for the 8 bits of the first byte, and so on. V1 is the valid bit on the first byte of the instruction register, and S1 is the stall signal from the first pipe.

    Part A: Give a diagram showing the relevant registers and data paths used to control the routing of instruction bytes from the instruction register to the next stages of the two pipelines.

    Part B: Give the column labels on the truth-table for the function that controls the multiplexors you identified in part A. The inputs to this function must include everything relevant to the routing problem, and the outputs will be multiplexor controls for each of the multiplexors.

    Part C: Assume that no optimization is applied to the truth-table in part B. That is, assume that it is simply stored in a ROM inside the CPU. How big is this ROM?

    Part D: Give the contents of 2 rows of this ROM in order to demonstrate that you understand how to work out the remaining rows.

  3. A Problem: Modify the calling sequence, receiving sequence and return sequence given at the end of part 1 of the notes for Lecture 32 so that it uses a return address instead of a continuation point. Clearly mark which instructions you had to change.

  4. Background: In the running example 5-stage pipelined machine we've been discussing, all instructions that change anything in registers or memory do so in the operand store stage. An alternative model has several pipeline stages that can complete instructions. For example the store register in memory instruction might be completed by the operand fetch stage if this is able to write to memory as well as read from memory.

    Part A: Does this alternative model offer a potential performance advantage? Why or why not?

    Part B: Does this alternative model pose potential problems for interrupt and trap handlers? Explain!