1

私のアプリケーションは、大きなサイズの行列に対していくつかの操作を行います。私は最近、キャッシュの概念と、この回答によるパフォーマンスへの影響に出くわしました。私の場合、キャッシュに適した最適なアルゴリズムは何かを知りたいです。

Algorithm 1:
for(int i = 0; i < size; i++)
{
    for(int j = i + 1; j < size; j++)
    {
        c[i][j] -= K * c[j][j];//K is a constant double variable
    }//c is a 2 dimensional array of double variables
}

Algorithm 2:
double *A = new double[size];
for(int n = 0; n < size; n++)
    A[n] = c[n][n];

for(int i = 0; i < size; i++)
{
    for(int j = i + 1; j < size; j++)
    {
        c[i][j] -= K * A[j];
    }
}

アレイのサイズが 1000x1000 を超えています。私のラップトップでのベンチマークは、サイズ 5000x5000 でアルゴリズム 2 が 1 よりも優れていることを示しています。行のセットがスレッドによって操作されるように、アプリケーションをマルチスレッド化したことに注意してください。

For example: For array of size 1000x1000.
thread1 -> row 0 to row 249
thread2 -> row 250 to row 499
thread3 -> row 500 to row 749
thread4 -> row 750 to row 999
4

2 に答える 2

2

ベンチマークが 2 番目のケースで大幅な改善を示している場合は、それがより適切な選択である可能性が高くなります。しかしもちろん、「平均的な CPU」を知るには、平均的と呼べる多数の CPU について知る必要があります - 他に方法はありません。そして、それは実際には平均 CPU の定義に依存します。「任意の x86 (AMD + Intel) CPU」または「時計から x86 範囲の最新の超高速作成まで、あらゆるものに見られるランダムな CPU」のことを話しているのでしょうか?

「データをコピーするc[n][n]」メソッドは、独自のアドレスを取得し、コードがより大きな行列を通過するときに (L1) キャッシュからスローされないため、役立ちます [そして、乗算に必要なすべてのデータは「寄り添う」。walk の場合c[j][j]、すべてのjステップで反復ごとにバイトがジャンプするsizeof(double) * (size * j + 1)ため、サイズが 4 を超えると、必要な次のアイテムが同じキャッシュラインにないため、そのデータを取得するには別のメモリ読み取りが必要になります。

言い換えれば、まともなサイズのキャッシュ (よりも大きいsize * sizeof(double)) を持つものには、明確な利点があります。キャッシュが小さい場合でも、何らかの利点がある可能性はかなりありますが、キャッシュされたコピーが の一部によって破棄される可能性が高くなりますc[i][j]。

要約すると、ほぼすべてのオプションで 2 番目のアルゴリズムの方が優れている可能性が非常に高くなります。

于 2013-09-21T09:24:39.303 に答える