キャッシュ階層

CPU は通常、小さく速いキャッシュから調べ、最後に DRAM へ進む。L1、より大きい L2、共有 L3、主記憶という構成がよく使われる。同じ load でも、どこにデータがあり、検索やリクエストがどう重なるかでコストが変わる。本課は各段の遅延を順に足すモデルを使う。

転送単位は一語ではなく隣接データをまとめたキャッシュラインだ。一般的な x86 と多くの ARM コアは 64 バイト、Apple silicon は 128 バイトの例が多いが、機種を確認する。一行を持って来て隣接語を使えば転送を共有でき、一語だけ使って次の行へ移ると利用率が低い。

行優先の二次元配列を行方向に走査すれば同じラインを続けて使える。同じ要素を列方向に読むと、一行から一語だけ使い、再訪前に置換されることがある。加算数が同じでも、配列、容量、順序によってメモリ交通と時間が変わる。

階層の仕組み

モデルは 64 語を 4 語ずつ 16 ラインへ分ける。L1 は 4 ライン、L2 は 8、L3 は全 16 を持ち、その下に DRAM がある。既定 L1 はダイレクトマップだ。

w9 はライン 9//4=2、内部オフセット 9%4=1。既定 L1 のアドレス下位 2 ビットが offset、次の 2 が index、残りが tag になる。2 のべきの固定配置ではフィールドの切り分けは配線に対応し、// と % は汎用除算器の動作ではなく説明用だ。

index が L1 の許可スロットを選ぶ。ライン #2 は二進 index 10 にしか入れない。有効ビットと tag で、そのスロットを共有する四つのメモリラインを区別する。有効かつ tag 一致ならヒットし、そうでなければ L2、L3、DRAM と進み、最初の一致で止める。

回答はライン全体で、欠けていた上位階層へ補充する。DRAM から戻る場合は L3、L2、L1 へ入れる。L1 の指定位置に別ラインがあれば置換する。

調べた段は未検出でも遅延を払う。L1=4、L2=12、L3=40、DRAM=200 サイクルなので、合計は次になる。

直列検索モデルの数値であり、任意の実ハードウェアの測定値ではない。

ステップ実行

既定は w0–w11 の 12 語を順に読み、L1 はダイレクトマップ。

1. w0：ライン #0、offset=0、index=00、tag=00。L1 は空、L2 と L3 にもなく、初回の強制ミスで 4+12+40+200=256 サイクル。w0、w1、w2、w3 が一緒に戻り、三段へ入る。L1 は空だったので追い出しはない。
2. w1：同じ #0 の offset=1。index と tag は同じで、有効な L1 に一致する。4 サイクルで、下から取り直さない。
3. w2、w3：各 4 サイクル。最初に取った四語をすべて使えた。
4. w4：ライン #1、index=01 で別スロット。初回ミスに 256 を払い、w4–w7 を取得する。
5. w5–w7：各 4 サイクルのヒット。
6. w8：#2 の初回ミスで 256。w9–w11 は各 4。

12 読み取りが 3 ラインにまとまり、3 ミスと 9 ヒット、ミス率 25%。合計 3×256+9×4=804 サイクルだ。

最終フレームは stride 4 と比較する。w0、w4、w8、…、w44 の 12 読み取りは 12 個の異なるラインから一語ずつ使う。すべて初回ミスで 12×256=3072、順次版の約 3.8 倍になる。

二次元の列走査と関係するが、同一実験ではない。実際の行・列走査は同じアドレスを別順で読む。このモデルの L3 は全メモリを持つため、固定アドレス集合の初回 DRAM 取得数は順序によらない。そこでアドレス集合を変え、異なるライン数、各行の利用量、再利用までに保つ必要がある範囲を示す。

ミスの値段は一つではない

conflict は w0 と w16 を交互に 10 回読む。#0 と #4 はともに L1 index 00（4%4=0）へ入る。使うのは二行だけで残り三スロットは空なのに、毎回追い出し合い L1 は 0/10 ヒットだ。

最初の二回だけ DRAM を使い、その後 8 回は L2 ヒットで 16 サイクル。L1 から消えても機械全体から消えたわけではない。L1 ミス率だけでは下位ヒットの利点を読めない。

