In the previous chapter, we took a brief first look at cache memory while exploring the overall memory hierarchy, describing it as a small, extremely fast layer of memory sitting between the CPU's registers and main memory. Now it is time to explore cache memory properly, looking closely at how it actually decides what data to store, how the CPU locates that data quickly, and how cache performance is measured in practice.
Cache memory exists to solve a very specific problem: while RAM is much faster than secondary storage, it is still noticeably slower than the CPU itself. Every time the CPU has to wait for data to arrive from RAM, valuable processing time is lost. Cache memory addresses this by keeping a small copy of frequently or recently used data much closer to the CPU, dramatically reducing how often the CPU needs to wait on slower main memory.
In this tutorial, you will learn about cache hits and misses, the different levels of cache found in modern CPUs, and the three main cache mapping techniques used to organize data inside cache: direct mapping, associative mapping, and set-associative mapping.
Whenever the CPU needs a particular piece of data, it first checks whether that data is already available in cache. If the data is found in cache, this is called a cache hit, and the CPU can retrieve it extremely quickly. If the data is not found in cache, this is called a cache miss, and the CPU must retrieve the data from the slower main memory instead, usually copying it into cache at the same time for potential future use.
CS Engineering Gyan's simulated CPU repeatedly needs a subscriber count value during several calculations First access: Value is not found in cache (cache miss) Value is retrieved from RAM and copied into cache Second access: Value is now found directly in cache (cache hit), retrieved much faster than before Third access: Value is still present in cache (cache hit), again retrieved quickly
The overall goal of cache design is to maximize the number of cache hits and minimize cache misses, since every cache hit avoids the delay of reaching out to main memory.
Cache performance is commonly measured using hit ratio, which represents the proportion of memory accesses that were successfully found in cache, expressed as a value between 0 and 1, or sometimes as a percentage. The miss ratio is simply the remaining proportion of accesses that were not found in cache.
Total memory accesses: 100 Cache hits: 92 Cache misses: 8 Hit Ratio = 92 / 100 = 0.92 (or 92%) Miss Ratio = 8 / 100 = 0.08 (or 8%)
A higher hit ratio generally indicates a more effective cache design, since it means the CPU is retrieving the data it needs from fast cache memory far more often than it needs to wait on slower main memory.
Modern CPUs typically organize cache memory into multiple levels, commonly labeled L1, L2, and L3, each offering a different balance between speed, size, and proximity to the CPU core.
| Cache Level | Relative Speed | Relative Size | Typical Location |
|---|---|---|---|
| L1 Cache | Fastest | Smallest | Built directly into each CPU core |
| L2 Cache | Fast | Larger than L1 | Close to the CPU core, sometimes shared |
| L3 Cache | Slower than L1 and L2 | Largest of the three | Shared across multiple CPU cores |
When the CPU looks for data, it typically checks L1 cache first, since it is the fastest. If the data is not found there, it checks L2, and finally L3, before eventually falling back to main memory if the data is not found in any level of cache at all.
Since cache memory is much smaller than main memory, it cannot possibly hold a copy of everything stored in RAM at once. Cache mapping techniques define the specific rules used to decide exactly where in cache a particular piece of data from main memory should be placed, and how the CPU can quickly locate it again later.
In direct mapping, each block of main memory is assigned to exactly one specific, fixed location in cache, determined by a simple calculation based on the memory address. This makes direct mapping simple and fast to implement, though it does mean that two different memory blocks mapped to the same cache location cannot both be stored in cache at the same time.
Assume cache has 4 available lines (0, 1, 2, and 3) Memory block 12 maps to cache line: 12 mod 4 = 0 Memory block 16 maps to cache line: 16 mod 4 = 0 Both block 12 and block 16 map to the exact same cache line If block 12 is already stored in cache line 0, loading block 16 will replace it, since they compete for the same single location
This competition for the same cache line, when it happens repeatedly between actively used memory blocks, can reduce the effectiveness of direct-mapped cache, since data may be evicted and reloaded frequently even though the cache overall still has free space elsewhere.
In associative mapping, also called fully associative mapping, a memory block can be placed into any available cache line, rather than being restricted to one single fixed location. This offers much greater flexibility compared to direct mapping, since the cache can choose the best available location for each new block.
Memory block 12 needs to be loaded into cache Cache currently has lines 1 and 3 available Block 12 can be placed into either line 1 or line 3, whichever the cache system determines is most suitable
While associative mapping offers excellent flexibility and generally leads to fewer unnecessary evictions compared to direct mapping, it requires more complex hardware to search through every single cache line when looking for a match, since the data could potentially be located anywhere within the cache.
Set-associative mapping offers a practical middle ground between direct mapping and fully associative mapping. In this approach, cache is divided into a number of sets, each containing a small, fixed number of lines, and a memory block is restricted to one specific set, but can be placed into any available line within that particular set.
Assume cache is organized into 2 sets, each containing 2 lines (this is called 2-way set-associative mapping) Memory block 12 maps to set: 12 mod 2 = 0 Block 12 can be placed into either line within set 0, but cannot be placed anywhere in set 1 This provides more flexibility than direct mapping, while remaining simpler to search than fully associative mapping
Set-associative mapping is extremely common in real-world CPU designs, since it balances the simplicity and speed of direct mapping with much of the flexibility offered by fully associative mapping, without requiring the full complexity of searching the entire cache for every single access.
| Mapping Technique | Placement Flexibility | Search Complexity |
|---|---|---|
| Direct Mapping | Each block maps to exactly one fixed cache line | Very simple and fast to search |
| Associative Mapping | A block can be placed in any available cache line | Complex, requires searching the entire cache |
| Set-Associative Mapping | A block maps to one set, but can use any line within it | Moderate, only searches within the relevant set |
When cache is full and a new memory block needs to be loaded, especially under associative or set-associative mapping where multiple lines are available as options, the cache system must decide which existing block to remove to make room. This decision is governed by a cache replacement policy.
One of the most common replacement policies is Least Recently Used, often abbreviated as LRU, which removes whichever block in cache has gone the longest without being accessed, based on the reasonable assumption that data used a while ago is less likely to be needed again soon compared to more recently accessed data.
A cache set contains three blocks: A, B, and C Access order so far: A, B, C, A, B A new block, D, needs to be loaded, but the set is full Block C was accessed least recently among A, B, and C Using LRU, block C is removed to make room for block D
Because of locality of reference, the pattern we introduced in the previous chapter where programs repeatedly access the same small sets of data over short periods, cache memory ends up being remarkably effective in real-world use, even though it is only a small fraction of the size of main memory. A well-designed cache can achieve hit ratios well above 90 percent for many typical programs, meaning the vast majority of memory accesses are served by fast cache rather than slower RAM.
| Advantages | Limitations |
|---|---|
| Significantly reduces the average time needed to access frequently used data. | Cache is much smaller than main memory, so not all data can be stored there at once. |
| Multiple cache levels balance speed and size effectively across the CPU. | More flexible mapping techniques require more complex and expensive hardware to implement. |
| Mapping techniques and replacement policies can be tuned to improve hit ratio. | Poorly matched access patterns can still lead to frequent cache misses despite a good design. |
| Mistake | Correct Practice |
|---|---|
| Confusing a cache hit with a cache miss. | Remember that a hit means the data was found in cache, while a miss means it had to be retrieved from main memory. |
| Assuming direct mapping allows a memory block to be placed anywhere in cache. | Remember that direct mapping restricts each block to exactly one specific, fixed cache line. |
| Believing associative mapping has no drawbacks compared to direct mapping. | Understand that associative mapping requires more complex hardware to search the entire cache for a match. |
| Forgetting that set-associative mapping still restricts a block to one specific set. | Remember that only the line within that set is flexible, not the set assignment itself. |
Cache memory sits between the CPU and main memory, using the pattern of locality of reference to serve the majority of memory requests far faster than main memory alone ever could. Cache hits and misses, along with hit ratio, give us a way to measure exactly how effective a particular cache design is in practice, while multiple cache levels, L1, L2, and L3, balance speed against size across the CPU.
Mapping techniques, direct, associative, and set-associative, define the specific rules for where a memory block can be placed in cache, each offering a different trade-off between flexibility and hardware complexity, while replacement policies like LRU determine which data gets removed when cache space runs out. Together, these ideas explain how a relatively small amount of cache memory can have such an outsized impact on overall system performance.
With cache memory covered, you are now ready to explore buses in computer organization, where we will look at exactly how data physically travels between the CPU, memory, and other components across a computer system.