プリフェッチ

ミスが80 nsのコストになるのは、プログラムがそれを待たなければならないときだけです。プリフェッチャは、プログラムより先にラインを要求するので、読み出しが来るときには待ちが終わっています。この講義では2種類のプリフェッチャを作り、カバレッジと精度で評価して、一定のストライドのループでは効き、順序が予測できない読み出しでは効かないことを示します。

これまでのキャッシュは、読み出しがミスしたときにラインを読み込んでいました。プリフェッチはそれを早めます。予想が当たれば、後で来る読み出しはラインがすでにキャッシュにあってヒットします。現代のプロセッサはどれも、読み出しのアドレスを監視して次を予想するハードウェアプリフェッチャを持っています。最も単純な予想は、ラインLを読んだなら次はラインL + 1が欲しいだろう、というものです。用意したキャッシュには、ヒットもミスも数えずにラインを読み込む fill メソッドがあり、これがまさにプリフェッチです。

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. 1ここでは次のラインのプリフェッチに費用はかかりません。fill はヒットにもミスにも数えられません。

800個の値を順に読むと、普通のキャッシュはラインごとに1回、つまり100回ミスします。次ラインプリフェッチャがあれば、全体で1回しかミスしません。最初の読み出しのあとは、次に必要なラインが常にすでにあるからです。2つ目のケースは限界を示します。プログラムが毎回4096バイト飛ぶなら、現在の次のラインは役に立たず、プリフェッチャは何も節約できません。50回の読み出しで50回ミスのままです。

本物のプリフェッチャは、プログラムが読むラインの中にパターンを探します。いちばん多いのは一定のストライドで、たとえばライン0, 3, 6, 9のように毎回3ライン飛ぶ読み方です。ストライド検出器は直前のラインと直前の差を覚えておき、新しい差がその前の差と等しければパターンと見なし、次のラインを「現在のライン＋差」と予測します。確信するのに等しい差が2つ必要なので、最初の2回の読み出しでは予測しません。

1. 1
   繰り返しは無視同じラインをもう一度読んでも、ストライドの手がかりにはなりません。
2. 2
   差を計算する新しいライン − 直前のライン。
3. 3
   直前の差と比べる差が等しければパターンなので、新しいライン＋差を予測します。
4. 4
   覚えておく新しい差と新しいラインを、次の読み出しのために保存します。

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. 1同じ差が2回続いたらストライドなので、次のラインは現在のライン＋差です。

最初の並びは3ライン飛びのストライドです。検出器は最初の2回は何も言わず、その後は9、12、15と、常に1歩先を予測します。2つ目の並びでは、ライン5の繰り返し読み出しは無視され、ストライド1は最後の読み出しで初めて確認されます。よい検出器は慎重です。外れた予測には代償があり、次にそれを見ます。

プリフェッチャは2つの数で評価します。カバレッジは問題をどれだけ解決したかを、精度はその作業のどれだけが役に立ったかを示します。測るには、トレースをキャッシュに通し、読み出しを行い、プリフェッチャに次に読み込むものを尋ね、プリフェッチしたラインを覚えておき、読み出しがそのいずれかにヒットしたら数えます。

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)

順番に読む場合、プリフェッチャはミスの98.8%をなくし、プリフェッチの99.6%が使われます。シャッフルした読み出しでは何もしません。繰り返しのストライドがないのでほとんどプリフェッチを出さず（1回だけ）、害もありません。これが望ましい振る舞いです。いつも当てずっぽうを出すプリフェッチャは、誰も読まないラインでキャッシュを埋めてしまいます。

ラボでは2,000個の終値を3通りで読みます。1つ目は順に並べて順に読む、2つ目は5値の行の中に置く（ストライド40バイト）、3つ目は順に並べて置いたまま出来高の小さい順に読む、です。最初の2つは規則的ですが、3つ目は日を並べ替えた順に訪れるのでランダムに見えます。ある日の出来高は次の日の出来高について何も教えないからです。

ヒントは、プリフェッチャが答える問い「次は何か」にあります。答えがアドレスのパターンにあるなら、ハードウェアがタダで見つけます。順序がデータに依存する場合、たとえば出来高で並べた行を訪れるときは、誰にも予測できません。ソフトウェア側の解決策は、データの配置を変えてアクセスを再び規則的にすることです。たとえば行を一度ソートして、あとは順に読みます。

ラボでは、2つのプリフェッチャ、それを評価するシミュレーション、そしてSPYの終値の3通りの読み方での研究を作ります。

• 関数 · 問い前提
• baseline_misses(trace)プリフェッチなしのミス数は？Cache
• next_line_misses(trace)次ラインプリフェッチャありのミス数は？Cache.fill
• StridePrefetcher().observe(line)次はどのラインか？直前のラインと直前の差
• run_with_prefetcher(trace, prefetcher)何が起きたか：ミス、プリフェッチ、有用なものCache
• quality(trace)カバレッジと精度はどれだけか？baseline_missesrun_with_prefetcher
• study(bars)SPYの終値でプリフェッチャはどこで効くか？qualitynext_line_misses

次のトピック：ここまでは、アドレスはラインであり、キャッシュのヒットだけが重要でした。TLBとヒュージページでは、あらゆるアドレスがまず仮想ページから物理ページへ変換されます。変換結果を覚える小さなキャッシュであるTLBもミスすることがあり、その起き方はページの大きさで変わります。