参照の局所性

参照の局所性（さんしょうのきょくしょせい、英: locality of reference）とは、1つのリソースに複数回アクセスする処理に関する情報工学上の概念である。

局所性の分類

参照の局所性には以下の3種類が存在する。

時間的局所性（英: temporal locality）: ある時点で参照されたリソースが近い将来にも再び参照される可能性が高いことを表す概念
空間的局所性（英: spatial locality）: あるリソースが参照されたとき、その近傍のリソースが参照される可能性が高いことを表す概念
逐次的局所性（英: sequential locality）: メモリが逐次アクセスされるという概念

これらの概念が真となるかどうかは、プログラムの作成方法に依存する。一般に関連するデータ群はメモリ内の近い位置に格納される。情報処理の一般的なパターンとして、ある項目を処理したら次へというように逐次的に処理が行われる。これが意味するのは、多くの処理をする場合に1つの項目に複数回アクセスすることになり、それによって時間的局所性が生じるということである。さらに次の項目に移るということは次の項目を参照するということであり、メモリ上の配置がまとまっていれば空間的局所性も生じる。

参照の局所性を増大させて利用することは最適化の一般的な技術である。これはメモリ階層の各レベルで行われている。ページング方式は空間的局所性を利用している。キャッシュは時間的局所性を利用している。キャッシュメモリは高速だが容量が小さいため、最近アクセスしたデータ(あるいはコード)とその近傍のみを格納することで大幅にシステム性能を向上させている。キャッシュ上のデータ群は必ずしも主記憶上で空間的に近いわけではなく、キャッシュラインという小さな単位でキャッシュに格納される。つまり、キャッシュラインのサイズを考慮するとここでも空間的局所性が利用されており、ある参照データのごく近い位置(同一キャッシュライン内)にあるデータが同時にキャッシュに置かれることで性能向上に寄与している。時間的局所性は最も基本的なレベルでも重要であり、最近の参照の結果はレジスタに保持される。また、ファイルシステムにおいても参照の局所性を利用した最適化が行われることがある。あるファイルの一部をリードしたプログラムはその続きをリードする可能性が高いため、最初のリード時に要求よりも大きめの単位で読み込んでおくといった空間的局所性を利用した最適化である。

メモリにおけるデータの局所性

データの局所性は普通のプログラムの典型的なメモリ参照の特徴である(ただし、典型的でないアクセスパターンも数多い)。データの局所性によって階層的なメモリ構成が性能向上に寄与することになる。コンピュータにおいてメモリはデータアクセスの速度によって階層化される。低レベルのメモリ階層は相対的に遅いが、大容量である。従って、プログラムはより上位のメモリ階層にキャッシュされることで高性能を発揮し、近い将来にアクセスされると予測されるデータをキャッシュすることでさらに高性能となる。これが理想であるが、実際には達成できないこともある。

典型的なメモリ階層は以下のようになっている(2006年現在の一般的なアクセス時間とサイズを以降の議論のために付記。個々の実際のシステムによってこれらの値は異なる):

レジスタ (8～32個のレジスタ) – 高速アクセス (0～1クロックサイクル)
一次および二次キャッシュ (128Kバイト～2Mバイト) – 若干遅いアクセス(10クロックサイクル)
主記憶装置(RAM) (128Mバイト～4Gバイト) – 遅いアクセス(100クロックサイクル)
ディスク(仮想記憶とファイルシステム) (1Gバイト～32Tバイト) – 非常に遅い(1,000～10,000クロックサイクル)
遠隔記憶(他のコンピュータまたはインターネット)(予算が許す限りの容量) – スピードは様々

最近のマシンでは、メモリ階層の下位レベルのブロックを1つ上位の階層に読み込む。これによって使用中のメモリ内容を置き換える場合、オペレーティングシステムは最もアクセスされていないと思われるデータを決定し、それを下位のメモリ階層に移す。この決定アルゴリズムはハードウェアをなるべく簡略化するために単純なものとなっていることが多いが、これも複雑化する傾向にある。

データの局所性の例

以下は行列 A と B の積を求める擬似プログラムの例である。

for i in 0..n
  for j in 0..m
    for k in 0..p
      C[i][j] = C[i][j] + A[i][k] * B[k][j];

大きな（キャッシュに入りきらない）行列を扱うとき、このアルゴリズムではメモリへのアクセスはかなり不連続的になる。C言語では同じ行の要素が連続してメモリ上に配置されるので、なるべく同じ行の要素に続けてアクセスした方が使用するメモリアドレスも連続的になり、空間的局所性が高い。つまり行のインデックスよりも列のインデックスの方が頻繁に変わるようにすると効率が上がる。j は2つの行列 B,C の列のインデックスなので、頻繁に変化する最も内側のループのカウンタにするとよい。このようにjとkのループを入れ替えることで、数学的には同値なアルゴリズムだが効率は上がり、特に行列が大きいと性能の向上は劇的なものとなる。

さらに時間的局所性を利用するには「ブロック化」と呼ばれる技法を使う。大きな行列を等しいサイズの部分行列に分け、短い時間に同じ部分行列を複数回参照する。

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE)
  for (kk = 0; kk < SIZE; kk += BLOCK_SIZE)
    for (jj = 0; jj < SIZE; jj += BLOCK_SIZE)
      for (i = ii; i < ii + BLOCK_SIZE; i++)
        for (k = kk; k < kk + BLOCK_SIZE; k++)
          for (j = jj; j < jj + BLOCK_SIZE; j++)
            C[i][j] = C[i][j] + A[i][k] * B[k][j];

この方法ではii,jj,kkが変化しない間、つまり内側3つの繰り返しの間に同じメモリが何度もアクセスされ、キャッシュに残り易くなっている（時間的局所性）。また、jを最も内側で変化させて空間的局所性も考慮している。なお、以上はメモリ上で配列の同じ行の要素が連続している Row-major order（英語版）の場合であり、FORTRANなどでは逆に Column-major order になっているため注意が必要である。

局所性の分類

メモリにおけるデータの局所性

データの局所性の例

関連項目