行列乗算アルゴリズムのループの順序がパフォーマンスに影響するのはなぜですか？

Question

は、私は二つの行列の積を見つけるための二つの機能を与えられています：

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]; 
} 

私は走ったとgprof、この機能を除いて、同一のコードでそれぞれを使用して2つの実行可能ファイルをプロファイリング。これらの2番目のサイズは、サイズ2048 x 2048の行列の方が大幅に（約5倍）高速です。

Answer 1

あなたが見ているのは、locality of referenceがコンピュータのメモリ階層に与える影響です。

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

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

最後に、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つのキャッシュミスが発生する可能性が高くなります。

しかし、この第二のバージョンを検討：あなたは、各反復でjが増加していることから、今

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]; 

を、あなたはおそらく、最も内側の文にありますミスどのように多くのキャッシュについて考えてみましょう。値は行優先順序であるため、c[i][j]の値はキャッシュ内にある可能性があります。これは、前回の反復でのc[i][j]の値も同様にキャッシュされ、読み込み可能なためです。同様に、b[k][j]がおそらくキャッシュされており、iとkは変更されていないため、a[i][k]もキャッシュされます。これは、内部ループの各繰り返しで、キャッシュミスを起こさない可能性が高いことを意味します。

全体的に言えば、これは、コードの第2バージョンがループの各繰り返しでキャッシュミスを起こす可能性は低いことを意味しますが、最初のバージョンはほぼ確実です。その結果、2番目のループは最初に見たより高速になりそうです。

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

さらに、複雑なループを使用してこのループのパフォーマンスをさらに最適化できます。たとえば、blockingという手法を使用して、アレイをキャッシュに長く保持できるサブ領域に分割し、次にこれらのブロックで複数の演算を使用して全体の結果を計算することでパフォーマンスを大幅に向上させることができます。

希望すると便利です。

Answer 2

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

Answer 3

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

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

Answer 4

メモリの局所性は別として、コンパイラの最適化もあります。ベクトル演算と行列演算のキーとなるものは、ループアンローリングです。あなたはこの内部ループiとj変更しないで見ることができます

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

。これは、

• 4倍少ないのループが存在します

  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]

• [i]の[K]メモリ内で連続してアクセスされている。
• メモリアクセスと乗算はCPUで（ほぼ同時に）パイプライン化できる。

nが4または6または8の倍数でない場合はどうなりますか？ （またはコンパイラがそれを展開することを決定したもの）コンパイラは、この整頓をあなたのために処理します。;）

このソリューションを高速化するには、最初にb行列を転置してみてください。これは少し余分な作業とコーディングですが、b-transposedへのアクセスもメモリ内で連続していることを意味します。 （[k]を[j]と交換すると）

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

最後にあなたは浮動小数点演算がより重く（両方のハードウェアおよびコンパイラに）最適化することができますようしかし、それは必ずしもそうではありません、あなたがintが速くなると思いかもしれませんdoublefloatの使用を検討かあります

秒例では、c [i] [j]が各繰り返しで変化しているため、最適化が難しくなります。