Copyright 2013, Clinton A Staley
In this module we'll go over optimization methods that take CPU cache into account. As processor speeds have exceeded RAM access speeds in the past decade or two, the use of fast on-chip CPU cache has become essential to full CPU efficiency. We won't explore all the architectural issues surrounding cache in this module, but we will introduce a simple example of the most common cache architecture, and then look at standard approaches for optimizing with respect to cache usage, and tools for profiling cache use.
Cache (v)
Cache lines and cache blocks (v)
Fully associative cache (v)
Cache memory is a small amount of very fast memory that resides on-chip with the CPU. The CPU keeps the content of the most recently or most commonly used memory addresses in its cache, and reads and writes them there, at much higher speed (a factor of 5x or more) than can be had from the standard RAM. If a given memory location is read multiple times in a short period, then the CPU must read it once (slowly) from RAM into cache, but can then can read/write it repeatedly, very quickly, from/to cache. Any write into cache also must be written into RAM for permanent storage, either immediately or after some delay depending on cache design. But, the CPU needn't wait for the slow write to RAM to complete, because an accurate copy of the new value will be in the cache, to be read immediately.
A typical CPU as of this writing offers perhaps 64 KB of fast cache, serving a memory of perhaps 4 GB. Those are pretty big values to draw and discuss, so we'll use a smaller model as our example case – call it the Minimem model. The Minimem model is fully representative of realistic cases; it's just a matter of scaling it up and adding more bits to the addresses.
The Minimem model, as shown in the diagram, has just 4096 bytes of standard, slow RAM. (Don't laugh, that was a realistic figure – 40 years ago.) The CPU has a small, fast cache memory of 128 bytes.
But, how exactly, is RAM content stored in cache? One might imagine some sort of general lookup table, where a given memory address and its associated content go into the cache as a key/value pair in a map or dictionary. The CPU would attempt to look up a desired address in the cache before resorting to RAM. Such an arrangement is possible, and is called a fully associative cache. But it's hardware expensive, and/or slow, to look up addresses in a large associative table, so this design is not common.
Instead, a typical cache is organized in groups of bytes called cache lines, with specific areas of RAM assigned to specific cache lines in the cache. A cache line is larger than a memory word, typically large enough to store several memory words. The Minimem model has 16-byte cache lines.
So, how many cache lines are there in the Minimem cache?
This is mostly an "are you awake" question. Given 128 bytes of cache and 16-byte cache lines, we'll have 8 cache lines. (A realistic cache might have 2048 or 4096 cache lines, of 16 or perhaps 32 bytes.)
Let's draw that here, with our cache now having 8 cache lines of 16 bytes each.
RAM doesn't get copied into the cache byte by byte. It is copied a cache line at a time, in 16 byte blocks the size of a cache line. Each cache-line sized piece of RAM is called a cache block.
The RAM cache blocks are on 16-byte boundaries within the RAM. One cannot for instance copy addresses 8-23 from RAM into a cache line. It would have to be addresses 0-15, or 16-31, etc. Given this, we can view our RAM as broken into 4096/16 = 256 cache blocks. I'll draw the first 16 of those, and the last 8, with some ellipses in between.
This does not imply, btw, that machine instructions can fetch RAM only by entire cache blocks. An instruction might still request, say, four bytes starting at address 8. But if it does, the entire 16 byte cache block that contains that value goes into the cache, whether you are going to use the other 12 bytes or not. Very often, you will use the other bytes, since it's common to fetch adjacent words in memory, but it's not guaranteed.
So, can any cache block from RAM go into any cache line in the cache? No. There's a further restriction. For simplicity of hardware, each cache block in RAM has one, and only one home cache line (not an official term) in the cache. It doesn't go into any other cache line but that one. The first 8 cache blocks in RAM have the first 8 lines of the cache, one-for-one, as their home cache lines, as the diagram shows. If they're cached, thats where they'll go. Of course there are a lot more cache blocks than cache lines, so many cache blocks must share the same cache line. The next 8 cache blocks in RAM also have the same home cache lines, again as shown in the diagram. And that pattern continues all the way through the RAM, with home cache lines rotated over and over again so that every eighth cache block goes into the same home cache line. More accurately, they compete for the same home cache line, since only one cache block at a time can occupy the cache line. The rotational pattern at least ensures that nearby cache blocks won't compete for the same cache line, but it doesn't prevent competition between widely separated cache blocks. The two biggest jobs in optimizing for cache are to focus on small groups of data at a time so what you're working on will fit in cache, and to structure your data to minimize competition for home cache lines.
A few questions to be sure you've got all this straight so far:
First, a simple warmup question. In the Minimem model, how many cache blocks does each cache line serve? How many cache blocks, in other words, compete for the same cache line?
The 4096 byte RAM has 4096/16 = 256 cache blocks, as we said earlier. Every eighth one competes for the same home cache line, so there are 32 cache blocks (256/8) competing for each home cache line.
What bits do the addresses of the 16 bytes in a cache line or cache block have in common? What bits would differ?
Given that a cache block starts on a 16-byte boundary and is 16 bytes long, only the bottom 4 bits in the addresses of its bytes will vary. The top 8 bits will be unchanging within the same cache block.
For instance, bytes 64-95 form a cache block. Their addresses are 0000 0010 0000 through 0000 0010 1111. We might say that the top 8 bits of the address identify the cache block, and the bottom 4 bits indicate the byte within the cache block.
The first 8 cache blocks in RAM all have different home cache lines. What do all their address bits share in common?
That's a total of 128 bytes (same size as the cache, obviously) so their bottom 7 bits will vary, but the top 5 stay the same.
Let's call each set of 8 cache blocks – one cache's worth of RAM – a cache block group (yet another unofficial term). Our first cache block group has addresses from 00000 0000000 to 00000 1111111, as shown in the diagram. It's top 5 bits are always 00000. The next cache block group commences with address 00001 0000000. It's top 5 bits are always 00001. We could say that the top 5 bits of the address identify the cache block group.
Now consider all the cache blocks that share the same home cache line. What do their address bits have in common? How do they differ?
The middle three bits, between the top 5 and bottom 4 bits, identify the home cache line. As we advance from cache block to cache block within a cache block group, those 3 bits go from 000 to 111, identifying the home cache line. So, all cache blocks that share the same cache line have the same middle three bits, but different top 5 bits, since they're all from different cache block groups.
Summarizing, we can view a 12 bit address as three bit fields:
5 bits identifying the cache block group | 3 bits identifying the cache line | 4 bits giving a byte offset within the cache block/line
In the next segment, we'll look at how the CPU knows which cache blocks are present in the cache, and we'll look at newer cache designs that reduce the competition between cache groups for the same cache line.