A concrete explanation of how a cache works

A very concrete explanation of how a cache worksA very concrete explanation of how a cache works A hash table implemented in hardware 2019.03.30 KO | ENPrinciple of LocalityCachesCache MetricsCache OrganizationIndexingTag MatchingTag OverheadAssociative CacheSet Associative Cache OrganizationConcrete ExampleHandling Cache WritesSoftware RestructuringReferences As 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 Locality The 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.Caches A 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 Metrics When 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} Miss rateAverage access time=Cache acessesCache misses=Hit latency+Miss rate×Miss latency 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 Organization A 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)O(1).A cache is made up of blocks. Each block holds data and can be...

A concrete explanation of how a cache works

Related Articles

(no title)

Scientists reverse brain aging, with a nasal spray

AI has torched the market for junior programmers

Al Vigier: Canada's AI strategy shouldn't include secret Palantir bills

The Anatomy of an AI-Native Org