17

Reading and Writing Assignments, Discussion Topics
COS/ELE 375

for class on Monday Nov. 29, 2010

Please read Section 5.3 of the text.

Please turn in written responses to these questions:

1. Associativity usually improves the miss ratio, but not always. Give a short string of address references for which a 2-way set-associative cache with LRU replacement would experience more misses than a direct-mapped cache of the same size. State the size of your caches.

2. This question asks you to figure out the numbers and sizes of a few things associated with a cache. Suppose the computer's address size is k bits (using byte addressing), the cache size is S bytes, the block size is B bytes, and the cache is A-way associative. B is of course a power of 2, so let B=2^b. Figure out what the following quantities are in terms of S, B, A, b, and k:

• the number of sets in the cache;
• the number of index bits in one address;
• the number of 2-input exclusive-OR gates needed to perform the address match; and
• the number of bits in the TAG memory (the part of the cache that holds the tag bits)--not the width of the tag memory, the total number of bits contained in the whole thing.

Then, be prepared to discuss the following in class:

3. We'll look at the hardware implications of cache associativity and larger block sizes. The text's pictures show one giant memory holding tags and data--does this make sense for big blocks? What logic paths might limit performance in a set-associative cache with big blocks? Remember to think about stores as well as loads as you consider these cache structures. You will probably find it helpful to draw some pictures of cache organizations as you prepare for this class.