Caches and Memory Hierarchy

Memory hierarchy introduction

Unfortunately, there isn’t a perfect memory device. So, we need to construct a system with multiple different memory devices to try to get the best of all possible devices!

Basic caching

Combining memory technologies into a single system

This video talks about how to combine multiple memory technologies in to a memory hierarchy. First, we look at a strawman example of what would happen if you just put some data in fast memory and other data in slow memory. Spoiler alert: it’s not very good.

Locality and caching

So, instead of naively putting data in fast vs slow memory, we can do much better if we take advantage of locality. First, we’ll look at temporal locality (i.e., when we use the same data multiple times). Then, we’ll look at spatial locality (i.e., when we use data nearby).

This video introduces caches and talks about different kinds of caches.

This video talks about different blocks sizes to take advantage of spatial locality.

Cache performance

Now that we’ve seen a bit about cache design, the next question is “how do we measure a cache’s performance?” This video introduces measuring cache performance with hit ratio and average memory access time or AMAT.

Memory hierarchy

To motivate a memory hierarchy, this video goes over another AMAT example.

This video talks about how a multi-level hierarchy can improve cache performance.

Cache design

Now that we’ve talked about cache performance and how caches fit into the broader memory system, let’s dig into how to design a cache.

To motivate cache design, we will be answering three questions.

1. How do we find data for a given address?
2. What do we do when there isn’t enough room in the cache (or, which data should we replace)?
3. What happens when we want to write data?

The next sections will discuss each of these questions in detail.

Direct-mapped caches

First, we’ll look at a “simple” direct-mapped cache. After understanding this, we can dive into more realistic cache designs.

This video introduces direct-mapped caches and starts to answer the question “How do we find data for a given address?”

This video talks about how to take an address and figure out where in the cache to look for the data.

This video goes deeper into the hardware design of direct-mapped caches and begins to motivate set associativity.

Set-associative caches

There are major problems with direct-mapped caches. Specifically, many addresses conflict for the same index in the cache. But! We have set-associative caches coming to the rescue!

This video goes into detail of how to design a set-associative cache and how to figure out where to look in a set-associative cache for data given an address.

This video talks about the area and power overheads of set-associative caches.

Replacement policies

Now, onto the next question: Which data should we replace?

This video introduces some replacement policies and some tradeoffs when trying to choose a replacement policy for a cache.

Write-back policies

And our final question: What happens when we want to write data?

This video discusses what happens when we try to write data to a cache and different write-back policies.

Summary of caches

This final video discusses the three C’s of cache misses.

---