2

100*100 の 2 つの大きな 2D 配列があります。操作を数回行う大きなループが 1 つあります。その中には 3 つのループがあります。最初のループでarr1は各セルの合計をarr2数値で乗算して格納し、2 番目のループでは 2 つの配列をファイルにストリーミングし、3 番目のループarr2では 2 つの配列の合計を数値で除算して格納します。

コードはよりよく説明します:

for(int i=1;i<x+1;i++) {//initialize
    for(int j=1;j<y+1;j++) {
        arr1[i][j]=i*j*5.5;
        arr2[i][j]=0.;
    }
}

for (int i=0;i<x+2;i++) {//padding
    vi[i][0]=5;
    vi[i][y+1]=-5;
}

for (int j=0;j<y+2;j++) {//padding
    vi[0][j]=10.;
    vi[x+1][j]=-10.;
}

for(int t=0;t<times;++t) {
    for(int i=1;i<x+1;++i) {
        for(int j=1;j<y+1;j++) {
            arr2[i][j]=(arr1[i+1][j]+arr1[i-1][j]+arr1[i][j-1]+arr1[i][j+1])*1.5;
        }
    }

    arr2[1][1]=arr2[1][y]=arr2[x][1]=arr2[x][y]=0.;

    for(int i=1;i<x+1;++i) {
        for(int j=1;j<y+1;j++) {
            arr1[i][j]=(arr1[i][j]+arr2[i][j])*0.5;

            if(arr2[i][j]+arr1[i][j]>5.)
                cout<<"\n"<<t<<"  "<<i-1<<" "<<j-1<<" "<<arr1[i][j]<<" "<<arr2[i][j];
        }
    }
}

コード全体が 14 秒以上で動作します。可能な限り最速で動作するようにコードを最適化するにはどうすればよいですか。

4

2 に答える 2

1

注: OP のコードは、パディングなどに関するコメントに応じて劇的に変更されました。元のコードには何も問題はありませんでした。これが、この回答に基づいています。

2D 配列が行優先 (最初のインデックスは行、2 番目のインデックスは列) でインデックス付けされていると仮定すると、メモリ アクセスは、最適なキャッシュ使用率のために既に正しい順序になっています (進行するにつれて近くの要素にアクセスしています)。 . 「maxi」の名前を「x」に変更したように見えるため、最新のコードはこの仮定に疑問を投げかけています。これは、列優先の2D配列にインデックスを付けていることを示唆しています（これはC / C ++の非常に非標準です）。

2D 配列を宣言する方法は指定されておらず、それによって違いが生じる可能性がありますが、生のポインターを使用するように実装を変換することで大きな改善が得られました。また、操作を組み合わせて反復ごとに方向を変えることで、(元の投稿から) 2 番目のループを排除しました。加重係数を変更して合計が 1.0 になるようにして、これをより簡単にテストできるようにしました (画像出力を生成することにより)。

typedef std::vector< std::vector<double> > Array2D;

void run( int x, Array2D & arr2 )
{

   Array2D temp = arr2; // easy way to create temporary array of the correct size

   int maxi=arr2.size(), maxj=arr2[0].size();

   for (int n=0;n<x;n++)
   {
      Array2D const & src = (n&1)?temp:arr2; // alternate direction
      Array2D & dst = (n&1)?arr2:temp;
      for (int i=1;i<maxi-1;i++)
      {
         double const * sp0=&src[i-1][1], * sp1=&src[i][1], * sp2=&src[i+1][1];
         double * dp=&dst[i][1];
         for (int j=1;j<maxj-1;j++)
         {
            dp[0]=(sp0[0]+sp1[-1]+4*sp1[0]+sp1[+1]+sp2[0])*0.125;
            dp++, sp0++, sp1++, sp2++;
         }
      }
   }

   if ( (x&1) ) arr2=temp; // copy the result back if the iteration count was odd
} /**/

あなたが調べることができる他のもの（多少プラットフォームに依存します）：

  • restrictポインターのキーワード (標準 C++ ではない)
  • プリフェッチ リクエスト -- コンパイラ/プロセッサ固有のメモリ アクセス レイテンシを削減する方法
  • コンパイル時に最適化が有効になっていることを確認してください
  • 配列のサイズによっては、利用可能なキャッシュをより有効に利用するために、アルゴリズムを列化する方が有利な場合があります。

利用可能なコンピューティング リソースを活用します (プラットフォームに大きく依存します)。

  • SIMDベースの実装を作成する
  • マルチコア CPU を活用 -- OpenMP
  • GPU を活用 -- OpenCL
于 2013-04-28T03:44:51.757 に答える
1

3 番目の配列を使用して、次の実行のために arr2 の配列値を一時的に格納できます。最初のループが完了したら、arr2 を一時配列で上書きします。このように、2 番目のループは必要ありません。時間の半分を節約できます。

for (n=0;n<x;n++)
{
   for (i=0;i<maxi;i++)
   {
      for (j=0;j<maxj;j++)
      {
         arr1[i][j]=(arr2[i+1][j]+arr2[i-1][j]+arr2[i][j+1]+arr2[i][j-1])*1.5;
         arr_tmp[i][j] = (arr1[i][j]+arr2[i][j])*0.5;
      }
   }
   arr2 = arr_tmp;
}
于 2013-04-28T01:46:11.390 に答える