18

2つの行列の積を見つけるための2つの関数が与えられます。

 void MultiplyMatrices_1(int **a, int **b, int **c, int n){
      for (int i = 0; i < n; i++)
          for (int j = 0; j < n; j++)
              for (int k = 0; k < n; k++)
                  c[i][j] = c[i][j] + a[i][k]*b[k][j];
  }

 void MultiplyMatrices_2(int **a, int **b, int **c, int n){
      for (int i = 0; i < n; i++)
          for (int k = 0; k < n; k++)
              for (int j = 0; j < n; j++)
                  c[i][j] = c[i][j] + a[i][k]*b[k][j];
 }

を使用して2つの実行可能ファイルを実行しgprof、プロファイリングしました。それぞれ、この関数を除いて同じコードを使用しています。これらの2つ目は、サイズが2048 x 2048のマトリックスの場合、大幅に（約5倍）高速です。理由について何か考えはありますか？

4

4 に答える 4

39

あなたが見ているのは、コンピュータのメモリ階層における参照の局所性の影響だと思います。

通常、コンピュータのメモリは、パフォーマンス特性が異なるさまざまなタイプに分類されます（これはメモリ階層と呼ばれることがよくあります）。最速のメモリはプロセッサのレジスタにあり、（通常は）単一のクロックサイクルでアクセスおよび読み取りが可能です。ただし、通常、これらのレジスタはほんの一握りです（通常は1KB以下）。一方、コンピュータのメインメモリは巨大ですが（たとえば8GB）、アクセスがはるかに遅くなります。パフォーマンスを向上させるために、コンピューターは通常、いくつかのレベルのキャッシュを持つように物理的に構築されていますプロセッサとメインメモリの間。これらのキャッシュはレジスタよりも低速ですが、メインメモリよりもはるかに高速です。したがって、キャッシュ内で何かを検索するメモリアクセスを実行すると、メインメモリに移動する必要がある場合よりもはるかに高速になる傾向があります（通常、5〜25倍）。もっと早く）。メモリにアクセスするとき、プロセッサは最初にメモリキャッシュでその値をチェックしてから、メインメモリに戻って値を読み込みます。キャッシュ内の値に一貫してアクセスすると、スキップする場合よりもパフォーマンスが大幅に向上します。メモリ、ランダムに値にアクセスします。

ほとんどのプログラムは、メモリ内の1バイトがメモリに読み込まれると、後でそのメモリ領域の周囲から複数の異なる値を読み取るように記述されています。したがって、これらのキャッシュは通常、メモリから単一の値を読み取るときに、その単一の値の周囲の値のメモリブロック（通常は1KBから1MBの間）もキャッシュに取り込まれるように設計されています。そうすれば、プログラムが近くの値を読み取った場合、それらはすでにキャッシュにあり、メインメモリに移動する必要はありません。

最後にもう1つ、C / C ++では、配列は行優先順に格納されます。つまり、行列の1つの行のすべての値が隣り合って格納されます。したがって、メモリ内では、配列は最初の行、2番目の行、3番目の行のようになります。

これを踏まえて、コードを見てみましょう。最初のバージョンは次のようになります。

  for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
          for (int k = 0; k < n; k++)
              c[i][j] = c[i][j] + a[i][k]*b[k][j];

それでは、コードの最も内側の行を見てみましょう。各反復で、kの値は増加して変化しています。これは、最も内側のループを実行しているときに、ループの各反復で、の値をロードするときにキャッシュミスが発生する可能性があることを意味しますb[k][j]。これは、行列が行優先の順序で格納されるため、kをインクリメントするたびに、行列の行全体をスキップして、キャッシュした値をはるかに超えてメモリにジャンプするためです。 。ただし、値は行優先の順序であり、の値が前の反復からキャッシュされているc[i][j]場合iはj、a[i][k]a[i][k]a[i][k]この反復での読み取りは、隣接するメモリ位置から行われます。その結果、最も内側のループの各反復で、1つのキャッシュミスが発生する可能性があります。

しかし、この2番目のバージョンを検討してください。

  for (int i = 0; i < n; i++)
      for (int k = 0; k < n; k++)
          for (int j = 0; j < n; j++)
              c[i][j] = c[i][j] + a[i][k]*b[k][j];

