1

注：この質問は、KeithRandallとChiyouの有益なフィードバックを使用して編集しました。

1D配列を使用して、特定の処理コンテキストで最も使用される2DNxMマトリックスエントリをキャッシュすることを考えています。問題は、洞察を得るための一連の作業がすでに存在するのか、それとも知っている人だけが存在するのかということです。最初に脚の作業の概要を説明し、後で質問もします。補足として、Chiyouはすでに空間充填曲線を提案しました。これは、概念的には私が求めているものに見えますが、私の特定の質問にはすぐには答えられません（つまり、私が求めているものを実行する曲線が見つかりません）。 。

レッグワーク： 現在、最も使用されているエントリは、ループと特殊なものpointer_array（以下のコードを参照）の組み合わせとして定義されており、これらを組み合わせて、最も使用されている行列要素へのインデックスを生成します。pointer_arrayには、範囲 [0、max（N、M）]の数値が含まれています（上記のNxMとして定義された行列の次元を参照）。

コードの目的は、いくつかのマトリックスエントリを処理するために、インデックスの適切な（プログラムのコンテキストで）組み合わせを生成することです。N = M、つまり正方行列が可能です。マトリックスをトラバースするコード（C ++）は、次のようになります。

for(int i = 0; i < N; i++)
{        
    for(int j = i + 1; j < M; j++)
    {
        auto pointer1 = pointer_array[i];
        auto pointer2 = pointer_array[i + 1];
        auto pointer3 = pointer_array[j];
        auto pointer4 = pointer_array[j + 1];

        auto entry1 = some_matrix[pointer1][pointer3];
        auto entry2 = some_matrix[pointer2][pointer4];
        auto entry3 = some_matrix[pointer3][pointer4];
        auto entry4 = some_matrix[pointer1][pointer2];

        //Computing with the entries...
    }
}

別の注意に値するいくつかの事柄：

  1. このキャッシングを価値のあるものにするためには、高密度にする必要があると思います。つまり、ランダムにアクセスでき、メモリ内に連続して配置されるものです。つまり、「無駄な」スペースはなく（おそらく、多数の個別のチャンクがある場合を除く）、複雑さはO（1）にあります。つまり、キャッシュは、1Dの行/列が主要な順序付けられた配列と完全に順序付けられた2D行列と同じにすることはできません。長さがmax（N、M）の配列に収まるはずだと思います（上記の行列の次元の定義を参照）。

  2. のエントリの多くはsome_matrix、ループ中に無視されます。

  3. pointer_arrayの順序は、マトリックスを通るルートを記録するため、他の場所でも使用されます。

  4. 私はさまざまな場面でこのニーズに遭遇しましたが、今回は2 optアルゴリズムを作成しました。このアルゴリズムのメモリアクセスパターンは、改善を目指しています。アルゴリズムを作成する方法は他にもあることは承知しています（ただし、これに遭遇した他の設定があり、一般的な解決策があるかどうか疑問に思っています）。

  5. 既成概念にとらわれずに考えるのは、概念的には2Dマトリックスにアクセスするのと似ているが、よりスマートなものと同様の種類のインデックスの組み合わせを作成することです。1つのオプションは、ループ中に行列の行/列をキャッシュすることです。

  6. pointer_arrayエントリは頻繁に使用されるため、some_matrix呼び出しをキャッシュして間接参照を置き換える方が理想的です。これによりentry*、ループ内の値の取得が高速になります。つまり、かなり大きなマトリックスではなく、プリロードされたキャッシュから取得できます。ここでのもう1つのポイントは、ストレージに保存されることです。つまり、頻繁に使用される値は、より高速なキャッシュに非常によく適合する可能性があります。

質問：マトリックスのインデックス作成が本質的に次のようになるように、インデックス作成スキームをデバイス化することは可能ですか？

//Load the 2D matrix entries to some_1d_cache using the pointer_array
//so that the loop indices can be used directly...

for (int i = 0; i < N; i++)
{        
    for (int j = i + 1; j < M; j++)
    {           
        //The some_1d_cache((x, y) call will calculate an index to the 1D cache array...
        auto entry1 = some_1d_cache(i, j);
        auto entry2 = some_1d_cache(i + 1, j + 1);
        auto entry3 = some_1d_cache(j, j + 1);
        auto entry4 = some_1d_cache(i, i + 1);

        //Computing with the entries...
    }
}

または、次のようなものでもかまいません

for (int i = 0; i < N; i++)
{        
    for (int j = i + 1; j < M; j++)
    {            
        auto pointer1 = pointer_array[i];
        auto pointer2 = pointer_array[i + 1];
        auto pointer3 = pointer_array[j];
        auto pointer4 = pointer_array[j + 1];

        //The some_1d_cache((x, y) call will calculate an index to the 1D cache array...
        auto entry1 = some_1d_cache(pointer1, pointer3);
        auto entry2 = some_1d_cache(pointer2, pointer4);
        auto entry3 = some_1d_cache(pointer3, pointer4);
        auto entry4 = some_1d_cache(pointer1, pointer2);

        //Computing with the entries...
    }
}
4

1 に答える 1

1

1D空間充填曲線を使用して2D行列にインデックスを付けることができます。数学的には、H（x、y）=（h（x）* h（y））です。また、基本的に細分化し、地域情報を保存し、飛行機を並べ替えるため、便利です。

于 2012-08-27T00:06:01.187 に答える