Instructions

You are encouraged to work on the problem set in groups and turn in one problem set for the entire group. Remember to put all your names on the solution sheet. Also remember to put the name of the TA in whose discussion section you would like the problem set returned to you.

Questions

1. Explain the differences between exceptions and interrupts. Be concise in your explanations.

   Explain the similarities of exceptions and interrupts. Clearly describe the steps required to handle an exception or an interrupt.

2. A computer has an 8KB write-through cache. Each cache block is 64 bits, the cache is 4-way set associative and uses a victim/next-victim pair of bits in each block for its replacement policy. Assume a 24-bit address space and byte-addressable memory. How big (in bits) is the tag store?

3. An LC-3b system ships with a two-way set associative, write back cache with perfect LRU replacement. The tag store requires a total of 4352 bits of storage. What is the block size of the cache? Please show all your work.

   Hint: 4352 = 2¹² + 2⁸.

4. (updated - 03/28/09)Based on Hamacher et al., p. 255, question 5.18. You are working with a computer that has a first level cache that we call L1 and a second level cache that we call L2. Use the following information to answer the questions.

   • The L1 hit rate is 0.95 for instruction references and 0.90 for data references.
   • The L2 hit rate is 0.85 for instruction references and 0.75 for data references.
   • 30% of all instructions are loads and stores.
   • The size of each cache block is 8 words.
   • The time needed to access a cache block in L1 is 1 cycle and the time needed to access a cache block in L2 is 6 cycles.
   • The accesses to the caches and memory are done sequentially. If there is a miss in the L1 and a hit in the L2 then the total latency is 7 cycles.
   • Memory is accessed only if there is a miss in both caches.
   • The width of the memory bus is one word.
   • It takes one clock cycle to send an address to main memory.
   • It takes 20 cycles to access the main memory.
   • It takes one cycle to send one word from the memory to the processor. Thus the total latency to get a word from memory to the processor is 22 cycles.
   • The bus allows sending a new address to memory in the same cycle that data is sent from memory to the processor.
   • Assume the data is accessible to the processor only AFTER the whole cache block has been brought in from the memory, and buffered on the processor chip. The processor can then access the data independent of and during the cache fill.
   1. What is the average access time per instruction (assume no interleaving)?
   2. What is the average access time per instruction if the main memory is 4-way interleaved?
   3. What is the average access time per instruction if the main memory is 8-way interleaved?
   4. What is the improvement obtained with interleaving?

5. Hamacher, pg.255, question 5.13. 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 hex 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 throughout 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 part (a) for a fully-associative cache that uses the LRU-replacement algorithm.

   3. Repeat part (a) for a four-way set-associative cache that uses the LRU replacement algorithm.

6. Below, we have given you four different sequences of addresses generated by a program running on a processor with a data cache. Cache hit ratio for each sequence is also shown below. Assuming that the cache is initially empty at the beginning of each sequence, find out the following parameters of the processor's data cache:

   • Associativity (1, 2, or 4 ways)
   • Block size (1, 2, 4, 8, 16, or 32 bytes)
   • Total cache size (256B, or 512B)
   • Replacement policy (LRU or FIFO)

   Assumptions: all memory accesses are one byte accesses. All addresses are byte addresses.

   Address traces

   Number	Address Sequence	Hit Ratio
   1	0, 2, 4, 8, 16, 32	0.33
   2	0, 512, 1024, 1536, 2048, 1536, 1024, 512, 0	0.33
   3	0, 64, 128, 256, 512, 256, 128, 64, 0	0.33
   4	0, 512, 1024, 0, 1536, 0, 2048, 512	0.25

Additional Question

The following problem is meant to help you understand the cache structure. This problems does not need to be turned in.

1. You will be given a cache simulator (just the executable) with a hard-coded configuration. Your job is to determine the configuration of the cache. The simulator takes a trace of memory addresses as input and provides a hit ratio as output. Find the following:

   • Associativity (1, 2, 4, or 8 ways)
   • Block size (1, 2, 4, 8, 16, or 32 bytes)
   • Total cache size (256B, 512B, or 1024B)
   • Replacement policy (LRU or Pseudo-LRU)

   Show the traces you used to determine each parameter of the cache. Assumptions: all memory accesses are one byte accesses. All addresses are byte addresses.

   Simulator

   The syntax for running the program is:

   ./cachesim   <trace.txt>

   The traces are just text files with one integer memory address per line. For example, the following trace would cause conflict misses in a direct-mapped, 256B cache:

   0
   256
   512
   0
   256

   Links to the simulator:

   • Simulator for Linux
   • Simulator for Solaris

   After downloading the file, please do chmod 700 cachesim.linux or chmod 700 cachesim.solaris.