To analyze a cache-oblivious algorithm,
we're going to need a model of how a cache works.
Here's the model I want you to assume,
which we sometimes call the ideal cache model.
Start by assuming that slow and
fast memory are divided into blocks of size L words.
This L is the same as the transfer size.
We'll refer to one of these blocks in fast memory or cache as a cache line.
So you have a machine in which fast memory is being managed automatically.
Consider your algorithm or program.
As it runs, it issues sequences of load and store operations.
These loads and stores reference addresses in slow memory.
For this lesson,
let's assume that the algorithm issues these operations sequentially.
Now, consider some load operation.
Suppose it reads from an address call it a and
wants to load the value into a register, call it r.
The hardware will check to see if a copy of a is already in fast memory.
If it's there, then it returns the value and completes the store operation,
which writes to register r.
Let's refer to this case as a cache hit,
because the value that we want is in cache.
If the value we want is not in cache, then it's a cache miss.
In this case, the hardware grabs the value from slow memory, but
also stashes a copy in the cache.
Keep in mind that the hardware has to transfer an entire cache line.
Now, which L consecutive words around the address a get transferred depends
on how a is aligned.
So, what about a store from say a register s to a memory address b?
It will behave kind of like a load operation.
There's a copy of b in cache, then it's a cache hit and
we update the cached value.
Otherwise, there's no copy of b in the cache and it's a cache miss.
The hardware would load the block from slow memory into cache.
In other words, a store miss like a load miss causes a memory transfer.
So those were the basics of load and store operations.
Here's the next assumption in the ideal cache model.
Cache is fully associative.
So, what does that mean?
Remember that a cache consists of a set of cache lines or cache blocks.
Now suppose you load a new block from slow memory, full associativity means
that this block is allowed to go into any block or line of the cache.
Now you may know about set associative caches and direct-mapped caches.
If you do, then you know the real caches typically don't implement full
associativity.
Rather, they implement one of these schemes,
which has the effect of restricting the possible cache
lines that are given memory address can go into.
Full associativity says, you can ignore this restriction.
It's a simplifying assumption that will make
our ideal cache model more powerful than real cache is.
Now at some point, the cache will be full of previously used values.
To make room for new values,
the hardware will need to choose some line to kick out or to evict.
If the value being evicted hasn't been written to main memory yet, because say,
it was a store hit previously, then that will cause another memory transfer.
I'll refer to those transfers as store-evictions.
So if we have to kick something out, what do we kick out?
That leads us to the next assumption of the ideal cache model,
optimal replacement.
Optimal replacement means that the hardware managing the cache actually
knows the future.
In particular, the hardware knows all future accesses.
It looks at all the blocks currently in the cache and then
evicts the one that will be accessed the most distantly in the future.
At first glance, this might strike you as being extremely idealistic or
optimistic.
But in fact, we'll do an analysis of just how
powerful this assumption really is in a moment.
Let's do a quick summary of all the assumptions of the ideal cache model.
We'll model the program as issuing a sequence of load and
store operations to slow memory.
The hardware manages the z words of cache,
which is divided into lines of size L words each.
These Z over L cache lines are sometimes called cache blocks.
As in the conventional I/O model,
slow memory to cache transfers will happen in lines or blocks of size L.
If the value for some slow memory address is already in cache,
it's a cache hit.
And otherwise, it's a cache miss.
The cache will assume it's fully associated.
Lastly, when we need to evict a cache line,
we'll assume an optimal replacement policy.
This policy sees the future.
One final point.
Remember that in the conventional I/O model, we counted memory transfers.
In the ideal cache model, we do the same thing.
The number of transfers is really equal to the number of misses plus the number
of store-evictions.
Now I think is a good time to see,
if you really understand how an ideal cache might work.