3

Locality of Referenceに関するウィキペディアの記事を読んでいますが、 Equidistant Localityの説明がやや不可解であることがわかります。

あまり意味が分からないので、どなたか平易な英語で説明していただけないでしょうか？

等距離の局所性: 空間的局所性と分岐局所性の中間です。等距離パターンで場所にアクセスするループを考えてみましょう。つまり、時空間座標空間のパスは点線です。この場合、単純な線形関数を使用して、近い将来にアクセスされる場所を予測できます。

「等距離パターンで場所にアクセスするループ」とはどういう意味ですか? 場所は互いに等距離ですか？

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

等距離の局所性が何を意味すると考えられているかについて誰かが明確にすることができれば、それは素晴らしいことです!

4

2 に答える 2

3

これは例で説明するのが一番だと思います。これらの局所性の原則は、物事を最適化するためによく使用されます。最新の 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;
    }
}

ベクトル (または他の言語では配列) では、要素は固定ストライドの連続したブロックにパックされます。したがって、 の最初の要素がtestaddressXにある場合、2 番目の要素はX+Y、3番目の要素はX+2Y, になり...ます。したがって、ベクトル自体は空間的局所性の非常に基本的な例であり、局所性は非常に予測可能です。次に要素はタイトなループでアクセスされるため、優れた時間空間性も得られます。要素も順次アクセスされるため、「時空」には等距離の空間性があります。これは、CPU がX+Y, X+2Y, X+3Yルックアップでパターンを認識するとすぐに、キャッシュ内の将来の要素の取り込みを開始できることを意味します。

これは、たとえば次のように対比できます。

#include <iostream>
#include <list>

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

リンクされたリストでは、要素は相互に参照され、個々の要素はメモリ内の任意の場所にある可能性があるため、空間的な局所性が失われます。ただし、ループ内の要素にアクセスするため、時間空間性は維持されます。このようなものは、検出してプリフェッチ用に最適化するのがはるかに困難です (ただし、不可能ではありません)。

最後に、組み合わされた時空の空間性が重要である理由の指標として、次の (少し不自然な) 例を考えてみましょう。

#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空間的局所性が良好でした (最初の例のようにストライド)。ループ内のアクセスを見るとtest、ルックアップに一時的な局所性があることがわかります。ただし、「時空間」では、配列のある部分から別の部分にジャンプするため、ルックアップは等距離ではありません。アクセスはシーケンシャルではないため、空間と時間の両方に等距離の空間性はありません。これを最適化することはほとんど不可能です。

于 2012-03-20T11:24:06.640 に答える
1

等距離パターンで場所にアクセスするループ

これはかなり不可解ですが、推測する必要がある場合は、ループのすべての反復が同じレベルの空間的/時間的局所性を持っていることを意味します。ループが単純に配列を反復している場合、各反復で、配置された要素にアクセスします前の要素の隣にあり (したがって、空間的局所性は最後の反復と同じです)、それは最後の反復と同じように「最近」です (したがって、時間的局所性も変更されていません)。

したがって、等距離の局所性はすべての反復で同じです。

于 2012-03-20T09:57:17.110 に答える