4

「double**times」から値を計算するコードがあります。「回」の次元が[nsims][N]（malloc ..で作成）であるとしましょう。ここで、int N=40およびintnsims=50000です。

結果は「double**moments」に保存されます。したがって、5つのネストされたforループがあります。

ただし、このコードは約100万回実行する必要があるため、問題は速度です。

私はすでにスレッド（ここには示されていません）を使用して、最も内側のforループを10個の並列スレッドに分割しています。これにより、すでに多くの時間を節約できます。

特に異なるデータ構造やこのようなものに関して、他の最適化の可能性を見ている人はいますか？

「interm=...」の式がなくても、時間がかかりすぎます。

for(j=2;j<=N;j++) {     
    for(k=j;k<=N;k++) {
        moment=0;
        for(i=2;i<=N;i++) {
            for(l=i;l<=N;l++) {
                if(strcmp(mmethod, "emp")==0) {
                    for(a=0;a<nsims;a++) {
                        interm=interm + (double) times[a][k] *
                                        times[a][j]*times[a][i] *
                                        times[a][l];    
                    }
                    interm = (double) interm/nsims;
                    moment = moment + (interm*i*l);
                    interm=0;
                }
            }
        }
        if(!(changed_times[k]==0
             && changed_times[j]==0
             && changed_times[l]==0
             && changed_times[i]==0))
        {
            moments[0][pcount]=(double) moment;
        } else {
            moments[0][pcount]=moments[0][pcount];
        }
        pcount++;
    }
}
4

3 に答える 3

3

内側のループ内で、times[a][k]*times[a][j]*times[a][i]式がの各値で同じであっても、毎回検索して乗算していることに注意してくださいa。乗算とメモリルックアップの両方でコストがかかる可能性があります。（コンパイラーはそれを最適化するのに十分賢いのかもしれませんが、私にはわかりません。）しかし、これらの値を内側のループにキャッシュしてみてください。

  ...
  double akji[nsims];
  for (a = 0; a < nsims; ++a) { akji[a] = times[a][k]*times[a][j]*times[a][i]; }
  for(l=i;l<=N;l++) {
interm=0;
for(a=0;a<nsims;a++) {
  interm += akji[a]*times[a][l]; 
}
moment += (interm*l);
  }
  moment = moment * i / nsims;
  ...
于 2013-03-15T14:14:45.990 に答える
1

問題のより高いレベルの説明から始めるべきだと思います。

しかし、2番目のオプションとして、配列インデックスを交換して、4つの（場合によっては異なる）ベクトルを組み合わせた非常に高速なSSE内部ループのコーディングを容易にすることをお勧めします。

 double times[N+1][nsims], *tend = times[N+1];
 double *j,*k,*i,*l;
 for (j=times[2];j<tend;j+=nsims)
  for (k=j;k<tend;k+=nsims)
   if (strcmp( )) ... /* One _can_ move this elsewhere, but why bother? */
   for (i=times[2];i<tend;i+=nsims)
    for (l=i;l<tend;l+=nsims) {
      interm = efficient_sse_implementation(j,k,i,l, nsims);
      ...
    }

個別のアレイが4つ未満の場合は、異なるカーネルを作成することで、ごくわずかな最適化を実現することもできます。（その場合、ストライドごとに1つのメモリ操作をスキップできます。）

編集

この場合、パターンの構造はfor(j=2;j<=N;j++) for (k=j;k<=N;k++)2回繰り返されますが、それだけで、はるかに高いレベルの最適化の可能性が示唆されます。実行される操作は何ですか。それで苦労している間、このパターンはまだ別の方法を示唆しています：780（またはそれくらい）の副産物をキャッシュしますが、同時にループブロッキングを実行します。このアプローチは、私が氏にコメントしたものと同じ問題を抱えているべきではありません。gcbenison。

 for (A=0;A<50000;A+=100) {
    int k=0;
    for (i=2;i<=N;i++)
     for (j=i;j<=N;j++,k++)
       for (a=0;a<100;a++) precalc[k][a]=times[i][A+a]*times[j][A+a];

    for (i=0;i<k;i++)  // Now i loops from 0..779 or so
     for (j=0;j<k;j++) {
       for (a=0;a<100;a++) partial_product+=precalc[i][a]*precalc[j][a];
       // accumulate also partial_product to moment
     }
 }

免責事項：これは未試行ですが、最適なブロックサイズ（必ずしも100ではない）が存在します（前のものよりもさらに悪い場合があります）。また、このアプローチでは、事前に計算されたテーブルに大量のメモリが使用されることに注意してください。（100のブロックサイズを選択すると、624000バイトのメモリが必要になります。これはかなり良い音です。256k未満になるには、ブロック長は42になります）。

