キャッシュラインと空間的局所性

キャッシュは1バイトだけを取ってくることはありません。64バイトの1ライン全体を取ってくるので、いま読んだ値の隣の値はすでにそこにあります。この講義ではキャッシュを作り、順番に読むほうが1ラインずつ飛ぶより8倍安いことを示し、価格の表に当てはめます。

メモリから取ってくるコストは、何バイト頼んでも同じです。そこでハードウェアは一度にたくさん頼みます。メモリは64バイトのブロックに切られ、キャッシュは必ずブロック丸ごとを読み込み、追い出します。キャッシュまで64バイトを運ぶエレベーターを想像してください。どうせ上がるなら、隣の値を一緒に乗せてもタダで、あとでそれが必要になったときにはもう上にあります。

どのバイトにもアドレスという、場所を示す番号があります。アドレスのラインを求めるには、ライン長で割って余りを捨てます。次のコードは4つのアドレスのラインを表示します。

line_bytes = 64for address in (0, 63, 64, 130):    print(address, "is in line", address // line_bytes)

0 is in line 0
63 is in line 0
64 is in line 1
130 is in line 2

アドレス0と63は同じライン0にあるので、一方を読み込めばもう一方はタダです。アドレス64はライン1の先頭で、130はライン2にあります。このトピックのすべては、この整数除算から導かれます。

最も単純なキャッシュは、保持できるラインごとに1つのスロットを持つ表です。ライン64バイトの32 KBキャッシュには512個のスロットがあります。メモリの各ラインは、剰余（ライン番号をスロット数で割った余り）で決まる1つのスロットにだけ入れます。これがダイレクトマップ方式のキャッシュです。多くのラインが1つのスロットを共有するので、スロットは今どのラインを持っているかを示すタグも覚えています。

1. 1
   ラインを求めるアドレスをライン長で割ります。
2. 2
   スロットを求めるライン番号をスロット数で割った余りを取ります。
3. 3
   タグを比べるスロットがこのラインを持っていればヒットです。
4. 4
   ミスなら入れ替えるラインをスロットに読み込み、前にあったラインは忘れます。

これがキャッシュのすべてです。次のクラスは15行の完全に動く版です。隣り合う4つの値、次のライン、そしてアドレス0に戻る読み出しを行います。

def line_of(address, line_bytes):    return address // line_bytesclass Cache:    def __init__(self, size_bytes, line_bytes):        self.line_bytes = line_bytes        self.n_lines = size_bytes // line_bytes        self.tags = [None] * self.n_lines        self.hits = 0        self.misses = 0    def access(self, address):        line = line_of(address, self.line_bytes)1        slot = line % self.n_lines        if self.tags[slot] == line:2            self.hits += 1            return True        self.misses += 1        self.tags[slot] = line        return Falsecache = Cache(size_bytes=512, line_bytes=64)reads = [0, 8, 16, 24, 64, 72, 0, 512, 0]print([cache.access(a) for a in reads])print(cache.hits, "hits and", cache.misses, "misses")

[False, True, True, True, False, True, True, False, False]
5 hits and 4 misses

1. 1スロットはライン番号をスロット数で割った余りです。
2. 2ヒットとは、スロットのタグがまさにこのラインだということです。

フラグのリストを読みましょう。最初の読み出しはミスしてライン0を読み込み、続く3つはライン0にあるのでヒット、64はミスしてライン1を読み込み、72はヒット、0に戻るとライン0が追い出されていないのでまたヒットします。次にアドレス512はライン8で、これもスロット0（8を8で割った余り）に入るため、ライン0を追い出し、最後の0番地の読み出しはまたミスします。1回のコンフリクトでミスが1つ増えたのです。

ではキャッシュを使ってみましょう。float64の値は8バイトなので、1ラインには8個入ります。配列を順に読むと、各ラインの最初の読み出しがミスし、続く7つがヒットするので、8回に1回のミスです。ストライド、つまり読み出しの間に一定数の値を飛ばして読むと、読み出しは別々のラインに当たります。次のコードは、ストライド1、2、4、8、16個のミス率を測ります。

def sequential_trace(n, elem_bytes):    return [i * elem_bytes for i in range(n)]def strided_trace(n, elem_bytes, stride):    return [i * stride * elem_bytes for i in range(n)]def miss_rate(trace, size_bytes=32768, line_bytes=64):    cache = Cache(size_bytes, line_bytes)    for address in trace:        cache.access(address)    return cache.misses / len(trace)n = 4096for stride in (1, 2, 4, 8, 16):    print("stride", stride, "values:", miss_rate(strided_trace(n, 8, stride)))

stride 1 values: 0.125
stride 2 values: 0.25
stride 4 values: 0.5
stride 8 values: 1.0
stride 16 values: 1.0

ストライドを2倍にするたびにミス率も2倍になり、1.0に達します。8個飛ばしだと64バイト、つまりちょうど1ライン分なので、すべての読み出しが新しいラインを開き、キャッシュは何も節約しません。それより大きなストライドでもこれ以上悪くならず、同じになるだけです。法則は次の式のとおりです。

日足の表には1日あたり5つの数（始値、高値、安値、終値、出来高）があります。多くのプログラムのように行ごとに保存すると、1日の5つの数が並びます。終値だけを読むなら、読み出しの間に4つの値を飛ばすことになり、ストライドは5、つまり40バイトです。列ごとに別々に保存すれば終値が連続し、ストライドは1です。数も読み出しも同じで、レイアウトだけが違います。

closes = 1000as_column = miss_rate(sequential_trace(closes, 8))as_rows = miss_rate(strided_trace(closes, 8, 5))print("column layout:", as_column)print("row layout:   ", as_rows)

column layout: 0.125
row layout:    0.625

終値が間隔を空けて並ぶと、ミスする読み出しが5倍になります。プログラムの答えは変わらず速度だけが変わり、プロファイラの計算の行にも現れません。余分な時間はメモリ待ちに使われているのです。

ラボでは、いま読んだ部品を同じ順序で作り、最後に実際のSPYの表での研究を行います。

• 関数 · 問い前提
• line_of(address, line_bytes)このアドレスはどのラインにあるか？整数除算
• Cache(size_bytes, line_bytes).access(address)この読み出しはヒットか？line_of
• sequential_trace(n, elem_bytes)順番に読むとどのアドレスに触れるか？単純な算術
• strided_trace(n, elem_bytes, stride)飛びながら読むとどのアドレスに触れるか？単純な算術
• miss_rate(trace, size_bytes, line_bytes)トレースのうちミスする割合は？Cache
• study(bars)SPYの終値に行レイアウトはどれだけ余計にかかるか？miss_ratestrided_trace

次のトピック：ダイレクトマップのキャッシュには、この講義でも触れた弱点、つまり同じスロットを共有するライン同士のコンフリクトがあります。連想度とコンフリクトミスでは、各スロットに複数の置き場所を与え、行が4096バイト間隔の表がなぜキャッシュを台無しにしうるかを見ます。