Cache Hierarchy: L1, L2, L3 Explained

The CPU-Memory Performance Gap

Modern CPUs can execute instructions in a fraction of a nanosecond. However, accessing data from main memory (DRAM) is orders of magnitude slower. This gap is often called the "memory wall." If the CPU had to wait for main memory for every single data access, its incredible processing speed would be wasted.

The solution is the memory hierarchy, a tiered system of memory components where each level is smaller, faster, and more expensive per byte than the level below it.

Caches are small, extremely fast memory buffers made of SRAM (Static RAM), which are placed between the CPU and the much slower DRAM (Dynamic RAM) that constitutes main memory.

To understand the technological difference, let's briefly look at the resource below.

The key takeaway is that SRAM's design makes it much faster than DRAM but also less dense and more expensive. This is why we can't just build a massive main memory out of SRAM; instead, we use a small amount of it strategically as a cache.

The Cache Hierarchy: L1, L2, and L3

Modern processors don't have just one cache; they have a multi-level hierarchy. Let's watch a short video that introduces this concept.

As the video explains, the hierarchy is typically organized as follows:

• L1 Cache: This is the fastest and smallest cache, located right on the CPU core. It is always a per-core resource. It's often split into two parts:
  • L1i (Instruction Cache): Caches the machine code instructions the CPU is executing.
  • L1d (Data Cache): Caches the data the program is operating on.
• L2 Cache: Larger and slightly slower than L1. In modern multi-core CPUs, L2 caches are also typically private to each core.
• L3 Cache: The largest and slowest of the on-chip caches. It is usually shared among all cores on the CPU die. It serves as a common backstop for misses in the L1 and L2 caches of multiple cores.

This per-core vs. shared distinction is crucial in multi-core programming, a topic we'll revisit when discussing cache coherency.

To see what this looks like on a real system, the article "Demystifying CPU Caches with Examples" shows how to use getconf on Linux to inspect your own CPU's cache configuration.

The Building Blocks: Cache Lines

When the CPU requests a single byte of data from main memory that isn't in the cache (a cache miss), the memory controller doesn't just fetch that one byte. It fetches a contiguous block of memory containing the requested byte. This block is called a cache line (or cache block).

A typical cache line size is 64 bytes.

This behavior is based on the principle of spatial locality: if a program accesses a particular memory location, it is highly likely to access nearby memory locations soon. By fetching an entire cache line, the cache pre-loads data the CPU will probably need next, turning what would have been multiple slow main memory accesses into fast cache hits.

The performance impact of this is enormous. The "Demystifying CPU Caches" article you just looked at has an excellent code example demonstrating this. By changing the access pattern from contiguous (hitting the same cache line 16 times in a row for 4-byte integers) to a stride of 16 (forcing a new cache line fetch for every access), the execution time increases dramatically. This is a classic interview-style question that tests your practical understanding of cache behavior.

Organization and Mapping: Sets, Ways, and Associativity

So, we have a cache full of 64-byte lines. When a new line is fetched from main memory, where does it go in the cache? And when the CPU needs data, how does it find the right line? This is determined by the cache's mapping policy.

There are three main types of mapping:

1. Direct-Mapped: Each block of main memory can only be mapped to one specific location in the cache. This is simple and fast but can lead to "conflict misses" where two frequently used memory blocks map to the same cache slot, constantly evicting each other.
2. Fully Associative: A block from main memory can be placed in any line in the cache. This is the most flexible and avoids conflict misses but is extremely expensive and power-hungry to implement because it requires comparing the address tag with every single line in the cache simultaneously.
3. N-Way Set-Associative: This is the practical compromise used in virtually all modern CPUs. The cache is divided into groups of lines called sets. A block from main memory maps to a specific set, but it can be placed in any of the N available slots (called ways) within that set.

An 8-way set-associative cache means each set contains 8 lines (ways).

Let's watch a video that explains these concepts visually.

Address Breakdown

As the video showed, the cache hardware interprets a memory address by splitting it into three pieces:

• Block Offset: The lower bits of the address that identify the specific byte within a cache line. For a 64-byte line, you need 6 bits ($2^6=64$) for the offset.
• Set Index: The next set of bits that determines which set the memory address maps to. If a cache has 64 sets, you need 6 bits ($2^6=64$) for the index.
• Tag: The remaining upper bits of the address. This tag is stored alongside the data in the cache line. It's used to distinguish between different memory blocks that could map to the same set.

A Worked Example

To solidify your understanding, we'll walk through a numerical problem, which is a common format for interview questions on this topic.

This walkthrough perfectly illustrates how associativity reduces conflict misses. In the example, when block 4 needs to be loaded, which maps to Set 0, it doesn't have to evict block 0 because another "way" (line 1) is available in that set.

To see how these concepts manifest in real-world processors, here are the configurations for the ARM and Intel CPUs discussed in the syllabus.

You can see that higher associativity (more ways) is common, especially in higher-level caches, to reduce the miss rate.

Conclusion

In this lesson, we've moved from the abstract idea of "fast memory" to a concrete model of how a modern CPU cache system is structured. Understanding this is the first step to writing high-performance code and acing system architecture interviews.

Key Takeaways:

• Caches exist to bridge the enormous performance gap between the CPU and main memory, using a hierarchy of small, fast SRAM to store frequently used data.
• The hierarchy consists of L1, L2, and L3 caches, which are progressively larger, slower, and have a higher degree of sharing between CPU cores.
• The cache line (e.g., 64 bytes) is the fundamental unit of transfer, exploiting spatial locality.
• N-Way Set-Associative mapping is the dominant cache organization, providing a balance between implementation cost and performance.
• A memory address is divided into a Tag, Set Index, and Block Offset to locate data in the cache. The number of ways (N) is the associativity, and it determines the flexibility of placing data within a set.

Preview of the Next Lesson:
Now that we understand the basic structure of a cache, what happens in a multi-core system when one core modifies data in its private cache that another core also has a copy of? This leads to the critical problem of cache coherency. Our next lesson will be: Analyze cache coherency issues in DMA and multi-core contexts, explaining why cache flush/invalidation is required.