Understanding CPU Cache: Levels and Cache Lines

1. The Need for Speed: SRAM vs. DRAM

To understand why caches are necessary, we first need to look at the fundamental physics and economics of computer memory. Why don't we just build computers with terabytes of memory that runs at the CPU's clock speed? The answer lies in a fundamental trade-off between speed, density, and cost.

Modern computers use two primary types of volatile memory:

• Static RAM (SRAM): This memory is built from a circuit called a flip-flop, which uses multiple transistors (typically six) to store a single bit. It doesn't need to be refreshed and holds its data as long as it has power. It is extremely fast, with access times on the order of a few CPU cycles. However, it is complex, consumes more power, and is less dense, making it very expensive per byte.
• Dynamic RAM (DRAM): This is the memory you know as "RAM" in your PC or laptop. It stores a bit using a single transistor and a tiny capacitor. This simple design makes it very dense and cheap. The downside is that the capacitor leaks its charge over time and must be constantly refreshed thousands of times per second. This refresh cycle, along with the analog nature of reading the charge, makes DRAM significantly slower than SRAM.

Let's watch a video that explains the physical differences between these two memory types. This knowledge from first principles is key to understanding why the memory hierarchy is designed the way it is.

The stark difference in these technologies forces a compromise. We use a small amount of expensive, fast SRAM for caches and a large amount of cheaper, slower DRAM for main memory. The cache then acts as a high-speed intermediary.

2. The Memory Hierarchy: L1, L2, and L3 Caches

Instead of a single cache, modern CPUs employ a multi-level cache hierarchy to balance the trade-offs between speed and size. This hierarchy typically consists of three levels: L1, L2, and L3. When the CPU needs a piece of data, it looks for it in this hierarchy, starting with the fastest and closest level.

Each level of the cache represents a different point in the speed-versus-size trade-off:

• L1 Cache: This is the smallest and fastest cache, located right on the CPU core itself. Its latency is extremely low, often just a few clock cycles. Because programs consist of both instructions and data, the L1 cache is usually split into two parts: an Instruction Cache (I-Cache) to feed the pipeline's fetch stage and a Data Cache (D-Cache) for load/store operations. The L1 cache is private to each CPU core.
• L2 Cache: Larger and slightly slower than L1. In modern CPUs, L2 caches are also typically private to each core. It acts as a backup for the L1 cache.
• L3 Cache: This is the largest and slowest of the caches. It is shared among all the cores on the CPU chip and is often called the Last-Level Cache (LLC). It serves as a large, shared buffer that helps reduce traffic to the very slow main memory, which is especially important in multi-core systems where different cores might need to access the same data.

The following table summarizes the typical characteristics of these cache levels.

To make these differences concrete, let's watch a segment from a classic talk by performance expert Scott Meyers. He provides real-world numbers for the size and latency of each level, which powerfully illustrates the massive performance penalty of a cache miss that has to go all the way to main memory.

The takeaway is clear: from a performance perspective, hitting in the L1 cache is ideal. Hitting in L2 or L3 is acceptable. Going to main memory is a performance disaster. The entire goal of cache-aware programming is to maximize the number of times the CPU finds what it needs in the caches—a cache hit—and minimize the number of times it has to go to main memory—a cache miss.

3. The Cache Line: The Fundamental Unit of Transfer

We've established the different levels of the cache, but how is data actually moved into them? A crucial insight is that memory is not moved byte by byte. Instead, the cache and main memory communicate in fixed-size chunks called cache lines.

A cache line is a contiguous block of memory, typically 64 bytes on modern x86 processors. When the CPU requests a single byte of data from an address that is not in the cache, it doesn't just fetch that one byte from RAM. The memory controller fetches the entire 64-byte cache line that contains the requested byte and places it into the cache.

This "all or nothing" transfer has profound implications for performance. If your program accesses one piece of data, it gets the data located next to it in memory for "free." This hardware behavior is designed to exploit a principle called spatial locality, which we will explore in the next lesson.

Let's revisit Scott Meyers' talk, where he uses this exact concept to explain why one of the two matrix traversal methods he introduced at the beginning is so much faster than the other.

This example is a perfect illustration of a core principle in high-performance computing: arranging your data and access patterns to align with the underlying hardware is critical for performance.

4. How Data is Found: A Glimpse into Cache Organization

To solidify your understanding of cache lines, it's helpful to have a basic mental model of how the CPU finds data within the cache. You can think of a cache as being structured like a hash map. A memory address is used as the "key" to quickly locate the data.

To do this, the CPU breaks a memory address into three parts:

1. Offset: The last few bits of the address specify the location of the desired byte within a cache line. For a 64-byte cache line, you need 6 bits to address any of the 64 bytes ($2^6=64$).
2. Index: The next set of bits are used to select which "bucket" or set in the cache this memory address maps to. If a cache has 256 sets, it would use 8 bits for the index ($2^8=256$).
3. Tag: The remaining, most significant bits of the address are stored along with the data in the cache line. When the CPU looks in a set, it compares the tag from the address with the tags of all the cache lines stored in that set. If a tag matches, it's a cache hit.

This Tag-Index-Offset structure allows the CPU to very quickly narrow down the search for a piece of data from the entire cache to just a small set of cache lines, enabling the low-latency access that makes caches effective.

Conclusion

In this lesson, we have drilled down into the solution for the great speed disparity between the CPU and main memory. We've seen that the memory system is not a single, monolithic block but a carefully designed hierarchy.

Key Takeaways:

• CPU caches exist to bridge the enormous speed gap between the fast CPU (built from SRAM) and slow main memory (built from DRAM).
• The memory hierarchy consists of multiple levels of cache (L1, L2, L3), each offering a trade-off between speed, size, and cost. L1 is the smallest and fastest, while L3 is the largest and slowest of the caches.
• Data is not moved between memory and caches byte by byte. Instead, it is transferred in fixed-size blocks called cache lines (typically 64 bytes).
• When the CPU requests one byte, the entire cache line containing it is loaded into the cache. This has a massive impact on performance.
• A memory address is broken down into Tag, Index, and Offset bits to efficiently locate data within the cache's structure.

We have now established the fundamental components and structure of the CPU cache system. The obvious next question is: how can we write code that takes advantage of this structure? In our next lesson, we will answer that by exploring the principles of spatial and temporal locality and analyzing how different data access patterns can either lead to exceptional performance through high cache hit rates or disastrous performance by constantly causing cache misses.