Ning Li
HECToR CSE team, Numerical Algorithms Group Ltd.
背景
HYPO4Dは、乱流研究用途の流体方程式を格子ボルツマン法を用いて解く、UCLで開発された計算コードです。
C言語で記述されたこのコードは、HECToRのXT4で広範に利用されており、4096コアまで極めて良好に(線形に)スケールすることが報告されています。開発者らは、このコードをX2ベクトルマシンへ移植して、より大きなシェアードメモリーを活用する初期の作業に参加していました。彼らは、コードの初期段階でセグメンテーション・フォールトする理由が全く不明な状態でCSEチームに依頼をしました。このバグは、コード移植時に彼らが意図せずソースの一部を削除してしまったことによる、未定義参照が原因でした。この後X2上の性能向上に注力することになりました。
利用したツール
このコードの特性を調べるために使用したのは以下のツールです：
- Crayコンパイラーのレポート機能 ： Cray Cコンパイラー'cc'のloopmarkリスト機能はコンパイル時に、コード最適化に関する情報を付加したソースコードを生成します。これはコンパイラーにフラグ'-h list=a'を渡せば可能です。Crayフォートランコンパイラーの'-R a'が同じ機能を持ちます。
- Cray 'explain'機能 : X2開発環境では、'explain CC-????'とタイプすると、エラー/警告/インフォメーションメッセージに関して詳細情報を見ることが出来ます。ここで????はコンパイラーによるメッセージIDです。
- 最も時間の掛かるルーチンを調べるために、最初にCray Performance Analysis Toolを用います。これには'サンプリング'実行のみで可能です。より大規模な場合は、キャッシュ効率やベクトルレジスター効率などの性能指標を知らねるために、詳細な’トレース’実行が必要です。
ベースケース
標準的な最適化レベル'-O3'でコンパイルしたオリジナルコードを比較のためのベースケースとします。256*128*128メッシュを用いて全てのテストに8コアで実行しました。これは十分な負荷を持つものであり、内部テストシステムTDS上で数分で終わるのに適切なサイズとなっています。ここで報告する時間情報はコードが持つ内部時間計測ルーチンを使用したものです。これらの値は偏差はほぼ無いことが解っています。
ベースケース実行は448秒で終了しました。開発者によれば、これは同構成のXT4での時間のほぼ倍です。改善すべきことが多くあるのは明らかです。格子ボルツマンコードで広く用いられる2番目の性能測定指標は、サイト更新率(SUPS：site-updates-per-second)と呼ばれる値です。ベースケースのSUPS値は1.87E+06でした。
Crayが推奨するオプション'-O3 -h fp3 -h cache2'を用いても性能に変化は見られませんでした。
ポインターはベクトル化を阻害する：
まず最初に、最も時間の掛かる2つのルーチン(ユーザーのXT4上の実験から得られた)を検証したところ、大きな問題を見つけました。このコードは大きなデータ配列を操作するのにCポインターを用いていました。これは洗練されたプログラミング技法(あるいは見方によれば全くエレガントでない)ですが、使い方を間違えればベクトル化コンパイルにとって大きな問題を生じます。コンパイラーは以下のようなメッセージを繰り返しレポートしています(詳細な情報を得るには'explain CC-6290'とタイプしてください)：
CC-6290 CC: VECTOR File = hypo4d_advection.c, Line = 31 A loop was not vectorized because a recurrence was found between "lattice" and "lattice2" at line 35.
ここで’lattice’と’lattice2’はループ中に現れる2次元配列です。これらに対してポインターで参照すると、コンパイラーはそれらのメモリーが重なるのかどうかが解らず、それらを含むループのベクトル化をあきらめます。以下のような簡単なコードで上記問題は明らかにされます：
void pntr(int *a, int *b) {
int i;
for (i=0;i<64;i++)
b[i] = i * a[i];
}
もしこの関数をpntr(&caller[0], &caller[10])を用いて呼び出した場合、このループを並列に動作させると結果は正しくなりません。Crayコンパイラーはこうすることを危険と見做し、問題回避のためにスカラーコードを生成します。実際にはメモリースペースをオーバーラップしてコードが作成されることは多くなく、2つのポインターは別の領域をアクセスし、またこのコードはそうした事例になっていました。依存性がないことをコンパイラーへ指示するためには、C99標準で定義された'restrict'キーワードを用います。例えば上の例では、関数定義をvoid pntr(int * restrict a, int * restrict b)とします。コード上の変更を避けるためには、全てのポインターがベクトル化しても安全であることをCコンパイラーへ指示するために、フラグ'-h restrict=a'を渡します。
このコンパイラーフラグを使うことにより、実行時間は390秒まで削減され、SUPS値は2.15E+06となり、115%高速化されました。
ここで次の段階へ進むために、現在の高コストルーチンを特定するため以下のCrayPatレポートを採取しました：
Samp % | Samp | Imb. | Imb. |Experiment=1
| | Samp | Samp % |Group
| | | | Function
| | | | PE='HIDE'
100.0% | 36558 | -- | -- |Total
|-----------------------------------------------
| 93.8% | 34297 | -- | -- |USER
||----------------------------------------------
|| 47.0% | 17181 | 669.00 | 4.3% |lbe_step
|| 35.5% | 12993 | 2829.88 | 20.4% |uniform_ABC_force
|| 6.5% | 2379 | 97.62 | 4.5% |advection
|| 2.5% | 897 | 1180.25 | 64.9% |ForceABC
|| 1.4% | 498 | 548.75 | 59.9% |LBForceTerm
||==============================================
| 5.9% | 2151 | -- | -- |ETC
||----------------------------------------------
|| 5.4% | 1973 | 888.25 | 35.5% |__cis
|===============================================
明らかに、関数lbe_stepおよびuniform_ABC_forceについてさらに注目していくべきでしょう。
I/O文はベクトル化を阻害する：
ルーチンlbe_stepは4重ループの浮動小数点演算を含むため、非常に大きなコストが掛かっています。これはループ内で、数値アルゴリズムの安定性を判定するというあまり望ましくない仕組みを持っています。開発者によれば、一度コードをセットアップすれば、不安定条件はめったに生じないとのことでした。この条件文を外すと、その計算部分が不要になり(つまりコンパイラーが生成するコードから取り除かれます)、コード性能は大きく向上しました：その性能は252秒で、SUPS=3.32E+06となり、ベースケースから128%高速化しました。
開発者へは安定性判定の方法の変更をアドバイスしました(可能な限り外側ループで条件文を少なくするように)。実用上その条件文によるチェックがめったに必要でないならば、プリプロセッサー指示を用いる事をアドバイスしました。そうすれば条件文のコードはコンパイル時にフィルタリングが出来て、実行時間を有効に使えます。
同様に、最内側ループ中のI/OがX2のループベクトル化を阻害していました。この時には、以下のコンパイラーメッセージが表示されます：
CC-6287 CC: VECTOR File = hypo4d_fequilibrium.c, Line = 39 A loop was not vectorized because it contains a call to function "printf" on line 114.
このI/O文は、ベクトル化を阻害する最内側ループから外しても、その他にも性能に悪影響を与える可能性があります。例えば：
CC-6205 CC: VECTOR File = hypo4d_advection.c, Line = 518 A loop was vectorized with a single vector iteration. CC-6004 CC: SCALAR File = hypo4d_advection.c, Line = 529 A loop was fused with the loop starting at line 518.
ここで最初の518行目のループはベクトル化されています。2番目の529行目のループは同じループ長を持つためループ融合されています(2つのループ内容が1つのループ内に纏められています)。ループ内の内容が大きいほど、コンパイラーによる最適化へさらなる改善の機会を与えます。不要なI/Oがこれら2つのループ間に存在すると、このような追加の最適化が困難になります。
次のCrayPatレポートから解るように、上述の最適化によりlbe_stepルーチンは高コストな関数ではなくなっています。
Samp % | Samp | Imb. | Imb. |Experiment=1
| | Samp | Samp % |Group
| | | | Function
| | | | PE='HIDE'
100.0% | 23879 | -- | -- |Total
|-----------------------------------------------
| 83.1% | 19838 | -- | -- |USER
||----------------------------------------------
|| 42.8% | 10212 | 6849.75 | 45.9% |uniform_ABC_force
|| 19.3% | 4602 | 621.62 | 13.6% |lbe_step
|| 10.2% | 2432 | 342.12 | 14.1% |advection
|| 4.7% | 1121 | 715.88 | 44.5% |ForceABC
|| 4.6% | 1101 | 779.62 | 47.4% |LBForceTerm
|| 1.3% | 303 | 49.38 | 16.0% |halo_exchange
||==============================================
| 16.6% | 3971 | -- | -- |ETC
||----------------------------------------------
|| 16.0% | 3825 | 4636.00 | 62.6% |__cis
|===============================================
同じような不要な条件文が、特に高コストな関数uniform_ABC_force等の他のコード部分にもあり、同様な修正が開発者にアドバイスされました。
インライン展開とベクトル化：
関数uniform_ABC_forceにはネストしたループ中に、ForceABCといった小さな関数の呼出しが多くありました。ネストしたループをベクトル化するためには、これらの関数呼出しをインライン展開すべきです。Crayコンパイラーのデフォルト仕様は関数のインライン展開に少し不便です。このような小さな関数は、コンパイラーに拾い上げてもらうためには、呼出される関数として呼び出すコードと同じソースファイル内に定義されていなくてはなりません。あるいはC言語コードの場合はフラグ'-h ipafrom='を用いて(Fortranでは'-O ipafrom=')、インライン展開されるべき関数のファイルを明白に指定するようにします。3番目のやり方として、インライン展開の動作を調整するためのコンパイラー指示行を使う方法がありますが、これは直截的なやり方とは言えないでしょう。
最初に行ったフラグ'-h restrict=a'による最適化は、実はインライン展開には悪影響を持ちます。コンパイラーは下記のようなメッセージを出しています：
CC-3148 CC: INLINE File = hypo4d_advection.c, Line = 496 Routine ForceABC was not inlined because a formal parameter is a restricted pointer and its corresponding actual argument is not a restricted pointer.
この問題に対処するには、このファイルのみにはフラグ'-h restrict=a'を適用しないような新しいビルド・スクリプトを作成します。その結果、コンパイラーは以下のメッセージを示しました：
CC-3001 CC: INLINE File = hypo4d_advection.c, Line = 496 The call to ForceABC was textually inlined.
このソースファイルhypo4d_advection.cへの変更は、まず最初に305秒まで性能劣化を生じます。そこでループのベクトル化が安全であることをコンパイラーへ命令するために、対象となるポインターへ直接キーワードrestrictを追加すれば、実行時間は231秒まで削減されます。さらにいくつかのI/O文をコメントアウトすると163秒まで削減され、SUPS＝5.14E+06となり、ベースケースに対して275%高速化しました。
最内側ループのアンローリング：
高コストコード部の多くは4重ループを含んでいます。外側の3つのループは空間インデックスであり、通常非常に大きな値(テストケースでは128と256)です；また、最内側ループは比較的小さな値を持つ格子ベクトルであり、このアプリケーションではコンパイル時に固定(=19)されています。デフォルトでは、コンパイラーがループ入替を可能でない限り、最内側ループがベクトル化対象となります。X2のハードウェアではベクトルレジスターは一度に128ワードまで格納することが出来るため、最内側ループを完全にアンローリングすれば、この大きなネストされたループがベクトル化されると期待できます。本ケースではこれはとても有用です。例えばhypo4d_fequilibrium.cのソースには複数の似たループが存在します。デフォルトではコンパイラーは最内側ループをベクトル化します：
CC-6315 CC: VECTOR File = hypo4d_fequilibrium.c, Line = 35 A loop was not vectorized because the target array (f_eq) would require rank expansion. CC-6315 CC: VECTOR File = hypo4d_fequilibrium.c, Line = 37 A loop was not vectorized because the target array (f_eq) would require rank expansion. CC-6315 CC: VECTOR File = hypo4d_fequilibrium.c, Line = 39 A loop was not vectorized because the target array (f_eq) would require rank expansion. CC-6205 CC: VECTOR File = hypo4d_fequilibrium.c, Line = 42 A loop was vectorized with a single vector iteration.
ここで42行目の最内側ループがベクトル化されていますが、これではハードウェアのベクトル長を全て活用していません。ソースコードの最内側ループの直前に指示行'#pragma _CRI unroll 19'を挿入すると、コンパイラーはそれを完全にアンローリングしました(コンパイラではunwoundとも言います)。つまりここでは、19個のループ内容が繰り返しコピーされて、ループそのものは削除されます。loopmarkリストにより下記のようなメッセージを得ます：
CC-6294 CC: VECTOR File = hypo4d_fequilibrium.c, Line = 35 A loop was not vectorized because a better candidate was found at line 39. CC-6294 CC: VECTOR File = hypo4d_fequilibrium.c, Line = 37 A loop was not vectorized because a better candidate was found at line 39. CC-6204 CC: VECTOR File = hypo4d_fequilibrium.c, Line = 39 A loop was vectorized. CC-6008 CC: SCALAR File = hypo4d_fequilibrium.c, Line = 44 A loop was unwound.
39行目の大きなループがベクトル化されたことが解ります。これによりより効率的なコードが生成されて、ハードウェア性能をさらに多く引き出すことが可能になり、コード性能は大きく改善します。同様な変更をコード全体に渡り、他の重要な関数(uniform_ABC_force,advection,LBForceTerm)へ適用したところ、実行時間は99秒まで減少(SUPS=8.49E+06)しました。最終的にベースケースより454%高速化しました。
再びCrayPatでコード性能を検証すると(今回はトレース情報を採取)、2つの大きな改善を見ることが出来ます。よりループ長の長い外側ループのベクトル化により、平均ベクトル長は8.91から64へ増加してハードウェア使用効率の改善が示されました。これに付随して、データキャッシュ効率も83%から100%へ大きく改善しました。
======================================================================== USER / lbe_step ------------------------------------------------------------------------ PAPI_VEC_INS 127.314M/sec 7969178998 instr ...... Utilization rate 100.0% Instr per cycle 0.36 inst/cycle HW FP Ops / Cycles 1.07 ops/cycle HW FP Ops / User time 857.580M/sec 41313895012 ops 3.3%peak HW FP Ops / WCT 857.580M/sec HW FP Ops / Inst 297.8% Avg VL 8.91 ops Data cache refs 0.001M/sec 54998 refs D cache hit ratio 83.3% MIPS 2303.97M/sec MFLOPS 6860.64M/sec Instructions per LD ST 252268.21 inst/ref LD & ST per D1 miss 6.00 refs/miss ======================================================================== USER / lbe_step ------------------------------------------------------------------------ PAPI_VEC_INS 127.314M/sec 819199998 instr ...... Utilization rate 100.0% Instr per cycle 0.20 inst/cycle HW FP Ops / Cycles 9.05 ops/cycle HW FP Ops / User time 7242.970M/sec 46604654208 ops 28.3%peak HW FP Ops / WCT 7242.970M/sec HW FP Ops / Inst 4425.6% Avg VL 64.00 ops Data cache refs 12.548M/sec 80738192 refs D cache hit ratio 100.0% MIPS 1309.29M/sec MFLOPS 57943.76M/sec Instructions per LD ST 13.04 inst/ref LD & ST per D1 miss 5877.37 refs/miss
最内側ループをアンローリングする前は、コンパイラーはベクトル演算とスカラー演算を共に生成しており、CrayPatによる平均ベクトル長は8.91という、loop countの19よりかなり少ない値でした。アンローリング後は全てのループはベクトル化され、平均ベクトル長がloop countと同じ64になっています。ベクトル命令の総数もまた90%近く、およそ8000Mから800Mへ削減されました。
ベクトルレジスターは128ワードまで格納できることから、上記のアイデアをさらに拡張して、最内側ループを最大のループ長を持つループへ順序を入れ替えることも考えられます。テストケースの問題サイズが256*128*128(各コアに対しては128*64*64)であることを思い出せば、最内側ループは最大のループ長でないことが解ります。別のケースでの異なるテストにおいて、128*128*256のメッシュを実行した結果(物理的に異なる問題ですが計算コストは同等のケースです)、全計算時間は93秒へ減少しました(SUPS=9.03E+06および483%の高速化)。領域分割ルーチンのデフォルトでは、nx>=ny>=nzが仮定されていました。これは任意に設定可能なので、nzを最も大きな数に設定するべきです。この領域分割ルーチンに少し修正を加えれば、ベクトルマシン上でのこのコード特性に利得をもたらすと考えられます。
結果のまとめ
HECToRのX2ベクトルマシン上でのHYPO4Dコードの性能は、以下のチューニングにより改善されました：
- データ依存性に対するコンパイラーへの指示
- ループ内の不要なチェック文およびI/Oの除去
- インライン展開対象関数のコンパイラーへの明確な指示
- より大きな外側ループのベクトル化のための手動内側ループ・アンローリング
結果として483%の性能向上が達成されました。loopmarkリストメッセージからは、コード性能のさらなる改善が見込まれています。一例としては、ソースコードを再構成すればおそらく可能な、より複雑なデータ依存性問題が挙げられます。