連想度とコンフリクトミス

1ラインにつき1スロットのキャッシュでは、同じスロットを共有する忙しい2つのラインが何度も互いを追い出します。各スロットに複数のウェイを持たせれば問題はほぼ消えますが、表の行がちょうど4096バイト間隔の場合は別です。この講義ではセットアソシアティブキャッシュを作り、2のべき乗の行サイズが読み出しの100%をミスさせうることを示します。

前のトピックのダイレクトマップのキャッシュでは、各メモリラインのスロットがちょうど1つに決まっていました。同じスロットに入る2つのライン、たとえば8スロットのキャッシュでライン0とライン8を使い続けると、一方を読むたびに他方が追い出されます。ほかの7スロットが空いていてもです。キャッシュの大きさに問題はなく、ラインたちが狭すぎる場所を取り合っているのです。この種のミスをコンフリクトミスと呼びます。

解決策はスロットをグループにまとめることです。スロットをセットにまとめ、セット内の各スロットをウェイと呼びます。メモリラインは前と同じ剰余で決まる1つのセットに属しますが、そのセットのどのウェイにも入れます。衝突する2つのラインは、2つ入る余地のあるセットを共有するようになります。セットの数は大きさから決まります。

アドレスは3つの部分に分かれるようになります。オフセットはライン内のバイト位置、セットインデックスはラインが属するセット、タグはライン番号の残りで、あるウェイがこのラインを持っているかを調べるのにキャッシュが比べる値です。次の関数は、ライン64バイト・64セットのキャッシュ向けにアドレスを分割します。

def split_address(address, line_bytes, n_sets):    line = address // line_bytes    return line // n_sets, line % n_sets, address % line_bytes1print(split_address(74565, 64, 64))

(18, 13, 5)

1. 1タグ、セットインデックス、オフセットは、それぞれアドレスの整数除算か剰余です。

アドレス74565はライン1165の5バイト目です。ライン1165はセット13（1165を64で割った余り）に入り、ライン番号の残りの18がタグです。セット13になるラインは、タグにかかわらず、そのセットの8つのウェイを取り合います。

セットが満杯で新しいラインが来たら、どれかが出ていかなければなりません。通常の規則はLRU、つまり最も最近使われていないラインを追い出すことです。各セットは、最も古く使われたものから最近のものへ並べたPythonのリストとして持てます。

1. 1
   セットを求めるライン番号をセット数で割った余り。
2. 2
   全ウェイを調べるヒットなら、そのラインを最近使った側の端に移します。
3. 3
   ミスなら追加する新しいラインを最近使った側の端に置きます。
4. 4
   最古を捨てるセットのライン数がウェイ数を超えたら、先頭を取り除きます。

これがキャッシュの全体です。末尾の実行では、ライン64バイトの256バイトのキャッシュで衝突する2つのライン（アドレス0と256）を、まず1ウェイ、次に2ウェイで読みます。

class SetAssocCache:    def __init__(self, size_bytes, line_bytes, ways):        self.line_bytes = line_bytes        self.ways = ways        self.n_sets = size_bytes // (line_bytes * ways)        self.sets = [[] for _ in range(self.n_sets)]        self.hits = 0        self.misses = 0    def access(self, address):        line = address // self.line_bytes        lines = self.sets[line % self.n_sets]        if line in lines:            lines.remove(line)            lines.append(line)1            self.hits += 1            return True        self.misses += 1        lines.append(line)        if len(lines) > self.ways:            lines.pop(0)2        return Falsefor ways in (1, 2):    cache = SetAssocCache(size_bytes=4 * 64, line_bytes=64, ways=ways)    flags = [cache.access(a) for a in [0, 256, 0, 256, 0, 256]]    print(ways, "way:", flags)

1 way: [False, False, False, False, False, False]
2 way: [False, False, True, True, True, True]