台帳は L1 ミスを三分類する。

• 強制ミス：まだ先取りされていないラインへの初回需要アクセス。
• 競合ミス：実際のマッピングでは追い出したが、同容量のフルアソシアティブなら保持できた。
• 容量ミス：同容量のフルアソシアティブでもミスする。

シミュレーターはフルアソシアティブの参照 L1 を並行して維持し、その結果で分類する。

2-way に変えると容量は 4 ラインのまま、2 セット×2 ウェイになる。index は 2 から 1 ビット、tag は 3 ビットへ増える。各ラインには所属セット内で二つの置き場所があり、同じ競合列は最初の二回だけミス、残り 8/10 がヒットする。

連想度、ラインサイズ、階層数はハードウェアの選択で、プログラムは主に配置と訪問順を変えられる。容量増加も index を変えて特定の競合を消す場合があるが、空きスロットがあるだけでは競合ラインがそこを使えるとは限らない。

working set は 10 ラインを二周し、L1 の 4、L2 の 8 を越える。第二周は毎回 L1 と L2 を外し、L3 の 56 サイクルで答える。LRU の循環置換で再訪予定のラインが既に消えており、2 ウェイ化だけでは容量不足を解決しない。実キャッシュは別方式や近似置換も使う。

境界ケース

• 一語への初回アクセスでも、そのラインは既にある場合がある。w0 の後の初 w1 はヒットでき、プリフェッチも先に運べる。ベンチマークは冷開始と定常状態を分ける。
• w5 を 8 回読むと最初 256、残り七回は各 4。下位取得を避けても L1 のコストはゼロではない。
• 一セットが満杯でも全体は空き得る。既定の競合列では三スロットが空のまま一つだけが往復置換する。
• 10 ラインを 8 ライン LRU へ循環させると毎再訪がミスする。少し超過しただけでも再利用をすべて失い得る。
• モデルの L3 は全 64 語を持ち、各行は初回以降 DRAM を使わない。実際は他の仕事や無効化で追い出されず、まだ常駐する場合だけだ。

よくある間違い

• 容量だけで競合を説明する。増量でマッピングが変わることもあるが、この例は同容量の 2 ウェイで直る。セットと配置を見る。
• ミスを DRAM の 200 と数える。本モデルは途中の検査も払い 256。実機の重なりや測定境界に、そのまま加算を当てはめない。
• load 数だけを数え、ラインと再利用を数えない。同じ反復数でも訪問ライン数は違い得る。
• 既定配置で上位ビットを index にする。中間ビットは隣接行を別セットへ分ける。上位を使うと #0–#3 が同セットに集まり得る。実機のハッシュなど別設計を否定する規則ではない。
• ライン転送を細部と見なす。同容量でも一語ずつしか取らなければ、既定の異なる 12 語は各初回ミスとなり、3 回では済まない。
• 構造体の一フィールドだけを転送したと思う。単位はラインだ。ホットなフィールドをまとめたり、状況に応じてロックと共有データを分けたりすると局所性やコヒーレンス交通が変わる。効果は測る。

モデルの範囲

実ラインはバイト単位で、tag 幅はアドレスと構造による。タグとデータの並列参照、未完了ミス状態によるリクエストの重なり、プリフェッチなどで動作は変わる。本課は書き込みを扱わず、dirty、write-back/write-through、write allocation はない。仮想アドレス、TLB、多コアコヒーレンスも省き、L2 と L3 のフルアソシアティブ LRU は教材上の設定だ。

同じ行優先配列で行・列走査を測定できる。以下は対応イベントを持つ Linux perf 環境の例。

perf stat -e cycles,L1-dcache-loads,L1-dcache-load-misses ./walk row
perf stat -e cycles,L1-dcache-loads,L1-dcache-load-misses ./walk col

サイクル、load、ミスを比べ、コンパイル結果と機械による差を確認する。macOS には xctrace record --template 'CPU Counters' があるが、テンプレートやイベントは環境依存。valgrind --tool=cachegrind --cache-sim=yes は対応プラットフォームでハードウェアカウンターなしの模擬解析を行え、実行オーバーヘッドは大きい。全環境で同じ道具が動くわけではない。