CPU Caches, My learnings from “What Every Programmer Should Know About Memory”
Welcome to the world of CPU Caches !
Once upon a time the frequency of the CPU core was equivalent to that of memory bus. memory access was only a bit slower than register access. Times have changed, CPU designers have increased its frequency. It is not the fact that faster RAM could not be built, but will it be economically viable is a question to ponder!
If we could place a smaller, very fast RAM (SRAM) as intermediate storage between the CPU and main memory (DRAM) and intelligently take temporary copies (i.e. cache) of data in main memory that will soon be used, would result in significantly greater performance.
Well, It turns out it is possible because program code and data has temporal and spatial locality.
Before moving ahead let’s demystify these two pieces of jargon.
- Temporal locality: If a code or data even if not close together is accessed there is a high chance it will be reused before long. for example, in a loop a function call is made and the function is located elsewhere in the memory, but the call to that function will be close in time.
- Spatial locality: If a code or data at a particular memory address is accessed, nearby memory locations are likely to be accessed soon. For instance, when iterating through an array sequentially, the program repeatedly access adjacent memory locations.
Realizing that this locality exists is the foundation for CPU caches we use them today.
How CPU Caches fit the big Picture
Before discussing the implementation details of CPU caches, let’s discuss formally where does they fit into the bigger picture of modern computer systems. We can start with depicting a simplified architecture of cache configuration.
In this representation, CPU core is connected to the cache, all the load and store operations need to happen through it.
Soon after the introduction of CPU cache the system got more complicated. The speed difference between the CPU and Main memory increased again. To mitigate this another level of cache was introduced, which was bigger and slower than the first level of cache.
In addition to that first level ( hence forth L1) cache was split to two dedicated parts the instruction cache (L1i) and data cache (L1d). In today’s system the architecture looks somewhat like below.
One thing to keep in mind here is, for multicore CPU higher level caches are usually shared and L1d , L1i caches remain local to each core. This arrangement leads to interesting synchronization problem, which we shall discuss in an upcoming post ( Coming soon 😊).
Cache implementation details
Now that we have high level understanding where CPU caches fit in modern computer systems. Let’s spend some time discussing their architecture.
CPU Caches are logically split into equal sized blocks, known as cache lines. In early caches these lines were 32 bytes long. nowadays the norm is 64 bytes. when CPU needs a data word, the full cache line is loaded to take advantage of temporal and spatial locality as discussed earlier.
Get Pratyush Rout’s stories in your inbox
Join Medium for free to get updates from this writer.
Now the main question is how do we find a particular address in these blocks. Well A memory address is logically split into 3 Parts as shown below.
Let’s forget about cache set for now ( we’ll come to it later) . If we map tag to each cache line, by searching through it , we can find the line where target address exist. Inside the target cache line using offset we can jump to the particular byte. The Caches where the cache lines are arranged this way is known as fully associative cache.
The main drawback of fully associative caches are to find a tag we have to search in all the entries. to understand the criticality of the bottleneck let’s do a simple math.
To achieve adequate performance, the cache logic would have to be able to pickup from all the entries the one matching tag in just a few CPU cycle. The effort to implement this would be enormous.
Here comes the idea of cache sets, using the set index we can directly index into the cache line and just do one comparison of tag to find the data. The Caches where there is one to one mapping of a cache set to a cache line is known as Direct mapped Cache.
The biggest downside to Direct Mapped caches is their lack of flexibility. Because every piece of data maps to exactly one specific line, you often run into ‘conflict misses.’ Two active variables might fight over the same single slot — constantly overwriting each other — even if there is plenty of free space available elsewhere in the cache 😔.
Okay so what’s next ! , There is a saying “It’s all about balance” . we’ll do the same.
Let’s assign multiple entries to same cache set. By doing so we are taking a balanced approach, where we don’t need to search for all entries or continuously evicting for the same entry. This type of caches are well know as Set associative cache.
Here is a simple diagram of 2 way Set associative cache.
In this example if we look carefully now for each set index we have two lines allocated. while looking for an address using the set index we can directly jump to the set and inside the set we have to do 2 comparison of tags to find out if it’s a hit or miss.
The main advantage we can think is of redundancy as for each set we have allocated more cache lines . It is in a balance because we neither have to search in all the entries nor get penalty of collisions.
In Summary
Today we tried to answer
- Why we need CPU caches ?
- What are different types of CPU caches ?
- How to find a data inside each caches ?
we’ll stop here . In the next part we’ll discuss more about the properties , how a programmer can effectively use them to write faster programs.
Thank you so much for reading so far ! . Please share your thoughts in comments.
Until next time bye 👋.
