ステンシル・カーネルの最適化
3次元の等方性ステンシル・カーネルについて、順をおって説明します。
使ったサンプルコードは C で書かれていますが、Fortran のバージョンもあります。
レジスタを効果的に使ってメモリのロードを減らしたり、
プリフェチの指示をうまく配置することで、R10Kプロセッサの性能を
引き出す最適化について説明します。
27点の3次元等方性ステンシル・カーネル アルゴリズム
27点の3次元等方性ステンシル・カーネル アルゴリズムは、3次元のグリッド
(配列 field_in)
上を、規則正しく移動します。各グリッドポイントでアルゴリズムはそのグリッドポイントと、
それに隣接した26個のポイントに基づく重みをかけて足し合わせた和を計算します。
その和は対応する2つ目の3次元グリッド(配列 field_out)に保存されます。
簡単のために、ここでは境界については考えず、表面上にないグリッドポイントについてのみ計算します。
図1 : この説明でのすべての座標系は同じです : i軸は垂直軸、j軸は水平軸で、
k軸は紙面に垂直な軸です。内側のループはいつもk軸に沿ったもので、
それはj軸に沿った真ん中の
ループと、i軸に沿った外側のループによってカプセル状に包まれています。
1つのグリッドポイントに対する等方的なステンシル計算が、重みを色で表した
ダイアグラムで示されています。
ステンシル・カーネルのプロトタイプ ( C ) :
for ( i=1; i< size_x1 ;i++)
for ( j=1; j< size_x2 ;j++)
for ( k=1; k< size_x3 ;k++)
{
out3 = weight3*( field_in[i-1][j-1][k-1]
+ field_in[i+1][j-1][k-1]
+ field_in[i-1][j+1][k-1]
+ field_in[i+1][j+1][k-1]
+ field_in[i-1][j-1][k+1]
+ field_in[i+1][j-1][k+1]
+ field_in[i-1][j+1][k+1]
+ field_in[i+1][j+1][k+1] );
out2 = weight2*( field_in[i ][j-1][k-1]
+ field_in[i-1][j ][k-1]
+ field_in[i+1][j ][k-1]
+ field_in[i ][j+1][k-1]
+ field_in[i-1][j-1][k ]
+ field_in[i+1][j-1][k ]
+ field_in[i-1][j+1][k ]
+ field_in[i+1][j+1][k ]
+ field_in[i ][j-1][k+1]
+ field_in[i-1][j ][k+1]
+ field_in[i+1][j ][k+1]
+ field_in[i ][j+1][k+1] );
out1 = weight1*( field_in[i ][j ][k-1]
+ field_in[i ][j ][k+1]
+ field_in[i ][j+1][k ]
+ field_in[i+1][j ][k ]
+ field_in[i-1][j ][k ]
+ field_in[i ][j-1][k ] );
out0 = weight0* field_in[i ][j ][k ];
field_out[i][j][k] = out0+out1+out2+out3;
}
4つの重みが1つもゼロでない時は、各グリッドポイントで
以下の計算とメモリ参照が必要です :
| 計算: |
加算 26 回 + 乗算 4 回 = 30 flops |
| ここまで減らせます: |
加算 15 回 + 乗算 3 回 = 18 flops |
| メモリ参照: |
ロード 27 回 + ストア 1 回 = 20 mem ref. |
| ここまで減らせます: |
ロード 9 回 + ストア 1 回 = 10 mem ref. |
演算回数の減少は、前に使ったグリッドポイントのデータ要素と計算を再使用することにより
実現されます。ここで、加算と乗算のバランスが同じでないということが重要です。
R10K には2つの浮動小数点ユニットがあり、その1つは加算のため、もう1つは乗算の
ためのものです。
この計算では加算のパイプラインがクリティカルリソースであり、このカーネルの性能を
240 MFlops に制限しています。
このテキストを通して、(i,j) 面または (j,k) 面は、2つのインデックスの繰り返しと、3つめの
インデックスを定数として決めることによって定義される平面であるとします。
C コードのコンパイル
ソースコード(stencil.c)は、異なるサブルーチンのカーネル
ループの各バージョンを含んでいます。
全ての例は SGIのコンパイラ バージョン 7.0.1 で、以下の
オプションを使ってコンパイルしました :
wutbreugel % cc -n32 -mips4 -O3 stencil.c -o stencil
いい計算コードを通常生成するコンパイラオプションがいくつかあります
(詳しくは、 cc(1) リファレンス ページを参照) :
| -n32 |
64ビット レジスタセットと 効率のよいコーリング規約を使う。 |
| -mips4 |
R10000 インストラクション フルセット のコンパイル。 |
| -O3 |
多くのコンパイラ最適化を可能にする。 |
| -OPT:roundoff=3 |
数学的に有効なあらゆるコード変換を丸め誤差を気にせず許可する |
| -OPT:IEEE_arithmetic=3 |
IEEE 精度に違反するかもしれない数学的に有効な変換を許可する。
例 : x/y --> x*recip(y) |
| -CLIST:=ON |
最適化されたプログラムのCソースを参照のために生成する。 |
一番内側のループの詳細が分かる、静的なソフトウェアパイプライニング(SWP)の
コンパイラのメッセージを得るには、注釈のついたアセンブリソースを得るための
-S オプションを使ってコンパイルしてから、そのソース中で探します。
cc (above options)... -S stencil.c
grep swps stencil.s
C コードの実行
ステンシル メインプログラムのコマンド引数は以下の通りです :
- ステンシル計算の繰り返しの数。
- グリッドのサイズ。このコードでは、すべての次元が同等の(キュービックな)3次元グリッドのみを使います。
- 使用するステンシル カーネルのバージョン。
(上のリストにあるように、0 がオリジナルのバージョンです)
試しに実行すると、以下と同様の結果が出ます :
wutbreugel % stencil 100 10 0
stencil 100 10 0
repeating stencil: 100
grid-size: 10 x 10 x 10 = 1000
optimization version: 0
size of the 3D-grid: 0.000954 MByte
0.030000 seconds: 585.938 nanoseconds per grid-point
最適化されたバージョン 0 のアルゴリズムで、40x40x40 グリッドを1000回実行
( R10k/4MB-195MHz の Origin2000 で計測 ) :
[crush]chem 195% stencil 1000 40 0
stencil 1000 40 0
repeating stencil: 1000
grid-size: 40 x 40 x 40 = 64000
optimization version: 0
size of the 3D-grid: 0.512000 MByte
40 0.512000 MByte 14.23 sec per grid-point: 259.331 ns 50.6 cycles
もっとも重要な数値は、グリッド ポイントあたりのプロセッサ サイクル数です。
この測定は、ステンシル サブルーチンを数回繰り返して計測し、
内部のグリッド ポイントと繰り返しの数によってその時間を割ることにより、
得られます。
この時間はns(ナノ秒)によっても与えられ、それは実際のCPUサイクルに
変換されます。
プロセッサのクロックレートは、プログラム中で明示的にコーディングされている
ことに注意して下さい。
/* R10K specific definition */
#define MHZ 195
double nanoseconds_per_cycle = 1000./MHZ ;
Cでの多次元配列とエイリアシング
Cは多次元配列にとても多様な方法でアクセスします。そしてこれがコンパイラにとって
ひどい頭痛の種となっています。本質的な難しさは、field[i][j][k] のような
エレメントの参照が、ポインタ-->ポインタ-->エレメント というように
行われることです。
この問題は、カーネルループのためのソフトウェアパイプライニングのコメントで
明らかです。
#<swps> 100 estimated iterations before pipelining
#<swps> Not unrolled before pipelining
#<swps> 49 cycles per iteration
#<swps> 30 flops ( 30% of peak) (madds count as 2)
#<swps> 27 flops ( 27% of peak) (madds count as 1)
#<swps> 3 madds ( 6% of peak)
#<swps> 42 mem refs ( 85% of peak)
#<swps> 16 integer ops ( 16% of peak)
#<swps> 85 instructions ( 43% of peak)
#<swps> 0 short trip threshold
#<swps> 17 ireg registers used.
#<swps> 12 fgr registers used.
#<swps>
#<swps> 42 min cycles required for resources
#<swps> 49 cycles in minimum schedule found
一番内側のループのスケジューリングについてのこれらのコンパイラの注釈は、
コンパイラができる最適化の度合いについてのさらなる情報を与えてくれます。
ピークのパーセンテージは、クリティカルパスが何かを最初に教えてくれます。
この場合には、42のメモリ参照("mem refs") があります。R10K はサイクル毎に 1 メモリ参照を
扱うので、他のすべての命令がこの参照の周辺にあるとして、メモリ参照の間に
相互依存がないと仮定した時、最小のスケジュールは 42 サイクルとなります。
この一番内側のループでは、なぜこんなにたくさんのメモリ参照があるのでしょうか。
コンパイラは、 field_out の各ストアが、与えられたいかなるポインタをも変える
可能性がある、という慎重な推測をせざるを得ません。これはすべてのポインタが
各サイクル毎にロードされることを意味します。これが、
SWPレポートのたくさんのメモリ参照の要因です。
ロードされるもの :
- field_inへの最初の3つのポインタのセット : i-1, i, i+1 (3 ロード)
- ポインタの2番目のセット : j-1, j, j+1 (3x3 ロード)
- グリッド エレメント自身 : 27 ロード
- field_out のアップデート : 2 ポインタ + 1 ストア
合計 : 42 メモリ参照
我々はポインタがデータエレメントとオーバーラップしないと知っていますが、
コンパイラがそれを仮定することはできません。それゆえ、
私達がコンパイラディレクティブに
-OPT:alias=disjoint を加えなければなりません :
#<swps> 100 estimated iterations before pipelining
#<swps> Not unrolled before pipelining
#<swps> 28 cycles per iteration
#<swps> 30 flops ( 53% of peak) (madds count as 2)
#<swps> 27 flops ( 48% of peak) (madds count as 1)
#<swps> 3 madds ( 10% of peak)
#<swps> 28 mem refs (100% of peak)
#<swps> 12 integer ops ( 21% of peak)
#<swps> 67 instructions ( 59% of peak)
#<swps> 2 short trip threshold
#<swps> 14 ireg registers used.
#<swps> 15 fgr registers used.
コンパイラはもうポインタをリロードしないですむので、この結果、内部ループのサイクル数
は49サイクルから28サイクルに落ちます。28のメモリ参照は、正確には27の field_in
エレメントと 1つの field_out エレメントです。ポインタによるオーバーヘッドは
もうありません。
40x40x40 のグリッドの計測を見てみましょう :
[crush]chem 193% timex stencil 1000 40 0
stencil 1000 40 0
repeating stencil: 1000
grid-size: 40 x 40 x 40 = 64000
optimization version: 0
size of the 3D-grid: 0.512000 MByte
40 0.512000 MByte 9.43 sec per grid-point: 171.854 ns 33.5 cycles
ポイントあたりのサイクル数の測定結果は50サイクルから33.5サイクルに減っています。
これはコンパイラによる静的なスケジューリングのSWPレポートとよく一致しています。
SWPレポートはキャッシュミスのペナルティのサイクルや、ループの始まりと終わりの
オーバーヘッドまで考慮することはできません。SWPレポートはループの安定した部分に
ついてのみ話をするので、めったに到達できない理想の結果を提示します。
最適化1. 配列をベクトルへと移す(C-限定)
alias=disjoint を使って、各繰り返しでのポインタのリロードを防ぐことができました。
平面 k+1 のエレメントが次の2つの繰り返しでも再使用できることをコンパイラに
理解させるためには、1次元配列の明示的な使用が効果的です。これは、コーディングの努力
によってなされます :
for ( i=1; i< size_x1-1 ;i++)
for ( j=1; j< size_x2-1 ;j++)
for ( k=1; k< size_x3-1 ;k++) {
field_out[i][j][k] = ....
}
の代わりに :
for ( i=1; i< size_x1-1 ;i++) {
pout_i = field_out[i];
for ( j=1; j< size_x2-1 ;j++) {
pout_i_j = pout_i[j];
for ( k=1; k< size_x3-1 ;k++) {
pout_i_j[k] = ...
}
を使います。
これは field_in の 3x3 すべてのポインタと、 field_out の 1つのポインタ
についてなされなければならず、これはいくつかの重要なコーディングを
代表しています
(ソースの subroutine Stencil_27Point_Isotrope_O1 を参照)。
結果は次のようになります :
#<swps> 100 estimated iterations before pipelining
#<swps> Not unrolled before pipelining
#<swps> 14 cycles per iteration
#<swps> 18 flops ( 64% of peak) (madds count as 2)
#<swps> 15 flops ( 53% of peak) (madds count as 1)
#<swps> 3 madds ( 21% of peak)
#<swps> 10 mem refs ( 71% of peak)
#<swps> 11 integer ops ( 39% of peak)
#<swps> 36 instructions ( 64% of peak)
#<swps> 2 short trip threshold
#<swps> 13 ireg registers used.
#<swps> 23 fgr registers used.
サイクル数は 14 サイクル、たった 10 のメモリ参照に減ります。これらの 10 のメモリ参照は
前にある (k+1) 平面の 3x3 のグリッドポイントと、 field_out のストアです。
k と k-1 平面のすべてのエレメントはレジスタに保持され、次の繰り返しで再使用されます。
実際にはエレメントの値ではなく、図2に kp_0, kp_1, kp_2 という値で描かれている、
途中段階の和が保持されます :
図2 : k+1 平面のデータポイントは、 field_out の値を計算するのに使われる 3 つの値に
足し合わされます。平面の個々の9つの値をいちいち保持する必要はありません。
修正されたアルゴリズムを使った 40x40x40 のテストケースについて計測します( 3番目の
引数は、このカーネルのバージョンを選ぶために 1 となります) :
[crush]chem 236% stencil 1000 40 1
stencil 1000 40 1
repeating stencil: 1000
grid-size: 40 x 40 x 40 = 64000
optimization version: 1
size of the 3D-grid: 0.512000 MByte
40 0.512000 MByte 5.38 sec per grid-point: 98.046 ns 19.1 cycles
サイクル数の測定結果は 19.1 で静的なコンパイラでの数 14 に極めて近いです。
キャッシュのスラッシングとキャッシュの局所性
このバージョンのコードを使って、広範囲のグリッドサイズでの性能を知ることが
重要です。
図3 : 8x8x8 から 743x743x743 までのレンジの立方グリッドを使って、
グリッドポイントあたりのCPUサイクルをプロットしたもの
( R10K/195MHz 4MBのキャッシュを持つ Origin2000 で測定 )。
図3のピークは1次と2次両方のキャッシュのスラッシングによるものです。
1次キャッシュは 2-way セット連想方式で、32 バイトの大きさです。
これは、2の14乗バイト(±32バイト)の倍数だけ離れたグリッドポイントが、
1次キャッシュラインのスラッシングを起こす可能性があることを意味します。
同じことが、4MB の大きさで2-wayセット連想方式である 2次キャッシュ
においても起こります。2次キャッシュでスラッシングを起こすには、
グリッドポイントが 2の21乗以上離れている必要があります。これは、2次元の
グリッドを使うには次元あたり 512グリッドポイントのオーダーでなければならない
ことを意味します。
図3の 512x512x512 のグリッドサイズでの大きなピークを見ると、2次キャッシュが
メモリと1次キャッシュの間でピンポンを引き起こして、性能を 30分の1に減らしている
と分かります。小さなピークは 1次キャッシュのスラッシングによるものです。
このシナリオでは、キャッシュラインは 1次と 2次キャッシュの間でピンポンを
しているだけで、約5倍の性能低下を引き起こしています。
キャッシュのスラッシングをもっと理解できるように、3次元配列の任意の
アクセスパターンをもち、グリッドのサイズを変えてキャッシュのスラッシングを
チェックできるシミュレータ
(thrash.c)
を用意ました。プロセッサ特有のパラメータとアクセスパターンが、
コードに直接書き込まれています。本質的なルーチンは、
メモリ参照あたりのスラッシングの
可能性を返す double thrash_penalty です。
図4 : 立方グリッドサイズに対する、(任意のユニットの)
キャッシュスラッシングペナルティ
のシミュレーションです。スラッシングをおこす 2次と 1次のキャッシュの間のペナルティ
率は 10 です。
32の倍数(±1)のすべての次元はキャッシュのスラッシングを起こす問題を
抱えています。
しかし、キャッシュの問題がある他の次元( 90, 91, 442, 779, …)もあります。立方でない
グリッドサイズを見てみると、キャッシュの問題を見つけるのに簡単な構造は
していません。
よって、キャッシュのフレンドリネスを計算するにはフルシミュレーションプログラム
が使われなければなりません。
立方グリッドの場合では、キャッシュの影響を克服するために配列にパッディングを
するという簡単で直接的な方法があります :
- 32の倍数±1のすべての次元は 3,2 あるいは 1 を足されるので、その結果できる
次元はピークから 2 離れています。2 は 256のような 2の冪乗の次元と 255, 257 でもまた
キャッシュのスラッシングが起こることからきています。サンプルコードで使っている
C では、この修正をグリッドのメモリを割り当てる手続きの中に容易に
含めることができます。
しかし Fortran では、配列の大きさをグリッドにアクセスするすべての
サブルーチンに渡されなければなりません。
- サンプルコードでパッディングを使うには、コンパイル時に -DPADDING という
オプションをつけます。
図5 : 立方グリッドで 8x8x8 から 743x743x743 までのレンジで、
パッディングのスイッチを ON にして、
R10K/195MHz, 4MB のキャッシュの Origin2000 で測定した、
グリッドポイントあたりの CPUサイクルをプロットしたものです。
パッディングの機能を使ってキャッシュのスラッシングの大部分を除去できたので、
小さなピークだけが見えます。振動の大部分は測定の不確定性によるものです。
ステンシルカーネルの性能のプロファイルは、今やグリッドのサイズによって
決まります。グリッドのサイズにより、データは1次または 2次キャッシュにフィット
するか、悪い時にはメモリから聞き出されます。グリッドサイズをいくつか
選んでみると、以下のようになります :
| グリッド |
1列のサイズ |
キャッシュのフィット |
1平面のサイズ |
キャッシュのフィット |
3Dグリッドのサイズ |
キャッシュのフィット |
| 16x16x16 |
128 byte |
1次 |
2 kbyte |
1次 |
32 kbyte |
1次 |
| 32x32x32 |
256 byte |
1次 |
8 kbyte |
1次 |
256 kbyte |
2次 |
| 40x40x40 |
320 byte |
1次 |
13 kbyte |
1次 |
512 kbyte |
2次 |
| 64x64x64 |
512 byte |
1次 |
32 kbyte |
1次 |
2 Mbyte |
2次 |
| 100x100x100 |
800 byte |
1次 |
80 kbyte |
2次 |
8 Mbyte |
メモリ |
| 128x128x128 |
1 kbyte |
1次 |
128 kbyte |
2次 |
16 Mbyte |
メモリ |
| 256x256x256 |
2 kbyte |
1次 |
512 kbyte |
2次 |
128 Mbyte |
メモリ |
| 512x512x512 |
4 kbyte |
1次 |
2 Mbyte |
2次 |
1 Gbyte |
メモリ |
| 1024x1024x1024 |
8 kbyte |
1次 |
8 Mbyte |
メモリ |
16 Gbyte |
メモリ |
図5 を見ると領域がはっきりと区別できます :
- 64x64x64 までのグリッドサイズ :
両方のグリッド(field_in,field_out) が2次キャッシュ(4MB)にフィットします。
1つの平面全体は1次キャッシュにフィットします。これにより、メモリの階層は
とても高い局所性を持ち、その性能はとてもよくて、グリッドポイントあたり
約20サイクルとなります。グリッド数が小さくなった時のサイクル数の増加は、
ループの繰り返しが小さくなるのに比例して大きくなる、ループの始めと終わりの
オーバーヘッドによるものです。
- 64x64x64 と 256x256x256 の間 :
field_in, field_out どちらのグリッドも2次キャッシュにフィットしないので、繰り返しの度に
メモリからロードされます。グリッドの個々の平面も1次キャッシュにフィットせず、
2次と1次キャッシュの余計なやりとりがなされます。これにより、繰り返しあたり
約30サイクル 、50%の性能低下が起こります。
(90x90x90 のピークは、使用したパッディング プロシージャでは直せなかった
キャッシュのスラッシングによるものです。)
- 256x256x256 以上 :
3Dグリッドは 512MBあるローカルノードのメモリでは全部をフィットしきれません。
よってグリッドの一部はリモートノードからロードされねばなりません。
リモートメモリへのアクセスの割合は、グリッドサイズとともに大きくなるので、
性能が落ちてサイクル数が増加します。
3Dグリッドの一辺の大きさも 大きくなって1次キャッシュのサイズに近づくので、
1次キャッシュの再使用もしだいに減っていきます。
perfex を使って プログラムの振舞いを分析する
40x40x40, 100x100x100, 400x400x400 の例を使って、R10K ハードウェアカウンタで
メモリ階層の実際のやりとりが、我々の考えと一致するかどうか見てみましょう。
perfex コマンドを使うと、コードの修正や再コンパイルなしで、
これらのカウンタに簡単にアクセスできます。perfex はプログラムの最初にのみ
カウンタを初期化して実行の最後でカウンタを読むので、性能への影響は
全くありません。
（注意 : perfex -a はカウンタを時分割して計測するので、
近似のカウントを示します。
--- 詳しくは、 perfex(1), r10k_counters(5), speedshop(1) を参照)
図6:k方向から見下ろした、9つの領域の列が示されています。
色はエレメントに対するキャッシュミスの可能性を表します。
無色 : たぶんキャッシュにある、 ピンク : 2次キャッシュにある、 青 : まだメモリか
2次キャッシュにある。
40x40x40 のケースの分析
[crush]chem 162% perfex -a -y stencil 10000 40 1
Based on 200 MHz IP27
Typical Minimum Maximum
Event Counter Name Counter Value Time (sec) Time (sec) Time (sec)
===================================================================================================================
0 Cycles...................................................... 10805619600 54.028098 54.028098 54.028098
16 Cycles...................................................... 10805619600 54.028098 54.028098 54.028098
21 Graduated floating point instructions....................... 8404698288 42.023491 21.011746 2185.221555
2 Issued loads................................................ 5593321184 27.966606 27.966606 27.966606
18 Graduated loads............................................. 5469415872 27.347079 27.347079 27.347079
25 Primary data cache misses................................... 598859936 26.978640 8.593640 26.978640
22 Quadwords written back from primary data cache.............. 290076256 5.583968 4.467174 6.483204
3 Issued stores............................................... 699103312 3.495517 3.495517 3.495517
19 Graduated stores............................................ 699027888 3.495139 3.495139 3.495139
6 Decoded branches............................................ 578314480 2.891572 2.891572 2.891572
24 Mispredicted branches....................................... 14847952 0.100224 0.032665 0.371941
26 Secondary data cache misses................................. 26800 0.023907 0.014119 0.025528
7 Quadwords written back from scache.......................... 436096 0.016576 0.016576 0.030091
9 Primary instruction cache misses............................ 23616 0.002128 0.000677 0.002128
10 Secondary instruction cache misses.......................... 592 0.000528 0.000312 0.000564
23 TLB misses.................................................. 352 0.000118 0.000118 0.000118
1 Issued instructions......................................... 25774011616 0.000000 0.000000 128.870058
4 Issued store conditionals................................... 0 0.000000 0.000000 0.000000
5 Failed store conditionals................................... 0 0.000000 0.000000 0.000000
8 Correctable scache data array ECC errors.................... 0 0.000000 0.000000 0.000000
11 Instruction misprediction from scache way prediction table.. 16784 0.000000 0.000000 0.000084
12 External interventions...................................... 52288 0.000000 0.000000 0.000000
13 External invalidations...................................... 66352 0.000000 0.000000 0.000000
14 Virtual coherency conditions................................ 0 0.000000 0.000000 0.000000
15 Graduated instructions...................................... 21148749104 0.000000 0.000000 105.743746
17 Graduated instructions...................................... 21156938912 0.000000 0.000000 105.784695
20 Graduated store conditionals................................ 0 0.000000 0.000000 0.000000
27 Data misprediction from scache way prediction table......... 785520 0.000000 0.000000 0.003928
28 External intervention hits in scache........................ 52240 0.000000 0.000000 0.000000
29 External invalidation hits in scache........................ 42304 0.000000 0.000000 0.000000
30 Store/prefetch exclusive to clean block in scache........... 0 0.000000 0.000000 0.000000
31 Store/prefetch exclusive to shared block in scache.......... 0 0.000000 0.000000 0.000000
Statistics
=========================================================================================
Graduated instructions/cycle................................................ 1.957199
Graduated floating point instructions/cycle................................. 0.777808
Graduated loads & stores/cycle.............................................. 0.570855
Graduated loads & stores/floating point instruction......................... 0.748679
Mispredicted branches/Decoded branches...................................... 0.025675
Graduated loads/Issued loads................................................ 0.977848
Graduated stores/Issued stores.............................................. 0.999892
Data mispredict/Data scache hits............................................ 0.001312
Instruction mispredict/Instruction scache hits.............................. 0.728978
L1 Cache Line Reuse......................................................... 9.300311
L2 Cache Line Reuse......................................................... 22344.520000
L1 Data Cache Hit Rate...................................................... 0.902916
L2 Data Cache Hit Rate...................................................... 0.999955
Time accessing memory/Total time............................................ 1.070644
L1--L2 bandwidth used (MB/s, average per process)........................... 440.599224
Memory bandwidth used (MB/s, average per process)........................... 0.192639
MFLOPS (average per process)................................................ 155.561617
perfex -a -y コマンドは、アプリケーションのクリティカルな問題を理解するのに
必要な情報をすべて教えてくれます。重要な特徴の1つは、すべてのカウンタがその
重要性に関連してソートされていてるので、何が問題なのかがすばやくわかるということです。
40x40x40 グリッドの場合では、サイクル数(0+16)に続くのは、Graduated floating point
instruction (21) です。これは、メモリの局所性や、分岐予測の
ような他の問題が、影響を与えていないことを示しています。1次キャッシュミス(25)
が6番目にあることもこれを裏打ちしています。以下では、カウント数と率が予期した値を
示しているかを見てみます。
最初は ストアについて考えます :
ストアの大部分は、内部のグリッドポイント field_out の
ストアです : 39x39x39=59319 x 1000回繰り返し = 59319000 ; これを終了したストアの
699027888と比較すると、16%だけ少ないので、考えていなかった別のストアがあります。
次は、ロードです : field_out あたり 9ロード : 59319000 x 9 = 5338710000 ;
終了したロードの 5469415872 と比べると、とてもよく一致しています。
L2 キャッシュ ヒット レートはほとんどすべてのリクエストが2次キャッシュに
ヒットしたことを教えてくれます ; よって、3D グリッドが 2次キャッシュに収まる
という想定は正しかったことが分かります。
L1 から L2のバンド幅は 440.6MB/s です ; 54秒で23760MB、すなわちテストの繰り返し
あたり約 2.4 MB が これらのキャッシュ間を移動しました。
L1キャッシュラインの再使用は 9.3 です。各1次キャッシュラインは 4つの倍精度の値を
保持できます。よって、長いベクトルを連続的にスイープするとその結果
3.0の再使用になります。1回のキャッシュミスが3回のロードあたります。
再使用の定義:再使用 = ((ロード+ストア)-(L1 ミス))/(L1 ミス)
3つの参照 ([i-1][j+1]; [i][j+1]; [i+1][j+1])は 4サイクル毎にそれぞれキャッシュ
ミスを起こします。これは出力ストアについても同様です。この 4サイクルは次の
ようになります。
((9 x 4 ロード + 1 x 4 ストア)-(3 ロードミス + 1 ストアミス))/(3 ロードミス + 1 ストアミス) = 9
メモリと 2次キャッシュの間のデータの流れ(メモリバンド幅のカウント)がとても
小さいことに注意して下さい。
小さなグリッドでは、2次と1次キャッシュの間で近似的に3Dグリッドのサイズの5倍の
メモリのやりとりがあります。図6で見られるように、影つきのエレメントは2次
キャッシュからリロードされねばならず、その結果1次キャッシュラインの再使用は
約 9 : 1 になります。
100x100x100 のケースの分析
[crush]chem 163% perfex -a -y stencil 1000 100 1
Based on 200 MHz IP27
Typical Minimum Maximum
Event Counter Name Counter Value Time (sec) Time (sec) Time (sec)
===================================================================================================================
0 Cycles...................................................... 26316543840 131.582719 131.582719 131.582719
16 Cycles...................................................... 26316543840 131.582719 131.582719 131.582719
26 Secondary data cache misses................................. 123465776 110.140115 65.043005 117.607325
21 Graduated floating point instructions....................... 14233701936 71.168510 35.584255 3700.762503
25 Primary data cache misses................................... 989541584 44.578848 14.199922 44.578848
2 Issued loads................................................ 8911256400 44.556282 44.556282 44.556282
18 Graduated loads............................................. 8825192992 44.125965 44.125965 44.125965
7 Quadwords written back from scache.......................... 482092816 18.324348 18.324348 33.264404
22 Quadwords written back from primary data cache.............. 485860208 9.352809 7.482247 10.858976
3 Issued stores............................................... 1044075552 5.220378 5.220378 5.220378
19 Graduated stores............................................ 1043442752 5.217214 5.217214 5.217214
6 Decoded branches............................................ 961839184 4.809196 4.809196 4.809196
23 TLB misses.................................................. 597856 0.200760 0.200760 0.200760
24 Mispredicted branches....................................... 9710624 0.065547 0.021363 0.243251
10 Secondary instruction cache misses.......................... 62544 0.055794 0.032949 0.059576
9 Primary instruction cache misses............................ 138848 0.012510 0.003978 0.012510
30 Store/prefetch exclusive to clean block in scache........... 896 0.000004 0.000004 0.000004
1 Issued instructions......................................... 42562327616 0.000000 0.000000 212.811638
4 Issued store conditionals................................... 0 0.000000 0.000000 0.000000
5 Failed store conditionals................................... 0 0.000000 0.000000 0.000000
8 Correctable scache data array ECC errors.................... 0 0.000000 0.000000 0.000000
11 Instruction misprediction from scache way prediction table.. 17424 0.000000 0.000000 0.000087
12 External interventions...................................... 41856 0.000000 0.000000 0.000000
13 External invalidations...................................... 62432 0.000000 0.000000 0.000000
14 Virtual coherency conditions................................ 0 0.000000 0.000000 0.000000
15 Graduated instructions...................................... 34857136288 0.000000 0.000000 174.285681
17 Graduated instructions...................................... 34850650896 0.000000 0.000000 174.253254
20 Graduated store conditionals................................ 0 0.000000 0.000000 0.000000
27 Data misprediction from scache way prediction table......... 991168 0.000000 0.000000 0.004956
28 External intervention hits in scache........................ 41792 0.000000 0.000000 0.000000
29 External invalidation hits in scache........................ 59632 0.000000 0.000000 0.000000
31 Store/prefetch exclusive to shared block in scache.......... 0 0.000000 0.000000 0.000000
Statistics
=========================================================================================
Graduated instructions/cycle................................................ 1.324533
Graduated floating point instructions/cycle................................. 0.540865
Graduated loads & stores/cycle.............................................. 0.374997
Graduated loads & stores/floating point instruction......................... 0.699420
Mispredicted branches/Decoded branches...................................... 0.010096
Graduated loads/Issued loads................................................ 0.990342
Graduated stores/Issued stores.............................................. 0.999394
Data mispredict/Data scache hits............................................ 0.001144
Instruction mispredict/Instruction scache hits.............................. 0.228350
L1 Cache Line Reuse......................................................... 8.972937
L2 Cache Line Reuse......................................................... 7.014703
L1 Data Cache Hit Rate...................................................... 0.899729
L2 Data Cache Hit Rate...................................................... 0.875229
Time accessing memory/Total time............................................ 1.552354
L1--L2 bandwidth used (MB/s, average per process)........................... 299.728523
Memory bandwidth used (MB/s, average per process)........................... 178.724870
MFLOPS (average per process)................................................ 108.173034
40x40x40 の perfex の出力と比べると、100x100x100 のオーダーのケースは
強烈に異なります。パフォーマンスの主な問題について見てみると、
2次キャッシュミスの CPU サイクルの方が、
浮動小数点演算のそれよりも多いことを説明しています。
他のCPU演算と完全にオーバーラップするという最善のケースでも、
CPUがミスのためにアイドル状態となって、65秒(最小カラム)という結果が出ます。
ロードとストアの計数が理論とよく一致することを自分で証明できます。
L1-L2間のデータの移動 : 299.7 MB/s x 131.6 sec = 39440 MB これが
39.44 MB/繰り返し
をもたらします。この結果は以前の実験と同じように、今のグリッドサイズ8MBが
L1キャッシュを通して5回渡されるのと一致します。よってここでも連続した
ステンシルが1次キャッシュに留まります。L1キャッシュラインの再使用率は
40x40x40のケースと同じくらいです。
この実験ではメモリバンド幅が著しく使用されています。これはグリッド全部は2次
キャッシュにフィットせず、メモリからロードされねばならないことを示します。
178.7MB/s x 131.6 sec = 23500 MB のレート、すなわち テストの繰り返し毎に
メモリとキャッシュの間で 23MB が移動します。
出力ストアはキャッシュからメモリへと同様にメモリからキャッシュへの移動を
全部で 16MB 引き起こします。残りの 8MB は入力配列のロードであり、ここでも
すべてが矛盾なく説明できます。
2次キャッシュラインの再使用率を考えます。2次キャッシュラインは4つの1次
キャッシュラインを保持します。連続したグリッドの平面は2次キャッシュラインに
フィットするので、 field_out と図1の暗い影のエレメントは4回の
1次キャッシュミスの度にメモリからロードされなければなりません。全部で
(3+1)x4 の1次キャッシュミスがありますが、2次キャッシュミスはたった2回です:
(16-2)/2 = 7 これはレポートの示している値とぴったり一致します。
400x400x400 のケースの分析
eo2k1 % perfex -y -a stencil 20 400 1
WARNING: Multiplexing events to project totals--inaccuracy possible.
Based on 196 MHz IP27
Typical Minimum Maximum
Event Counter Name Counter Value Time (sec) Time (sec) Time (sec)
===================================================================================================================
0 Cycles...................................................... 55179443008 281.527770 281.527770 281.527770
16 Cycles...................................................... 55179443008 281.527770 281.527770 281.527770
25 Primary data cache misses................................... 2764968272 127.103899 39.781686 127.103899
26 Secondary data cache misses................................. 320287360 123.375998 80.660123 137.266011
21 Graduated floating point instructions....................... 19096750144 97.432399 48.716199 5066.484732
2 Issued loads................................................ 11616291984 59.266796 59.266796 59.266796
18 Graduated loads............................................. 11533211520 58.842916 58.842916 58.842916
7 Quadwords written back from scache.......................... 756560032 24.704001 16.327801 24.704001
22 Quadwords written back from primary data cache.............. 770880608 15.142298 12.349822 17.502136
3 Issued stores............................................... 1553602032 7.926541 7.926541 7.926541
19 Graduated stores............................................ 1552211424 7.919446 7.919446 7.919446
6 Decoded branches............................................ 1365026288 6.964420 6.964420 6.964420
23 TLB misses.................................................. 1526912 0.530446 0.530446 0.530446
9 Primary instruction cache misses............................ 458896 0.042190 0.013182 0.042190
10 Secondary instruction cache misses.......................... 103344 0.039809 0.026026 0.044290
24 Mispredicted branches....................................... 3340448 0.024201 0.010908 0.088965
30 Store/prefetch exclusive to clean block in scache........... 128 0.000001 0.000001 0.000001
1 Issued instructions......................................... 62520501824 0.000000 0.000000 318.982152
4 Issued store conditionals................................... 0 0.000000 0.000000 0.000000
5 Failed store conditionals................................... 0 0.000000 0.000000 0.000000
8 Correctable scache data array ECC errors.................... 0 0.000000 0.000000 0.000000
11 Instruction misprediction from scache way prediction table.. 90144 0.000000 0.000000 0.000460
12 External interventions...................................... 171152 0.000000 0.000000 0.000000
13 External invalidations...................................... 442448 0.000000 0.000000 0.000000
14 Virtual coherency conditions................................ 0 0.000000 0.000000 0.000000
15 Graduated instructions...................................... 46853825360 0.000000 0.000000 239.050129
17 Graduated instructions...................................... 46859809952 0.000000 0.000000 239.080663
20 Graduated store conditionals................................ 0 0.000000 0.000000 0.000000
27 Data misprediction from scache way prediction table......... 12815040 0.000000 0.000000 0.065383
28 External intervention hits in scache........................ 170992 0.000000 0.000000 0.000000
29 External invalidation hits in scache........................ 198576 0.000000 0.000000 0.000000
31 Store/prefetch exclusive to shared block in scache.......... 0 0.000000 0.000000 0.000000
Statistics
=========================================================================================
Graduated instructions/cycle................................................ 0.849117
Graduated floating point instructions/cycle................................. 0.346085
Graduated loads & stores/cycle.............................................. 0.237143
Graduated loads & stores/floating point instruction......................... 0.689641
Mispredicted branches/Decoded branches...................................... 0.002447
Graduated loads/Issued loads................................................ 0.992848
Graduated stores/Issued stores.............................................. 0.999105
Data mispredict/Data scache hits............................................ 0.005242
Instruction mispredict/Instruction scache hits.............................. 0.253533
L1 Cache Line Reuse......................................................... 3.732576
L2 Cache Line Reuse......................................................... 7.632774
L1 Data Cache Hit Rate...................................................... 0.788699
L2 Data Cache Hit Rate...................................................... 0.884162
Time accessing memory/Total time............................................ 1.128744
L1--L2 bandwidth used (MB/s, average per process)........................... 358.092824
Memory bandwidth used (MB/s, average per process)........................... 188.619910
MFLOPS (average per process)................................................ 67.832563
100x100x100 と 400x400x400 のケースの違いは、3Dグリッドのストアにリモートノードも
使わねばならないことです。この効果は R10K パフォーマンスカウンタでは直接は
測定できません。これはローカルとリモートのメモリ参照の操作が、ハブチップによって
制御されているからです。そのため、このケースで得られるほとんどの数は 100x100x100
のケースと比較できます。プロファイルではっきりと強調されている明瞭な違いがあります:
1次キャッシュミスです。3Dグリッドの列のサイズは今 4kバイトの大きさなので、
以前は [i,j] 列であった [i,j-1] 列をキャッシュで見つけるチャンスは減っています。
だから今は図6の白い箱も2次キャッシュから1次キャッシュにリロードされねばなりません。
この想定はL1キャッシュラインの再使用の値 3.7 でも見られます。3 は繰り返し毎に
各列が新たにアクセスされることを表します(40x40x40 のケースの再使用の説明を参照)。
よって次の繰り返しでの1つの列の再使用はドラスティックに減ります。
プリフェチを使った最適化
3つすべてのテストケースから、ロードとストアが実行時間のかなりの
部分を占めているこてが分かります。メモリリクエストの最善のインターリーブは
すべてのカーネルをスピードアップさせます。これが、実際の読み込みが起こる前に
キャッシュラインを1次キャッシュに(必要なら2次キャッシュに)ロードする、
プリフェチのマシンへの指示の役割です。
ステンシル・ カーネルが到達する最善の時間は、もしすべてのロードが完全に計算と
オーバーラップしているならば、Graduated Floating Point Operation でレポート
された時間になります。
プリフェチを使うと、この最善の時間に近づけることができます。カーネルは、
乗算と加算の理想的な混合ではなく大部分が加算なので、すべてのパイプラインを最善に
使った時の最小の計算時間ではなく、"典型的な"計画した時間を目標とします
(40x40x40 のケースでは 42秒、100x100x100 では 71秒、400x400x400 では 97秒です)。
コンパイラは R10000 へのプリフェチの命令を、自動的に、あるいはプログラムでの明示的な
制御により行います。プリフェチのオプションとプログラムは、 cc(1) リファレンスページ
に書いてあります。プリフェチについて次の3点を覚えておいて下さい :
- プリフェチはマシンの命令であり他と同様に実行するのに時間がかかります。
- プリフェチの指示はロード/ストア ユニットのパイプラインの16のポジションのうちの
1つを占有します。
- プリフェチがキャッシュにないデータを参照する時に、キャッシュのロードが
起こります。多くて4つのキャッシュロードを一度にペンディングできます;
プリフェチのロードはこれらのペンディングの指示と競合します。
これらの理由により、よく考えずにプリフェチを使うと実際の実行時間は遅くなります。
しかし、(図4にあるように)アルゴリズムの振舞いを理解することで、
(図6にもあるように)早くロードするべき大切なエレメントは次のものであることが
分かります :
- field_out[i][j][k] このエレメントは一度だけ使われるので、
潜在的にメモリからロードされなければなりません。
- field_in[i+1][j+1][k+1] 以前言ったように、この参照は前には使った
ことのないエレメントを使うので、これも潜在的にメモリからロードされます。
- field_in[i][j+1] と field_in[i-1][j+1] これらのエレメントは
前に使いましたが、1次キャッシュから追い出される可能性が高いので、2次キャッシュ
からリロードされなければなりません。
コンパイラには、必要なエレメントを予想するというように、アルゴリズムを
深く理解することはできません。静的なコンパイラの出力を見てみると、カーネルの
ループは14サイクルで実行していて、すでに10のメモリ参照があるので、プリフェチを
実行できる残りのサイクルは4サイクルだけです。コンパイラは空いている4つの
スロットでどのエレメントをプリフェチするかを選ぶことはできないので、
プリフェチは全く行いません。よって、プリフェチを可能にするには、
手で行う必要があります。
データがプリフェチされるべきかということに加えて、データの最初の使用に関連して、
どれだけの時間プリフェチが起こるかをあらかじめ知っておく必要があります。
そのため、メモリ参照と、データが Origin2000 の1次キャッシュに到達する間の
レイテンシを知ることが重要です :
- 2次キャッシュから : 45 - 60 ns すなわち 約 10 CPUサイクル
- ローカルメモリから : 315 ns すなわち 約 65 CPUサイクル
- リモートメモリから : 500 - 1200 ns すなわち 100 - 240 CPUサイクル
理想的には、データの参照が起こった時点で確実にそのデータが1次キャッシュに
あるためには、そのデータを使うよりもずっと前にプリフェチの命令が
発行されていなければなりません。しかし、参照がずっと前に
行われたときは、そのキャッシュラインを使う前にスラッシュされてしまう可能性が
あります。本質的には、プリフェチされたエレメントと使われたデータエレメントの
間のすべてのキャッシュラインは、1次キャッシュラインになければならず、これが
スラッシングを引き起こします。我々が使った単純なモデルでは、前にプリフェチした
エレメントの数によってキャッシュラインが引き伸ばされています。この単純な考えに
よって、
スラッシングのプログラム
を使ってプリフェチのシナリオをシミュレーションすることもできます。
プリフェチをやり過ぎると図4のピークを広げて新しいピークを作り出し、すべての
次元がスラッシングの可能性に脅かされるという点で、パディングがとても難しくなる、
と簡単なテストをすることで分かります。これは、プリフェチがむやみに促進される
べきものではないことを意味します。
以下でのおおまかな指針 :
- 2次キャッシュだけにあるエレメント :
マニュアルのプリフェチをデータエレメント [k+4] に行います。1次キャッシュライン
(32バイト)には4つのデータエレメントがあるので、プリフェチは、そのデータが
今のキャッシュラインからロードされている間に、次のキャッシュラインのロードを
行います。
- メモリにあると考えられるエレメント :
2次キャッシュラインのサイズは16個のエレメントの長さ(128バイト)なので、
同じラインに沿って、データエレメント [k+16] をプリフェチします。
新しい2次キャッシュラインが参照されると、それに続く次の2次キャッシュラインが
プリフェチによってリクエストされるという意味です。この新しいキャッシュラインは
1次キャッシュに到達します。
- ローカルノード: 4.5 繰り返し =
(65 CPUサイクル)/(理想では 繰り返しあたり 14 CPUサイクル)
- 近くのノード: 7 繰り返し =
(100 CPUサイクル)/(理想では 繰り返しあたり 14 CPUサイクル)
- 遠くのノード: 17 繰り返し =
(240 CPUサイクル)/(理想では 繰り返しあたり 14 CPUサイクル)
これはほとんどすべてのデータが、参照される前にCPUにあることを意味します。
1次キャッシュラインは4つの倍精度の値を保持することができ、
このコードはそれらの全部(ストライド1)を処理するので、キャッシュラインへの
プリフェチは、4サイクル毎にのみなされます。これを行うために、コンパイラは
普通カーネルループのコピー(カーネルの複製)を複数個作り、
PREF命令を一カ所にだけ挿入します。複製は普通、他の最適化(ループの
アンローリング)のために行われるのですが、この場合ではコンパイラは
3回ループの複製を作ります。
メモリと2次キャッシュからプリフェチを行うバージョン
(サブルーチン : Stencil_27Point_Isotrope_O3)のカーネルルーチンは、下にあるように、
4つのプラグマを加えただけのものです。
for ( k=1; k< size_x3-1 ;k++)
{
#pragma prefetch_ref=pin_ip_jp[k+16], stride=16, kind=rd
#pragma prefetch_ref=pin_i0_jp[k+4], stride=4, kind=rd
#pragma prefetch_ref=pin_im_jp[k+4], stride=4, kind=rd
#pragma prefetch_ref=pout_i_j[k+16], stride=16, kind=wr
out3 = weight3*( pin_im_jm[k-1]
+ pin_ip_jm[k-1]
+ pin_im_jp[k-1]
+ pin_ip_jp[k-1]
+ pin_im_jm[k+1]
+ pin_ip_jm[k+1]
+ pin_im_jp[k+1]
+ pin_ip_jp[k+1] );
out2 = weight2*( pin_i0_jm[k-1]
+ pin_im_j0[k-1]
+ pin_ip_j0[k-1]
+ pin_i0_jp[k-1]
+ pin_im_jm[k ]
+ pin_ip_jm[k ]
+ pin_im_jp[k ]
+ pin_ip_jp[k ]
+ pin_i0_jm[k+1]
+ pin_im_j0[k+1]
+ pin_ip_j0[k+1]
+ pin_i0_jp[k+1] );
out1 = weight1*( pin_i0_j0[k-1]
+ pin_i0_j0[k+1]
+ pin_i0_jp[k ]
+ pin_ip_j0[k ]
+ pin_im_j0[k ]
+ pin_i0_jm[k ] );
out0 = weight0* pin_i0_j0[k ];
pout_i_j[k] = out0+out1+out2+out3;
}
このバージョンを実行すると :
stencil 1000 40 3
repeating stencil: 1000
grid-size: 40 x 40 x 40 = 64000
optimization version: 3
size of the 3D-grid: 0.512000 MByte
40 0.512000 MByte 5.17 sec per grid-point: 94.219 ns 18.4 cycles
stencil 1000 100 3
repeating stencil: 1000
grid-size: 100 x 100 x 100 = 1000000
optimization version: 3
size of the 3D-grid: 8.000000 MByte
100 8.000000 MByte 94.94 sec per grid-point: 100.872 ns 19.7 cycles
図7 : プリフェチをしたカーネルの性能をプロットしたもの(実線)と図4のプリフェチなし
のバージョンとの比較。
明示的な測定と図7の両方から分かるように、プリフェチにより性能がかなり向上しています。
256x256x256 までは性能が グリッドポイントあたり 20 CPUサイクルです。簡単な
パッディングプロシージャでは防げなかったキャッシュのスラッシングによるピークが
まだダイアグラムに見られます。とても大きなグリッドサイズでは、個々の列の大きさの
増加によって1次キャッシュに入りきれずに再使用できないことからくると思われる、
性能の低下が見られます。これは次の2つの方法で克服できます :
- PREFETCH の指示をもっと使う。
- ブロッキング。
ブロッキングは好ましい解決法なので、これを用いたさらなる最適化の余地があります。
残念なことに、アンロール ディレクティブはこの C コードでは役に立たないので、
アンロール を手で行わねばなりません。
ステンシル カーネルの Fortran バージョン
比較のために、
ステンシル コードの Fortran バージョン
を作って、それをマニュアルでのプリフェチの指示の挿入ありとなしの
2つのケースで実行しました。
C プログラムで行った、多次元配列の1次元のベクトルへの変換は、必要ありません。
これは、Fortran では配列が、ポインタを通してではなく直接アドレスされるからです。
コンパイラは洗練されていないバージョンでの、最善のスケジュールを見つけました。
プリフェチの分析と挿入は、C バージョンと同様です。
このコードをコンパイルするのに、以下のコマンドを使いました :
f77 -64 -mips4 -O3 -OPT:alias=disjoint:roundoff=3:IEEE_arithmetic=3 -CLIST:=ON
-FLIST:=ON -DFORTRAN -DPADDING stencil.c fstencil.f -o stencil
オプションについては f77(1) リファレンス ページに詳しく書いてあります。
簡潔に書くと :
| -n32 |
64ビット レジスタセットと効率のよいコーリング規約を使う。 |
| -mips4 |
R10000 インストラクション フルセット のコンパイル。 |
| -O3 |
多くのコンパイラ最適化を可能にする。 |
| -OPT:alias=disjoint
| どの引数も互いにエイリアスされていないことをコンパイラに保証する。
|
| -OPT:roundoff=3 |
数学的に有効なあらゆるコード変換を丸め誤差を気にせず許可する |
| -OPT:IEEE_arithmetic=3 |
IEEE 精度に違反するかもしれない数学的に有効な変換を許可する。
例 : x/y --> x*recip(y) |
| -CLIST:=ON |
最適化されたプログラムのCソースを参照のために生成する。 |
| -FLIST:=ON |
最適化されたプログラムの Fortran ソースを参照のために生成する。 |
| -DFORTRAN |
C のmain() に Fortran のサブルーチンをコールするように指定する。 |
カーネルの Fortran バージョンは、(stensil.c をベースとする)メインプログラムの
4番目の引数に -1,-2, あるいは -3 を渡すことによってテストできます。
コンパイラによって最適化された基本的なカーネル
f77 コンパイラによって最適化された基本的なカーネル
(プロシージャ fstencil_org)は、-1で呼び出されます。
[crush]chem 241% stencil 1000 40 -1
stencil 1000 40 -1
repeating stencil: 1000
grid-size: 40 x 40 x 40 = 64000
optimization version: -1
size of the 3D-grid: 0.512000 MByte
40 0.512000 MByte 4.89 sec per grid-point: 89.116 ns 17.4 cycles
[crush]chem 240% stencil 1000 100 -1
stencil 1000 100 -1
repeating stencil: 1000
grid-size: 100 x 100 x 100 = 1000000
optimization version: -1
size of the 3D-grid: 8.000000 MByte
100 8.000000 MByte 107.58 sec per grid-point: 114.302 ns 22.3 cycles
最小のプリフェチ
プリフェチのディレクティブ(プロシージャ fstencil_o2)は、-2 で呼び出されます。
[crush]chem 238% stencil 1000 40 -2
stencil 1000 40 -2
repeating stencil: 1000
grid-size: 40 x 40 x 40 = 64000
optimization version: -2
size of the 3D-grid: 0.512000 MByte
40 0.512000 MByte 4.81 sec per grid-point: 87.659 ns 17.1 cycles
[crush]chem 239% stencil 1000 100 -2
stencil 1000 100 -2
repeating stencil: 1000
grid-size: 100 x 100 x 100 = 1000000
optimization version: -2
size of the 3D-grid: 8.000000 MByte
100 8.000000 MByte 91.35 sec per grid-point: 97.058 ns 18.9 cycles
測定結果を見てみると、Fortran のバージョンの方がわずかに性能がいいです。
これは、C では個々のステンシルにポイントするポインタの問題を扱わなければならない
のに対して、Fortran ではその必要がないことによるものです。
結論
Origin2000 と IRIX で提供されるプロファイリング ツールとコンパイラ オプションを
使うと、アルゴリズムの振舞いを正確に分析し、CPU ハードウェアを
最大限に使えるよう、生成されたコードをチューニングすることが可能となります。