Homework 5

CS26

80 pts., due Nov. 21

Show all work.

1. (10 pts.) Consider an ordinary DRAM, a Fast Page Mode DRAM, and an EDO DRAM all rated at the same access speed.
   1. Under what conditions will the Fast Page Mode DRAM be no faster than ordinary DRAM? I.e., characterize the memory access patterns that slow it down.

   2. Are there any memory access patterns that would slow down an EDO DRAM?

   3. Characterize the memory access patterns which would cause an interleaved memory to perform no better than a non-interleaved memory.

2. (10 pts.) In most computers, interrupts are not acknowledged until the current machine instruction completes execution. Consider the possibility of suspending operation of the processor at any point during the execution of an instruction in order to acknowledge an interrupt. Discuss the difficulties that may arise.

3. (10 pts.) Three devices, A, B, and C, are connected to the bus of a computer. I/O transfers for all three devices use interrupt control. Interrupt nesting for devices A and B is not allowed, but interrupt requests from C may be accepted while either A or B is being serviced. Suggest different ways in which this can be accomplished in each of the following cases:
   1. The computer has one interrupt request line.

   2. Two interrupt request line, INTR1 and INTR2, are available. INTR1 has higher priority.

   Specify when and how interrupts are enabled and disabled in each case.

4. (10 pts.) Comment on the following statement: ``Using a faster processor chip results in a corresponding increase in performance of a computer, even if the main memory speed stays the same.''

5. (10 pts.) A program consists of two nested loops --- a small inner loop and a much larger outer loop. Here is the general structure of the program:

   

   The memory addresses are in decimal. With the exception of the two branches at addresses 239 and 1200, all instructions utilize straight line sequencing. Each address contains one instruction. The program is to be run on a computer that has an instruction cache organized in the direct-mapped manner and that has the following parameters:

   

   The cycle time of the main memory is 10 s and the cycle time of the cache is 1 s.

   1. Determine the number of bits in the TAG, BLOCK, and WORD fields in main memory addresses.

   2. Compute the total time needed for instruction fetching during execution of the program.

6. (10 pts.) Consider the effectiveness of interleaving with respect to the size of cache blocks. Using calculations similar to those in Section 5.6.2, estimate the performance improvement for block sizes of 16, 8, and 4 words. Assume that all words loaded into the cache are accessed by the CPU at least once.

7. (20 pts.) A byte-addressable computer has a small data cache capable of holding eight 32-bit words. Each cache block consists of one 32-bit word. When a given program is executed, the processor reads data from the following sequence of hexadecimal addresses: 200, 204, 208, 20C, 2F4, 2F0, 200, 204, 218, 21C, 24C, 2F4

   This pattern is repeated four times.

   1. Show the contents of the cache at the end of each pass through this loop if a direct mapped cache is used. Compute the hit rate for this example. Assume that the cache is initially empty.

   2. Repeat for an associative mapped cache that uses LRU replacement.

   3. Repeat for a four-way set associative cache.