参照の地域

コンピュータサイエンスにおいて、参照の局所性（局所性の原理とも呼ばれる）^[1]とは、プロセッサが短期間に同じメモリ位置のセットに繰り返しアクセスする傾向のことである。^[2]参照の局所性には、時間的局所性と空間的局所性の2つの基本的なタイプがある。時間的局所性は、比較的短い時間内に特定のデータやリソースを再利用することである。空間的局所性（データ局所性^{[3]とも呼ばれる）は、比較的近いストレージ位置内でデータ要素を使用することである。空間的局所性の特殊なケースである順次局所性は、1次元}配列内の要素をトラバースするなど、データ要素が線形に配置されアクセスされる場合に発生する。

局所性は、コンピュータ システムで発生する予測可能な動作の一種です。参照の局所性が強いシステムは、キャッシュ、メモリのプリフェッチ、プロセッサ コアの高度な分岐予測などの技術を使用することで、パフォーマンスを最適化するのに最適です。

参照の局所性にはいくつかの異なるタイプがあります。

• 時間的局所性: ある時点で特定のメモリ位置が参照された場合、近い将来に同じ位置が再び参照される可能性が高くなります。同じメモリ位置への隣接する参照は時間的に近接しています。この場合、後続の参照の待ち時間を減らすために、参照されたデータのコピーをより高速なメモリ ストレージに保存する努力をするのが一般的です。時間的局所性は空間的局所性の特殊なケースです (以下を参照)。つまり、予測される位置が現在の位置と同一である場合です。
• 空間的局所性: 特定のストレージ位置が特定の時間に参照された場合、近くのメモリ位置が近い将来に参照される可能性が高くなります。この場合、現在の参照の周囲の領域のサイズと形状を推測し、その後の参照のために高速アクセスを準備することが一般的です。
  • メモリ局所性（またはデータ局所性^[3]）：メモリに明示的に関連する空間局所性。
• 分岐局所性: 空間的・時間的座標空間におけるパスの見込み部分に可能な選択肢がわずかしかない場合。これは、命令ループが単純な構造である場合、または条件分岐命令の小さなシステムの可能な結果が少数の可能性に制限されている場合に当てはまります。分岐局所性は、少数の可能性が互いに遠く離れた場所にある可能性があるため、通常は空間局所性ではありません。
• 等距離局所性: 空間局所性と分岐局所性の中間。等距離パターンで場所にアクセスするループ、つまり空間時間座標空間のパスが点線であるとします。この場合、単純な線形関数で、近い将来にアクセスされる場所を予測できます。

頻繁に発生する時間的および空間的局所性を活用するために、ほとんどの情報ストレージ システムは階層化されています。等距離局所性は通常、プロセッサのさまざまな非自明な増分命令によってサポートされます。分岐局所性については、最新のプロセッサには高度な分岐予測機能があり、この予測に基づいてプロセッサのメモリ マネージャは妥当な選択肢のデータを収集して前処理しようとします。

局所性にはいくつかの理由があります。これらの理由は、側面に応じて、達成すべき目標または受け入れるべき状況のいずれかです。以下の理由は互いに関連し合っているわけではなく、実際、以下のリストは最も一般的なケースから特殊なケースまで続きます。

• 予測可能性: 局所性は、コンピュータ システムにおける予測可能な動作の 1 つのタイプにすぎません。
• プログラムの構造: 局所性は、決定可能な問題を処理するコンピュータ プログラムの作成方法が原因でよく発生します。通常、関連するデータはストレージ内の近くの場所に格納されます。コンピューティングの一般的なパターンの 1 つは、複数の項目を 1 つずつ処理することです。つまり、大量の処理が行われると、単一の項目に複数回アクセスすることになり、参照の時間的局所性が生じます。さらに、次の項目に移動すると、次の項目が読み取られることになります。したがって、メモリの場所は通常、バッチで読み取られるため、参照の空間的局所性が生じます。
• 線形データ構造: 局所性は、コードにインデックスで配列やその他のデータ構造を参照する傾向があるループが含まれているためによく発生します。空間局所性の特殊なケースである順次局所性は、関連するデータ要素が線形に配置され、アクセスされる場合に発生します。たとえば、1 次元配列の要素をベース アドレスから最上位の要素まで単純に走査すると、メモリ内の配列の順次局所性が活用されます。^{[4]等距離局所性は、線形走査が、構造とサイズが同じである隣接する}データ構造のより長い領域にわたって行われ、各構造全体ではなく、各構造の相互に対応する要素にアクセスする場合に発生します。これは、行列が行の順次行列として表され、行列の 1 つの列にアクセスする必要がある場合に当てはまります。
• メモリ階層の使用効率:ランダム アクセス メモリは、いつでもどこでも読み取りまたは書き込みができる機能をプログラマに提供しますが、実際には、レイテンシとスループットはキャッシュの効率によって影響を受けます。キャッシュの効率は、参照の局所性を高めることで改善されます。参照の局所性が低いと、キャッシュスラッシングやキャッシュ汚染が発生します。これを回避するには、局所性が低いデータ要素をキャッシュからバイパスします。

