研究日誌。

大規模なグラフ処理に対してメモリ階層構造を考慮した高性能なソフトウェアを開発。

広告

※このエリアは、60日間投稿が無い場合に表示されます。記事を投稿すると、表示されなくなります。

行列積とループ・ブロッキング。

2007-10-19 16:56:45 | Weblog
インテル日本語資料の「IA-32 インテルアーキテクチャー最適化」にも記されている、ループ・ブロッキングの有効性を検証してみた。
ループ・ブロッキングとは、キャッシュサイズを考慮してループをブロックすることである。
反復のたびにおきてしまうキャッシュミスを軽減することができ、キャッシュとメモリーのパフォーマンスを向上させることができる。

実験環境は Xeon 3.0GHz であるが、今回はスレッド数は1に固定した。ちなみにキャッシュサイズは 4096 KB となっている。
今回は 512 x 512 と 1024 x 1024 の2種類のみであるが、次の4パターンについてプロファイルしてみた。
(0) GotoBLAS (あくまでも参考)
(1) 通常の積演算
(2) 通常の積演算にループ・ブロッキングを適用
(3) 事前に行列Bに対して転置処理を行い、アクセス方向を修正した積演算
(4) 事前に行列Bに対して転置処理を行い、アクセス方向を修正した積演算に対してループ・ブロッキングを適用


ループの大きさによってかなりのバラツキがあることにおどろいた。
通常のループであれば、ブロックサイズは2~8程度と小さめで、
事前にアクセス方向を修正しておけば、256と大きめがよいようだ。


512 x 512
    1   2  4   8   16  32  64   128  256   512
(0)  35
(1) 1700
(2) 1500 765 825 1000 1327 1400 1420 1450 1450 1500
(3)  190
(4)  920 365 257  228  211 200  196  202 198  196


1024 x 1024
    1    2    4   8   16   32   64   128   256   512  1024
(0) 235
(1) 60000
(2) 65000 23300 10700 9600 11200 11500 11500 11800 11700 17500 54500
(3) 2550
(4) 7600  3050  2120 1800  1710 1625  1580  1626 1610  2050  2420


以下はソースコードの一部である。


 /* (1)通常の積演算 */
 for (m = 0; m < M; m++) {
  for (n = 0; n < N; n++) {
   for (k = 0; k < K; k++) {
    C[m * N + n] += A[m * K + k] * B[k * N + n];
   }
  }
 }


 /* (2)通常の積演算にループ・ブロッキングを適用 */
 for (m = 0; m < M; m+=block) {
  for (n = 0; n < N; n+=block) {
   for (k = 0; k < K; k+=block) {
    
    for (mm = m; mm < m+block; mm++) {
     for (nn = n; nn < n+block; nn++) {
      for (kk = k; kk < k+block; kk++) {
       C[mm * N + nn] += A[mm * K + kk] * B[kk * N + nn];
      }
     }
    }
    
   }
  }
 }

 /* (3)事前に行列Bに対して転置処理を行い、アクセス方向を修正した積演算 */
 for (m = 0; m < M; m++) {
  for (n = 0; n < N; n++) {
   for (k = 0; k < K; k++) {
    C[m * N + n] += A[m * K + k] * B[n * K + k];
   }
  }
 }

 /* (4)事前に行列Bに対して転置処理を行い、
   アクセス方向を修正した積演算に対してループ・ブロッキングを適用 */
 for (m = 0; m < M; m+=block) {
  for (n = 0; n < N; n+=block) {
   for (k = 0; k < K; k+=block) {
    
    for (mm = m; mm < m+block; mm++) {
     for (nn = n; nn < n+block; nn++) {
      for (kk = k; kk < k+block; kk++) {
       C[mm * N + nn] += A[mm * K + kk] * B[nn * K + kk];
      }
     }
    }
    
   }
  }
 }
ジャンル:
ウェブログ
コメント (2)   この記事についてブログを書く
« DMA転送と処理のバランス2。 | トップ | 分枝限定法。 »
最近の画像もっと見る

2 コメント

コメント日が  古い順  |   新しい順
Unknown (後藤)
2007-10-23 04:10:48
パラメータに 2^n を使うとキャッシュコンフリクトのために性能が大きく落ちるので使わない方がいいです。もし、このソースをそのまま使うならば、1020x1020 とか 504x504 がよろしいかと。
ついでに、商用コンパイラはこのループ形式を認識して別物に書き換えてしまうので、gcc の比較的古いバージョン(2.93 とか)を使うと素直な性能が出るので勉強になります。
Unknown (u1low_cheap)
2007-10-24 22:45:53
貴重な御意見ありがとうございます。
キャッシュコンフリクトまで考慮せずに、かなり安易に実験しておりました。
1020x1020 や 504x504 で試したところ、よりよい値が出ました。
今回はコンパイラは gcc-4.1.2 でやってみましたが、
古いヴァージョンでも試してみようと思います。
不慣れなことなので、試し試しやってはいるのですが、やはり難しいです。

コメントを投稿

Weblog」カテゴリの最新記事

関連するみんなの記事