Computer Organization, Assignment 5

Due Friday, December 5 (late at 6am on 12/6)

  1. (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.
  2. (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.
  3. 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.
  4. (4 points) Consider the direct-mapped cache in FIgure 4-38 for the address 0xFEB43265.
    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.
  5. (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.
  6. (4) Referring to Figure 8-25, list two weakly consistent sequences involving 3B, 1D, 1E. List two inconsistent sequences involving 3B, 1D, 1E.
  7. (3) Referring to Figure 8-28 (b), what will be the state for each cache if CPU 3 reads the same cache line?
  8. (3) Referring to Figure 8-28 (a), what will be the state for each cache if CPU 3 writes to the same cache line?
  9. (2) If a crossbar switching network connects 32 CPUs with 32 memories, how many switches are needed?
  10. (3) If an omeage crossbar switching network connects 32 CPUs with 32 memories, how many switches are needed?
  11. (4) For topologies a, c, d, e listed in Fig. 8-37, compute the diameter of the network.
  12. (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 have the same number of nodes each.
  13. (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.

You must verify that your upload is correct. The online program has an option to download what was just uploaded. It is your responsiblity to be sure that the file can still be read. If I cannot read the file, it will be graded as a 0.

Course Objectives met by this Homework