Where Can a Block Be Placed?
The advantage of increasing the degree of associativity is that it usually decreases the miss rate. The improvement in miss rate comes from reducing misses that compete for the same location. The following figures show the data cache miss rates for each of eight cache sizes improve as the associativity increases.
| Scheme Name | Number of Sets | Blocks per Set |
|---|---|---|
| Direct mapped | Number of blocks in cache | 1 |
| Set associative | Number of blocks in the cache / Associativity | Associativity (typically 2-16) |
| Fully associative | 1 | Number of blocks in the cache |
| The largest gains are obtained in going from direct mapped to two-way set associative. Smaller caches obtain a significantly larger absolute benefit from associativity because the base miss rate of a small cache is larger. |
|
How Is a Block Found?
The choice of how we locate a block depends on the block placement scheme, since that dictates the number of possible locations:
| Associativity | Location Method | Comparisons Required |
|---|---|---|
| Direct mapped | Index | 1 |
| Set associative | Index the set, search among elements | Degree of associativity |
| Fully associative | Search all cache entries | Size of the cache |
| Separate lookup table | 0 |