Computer Organization, Problem Set 3

1. Devise a way in Java or C to interchange two variables A and B wihtout using a third variable or register. Hint: Use exclusive or.
2. Implement IXOR in Mic-1. The command will pop the top two values on the stack, XOR them together, and store the result on top of the stack.
3. Implement LDC_W_ARRAY, in Mic-1. The command has a 2-byte offset to the first constant to load onto the stack. The third byte after the opcode is the count of how many constants to push. If the constant is zero, then nothing should be pushed. Be very careful when you create label names. It is safest to always create a new label, than to reuse an existing label from the microcode.
4. The DMA transfer descrived in Fig. 5-32 requires 2 bus transfers to move data betweenan I/O device and memory. Describe how the perfomance of DMA can be improved by unsing the bus architecture in Fig. 3-35.
5. There are three improvements from MIC-1 to MIC-2:
   1. 3 bus architecture,
   2. instruction fetch unit handles the PC and can access 16-bit operands,
   3. merging the interpreter loop.

   INVOKEVIRTUAL in MIC-1 has 22 lines of code, it has 11 lines of code in MIC-2. There are three types of changes:

   1. sequences of instructions are grouped into one instruction,
   2. some instructions are removed,
   3. some instructions are modified.

   For the MIC-1 INVOKEVIRTUAL command,

   1. indicate which instructions are unchanged, grouped, modified, or removed.
   2. indicate which of the three improvements allowed the alteration. There could be more than one per line. Use removed as the last choice. If multiple instructions are combinded into one, then use grouped, instead of removed and changed.
   3. If they are grouped, modified or unchanged, indicate the corresponding instruction from Mic-2.

   If there is a choice between marking a statement as being grouped with others or being removed, choose grouped.

   Correction: line 5 in Mic-2 should be the same as line 12 in Mic-1. H does not needed to be updated in line 5 of Mic-2.

6. Implement IFLE in Mic-2. It tests if the top of the stack is less than or equal to zero. Perform a conditional branch if the top of stack is less than or equal to zero, otherwise continue to the next default instruction. Provide possible addresses for all the labels used.
7. Show how INVOKEVIRTUAL from Mic-2 would be placed into the Mic-3 pipeline. Draw a chart like the one in the book for SWAP.
8. Find the sequences of microinstructions that use the most consecutive bytes from the shift register in the IFU, without a chance to refill the register. Is there a possibility that the shift register could be empty when MBR1 or MBR2 is needed?

9. Show how these instructions would be fed through the seven-stage pipeline for Mic-4.

         ILOAD I
         ILOAD J
         ISUB
         ISTORE K
       

   Use MAL to represent the instructions in the ROM.

10. The Mic-2 data path uses latches for the A, B and C registers. Could this be a problem? In other words, do we need to use flip-flops instead of latches?
11. Draw a finite-state machine for branch prediction that changes state after making two out of three mispredictions.
12. Create a table similar to the one in Figure 4-44 for the instructions below.
    R3 = R0 / R2
R3 = R3 * R2
R2 = R0 + R1
R0 = R2 / R5
R6 = R3 - R6
R3 = R8 + R0
    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. Assume that the secret registers are S0 through S8.
    1. Add a column that indicates the type of dependency, if there is one. If there is more than one, list them all.
       • No Dependency
       • RAW
       • WAR
       • WAW
    2. Add a column for renamed registers. List how a register was renamed, like S3 = R3.
13. A computer prefetches up to 20 instructions in advance. However, on the average, four of these are conditional branches, each with a probability of 90% of being predicted correctly. What is the probabliity that the prefetching is compeletely correct?
14. A computer has a two-level cache. Suppose that 70% of the memtory references hit on the first level cache, 20% hit on the second level cache, and the remaining miss both caches. The access times are 10 nsec, 20 nsec and 100 nsec, respectively.
    1. If all three cache reads begin at the same time, and unneeded reads are cancelled when a cache is hit, what is the average access time?
    2. If the times for the level 2 cache and memory start counting when at the moment it is known that they are needed (e.g., a level 2 cache access does not start until the level 1 cache miss occurs), then what is the average access time?
15. 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.
16. Draw a finite state machine for a 3-bit history table for branch prediction. The prediction is changed only after a third wrong prediction.
17. Consider the open computer lab on a typcial day. 50 students are working at 50 terminals. Is this a SIMD or MIMD system? Under what conditions might it be the other type of system?
18. For each topology shown in Fig. 8-37, compute the diameter of the network.
19. For each topology shown 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 (isolating at least one node from some other node).