Fall 2002, Computer Organization, Assignment 4

Section 02: Due Monday, December 2 at the start of class

There are 40 points on this homework, but it has the same weight as the other assignments.

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

  1. (5 points) Assume there is another condition code that tests for signed overflow, V. It will be set after each ALU operation. If the operation is not F0=F1=1, then the V bit is cleared. If the operation is F0=F1=1, then the V will be set if there is signed overflow. Write the Mic-2 instructions that will implement IFICMP_GTS offset. It will pop the top two values from the stack and jump if the second value is greater than the first value when treated as signed numbers. If the V is set, it means that the current value of the Z bit is wrong.
  2. (6 points) Use Mic-2 for this one. Write the instruction for IMUL varnum const that will multiply the local variable by the constant and write the result back to the local variable. There is not a multiply instruction in the ALU, so you will need to use repeated additions. Either number may be negative. Do not worry about overflow.
  3. (4 points) Draw a finite state machine for determining branch prediction where the prediction is changed if the prediction is wrong 2 out of the last 3 tests.
  4. (4 points) 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 ILOAD.
  5. (6 points) Create a table similar to the one in Figure 4-44 for the instructions below.

    R3 = R0 + R1
    R3 = R3 - R2
    R4 = R0 * R1
    R0 = R2 + R5
    R6 = R3 / R0
    R3 = R8 + R9

    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.
  6. A computer has a two-level cache. Suppose that 70% of the memory references hit on the first level cache,  20% hit on the second level, and 10% miss. The access times are 5 nsec, 15 nsec, and 60 nsec.
    1. (2 points) What is the average access time, assuming the times for the level 2 cache and memory start counting at the moment it is known that they are needed (e.g. a level 2 cache access does not even start until the level 1 cache miss occurs)? Show your work.
    2. (2 points) What is the average access time, assuming the time for the level 2 cache starts counting at the moment it is known that it is needed , but that the memory access starts at the same time as the level 1 cache access (e.g. a level 2 cache access does not even start until the level 1 cache miss occurs, but that main memory and the level 1 cache are accessed simultaneously)? Show your work.
  7. (4 points) Consider the direct-mapped cache on page 267 for the address BEF23456h.
    1. What would be the tag and line for this address ? Leave your answers in hex. Show your work.
    2. Suppose the number of bytes in a word were doubled to 8, that there were the same number of lines in the cache, and that there were 16 words in a line. What would be the tag and line for this address? Leave your answers in hex. Show your work.
  8. (1 point) Ignoring the prefetch of code and microinstructions, Mic-3 does not agree with Mic-4. Explain.
  9. (1 point) How long is a microinstruction in Mic-4?
  10. (1 point) All instructions in Mic-4 that have the final bit set have a particular operation in them. What is that operation?
  11. (2 points) Which instructions in Mic-2 would have the goto bit set in Mic-4?
  12. (2 points) Conditional branch instructions in Mic-4 must have a different format than all other instructions. Explain.