ほとんどの場合、参照の大部分がクラスターに集約され、このクラスター システムの形状が適切に予測できる場合は、パフォーマンスの最適化に使用できます。最適化手法を使用して局所性を活用する方法はいくつかあります。一般的な手法は次のとおりです。

• 参照の局所性を高める（一般的にはソフトウェア側）
• 参照の局所性を活用する: 通常はハードウェア側で実現されますが、時間的および空間的な局所性は階層型ストレージ ハードウェアによって活用できます。等距離の局所性は、プロセッサの適切に特殊化された命令によって使用できます。この可能性は、ハードウェアだけでなくソフトウェアの責任でもあり、その構造が、問題の特殊化された命令を呼び出すバイナリ プログラムをコンパイルするのに適しているかどうかも問題になります。分岐の局所性はより複雑な可能性であるため、より多くの開発努力が必要ですが、この種の局所性には、残りのすべての局所性よりも将来の調査の余地がはるかに多くあります。

階層型メモリは、空間的および時間的局所性の利点を活用し、メモリ階層の複数のレベルで使用できるハードウェア最適化です。ページングは​​、時間的および空間的局所性の利点を明らかに受けます。キャッシュは、特別に設計された、より高速で小さいメモリ領域であり、一般的に最近参照されたデータと最近参照されたデータの近くにあるデータを保持するために使用され、潜在的なパフォーマンスの向上につながるため、時間的局所性を活用する簡単な例です。

キャッシュ内のデータ要素は、必ずしもメイン メモリ内で空間的に近いデータ要素に対応するわけではありません。ただし、データ要素は 1 度に 1キャッシュ ラインずつキャッシュに取り込まれます。つまり、空間的な局所性がここでも重要になります。つまり、1 つの要素が参照されると、隣接するいくつかの要素もキャッシュに取り込まれます。最後に、時間的な局所性は最下位レベルで役割を果たします。非常に近い距離で参照される結果はマシン レジスタに保持できるためです。一部のプログラミング言語 ( Cなど) では、プログラマが特定の変数をレジスタに保持するように指示できます。

データ ローカリティは、通常のプログラムの典型的なメモリ参照機能です (ただし、不規則なメモリ アクセス パターンは多数存在します)。これにより、階層型メモリ レイアウトが有益になります。コンピューターでは、データ アクセスを高速化するために、メモリが階層に分割されます。メモリ階層の下位レベルは、低速ですが、サイズが大きい傾向があります。したがって、メモリが上位レベルのメモリ階層にキャッシュされている間にメモリを使用し、将来すぐに使用されるデータを置き換える他のデータを上位レベルの階層に持ち込まないようにすると、プログラムはより優れたパフォーマンスを達成できます。これは理想であり、実現できない場合もあります。

^{[アップデート]}一般的なメモリ階層 (アクセス時間とキャッシュ サイズは、説明の目的で 2013 年時点で使用されている一般的な値の概算です。実際の値と階層内の実際のレベル数は異なります):

• CPUレジスタ（8～256レジスタ） – プロセッサの最も内側のコアの速度で即時アクセス可能
• L1 CPUキャッシュ（32 KB～512  KB） – 各コアが独占的に所有する最内部メモリバスの速度で高速アクセス
• L2 CPUキャッシュ（128 KB～24  MB ） –メモリバスの速度が2つのコア間で共有されるため、アクセスが若干遅くなります。
• L3 CPU キャッシュ (2 MB ～最大 64  MB ) – 同じプロセッサのさらに多くのコア間でメモリ バスの速度が共有されるため、アクセスがさらに遅くなります。
• メイン物理メモリ( RAM ) (256 MB ～ 64  GB ) – アクセスが遅く、その速度はプロセッサとマザーボード上のメモリモジュール間の空間距離と一般的なハードウェアインターフェイスによって制限されます。
• ディスク（仮想メモリ、ファイルシステム）（1 GB ～ 256  TB） – コンピュータのメインボードとディスクデバイス間のデータチャネルが狭く（ビット幅）、物理的に非常に長いため、また、遅いハードウェアインターフェイスの上に余分なソフトウェアプロトコルが必要なため、非常に低速です。
• リモートメモリ（他のコンピュータまたはクラウド）（実質的に無制限） – 速度は非常に遅いものから極めて遅いものまでさまざまです

最近のマシンは、下位のメモリ ブロックをメモリ階層の次のレベルに読み込む傾向があります。これにより使用メモリが置き換えられると、オペレーティング システムは、アクセスが最も少ない (または最新の) データを予測し、メモリ階層を下に移動しようとします。予測アルゴリズムは、ハードウェアの複雑さを軽減するために単純になる傾向がありますが、やや複雑になってきています。

