参照の局所性

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

[編集] 局所性の分類

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

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

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

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

[編集] メモリにおけるデータの局所性

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

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

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

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

[編集] データの局所性の例

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

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];

横軸をメモリアドレス、縦軸を時間としたメモリ参照の推移を示す図。8x8の行列の積を求めるときのものであり、1行は最内ループを回りきるまでにアクセスの発生する箇所を示す。ピンク：リード1回、赤:リード8回、灰：リード1回＋ライト1回、黒：リード8回＋ライト8回。上はi→j→k、下はi→k→jの順にループをコーディングした場合を示している。

大きな行列を扱うとき、このアルゴリズムはデータを過剰にかき回す傾向がある。メモリはアドレス上連続なブロックとして上位階層に引き上げられるので、C言語では同じ行内の要素をなるべく連続してアクセスした方が有利である(空間的局所性)。行のインデックスを固定すれば、2番目のインデックスが頻繁に変わるようになる。CおよびC++では、それによって使用するメモリアドレスがより連続的になることを示している。j は行列 C と行列 B の列のインデックスを変化させるので、最も内側のループで変化させるべきである(これにより行を変化させるiとkが固定されている状態で列だけが変化するようになる)。このように変更しても数学的な違いはなく、効率が向上する。jとkのループを入れ替えることによる性能向上は行列が大きくなるほど劇的なものとなる。ここでいう大きな行列とは、100,000以上の要素を持つようなキャッシュに入りきらない大きさの行列である。

上記の例で時間的局所性を利用するには「ブロック化」と呼ばれる技法を使う。ここでの「ブロック化」とは大きな行列を等しいサイズの部分行列に分けることで、これによって部分行列が複数回参照されるようになる。

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 < SIZE; i++)
        for (k = kk; k < kk + BLOCK_SIZE && k < SIZE; k++)
          for (j = jj; j < jj + BLOCK_SIZE && k < SIZE; j++)
            C[i][j] = C[i][j] + A[i][k] * B[k][j];

この解法の時間的局所性はブロックが移動する前に複数回使われることで達成されており、キャッシュに残り易くなっている。また、連続したメモリ領域へのアクセスも考慮されているので空間的局所性も達成している。なお、以上は所謂 Raw-major order と呼ばれる配列のメモリ配置の場合であり、FORTRANなどでは逆に Column-major order と呼ばれる配置になっているため注意が必要である。