1. 1ヒットしたラインを末尾へ移すとリストの順序が保たれ、先頭は常に最も古く使われたものになります。
2. 2満杯のセットは先頭のエントリ、つまり最も古く使われたラインを失います。

1ウェイでは2つのラインが互いを追い出し、6回の読み出しがすべてミスします。2ウェイなら2つのラインがセットに収まり、最初の2回のコールドミスのあとは毎回ヒットします。ウェイを1つ足すだけで、このパターンのコンフリクトミスはすべて消えました。

ここからが落とし穴です。float64が512列の表は、1行がちょうど4096バイトです。1列を読むとはアドレス0、4096、8192、……を読むことです。このキャッシュではセットインデックスはライン番号を64で割った余りで、4096バイトはちょうど64ライン分なので、これらのアドレスはすべて同じセットインデックスになります。次のコードは、行サイズ4096バイトと、それに1ライン足した4160バイトの場合の最初の6行のセットを表示します。

n_sets = 64for row_bytes in (4096, 4160):    sets = [(i * row_bytes // 64) % n_sets for i in range(6)]    print(row_bytes, "->", sets)

4096 -> [0, 0, 0, 0, 0, 0]
4160 -> [0, 1, 2, 3, 4, 5]

行が4096バイトだと、列のすべての終値がセット0を取り合います。4160バイトならセット0、1、2、3、……と順に回り、キャッシュ全体を使います。次のコードは96個の終値を2回読み、1、2、4、8ウェイのミス率を測ります。

def column_trace(n_rows, row_bytes, passes):    return [i * row_bytes for i in range(n_rows)] * passesdef miss_rates_by_ways(trace, size_bytes, line_bytes, ways_list):    rates = {}    for ways in ways_list:        cache = SetAssocCache(size_bytes, line_bytes, ways)        for address in trace:            cache.access(address)        rates[ways] = cache.misses / len(trace)    return ratesfor row_bytes in (4096, 4160):    print(row_bytes, miss_rates_by_ways(column_trace(96, row_bytes, 2), 32768, 64, [1, 2, 4, 8]))

4096 {1: 1.0, 2: 1.0, 4: 1.0, 8: 1.0}
4160 {1: 0.5, 2: 0.5, 4: 0.5, 8: 0.5}

パディングした表は最初の走査でしかミスせず、ウェイ数に関係なく全読み出しの0.5です。揃った表は8ウェイでも毎回ミスします。96ラインには96個の置き場所が必要なのにセットは8個だからです。さらに、循環パターンではLRUが次に読むラインをいつも追い出すので、2回目の走査は何も見つけられません。ウェイを増やして効くのは、ライン数に届いてからです。

ラボは講義の順に進みます。アドレスの分割、LRUキャッシュ、2種類のトレース、ウェイ数ごとの比較、そして実際のSPYの表での研究です。

• 関数 · 問い前提
• split_address(address, line_bytes, n_sets)アドレスのタグ・セット・オフセットは？整数除算
• SetAssocCache(size_bytes, line_bytes, ways).access(address)複数ウェイのLRUキャッシュでこの読み出しはヒットか？LRU順のラインのセット
• conflict_trace(n_lines, line_bytes, n_sets, rounds)どのアドレスが1つのセットで衝突するか？単純な算術
• column_trace(n_rows, row_bytes, passes)1列を読むとどのアドレスに触れるか？単純な算術
• miss_rates_by_ways(trace, size_bytes, line_bytes, ways_list)ウェイを増やすとミス率はどう変わるか？SetAssocCache
• study(bars)行間隔4096バイトのコストは？column_tracemiss_rates_by_ways

次のトピック：衝突しなければキャッシュは正しいラインを保持できるようになりましたが、ラインはどのくらいの間役に立つのでしょうか。時間的局所性とワーキングセットでは、値がどれだけ早く再び読まれるかを測り、プログラムが収まり始めるキャッシュサイズを見つけます。