マルチスレッド・アプリケーションの並列タスクの処理サイズ (粒度) は、並列パフォーマンスを左右します。マルチスレッド用にアプリケーションを分解する際、理論的に処理をできるだけ多くの並列タスクに「分割 (partition) 」する方法があります。次にその並列タスクで、共有データと実行順の観点から必要な通信 (communication) を特定します。タスクの分割、スレッドへのタスクの割り当て、タスク間での (共有) データの通信はコストフリーの処理ではないため、凝集化 (agglomerate) するか、パーティションを結合して、オーバーヘッドを軽減し、最も効率良い実装を行う必要があります。凝集化のステップは、並列タスクに最適な粒度を決めるプロセスです。
粒度の選択は、スレッド間のワークロードをいかにバランスよく配分するかという点に関係します。小さなタスクが多数ある場合には簡単にワークロードのバランスを保てますが、通信、同期などといった形でオーバーヘッドがかなり生じます。そのため、小さなタスクを 1 つのタスクにまとめて各タスクの粒度 (処理量) を大きくし、並列化のオーバーヘッドを抑えます。インテル® Parallel Amplifier などのツールを使用すると、アプリケーションに適切な粒度を見極めることができます。
下記は、通信オーバーヘッドを抑え、スレッドに適切な粒度を見極めることで並列プログラムのパフォーマンスがいかに向上するかを示した例です。この例は、素数を数えるアルゴリズムで、約数が見つかるかあるいは数字が素数になるまで素数を係数で割っていくという単純な総当たりアルゴリズムです。正の奇数は、(4k+1) または (4k+3)、k ≧ 0 で計算できるため、コードによりそれぞれの式に当てはまる素数を数えられます。例では、3 から 100 万までの素数を数えます。
最初のコードは、OpenMP* を使用した並列バージョンです。
#pragma omp parallel
{ int j, limit, prime;
#pragma for schedule(dynamic, 1)
for(i = 3; i <= 1000000; i += 2) {
limit = (int) sqrt((float)i) + 1;
prime = 1; // assume number is prime
j = 3;
while (prime && (j <= limit)) {
if (i%j == 0) prime = 0;
j += 2;
}
if (prime) {
#pragma omp critical
{
numPrimes++;
if (i%4 == 1) numP41++; // 4k+1 primes
if (i%4 == 3) numP43++; // 4k-1 primes
}
}
}
}
このコードは、通信オーバーヘッド (同期) が高く、また個々のタスクサイズがスレッドに対して小さ過ぎます。ループの内側には、カウント変数のインクリメントを安全に行うことができるようクリティカル・セクションがあります。インテル®Parallel Amplifier が示すように (図 1)、クリティカル領域によって、同期とロックのオーバーヘッドが並列ループに加わります。
図 1. ロックと待機の分析結果により、OpenMP* のクリティカル領域が同期オーバーヘッドの原因であることがわかります。
大規模なデータセット内で値に基づいてカウンター変数をインクリメントすることは、リダクションと呼ばれる一般的な式です。クリティカル領域を少なくして、OpenMP のリダクション節を追加することでロックと同期のオーバーヘッドを取り除くことができます。
#pragma omp parallel
{
int j, limit, prime;
#pragma for schedule(dynamic, 1) \
reduction(+:numPrimes,numP41,numP43)
for(i = 3; i &;lt;= 1000000; i += 2) {
limit = (int) sqrt((float)i) + 1;
prime = 1; // assume number is prime
j = 3;
while (prime && (j &;lt;= limit))
{
if (i%j == 0) prime = 0;
j += 2;
}
if (prime)
{
numPrimes++;
if (i%4 == 1) numP41++; // 4k+1 primes
if (i%4 == 3) numP43++; // 4k-1 primes
}
}
}
ループ本体のクリティカル領域が排除されることにより、ループの反復実行回数によっては大幅に実行速度を向上できることがあります。しかし、上記のコードにはまだ並列オーバーヘッドが存在し、その原因は、各タスクの処理サイズの小ささにあります。スケジュール (dynamic, 1) 節では、スケジューラーが動的に各スレッドに対して同時に 1 回の反復 (またはチャンク) を分配するよう指定されています。各ワーカースレッドは、1 回の反復を処理し、それからスケジューラーに戻って、別の反復処理を取得するために同期します。チャンクサイズを大きくすることでスレッドに割り当てられる各タスクの処理サイズが大きくなり、各スレッドがスケジューラーと同期をとる回数が減ります。
この方法によってパフォーマンスを向上できますが、粒度を大きくし過ぎると、(前述したように) ロード・インバランスを引き起こします。たとえば、次のコードのようにチャンクサイズを 10,000 に増やしたとします。
#pragma omp parallel
{
int j, limit, prime;
#pragma for schedule(dynamic, 100000) \
reduction(+:numPrimes, numP41, numP43)
for(i = 3; i <= 1000000; i += 2)
{
limit = (int) sqrt((float)i) + 1;
prime = 1; // assume number is prime
j = 3;
while (prime && (j <= limit))
{
if (i%j == 0) prime = 0;
j += 2;
}
if (prime)
{
numPrimes++;
if (i%4 == 1) numP41++; // 4k+1 primes
if (i%4 == 3) numP43++; // 4k-1 primes
}
}
}
このコードの実行をインテル®Parallel Amplifier で分析すると、4 つのスレッドで行われる処理量にインバランスが生じていることがわかります (図 2)。この計算例の重要なポイントは、それぞれのチャンクの処理量が異なり、またタスクとして割り当てられているチャンクが少な過ぎる (4 つのスレッドに対して 10 個のチャンク) ためにロード・インバランスが生じていることです。(for ループからの) 素数の値が増えるにつれて、(while ループの) 素数の係数のテストのために必要な反復処理も増えます。このように、各チャンクの処理全体で前のチャンクよりも while ループの反復数が多くなります。
図 2. Concurrency (並列性) の分析結果により、各スレッドによって使用される実行回数のインバランスが示されています。
プログラムに最適な粒度を見つけるには、より適切な処理サイズ (100) を使用しなければなりません。また、連続したタスク間での処理量の差は前のチャンクサイズよりは深刻ではないため、動的なスケジュールではなく静的なスケジュールを使用して、さらに並列オーバーヘッドを取り除くことができます。下記のコードでは、スケジュール節の変更によって、このコードセグメントからオーバーヘッドが取り除かれ、並列パフォーマンス全体で優れた実行速度を達成しています。
#pragma omp parallel
{
int j, limit, prime;
#pragma for schedule(static, 100) \
reduction(+:numPrimes, numP41, numP43)
for(i = 3; i <= 1000000; i += 2)
{
limit = (int) sqrt((float)i) + 1;
prime = 1; // assume number is prime
j = 3;
while (prime && (j <= limit))
{
if (i%j == 0) prime = 0;
j += 2;
}
if (prime)
{
numPrimes++;
if (i%4 == 1) numP41++; // 4k+1 primes
if (i%4 == 3) numP43++; // 4k-1 primes
}
}
}