OpenMPでは、タスクスケジューリングは主に並列forループで使用されます。ループの各反復の計算量が等しくない場合、単純に各スレッドに同じ反復回数を割り当てると、各スレッドの計算負荷が不均等になり、一部のスレッドが先に実行されたり、一部のスレッドが後に実行されたりして、一部のCPUコアがアイドル状態になり、プログラムのパフォーマンスに影響を与えます。例えば、次のようなコードです：
int i, j;
int a = {0};
for ( i =0; i < 100; i++)
{
for( j = i; j < 100; j++ )
{
a[i][j] = i*j;
}
}
一番外側のループを並列化する場合、例えば4つのスレッドを使用し、各スレッドに平均25回のループ反復を割り当てたとすると、i = 0とi = 99では計算に100倍の差があることは明らかで、スレッド間で大きな負荷不均衡が発生する可能性があります。このような問題を解決するために、OpenMPではループの並列化のためのタスクスケジューリング方式をいくつか用意しています。
OpenMPでは、ループ並列化のためのタスクスケジューリングはschedule句を用いて実装されます。
1.1.1 スケジュール条項の使用
schedule句はフォーマットで使用されます：
schedule(type[,size])
scheduleはtypeとsizeの2つの引数を持ち、size引数はオプションです。
1.タイプパラメーター
スケジューリングタイプを示します：
- dynamic
- guided
- runtime
- static
4つのスケジューリングタイプは、実際には静的、動的、ガイド付きだけであり、ランタイムは実際には環境変数に基づいて最初の3つのタイプのいずれかを選択します。
ランスケードバー
2.サイズパラメータ
sizeパラメータはループの反復回数を示し、整数でなければなりません。static、dynamic、およびguidedスケジューリング・メソッドでは、sizeパラメータを使用する場合と使用しない場合があります。typeパラメータがruntimeの場合、sizeパラメータは不正です。
1.1.2 静的スケジューリング
並列forコンパイル指示文にschedule句が伴わない場合、ほとんどのシステムではデフォルトで静的スケジューリングが使用されます。n個のループ反復とt個のスレッドを仮定すると、各スレッドには約n/t個の反復が静的に割り当てられます。なぜ約n/t反復と言うのでしょうか？なぜなら、n/tは必ずしも整数ではないため、実際に割り当てられる反復回数は1回、またはsizeパラメータが指定されている場合は1サイズだけ異なる可能性があるからです。
スタティック・スケジューリングは、sizeパラメータなしでも、sizeパラメータ付きでも可能です。
3.sizeパラメータは使用しないでください。
sizeパラメータを指定しない場合、各スレッドにはn/t回の連続反復が割り当てられます：
スケジュール(静的)
例えば、以下のコード：
#pragma omp parallel for schedule(static)
for(i = 0; i < 10; i++ )
{
printf("i=%d, thread_id=%d/n", i, omp_get_thread_num());
}
上記のコードを実行すると、次のように表示されます：
i=0, thread_id=0
i=1、スレッド_id=0
i=2、スレッドID=0
i=3、スレッドID=0
i=4、スレッドID=0
i=5、スレッドID=1
i=6、スレッドID=1
i=7、スレッドID=1
i=8、スレッドID=1
i=9、スレッドID=1
スレッド0は0から4回連続、スレッド1は5から9回連続の繰り返しであることがわかります。マルチスレッド実行のタイミングはランダムであるため、この後の例でもそうであるように、実行されるたびに出力される結果の順序が異なる可能性があることに注意してください。
4.sizeパラメータを使用します。
sizeパラメータが使用された場合、sizeは次のように連続した反復計算のために各スレッドに割り当てられます：
schedule(static, size)
例えば、以下のコード：
#pragma omp parallel for schedule(static, 2)
for(i = 0; i < 10; i++ )
{
printf("i=%d, thread_id=%d/n", i, omp_get_thread_num());
}
実行すると次のような結果が出力されます：
i=0, thread_id=0
i=1、スレッド_id=0
i=4、スレッドID=0
i=5、スレッドID=0
i=8、スレッドID=0
i=9、スレッドID=0
i=2、スレッドID=1
i=3、スレッドID=1
i=6、スレッドID=1
i=7、スレッドID=1
プリントアウトからわかるように、0と1の反復はスレッド0に、2と3の反復はスレッド1に、4と5の反復はスレッド0に、6と7の反復はスレッド1に、...と割り当てられています。各スレッドは2つの連続した反復計算に順番に割り当てられます。
#p#
1.1.3 動的スケジューリング
動的スケジューリングは、各スレッドに動的に反復処理を割り当てることです。動的スケジューリングは、sizeパラメータの有無にかかわらず使用できます。sizeパラメータなしは、各スレッドに反復処理を1つずつ割り当てることであり、sizeパラメータありは、スレッドが指定されたサイズの回数を割り当てるたびに反復処理を行うことです。
以下は、sizeパラメータを使用しないダイナミック・スケジューリングの例です：
#pragma omp parallel for schedule(dynamic)
for(i = 0; i < 10; i++ )
{
printf("i=%d, thread_id=%d/n", i, omp_get_thread_num());
}
プリントアウトは以下の通り：
i=0, thread_id=0
i=1, thread_id=1
i=2、スレッドID=0
i=3、スレッドID=1
i=5、スレッドID=1
i=6、スレッドID=1
i=7、スレッドID=1
i=8、スレッドID=1
i=4、スレッドID=0
i=9、スレッドID=1
以下はsizeパラメータを使ったダイナミック・スケジューリングの例です：
#pragma omp parallel for schedule(dynamic, 2)
for(i = 0; i < 10; i++ )
{
printf("i=%d, thread_id=%d/n", i, omp_get_thread_num());
}
プリントアウトは以下の通り：
i=0, thread_id=0
i=1、スレッド_id=0
i=4、スレッドID=0
i=2、スレッドID=1
i=5、スレッドID=0
i=3、スレッドID=1
i=6、スレッドID=0
i=8、スレッドID=1
i=7、スレッドID=0
i=9、スレッドID=1
プリントアウトから、反復0、1、4、5、6、7はスレッド0に割り当てられ、反復2、3、8、9はスレッド1に割り当てられ、それぞれに2つの反復が割り当てられていることがわかります。
1.1.4ガイド付きスケジューリング
ガイド付きスケジューリングは、ガイド付きヒューリスティックを使用するセルフスケジューリングメソッドです。最初に各スレッドに大きな反復ブロックが割り当てられ、その後、割り当てられた反復ブロックは徐々に減っていきます。反復ブロックのサイズは指定のサイズまで指数関数的に減少し、サイズパラメータが指定されていない場合は最小の1まで減少します。
例えば、以下のコード：
#pragma omp parallel for schedule(guided,2)
for(i = 0; i < 10; i++ )
{
printf("i=%d, thread_id=%d/n", i, omp_get_thread_num());
}
プリントアウトは以下の通り：
i=0, thread_id=0
i=1、スレッド_id=0
i=2、スレッドID=0
i=3、スレッドID=0
i=4、スレッドID=0
i=8、スレッドID=0
i=9、スレッドID=0
i=5、スレッドID=1
i=6、スレッドID=1
i=7、スレッドID=1
0回目、1回目、2回目、3回目、4回目はスレッド0、5回目、6回目、7回目はスレッド1、8回目、9回目はスレッド0に割り当てられます。
1.1.5 ランタイムスケジューリング
ランタイム・スケジューリングは、これまでの3つのスケジューリング方法のような本格的なスケジューリング方法ではなく、環境変数OMP_SCHEDULEに基づいて実行時のスケジューリングタイプを決定し、最終的に使用されるスケジューリングタイプは、やはり前述の3つのスケジューリング方法のいずれかです。
例えば、unixシステムでは、setenvコマンドを使用してOMP_SCHEDULE環境変数を設定できます：
setenv OMP_SCHEDULE "dynamic, 2"
上記のコマンドでは、スケジューリング・タイプをダイナミック・スケジューリングに設定し、ダイナミック・スケジューリングの反復回数を2回としています。
Windows環境では、「システムのプロパティ|詳細|環境変数」ダイアログボックスで環境変数を設定できます。