編集2：

//EDIT_1のループがとの両方P[2][a]*P[3][a]を計算することに注意してくださいP[3][a]*P[2][a]。

    for (i=0;i<k;i++)  // Now i loops from 0..779 or so, but... we can limit the
     for (j=i;j<k;j++) { // calculation to the upper triangle of the 780^2 matrix
       for (a=0;a<100;a++) partial_product+=precalc[i][a]*precalc[j][a];
       moment[i]+=partial_product;
       moment[lower_triangle(i)]+=partial_product;  // <-- 50% speed increase
     }

編集3：そしてここに試してみることがあります：

gcc -O4 -DCACHELEVEL=2 -DPOPULATE=1 -DARRAY_OPT=1 && time ./a.out
  • POPULATE配列を初期化します（ゼロ以外の内容が重要であると想定）
  • ARRAY_OPT=1配列のインデックスを（おそらく）より良い順序に切り替えます
  • CACHELEVEL=2または中間結果のキャッシュを3回切り替えます。
  • STRCMPmemcmp vs. strcmpvs'1'をテストするためのソースコードにあります

NOT TODO 1：キャッシュされた値を使用したLOOP_BLOCKING-パフォーマンスを低下させます
TODO 2：上三角計算のみ
TODO 3changed_times[n] ：との意味を調べます-moments[0][p]
現在目立つように、計算は保存されません！

#include <stddef.h>
#define N 40
#define nsims 8000

#if ARRAY_OPT
#define TIMES(n,a) times[n][a]
double times[N+1][nsims]; // [nsims];
#else
#define TIMES(n,a) times[a][n]
double times[nsims][N+1];
#endif

#define STRCMP 1
// vs.
// #define STRCMP1 strcmp(mmethod, "emp")==0

void init()
{
#ifdef POPULATE
    int i,a;
    for (i=0;i<=N;i++)
      for (a=0;a<nsims;a++)
         TIMES(i,a) = (double)((i^a)&7) - 3.5;
#endif
}

  double moments[4000] = { 0 };
  double cache1[nsims];
  double cache2[nsims];

int main()
{
  int j,k,i,l,a, pcount=0;
  init();
  int changed_times[N+1]={0};
  char *mmethod="emp";

  double moment,interm;
  for(j=2;j<=N;j++) {     
    for(k=j;k<=N;k++) {
#if CACHELEVEL == 2
        for (a=0;a<nsims;a++) cache1[a]=TIMES(j,a)*TIMES(k,a);
#endif
        moment=0;
        for(i=2;i<=N;i++) {
#if CACHELEVEL == 3
            for (a=0;a<nsims;a++)         cache2[a]=TIMES(j,a)*TIMES(k,a)*TIMES(i,a);
#else
            for (a=0;a<nsims;a++) cache2[a]=cache1[a]*TIMES(i,a);
#endif
            for(l=i;l<=N;l++) {
                if(STRCMP) { 
                    for(a=0;a<nsims;a++) {
#if CACHELEVEL >= 2
                        interm += (double) cache2[a]*TIMES(l,a);
#else
                        interm=interm + (double) TIMES(k,a) * TIMES(j,a) * TIMES(i,a) * TIMES(l,a);
#endif
                    }
                    interm = (double) interm/(double)nsims;
                    moment = moment + (interm*i*l);
                    interm=0;
                }
            }
        }
        //if(!(changed_times[k]==0
        //     && changed_times[j]==0
        //     && changed_times[l]==0
        //     && changed_times[i]==0))
        //{
        //    moments[0][pcount]=(double) moment;
        //      changed_times[k]++;changed_times[j]++; /* or what? */
        //      changed_times[l]++;changed_times[i]++;
        //} else {
        //    moments[0][pcount]=moments[0][pcount];
        //}
        pcount++;
    }
  }
  printf("%d %f\n",pcount, moment);
}
于 2013-03-15T14:02:40.763 に答える
0

最初の明らかな最適化はstrcmp()、ループの外に移動することです。

文字列の比較にはかなりの時間がかかる場合があります（実際にはそれほど多くはありませんが、この呼び出しをこのように何度も繰り返すと、大きな違いが生じます）。また、この呼び出しはコンパイラによって最適化されることはない可能性がありますが、その結果は処理全体を通じて一定です。したがって、ネストされたループに入る前に結果を一時的なブール変数に格納し、ループ内のブールのみをテストします。

また、コードの一部を最適化しようとするときはいつものように、リリースターゲットを使用して（デバッグ情報なしで）コンパイルし、可能なすべてのコンパイラ最適化をオンにするようにしてください。

于 2013-03-15T14:10:50.120 に答える