参照の局所性

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

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

局所性は、コンピュータシステムで発生する予測可能な動作の一種です。強力な参照の局所性を示すシステムは、プロセッサコアのパイプライン化段階で のキャッシングメモリのプリフェッチ、高度な分岐予測などの手法を使用したパフォーマンス最適化の優れた候補です。

地域の種類

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

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

頻繁に発生する時間的および空間的局所性の恩恵を受けるために、ほとんどの情報ストレージシステムは階層的です。等距離の局所性は通常、プロセッサの多様で重要な増分命令によってサポートされます。分岐の局所性については、現在のプロセッサには高度な分岐予測子があり、この予測に基づいて、プロセッサのメモリマネージャは、もっともらしい代替のデータを収集して前処理しようとします。

関連性

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

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

一般的な使用法

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

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

空間的および時間的局所性の使用

階層メモリ

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

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

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

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

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

行列の乗算

一般的な例は、行列の乗算です。

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

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

for  i  in  0 .. n
   k  in  0 .. p _
     0j  場合..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

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

2番目のケースでは、の読み取りと書き込みのC[i][j]両方がキャッシュにあり、の読み取りはB[k][j]キャッシュにあり、の読み取りはA[i][k]内部ループから引き上げることができます。

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

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

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

上記の例では、ブロッキングと呼ばれる手法を使用して、時間的局所性を改善することもできます大きい方の行列は均等なサイズの部分行列に分割できるため、小さい方のブロックはメモリ内で数回参照(乗算)できます。この例は、サイズSIZE x SIZEの正方行列に対して機能しますが、必要に応じてSIZE_I、SIZE_J、およびSIZE_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 
      maxi  =  min ii  +  BLOCK_SIZE  SIZE ;
      for  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 ] ;

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

も参照してください

参考文献

  1. ^ 物理学における局所性の原則と混同しないでください
  2. ^ William。、Stallings(2010)。コンピュータの編成とアーキテクチャ:パフォーマンスのための設計(第8版)。ニュージャージー州アッパーサドルリバー:プレンティスホール。ISBN 9780136073734OCLC268788976 _
  3. ^ a b 「NISTビッグデータ相互運用性フレームワーク:第1巻」、[ https://doi.org/10.6028/NIST.SP.1500-1r2 urn:doi:10.6028 / NIST.SP.1500-1r2
  4. ^ アホ、ラム、セティ、ウルマン。「コンパイラ:原理、技術、ツール」第2版。Pearson Education、Inc。2007

参考文献