ここで、j反復ごとに増加しているので、最も内側のステートメントで発生する可能性のあるキャッシュミスの数について考えてみましょう。値は行優先の順序であるため、の値はc[i][j]キャッシュ内にある可能性がありc[i][j]ます。これは、前の反復からの値もキャッシュされ、読み取る準備ができているためです。同様に、b[k][j]はおそらくキャッシュされ、変更されiてkいないため、チャンスもa[i][k]キャッシュされます。これは、内部ループの各反復で、キャッシュミスが発生しない可能性が高いことを意味します。

全体として、これは、コードの2番目のバージョンでは、ループの各反復でキャッシュミスが発生する可能性が低いことを意味しますが、最初のバージョンではほぼ確実にキャッシュミスが発生します。その結果、これまで見てきたように、2番目のループは最初のループよりも高速になる可能性があります。

興味深いことに、多くのコンパイラは、コードの2番目のバージョンが最初のバージョンよりも高速であることを検出するためのプロトタイプサポートを開始しています。並列処理を最大化するためにコードを自動的に書き直そうとする人もいます。Purple Dragon Bookのコピーをお持ちの場合は、第11章でこれらのコンパイラの動作について説明します。

さらに、より複雑なループを使用して、このループのパフォーマンスをさらに最適化できます。たとえば、ブロッキングと呼ばれる手法を使用すると、配列をキャッシュに保持できるサブ領域に分割し、これらのブロックで複数の操作を使用して全体的な結果を計算することで、パフォーマンスを大幅に向上させることができます。

お役に立てれば！

于 2011-09-13T00:42:34.950 に答える
6

これは、メモリの局所性である可能性があります。ループを並べ替えると、最も内側のループで必要なメモリが近くなり、キャッシュできますが、非効率的なバージョンでは、データセット全体からメモリにアクセスする必要があります。

この仮説をテストする方法はcachegrind、2つのコードで（のような）キャッシュデバッガーを実行し、それらが発生するキャッシュミスの数を確認することです。

于 2011-09-13T00:34:56.260 に答える
1

メモリの局所性とは別に、コンパイラの最適化もあります。ベクトルおよび行列演算の重要なものは、ループ展開です。

for (int k = 0; k < n; k++)
   c[i][j] = c[i][j] + a[i][k]*b[k][j];

この内側のループiで見ることができ、j変更しないでください。これは、次のように書き直すことができることを意味します

for (int k = 0; k < n; k+=4) {
   int * aik = &a[i][k];
   c[i][j] +=
         + aik[0]*b[k][j]
         + aik[1]*b[k+1][j]
         + aik[2]*b[k+2][j]
         + aik[3]*b[k+3][j];
}

あなたはそこにあることがわかります

  • c[i][j]へのループとアクセスが4分の1になります
  • a[i][k]はメモリ内で継続的にアクセスされています
  • メモリアクセスと乗算は、CPUで（ほぼ同時に）パイプライン化できます。

n4または6または8の倍数でない場合はどうなりますか？（またはコンパイラーがそれを展開することを決定したものは何でも）コンパイラーはこの整理を自動的に処理します。;）

このソリューションをより速くスピードアップするには、b最初にマトリックスを転置してみてください。これは少し余分な作業とコーディングですが、b-transposedへのアクセスもメモリ内で継続的であることを意味します。（[k]を[j]と交換しているため）

パフォーマンスを向上させるためにできるもう1つのことは、乗算をマルチスレッド化することです。これにより、4コアCPUでパフォーマンスを3倍向上させることができます。

最後に、使用を検討するfloatか、より高速になるdoubleと思うかもしれませんintが、浮動小数点演算をより高度に最適化できるため（ハードウェアとコンパイラの両方で）、常にそうであるとは限りません。

2番目の例では、c [i] [j]が反復ごとに変化するため、最適化が困難になります。

于 2011-09-13T07:58:12.350 に答える
0

おそらく2つ目は、配列要素にアクセスするためにメモリ内をさらにスキップする必要があります。それは別のことかもしれません-コンパイルされたコードをチェックして、実際に何が起こっているかを確認することができます。

于 2011-09-13T00:34:45.317 に答える