c++ - Bit Shifting in Cache Simulation -

what formula calculating index , tag bits in

1. direct mapped cache
2. associative cache
3. set associative cache

i using formula direct mapped:

#define block_shift 5; #define cache_size 4096; int index = (address >> block_shift) & (cache_size-1); /* in line above want "middle bits" block goes */ long tag = address >> block_shift; /* high order bits tag */ 

please tell me how many bits shifted in associative , set associative cache..

so, think concrete answer question "zero", that's because asking wrong question.

right, cache given size x, directly mapped, use lower part [or other part(s)] of address form index cache. index value between 0 , (chace-size-1). in other words, "address modulo size". since sizes of caches 2ⁿ, make use of fact both of these can performed using simple bitwise "and" (size-1) instead of using divide.

in code, each cache entry (cache-line) holds "block" of 32 bytes, address should divided (shifted) down block-size. 2⁵ = 32. shift remains constant constant cache-line size. since there no other shift in example code, presume misunderstanding should do.

in set-associative cache, there multiple sets of cache-lines can used same index. instead of taking lower part of address index, take smaller part of lower address. so, index = address_of_block & (cache_size-1) should become address_of_block & ((cache_size-1) / ways. since dealing 2ⁿ number again, can use old "shift instead of divide" trick - x / y y 2ⁿ can done x >> n.

so, have figure out n number of ways.

and of course, figure out how determine of ways use when replacing in cache, different question.