概要

参照の局所性は、プログラムがメモリへアクセスする際のパターンを表す。特定のデータ項目やアドレスが繰り返し使われたり、互いに近い場所が連続して参照されたりする。ハードウェアとソフトウェアはこうした性質を利用し、CPUレジスタやキャッシュから主記憶、ディスクに至るメモリ階層全体で、平均アクセス時間の短縮とスループット向上を図る。簡潔な入門としてはこの概要を参照するとよい。

主な種類

局所性には、広く認められている2つの形がある。

  • 時間的局所性：ある位置が一度参照されると、近い将来に再び参照されやすい。例として、ループカウンタや頻繁に使う変数がある。
  • 空間的局所性：あるメモリ位置が参照されると、その近くのアドレスも近いうちにアクセスされやすい。例として、配列を順番に走査する処理がある。

歴史と理論

局所性の考え方は、何十年にもわたりコンピュータアーキテクチャとオペレーティングシステムを導いてきた。ワーキングセット・モデルや、仮想記憶管理で局所性を活用するための理論的研究は1960年代に発展し、キャッシュやページングの方針が性能に大きく影響しうる理由を説明する助けとなった。基礎資料や形式的なモデルについては、さらなる背景のような資料が参考になる。

実用上の重要性と例

局所性は実世界の多くの振る舞いに影響する。CPUキャッシュは最近使われたキャッシュラインを保持して時間的局所性を活用し、プリフェッチャは隣接ブロックを読み込んで空間的局所性を活用する。仮想記憶管理では、あるプロセスのワーキングセットをRAM上に保つ。簡単な例として、巨大な配列を順番に反復処理するのは空間的局所性を、厳密なループ内で同じ変数を繰り返し参照するのは時間的局所性を使っている。

最適化と手法

プログラマやコンパイラは、データ構造や制御フローを組み替えることで局所性を改善する。代表的な手法には、行列に対するブロッキング（タイリング）、連続したデータ配置、キャッシュに適した順序で配列へアクセスするためのループ交換、ソフトウェア・プリフェッチなどがある。これらはキャッシュヒットを増やし、高コストなメモリ待ちを減らすことを目的とする。

限界と考慮点

すべてのワークロードが強い局所性を示すわけではない。規則性の低いアクセスパターン、大きなランダムデータ集合、ポインタ主体の構造は、キャッシュの有効性を下げることがある。適切な最適化を選び、性能測定を正しく解釈するには、ワークロードの特性とメモリ階層を理解することが重要である。