最近、ブログ「 OpenMP 3.0タスクモデル：Cilkと同じくらいスムーズですか？」 」 その後、再帰関数がOpenMP 3.0タスクとどの程度並列化するかを確認することにしました。 3番目の標準の前は、動的または不規則な並列処理（たとえば、while関数または再帰関数を含むループ）がサポートされていなかったことを思い出してください。
計算システム
まず、使用したコンピューティングシステムの説明から始めます。
以下は、結果をカバーできるコンピューターのリストです。 残りはまだ生産に入っていません。
並列化プロセス
テストのために、 フィボナッチ数を計算する例を取り上げました。 並列化のアイデアは次のとおりです。再帰の各ステップで非同期タスクを作成し、関数を終了する前に同期を整理します。 残念ながら、このアプローチでは、1を超える加速は得られませんでした。ランタイムコストが支配的だったためです。 ここで解決策が見つかり、簡単であることが判明しました。再帰ステップの一部のタスクのみを作成し、残りを順番に実行します。 つまり、ランタイムコストとランタイムのバランスを取ります。 以下は、バランスをとるコードの一部です。
INT_TYPE
fib( INT_TYPE n ) {
INT_TYPE i, j;
if( n < SPLITTER ) {
return fib_serial( n );
} else {
#pragma omp task shared( i )
i = fib( n - 1 );
#pragma omp task shared( j )
j = fib( n - 2 );
#pragma omp taskwait
return i + j;
}
}
この例では、SPLITTERがバランスを取る役割を果たします。 すべてのソースコードはこちらからダウンロードできます 。
しかし、それほど単純ではありません。 異なるSPLITTER値の場合、並列化効率は異なります。 空を指で突くことで、並列化効率が1に近づくスプリッター19と32の2つの値を取得しました。
編集
すべてのソフトウェアのうち、コンパイラのみが対象となります。 3つのコンパイラーを自由に使用できました。Intel®Composer XE for Linux、Microsoft Visual C ++ 2010、およびGCC。 Visual C ++は、OpenMP 3.0をサポートしていないため（現時点ではOpenMP2.5のみがサポートされているため）、すぐに削除されます。 GCCはバージョン4.4以降のOpenMP 3.0をサポートしています。私は4.5.0を使用しました。
以下は、動的ライブラリと静的ライブラリの両方を含む実行可能ファイルのコンパイル時間とサイズです。 ただし、GCCとは異なり、Intel®Composer XEがリモートマシンにインストールされていることに注意してください。 これはコンパイル時間の増加につながります。
GCCおよびIntel®Composer XEの文字列は次のとおりです。
＃gcc ./fib_task.c -fopenmp
＃gcc ./fib_task.c -fopenmp -static
＃icc ./fib_task.c -openmp -static
＃icc ./fib_task.c -openmp
ランタイムとスケーラビリティ
すべての測定は、SPLITTER = 19およびSPLITTER = 32の50番目のフィボナッチ数を検索するために実行されました。
加速と並列化の効率
このグラフは、SPLITTER = 32の場合の加速を示しています。 効率は、スレッド数と加速の比率です。
ソースおよび実行可能ファイル
上記のように、ソースファイルはここからダウンロードできます 。 この例では、41番目のフィボナッチ数が計算されます。 測定値を再生するには、変数n = 50および期待される変数= 12586269025ULを変更する必要があります。 すぐにダウンロードすることもできます
- SPLITTER = 19およびSPLITTER = 32用にIntel®Composer XEで生成された実行可能ファイル。
- SPLITTER = 19およびSPLITTER = 32に対してGCC 4.5.0で生成された実行可能ファイル。
結論
実際、ランタイムとアクセラレーションを備えたチャートは、すべてを物語っています。
- Composer XEの場合、スレッドの数が物理コアの数を超えない限り、並列化効率は〜1です。
- GCC 4.5.0の場合、スレッドの数が物理コアの数を超えない限り、並列化の効率は約0.5です。
残りの結論は、それぞれが彼自身のことに興味があるので、あなた自身を作ることをお勧めします。
あとがき
PringerLinkの記事「 OpenMP Tasking Controlを改善するための拡張機能 」で、バランサーとして機能する新しい最終節の導入を提案した記事を見つけました。 私の意見では、これは地味な提案です。 また、句バランサーを追加することもできます。これにより、リアルタイムで適応バランスが取れます。
Intelソフトウェア製品のパフォーマンスと最適化の詳細については、最適化通知ページを参照してください。