size of cache and calculating cache set

Question

I'm trying to understand cache basics. If I have

#define OFFSET_BITS (6)                              // 64 bytes cache line
#define SET_INDEX_BITS (5)                           // 32 sets
#define TAG_BITS (64 - OFFSET_BITS - SET_INDEX_BITS) //
#define NWAYS (8)                                    // 8 ways cache.

What is the size of cache in this machine? Is it just adding the offset, set and tag bits? Also, lets say I have an address 0x40000100, what is the cache set for the address? How do I calculate that?

Brendan Brendan · Accepted Answer · 2018-04-17T03:15:41

Assume you have an array, like this:

uint8_t myCache[1 << SET_INDEX_BITS][NWAYS][1 << OFFSET_BITS];

For NWAYS = 8, SET_INDEX_BITS = 5 and OFFSET_BITS = 6; the size of the array (the size of the cache) would be 16384 bytes (16 KiB).

Note that "cache size" only refers to how much data the cache can store, and excludes the cost of storing the tags needed to find the data.

The tags could be representing by a second array, like this:

myCacheTags[1 << SET_INDEX_BITS][NWAYS];

If one tag costs 53 bits, then 256 tags will cost 13568 bits; so to actually implement the cache you'd need a minimum of 18080 bytes. Of course in C (where you can't have an array of 53-bit integers) it'd cost a little more for padding/alignment (the array of tags would end up costing 64 bits per tag instead).

To find a cache line in the cache you'd do something like:

uint8_t *getCacheLine(uint32_t address) {
    int setIndex = (address >> OFFSET_BITS) & (( 1 << SET_INDEX_BITS) - 1);
    int myTag = address >> (OFFSET_BITS + SET_INDEX_BITS);

    for(int way = 0; way < NWAYS; way++) {
        if(myTag == myCacheTags[setIndex][way]) {
            return myCache[setIndex][way];
        }
    }
    return NULL;   // Cache miss
}

Note: Typically the tag contains some kind of "valid or invalid" flag (in case an entry in the cache contains nothing at all), and typically the tag also contains something to represent the how recently used the cache line is (for some kind of "least recently used" eviction algorithm). The example code I've provided is incomplete - it doesn't mask off these extra bits when doing if(myTag == myCacheTags[setIndex][way]), it doesn't check any valid/invalid flag, and it doesn't update the tag to indicate that the cache line was recently used.

size of cache and calculating cache set

1 Answers