一般的な例としては行列の乗算があります。

iが0 .. nの場合   
  jが0 .. mの場合   
    kが0 .. pの場合   
      C [ i ][ j ] = C [ i ][ j ] + A [ i ][ k ] * B [ k ][ j ] ;      

jとのループ順序を切り替えるとk、少なくとも最後の次元に連続した配列要素を配置する言語では、大規模な行列乗算の速度が劇的に向上します。これにより、数学的な結果は変わりませんが、効率が向上します。この場合、「大規模」とは、各行列におよそ 100,000 を超える要素があるか、行列が L1 キャッシュと L2 キャッシュに収まらないほどのアドレス指定可能なメモリがあることを意味します。

iが0 .. nの場合   
  kが0 .. pの場合   
    jが0 .. mの場合   
      C [ i ][ j ] = C [ i ][ j ] + A [ i ][ k ] * B [ k ][ j ] ;      

この高速化の理由は、最初のケースでは、 の読み取りはA[i][k]キャッシュ内にある (kインデックスは連続した最後の次元であるため) が、B[k][j]はキャッシュ内にないため、 にキャッシュ ミス ペナルティが発生するためですB[k][j]。C[i][j]は、内部ループから持ち上げるkことができるため無関係です (ループ変数は です) 。

iが0 .. nの場合   
  jが0 .. mの場合   
    温度= C [ i ][ j ]  
    kが0 .. pの場合   
      温度=温度+ A [ i ][ k ] * B [ k ][ j ] ;      
    C [ i ][ j ] =温度  

2 番目のケースでは、 の読み取りと書き込みはC[i][j]両方ともキャッシュ内にあり、 の読み取りはB[k][j]キャッシュ内にあり、 の読み取りはA[i][k]内部ループの外部にホイストできます。

iが0 .. nの場合   
  kが0 .. pの場合   
    温度= A [ i ][ k ]  
    jが0 .. mの場合   
      C [ i ][ j ] = C [ i ][ j ] +温度* B [ k ][ j ] ;      

したがって、2 番目の例では内部ループにキャッシュ ミス ペナルティはありませんが、最初の例ではキャッシュ ペナルティがあります。

2014 年のプロセッサでは、Cで記述され でコンパイルされた場合、2 番目のケースは最初のケースよりも約 5 倍高速ですgcc -O3。(逆アセンブルされたコードを注意深く調べると、最初のケースではGCC がSIMD命令を使用し、2 番目のケースでは使用していないことがわかりますが、キャッシュ ペナルティは SIMD の利点よりもはるかに悪いです。) ^{[引用が必要]}

上記の例では、ブロッキングと呼ばれる手法を使用することで、時間的局所性も改善できます。大きな行列を均等なサイズのサブ行列に分割して、メモリ内にある小さなブロックを複数回参照 (乗算) することができます。この例は、SIZE x SIZE の次元の正方行列で機能しますが、必要に応じて SIZE_I、SIZE_J、および SIZE_K を置き換えることで、任意の行列に簡単に拡張できます。

( ii = 0 ; ii < SIZE ; ii += BLOCK_SIZE )の場合         
  ( kk = 0 ; kk < SIZE ; kk += BLOCK_SIZE )の場合         
    ( jj = 0 ; jj < SIZE ; jj += BLOCK_SIZE )の場合         
      maxi = min ( ii + BLOCK_SIZE 、SIZE ) ;     
      ( i = ii ; i < maxi ; i ++ )の場合       
        maxk = min ( kk + BLOCK_SIZE 、SIZE ) ;     
        for ( k = kk ; k < maxk ; k ++ )       
          maxj = min ( jj + BLOCK_SIZE 、SIZE ) ;     
          for ( j = jj ; j < maxj ; j ++ )       
            C [ i ][ j ] = C [ i ][ j ] + A [ i ][ k ] * B [ k ][ j ] ;      

上記のソリューションの時間的局所性は、ブロックを移動する前に複数回使用できるため、メモリへの出し入れの頻度が少なくなり、実現されます。連続したメモリ アドレスを持つ要素は、メモリ階層内で一緒に引き上げられる傾向があるため、空間的局所性が向上します。

• キャッシュ無視アルゴリズム
• 通信回避アルゴリズム
• ファイルシステムの断片化
• 分割されたグローバルアドレス空間
• 行優先と列優先の順序
• スケーラブルなローカリティ
• スクラッチパッドメモリ
• ワーキングセット
• ヒューリスティック

• Peter J. Denning、「局所性原理」、Communications of the ACM、第 48 巻、第 7 号、(2005 年)、19 ～ 24 ページ
• Peter J. Denning、Stuart C. Schwartz、「ワーキング セット モデルの特性」、Communications of the ACM、第 15 巻、第 3 号 (1972 年 3 月)、191 ～ 198 ページ