Sun C コンパイラは、メモリー共有型マルチプロセッサ、マルチコア、またはマルチスレッドのシステム上で実行するコードを最適化できます。 コンパイルされたコードは、システムの複数のプロセッサを使用して並列して実行できます。自動的な並列化と明示的な並列化という両方の手法が使用可能です。この章では、このコンパイラの並列化機能を利用する方法について説明します。
C コンパイラは、並列化しても安全であると判断したループに対して並列コードを生成します。通常、これらのループは、独立して実行可能な繰り返しを持っています。繰り返しが実行される順番や、並列に実行するかどうかといったことなどは、ループの実行結果に影響はありません。すべてではありませんが、ほとんどのベクトル処理用ループはこのような種類のループです。
C では別名が存在する (複数の変数が同一の実体である / を指す) 可能性があるため、並列化の安全性を判断することは困難です。コンパイラの作業を容易にするために、Sun C には別名の情報をコンパイラに渡すためのプラグマおよびポインタ修飾子が用意されています。詳細については、第 5 章型に基づく別名解析を参照してください。
次の例は、C を並列化し、制御する方法を示しています。
% cc -fast -xO4 -xautopar example.c -o example |
この例では、通常の方法で実行できる example という実行可能ファイルが生成されます。マルチプロセッサ上で実行する場合は、「B.2.75 -xautopar」 を参照してください。
OpenMP の仕様に準拠するようにコードをコンパイルできます。OpenMP API の仕様の詳細は、http://www.openmp.org/ の OpenMP Web サイトを参照してください。
コンパイラ の OpenMP サポートを利用するには、コンパイラの -xopenmp オプションを発行する必要があります。「B.2.124 -xopenmp[= i]」を参照してください。
標準命令への移植については、『OpenMP API ユーザーズガイド』を参照してください。
OpenMP 実行時システムは、軽度のエラーに対し警告を発行できます。次の関数を使用すると、それらの警告を処理するコールバック関数を登録できます。
int sunw_mp_register_warn(void (*func) (void *) )
この関数のプロトタイプにアクセスするには、<sunw_mp_misc.h> に対する #include プリプロセッサ指令を発行します。
関数を登録したくない場合、環境変数 SUNW_MP_WARNを TRUE に設定すると、警告メッセージが stderr に送られます。SUNW_MP_WARN の詳細については、「SUNW_MP_WARN」 を参照してください。
この実装の OpenMP に固有の情報については、『OpenMP API ユーザーズガイド』を参照してください。
並列化された C には、関連する環境変数として次の 4 つが存在します。
PARALLEL または OMP_NUM_THREADS
SUNW_MP_THR_IDLE
SUNW_MP_WARN
STACKSIZE
マルチプロセッサ上で実行する場合は、PARALLEL 環境変数を設定してください。PARALLEL 環境変数には、プログラムの実行に使用できるプロセッサの数を指定します。次は、PARALLEL を 2 に設定する例を示しています。
% setenv PARALLEL 2 |
対象マシンに複数のプロセッサが搭載されている場合は、スレッドは個々のプロセッサにマップできます。この例では、プログラムを実行すると、2 個のスレッドが生成され、各スレッド上でプログラムの並列化された部分が実行されるようになります。
PARALLEL と OMP_NUM_THREADS のどちらかを使用できます。これらは同等です。
現在のところ、プログラムの初期実行を行うスレッドが結合スレッドを作成します。作成されたこれらの結合スレッドは、プログラムの並列部分 (並列ループ、並列領域など) の実行に加わり、プログラムの順次実行部分が実行される間スピン待ち状態を維持します。これらの結合スレッドは、プログラムが終了するまで休眠または停止することはありません。並列化されたプログラムを 1 つのシステム上で実行する場合は、結合スレッドをスピン待ちにすると最高のパフォーマンスが得られます。ただし、スピン待ちのスレッドはシステム資源を使用します。
SUNW_MP_THR_IDLE 環境変数は、各スレッドが並列ジョブの分担部分を終えたあとの各スレッドの状態を制御するために使用してください。
% setenv SUNW_MP_THR_IDLE value |
valueには、spin または sleep[n s|n ms] のどちらかを指定できます。デフォルトは sleep であり、スレッドを n 単位のスピン待ちにしたあと、休眠させます。待ち時間の単位は秒 (s、デフォルトの単位) かミリ秒 (ms) で、1s は 1 秒、10ms は 10 ミリ秒を意味します。引数を取らずに sleep を指定すると、スレッドは並列化タスクの完了直後にスリープ状態に入ります。sleep、sleep0、sleep0s、および sleep0ms はすべて同等です。n 単位が到着する前に新しいジョブが到着すると、スレッドはスピンを停止し、新しいジョブを開始します。
もう 1 つの選択肢は spin です。並列化タスクの完了したスレッドは、新しい並列化タスクが到着するまでスピン (busy-wait) します。
SUNW_MP_THR_IDLE に不正な値が含まれているか、設定されていない場合は、デフォルトとして sleep が使用されます。
この環境変数を TRUE に設定すると、OpenMP そのほかの並列化ランタイムシステムから発行された警告メッセージを出力できます。
% setenv SUNW_MP_WARN TRUE |
sunw_mp_register_warn() を使用して、警告メッセージを処理する関数を登録してある場合、SUNW_MP_WARN は警告メッセージを出力しません。これは、環境変数を TRUE に設定してある場合も同様です。関数を登録しておらず、SUNW_MP_WARN を TRUE に設定してある場合、SUNW_MP_WARN は警告メッセージを stderr に出力します。関数を登録しておらず、SUNW_MP_WARN を設定していない場合、警告メッセージは発行されません。sunw_mp_register_warn() の詳細については、「3.2.1 OpenMP の実行時の警告の処理」を参照してください。
プログラムを実行すると、マスタースレッドにはメインメモリースタックが、各スレーブスレッドには個別のスタックが保持されます。スタックとは、サブプログラムが呼び出されている間、引数と自動変数を保持するために使用される一時的なメモリーアドレス空間です。
メインスタックのデフォルトサイズは、およそ 8M バイトです。現在のスタックサイズの確認と設定には、limit コマンドを使用します。次に例を示します。
% limit cputime unlimited filesize unlimited datasize 2097148 kbytes stacksize 8192 kbytes <- current main stack size coredumpsize 0 kbytes descriptors 256 memorysize unlimited % limit stacksize 65536 <- set main stack to 64Mb |
マルチスレッド化されたプログラムの各スレーブスレッドは、それ自体のスレッドスタックを持ちます。このスタックはマスタースレッドのメインスタックに似ていますが、各スレッド固有のものです。スレッドのスタックには、スレッド固有の配列とその (スレッドに対して局所的な) 変数が割り当てられます。
スレーブスレッドはすべて、同じスタックサイズを持ちます。デフォルトのスタックサイズは、32 ビットアプリケーションの場合は 4M バイト、64 ビットアプリケーションの場合は 8M バイトです。このサイズは、STACKSIZE 環境変数で設定します。
% setenv STACKSIZE 16483 <- Set thread stack size to 16 Mb |
並列化されたコードでは、通常、スレッドのスタックサイズをデフォルト値より大きな値に設定する必要があります。
時折、スタックサイズを増やす必要があるという警告メッセージがコンパイラによって表示されることがあります。しかし、通常 (とりわけスレッド固有 / 局所の配列が関わる場合)、設定すべきサイズは試行錯誤でしか把握できません。スタックサイズがスレッドを実行するには小さすぎる場合、プログラムはセグメント例外を生成して終了します。
STACKSIZE 環境変数の設定は、Solaris pthreads API を使用しているプログラムに影響しません。
並列化された C では、キーワード restrict を使用できます。キーワード restrict を適切に使用すると、コードシーケンスを並列化できるかどうかを判別するために必要なデータの別名をオプティマイザが認識する場合に有効です。詳細については、「D.1.2 C99 のキーワード」を参照してください。
C コンパイラは、プログラム中のループを解析して、ループの各繰り返しを安全に並列実行できるかどうかを判断します。この解析の目的は、ループ中の任意の 2 個の繰り返しが、互いに干渉しないかどうかを調べることです。通常、干渉は、ある繰り返しが書き込みを行なっている変数に対して、別の繰り返しが読み込みを行うと発生します。次に示すプログラムの一部を考えてみましょう。
for (i=1; i < 1000; i++) { sum = sum + a[i]; /* S1 */ } |
「3.4 データの依存性と干渉」では、2 個の連続した繰り返しである i および i+1 が、同じ変数 sum に書き込みと読み込みを実行しています。したがって、このような 2 個の繰り返しを並列に実行するには、なんらかの方法で変数をロックすることが必要になります。ロックをしないと、2 個の連続した繰り返しを安全に並列実行することができなくなります。
ところが、このロック機構を使用すると、オーバーヘッドが発生してプログラムの実行を遅くすることになります。C コンパイラは「3.4 データの依存性と干渉」のループの並列化を行いません。「3.4 データの依存性と干渉」には、2 個の連続したループの繰り返しにデータの依存関係があるからです。別の例を考えてみましょう。
for (i=1; i < 1000; i++) { a[i] = 2 * a[i]; /* S1 */ } |
この場合、ループ中の各繰り返しでは、異なる配列の要素が参照されています。したがって、ループ中の繰り返しを実行する順番を守る必要がありません。また、異なる繰り返しでアクセスするデータが互いに干渉しないため、ロックを使用せずに並列実行することが可能になります。
ループ内の 2 個の異なる繰り返しで、同じ変数を参照していないかどうかを判断するためにコンパイラが実行する解析を、「データ依存性解析」といいます。1 回でも変数に書き込みを実行している場合には、データ依存性によって並列化することができなくなります。コンパイラが実行する依存性解析の結果、次のいずれかの解答が得られます。
依存性があります。この場合には、ループを安全に並列実行できません。前述の「3.4 データの依存性と干渉」がこれに該当します。
ループ内に依存性がありません。ループを任意の数のプロセッサを使用して並列に実行することができます。前述の「3.4 データの依存性と干渉」がこれに該当します。
依存性を確認できません。コンパイラは、安全に実行することを重視して、ループに並列実行できないような依存関係が存在するものと仮定して、ループを並列化しません。
「3.4 データの依存性と干渉」ではループの 2 個の繰り返しで配列 a の同じ要素に書き込まれるかどうかは、配列 b に重複する要素が存在するかどうかによって決まります。コンパイラがこの事実を確認できないかぎり依存性があるものと判断され、ループは並列化されません。
for (i=1; i < 1000; i++) { a[b[i]] = 2 * a[i]; } |
ループの並列実行は、Solaris スレッドによって実行されます。プログラムの初期実行を行うスレッドをマスタースレッドといいます。プログラムの起動時に、マスタースレッドによって複数のスレーブスレッドが生成されます (次の図を参照)。プログラムの終了時には、すべてのスレーブスレッドが終了されます。オーバーヘッドを最小限に抑えるために、スレーブスレッドの生成は 1 回だけ実行されます。
起動後、マスタースレッドによってプログラムの実行が開始されますが、スレーブスレッドはアイドル状態で待機します。マスタースレッドが並列ループを検出すると、ループの異なる繰り返しがスレーブおよびマスタースレッドに割り当てられ、ループの実行が開始されます。それぞれのスレッドが実行を終了すると、残りのスレッドの終了と同期が取られます。この同期を取る点を「バリア」といいます。すべてのスレッドが分担した実行を終了してバリアに達するまで、マスタースレッドは残りのプログラムを実行することができません。スレーブスレッドは、バリアに達すると、ほかの並列化された部分が検出されるまで待ち状態になり、マスタースレッドがプログラムの実行を続行します。
この処理では、次に説明するオーバーヘッドが発生します。
同期と作業を分散するためのオーバーヘッド
バリア同期でのオーバーヘッド
一般的な並列ループの中には、並列化で得られるメリットよりオーバーヘッドの方が多くなってしまうものがあります。このようなループでは、実行速度が大きく低下することがあります。次の図ではループが並列化されていますが、水平の棒で示されたバリアは相当なオーバーヘッドを示しています。バリア間の作業は、図中に示すとおりに 1 つずつ実行される (順次実行) か、あるいは同時に実行 (並列実行) されます。ループの並列実行に必要な時間は、バリアの位置でマスタースレッドとスレーブスレッドの同期を取るために必要な時間よりはるかに短くてすみます。
データの依存性が存在してもコンパイラがループを並列化できる場合があります。次の例を考えてみましょう。
for (i=1; i < 1000; i++) { t = 2 * a[i]; /* S1 */ b[i] = t; /* S2 */ } |
この例では、配列 a と b が重なりあっていないと仮定すると、2 回の繰り返しの間に、変数 t による明らかなデータ依存性が存在します。繰り返しの 1 回目と 2 回目に注目すると、次のような文が実行されることになります。
t = 2*a[1]; /* 1 */ b[1] = t; /* 2 */ t = 2*a[2]; /* 3 */ b[2] = t; /* 4 */ |
文 1 および 3 によって変数 t が変更されるので、これらを並列実行することはできません。しかし、変数 t は常に同じ繰り返しの中で計算されて使用されるので、コンパイラは繰り返しごとに変数 t のコピーを使用することができます。したがって、このような変数による異なる繰り返し間での干渉を回避することができます。実際に変数 t は、繰り返しを実行する各スレッドに固有の変数として使用されます。これを説明した例を、次に示します。
for (i=1; i < 1000; i++) { pt[i] = 2 * a[i]; /* S1 */ b[i] = pt[i]; /* S2 */ } |
「3.4.2 固有スカラーと固有配列」は「3.4 データの依存性と干渉」と基本的に同じ例ですが、各スカラー変数参照 t が配列参照 pt に置き換えられています。各繰り返しでは、pt の異なる要素が使用されるので、任意の 2 個の繰り返し間でのデータ依存性がなくなります。ただし、この方法では、大きな配列を余分に生成することになります。実際には、コンパイラによってスレッドごとに 1 個の変数だけが割り当てられ、その変数をループの実行で使用します。つまりこのような変数は、スレッドごとに固有であるといえます。
コンパイラは、配列変数を固有化してループを並列実行することもできます。次の例を考えてみましょう。
for (i=1; i < 1000; i++) { for (j=1; j < 1000; j++) { x[j] = 2 * a[i]; /* S1 */ b[i][j] = x[j]; /* S2 */ } } |
「3.4.2 固有スカラーと固有配列」では、外側のループの異なる繰り返しによって、配列 x の同じ要素が変更されるので、外側のループを並列化することはできません。しかし、外側のループを実行するそれぞれのスレッドに配列 x 全体のスレッド固有のコピーが存在すれば、外側の任意の 2 個のループ間で干渉が発生しません。これを説明した例を次に示します。
for (i=1; i < 1000; i++) { for (j=1; j < 1000; j++) { px[i][j] = 2 * a[i]; /* S1 */ b[i][j] = px[i][j]; /* S2 */ } } |
スレッド固有スカラー変数の場合と同様に、配列をすべての繰り返しに対して展開する必要はありません。システムで実行されるスレッドの数に対してのみ展開すればよいことになります。これはコンパイラによって自動的に行われ、各スレッドのスレッド固有領域にオリジナルの配列がコピーされます。
変数のスレッド固有化は、プログラムの並列化を向上させる上で便利な方法です。しかし、スレッド固有変数がループの外側で参照される場合には、その値が正しいことを保証することが必要になります。次の例を考えてみましょう。
for (i=1; i < 1000; i++) { t = 2 * a[i]; /* S1 */ b[i] = t; /* S2 */ } x = t; /* S3 */ |
「3.4.3 ストアバック変数の使用」では、文 S3 で参照されている変数 t の値が、ループを終了したときの最終結果になります。変数 t がスレッド固有化され、ループの実行が終了したあと、t の正しい値をオリジナルの変数に戻すことが必要になります。この操作をストアバック (書き戻し) といいます。これは、繰り返しの最後における t の値をオリジナルの変数 t に書き込むことで実現できます。多くの場合、この操作はコンパイラによって自動的に行われます。しかし、最終値を簡単に計算できないこともあります。
for (i=1; i < 1000; i++) { if (c[i] > x[i] ) { /* C1 */ t = 2 * a[i]; /* S1 */ b[i] = t; /* S2 */ } } x = t*t; /* S3 */ |
正しく実行した場合、文 S3 の t の値は、一般的にはループの最後における t の値にはなりません。最後の繰り返しで、C1 が真の場合に限って、最後の t の値に等しくなります。すべての場合における t の最終値を計算することは、非常に困難です。このような場合には、コンパイラはループを並列化しません。
ループの繰り返し間に本当の依存性が存在すると、依存性の原因となっている変数を簡単にスレッド固有化できない場合があります。このような状況は、たとえば、変数がある繰り返しから別の繰り返しで累積計算されているような場合に発生します。
for (i=1; i < 1000; i++) { sum += a[i]*b[i]; /* S1 */ } |
「3.4.4 縮約変数の使用」では、ループで 2 個の配列のベクトル積を計算して、共通変数 sum を求めています。このループを単純な方法で並列化することはできません。ここでは、文 S1 の計算式に結合の法則を適用し、各スレッドに対して psum[i]というスレッド固有変数を割り当てることができます。変数 psum[i]のコピーはそれぞれ 0 に初期化します。各スレッドは、スレッド固有の変数 psum[i] に自分で計算した部分和を代入します。バリアに達したら、すべての部分和を合計してオリジナルの変数 sum に代入します。この例では、和の縮約をしているので、変数 sum を縮約変数といいます。しかし、スカラー変数を縮約変数にした場合には、丸め誤差が累積されて、sum の最終値に影響する可能性があることに注意してください。コンパイラは、ユーザーによる明確な指示がされた場合に、この操作を実行します。
実行時間の大部分を占めるプログラム部分が並列化できない場合、速度の向上は期待できません。これは、基本的にアムダールの法則の結果から言えることです。たとえば、プログラム実行の 5% 部分に相当するループしか並列化できない場合、全体的に速度を向上できる限界は 5% です。しかし、実際には、負荷の量と並列実行に伴うオーバーヘッドによって、まったく速度が向上しないこともあります。
したがって、一般的な規則として、プログラムの並列化される部分が大きくなればなるほど、大幅な速度の向上を期待できます。
それぞれの並列ループには、起動時と終了時にわずかなオーバーヘッドがあります。起動時のオーバーヘッドには作業を分散するためのものがあり、終了時には、バリアでの同期によるものがあります。ループによって実行される作業量が比較的小さい場合には、速度の向上を期待できません。実際にループの実行が遅くなることもあります。したがって、プログラム実行の大部分が小さな並列ループから構成されている場合には、全体の実行速度は上がらず、かえって遅くなることがあります。
コンパイラは、いくつかのループ変換を実行することで、ループの規模を大きくしようとします。この変換には、ループの交換およびループの融合が含まれます。したがって、一般的には、プログラム中の並列化部分が少ない場合や小さな並列化部分に分割される場合には、速度の向上を期待できません。
プログラムサイズが大きくなると、プログラムの並列度が向上することがあります。たとえば、あるプログラムが順次実行する部分がプログラムサイズの 2 乗に増加し、並列化可能な部分が 3 乗に増加するものとします。このプログラムでは、並列化された部分の作業量が順次実行する部分よりも速い勢いで増加します。したがって、資源の限界に達しないかぎり、ある時点で速度向上の効果が明確に表れます。
一般に並列 C の能力を有効利用するには、コンパイル指令を実験したり、プログラムの大きさやプログラムを再構成するといった調整を行う必要があります。
決まったサイズの問題の処理速度の向上度は、一般にアムダールの法則によって予測されます。アムダールの法則は単純に、特定の問題に対して並列化がもたらす速度の向上は、問題の逐次処理部分によって制限されると説明しています。次の式は、逐次処理領域で費やされる時間の割合が F であり、時間のうち残りの割合が P 個のプロセッサの間で一様に費やされる状況における問題の速度向上について説明します。この式からわかるように、式の 2 番目の項の値がゼロになると、値が決まっている 1 番目の項によって全体的な速度の向上度が制限されます。
次の図に、この概念を示します。灰色の部分がプログラム中の逐次処理部分を表現しています。この部分は 1、2、4、8 プロセッサ各々の場合で一定であるのに対し、斜線部分がプログラムの並列処理部分で、複数のプロセッサ間で一様に分割され、処理時間が短くなっています。
プロセッサの数が増加するにつれ、各プログラムの並列処理部分の所要時間は減少していますが、各プログラムの逐次処理部分は同じままです。
ただし実際には、複数のプロセッサに作業を分散し通信するためのオーバーヘッドが存在します。このようなオーバーヘッドは、プロセッサの数に対して一定であったり、そうでなかったりします。
次の図には、プログラムに逐次処理部分がそれぞれ 0%、2%、5%、10% 含まれる場合の理想的な速度向上が示されています。この図では、オーバーヘッドは想定されていません。
グラフは、オーバーヘッドがないと想定した場合、0%、2%、5%、および 10% の逐次処理部分を含むプログラムでの理想的な速度向上を示しています。横軸はプロセッサの数、縦軸は速度を表しています。
モデルにオーバーヘッドの影響を取り入れると、速度向上の曲線は大幅に変わります。ここでは、説明上 2 つの部分、つまり、プロセッサの数には無関係な固定部分と、使用されるプロセッサの 2 乗で増加する可変部分から成るオーバーヘッドを想定します。
S 分の 1 は、{F プラス (1 マイナス P 分の F) プラス K1 プラス K2 P 二乗} 分の 1 に等しいです。
この式で K1 と K2 は一定の係数です。この仮定では、速度向上の曲線は次の図のようになります。この場合、速度の向上にピーク点があることに注目してください。ある点を越えると、プロセッサを増加させてもパフォーマンスが下がり始めます。
グラフは、すべてのプログラムで 5 プロセッサのときにもっとも処理速度が早く、8 プロセッサまで増えると徐々に遅くなることを示しています。横軸はプロセッサの数、縦軸は速度を表しています。
アムダールの法則では、実際の問題を並列化するときの速度向上の効果を正しく予測できません。プログラムの逐次処理部分に費やされる時間の割合は、問題のサイズに依存することがあります。つまり、問題のサイズが増加すると、速度向上の可能性が大きくなる場合があります。例を使って説明します。
/* * initialize the arrays */ for (i=0; i < n; i++) { for (j=0; j < n; j++) { a[i][j] = 0.0; b[i][j] = ... c[i][j] = ... } } /* * matrix multiply */ for (i=0; i < n; i++) { for(j=0; j < n; j++) { for (k=0; k < n; k++) { a[i][j] = b[i][k]*c[k][j]; } } } |
理想的にオーバーヘッドがゼロで、2 番目に入れ子にされたループが並列に実行されると仮定すると、問題のサイズが小さい場合 (すなわち n の値が小さい) と、プログラムの順次実行部分と並列実行部分の大きさがそれほど違わないことがわかります。ところが、n が大きくなると、並列実行部分に費やされる時間が順次実行の部分に対するものよりも早い勢いで大きくなります。この問題の場合は、問題のサイズが大きくなるにつれてプロセッサの数を増やす方法が有効です。
並列ループの繰り返しを複数のスレッドに分散する作業を「ループのスケジューリング」といいます。速度を最大限に向上させるには、作業をスレッドに均等に分散することによって、オーバーヘッドがあまり発生しないようにすることが重要です。コンパイラは、異なる状況に合わせて、いくつかの種類のスケジューリングをすることができます。
ループの個々の繰り返しが実行する作業が同じである場合には、システムの複数のスレッドに均一に作業を分散すると効果があります。この方法を静的スケジューリングといいます。
for (i=1; i < 1000; i++) { sum += a[i]*b[i]; /* S1 */ } |
静的スケジューリング (チャンクスケジューリングともいう) では、各スレッドは同じ回数の繰り返しを実行します。たとえばスレッドの数が 4 であれば、前述の例では、各スレッドで 250 回の繰り返しが実行されます。割り込みが発生しないものと仮定し、各スレッドが同じ早さで作業を進行していくと、すべてのスレッドが同時に終了します。
各繰り返しで実行する作業が異なる場合、静的スケジューリングでは、一般に、よい負荷バランスを得ることができなくなります。静的スケジューリングでは、すべてのスレッドが、同じ回数の繰り返しを処理します。マスタースレッドを除くすべてのスレッドは、実行を終了すると、次の並列部分が検出されるまで待つことになります。残りのプログラムの実行はマスタースレッドが行います。セルフスケジューリングでは、各スレッドが異なる小さな繰り返しを処理し、割り当てられた処理が終了すると、同じループのさらに別の繰り返しを実行することになります。
ガイド付きセルフスケジューリング (Guided Self Scheduling、GSS) では、各スレッドは、連続した小数の繰り返しをいくつか受け持ちます。各繰り返しで作業量が異なるような場合には、GSS によって、負荷のバランスが保たれるようになります。
コンパイラは、プログラム中のループを並列に実行できるようにするために、ループ再構成のための変換を数回実行します。この変換のいくつかは、シングルプロセッサ上でのループの実行速度も向上させます。コンパイラが実行する変換を次で説明します。
ループには、並列に実行できる文とできない文とが存在することがあります。通常、並列実行できない文はごく少数です。ループの分散によって、これらの文を別のループに移動し、並列実行可能な文だけから成るループを作ります。これを次の例で説明します。
for (i=0; i < n; i++) { x[i] = y[i] + z[i]*w[i]; /* S1 */ a[i+1] = (a[i-1] + a[i] + a[i+1]/3.0; /* S2 */ y[i] = z[i] - x[i]; /* S3 */ } |
配列 x、y、w、a、z が重なりあっていないと仮定すると、文 S1 および S3 を並列実行することはできますが、文 S2 はできません。このループを異なる 2 個のループに分割すると次のようになります。
/* L1: parallel loop */ for (i=0; i < n; i++) { x[i] = y[i] + z[i]*w[i]; /* S1 */ y[i] = z[i] - x[i]; /* S3 */ } /* L2: sequential loop */ for (i=0; i < n; i++) { a[i+1] = (a[i-1] + a[i] + a[i+1]/3.0; /* S2 */ } |
この変換のあと、前述のループ L1 には並列実行を妨害する文が含まれていないので、これを並列実行できるようになります。ところが、2 番目のループ L2 は元のループの並列実行できない部分を引き継いだままです。
ループの分散は、常に効果があって安全に実行できるとはかぎりません。コンパイラは、この効果と安全性を確認するための解析を実行します。
ループが小さい、すなわちループでの作業量が少ないと、大幅にパフォーマンスを向上させることはできません。これは、ループでの作業量に比べて、並列ループを起動するときのオーバーヘッドが大きくなるためです。このような状況では、コンパイラはループの融合を使用して、いくつかのループを 1 つの並列ループに融合し、ループを大きくします。同じ回数の繰り返しを行うループが隣接していると、ループの融合は簡単にしかも安全に行われます。次の例を考えてみましょう。
/* L1: short parallel loop */ for (i=0; i < 100; i++) { a[i] = a[i] + b[i]; /* S1 */ } /* L2: another short parallel loop */ for (i=0; i < 100; i++) { b[i] = a[i] * d[i]; /* S2 */ } |
この例では、2 個の小さなループが隣どうしに記述されていて、次のように安全に融合することができます。
/* L3: a larger parallel loop */ for (i=0; i < 100; i++) { a[i] = a[i] + b[i]; /* S1 */ b[i] = a[i] * d[i]; /* S2 */ } |
これによって、並列ループの実行によるオーバーヘッドを半分にすることができます。ループの融合は、別の場合にも役に立ちます。たとえば、同じデータが 2 個のループで参照されている場合には、この 2 個のループを融合すると、参照を局所的なものにすることができます。
ただし、ループの融合は常に安全に実行できるとはかぎりません。ループの融合によって、元々存在していなかったデータの依存関係が生成されると、実行結果が正しくなくなることがあります。次の例を考えてみましょう。
/* L1: short parallel loop */ for (i=0; i < 100; i++) { a[i] = a[i] + b[i]; /* S1 */ } /* L2: a short loop with data dependence */ for (i=0; i < 100; i++) { a[i+1] = a[i] * d[i]; /* S2 */ } |
「3.7.2 ループの融合」でループの融合が実行されると、文 S2 から S1 に対するデータの依存性が生成されます。実際に、文 S1 の右辺にある a[i] の値が、文 S2 で計算されるものになります。これはループが融合されないと起こりません。コンパイラは、ループの融合を実行すべきかどうかを判断するために解析を行い、安全性と有効性を確認します。場合によっては、任意の数のループを融合できることがあります。このような方法でループの作業量を多くすると、並列実行が十分に有効であるようなループを生成することができます。
入れ子になっているループのもっとも外側のループを並列化すると、発生するオーバーヘッドが小さいために、一般に大きな効果が期待できます。しかし、そのループに依存性がある場合は、並列化することは安全ではありません。次の例で説明します。
for (i=0; i <n; i++) { for (j=0; j <n; j++) { a[j][i+1] = 2.0*a[j][i-1]; } } |
この例では、添字変数 i を持つループは、連続する 2 つの繰り返しで依存関係があるために、並列化することができません。ただし、2 つのループを交換することができるため、交換すると並列ループ (j のループ) が今度は外側のループになります。
for (j=0; j<n; j++) { for (i=0; i<n; i++) { a[j][i+1] = 2.0*a[j][i-1]; } } |
この結果生成されたループでは並列作業の分散に対するオーバーヘッドが 1 回で済むのに対して、元のループでは、n 回必要でした。コンパイラは、これまで説明したように、ループの交換をするかどうか決定するための解析を行い、安全性と有効性を確認します。
ISO C の別名を使用すると、ループを並列化できなくなることがあります。別名とは、2 個の参照が記憶領域の同じ位置を参照する可能性のある場合に発生します。次の例を考えてみましょう。
void copy(float a[], float b[], int n) { int i; for (i=0; i < n; i++) { a[i] = b[i]; /* S1 */ } } |
変数 a および b は引数であるため、次のように呼ばれる場合には、a および b が重なりあった記憶領域を参照している可能性があります。次のようなルーチン copy が呼び出される例を考えてみましょう。
copy (x[10], x[11], 20); |
呼び出された側では、copy ループの連続した 2 回の繰り返しが、配列 x の同じ要素を読み書きしている可能性があります。しかし、ルーチン copy が次のように呼び出された場合には、実行される 20 回の繰り返しループで、重なりあう可能性がなくなります。
copy (x[10], x[40], 20); |
一般的に、ルーチンがどのように呼び出されるかをコンパイラが知っていないかぎり、この状況を正しく解析することは不可能になります。ANSI/ISO C では、ANSI C に対する拡張キーワードを装備することで、このような別名の問題に対して指示することが可能になっています。詳細については、「3.8.2 制限付きポインタ」を参照してください。
別名の問題の一因は、配列参照とポインタ計算演算を定義できる C 言語の性質にあります。効率的にループを並列化するためには、プラグマを自動的または明示的に使用して、配列として配置されているすべてのデータを、ポインタではなく C の配列参照の構文を使用して参照する必要があります。ポインタ構文が使用されると、コンパイラはループの異なる繰り返し間でのデータの関係を解析できなくなります。そのため、安全性を考慮してループを並列化しなくなります。
コンパイラが効率よくループを並列化できるようにするには、左辺値が記憶領域の特定の領域を示していなければいけません。別名とは、記憶領域の決まった位置を示していない左辺値のことです。オブジェクトへの 2 個のポインタが別名であるかどうかを判断することは困難です。これを判断するにはプログラム全体を解析することが必要であるため、非常に時間がかかります。次の関数 vsq() を考えてみましょう。
void vsq(int n, double * a, double * b) { int i; for (i=0; i<n; i++) { b[i] = a[i] * a[i]; } } |
ポインタ a および b が異なるオブジェクトをアクセスすることをコンパイラが知っている場合には、ループ内の異なる繰り返しを並列に実行することができます。しかし、ポインタ a および b でアクセスされるオブジェクトが重なりあっていれば、ループを安全に並列実行できなくなります。コンパイル時に関数 vsq() を単純に解析するだけでは、a および b によるオブジェクトのアクセスが重なりあっているかどうかを知ることはできません。この情報を得るには、プログラム全体を解析することが必要になります。
制限付きポインタを使ってオブジェクトを明確に区別すると、コンパイラによるポインタ別名の解析が実行可能になります。次に、vsq() の関数パラメータを制限付きポインタとして宣言した例を示します。
void vsq(int n, double * restrict a, double * restrict b) |
ポインタ a および b が制限付きポインタとして宣言されているので、a および b で示された記憶領域が区別されていることがわかります。この別名情報によって、コンパイラはループの並列化を実行することができます。
キーワード restrict は volatile に似た型修飾子で、ポインタ型に対して有効です。なお、restrict は -Xs モードでコンパイルする場合を除き、-xc99=all を使用する場合に有効なキーワードです。ソースコードを変更しない場合があります。その場合、次のコマンド行オプションを使用して、ポインタ型の値をとる関数の引数を restrict ポインタとして扱うように指定できます。
-xrestrict=[func1,…,funcn] |
関数リストが指定されている場合、指定された関数内のポインタパラメータは制限付きとして扱われます。指定されていない場合は、C ファイル全体のすべてのポインタパラメータが制限付きとして扱われます。たとえば、-xrestrict=vsq を使用すると、前述の関数 vsq() についての最初の例では、ポインタ a および b がキーワード restrict によって修飾されます。
restrict を正しく使用することはとても重要です。区別できないオブジェクトを指しているポインタを制限付きポインタにしてしまうと、ループを正しく並列化することができなくなり、不定な動作をすることになります。たとえば、関数 vsq() のポインタ a および b が重なりあっているオブジェクトを指している場合には、b[i] と a[i+1] などが同じオブジェクトである可能性があります。このとき a および b が制限付きポインタとして宣言されていなければ、ループは順次実行されます。a および b が間違って制限付きであると宣言されていれば、コンパイラはループを並列実行するようになりますが、この場合 b[i+1] の結果は b[i] をを計算したあとでなければ得られないので、安全に実行することはできません。
すでに述べたように、並列化の適用や有効性をコンパイラだけで決めるには、情報が不十分なことがあります。コンパイラはプラグマをサポートしており、コンパイラだけでは不可能なループの並列化を効率よく実行することができます。この節の残りの部分で説明する Sun 固有の MP プラグマは、OpenMP 規格に準拠するため非推奨になりました。標準命令については、『OpenMP API ユーザーズガイド』を参照してください。
Sun 固有の MP プラグマは推奨されず、サポートされません。代わりに、OpenMP 3.0 規格で規定された API をサポートします。標準命令への移植については、『OpenMP API ユーザーズガイド』を参照してください。
直列プラグマには 2 通りあり、どちらも for ループに適用されます。
#pragma MP serial_loop
#pragma MP serial_loop_nested
#pragma MP serial_loop は、次に存在する for ループを自動的に並列化しないことを指示します。
#pragma MP serial_loop_nested は、次に存在する for ループ、およびその for ループの中で入れ子になっている for ループを自動的に並列化しないことを指示します。
これらのプラグマのスコープは、そのプラグマから始まり、次のブロックの始まりか現在のブロック内のプラグマに続く最初の for ループ、または現在のブロックの終わりのいずれか先に達したところで終わります。
Sun 固有の MP プラグマは推奨されず、サポートされません。代わりに、OpenMP 3.0 規格で規定された API をサポートします。標準命令への移植については、『OpenMP API ユーザーズガイド』を参照してください。
並列プラグマは 1 つだけあります。#pragma MP taskloop [options]
MP taskloop プラグマは、オプションとして、次の引数を取ることができます。
maxcpus (プロセッサ数)
private (スレッド固有変数リスト)
shared (共有変数リスト)
readonly (読み取り専用変数リスト)
storeback (ストアバック変数リスト)
savelast
reduction (縮約変数リスト)
schedtype (スケジューリング型)
このプラグマのスコープは、プラグマから始まり、次のブロックの始まりか現在のブロック内のプラグマに続く最初の for ループ、または現在のブロックの終わりのいずれか先に達したところで終わります。プラグマは、スコープの終端に到達した時点で最初に見つかった for ループに適用されます。
オプションは、1 つの MP taskloop pragma に 1 つだけ指定できます。ただし、プラグマは蓄積されて、スコープ内の最初に見つかった for ループに適用されます。
#pragma MP taskloop maxcpus(4) #pragma MP taskloop shared(a,b) #pragma MP taskloop storeback(x) |
これらのオプションは、for ループの前に複数回指定できます。オプションが衝突を起こす場合には、コンパイラによって警告メッセージが出力されます。
MP taskloop プラグマは、現在のブロック内にある次の for ループに適用されます。Sun ANSI/ISO C によって並列化された for ループに入れ子は存在しません。
MP taskloop プラグマは、for ループを並列化するように指示します。
不規則なフロー制御や、一定しない増分による繰り返しを持った for ループに対しては、正当な並列化を実行できません。たとえば、setjmp、longjmp、exit、abort、return、goto、labels、break を含んだ for ループは並列化に適しません。
特に重要なこととして、繰り返し間の依存性を持った for ループでも、明示的に並列化できる点に注意してください。すなわち、このようなループに対して MP taskloop プラグマが指定されていると、for ループが並列化に適していないと判断されないかぎり、単にこの指示に従って並列化を実行してしまいます。このような明示的な並列化を行なった場合は、不正確な結果が発生しないかを確認してください。
1 つの for ループに対して serial_loop または serial_loop_nested と taskloop の両方のプラグマが指定されている場合には、最後の指定が優先的に使用されます。
次の例を考えてみましょう。
#pragma MP serial_loop_nested for (i=0; i<100; i++) { # pragma MP taskloop for (j=0; j<1000; j++) { ... } } |
この例では、i ループは並列化されませんが、j ループは並列化されます。
#pragma MP taskloop maxcpus (プロセッサ数) は、指定が可能であれば、現在のループに対して使用されるプロセッサの数を指定します。
maxcpus に指定する値は正の整数でなければいけません。maxcpus が 1 であれば、指定されたループは直列に実行されます。なお、maxcpus を 1 に指定した場合には、serial_loop プラグマを指定したことと同等になる点に注意してください。また、maxcpus の値か PARALLEL 環境変数のどちらか小さい方の値が使用されます。環境変数 PARALLEL が指定されていない場合には、この値に 1 が指定されているものとして扱われます。
1 つの for ループに複数の maxcpus プラグマが指定されている場合には、最後に指定された値が優先的に使用されます。
ループに使用される変数は、private、shared、reduction、または readonly のどれかに分類されます。1 つの変数は、これらの種類のうち 1 つにのみ属します。変数の種類を reduction または readonly にするには、明示的にプラグマで指示しなければいけません。#pragma MP taskloop reduction および #pragma MP taskloop readonly を参照してください。変数を private または shared にするには明示的にプラグマを使用するか、または次のスコープの規則に基づいて決まります。
スレッド private 変数は、for ループのある繰り返しを処理するためにそれぞれのプロセッサが専用に使用する値を保持します。別の言い方をすれば、for ループのある繰り返しでスレッド private 変数に割り当てられた値は、for のループの別の繰り返しを処理しているプロセッサからは見えません。これに対して shared 変数は、for ループの繰り返しを処理しているすべてのプロセッサから現在の値にアクセスできる変数のことです。ループのある繰り返しを処理しているプロセッサが shared 変数に代入した値は、そのループの別の繰り返しを処理しているプロセッサからでも見ることができます。共有変数を参照しているループを #pragma MP taskloop 指令によって明示的に並列化する場合には、値の共有によって正確性に問題が起きないことを確認しなければいけません (競合条件の確認など)。明示的に並列化されたループの共有変数へのアクセスおよび更新では、コンパイラによる同期はとられません。
明示的に並列化されたループの解析において、変数がスレッド private と shared のどちらであるかを決定するために、次の「デフォルトのスコープの規則」が使用されます。
変数がプラグマによって明示的に分類されていない場合には、その変数がポインタまたは配列として宣言されていて、かつループ内では配列構文を使用して参照しているかぎり、その変数はデフォルトで shared 変数として分類されます。これ以外の場合は、スレッド private 変数として分類されます。
ループのインデックス変数は常にスレッド private 変数として扱われ、また常に storeback 変数です。
明示的に並列化された for ループ内で使用されているすべての変数を、shared、private、reduction、または readonly として明示的に指定し、「デフォルトのスコープの規則」が適用されないようにしてください。
コンパイラは、共有変数に対するアクセスの同期を一切実行しないので、たとえば、配列参照を含んだループに対して MP taskloop プラグマを使用する前には、十分な考察が必要になります。このように明示的に並列化されたループで、繰り返し間でのデータ依存性がある場合には、並列実行を行うと正しい結果を得られないことがあります。コンパイラによって、このような潜在的な問題を検出し、警告メッセージを出力することもできますが、一般的にこれを検出することは非常に困難です。なお、共有変数に対する潜在的な問題を持ったループでも、明示的に並列化を指示されると、コンパイラはこの指示に従います。
#pragma MP taskloop private (スレッド固有変数)
このプラグマは、現在のループでスレッド固有変数として扱われる必要のあるすべての変数を指定するために使用します。ループで使用されている別の変数は、それ自体が明確にshared、readonly、または reduction であることが指定されていないかぎり、デフォルトのスコープの規則に従って、shared またはスレッド private のどちらかに分類されます。
スレッド private 変数は、ループのある繰り返しを処理するためにそれぞれのプロセッサが専用に使用する値を保持します。別の言い方をすれば、ループのある繰り返しを処理しているプロセッサによってスレッド private 変数に代入された値は、そのループの別の繰り返しを処理しているプロセッサから見ることはできません。スレッド private 変数には、ループの繰り返しの開始時に初期値は代入されず、繰り返し内で最初に使用される前に、その繰り返し内で値が代入されなければいけません。値が設定される前にその値を参照するように明確に宣言されたスレッド private 変数を持つループを実行すると、その動作は保証されません。
#pragma MP taskloop shared (共有変数リスト)
このプラグマは、現在のループでスレッド shared 変数として扱われる必要のあるすべての変数を指定するために使用します。ループで使用されている別の変数は、それ自体が明確にスレッド private、 readonly、storeback、または reduction であることが指定されていないかぎり、デフォルトのスコープの規則に従って、shared またはスレッド private のどちらかに分類されます。
shared 変数とは、ある for ループの繰り返しを処理しているすべてのプロセッサから現在の値を見ることのできる変数のことです。ループのある繰り返しを処理しているプロセッサが shared 変数に代入した値は、そのループの別の繰り返しを処理しているプロセッサからでも見ることができます。
#pragma MP taskloop readonly (読み取り専用変数リスト)
readonly 変数は、ループの繰り返しで変更されない共有変数の特殊なクラスです。変数を読み取り専用として指定すると、ループの繰り返しを処理しているそれぞれのプロセッサに対して、個々にコピーされた変数値が使用されます。
#pragma MP taskloop storeback (ストアバック変数リスト)
このプラグマは、現在のループで storeback 変数として扱われる必要のあるすべての変数を指定するために使用します。
storeback 変数とは、ループの中で変数値が計算され、その値がループの終了後に使用される変数のことです。ループの最後の繰り返しにおける storeback 変数の値が、ループの終了後に利用可能になります。このような変数は、その変数が明示的な宣言やデフォルトのスコープ規則によってスレッド固有変数となっている場合には、この指令を使用して明示的に storeback 変数として宣言するとよいでしょう。
なお、storeback 変数に対する最終的な戻し操作 (ストアバック操作) は、明示的に並列化されたループの最後の繰り返しにおいて、その中で実際に storeback の値が変更されたかどうかには関係なく実行される点に注意してください。すなわち、ループの最後の繰り返しを処理するプロセッサと、storeback 変数の最終的な値を保持 ているプロセッサとは、異なる可能性があります。次の例を考えてみましょう。
#pragma MP taskloop private(x) #pragma MP taskloop storeback(x) for (i=1; i <= n; i++) { if (...) { x=... } } printf (“%d”, x); |
前述の例では、printf() 呼び出しによって出力される storeback 変数 x の値は、i ループを直列に実行した場合の出力値とは異なる可能性があります。なぜならば、明示的に並列化されたループでは、ループの最後の繰り返し (すなわち i==n のとき) を処理し、x に対してストアバック操作を行うプロセッサは、現在最後に更新された x の値を保持するプロセッサとは同じでないことがあるからです。このような潜在的な問題に対し、コンパイラは警告メッセージを出力します。
明示的に並列化されたループでは、配列として参照される変数を storeback 変数としては扱いません。したがって、このような変数にストアバック処理が必要な場合 (たとえば、配列として参照される変数がスレッド固有変数として宣言されている場合) には、その変数を ストアバック変数リストに含める必要があります。
#pragma MP taskloop savelast
このプラグマは、ループ内のすべてのスレッド固有変数をストアバック変数として扱うために使用します。このプラグマの構文を次に示します。
#pragma MP taskloop savelast
各変数をストアバック変数として宣言するときには、それぞれのスレッド固有変数をリストするよりも、この形式が便利であることがよくあります。
#pragma MP taskloop reduction (list_of_reduction_variables) このプラグマは、縮約変数リストにあるすべての変数が、そのループに対して reduction 変数として扱われるために使用します。reduction 変数とは、ループのある繰り返しを処理している個々のプロセッサによって、その値が部分的に計算され、最終値がすべての部分値から計算される変数のことをいいます。reduction 変数リストにより、そのループが縮約ループであることをコンパイラに指示し、適切な並列縮約用のコードを生成できるようにします。次の例を考えてみましょう。
#pragma MP taskloop reduction(x) for (i=0; i<n; i++) { x = x + a[i]; } |
ここでは変数 x が (sum) 縮約変数であり、i ループが (sum) 縮約ループになっています。
Sun ISO C コンパイラには、指定されたループのスケジューリングを戦略的に制御するために、taskloop プラグマと同時に使用するいくつかのプラグマが用意されています。このプラグマの構文を次に示します。
#pragma MP taskloop schedtype (スケジューリング型)
このプラグマによって、並列化されたループをスケジュールするためのスケジューリング型を指定することができます。スケジューリング型には、次のいずれかを指定できます。
static
static スケジューリングでは、ループのすべての繰り返しが、そのループを処理するすべてのプロセッサに均等に配分されます。次の例を考えてみましょう。
#pragma MP taskloop maxcpus(4) #pragma MP taskloop schedtype(static) for (i=0; i<1000; i++) { ... } |
前述の例では、4 個のプロセッサが、ループの繰り返しを 250 ずつ処理します。
self [(chunk_size)]
self スケジューリングでは、ループのすべての繰り返しが処理されるまで、固定された回数の繰り返しチャンクサイズを、そのループを処理するそれぞれのプロセッサで処理します。オプションの chunk_size には、使用するチャンクサイズを指定します。chunk_size は、正の整定数か、もしくは整数型の変数でなければいけません。変数の chunk_size が指定された場合は、そのループを開始する前に、その変数が正の整数値であるかどうかが評価されます。最小チャンクサイズが指定されていない場合、もしくは、この値が正でない場合、チャンクサイズはコンパイラによって決められます。次の例を考えてみましょう。
#pragma MP taskloop maxcpus(4) #pragma MP taskloop schedtype(self(120)) for (i=0; i<1000; i++) { ... } |
前述の例では、ループを処理するそれぞれのプロセッサに割り当てられる繰り返し数は、割り当て順に解釈すると次のようになります。
120、120、120、120、120、120、120、120、40。
gss [(min_chunk_size)]
guided self スケジューリングでは、ループのすべての繰り返しが処理されるまで、可変数の繰り返し (「最小チャンクサイズ」) を、そのループを処理するそれぞれのプロセッサで処理します。オプションの min_chunk_size を指定すると、可変なチャンクサイズが最低でも min_chunk_size になるように設定されます。min_chunk_size は、正の整定数か、もしくは整数型の変数でなければいけません。変数の min_chunk_size が指定された場合は、そのループを開始する前に、その変数が正の整数値であるかどうかが評価されます。最小チャンクサイズが指定されていない場合、もしくは、この値が正でない場合、チャンクサイズはコンパイラによって決められます。次の例を考えてみましょう。
#pragma MP taskloop maxcpus(4) #pragma MP taskloop schedtype(gss(10)) for (i=0; i<1000; i++) { ... } |
前述の例では、ループを処理するそれぞれのプロセッサに割り当てられる繰り返し数は、割り当て順に解釈すると次のようになります。
250、188、141、106、79、59、45、33、25、19、14、11、10、10、10。
factoring [(min_chunk_size)]
factoring スケジューリングでは、ループのすべての繰り返しが処理されるまで、可変数の繰り返し (「最小チャンクサイズ」) を、そのループを処理するそれぞれのプロセッサで処理します。オプションの min_chunk_size を指定すると、可変なチャンクサイズが最低でも min_chunk_size になるように設定されます。min_chunk_size は、正の整定数か、もしくは整数型の変数でなければいけません。変数の min_chunk_size が指定された場合は、そのループを開始する前に、その変数が正の整数値であるかどうかが評価されます。最小チャンクサイズが指定されていない場合、もしくは、この値が正でない場合、チャンクサイズはコンパイラによって決められます。次の例を考えてみましょう。
#pragma MP taskloop maxcpus(4) #pragma MP taskloop schedtype(factoring(10)) for (i=0; i<1000; i++) { ... } |
前述の例では、ループを処理するそれぞれのプロセッサに割り当てられる繰り返し数は、割り当て順に解釈すると次のようになります。
125、125、125、125、62、62、62、62、32、32、32、32、16、16、16、16、10、10、10、10、10、10