I am working on a computer organization caching problem
The Problem: What happens if the associativity level is greater than the cache size?

I know that associativity level is how many blocks are in a set. Say we have a 16 way set associative cache and a cache size of 15. What would happen? Would the cache break or would it turn into a fully associative cache(1 set)

  • 1
    $\begingroup$ If the associativity was equal to the number of blocks, it would be fully associative. One might interprete the associativity being greater than the number of blocks to mean that there are more tags than blocks, where at least one of the tags is invalid. While having tags without data has some uses (such as L2 tag inclusion of multiple highly associative L1s, tracking reuse, cache compression, and V-way cache), such would typically be used in a larger cache where full associativity is not practical. Checking 4,096 tags for every access in a 256KiB L2 is impractical. $\endgroup$ Jun 4 '15 at 3:00
  • $\begingroup$ @PaulA.Clayton Doesn't associativity level mean number of sets? From eecg.toronto.edu/~moshovos/ECE243-07/l26-caches.html , if associativity was equal to the number of blocks, that be a direct-mapped cache, not a fully associative. Like if you had 8 blocks and an associativity of 8, then there would be 8 sets and a block from RAM would have a designated set to go to. $\endgroup$ Jun 4 '15 at 4:39
  • $\begingroup$ The associativity is equal to the number of blocks in the set (i.e., that are addressed by a specific index value); this is the number of ways (thus n-way associativity). Look at it as the number of placement choices (in the cache) available for a given block in memory. A direct-mapped cache has only one block in each set (a block in memory maps directly to a specific block, no choice). If you are familiar with hash tables, a set corresponds to a bucket (indexing); most hash tables are "direct-mapped" but with N-entries per bucket a hash would be "N-way associative". $\endgroup$ Jun 4 '15 at 10:39
  • $\begingroup$ @PaulA.Clayton Thank you. Can you clarify the "there are more tags than blocks, where at least one of the tags is invalid." part? Doesn't each block have to be associated with a tag that identifies the block address in RAM it came from, Correct me if that's wrong. From that wouldn't the only of a TAG being in a cache be if it's associated with a block. So theoretically the number of tags can't be greater than the number of blocks? $\endgroup$ Jun 4 '15 at 15:55
  • $\begingroup$ In a conventional cache having more tags than blocks (associativity greater than the number of blocks) does not make sense. However, e.g., a cache in which compressible blocks are stored in half-sized blocks would have excess tags if none of the blocks are sufficiently compressible (e.g., there might be 8 tags per set but only .12 half-sized blocks, leaving two unused tags if all blocks require two half-sized blocks). If each set had 8 blocks but 16 tags, one could track the history of evictions to avoid a second eviction of a block that is more likely to be reused soon. $\endgroup$ Jun 4 '15 at 16:57

Since the associativity is equal to the number of cache blocks in a set, in a traditional cache design there is no sensible interpretation of having associativity greater than capacity; a set cannot have more cache blocks than are in the entire cache.

Having more tags than full-sized blocks in a set can make sense.

If the data in a block can be compressed (possibly in a lossy manner), then data from multiple blocks may fit in the storage provided in a single block. In this case having more tags than uncompressed cache blocks allows such compressed data to be cached and indexed normally. For example, with twice as many tags, a 64-byte cache block compressed to 24 bytes and one compressed to 40 bytes could fit into a single 64-byte storage (with some metadata overhead beyond just the extra tag).

Related to compression, extra tags can also be used to facilitate use of large cache blocks with sectors allocated to different tags. For example, each tag could include a full set of valid bits for all subblocks (sectors) in a cache block, reducing the tag overhead (a valid bit is smaller than a tag) at the cost of less effective allocation. This was proposed for off-chip DRAM caches with on-chip SRAM tags (i.e., limited tag storage budget relative to cache capacity).

Extra tags can also be used to reduce back invalidation in a cache that is tag-inclusive of another cache. Tag inclusion allows the inclusive cache to be probed and avoid accessing the included cache unless the data is present there (this is a form of snoop filtering), but a replacement in an inclusive cache that victimizes an entry shared in the included cache forces the block to be removed (back invalidation) from the included cache to maintain the inclusion property.

Extra tags can also be used to improve replacement policy by keeping a record of recent victims. For example, on a tag hit but data miss, the block might be allocated with a "sticky" bit set that would be unset when the block would normally be evicted using the standard (LRU-oriented) replacement policy (this is not the best replacement policy helped by extra tags but it is a clear example).

Similarly, extra tags might be used to improve prefetch accuracy. For example, a proposed prefetch to an address that is a tag hit is more likely to be used than one that is a tag miss.

Extra tags can also be used in decoupling indexing of tags and storage of data. For example, Moinuddin K. Qureshi et al.'s "The V-Way Cache : Demand-Based Associativity via Global Replacement" proposes using twice as many sets as a cache of the capacity and associativity would normally have. This has the benefit of reducing conflict misses under a constant number of tag comparisions because generally some blocks would be allocated to the alternate set that would map to a single set normally (the number of currently used ways in a set can vary). This excess associativity also allows global replacement with full utilization of data storage capacity; if the capacity was equal to the product of associativity and number of sets, then an victimized block (invalidated tag) would mean fewer valid tags than data storage blocks.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.