A very concrete explanation of how a cache works

A hash table implemented in hardware 2019.03.30KO | ENPrinciple of LocalityCachesCache MetricsCache OrganizationIndexingTag MatchingTag OverheadAssociative CacheSet Associative Cache OrganizationConcrete ExampleHandling Cache WritesSoftware RestructuringReferencesAs technology has advanced, processor speed has risen quickly, but memory speed hasn’t kept up. No matter how fast a processor is, if memory responds slowly the whole system ends up slow. The device that addresses this is the cache.A cache is a small, fast memory that sits inside the CPU chip. (It’s also expensive.) Going to main memory for data every time is slow, so the cache holds frequently used data and lets the processor reach that data from the cache instead of main memory, which speeds things up.Principle of LocalityThe judgment about which data is “frequently used” follows the principle of locality, which can be split into temporal locality and spatial locality.Temporal locality is the tendency to access recently accessed data again. For example, the variable i that serves as the index in a loop is accessed several times within a short span.for (i = 0; i < 10; i += 1) { arr[i] = i; }Spatial locality is the tendency to access the space near recently accessed data again. In the loop above, as it references each element of the array arr, it accesses nearby memory locations one after another. That’s because an array’s elements are allocated consecutively in memory.Even within a single process, some parts are used often and others aren’t, so the operating system manages a process by dividing it into units called pages, and the figure above is a trace of page references. The horizontal axis is execution time, and the vertical axis is the memory address. A horizontal run of references means the same memory address was referenced over a long stretch of time, while a vertical run means closely spaced memory addresses were referenced at the same time. You can see that the principle of locality applies to page access too.

CachesA CPU chip contains several caches, and each one has its own purpose and role.+-------------+------+------+ +---------------+ +--------+ | | I$ | | <-- | | <-- | | + Processor +------+ L2 | | Main Memory | | Disk | | | D$ | | --> | | --> | | +-------------+------+------+ +---------------+ +--------+L1 Cache: The cache closest to the processor. For speed, it’s split into I$ and D$. Instruction Cache (I$): The cache that handles data in the memory’s TEXT segment.Data Cache (D$): The cache that handles all data except the TEXT segment.L2 Cache: A larger-capacity cache. For the sake of size, it isn’t split the way the L1 cache is.L3 Cache: The cache shared by multiple cores in a multi-core system.Today, caches take up 30 to 70% of a CPU chip’s area. The i486, a single-core processor made in 1989, had just one 8KB I/D cache. The die map of the Intel Core i7 quad-core chip, on the other hand, shows that each of the four cores has its own 256KB L2 cache, plus an 8MB L3 cache shared by all the cores. (The region above the L2 cache looks like the L1 cache, but I wasn’t sure, so I didn’t label it.)Cache MetricsWhen measuring a cache’s performance, hit latency and miss latency are considered important factors.When the data the CPU requests is in the cache, that’s a cache hit. Hit latency is the time it takes to fetch the cached data on a hit. When the requested data isn’t in the cache, that’s a cache miss, and miss latency is the time it takes to fetch the data from a higher-level cache (for example, when the data isn’t in the L1 cache and is looked up in the L2 cache) or from memory on a miss.

