Caches

For main memory, we use dynamic random-access memory (DRAM). The latency to access first words is moderately fast (~30-40 processor cycles). However, data is impermanent: capacitors are used to store bits, so when power is removed, we lose data.

Contrast with static random-access memory (SRAM), used for caches. It is still volatile, but faster and more expensive.

Secondary memory (or disk) is attached as a peripheral I/O device and is non-volatile. Solid-state drives (SSD) and hard disk drives (HDD) are the most common types. Access to this memory is very slow (~40-100us for SSD, which is ~100k processor cycles), but they are also very cheap.

As a general rule of thumb, the runtime cost of operations are as follows:

• File operations are extremely slow since they must read/write from the disk
• Memory operations are ~100x faster than file operations since they use RAM
• Branches and jumps take ~5 cycles due to control hazards
• Arithmetic operations are the fastest, taking ideally 1 cycle

We can use a library analogy to represent the memory hierarchy. We can think of retrieving memory as finding a book in a large library: the time taken involves the time we need to walk to the library, find the desired information, and walk back. Additionally, larger libraries worsen this delay.

If registers are what you store in your brain, then proportionally:

• Main memory is a library on campus
• Disk memory is a library in Los Angeles
• Tape memory is a library on the moon

To speed up memory access, we can use caches. Using the library analogy, instead of going to the library each time to retrieve information, we can borrow some books to store at home. The idea is that if you use a book once, chances are you will use it again. If we need another book, we borrow another one without returning earlier books until your bookshelf is too full to carry more books.

Caches are faster but more expensive than DRAM. They are often placed close to or on the same chip as the processor, since we want fast access times.

The hit rate of a cache is the percentage of accesses that result in a hit. The miss rate of a cache is the percentage of accesses that result in a miss. Hit time is how long it takes to check the cache, and the miss penalty is how long it takes to access main memory. Thus, if we get a cache miss, the total runtime is equal to the hit time plus the miss penalty. The average memory access time (AMAT) is the average time it takes for one memory access, given a hit rate.

Caching is only useful if you can predict what memory a program will access soon. If a program uses completely random memory accesses, caches are guaranteed (on average) to slow down access times! Thus, can we predict future memory accesses given the most recent memory accesses?

A fully associative cache is parametrized on two aspects: the block size, and the number of blocks that can be stored in the cache. When a memory access occurs:

1. Check if the cache contains the data, and if so, return the data.
2. If the data is not present in the cache, load the block of memory into the cache.
3. Return the data.

A fully associative cache stores cache tags that identify which block of memory is stored, a 1-bit bit that differentiates actual data from garbage, and the actual cache data. To find data in the cache, we check if a line with a matching tag exists with the valid bit set to 1, and then access the corresponding data with our offset:

When reading memory, 3 things can happen:

• cache hit: cache block is valid and contains proper address
• cache miss: cannot find valid block in cache, so fetch from memory and replace an invalid block
• cache miss with eviction: cache miss, but cache is full, so we need to remove a block from the cache

A cache is considered cold if it doesn’t have valid data in it, and hot if it has valid data with a high ratio of cache hits.

While nice, an actual implementation of a fully associative cache is complicated and requires a lot of circuitry. The main problem is that any slot in our cache could store our data, so we need to check all spots.

Our solution to this is to group blocks together. In a direct-mapped cache, we store one block per group: so if we need to store another block of that group, we must first evict the previous block. We will group by the bottom three bits of a tag, as this gives us a pretty even distribution (since memory is often located in consecutive locations).

A memory address can be divided into a tag, and index, and an offset. The bottom bits of our address is our offset, the next few bits the index, and the top bits will be the tag. The index determines which group the block goes into, the offset determines which byte we are pointing to in the block, and the tag determines if the block stored in the group is the one we want.

Notice that we do not need an eviction policy since there is only one place our block can go.

Direct-mapped caches thrash a lot, but fully associative caches use a lot of comparators. To solve this, we can make a compromise by using a N-way set associative cache.

A set-associative cache can be thought of as a set of multiple direct-mapped caches. In other words, blocks are still grouped together, and we still find the group using the index, but there can be multiple blocks with the same index. This solves a lot of thrashing issues because even if two segments of memory have the same index, we can store both of them in our cache.

When we write data to memory, we have two policies that we can use to govern the write:

• Write-through: when a write occurs, update the data both in the cache and in main memory.
• Write-back: when a write occurs, only update the data in the cache, and update in memory only when that block gets evicted.

The write-back policy is much faster than write-through, but it is also more complicated. We purposefully let main memory go stale, and rely on the cache as the main source of truth. When we later evict the block from the cache, we write all changes for that block to main memory at once. This means we need to keep track of which blocks changed in the cache using a dirty bit.

With one cache, if we get a cache hit, then we get fast access; if we get a cache miss, we get slow access. The problem is that hit rate scales with access time: the higher the hit rate we want, the slower we’ll end up making cache accesses (e.g. larger cache means more places to search).

A solution is to add multiple layers of caches, with each layer being larger than the last. When we check caches, we first check the L1 cache, otherwise check L2 cache, and so on. Each level of cache is larger than the previous level and should have a subset of its data in the next cache: a hit in L3 cache causes the data to brought up to both the L1 and L2 caches.