# How can i compute tag-index-displacement bits of an address if cache size is not a power of two?

How can i compute tag-index-displacement bits from an address if cache size is not a power of two? Intuitively, i would be inclined to think that i can not directly indicate which bits of the address are used to tag, index blocks and displacement. Instead, i think that i should do some conversion such that it appears that the sum of the bits of tag, index and displacement must be greater than the bits of address. This because for the index i need a number i of bits such that i ≥ log_2(number of blocks), for displacement i need a number d of bits such that d ≥ log_2(dimension of each block in bytes) if i suppose a byte addressable cache. Some suggestions?

As suggested by maverick1989, i explicate the data of the part of the exercise that give me trouble. I have a cache direct-mapped of 5256KB with 32B blocks. Assume a 32-bit addressing mode. This mean that i have (5256*1024)/32 = 168192 blocks. Thus, i need log_2(32)=5 bits of displacement to address a single byte in a block and log_2(168192)=17.3597... bits of index to address a block in the cache. Obviously i have to use 18 bits instead of 17.35.... Now i have some trouble to find the value of these 18 bits, given the address. And after that, what about tag bits?

• Normally, cache sizes are a power of two. In principle, you could use modular arithmetic (mod and div), but that sounds a bit messy. Have you found a computer that actually has a non-power-of-two cache size? Is this a real problem you face with a real computer? – D.W. Sep 9 '15 at 18:22
• All the real caches that i have found have size power of two. I found this case in an exercise. – gvgramazio Sep 10 '15 at 14:53

One way is by having multiple cache banks, each of which is a power of two in size. For example, 3 banks of 16kB each. The first 3 (bank_num) bits can be used with one-hot encoding to decide which bank would need to be checked to access the requested data (or to write to).

The rest of the cache access would proceed as usual (look up TLB to get tag bits, index into cache in parallel, etc.)

However, usually non-powers of two caches are not used because the IPC to cache size curve is such that it you find the sweet spot very close to a number that is a power of two (or you don't lose significantly in IPC by moving to a power of two).

• I appreciate your answer but this isn't my case. I read that there is the possibility that a n-way associative cache has n that is not a power of two. My question is regarding the possibility that a cache has a number, that is not a power of two, of blocks (that have size power of two). I don't know if this is the case of some real cache or if it is just a theoretical case, i found it as part of exercise in an exam. – gvgramazio Sep 10 '15 at 15:07
• @giusva "... cache has a number, that is not a power of two, of blocks (that have size power of two)". Number of what? Can you explain? Sets? For a 3-way set associative cache, for example, you'd still use 2 bits for the block. Performing some kind of logic operation on the bits is usually not done simply because it adds to the critical path of the look up (which is already plagued by complex, slow hardware). Note that while it is usually not done, examples exist (skewed associative caches). – maverick1989 Sep 10 '15 at 18:21
• Sorry for bad explanation. I meant that i have a cache direct-mapped that has n blocks where n is not a power of two. Instead, blocks have size m where m is a power of two. Thus, the nominal size of cache is not a power of two. – gvgramazio Sep 11 '15 at 13:08
• To clarify even more my question, i explicate the data of the part of the exercise that give me trouble. I have a cache direct-mapped of 5256KB with 32B blocks. Assume a 32-bit addressing mode. This mean that i have (5256*1024)/32 = 168192 blocks. Thus, i need log_2(32)=5 bits of displacement to address a single byte in a block and log_2(168192)=17.3597... bits of index to address a block in the cache. Obviously i have to use 18 bits instead of 17.35.... Now i have some trouble to find the value of these 18 bits, given the address. And after that, what about tag bits? – gvgramazio Sep 11 '15 at 13:25
• @giusva, thanks for the explanation. I think you've figured everything out, though. So, could you elaborate why you are having trouble finding the value of those bits? Certainly, a large chunk of numbers that can be indexed by 18 bits would be unused, but that's okay. Also, the tag would be the rest of the bits - 9 for 32-bit addressing. – maverick1989 Sep 13 '15 at 13:47

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.