Copyright 2013, Clinton A Staley
In this segment we'll finish up the optimization of CountInversions, introducing a couple of more sophisticated cache optimization methods. The prior segment cut out half of the cache misses by improving spatial contiguity of the data, arriving at CountInversions2.c, which will be our starting point for this segment.
Temporal contiguity (v)
Loop-tiling (v)
Binary resonance (v)
The optimization required to cut down on the remaining cache misses is more sophisticated. The reason we get so many cache misses is that for each vals[i], we traverse all the remaining vals[j] values. This causes long runs through the vals array, which runs create a series of cache misses. After incrementing i, we retraverse almost the same run of vals[j] values the next time (less one). One might hope for some help from precached data at that point, but the end of the prior run will long since have booted the start of the run out of cache, so the new run starts afresh with cache misses. The cache just isn't big enough to store all the tags in the array at once.
How may pairwise comparisons of a vals[i] and a vals[j] will we make, given numHogs of 10000? How does this compare with the cache miss count for line 28?
About 100002/2, or 50 million. This matches very closely with the cache miss count.
Each pair is causing a cache miss. The vals[i] value stays cached during the line 27-31 inner loop in CountInversions2.c, but each new vals[j] access causes a cache miss.
If the core problem is that the cache can't hold an entire run of vals[j] values without losing the first ones, perhaps we need shorter runs. What if we group the loops differently? Imagine the entire array of 10000 CacheHogs broken into sets of say 20 CacheHogs each. Would we be able to compare just the CacheHogs within each set with minimal cache misses?
The critical question is whether all the data needed for one set would fit in the cache. Assuming a set of 20 CacheHogs, how big a cache would be needed to be able to load the entire CacheHog set into cache, at the cost of one set of cache misses, and then to work entirely in cache for all roughly 202/2 = 200 or so comparisons? Remember that cache won't load an entire CacheHog if we're not accessing most of it. Cache loads only the cache lines used, not the entire C data structure. Assume a cache line of 64 bytes.
Each CacheHog will take one cache line for its two tags (but nothing more than that) so we'd need 20*64 = 1280 bytes of cache.
Even the 8KB cache on the ancient processor we're using can manage that. So we can do the 200 comparisons within each set of 20 CacheHogs at the cost of 20 cache misses, cutting the miss rate from around 100% to around 10%
But what about between sets? There are 10,000/20 = 500 CacheHog sets in the array. Most of the comparisons are between CacheHogs in different sets. Between any pair of sets there are 400 CacheHog pairs to be checked.
What if we do one pair of sets at a time? The diagram shows the concept. We start with a set A, doing all the internal comparisons for A first, and then doing all comparisons with A and each following set, in their entirety, all 400 of them, before moving on to compare A with another set. Given that we'd already have set A cached, we'd incur, for each following set, another 20 cache misses, but then would be able to do 400 comparisions in cache, assuming that both sets fit in the cache at the same time. 20 misses/400 comparisons = 5%. That's even better than the 10% we had for the intraset comparisons.
This method is called loop-tiling and the "sets" are termed tiles. (An alternative and somewhat uglier term is strip-mining.) We'll use "tile" instead of "set" henceforth. Loop-tiling requires a rather sophisticated cascade of nested loops, with the outer loops driving through all the tiles, and inner loops driving through the comparisons within each pair of tiles. With the right loops, there's no need to actually break the array into pieces; looping carefully within the array will work. CountInversions3Fill.c has a partial implementation of loop-tiling, with tileSize left as an input variable so we can easily experiment with different tile sizes.
Fill in the rest of CountInversions3Fill.c, without consulting CountInversions3.c, compile it, and get it working. The big for-loop drives through the tiles, with iBase and iLim giving the bounds of each successive tile. The line 31-37 loop does intra-tile comparisions within tile i. Then the line 40-49 loop goes through all the tiles in the rest of the array after tile i, with jBase and jLim giving the bounds of a second tile. Don't worry if you find the loop-tiling doesn't improve things yet; it will after we do some tweaking in the following discussion.
This one should have taken you a bit of time. The solution I came up with is in CountInversions3.c. The loop on 31-37 is doing intratile comparisons using just iBase and iLim. Then the big loop on 40-49 goes through each of the succeeding tiles, and comparing it against the i tile's content, using iBase and iLim and jBase and jLim to do the intertile comparison.
A similar pattern will work for any nested-loop computation that needs cache optimization. So, we have a new rule:
Cache Optimization Rule 3: Use loop-tiling to group nested loop computations.
The first two rules dealt with spatial contiguity. This one deals with temporal contiguity – rearranging code so that the uses of a given memory location are closer to one another in time, so that the location can stay cached for multiple uses.
So, let's try out our new loop-tiled implementation.
What tile size would be appropriate for an 8KB cache with 64 byte cache lines? (Leave a little room for other variables like i, j, iLim, jLim, etc.).
Well, we have 128 cache lines. If we reserve 120 of them for tiles, and assume that each CacheHog needs just one cache line, then we can keep two tiles of 60 CacheHogs each in cache.
So, we try out the code with a tile size of 60 out and... Nothing. We're still at about 50 million cache misses.
OK, so maybe we miscalculated. Let's try a smaller tile size, maybe 8....
Same result. This is irritating. So, what's going on here? It's almost as if our cache is a lot smaller than we thought, and indeed that's effectively what's happening. Get ready to use all that deep cache architecture we learned in the prior segments.
Consider the cache size of 8K, cache line size of 64B, and associativity of 4. How many cache sets are there?
128 cache lines, but just 32 cache sets.
OK, now consider carefully the size of a CacheHog. How many different cache sets will be used by accessing tag1 and tag2 from each CacheHog in a contiguous array of them? To which cache sets, in other words, do all the tag fields in the array map?
CacheHogs are exactly 1024 bytes long, so each pair of tag fields in successive array elements is 1024 bytes apart, or 1024/64 = 16 cache lines apart. They map to every 16th cache set, which in a 32 set cache means they'll all map into just two cache sets.
So, we're hitting just 1/16 of our cache, a total of 8 cache lines in two cache sets. It's as if 15/16ths of the cache weren't even there.
Let's reality-check that. Trying a tile size of 4, so we can fit two tiles into this 8 cache line area, we find...
We get an improvement! It's just a 50-60% reduction, down to 22 million misses, but at least something's happening. The reason it's not better is that with a tile size of 4 we're getting 4 cache misses to load each tile, with just 16 pairs between each set of tiles, so a 25% cache miss rate is inevitable. Plus, at least some of the other variables that also need cache are probably hitting the same cache sets that our tiles are overusing.
The fix is to stagger CacheHogs so they don't line up so neatly. It's that binary-powered length of 1024 that's creating what we might call binary resonance between the vals array and the cache. A simple fix would be to add a dummy 16 bytes or so to the end of each CacheHog to break this resonance. Doing so, in CountInversions4.c, we find...
Wow. 1.5 million misses, or a rate of about .5% for the line in question, and .2% for the program overall. That's about as good as it gets. And running the program we find an execution time of...
under .5 s
Sure beats the 7s or so we started with, by a factor of around 15x, and it's all due to reorganizing for cache efficiency.
Based on this, let's add a fourth rule:
Cache Optimization Rule 4: Break up binary resonance
And note that this last rule, and the diagnosis that led to it, requires a full understanding of cache architecture, as well as knowledge of the cache parameters for the machine under study.