Prefetching

A miss only costs 80 ns if the program has to wait for it. A prefetcher asks for a line before the program does, so the wait is over by the time the read arrives. This lecture builds two prefetchers, scores them with coverage and accuracy, and shows where they work, in loops with a regular stride, and where they cannot, in reads in an unpredictable order.

So far the cache loaded a line when a read missed. A prefetch loads it earlier. If the guess is right, the read that comes later finds the line already in the cache and hits. Every modern processor has hardware prefetchers that watch the addresses of reads and guess what comes next. The simplest guess is: whoever read line L will want line L + 1 next. Our provided cache has a fill method that loads a line without counting a hit or a miss, which is exactly a prefetch.

def baseline_misses(trace):    cache = Cache()    for address in trace:        cache.access(address)    return cache.missesdef next_line_misses(trace):    cache = Cache()    for address in trace:        cache.access(address)        cache.fill((address // LINE_BYTES + 1) * LINE_BYTES)1    return cache.missestrace = [8 * i for i in range(800)]print("no prefetch:", baseline_misses(trace), "- next line:", next_line_misses(trace))jumps = [i * 4096 for i in range(50)]print("jumps of 4096 bytes:", baseline_misses(jumps), "- next line:", next_line_misses(jumps))

no prefetch: 100 - next line: 1
jumps of 4096 bytes: 50 - next line: 50

1. 1Prefetching the next line costs nothing here: fill does not count as a hit or a miss.

Reading 800 values in order, a plain cache misses once per line, 100 times. With the next-line prefetcher it misses once in total: after the very first read, the line that is needed next is always already there. The second case shows the limit. If the program jumps 4096 bytes at a time, the line after the current one is useless and the prefetcher saves nothing: still 50 misses out of 50 reads.

Real prefetchers look for a pattern in the lines a program reads. The most common one is a constant stride: the program reads lines 0, 3, 6, 9, jumping three lines each time. A stride detector remembers the last line and the last step. When the new step equals the last one, it is a pattern and the next line is the current one plus the step. It takes two equal steps to be sure, so it never guesses on the first two reads.

1. 1
   Ignore a repeatReading the same line again says nothing about a stride.
2. 2
   Compute the stepThe new line minus the last line.
3. 3
   Compare with the last stepEqual steps mean a pattern: predict the new line plus the step.
4. 4
   RememberKeep the new step and the new line for the next read.

class StridePrefetcher:    def __init__(self):        self.last_line = None        self.last_delta = None    def observe(self, line):        if line == self.last_line:            return None        prediction = None        if self.last_line is not None:            delta = line - self.last_line            if delta == self.last_delta and line + delta >= 0:1                prediction = line + delta            self.last_delta = delta        self.last_line = line        return predictionp = StridePrefetcher()print([p.observe(line) for line in [0, 3, 6, 9, 12]])p = StridePrefetcher()print([p.observe(line) for line in [5, 5, 5, 6, 7]])

[None, None, 9, 12, 15]
[None, None, None, None, 8]

1. 1Two equal steps in a row: this is a stride, so the next line is the current one plus the step.

The first sequence is a stride of three lines. The detector says nothing for the first two reads and then predicts 9, 12 and 15, always one step ahead. In the second sequence the repeated reads of line 5 are ignored, and the stride of 1 is only confirmed at the last read. A good detector is cautious: a wrong guess has a price, as we will see next.

Two numbers score a prefetcher. The coverage says how much of the problem it solved. The accuracy says how much of its work was useful. To measure them we run the trace through the cache, make a demand read, ask the prefetcher what to load next, remember which lines were prefetched, and count when a demand read hits one of them.

def run_with_prefetcher(trace, prefetcher):    cache = Cache()    marked = set()    prefetches = 0    useful = 0    for address in trace:        line = address // LINE_BYTES        if cache.access(address):            if line in marked:                useful += 1                marked.discard(line)        else:            marked.discard(line)        target = prefetcher.observe(line)        if target is not None and not cache.contains(target * LINE_BYTES):            cache.fill(target * LINE_BYTES)            prefetches += 1            marked.add(target)    return {"demand_misses": cache.misses, "prefetches": prefetches, "useful": useful}def quality(trace):    baseline = baseline_misses(trace)    run = run_with_prefetcher(trace, StridePrefetcher())    coverage = 1 - run["demand_misses"] / baseline    accuracy = run["useful"] / run["prefetches"] if run["prefetches"] else 0.0    return baseline, run, round(coverage, 3), round(accuracy, 3)import randomordered = [8 * i for i in range(2000)]shuffled = [8 * p for p in random.Random(1).sample(range(2000), 2000)]print("in order:", quality(ordered))print("shuffled:", quality(shuffled))

in order: (250, {'demand_misses': 3, 'prefetches': 248, 'useful': 247}, 0.988, 0.996)
shuffled: (250, {'demand_misses': 250, 'prefetches': 1, 'useful': 0}, 0.0, 0.0)

On the in-order read the prefetcher removes 98.8% of the misses and 99.6% of its prefetches are used. On the shuffled read it does nothing: with no repeating step it almost never issues a prefetch (just one), and so it also does no harm. That is the behaviour to want. A prefetcher that guessed all the time would fill the cache with lines nobody reads.

The lab reads 2,000 closes in three ways: stored one after another and read in order, stored inside rows of five values (a stride of 40 bytes), and stored one after another but read in order of rising trading volume. The first two have a regular pattern; the third visits the days in an order that looks random, because the volume of one day tells nothing about the volume of the next.

The hint is in the question that the prefetcher answers: what comes next? If the answer is in the pattern of the addresses, hardware finds it for free. If the order depends on data, as when you visit rows sorted by volume, nothing can guess it. The software fix is to change the data layout so that the access becomes regular again, for instance by sorting the rows once and then reading them in order.

The lab builds the two prefetchers, the simulation that scores them and the study on the three ways of reading the SPY closes.

• Function · questionBuilds on
• baseline_misses(trace)How many misses with no prefetching?Cache
• next_line_misses(trace)How many with a next-line prefetcher?Cache.fill
• StridePrefetcher().observe(line)Which line comes next?The last line and the last step
• run_with_prefetcher(trace, prefetcher)What happened: misses, prefetches, useful ones?Cache
• quality(trace)What coverage and accuracy does it reach?baseline_missesrun_with_prefetcher
• study(bars)Where does the prefetcher help on the SPY closes?qualitynext_line_misses

Next topic: so far an address was a line and a cache hit was all that mattered. In TLB and huge pages every address first has to be translated from a virtual page to a physical one, and a small cache of translations, the TLB, can miss too, in a way that depends on the page size.