Average access time is calculated as follows:Miss rate=Cache missesCache acessesAverage access time=Hit latency+Miss rate×Miss latency \begin{aligned} \text{Miss rate} &= {\text{Cache misses} \over \text{Cache acesses}} \\ \text{Average access time} &= \text{Hit latency} + \text{Miss rate} \times \text{Miss latency} \end{aligned} To improve a cache’s performance, you can shrink the cache to reduce hit latency, enlarge the cache to reduce the miss rate, or use a faster cache to reduce latency.Cache OrganizationA cache is made of fast-responding SRAM (Static Random Access Memory); given an address as a key, it can access the corresponding location immediately. DRAM (Dynamic Random Access Memory) has this same property, but by hardware design DRAM is slower than SRAM. When people say “main memory,” they usually mean DRAM.Being able to access a location immediately when given an address as a key means a cache is essentially a hash table implemented in hardware. A cache is fast partly because it holds only frequently used data, but also because a hash table’s time complexity is fast, on the order of O(1)O(1).A cache is made up of blocks. Each block holds data and can be accessed using an address as a key. The number of blocks and the block size determine the cache’s size.IndexingRather than using the entire address as the key, only part of it is used. For example, with 1,024 blocks and a block size of 32 bytes, a 32-bit address can be indexed as follows.Here, the low 5 bits of the full address are used as the offset, and the next 10 bits are used as the index to access a block. The index is 10 bits because representing every index of 2n2^n blocks requires log2blockslog{_2}\text{blocks} bits. Since there are 210=10242^{10} = 1024 blocks here, log21024=10log{_2} 1024 = 10, so 10 bits are used as index bits. (

I’ll explain the offset bits below.)But doing only this leaves too great a risk that different pieces of data will share the same index.Tag MatchingTo reduce index collisions, part of the address is used as a tag. Suppose there are 1,024 blocks, a block size of 32 bytes, and we access the 32-bit address 0x000c14B8:First, access the field of the tag array that corresponds to the index (0010100101).Next, check the valid bit of that tag field.If the valid bit is 1, compare whether the tag field (00000000000011000) and the address’s tag (00000000000011000) are equal.AND the comparison result (true, 1) with the valid bit (1).A valid bit of 1 means a correct value exists in that block. The tag field and the address’s tag match, and the valid bit is 1, so the result of the example above is a hit. On a hit, the data at that index is referenced from the data array. (For reference, the data array and the tag array are both hardware too.)If the valid bit is 0, it means the block has no value or an invalid one, so a miss occurs. In that case, the address’s tag is written into the tag field, the value requested from a higher-level cache or memory is fetched and written into the data field, and the valid bit is changed to 1.Even if the valid bit is 1, a miss occurs when the tag doesn’t match. In that case, how it’s handled depends on the replacement policy. If you use the FIFO (First-In First-Out) policy, where the data that came in first is replaced first, the existing block is always replaced. The tag array’s field is changed to the address’s tag, and the data requested from a higher-level cache or memory is fetched to replace the value in the data field with the new data. (In practice, not only the requested data but also the data around it is fetched.) The existing data is pushed up to the higher-level cache.

The reason the upper 15 bits of the address are used as tag bits is that the number of tag bits is determined by Address bits−(log2Block size+Index bits)\text{Address bits} - (\log{_2}\text{Block size} + \text{Index bits}). In this case, 32−(5+10)=1732 - (5 + 10) = 17 bits are used as tag bits, and the remaining 5 bits are used as offset bits.Tag OverheadAdding the tag array means more space is needed. But a “32KB cache” still means a cache that can store 32KB of data. That’s because the space for tags is treated as overhead, independent of the block size.Let’s work out the tag overhead of a 32KB cache made up of 1,024 32B blocks:17bit tag+1bit valid=18bit18bit×1024=18Kb tags=2.25KB \begin{aligned} 17 \text{bit tag} + 1 \text{bit valid} &= 18 \text{bit} \\ 18 \text{bit} \times 1024 = 18 \text{Kb tags} &= 2.25 \text{KB} \end{aligned} In other words, a tag overhead of 7% arises.There’s a time cost as well as a space cost. Because you access the tag array to check for a hit and only then access the data array to fetch the data, hit latency ends up increasing.So the two steps are run in parallel: while the tag array is being checked for a hit, the data array is accessed ahead of time. This reduces hit latency, but you have to accept the wasted resources when a miss occurs.Associative CacheWhen two different addresses have the same index, a collision occurs, and a block is replaced according to the replacement policy. But changing the cache’s contents on every collision leads to more misses and can cause the ping-pong problem, where the contents of a single slot are swapped out endlessly.This problem can be improved by creating multiple tag arrays and data arrays. In other words, the index ends up pointing to several blocks.