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)
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.
