teaching machines

CS 352 Lecture 35 – Caching Strategies

December 7, 2016 by . Filed under cs352, fall 2016, lectures.

Dear students,

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:

  1. fully-associative
  2. direct-mapped
  3. 2-way set associative
  4. 4-way set associative

Here’s your TODO list for next time:

See you next class!

Sincerely,