参照の局所性
 | この記事は英語版の対応するページを翻訳することにより充実させることができます。（2023年12月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。（2023年8月） |
参照の局所性（さんしょうのきょくしょせい、英: 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];
i,j,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 になっているため注意が必要である。
関連項目
「Locality of reference」の例文・使い方・用例・文例
- Microsoftがβ版をランチするのは「NetShow streaming server」で動画や音声をオンデマンドで提供する。
- 《主に米国で用いられる》 ＝ 《主に英国で用いられる》 an admiral of the fleet 海軍元帥.
- 篏入的 r 音 《英音の India office /ndiərfɪs/の /r/の音》.
- ＝《口語》 These kind of stamps are rare. この種の[こういう]切手は珍しい.
- (英国の)運輸省. the Ministry of Education(, Science and Culture) (日本の)文部省.
- は of の誤植です.
- を off と誤植する.
- あいまい母音 《about, sofa などの /ə/》.
- 副詞的小詞 《on, in, out, over, off など》.
- 迂言的属格 《語尾変化によらず前置詞によって示す属格; たとえば Caesar's の代わりの of Caesar など》.
- çon of garlic [humor]. それにはガーリック[ユーモア]がちょっぴり必要だ.
- 《主に米国で用いられる》 ＝ 《主に英国で用いられる》 the Speaker of the House of Commons 下院議長.
- 《主に米国で用いられる》 ＝ 《主に英国で用いられる》 the Committee of Ways and Means 歳入委員会.
- 初めて読んだ英文小説は“The Vicar of Wakefield”
- （違法罪―a sin of commission―に対する）怠惰罪
- 『each』、『every』、『either』、『neither』、『none』が分配的、つまり集団の中の1つのものを指すのに対し、『which of the men』の『which』は分離的である
- 『hot off the press（最新情報）』は『hot（最新の）』の拡張感覚を示している
- 『Each made a list of the books that had influenced him』における制限節は、リストに載った本を制限節で定義された特定の本だけに制限する
- 臨床的鬱病を治療するのに用いられる三環系抗鬱薬（商品名ImavateとTofranil）
- 『sunshine-roof』は『sunroof（サンルーフ）』に対する英国の用語である
- Locality of referenceのページへのリンク
