一般に、独立したタスク (ワークロード) のマッピングやスケジューリングは 2 つの方法 (静的および動的) で行われます。すべてのタスクが同じ長さの場合、単に利用可能なスレッド間でタスクを静的に分割する (タスクの総数をほぼ同じ大きさのグループに分割して各スレッドに割り当てる) のが最良のソリューションです。個々のタスクの長さが異なる場合、スレッドにタスクを動的に割り当てるほうが良い結果が得られます。
インテル®Parallel Amplifier で提供される並列性分析は、アプリケーションがシステムの利用可能なコアをどのように活用しているかを測定します。分析中、インテル®Parallel Amplifier は、アクティブなスレッド数を収集して、その情報を表示します。アクティブなスレッドとは、実行中のスレッド、またはキューイングされているスレッドのうち、定義された待機 API やブロッキング API で待機していないものです。実行中のスレッド数は、アプリケーションの並列レベルに対応します。並列レベルとプロセッサー数を比較することで、インテル®Parallel Amplifier は、アプリケーションによるシステムで利用可能なプロセッサーの利用状況を分類します。
ここでは、C で記述したサンプルプログラムを使用して、インテル®Parallel Amplifier がどのように hotspot とロード・インバランス問題を検出するかを説明します。このプログラムは 3 次元の距離に基づいて質点系の位置エネルギーを計算します。これはネイティブ Win32* スレッドを使用して、NUM_THREADS 変数で指定した数のスレッドを作成するマルチスレッド・アプリケーションです。この記事では、Win32 スレッド、スレッド化手法、スレッドの実装方法については説明していません。インテル®Parallel Amplifier がロード・インバランスの検出やスケーラブルな並列アプリケーションの開発にどのように役立つかについてのみ解説します。
for (i = 0; i < NUM_THREADS; i++)
{
bounds[0][i] = i * (NPARTS / NUM_THREADS);
bounds[1][i] = (i + 1) * (NPARTS / NUM_THREADS);
}
for (j = 0; j < NUM_THREADS; j++)
{
tNum[j] = j;
tHandle[j] = CreateThread(NULL,0,tPoolComputePot,&tNum[j],0,NULL);
}
DWORD WINAPI tPoolComputePot (LPVOID pArg) {
int tid = *(int *)pArg;
while (!done)
{
WaitForSingleObject (bSignal[tid], INFINITE);
computePot (tid);
SetEvent (eSignal[tid]);
}
return 0;
}
各スレッドを並列に実行するルーチン computePot を下記に示します。各スレッドはスレッドの割り当て識別番号 (tid) でインデックス付けされた格納境界を使い、使用する質点の開始 (start) と終了 (end) を決定します。スレッドはそれぞれ、反復空間 (start から end) を初期化した後、質点の位置エネルギーの計算を開始します。
void computePot (int tid) {
int i, j, start, end;
double lPot = 0.0;
double distx, disty, distz, dist;
start = bounds[0][tid];
end = bounds[1][tid];
for (i = start; i < end; i++)
{
for (j = 0; j < i-1; j++)
{
distx = pow ((r[0][j] - r[0][i]), 2);
disty = pow ((r[1][j] - r[1][i]), 2);
distz = pow ((r[2][j] - r[2][i]), 2);
dist = sqrt (distx + disty + distz);
lPot += 1.0 / dist;
}
}
gPot[tid] = lPot;
}
hotspot 分析でアプリケーションの hotspot を検出できるため、開発者は適切な関数を作成することに集中できます。このアプリケーションの合計経過時間は、インテル® Core™2 Quad プロセッサーを搭載したシングルソケット・システムで約 15.4 秒です。hotspot 分析では、computePot ルーチンがメインの hotspot で、CPU 時間のほとんど (23.331 秒) を費やしていることがわかります。関数 computePot のソースにドリルダウンすると、hotspot の詳細な内容が表示されます (図 1)。
図 1. hotspot 分析のソースコード・ビュー
並列性分析では、同ルーチンの CPU 利用率が poor で (図 2)、アプリケーションは平均 2.28 コアを使用している (図 3) ことがわかります。メインの hotspot ではすべての利用可能なコアが利用されていないため、ほとんどの時間で CPU 利用率は poor (1 つのコアのみ利用) か OK (2 ～3 コアを利用) のいずれかになっています。次に、CPU 利用率が poor の要因となっているロード・インバランスがあるかどうか見てみましょう。これを調べる最も簡単な方法は、図 4 で示されているように、新しい粒度として [Function-Thread-Bottom-up Tree (関数-スレッド-ボトムアップ・ツリー)] または [Thread-Function-Bottom-up Tree (スレッド-関数-ボトムアップ・ツリー)] を選択することです。
図 2. 並列性分析結果
図 3. 並列性分析結果のサマリービュー
並列性分析結果の時間は次の利用状況を示します。
- Idle
: プログラム中のすべてのスレッドが待機中です。実行中のスレッドはありません。
- Poor
: デフォルトでは、スレッド数が並列化ターゲットの 50% 以下の場合です。
- OK
: デフォルトでは、スレッド数が並列化ターゲットの 51 ～ 85% の場合です。
- Ideal
: デフォルトでは、スレッド数が並列化ターゲットの 86 ～ 115% の場合です。
図 4. 並列性分析結果で [Function-Thread (関数-スレッド)] グループを表示
図 4 から、このルーチンを実行している 4 つのワーカースレッドが同じ量の作業を行っていないため、ロード・インバランスが発生し、CPU 利用率が poor になっていることがわかります。このような動作が行われていると、マルチスレッド・アプリケーションは適切にスケーリングされません。ソースコードをよく調べると、メインルーチン内の外ループが、スレッドプール内に作成されるワーカースレッドの数に基づいて質点の反復を静的に分割していることがわかります (start = bounds[0][tid], end = bound[1][tid])。このルーチン内の内ループは終了条件として外のインデックスを使用しています。このため、より大きな質点数が外ループで使用されると、より多くの反復が内ループで実行されます。質点の各ペアは位置エネルギーの計算に一度しか役に立っていないことになります。この静的分配により異なる計算量が割り当てられていることがわかります。
このロード・インバランス問題を解決する 1 つの方法は、スレッドに対して質点をより動的に割り当てることです。例えば、オリジナルバージョンのように質点の連続するグループを割り当てるのではなく、各スレッドをスレッド ID (tid) でインデックス付けされた質点から開始すると、質点番号がスレッドの番号と異なるすべての質点を計算できます。例えば、2 つのスレッドを使用する場合、1 つのスレッドで偶数番号の質点を処理し、別のスレッドで奇数番号の質点を処理します。
void computePot(int tid) {
int i, j;
double lPot = 0.0;
double distx, disty, distz, dist;
for(i=tid; i<NPARTS; i+= NUM_THREADS ) { //<-for( i=start; i<end; i++ )
for( j=0; j<i-1; j++ ) {
distx = pow( (r[0][j] - r[0][i]), 2 );
disty = pow( (r[1][j] - r[1][i]), 2 );
distz = pow( (r[2][j] - r[2][i]), 2 );
dist = sqrt( distx + disty + distz );
lPot += 1.0 / dist;
}
}
gPot[tid] = lPot;
この変更後のアプリケーションの並列性分析結果では、hotspot だった関数がすべての利用可能なコアを完全に利用するようになったことを示しています (図 5)。
図 5. 変更後の並列性分析結果
サマリーペイン (図 6) で変更の結果を素早く確認できます。経過時間は ~15.4 秒から ~9.0 秒に短縮され、平均 CPU 利用率は 2.28 から 3.9 に向上しました。ワーカースレッドで等しい量の計算を行うように変更しただけで、速度が 1.7 倍になり、経過時間が ~41.5% 短縮されたことになります。
図 6. ロードバランス・バージョンのサマリービュー
サマリーと並列性分析結果からわかるように、変更後のアプリケーションはほぼすべての利用可能なコアを利用しており、逐次コードのセグメント (利用率が poor) と利用されていないセグメントがどちらもなくなっています。
スレッド化にはさまざまな手法があり、スレッドへのタスクの分配を制御する方法は手法によって異なります。以下に一般的なスレッド化手法を示します。
- 明示的またはネイティブなスレッド化手法 (Win32 スレッドと POSIX* スレッドなど)
- 抽象化手法
- インテル® スレッディング・ビルディング・ブロック (インテル®TBB)
- OpenMP*
明示的なスレッド化手法 (Win32 スレッドと POSIX スレッドなど) では、独立したタスクをスレッドに自動でスケジューリングする方法はありません。必要に応じて、そのような機能をアプリケーションにプログラミングしなければなりません。タスクの静的スケジューリングは、この例で示しているように単純です。動的スケジューリングの場合は、生産者/消費者とマネージャー/ワーカーの 2 つの方法を簡単に実装できます。前者は、1 つまたは複数のスレッド (生産者) がタスクをキューに入れ、必要に応じて消費者スレッドがタスクをキューから取り出して処理します。必須ではありませんが、生産者/消費者モデルではタスクが消費者スレッドで使用できるようになる前に前処理を行います。マネージャー/ワーカーモデルでは、ワーカースレッドは処理がある場合は常にマネージャー・スレッドを待機し、直接処理の割り当てを受けます。
どちらのモデルを使用した場合でも、適切なスレッド数とスレッドの組み合わせを使用して、計算処理のタスクを行うスレッドがアイドル状態にならないようにします。単一のマネージャー・スレッドは簡単にコード化でき、タスクの適切な分配が保証されますが、消費者スレッドがたまにアイドル状態になる場合は、消費者の数を減らすか生産者スレッドの数を増やす必要があります。アルゴリズムの考慮と割り当てられるタスク数とタスクの長さによって適切なソリューションが決まります。
OpenMP では for ワークシェアリング構造に 4 つのスケジューリング手法が用意されています (各手法の詳細な説明は OpenMP 仕様を参照)。デフォルトでは、反復の静的スケジューリングが使用されます。反復ごとの作業量が変化してパターンが予測できない場合は、反復の動的スケジューリングのほうがワークロードのバランスが向上します。
動的スケジューリングを使用すると、フォルス・シェアリングと呼ばれるマイクロアーキテクチャー上の問題が発生することがあります。フォルス・シェアリングは、パフォーマンスを低下させるパターンアクセス問題です。フォルス・シェアリングは、2 つ以上のスレッドが同じキャッシュライン (インテル®アーキテクチャーでは 64 バイト) に繰り返し書き込みを行うと発生します。ワークロードをスレッド間で動的に分配している場合は特に注意が必要です。
インテル® スレッディング・ビルディング・ブロック (インテル® TBB) は、ランタイムベースのプログラミング・モデルです。マルチコア・プロセッサーの潜在的なパフォーマンスを活用できるように支援する、テンプレート・ベースのランタイム・ライブラリーで構成されています。開発者は同時収集と並列アルゴリズムを活用して、スケーラブルなアプリケーションを作成することができます。ワークスチール・メカニズムによる分割統治スケジューリング・アルゴリズムが提供されるため、開発者はさまざまなスケジューリング・アルゴリズムについて考慮する必要がありません。ワークスチール・メカニズムを利用することで、インテル®TBB は動的にワーカースレッド間のタスクのバランスをとります。