Thread: Cache simulator - bit shifting

I'm attempting to make a cache simulator in C++. But I need to access individual bits in an integer to figure out where in my "cache" the writing actually gets done. I'm pretty new to bit shifting. Say I'm trying to access the the bits of the int 5, which are its "address". I'm simulating a direct mapped cache. I need to find its tag, the set it goes into, and which line. How do I use bit shifting to access the bits to aquire the tag, the index bits, offset bits, block number...all these pieces in order to actually find where I store it in the cache.
I need to break the bits up into 3 sections: tag, set index, and block index. I think I can figure out the set and block index sizes based on the values passed in. The tag bits are just the remaining ones. And I'm hard coding values such as cache size (C) - 1024, number of physical address bits (m) - 32, block size (B) - 2, number of lines per set (E) - 1 (again, directly mapped cache). How would this look? I'll be using unsigned longs, so it can handle up to 64 bits. Thank you!

"Block index", is normally called "block offset", it's the part of the address that is just passed through to select which byte within a cache row is to be used. The index is the portion of the physical address used to index into the cache. If the cache is multi-way associative, there will be multiple cache rows that have the same index, which one to use is determined by a match of the tag bits. If the cache is fully associative, there are no index bits. As you mentioned the number of tag bits is the number of physical address bits - (number of index bits + number of offset bits). In your case you only need 32 bits:

Wiki article: http://en.wikipedia.org/wiki/CPU_cache

Using the first wiki article example, you have 21 tag bits, 5 index bits, 6 offset bits. To split up a 32 bit unsigned address:

offset = (address >> 0) & ((1 << 6) -1);
index = (address >> 6) & ((1 << 5) -1);
tag = (address >> 11) & ((1 << 21) -1);

Originally Posted by rcgldr

"Block index", is normally called "block offset", it's the part of the address that is just passed through to select which byte within a cache row is to be used. The index is the portion of the physical address used to index into the cache. If the cache is multi-way associative, there will be multiple cache rows that have the same index, which one to use is determined by a match of the tag bits. If the cache is fully associative, there are no index bits. As you mentioned the number of tag bits is the number of physical address bits - (number of index bits + number of offset bits). In your case you only need 32 bits:

Wiki article: CPU cache - Wikipedia, the free encyclopedia

Using the first wiki article example, you have 21 tag bits, 5 index bits, 6 offset bits. To split up a 32 bit unsigned address:

offset = (address >> 0) & ((1 << 6) -1);
index = (address >> 6) & ((1 << 5) -1);
tag = (address >> 11) & ((1 << 21) -1);

Thank you for the response! So then what would it look like to split up a 64 bit address...I'd like my cache to be able to handle up to 64 bits using unsigned longs

Originally Posted by johngoodman

Thank you for the response! So then what would it look like to split up a 64 bit address...I'd like my cache to be able to handle up to 64 bits using unsigned longs

It would look similar, the only difference is the bit offset (the right shift part) and the number of bits in the field (the and part).