The straightforward manner of indexing and tagging a cache is for the index to be the address (in blocks, i.e., removing the block offset) modulo the way size (in blocks) and for the tag to be the quotient of these numbers. The computational cost of exact division for non-powers-of-two makes this less practical for first level caches, but Mersenne number (2n-1) modulo indexing has been proposed for L2 caches to reduce conflicts under regular strided accesses. The cost of calculating the modulo of a Mersenne number is modest, summing sections of the block address (e.g., block address 0xMMMN_NNOO_OPPP with a 4Ki-block way would map to 0xMMM + 0xNNN + 0xOOO + 0xPPP, with 0xfff mapping to 0x000) and only the final sum needs the carry to be propigated. The tag can simply use the bits for a smaller power-of-two-sized cache; one tag bit would encode very little information. (Alternatively, one could guarantee that cacheable addresses never exceed the Mersenne number quotient equal to the highest power-of-two quotient. This leaves a little of the highest portion of the address space as uncacheable, but saves one tag bit.)
IBM's POWER4 L2 cache had three partitions with the partition determined by modulo three of a large number of address bits. This points to the fact that maximally even distribution of blocks to indices is not required.
With an even distribution of accesses across the entire address space, modulo indexing in a non-power of two cache increases conflicts for the smaller indices (for block 0 with Mersenne numbers). Since even distribution is just an appoximate model of actual access behaviors, layering another approximation on top of it need not catastrophically increase the miss rate.
Exploiting approximation, a highly associative cache with ways having a large Mersenne number of blocks could even simply invert an arbitrary indexing bit in each way (one way could avoid this inversion), dropping one in the power-of-two blocks for each way. In an eight-way associative cache with 212-1 blocks per way, eight blocks per 4Ki blocks (less than 0.2%) would be limited to seven-way associativity. This technique could be applied to larger reductions from a power-of-two at the cost of significantly increasing the number of addresses with reduced associativity.
Using skewed associativity (where each way uses a different more complex hash of address bits to determine the index), would further scramble the addresses suffering reduced associativity from high indices not be available, though the miss count increase (compared to a power-of-two way) from the simple bit inversion technique would be modest in high capacity highly associativte caches.
For a direct-mapped cache, using a complex hash of the address to generate an N-bit index and mapping indices to missing blocks to adjacent blocks might be acceptable. The blocks that conflict could be somewhat scrambled.
With set associative caches, one can also use different power of two indices for different ways (which can be viewed as separate caches accessed in parallel). The different ways/caches could also have different allocation and replacement policies. For example, a small highly associative cache (victim cache) might only accept allocation of blocks evicted from the larger less associative cache or a reversal of this allocation policy might be used with selective victims from a small highly associative cache going to a larger less associative cache (HP PA 7200's assist cache plus off-chip direct-mapped cache is an example). Selective allocation could also be used to increase conflicts in accesses with low temporal reuse, allocating non-temporal accesses to a small, modest-associativity cache.
The most straightforward method of providing non-power-of-two cache sizes is to have a non-power-of-two associativity. This allows a single simple indexing function to be used.
