フォルスシェアリングとパディング

4つのスレッドがそれぞれ自分のカウンタを更新し、共有しているものは何もないのに、ループは本来より40倍遅くなります。4つのカウンタが同じキャッシュラインにあり、コアがそれを奪い合うからです。この講義ではキャッシュコヒーレンスの小さなモデルを作り、SPYの表の日付で動くループでフォルスシェアリングがどれだけ高くつくかを示し、数バイトのパディングで直します。

ここまでは1つのプログラムが1つのコアで動いていました。実際のマシンには複数のコアがあり、それぞれに小さく速い専用キャッシュがあります。すると問題が起きます。コア0とコア1がともにあるラインのコピーを持ち、コア0がそれを変更したら、コア1は古い値を読み続けてはいけません。これを防ぐハードウェアの規則がキャッシュコヒーレンスです。最も簡単な実現方法は、コアがラインに書き込む前に、他のすべてのコアのそのラインのコピーを捨てることで、これが無効化です。

1. 1
   自分のキャッシュを見るラインがなければ、このアクセスはミスです。
2. 2
   書き込みなら他を追い出すラインを持つ他のコアは、それぞれコピーを失います。1コアにつき1回の無効化です。
3. 3
   ラインを保持するその後、ラインはこのコアのキャッシュにあり、次のアクセスに備えます。

次のクラスは、コアごとに保持しているラインの集合を持ちます。3つのステップを再生します。コア0がバイト0に書き込み、コア1がバイト8（同じライン）に書き込み、再びコア0がバイト0に書き込みます。

class CoherentCaches:    def __init__(self, n_cores):        self.lines = [set() for _ in range(n_cores)]        self.misses = 0        self.invalidations = 0    def access(self, core, address, write):        line = address // LINE_BYTES        hit = line in self.lines[core]        if not hit:            self.misses += 1        if write:            for other, held in enumerate(self.lines):1                if other != core and line in held:                    held.discard(line)                    self.invalidations += 1        self.lines[core].add(line)        return hitcaches = CoherentCaches(2)print(caches.access(0, 0, True), caches.access(1, 8, True), caches.access(0, 0, True))print("misses:", caches.misses, "invalidations:", caches.invalidations)

False False False
misses: 3 invalidations: 2

1. 1書き込みは、そのラインを持つ他のコアからラインを取り除き、コピー1つにつき1回の無効化を数えます。

3回のアクセスはすべてミスです。コア1の書き込みでコア0のコピーが無効化され、次のコア0の書き込みで今度はコア1のコピーが無効化されます。コア0とコア1は同じバイトには一度も書いていません。隣り合うバイトだけなのに、書き込みのたびにラインを奪い合います。

イベントを並列に数える一般的な方法は、各コアに専用のカウンタを持たせ、どのコアも他を待たないようにすることです。カウンタは1つ8バイトで、配列に並べると4つが64バイトの1ラインに入ります。50周分の更新（毎周コアごとに1回の書き込み）を作り、カウンタの間隔を8バイト（詰めた場合）と64バイト（パディングした場合）にして再生します。時間は、コア自身のキャッシュでのアクセスが1 ns、他のコアからラインを取ってくるミスが60 nsです。

def counter_address(core, stride_bytes):    return core * stride_bytesdef update_trace(n_cores, n_updates, stride_bytes):    return [(core, "w", counter_address(core, stride_bytes)) for _ in range(n_updates) for core in range(n_cores)]def run_trace(trace, n_cores):    caches = CoherentCaches(n_cores)    for core, op, address in trace:        caches.access(core, address, op == "w")    return {"accesses": len(trace), "misses": caches.misses, "invalidations": caches.invalidations}def time_ns(stats):    return (stats["accesses"] - stats["misses"]) * HIT_NS + stats["misses"] * MISS_NSfor name, stride in (("packed", 8), ("padded", 64)):    stats = run_trace(update_trace(4, 50, stride), 4)    print(name, stats, time_ns(stats), "ns")

packed {'accesses': 200, 'misses': 200, 'invalidations': 199} 12000.0 ns
padded {'accesses': 200, 'misses': 4, 'invalidations': 0} 436.0 ns

詰めた場合は、200回の書き込みがすべてミスし、そのうち199回が直前の書き手を無効化して12,000 nsです。パディングすると、各コアが自分のラインにカウンタを持ち、最初に4回のコールドミスがあるだけで、以降はすべての書き込みがヒットし、無効化はなく、436 nsです。算術はまったく同じなのに27倍速くなります。4つのコアがラインを奪い合わなくなったからです。

各カウンタに専用のラインを与えるには、カウンタ間の距離をライン長の倍数にする必要があるので、要素のサイズを次の64の倍数に切り上げます。8バイトのカウンタは64バイトを使い、56バイトが無駄になります。65バイトの要素は128バイトです。次の関数が切り上げを行います。

def padding_needed(item_bytes):    return math.ceil(item_bytes / LINE_BYTES) * LINE_BYTESprint([padding_needed(size) for size in (8, 63, 64, 65, 100)])

[64, 64, 64, 128, 128]

ラボでは4つのコアがそれぞれ担当する取引日を数え、SPYの表のi番目の日は「曜日 % 4」のコアに割り当てられます。最初の1,000日が、日付順に書き込みを駆動します。日はカレンダーどおりに進むので、同じコアが続けて書くことはまれで、ラインは何度も奪われます。カウンタを詰めると1,000回の書き込みのうち818回がミスし、817回が他のコアを無効化します。パディングすると、最初の4回の書き込みだけがミスします。

ラボでは、コヒーレンスのモデル、指定した間隔でのコアごとのカウンタのトレース、再生、パディングの規則、時間モデル、そしてSPYの日付での研究を作ります。

• 関数 · 問い前提
• CoherentCaches(n_cores).access(core, address, write)ヒットかミスか、誰がコピーを失うか？単純な算術
• counter_address(core, stride_bytes)コアのカウンタはどこにあるか？単純な算術
• update_trace(n_cores, n_updates, stride_bytes)コアはどんな書き込みをするか？counter_address
• run_trace(trace, n_cores)ミスと無効化は何回か？CoherentCaches
• padding_needed(item_bytes)要素はどれだけ離す必要があるか？単純な算術
• time_ns(stats)実行にどれだけかかるか？ヒットとミスのコスト
• study(bars)SPYの日付でフォルスシェアリングはどれだけ高くつくか？run_tracepadding_neededtime_ns

次のトピック：フォルスシェアリングは、同じソケットを共有するコアの話でした。2ソケットのマシンではメモリ自体が分かれ、あるコアに近い部分と遠い部分ができます。NUMAの影響では、ページをノードに配置し、ローカルとリモートのアクセスを数え、その差をコストで見積もります。