地域 - 等距離地域のための英語の説明

Question

私はLocality of Reference上のWikipediaの記事を読んでいて、私は助けることが等距離地域のために与えられた説明はかなり不可解なことを見つけることができません。

私は本当にそれを感じることができません、誰かが簡単な英語でそれを説明しようとすることができたのだろうかと思ったのですか？

等価局所性：空間局所性と分岐局所性の中間である。 。 の等距離パターンにおける位置にアクセスするループ、すなわち空間 - 時間座標のパス のスペースは点線であると考えてください。この場合、近い将来にどの位置がアクセスされるのかを単純な線形関数 で予測できます。

"等距離パターンで位置にアクセスするループ"とはどういう意味ですか？場所はお互いに等しい距離ですか？

「」についてのこのゴミは何ですか？空間 - 時間座標空間は点線です "？それは私には意味がありません。

誰かが何を明確にすることができたらイクスピアントローカリティは、それが素晴らしいと思われます！

Answer 1

私はこれが例で最もよく説明されていると思います。これらの地域の原則は、物を最適化するためによく使われます。現代のCPUの可能なコンポーネントはメモリプリフェッチャです。メモリプリフェッチャは、使用するメモリを推測し、必要なときにキャッシュに格納します。これは、地域の原則に大きく依存しています。あなたは、この（C++の例）のような何かを行う場合

は、例えば配列を取る：

#include <iostream> 
#include <vector> 

int main() 
{ 
    std::vector<int> test = { 1, 2, 3, 4, 5}; 
    for(int& i: test) 
    { 
     std::cout << i << std::endl; 
    } 
} 

ベクトルで

（または配列を他の言語で）要素は、固定された進歩と連続したブロックにパックされています。したがって、testの最初の要素がアドレスXにある場合、2番目の要素はX+Yになり、3番目の要素はX+2Y,...になります。したがって、ベクトルそのものは空間的局所性の非常に基本的な例であり、局所性は非常に予測可能です。 次に、エレメントがタイトループでアクセスされるため、良い時間的空間性も持っています。要素は順次アクセスされるため、「時空」には等間隔の空間性があります。これは、CPUがX+Y, X+2Y, X+3Yパターンのintを認識するとすぐに、キャッシュ内の将来の要素を引き出すことを開始できることを意味します。

あなたは、たとえばでこれを対比することができます

#include <iostream> 
#include <list> 

int main() 
{ 
    std::list<int> test = { 1, 2, 3, 4, 5}; 
    for(int& i: test) 
    { 
     std::cout << i << std::endl; 
    } 
} 

をリンクリストでは、要素がお互いを参照してください、そして、あなたの空間的局所性を失うので、個々の要素は、メモリ内の任意の場所ですることができます。しかし、ループ内の要素にアクセスするので、あなたは一時的な空間性を保ちます。このようなものは、プリフェッチを検出して最適化するのが非常に難しくなります（ただし不可能ではありません）。

最後に、複合時空空間性が重要である理由指標として、この（少し不自然）の例を検討：あなたは純粋にtestコンテナを見れば

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <random> 
#include <iterator> 

int main() 
{ 
    std::vector<int> test = { 1, 2, 3, 4, 5 }; 
    std::vector<unsigned int> indices = { 0, 1, 2, 3, 4 }; 
    std::random_device rd; 
    std::shuffle(std::begin(indices), std::end(indices), std::mt19937 { rd() }); 
    for (unsigned int& i : indices) 
    { 
     std::cout << test[i] << std::endl; 
    } 
} 

を、それは再び良い空間的局所性を持っていた（のようなストライド最初の例）。ループ内のtestアクセスを見ると、ルックアップに時間的局所性があることがわかります。しかし、「タイムスペース」では、配列のある部分から別の部分にジャンプするときにルックアップが等距離にならず、アクセスは順次的ではないので、空間と時間の両方に等間隔の空間性はありません。これは最適化することはほとんど不可能です。

Answer 2

かなり不可解ですが、私は推測していたならば、それはループのすべての反復が、空間的/時間的局所性の同じレベルを持っていることを意味し等距離パターン

内の場所にアクセスするループ：ループが単純に配列を反復している場合、各反復で、前の要素の隣にある要素にアクセスします（空間的局所性は最後の繰り返しと同じです）。最後の反復では（時間的局所性も変わらない）。

等距離の局所性はすべての反復で同じです。