概念・定理図鑑 · 基礎から応用へ

参照局所性:時間と空間の二つの近さ

同じデータの再利用と、近接したデータへのアクセスを分けて考え、キャッシュが効く条件を具体例で捉えます。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 時間的局所性と空間的局所性
  2. キャッシュラインで考える
  3. ループの順番を変える例
  4. 局所性だけでは性能は決まらない
  5. 再利用距離を手で追う
  6. この記事をロゲイアに質問する理解を確かめる

時間的局所性と空間的局所性

参照局所性とは、アクセス先が時間やアドレス空間の中で偏る性質です。時間的局所性は同じ場所を短い間隔で再び使うこと、空間的局所性は近くの場所を続けて使うことを指します。ループで繰り返し読む係数は前者、配列を先頭から順に読む操作は後者の例です。どちらも「すべてのアクセスが等しく起こる」という仮定から外れるため、小さい高速な記憶領域が役に立ちます。

キャッシュラインで考える

CPUキャッシュは通常、個々の変数より大きいキャッシュラインを単位としてデータを扱います。例としてラインを64バイト、整数を4バイトとすると、整列した連続16要素が同じラインに収まります。先頭の読み出しでラインを取得できれば、その後の近接要素は同じラインから読める可能性があります。ただし実際のラインサイズ、整列、プリフェッチの有無は機種によって異なり、この数値は説明用の条件です。

ループの順番を変える例

行優先で配置された二次元配列では、同じ行を横に進む走査は連続したアドレスを使います。列を固定して行を飛び越える走査では、行幅に応じた大きな間隔が生まれます。どちらも要素数が同じなら計算量は同じですが、必要なライン取得回数は変わり得ます。比較実験では配列の配置方式、要素サイズ、作業集合の大きさを揃え、時間だけでなくキャッシュミスの計測も併せて解釈します。

局所性だけでは性能は決まらない

局所性が良くても、作業集合がキャッシュ容量を超えたり、複数のアドレスが同じ配置先を競ったりするとミスは増えます。複数コアが同じラインを書き換える場合は、データの受け渡しによる負担も発生します。局所性は性能を考える有力な手掛かりですが、処理時間を単独で予測する公式ではありません。アルゴリズムの処理量やメモリ帯域、測定時の他の負荷も分けて確かめる必要があります。

再利用距離を手で追う

容量2ラインの完全連想キャッシュで、LRU置換、初期状態は空と仮定します。参照列A、B、A、C、Aでは、最初のAとBがミス、次のAがヒットです。Cを入れる際は最近使わなかったBを追い出すので、最後のAもヒットし、計3ミス2ヒットになります。参照列A、B、C、A、Bでは5回すべてミスになります。同じ五つの参照でも、再利用までに間に入る別ラインの数が変わると結果が変わります。これは置換規則を固定したモデルの計算であり、実機のプリフェッチや集合の競合を含む測定値ではありません。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 8

AI基盤へ進む · STEP 5

学習コースから次を選ぶ