We looked last time at how our code will perform better if we capitalize on temporal and spatial locality. Sadly, we cannot avoid misses altogether. Caches are finite storage, and their designers must decide where blocks from memory will go in the cache and how long they will stay there. As you’ve done an assignment on caching in CS 252, I don’t want to spend a lot of time re-enumerating these various strategies. We will describe their operation in pseudocode, and then do a little physical simulation.
First up is the fully associative cache, which places blocks from memory anywhere there’s room:
blockID = address / blockSize for each block in blocks if block.tag == blockID return block[address % blockSize] # A hit! :) # A miss. :( if cache is full kick out the least-recently-used block retrieve block from memory place it in random empty slot return block[address % blockSize]
Next is the direct-mapped cache, where each block from memory has a very specific home in the cache:
blockID = address / blockSize slot = blockID % nBlocks if blocks[slot].tag != blockID blocks[slot] = retrieve block from memory return blocks[slot][address % blockSize]
Finally we have the n-way set associative cache, where each block from memory falls into a very specific window of the cache:
blockID = address / blockSize set = blockID % nSets for each block in set if block.tag == blockID return block[address % blockSize] # A hit! :) # A miss. :( if set is full kick out the least-recently-used block retrieve block from memory place it in random empty slot within set return block[address % blockSize]
This last strategy is a generalization of the first two. A fully-associative cache is one with just one set holding all the blocks. A direct-mapped cache is one where each set holds just one block.
For the remainder of our time today, we will do a little exercise where I (call me Processor Chris) request reads of a certain byte from memory. Your classmates will serve as cache lines that hang on the blocks holding the requested data. As I continue to make read requests, it will your job to deduce what sort of caching strategy is at work. You can choose from four:
Here’s your TODO list for next time:
See you next class!