Memory Hierarchy & Caching

The Processor-Memory Performance Gap

In the last lesson's simplified model, fetching from memory seemed like just another step. In reality, it's an incredibly slow one from the CPU's perspective. The speed of processors has increased at an exponential rate over the last few decades, far outpacing the speed improvements in standard main memory (DRAM). This creates what is known as the processor-memory performance gap.

Let's put some numbers to this.

As you can see, a register access is a sub-nanosecond operation, completing within a single clock cycle. An access to main memory (DRAM), however, can take 50-100 nanoseconds. For a modern 3 GHz processor, that's a delay of 150-300 clock cycles! During that time, the CPU could have executed hundreds of instructions. It's like a master chef who can chop vegetables in a fraction of a second but has to wait several minutes for an assistant to bring an ingredient from the pantry. This waiting is called a stall, and it's a huge waste of processing power.

The Solution: A Hierarchy of Memories

If we can't make the main pantry faster, maybe we can place a small, super-fast pantry right next to the chef's station. This is precisely the idea behind the memory hierarchy. Instead of a single, large block of memory, computers use a layered pyramid of memory technologies, each with a different balance of speed, size, and cost.

The video below introduces this concept and uses a great analogy to build intuition.

Let's formalize the structure you saw in the video.

The key trade-offs are:

• Speed vs. Size: Faster memory technologies (like SRAM used in caches) are more complex and take up more physical space per bit than slower technologies (like DRAM used in main memory). This makes it impractical to build a huge main memory out of the fastest technology.
• Cost: Directly related to the above, the cost per gigabyte of storage plummets as you go down the pyramid. A gigabyte of register memory would be astronomically expensive compared to a gigabyte on a hard disk.

This hierarchical structure creates the illusion of a large, fast memory. The vast majority of the time, the CPU finds what it needs in the fast upper levels, enjoying near-register speeds, even though most of the system's data resides in the slower, larger levels below. But why does this illusion work?

Why the Hierarchy Works: The Principle of Locality

The memory hierarchy is effective for one simple reason: programs are not random. They exhibit a predictable property known as the principle of locality of reference. This principle has two main forms.

The following video and PDF lecture notes define these two forms of locality.

To summarize:

1. Temporal Locality (Locality in Time): If a program accesses a memory location, it is very likely to access that same location again soon.

   • Example: A variable inside a loop, like a counter or a sum. It's accessed in every iteration.

2. Spatial Locality (Locality in Space): If a program accesses a memory location, it is very likely to access memory locations nearby soon.

   • Example: Iterating through an array in C. a[0], a[1], a[2], ... are all stored contiguously in memory.

The memory hierarchy is built entirely to exploit this predictable behavior.

Caching in Action: Hits, Misses, and Blocks

The mechanism that exploits locality is caching. Caching is the process of storing a copy of data from a slower, larger memory level into a faster, smaller one. The smaller, faster memory is called the cache.

Here’s how it works:

1. The CPU requests data from a memory address.
2. The system first checks the fastest cache (L1).
3. If the data is found in the cache, it's a cache hit. The data is delivered to the CPU at high speed.
4. If the data is not in the cache, it's a cache miss. The system then checks the next level down (L2 cache). If it's a miss there, it checks L3, and so on, until the data is found (eventually in main memory or on disk).
5. When the data is located in a slower level (e.g., RAM), a block of memory around the requested data is copied into the cache. This block is called a cache line (typically 64 bytes on modern systems).

This process directly leverages locality:

• By loading an entire cache line instead of just the single byte requested, the system exploits spatial locality. The odds are high that the program will soon need the adjacent data, which has now been pre-loaded into the fast cache.
• By keeping recently accessed cache lines in the cache, the system exploits temporal locality. The next time the program needs that same data, it will result in a fast cache hit.

A Deeper Look: Why Misses Happen

As an aspiring OS developer, it's useful to know that not all misses are the same. Understanding why a miss occurred is key to performance analysis. Cache misses are generally categorized into three types, often called the "3 Cs".

Here is a summary of the three types of cache misses:

• Compulsory Miss: The very first time a memory location is accessed. The data must be fetched from main memory because it has never been in the cache before. These are unavoidable.
• Capacity Miss: The miss occurs because the cache is not large enough to hold all the data the program is actively using. A piece of data was in the cache, but it was evicted to make room for something else, and now the program needs it again.
• Conflict Miss: The miss occurs even though there is empty space in the cache. Due to the way memory addresses are mapped to cache lines, the requested data conflicts with another piece of data for the same spot in the cache, forcing an eviction. We will explore cache mapping strategies in more detail later in your journey, but it's good to be aware of this category now.

Practical Impact: Locality and Code Performance

This isn't just abstract theory. The way you structure your code, especially loops in C, can have a dramatic impact on its locality and, therefore, its performance.

Consider traversing a 2D array in C, which stores its elements in "row-major" order. This means a[0][0] is followed in memory by a[0][1], a[0][2], etc., and then a[1][0], a[1][1], and so on.

int a[1000][1000];

// Good spatial locality
for (int i = 0; i < 1000; i++) {
    for (int j = 0; j < 1000; j++) {
        sum += a[i][j]; // Accesses memory sequentially
    }
}

// Poor spatial locality
for (int j = 0; j < 1000; j++) {
    for (int i = 0; i < 1000; i++) {
        sum += a[i][j]; // Jumps through memory
    }
}

In the first loop, each access to a[i][j] is immediately followed by an access to its memory neighbor, a[i][j+1]. When a[i][0] causes a cache miss, the cache line loaded will likely contain a[i][1] through a[i][15] (assuming a 64-byte line and 4-byte integers). The next 15 accesses will be lightning-fast cache hits.

In the second loop, the program accesses a[0][0], then a[1][0], then a[2][0]. These elements are far apart in memory (1000 integers apart). Each access is likely to cause a new cache miss, fetching a cache line that contains data the program won't use until much later. This is called having a large "stride" and it thrashes the cache, leading to poor performance.

The lecture notes you read earlier have a similar example. Thinking about memory access patterns is a critical skill for low-level programming.

Conclusion

In this lesson, we have explored the critical concept of the memory hierarchy and why it is fundamental to modern computer performance.

• Key Takeaways:
  • There is a massive performance gap between the CPU and main memory.
  • The memory hierarchy bridges this gap by layering memory types with different speed, size, and cost trade-offs.
  • The hierarchy is effective because of the principle of locality: programs tend to reuse data and instructions they have recently used (temporal locality) and access data near what they just accessed (spatial locality).
  • Caching exploits locality by storing recently used memory blocks (cache lines) in faster, smaller memories. Accessing data in the cache is a fast hit; failing to find it is a slow miss.
  • Writing code with good locality is essential for high performance.

You now understand that not all memory accesses are equal. As we move forward in building our OS, you'll see how the kernel itself must be carefully managed with respect to the memory hierarchy to ensure the whole system runs efficiently.

In our next lesson, we will shift our focus from the CPU's communication with memory to its communication with the outside world. We'll explore how the CPU talks to peripheral devices like keyboards, timers, and disk controllers using Port-Mapped and Memory-Mapped I/O.