why does associativity matter

A student writes:

	Dear Dr. Patt,

	Sorry to come back to the topic of caches, but I realized I do not 
	fully understand a certain aspect while doing the problem set.

Actually, as I read the rest of this email, he understands a good part of it.

	Now, suppose we have (correct me if I am wrong) :-
	1) 8 KB Data cache
	2) Direct Mapped
	3) Write-through
	4) Block size of 64
	5) 24 bit Address space
	6) Byte addressable

	>From my knowledge :-
	1) Addr[******] will specify the Byte on the Block
	2) Addr[******] will specify the Index bits
	3) Addr[******] will specify the Tag bits

****** = compliments of me.

	Ok, so suppose we wish to change this cache into a 4-way set Associative
	cache, keeping every other feature to be the same.

	Will the following changes to the tag and index bits be correct?
	1) Addr[*******] will specify the Index bits
	2) Addr[*******] will specify the Tag bits

Again, ******* = compliments of me.  For the record, he got it right.

	Also , why would it make a difference to change a cache from 
	Direct Mapped
	to X-Way Associative? I saw the graph you drew illustrating the
	performance gain, but would it really change the hit ratio as only the
	mapping seems to change?

What does the change of the mapping indicate?  Let's go back to the problem
we worked in class because the numbers are so small that it is easy to keep
it all in our heads.  Recall, we had 32 blocks of memory and 8 blocks in the

If the cache were direct mapped (set size = 1), every block in the
cache has exactly 4 memory blocks competing for it.  What if two of those
blocks need to be accessed again and again.  Since the cache is direct mapped,
two of them can not fit in the cache at the same time.  Therefore, lots of
cache misses as they continually get kicked out and then back in.

What if the cache were 2-way set associative (set size = 2).  Now we have 8
blocks of memory competing for 2 slots in the cache.  The ratio is still 4 to
1, which is not surprising given 32 blocks of memory and 8 blocks of cache.
However, with 8 competing for 2, the two we want in now can be in the cache
at the same time.  No more kicking one out only to bring it back in.  Therefore
the hit ratio improves.

Let's make it concrete.  Say blocks A,B,C,D in memory compete for the same
block E in a direct mapped cache, and blocks R,S,T,U compete for the same
block V in a direct mapped cache.  Suppose we want A and B in the cache
at the same time, and we do not want any of R,S,T,U in the cache.  Our 2-way
set associative cache wins if E and V form a set.  That is, A and B can be in
E and V simultaneously.  As long we don't want to bring in any of R,S,T,U,
the 4 blocks we have added to grow 4 to 8 is a win, since growing 4 to 8
comes with growing the set size from 1 to 2.

Does this help?  If not, please ask again.

Yale Patt

	Once again thanks for your help,

	<<name withheld to protect the student who wants to fully understand>>