Cache:

1. Consider the following sequence of address references given as decimal word references:

0, 1, 8, 1, 0, 1, 2, 8, 2, 1, 0, 1, 2, 3, 8, 9, 10, 11, 12, 0

Assume that each of the following caches uses an LRU replacement scheme, and that each cache is initially empty. Each cache holds a total of eight words, and the binary address of each reference consists of five bits (e.g., 01100).

a) Assuming a direct-mapped cache with 8 one-word blocks, label each reference in the list as a hit (H) or miss (m) and show the final contents of the cache (including the valid bit, tag, and data at each cache index).

b) Show the hits, misses, and final cache contents for a direct-mapped cache with 2 four-word blocks.

c) Show the hits, misses, and final cache contents for a 2-way set-associative cache with 4 sets of two one-word blocks. Assume that the cache is initially empty.

d) Based entirely upon the results you reported in parts (a), (b), and (c) of this question, which of these three cache utilization schemes is best? Explain your answer.