小さなキャッシュを一つ決める
キャッシュに値が入るかどうかを、容量の合計だけで判断すると、説明できない失敗が残ります。例えば空きのある集合がほかにあっても、ある集合へアクセスが集中すれば、そこにある値を追い出す必要があります。このガイドでは、メモリのアドレスを、ライン内の位置、集合番号、タグへ分け、どのアクセスが競合するかを紙で追います。前提は二進数の桁の重みと、キャッシュラインが近くのバイトをまとめて運ぶという考え方です。CPUとメモリ階層の主教材を読んだ後に進んでください。
説明用のキャッシュは、ラインが64バイト、集合が4個、各集合に2本のラインを置ける2 way構成です。データ部分の容量は64×4×2=512バイトになります。タグや有効ビットなどの管理情報はこの512バイトへ含めません。メモリはバイト単位でアドレスを付け、対象のアクセスは一つのライン内に収まるものとします。この模型は実CPUの全キャッシュを再現するものではありません。仮想アドレスと物理アドレスの使い分け、複雑な索引、先読みは後で考えます。
アドレスを三つの役割へ分ける
アドレスをaとすると、ライン内のバイト位置はaを64で割った余りです。ライン番号はaを64で整数除算した値で、集合番号はそのライン番号を4で割った余りになります。タグはライン番号を4で整数除算した値です。したがって、offset=a mod 64、set=floor(a/64) mod 4、tag=floor(a/256)と計算できます。ここでtagはデータそのものではなく、その集合の各wayへどのメモリラインを入れているかを見分ける情報です。
64は2の6乗なので、下位6ビットがライン内の位置を表します。集合は4個なので、次の2ビットが集合番号です。それより上がタグになります。例えばアドレス320は、320=1×256+1×64+0ですから、タグ1、集合1、位置0です。16進数の見た目だけで判断せず、まずバイト数へ戻して分けましょう。同じ集合番号でもタグが違えば別のラインです。逆に位置だけが違い、タグと集合番号が同じなら、同じラインの別のバイトを指しています。
同じラインへのアクセスを照合する
表の0と8は、どちらもタグ0、集合0です。キャッシュが空のときにアドレス0を読むと、0から63までのラインを持ってくると考えます。続いて8を読めば、そのラインが残っている限りヒットします。8バイトの整数を読んだから、8バイトだけを運んだとは限りません。この違いが空間局所性を説明します。一方、64を読むと集合1へ別のラインが入り、0のラインを置く場所とは直接競合しません。
表の256と512は集合0へ戻りますが、タグは1と2です。ラインの開始アドレスが256バイトずつ離れると、4集合を一周して同じ集合へ来るためです。2 wayなら集合0へ同時に置けるのは二つのタグまでです。これは512バイトという全容量だけからは見えません。0、256、512の三つのラインのデータは合計192バイトですが、この構成では三つを同時に集合0へ置けません。どのwayを選び、どれを追い出すかが次の問題になります。
| アドレス(B) | 位置 | 集合 | タグ |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 8 | 8 | 0 | 0 |
| 64 | 0 | 1 | 0 |
| 256 | 0 | 0 | 1 |
| 320 | 0 | 1 | 1 |
| 512 | 0 | 0 | 2 |
置換規則を決めて履歴を追う
ここでは各集合に厳密なLRUを仮定し、最も長く参照していないラインを追い出します。空の状態から0、256、0、512、256の順に読むとしましょう。最初の0と256はミスですが、二つのwayへ両方を置けます。三回目の0はヒットし、タグ0が最近使った側になります。四回目の512はタグ2なのでミスです。この時点で古いのはタグ1ですから、256のラインを追い出します。最後の256は、直前に追い出されたためミスになります。
この履歴ではヒット1回、ミス4回です。最初の二回は初めて読むためのミスで、後半には集合の競合が関わります。ただし、ミスの分類を厳密に行うときは、比較対象となる同容量の完全連想キャッシュなども定義します。「繰り返しだから全てヒット」「全容量未満だから追い出さない」という予測が、どの行で崩れるかを確認することが先です。実CPUが厳密LRUを使うと仮定してはいけません。置換方式が変われば、同じ入力列でも最後に残るタグは変わる可能性があります。
実際の配列へ結び付ける
行優先の二次元配列で、各行の長さが256バイトなら、同じ列を次の行へたどるたびに、この模型では同じ集合へ移ります。行の長さを変えると、集合の使い方も変わります。しかし「1要素だけ余分に確保すれば必ず速い」という結論にはなりません。値の型、各行の開始位置、走査範囲、複数配列の対応を含めてアドレスを計算し、同じ結果を得ていることを確認します。データ配置の変更にコピーが必要なら、その費用も利用場面に含めます。
実験では行と列の走査、strideの変更、開始位置の変更を別々に扱います。これらは、同じバイト列をどの順に使うか、どのバイトをそもそも使うか、ラインをまたぐかという異なる問いです。同時に変えると、時間差の理由を切り分けにくくなります。まず模型から競合しそうな列を予測し、次にCのコードで同じ入力とチェックサムを保ちます。実時間が予測どおりでなくても計算を隠さず、コンパイラの変換や実キャッシュ構成との違いを調べる材料にしてください。
模型と実機の間にある前提を確認する
実際のCPUには複数階層のキャッシュがあり、ある階層のミスが直ちに主記憶へのアクセスになるとは限りません。仮想アドレスから物理アドレスへの変換、ページサイズ、共有キャッシュの索引、先読み、ほかの実行単位による追い出しも結果へ影響します。アドレスの下位ビットを分けただけで、全階層の配置を証明したとは扱いません。キャッシュの仕様が必要な判断には、対象モデルの公式資料と、その環境で読める構成情報を使います。
測定にはコンパイラ版、最適化設定、CPUとISA、配列のサイズ、アクセス数、反復、出力の利用を残します。時間差しか取れなかった場合は、キャッシュミスの実測値を書き足しません。命令数、TLB、先読み、CPU周波数や実行待ちも同じ時間へ現れるためです。仮想マシンでは、公開されたCPU名とホスト全体の配置が一致するとも限りません。模型の予測、実行したコード、観測した時間、取得できたカウンタを別の欄に置くと、どこまで説明できたかを読み手も判断できます。
容量とwayを別々に変える
元の模型でwayだけを4へ増やすと、集合番号の計算は変わらず、集合0へ四つのタグを置けます。一方、集合を8へ増やすと集合番号に使うビットが増え、256の対応先も変わります。どちらもデータ容量を増やす変更ですが、同じアドレス列の競合へ及ぼす作用は同じではありません。容量512という一つの値から、集合数とwayを一意には決められないことも確認してください。仕様を調べるときは容量だけでなく、ライン長と連想度を合わせて読みます。
条件を変える課題と解答
課題は、同じ64バイトのラインで集合を8個、2 wayへ変えたときに、アドレス0、256、512が競合するかを説明することです。解答では位置に6ビット、集合に3ビットを使い、タグはfloor(a/512)になります。0は集合0・タグ0、256は集合4・タグ0、512は集合0・タグ1です。三つのライン全てが同じ集合へ来るわけではなく、集合0へ来る二つも2 wayへ収まります。空からこの三つを読んだだけなら、追い出す必要はありません。容量は1024バイトへ増えていますが、判断には各集合の対応も使いました。
追加課題として、元の4集合へ戻し、アクセスを0、64、128、192へ変えてください。四つは別の集合へ一つずつ入ります。これに対し0、256、512、768は一つの集合へ集まるため、2 wayでは同時に保持できません。どちらも四つのラインを読んでいるのに結果が違う理由を、タグと集合で説明できれば到達点です。続く行列走査とstrideの実験では、この予測を出発点に、実際に作られたコードと時間を比較します。模型から時間の倍率まで計算したことにはしないでください。