Fall 2001, Computer Organization, Assignment 4

Section 01: Due Tuesday, December 4 at the start of class
Section 02: Due Monday, December 3 at the start of class

There are 40 points on this homework, but it has the same weight as the other assignments. I am tired of counting half points!

Upload the assignment if it is going to be late. Hand-in a hard copy in class.

  1. (6 points) Use Mic-2 for this one. Assume there is an extra condition code for the carry bit (C). There is also a new jump bit in the microcode: JAMC. Create the Mic-2 microcode for IF_ICMPGTU (If Greater Than Unsigned). The instruction will pop the top two values on the stack, subtracting the top value from the second value on the stack (second - top). The result is not stored. The instruction will jump if the top value is greater than the second value, when treated as unsigned numbers. The instruction will have an operand that is the 16-bit offset for the jump.
  2. (6 points) Use Mic-2 for this one. The instruction ISHR (arithmetic shift right) exists in JVM but not in IJVM. It uses the top two values on the stack: it removes the top value and replaces the second value with the result. The second word on the stack is the operand to be shifted. Its content is shifted right by a value between 0 and 31 inclusive, depending on the value in the 5 least significant bits of the top word on the stack (the other 27 bits of the top word are ignored). The sign bit is replicated to the right for as many bits as the shift count. Extend the microcode to include this instruction as part of IJVM. You may not make any assumptions about what the opcode for the instruction is. An extra point if it is done in 9 instructions or less. (Hint: You will need to generate the number 31)
  3. (4 points) Draw a finite state machine for branch predictioin that  will only change predictions after three consecutive mispredictions.
  4. (6 points) Mic-3. Figure 4-33 on page 258 shows how the SWAP instruction from Mic-2 would be sequenced in Mic-3. Create a similar table for IAND.
  5. (6 points) Create a table similar to the one in Figure 4-43 for the following instruction sequence.

    R1 = R1 * R2
    R1 = R1 + R3
    R4 = R2 + R2
    R3 = R3 / R1
    R1 = R1 + R2

    You do not need to indicate the scoreboard for the registers being read and written. Use in-order issue and in-order retire. Add a column that indicates the type of dependency, if there is one:
  6. (6 points) Create a table similar to the one in Figure 4-44 for the instructions in the previous question. You do not need to indicate the scoreboard for the registers being read and written. Use out-of-order issue and out-of-order retire, with register renaming.
  7. (2 points) Do question 26 from the Chapter 4 exercises in the book on page 301.
  8. (4 points) Consider the direct-mapped cache on page 267.