Computer Organization, Assignment 5

Due Friday, December 5 at midnight

1. (6 points) Assume there is another condition code V that tests for signed overflow. 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 N bit is wrong.

2. (6 points) Use Mic-2. 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 numeric opcode for the instruction is (Hint: You will need to generate the number 31). An extra point if it is done in 9 instructions or less.
3. (6 points) Create a table similar to the one in Figure 4-43 for the instructions below.
   R3 = R0 + R1
R3 = R3 - R2
R2 = 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 in-order issue and in-order retire, without register renaming. Add a column that indicates the type of dependency, if there is one. If there is more than one, list the one that is more important.
   • No Dependency
   • RAW
   • WAR
   • WAW
4. (6 points) Create a table similar to the one in Figure 4-44 for the instructions below.
   R3 = R0 + R1
R3 = R3 - R2
R2 = 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. Add a column that indicates the type of dependency, if there is one. If there is more than one, list the one that is more important. Assume that the secret registers are S0 through S8.
   • No Dependency
   • RAW
   • WAR
   • WAW
5. A computer has a two-level cache. Suppose that 80% of the memory references hit on the first level cache, 15% hit on the second level, and 5% miss. The access times are 5 nsec, 20 nsec, and 40 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; a memory access does not start until the level 2 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.
6. (4 points) Consider the direct-mapped cache on page 267 for the address FEB43265h.
   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 twice as many 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.
7. (3) Referring to Figure 8-24, would sequential consistency exist if R3 gets (200, 100) and R4 gets (200, 100)? Explain the sequence of writes and reads if is it consistent or explain why it is inconsistent.
8. (4) Referring to Figure 8-25, list two weakly consistent sequences involving 3B, 1D, 1E. List two inconsistent sequences involving 3B, 1D, 1E.
9. (3) Referring to Figure 8-28 (b), what will be the state for each cache if CPU 3 reads the same cache line?
10. (3) Referring to Figure 8-28 (a), what will be the state for each cache if CPU 3 writes to the same cache line?
11. (2) If a crossbar switching network connects 32 CPUs with 32 memories, how many switches are needed?
12. (3) If an omeage crossbar switching network connects 32 CPUs with 32 memories, how many switches are needed?
13. (4) For topologies a, c, d, e listed in Fig. 8-37, compute the diameter of the network.
14. (4) For topologies a, d, e, f listed in Fig. 8-37, compute the minumum number of arcs that can be removed in order to split the topology into two parts that hage the saem number of nodes each.
15. (4) For topologies d, e, f, g listed in Fig. 8-37, determine the degree of fault tolerance each one has, defined as the maximum number of links that can be lost without partitioning the network in two.
    

Submitting the Assignment

You may write all your answers on paper, scan the papers and zip them, then submit the zip to me.

Upload your file to me using the upload program on my class page:
Submitting Homework Online.

Course Objectives met by this Homework