Computer Organization and Structure

Homework #6

Due: 2004/1/13

1. Here is a series of address references given as word addresses: 1, 4, 8, 5, 20, 17, 19, 56, 9, 11, 4, 43, 5, 6, 9, 17. Assuming a direct-mapped cache with 16 one-word blocks that is initially empty, label each reference in the list as a hit or a miss and show the final contents of the cache. Using the same series of references, show the hits and misses and final cache contents for a direct-mapped cache with four-word blocks and a total size of 16 words.

2. Cache C1 is direct-mapped with 16 one-word blocks. Cache C2 is direct-mapped with 4 four-word blocks. Assume that the miss penalty for C1 is 8 clock cycles and the miss penalty for C2 is 11 clock cycles. Assuming that the caches are initially empty, find a reference string for which C2 has a lower miss rate but spends more cycles on cache misses than C1, and find a series of reference for which C2 has more misses than C1. Use word addresses.

3. Here is a series of address references given as word addresses: 1, 4, 8, 5, 20, 17, 19, 56, 9, 11, 4, 43, 5, 6, 9, 17. Show the hits and misses and final cache contents for a two-way set-associative cache with one-word blocks and a total size of 16 words. Assume LRU replacement. The same questions but for a fully associative cache with one-word blocks and a total size of 16 words. The same questions but for a fully associative cache with four-word blocks and a total size of 16 words.

4. Consider three machines with different cache configurations:

n Cache 1: Direct-mapped with one-word blocks

n Cache 2: Direct-mapped with four-word blocks

n Cache 3: Two-way set associative with four-word blocks

The following miss rate measurements have been made:

n Cache 1: Instruction miss rate is 4%; data miss rate is 8%.

n Cache 2: Instruction miss rate is 2%; data miss rate is 5%.

n Cache 3: Instruction miss rate is 2%; data miss rate is 4%.

For these machines, one-half of the instructions contain a data reference. Assume that the cache miss penalty is 6 + Block size in words. The CPI for this workload was measured on a machine with cache 1 and was found to be 2.0. Determine which machine spends the most cycles on cache misses. If the cycle times for the machines are 2ns for the first and second machines and 2.4ns for the third machine. Determine which machine is the fastest and which is the slowest.