1

コードのシリアルボトルネックを構成する次のタイトなループがあります。理想的には、これを呼び出す関数を並列化しますが、それは不可能です。

//n is about 60
for (int k = 0;k < n;k++) 
{
    double fone = z[k*n+i+1];
    double fzer = z[k*n+i];
    z[k*n+i+1]= s*fzer+c*fone;
    z[k*n+i] = c*fzer-s*fone;
}

このコードを助けることができるベクトル化やいくつかの邪悪なインラインなど、実行できる最適化はありますか?

三重対角行列の固有解を探しています。http://www.cimat.mx/~posada/OptDoglegGraph/DocLogisticDogleg/projects/adjustedrecipes/tqli.cpp.html

4

3 に答える 3

8

簡単な答え:行列のメモリ レイアウトを行優先から列優先に変更します。

長い答え: 行優先順で格納された行列の (i) 番目と (i+1) 番目の列にアクセスしているようです。おそらく、全体として CPU キャッシュに収まらない大きな行列です。基本的に、ループの反復ごとに、CPU は RAM を待機する必要があります (100 サイクルのオーダー)。理論的には、数回の反復の後、アドレス予測が開始され、ループがデータ項目にアクセスする前であっても、CPU は投機的にデータ項目をロードする必要があります。これにより、RAM レイテンシが改善されるはずです。しかし、それでもコードがメモリ バスを非効率的に使用するという問題が残ります。CPU とメモリは単一バイトを交換することはなく、キャッシュ ラインのみを交換します (現在のプロセッサでは 64 バイト)。ロードおよび格納された 64 バイトのキャッシュ ラインごとに、コードは 16 バイト (または 4 分の 1) しか触れません。

マトリックスを転置し、ネイティブのメジャー オーダーでアクセスすると、メモリ バスの使用率が 4 倍になります。これはおそらくコードのボトルネックであるため、同程度の高速化が期待できます。

それだけの価値があるかどうかは、アルゴリズムの残りの部分に依存します。もちろん、変更されたメモリ レイアウトにより、他の部分が影響を受ける可能性があります。

于 2012-12-16T11:13:19.450 に答える
1

I take it you are rotating something (or rather, lots of things, by the same angle (s being a sin, c being a cos))?

Counting backwards is always good fun and cuts out variable comparison for each iteration, and should work here. Making the counter the index might save a bit of time also (cuts out a bit of arithmetic, as said by others).

for (int k = (n-1) * n + i; k >= 0; k -= n)
{
    double fone=z[k+1];
    double fzer=z[k];
    z[k+1]=s*fzer+c*fone;
    z[k]  =c*fzer-s*fone;
}

Nothing dramatic here, but it looks tidier if nothing else.

于 2012-12-16T10:32:24.547 に答える
1

最初の動きとして、このループでポインターをキャッシュします。

//n is about 60
double *cur_z = &z[0*n+i]
for (int k = 0;k < n;k++) 
{
    double fone = *(cur_z+1);
    double fzer = *cur_z;
    *(cur_z+1)= s*fzer+c*fone;
    *cur_z = c*fzer-s*fone;
    cur_z += n;
}

第二に、この関数のテンプレート化されたバージョンを作成する方が良いと思います。その結果、行列が整数値を保持している場合、パフォーマンスが向上します (FPU 操作が遅いため)。

于 2012-12-16T11:03:04.030 に答える