Copyright 2013, Clinton A Staley
In this segment we'll finish up our discussion of cache design, before moving on to optimizing code for cache efficiency.
Direct mapped cache (v)
Set-associative cache (v)
Cache associativity (v)
L1/L2/instruction caches (v)
When the CPU reads or writes an address, it uses the middle 3 bits of the address to identify the home cache line at which the data for that address would be found, if it were in cache. But, if there is data in that cache line, how does it know whether the data is from the desired cache block group, or some other cache block group? To resolve this, each cache line includes a tag comprising the top 5 address bits of the cache block currently occupying that cache line. If that tag matches the top 5 bits of the desired address, then the cache line has a cache block from the right cache group, otherwise the CPU loads the desired cache block into the cache line and evicts the current content and updates the tag.
In the diagram, I've expanded the cache, with tags on the cachc lines to show how this might look in practice. For each of the following hex addresses, indicate what cache line would hold that address if it were in cache, and determine whether the desired cache block is in the cache, or needs to be loaded from RAM. (I suggest you expand them into binary, and break out the three fields describe in the earlier lecture segment.)
0x104
0x3A5
0x833
Expanding those, one at a time:
0x104 00010 000 0100 Cache block group 2, home cache line 0, offset 4. This is in cache, at the home cache line of 000.
0x3A5 00111 010 0101 Cache block group 7, home cache line 2, offset 5. Home cache line 2 currently has content from cache block group 31. The address is not in cache.
0x833 10000 011 0011 Cache block group 16, home cache line 3, offset 3. Home cache line 3 has the right tag, so this is in cache.
What we've described thus far is called a direct mapped cache: one in which each cache block has a fixed home cache line, and only one cache block can occupy a cache line at a time. Direct mapped cache is fast and relatively simple, but it has the significant limitation that a given home cache line can only accommodate a single cache block. If the CPU is working at the same time with two different cache block groups in memory it will often deal with cache blocks having the same home cache line, and they will repeatedly evict one another from the cache.
Modern caches address this problem by expanding cache lines into cache sets of 2, 4, or 8 cache lines. Cache blocks don't have home cache lines in this model, they have home cache sets (again, an unofficial term). Here's a redrawing of our Minimem model with cache sets comprising two cache lines each. A cache block can go into any of the cache lines in its home cache set. Each cache line within a cache set still has a tag, so when the CPU seeks a given cache block, it goes to the indicated cache set, and the seeks a cache line within the cache set that has the right tag. Each cache set is thus a small lookup table in its own right.
This design is called a set-associative cache. The number of cache lines per cache set is called the cache's associativity. Here we have an associativity of 2, for instance. A set-associative cache is more complex in that all cache lines within a cache set must be checked for the presence of the desired cache block, but it reduces cache collisions. If the CPU simulateously works with two cache blocks having the same home cache set, that's no problem.
Of course, given the same total amount of cache memory, there will be fewer cache sets than cache lines, which in turn reduces the number of cache blocks per cache block group. In our new model with 4 cache sets of two cache lines each, every fourth cache block would have the same home cache set, where before every eighth cache block had the same home cache line.
How would going from associativity of 1 (the direct-mapped model) to an associativity of 2, in Minimem, affect the division of bits from answer 6 in the prior segment?
There would be just 2 bits identifying the cache set, and the tag would be one bit larger at 6 bits. The byte offset bits would remain at 4. The top bit of what would have been the cache line identifier instead becomes the last bit of the tag.
Note that set-associative cache also requires more complex rules regarding evicting existing cache blocks in order to make room for a desired one. It's no longer a matter of simply kicking out the one cache block occupying the cache line in question. Instead, one of the perhaps 8 different cache blocks (if we have associativity of 8) in the cache line must be chosen. A typical cache uses an LRU (least recently used) strategy, evicting whichever cache block was least recently used.
What if we changed Minimem to an associativity of 8? What type of cache would we then have? (Consult vocabulary from earlier in this topic)
The entire cache would be one big cache set, any cache block could go in any cache line in the cache, and we'd determine which cache blocks were present entirely by looking up their (now 8 bit) tags. In other words, we'd have a fully associative cache.
So, gradually increasing the cache associativity from 1 to the number of cache lines in the entire cache moves us from a direct-mapped cache to a fully associative one. How far along that spectrum you go is a matter of how much hardware expense you can afford for the tag-based lookup of cache lines in each cache set. A set-associative cache is sort of a "poor man's fully associative cache".
You now have a basic summary of cache architecture for a typical L1 (top level, fastest) cache. To translate the Minimem model into a real cache and memory architecture, just do something like the following (using common figures as of this writing):
1. Increase cache line size to 32 bytes
2. Increase cache size to 64K
3. Increase memory size to 4G
4. Make the associativity 8
Just to be sure you have the "real" picture, given the sizes just listed, how would a 32-bit address be divided into fields of bits in a real cache model? How big would a tag be? How many cache lines and cache sets would there be? How many bits of the address would be used to identify the cache set? How many cache blocks would compete for the same cache set, and what fraction of them could be in the cache set at the same time?
With the figures given, the cache would have 2048 cache lines, in 256 cache sets of 8 cache lines each. The bottom 5 bits of the address would be offsets within a cache line. The next 8 bits would identify the cache set. That leaves 32 – 8 - 5 = 19 bits for the tag. So the address would be viewed as 19 tag bits, 8 cache set index bits, and 5 offset bits within the cache line. The overall memory has 128M cache blocks, and every 256th one of them competes for the same cache set. So 512K cache blocks compete for each cache set. But 8 of them can be resident in that cache set at once, so up to 1 out of 64K cache blocks could be in the L1 cache at a time.
In case you thought one cache wasn't complex enough, modern processors generally have at least two levels of cache. The second level cache is termed L2 cache. and it uses memory hardware (usually still on chip with the CPU) that falls between L1 and RAM in both speed and cost. Being cheaper than L1, the L2 cache is larger, generally by a factor of 8 or 16.
The good news is that the architecture we've described for L1 cache typically applies unchanged for L2 cache. L2 cache is made of cache lines, almost always the same size as the L1 cache lines. When a cache line is pulled into L1, it also gets copied into L2. When the line is dropped from L1, it may still be retained in the larger L2 cache, at least for a while. So the effect of L2 cache is that a cache line recently dropped from L1 cache is quicker to come back to L1 cache than would normally be the case if it was only present in RAM. For purposes of software optimization, that's most of what you need to know about L2, and for that matter, L3 or other levels of cache. (Yes, some processors do actually have three levels of cache, but the pattern, again, is the same as for L1 and L2, just with yet more cache lines and yet slower speed.)
Our discussion thus far has concentrated on data caching, but of course machine instructions are another form of data that the CPU pulls from RAM, and which might benefit from caching. CPUs generally have separate caches for data and instructions.
What particular patterns of code would benefit from instruction caching? Long blocks of nonbranching code, for instance?
Not long blocks, no. But loops certainly would, as would functions that are called repeatedly within a short time. In both cases the same instructions will be executed repeatedly in a short time, and will be worth holding in a faster instruction cache.
Instruction caches are less interesting for code optimization purposes than are data caches, since we have less control over the order of instruction execution than over the organization and access of data, but it is worth remembering that breaking a loop into smaller subloops, or reorganizing function calls to group calls of the same function where possible, may both be useful in some cases.
As I said at the start of this segment, there is a great deal more to cache design, but this covers the basics needed to understand how to optimize for cache efficiency. In the next topic we'll look at strategies for optimizing cache utilization in software.