Keiichi Oono's Weblog

2008年 3月 28日 金曜日

コンパイラによる自動並列化の捕捉。縮約 (reduction) を自動で行わせる

前回の自動並列化の説明で、理解不足の点がありました。「姫野ベンチ」で自動並列化を試みた際に gosa という変数の演算部分が並列化できなかったため効果が現れませんでした。という説明をしましたが gosa という変数の演算のj自動並列化を可能にするオプションがありました。このエントリでは、前回はどうして並列化できなかったのか、という点と並列化を可能にするオプションについて説明します。

姫野ベンチのソースコードはダウンロードして展開すれば読むことができますが、直接読める形で公開されていません。コードの一部を紹介することに問題はないのかもしれませんが、このエントリでは姫野ベンチのソースコードは直接使わずに、同等のコードに置き換えて説明します。

どうして並列化できなかったのか

前回のエントリでは「変数がループ内に完全に閉じていないため」と簡単に説明しただけですが、具体的には以下のような状況です

for (i=1; i < 1000; i++) {
    sum += a[i]*b[i]; /* S1 */
}

変数 sum は、1 つ前のループ実行時の sum に配列の値から求めた積を加算しているため、単純な方法で並列化することはできません。例えば 2 のスレッドで実行したとしても、最後にはそれぞれのスレッドで求めた sum を一つの値に合算しないと、求める値を得ることはできません。

縮約 (reduction)

この、スレッド毎に一時的な変数で部分和を求めておいて最終的な結果は合算して求める。という処理を行うために、OpenMP では縮約 (reduction) と呼ばれる指定を変数に対して行うことができるようになっています。指定された変数のことを縮約変数と呼びます。ただし丸め誤差の影響から、縮約して複数スレッドで実行した演算結果は、単一スレッドでの演算結果と個なる場合があります。

OpenMP で、ある変数を縮約変数として扱うか否かは明示的に指定する必要があります。

/* OpenMP: for ループで sum を縮約変数として指定 */
#pragma omp parallel for reduction (+:sum)

変数を縮約変数として自動並列化する -xreduction オプション

コンパイラによる自動並列化を行う際にも、コンパイラに縮約を行うように指示をすることができます。縮約可能であると判断された場合には変数は縮約変数として扱われ、並列化されます。OpenMP による並列化を行う場合と同じく、明示的に指示しない限り縮約のための解析と縮約変数の指定は行われません。縮約を行うように指示する場合には -xreduction オプションを追加します。指定されるとコンパイラは、解析の結果可能であれば変数を縮約変数として扱います。

姫野ベンチのソースで試してみる

コンパイル時に gosa の演算が縮約され、198 行目のループが並列化されたことを示すメッセージが出力されました:

cc -c  -fast -m64 -DMIDDLE -xvector=simd -xdepend -xautopar -xreduction -xloopinfo himenoBMTxps.c
"himenoBMTxps.c", 152 行目: 並列化されます
"himenoBMTxps.c", 153 行目: 並列化されません、利得なし
"himenoBMTxps.c", 154 行目: 並列化されません、利得なし
"himenoBMTxps.c", 170 行目: 並列化されます、逐次版が生成されました
"himenoBMTxps.c", 171 行目: 並列化されません、利得なし
"himenoBMTxps.c", 172 行目: 並列化されません、利得なし
"himenoBMTxps.c", 195 行目: 並列化されません、安全でない依存性 (wrk2 p)
"himenoBMTxps.c", 198 行目: 並列化されます、縮約、逐次版が生成されました
"himenoBMTxps.c", 199 行目: 並列化されません、利得なし
"himenoBMTxps.c", 200 行目: 並列化されません、利得なし
"himenoBMTxps.c", 223 行目: 並列化されます、逐次版が生成されました
"himenoBMTxps.c", 224 行目: 並列化されません、利得なし
"himenoBMTxps.c", 225 行目: 並列化されません、利得なし
cc -o bmt himenoBMTxps.o  -fast -m64 -DMIDDLE -xvector=simd -xdepend -xautopar -xreduction -xloopinfo

実行結果は以下のようになりました。前回と同じく自動並列化した実行ファイルは OMP_NUM_TREADS=2 という環境変数を指定した上で実行しています:

CPU	2 次キャッシュ	メモリ
AMD Opteron 250 (2.4GHz) x2	1 MB	3326 MB

結果 (5 回計測した中央値)

コンパイルオプション	結果 (MFLOPS)
-DMIDDLE -fast -m64 -xvector=simd -xdepend	812.315620
-DMIDDLE -fast -m64 -xvector=simd -xdepend -xautopar -xreduction -xloopinfo	1069.074965

自動並列化を行う場合に、「安全でない依存性」と報告された変数が縮約によって並列化される可能性がある場合には -xautopar に加えて -xreduction を指定することで、-xautopar だけでは並列化できなかった部分も並列化することができるようになります。

 
Posted by keiichio ( 3月 28日 2008年, 02:22:46 午後 JST ) Permalink 投稿されたコメント [0]