並列パフォーマンス
マルチコア コンピュータ用にマネージ コードを最適化する
Daan Leijen and Judd Hall
この記事の内容 : :
- Task Parallel Library
- Parallel.For と ThreadPool
- 静的な作業配分
- フューチャ
|
この記事は次のテクノロジを使用しています:
Parallel FX Library
|
コンテンツ
マルチプロセッサ コンピュータが標準になりつつある一方で、シングルプロセッサの需要は落ち込んできています。このため、複数のプロセッサでプログラムを並列に実行することがパフォーマンスを向上させる鍵といえます。ただし、そのような複数のプロセッサを実際に活用するアルゴリズムを作成するのは非常に難しいのが現状です。実際、多くのアプリケーションはシングルコアだけを使用し、マルチコア コンピュータで実行しても処理速度の向上は見られません。このため、独自のプログラムを新しい方法で作成する必要があります。
TPL の概要
Task Parallel Library (TPL) は、自動的に複数のプロセッサを使用できるマネージ コードを簡単に作成できるように設計されています。このライブラリを使用すると、既存の逐次コードで潜在的な並列処理を簡単に表現でき、公開された並列タスクは使用可能なすべてのプロセッサで同時に実行されます。通常、これにより処理速度が大幅に向上します。
TPL は、Microsoft
® Research、マイクロソフトの共通言語ランタイム (CLR) チーム、および並列コンピューティング プラットフォーム チームが共同で作成しています。TPL は、Microsoft .NET Framework の次世代の同時実行サポートである Parallel FX Library の主要コンポーネントです。TPL のバージョン 1.0 はまだリリースされていませんが、最初の Parallel FX Communicty Tech Preview (CTP) が 2007 年の秋に MSDN
® で利用できるようになります。詳細については、
http://blogs.msdn.com/somasegar を参照してください。TPL は言語拡張が不要で、.NET Framework 3.5 以上で使用できます。
Visual Studio® 2008 は完全にサポートされ、すべての並列処理は通常のメソッド呼び出しを使用して表現されます。たとえば、1 つの配列の要素を二乗する次の for ループがあるとします。
for (int i = 0; i < 100; i++) {
a[i] = a[i]*a[i];
}
反復はそれぞれ別個に行われる (後続の反復は前の反復で行われた状態の更新を読み込まない) ため、次のように TPL で並列 for メソッドを呼び出して潜在的な並列処理を表すことができます。
Parallel.For(0, 100, delegate(int i) {
a[i] = a[i]*a[i];
});
Parallel.For は、3 つの引数を使用する標準の静的メソッドです。この最後の引数は、デリゲート式になります。このデリゲートは、前の例の変更されていないループ本体をキャプチャします。これにより、特にプログラムへの同時実行の導入を簡単に行うことができるようになります。
このライブラリには、動的な作業配分のための優れたアルゴリズムが含まれており、作業負荷や特定のコンピュータに自動的に適応します。一方、ライブラリのプリミティブは潜在的な並列処理を表すだけで、実際に並列処理は生成しません。たとえば、シングルプロセッサ コンピュータでは、並列 for ループは順番に実行され、厳密な逐次コードのパフォーマンスとかなり近いものになります。一方、デュアルコア コンピュータでは、ライブラリは 2 つのワーカー スレッドを使用して、作業負荷と構成に応じてループを並列に実行します。つまり、現時点でコードに並列処理を導入しておくと、複数のプロセッサが使用可能になった時点で、アプリケーションでは自動的にそれらのプロセッサが使用されます。同時に、コードは古いシングルプロセッサ コンピュータでも正しく実行されます。
ただし、ライブラリは共有メモリを使用する並列コードを正しく同期することはできません。特定のコードを安全に並列処理できるようにするのはプログラマの役目です。共有メモリに対する同時変更を保護するためには、ロックなどの他のメカニズムも必要です。ただし、TPL は同期に役立ついくつかの抽象化を備えています (これについてはこの後すぐに取り上げます)。
構造化並列処理
並列プログラミングの中で最も重要な抽象化の 1 つは並列ループです。たとえば、次の (未熟な) 行列乗算ルーチンについて考えてみましょう。
void SeqMatrixMult(int size, double[,] m1, double[,] m2, double[,] result)
{
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
result[i, j] = 0;
for (int k = 0; k < size; k++) {
result[i, j] += m1[i, k] * m2[k, j];
}
}
}
}
この例では、外側の反復は互いに独立し、潜在的に並列処理できるようになっています。この潜在的な並列処理を TPL を使用して公開するのは簡単です。まず、コンパイル時に System.Concurrency.dll アセンブリを参照します。次に、using ステートメントを使用してライブラリをコードにインポートします。
using System.Concurrency;
名前空間が使用可能になったら、行列乗算の外側の for ループを、静的な Parallel.For メソッドへの呼び出しに置き換えるだけです。
void ParMatrixMult(int size, double[,] m1, double[,] m2, double[,] result)
{
Parallel.For( 0, size, delegate(int i) {
for (int j = 0; j < size; j++) {
result[i, j] = 0;
for (int k = 0; k < size; k++) {
result[i, j] += m1[i, k] * m2[k, j];
}
}
});
}
Parallel.For コンストラクタは、3 つの引数を使用する標準の静的メソッドです。最初の 2 つの引数で、反復の制限 (0 ～サイズ) を指定します。最後の引数は、各反復で呼び出されるデリゲート関数です。このデリゲートは反復のインデックスを最初の引数として受け取り、前の例の変更されていないループ本体を実行します。デリゲートによってループ本体の自由変数が自動的にキャプチャされるため (result と m1 のように)、元のループ本体に変更を加える必要はありません。デリゲート式の詳細については、
msdn.microsoft.com/msdnmag/issues/06/00/C20 を参照してください。
最後に、いずれかの反復で例外がスローされた場合は、すべての反復が取り消され、最初にスローされた例外が呼び出し元のスレッドで再度スローされます。これにより、例外は正しく伝達されて失われることはありません。
TPL を使用しない場合、このループで潜在的な並列処理を表すのはかなり難しくなります。.NET ThreadPool クラスを使用する場合でも、同期のコストや作業区分を考慮する必要があります。図 1 に、スレッド プールを使用して並列処理される行列乗算ルーチンを示します。
Figure 1 静的な作業配分と明示的な同期
void ThreadpoolMatrixMult(int size, double[,] m1, double[,] m2,
double[,] result)
{
int N = size;
int P = 2 * Environment.ProcessorCount; // assume twice the procs for
// good work distribution
int Chunk = N / P; // size of a work chunk
AutoResetEvent signal = new AutoResetEvent(false);
int counter = P; // use a counter to reduce
// kernel transitions
for (int c = 0; c < P; c++) { // for each chunk
ThreadPool.QueueUserWorkItem(delegate(Object o)
{
int lc = (int)o;
for (int i = lc * Chunk; // iterate through a work chunk
i < (lc + 1 == P ? N : (lc + 1) * Chunk); // respect upper
// bound
i++) {
// original inner loop body
for (int j = 0; j < size; j++) {
result[i, j] = 0;
for (int k = 0; k < size; k++) {
result[i, j] += m1[i, k] * m2[k, j];
}
}
}
if (Interlocked.Decrement(ref counter) == 0) { // use efficient
// interlocked
// instructions
signal.Set(); // and kernel transition only when done
}
}, c);
}
signal.WaitOne();
}
この例は既に高度な内容になっています。作業項目にスレッド プールを使用し、単一の待機ハンドルと共にカウンタを使用してカーネル遷移の数を最小化しています。さらに、プロセッサの数に基づいてループを静的にチャンクに分割し、必要な数の 2 倍のチャンクを作成して、動的な作業負荷に適応できるようにしています。ただし、Parallel.For とは異なり、図 1 のアプローチはループ本体で例外を伝達せず、取り消すことができません。
このコードが Parallel.For メソッドよりも作成が難しく、間違いを起こしやすいのは明らかです。また、手動でチューニングしたり、最適に近い作業区分を使用しているにもかかわらず、スレッド プール アプローチでは一般的に Parallel.For メソッドよりもパフォーマンスが低下します。図 2 に、いくつかのテスト例の結果を示します。この結果は、750x750 要素を使用した行列乗算の外側のループを並列処理するときの相対的な処理速度の向上を表しています。つまり、1 は標準の for ループでの実行時間を表しています。テストは、3 GB のメモリが搭載され、Windows Vista® Ultimate を実行している 4 ソケットのデュアルコア コンピュータで行われました。シングルコア コンピュータでは、Parallel.For バージョンは実際には直接の for ループと同じように実行されます。
.gif)
図 2 Parallel.For と ThreadPool のパフォーマンスの比較
並列処理を過度に公開する
次のように 2 番目の for ループを並列処理すると、さらに多くの並列処理を公開できます。
Parallel.For( 0, size, delegate(int i) {
Parallel.For( 0, size, delegate(int j) {
result[i, j] = 0;
for (int k = 0; k < size; k++) {
result[i, j] += m1[i, k] * m2[k, j];
}
});
});
並列ループを入れ子にするのは問題がありませんが、一般的にこの方法では 2 つの理由でパフォーマンスが低下します。1 つは、この例の場合、使用可能なコアの数は一般に行列のサイズよりもはるかに少ないため、外側のループが既に十分すぎるほどの並列処理を行う機会を公開しているという点です。もう 1 つは、すべてのデリゲート式が自由変数を格納するためのメモリを割り当てているという点です。最初の例で、コストが反復で補われる割り当てが 1 つしかなかったのはこのような理由からです。新しいコードでは、内側の Parallel.For は外側のループの各反復でヒープ割り当てを実行します。CLR では割り当ては非常に効率よく行われますが、それでも反復ごとに実行される作業量と比較すると、はるかに大きなコストになります。
それらの反復は独立していないため、内側のループを並列処理できません。特に、すべての反復が result[i,j] の場所に追加されるため競合が発生します。このループを並列処理すると、2 つの反復によって現在の値がレジスタに同時に読み込まれ、追加されて結果が書き戻されます。このため、1 つの追加が失われます。内側のループを並列処理する唯一の方法は、ロックを使用して追加のループを正しく保護することです。もちろん、実際にこの方法を行うことはお勧めできません。しばらくの間追加の割り当てを無視した場合でも、同時実行の各反復は同じロックについて競合するため、パフォーマンスに大きく影響します。この点については、集計操作を説明する際に簡単に触れます。競合とロックの詳細については、
msdn.microsoft.com/msdnmag/issues/05/08/Concurrency/default.aspx を参照してください。
レイ トレーサの例
レイ トレーシングは、写実的なレンダリングを簡単に生成できる優れた方法です。ただし、この技法では、計算の作業負荷が非常に大きくなります。各レイを並列に計算できるので、レイ トレーシングはこのライブラリの優秀な候補といえます。ここでは、Luke Hoban が作成した既存のレイ トレーサ (
blogs.msdn.com/lukeh/archive/2007/04/03/a-ray-tracer-in-c-3-0.aspx を参照) を、TPL を使用して並列で実行できるように変更します。レイ トレーサは、
図 3 に示すような画像を生成し、Parallel FX CTP でサンプルとして使用できます。元のレイ トレーサのコア ループは、結果の画像のすべてのピクセルを反復処理します。
.gif)
図 3 並列レイ トレーサ (画像を拡大するには、ここをクリックします)
void Render(Scene scene, Color[,] rgb)
{
for (int y = 0; y < screenHeight; y++)
{
for (int x = 0; x < screenWidth; x++) {
rgb[x,y] = TraceRay(new Ray(scene,x,y));
}
}
}
各レイは個別に追跡できるため、元のコードを 1 行変更するだけで並列処理できます。
void Render(Scene scene, Color[,] rgb)
{
Parallel.For(0, screenHeight, delegate(int y)
{
for (int x = 0; x < screenWidth; x++) {
rgb[x,y] = TraceRay(new Ray(scene,x,y));
}
});
}
8 コアのコンピュータで、元のコードは、350x350 ピクセルの画像に対して毎秒 1.7 個のフレームを生成できます。一方、並列バージョンを同じ 8 コア プロセッサ コンピュータで実行すると、毎秒 12 個のフレームが生成されます。これは 8 コア プロセッサ コンピュータで 7 倍の処理速度です。若干の変更だけでこのようなすばらしい結果になります。1 秒あたり 12 個のフレームが生成される場合、床の上をはずむボールの滑らかなアニメーションを作成するのに十分な速さです。これは非常に単純なレイ トレーサであるため、さらに最適化してより滑らかなアニメーションを作成することもできます。
動的な作業配分
スレッド プールを使用してループを手動で並列処理する場合、開発者は最終的に作業を静的に分割することがよくあります。たとえば、レイ トレーサでは、画像が偶数のパーツに分割されることがよくあります。各パーツは別々のスレッドで処理されます。実際の作業負荷は不均等に分割される可能性があるため、一般的にこの方法は適切とはいえません。たとえば、反射を表現するために画像の下側の計算に 2 倍の時間がかかる場合、画像の上側を処理するスレッドは、そのほとんどの時間を下側のスレッドの完了を待機するのに費やします。作業が均等に分割された場合でも、同時に実行されているシステムでのページのエラーやその他のプロセスにより、この状況が発生する場合があります。
複数のプロセッサで適切に機能するために、TPL は Work-stealing (ワーク スティーリング) という方法を使用して動的に適応し、ワーカー スレッドに作業項目を配分します。既定では、ライブラリにはプロセッサごとに 1 つのワーカー スレッドを使用するタスク マネージャがあります。これにより、OS によって最小のスレッド切り替えが確実に行われます。各ワーカー スレッドは、実行する作業の独自のローカル タスク キューをそれぞれ持っています。各ワーカーは通常新しいタスクを独自のキューにプッシュし、タスクが実行されるたびに作業をポップします。そのローカル キューが空の場合、ワーカーは作業そのものを探して、他のワーカーのキューにある作業を "盗もう" とします。
この方法の利点は、作業キューが分散され、ほとんどの操作がワーカーにローカルであるため、ワーカー間で同期がほとんど行われないという点です。これはスケーラビリティの点で重要です。さらに Work-stealing には、実証された適切なキャッシュの局所性および作業配分プロパティがあります。たとえば、作業負荷が不均等である場合、1 つのワーカーが特定のタスクの実行に長時間かかる可能性がありますが、他のワーカーがそのキューから作業を盗むので、すべてのプロセッサは常にビジー状態になります。通常のアプリケーションでは、タスクにどのくらいの時間がかかるのかを予測するのが難しいため、動的な作業配分は重要です。これは、プロセッサを多くの異なるプロセスで共有したり、ワーカー スレッドが取得するタイム スライスを予測できないようなデスクトップ システムに特に当てはまります。
図 4 に、4 つのスレッドを使用するアクションでの動的な作業配分を示します。この図は 図 3 と同じレイ トレースの画像を示していますが、ここでは各ワーカー スレッドが異なる色を使用してそのピクセルを表示しています。ライブラリがワーカー スレッドに均等に作業を配分し、作業負荷に動的に適応しているのがわかります。
.gif)
図 4 ワーカー スレッドでの作業の配分 (画像を拡大するには、ここをクリックします)
動的な作業配分を実行するだけでなく、ライブラリはワーカーがブロックされた場合にワーカー スレッドの数を動的に調整します。操作をブロックする例として、ファイルの読み取り、キーが押されるまでの待機、ユーザー名の取得 (これによってドメイン上のネットワークにアクセスできるため) などがあります。タスクが知らないうちにブロックされると、同時実行レベルが低下するのに伴いパフォーマンスも低下することがあります (その場合でもプログラムは正しく動作します)。パフォーマンスを改善するために、ライブラリはワーカー スレッドがブロックされているかどうかを自動的に追跡して確認し、必要に応じて追加のワーカー スレッドを投入して同時実行レベルを維持します。操作がブロック解除されたら、スレッド切り替えの影響を軽減するために一部のワーカーを終了させることもできます。
集計
ドメインで反復処理を実行して値を 1 つの結果に集計するために for ループを使用することがよくあります。たとえば、100 未満の素数を合計する反復処理の例を次に示します。
int sum = 0;
for(int i = 0; i < 100; i++) {
if (isPrime(i)) sum += i;
}
あいにく、並列処理によってデータの競合が発生するためこのループは並列処理できません。各反復は、共有の sum 変数をロック保護を使用せずに変更します。2 つの同時反復が同時に sum の値を増やすと、それら両方がレジスタ内の同じ値を読み込み、追加し、それらの結果を書き戻す可能性があります。その結果 1 つの追加が失われます。次のようにロックを使用して追加を保護するのが正しい方法です。
int sum = 0;
Parallel.For(0, 100, delegate(int i) {
if (isPrime(i)) {
lock (this) { sum += i; }
}
});
ただし、すべての並列反復が同じロックと同じメモリの場所 (sum) の両方を取得しようとして競合が起こるため、パフォーマンス上の問題が発生します。そのため、各ワーカー スレッドでスレッド ローカルの sum を維持し、ループの最後でグローバルな sum のみに追加した方が良い結果になります。このパターンは Parallel.Aggregate 操作でキャプチャされるので、次のように書き換えることができます。
int sum = Parallel.Aggregate(0, 100, // iteration domain
0, // initial value
delegate(int i) { return (isPrime(i) ? i : 0) }, // apply
// on each element
delegate(int x, int y) { return x+y; } // combine results
);
集計操作では 5 つの引数を受け取ります。最初の 2 つの引数で、反復ドメインを指定します。これは列挙子にすることもできます。次の引数は、結果の初期値です。その後の 2 つの引数はデリゲート関数です。最初の関数は各要素に適用され、それ以外の関数は要素の結果を組み合わせるために使用されます。
ライブラリはスレッド ローカル変数を自動的に使用して、ロックを使用せずにスレッド ローカルの結果を計算します。ロックを使用するのは最後のスレッド ローカルの結果を組み合わせるときだけです。集計が並列処理される場合、要素は逐次集計とは異なる順序で組み合わされる可能性がある点に注意してください。したがって、デリゲート関数の組み合わせは関連するものにする必要があり、初期値は単位要素にする必要があります。
fork と join の並列実行
もう 1 つの一般的な並列パターンとして、fork と join の並列実行があります。例として、次の逐次クイックソート実装について考えてみましょう。
static void SeqQuickSort<T>(T[] domain, int lo, int hi) where T : IComparable<T>
{
if (hi - lo <= Threshold) InsertionSort(domain, lo, hi);
int pivot = Partition(domain, lo, hi);
SeqQuickSort(domain, lo, pivot - 1);
SeqQuickSort(domain, pivot + 1, hi);
}
このアルゴリズムは、要素型 T のジェネリックであり、必要なのは T インスタンスを比較できることだけです。特定のしきい値では、このアルゴリズムは挿入ソートに頼ることになります。挿入ソートを使用すると、少数の要素の場合にパフォーマンスが向上します。それ以外の場合は、入力配列を 2 つの部分に分割し、各部分を個別にクイックソートします。各並べ替えは配列のそれぞれ異なる部分で動作するため、これらの 2 つの並べ替えは並列で実行できます。これは、Parallel.Do メソッドを使用して簡単に表すことができます。
static void ParQuickSort<T>(T[] domain, int lo, int hi) where T : IComparable<T>
{
if (hi - lo <= Threshold) InsertionSort(domain, lo, hi);
int pivot = Partition(domain, lo, hi);
Parallel.Do(
delegate { ParQuickSort(domain, lo, pivot - 1); },
delegate { ParQuickSort(domain, pivot + 1, hi); }
);
}
Parallel.Do メソッドは、2 つ以上のデリゲートを引数として受け取り、それらを並列で実行する可能性のある静的メソッドです。クイックソートは再帰的であり、すべての呼び出しで追加の並列タスクが導入されるため、多くの並列処理が公開されます。また、ライブラリでは並列実行が保証されないため、ほとんどのタスクは実際には順番に実行されます。これは最適なパフォーマンスには欠かせない条件です。
タスクとフューチャ
これまでのすべての例は、並列コードのスコープがレキシカル スコープによって判断される構造化並列処理を示していましたが、すべての並列アルゴリズムがこの方法で表現できるわけではありません。さいわいなことに、ライブラリでも一般的な並列タスクがサポートされます。
class Task
{
Task( Action action );
void Wait();
void Cancel();
bool IsCompleted { get; }
...
}
潜在的に並列実行が可能な、関連付けられたアクションを指定してタスクを作成します。アクションは、タスクを作成してから最初に Wait メソッドを呼び出すまでのいずれかの時点で実行されます。関連付けられたアクションを別のスレッドで並列に実行することはできますが、アクションがスレッド間で移行されることはありません。これにより、プログラマは何の心配もせず、LeaveCriticalSecion を EnterCriticalSection と異なるスレッドで実行する場合など、Windows クリティカル セクションのようにスレッド アフィン変換の抽象化を使用できるので便利です。タスクが既に完了している場合は、Wait からすぐに制御が戻ります。
関連付けられたアクションで発生した例外はタスクに格納され、Wait が呼び出されるたびに繰り返し発生します。同様に、Parallel.For および Parallel.Do 関数はスローされたすべての例外を累積し、すべてのタスクの完了時に再度発生します。これにより、例外は失われることなく、依存対象に正しく伝達されます。
最後に、Cancel を呼び出して該当のタスクと関連付けられたアクションで作成されたすべてのタスク (子タスク) を取り消すことができます。取り消しは事前に準備されないため、実行中のタスクはライブラリに呼び戻すことで協調して作業を終了する必要があります。これは、たとえば新しいタスクを作成したり、Wait メソッドを呼び出したりすることで実行できます。親タスクが取り消されると、これらのライブラリの呼び出しによって (同期の) OperationCanceled 例外が発生し、アクションが停止します。
タスクは、作業項目が取り消しまたは待機が可能なハンドルを返し、例外が伝達される改善されたスレッド プールと見なすことができます。また、関連付けられたアクションによって結果が計算される、フューチャ (Future) と呼ばれるタスクのバリエーションもあります。
class Task<T> : Task
{
Task ( Func<T> function );
T Value { get; } // does an implicit wait
}
フューチャは、結果を計算するタスクであり、標準のアクションではなく結果を返すアクションで構築されます。この結果は、Func<T> 型のデリゲートになります。ここで T はフューチャ値の型を表します。
フューチャの結果は、Value プロパティを通じて取得されます。Value プロパティは Wait を内部で呼び出して、タスクが完了していること、および結果値が計算されていることを確認します。Wait が呼び出されているため、Value を呼び出すと値の計算中に発生した例外がスローされます。これを確認する 1 つの方法は、フューチャを計算で確定された値または例外値のいずれかを含むものとして考えることです。
フューチャは、MultiLisp で既に実装されている古い概念です。ただし、ここに示すフューチャの概念は、プログラマが共有メモリを正しくロックすることに責任を持つという点で "安全" ではありません。これは、フューチャのアクションがメモリ トランザクションに自動的にラップされるアプローチとは対照的です。
フューチャ抽象化は、ループほど構造化されていないシンボリック コードで適切に動作します。たとえば、次のバイナリ ツリー ノードとリーフの定義について考えてみましょう。
class Node : Tree {
int depth; // The depth of the tree
Tree left; // The left sub tree
Tree right; // The right sub tree
...
}
class Leaf : Tree {
int value; // values are stored in the leafs
...
}
この例では、リーフのすべての値を合計する仮想 Sum メソッドをツリーで定義するとします。リーフは単にその値を返します。ノードは、そのサブツリーの合計を追加します。
override int Sum() {
int l = left.Sum();
int r = right.Sum();
return (r + l);
}
この場合、各子の計算は互いに独立しているため、並列に実行できます。この例の並列処理はレキシカルにスコープが設定されており、Parallel.Do を使用することができますが、デモンストレーションのためにフューチャを使用します。
override int Sum()
{
Task<int> l = new Task<int>( left.Sum );
int r = right.Sum();
return (r + l.Value);
}
左側の各サブツリーに対して、int 型の新しいフューチャを作成し、デリゲートをコンストラクタ引数として渡します。この例では、左側の子 left.Sum の Sum メソッドを呼び出さずに渡します。右側のサブツリーの合計を計算して続行します。フューチャを作成することで、他のプロセッサは左側のサブツリーの合計の評価を並列に開始できます。最後に、Value プロパティを使用してフューチャの値を要求します。
タスクが別のワーカー スレッドによって既に計算済みの場合、この呼び出しによって結果の値がすぐに返されます。タスクが別のワーカー スレッドで実行中の場合は、結果が使用可能になるまでブロックします (ただし、同時実行レベルを維持するために別のワーカー スレッドがスケジュールされます)。
タスクが全く開始されないという非常に一般的なシナリオをもう 1 つ示します。この例では、Value を呼び出すと呼び出し元のスレッドでタスクが直接実行されます。これは、間接的なメソッドの呼び出しを行うだけなので、一般的で非常に効率が良い方法です。一方、OS が提供するシグナルを待機している場合、シグナルを発生させることは不可能で、唯一実行できる操作は呼び出し元のスレッドをブロックすることですが、これは一般的にパフォーマンスを低下させます。上記の例では、値の計算方法が明確であり、ライブラリはスレッドをブロックするのではなく、関連付けられたアクションを直接実行します。
リーフで実行される作業量は非常に小さいため、特定のツリーの深さで順番に合計処理を実行して各タスクで実行される作業のサイズを増やす方がよい場合があります。たとえば、逐次 Sum メソッドの SeqSum を使用する場合は、次のように記述できます。
override int Sum()
{
if (depth < 10) return SeqSum();
Task<int> l = new Task<int>( left.Sum );
int r = right.Sum();
return (r + l.Value);
}
一般的に、正しいしきい値制限は、タスクのアクションで実行される作業量とタスク オブジェクトを割り当てるコストとを比較して決定されます。経験から言うと、割り当ての負荷はかなり低く、しきい値の制限は通常約 100 の浮動小数点乗算になります。
フューチャは実際に優れた値であるため、フューチャを使用して 1 つのプログラムの論理的に区別された部分間に並列処理を導入できます。たとえば、別の異なるフェーズが実際にフューチャの値を要求するデータ構造にそれらのフューチャを保存できます。これに適するのは、ゲーム アプリケーションです。たとえば、1 つのフェーズですべてのキャラクタの新しい状態をフューチャとして計算でき、他のフェーズではそれらの状態のフューチャの値を後から使用します。マルチコア コンピュータでは、これらのフューチャは、各フェーズで実行されている作業と並列に計算できます。
複製可能タスク
ライブラリは、2 つの基本概念 (タスクと複製可能タスク) に基づきます。フューチャや並列 for ループなどの他の抽象化は、すべてこれら 2 つの基本概念の観点から表されます。これにより、操作は一貫したセマンティクスによって通常どおりに動作します。たとえば、例外は常に正しく伝達され、すべての抽象化は取り消すことができます (並列 for ループを含む)。
複製可能タスクは、実際には TPL が提供する標準の抽象化を拡張するライブラリ作成者向けであり、通常のコードで使う場合は慎重に使用する必要があります。複製可能タスクは、次のように通常のタスクから直接派生します。
class ReplicableTask : Task
{
ReplicableTask( Action action );
}
複製可能タスクは、同時に複数のスレッドによって自身を実行できるタスクを表し、作業の動的配分から抽出している間に、遍在的にすべてに適用される同時実行パターンをキャプチャします。コンストラクタは、別のスレッドで並列実行され、複数のスレッドによって同時に実行される可能性のあるアクション デリゲートを受け取ります。それらの実行のいずれかで例外が発生した場合は、いずれか 1 つの例外だけが格納され、Wait によって再びスローされます。
複製可能タスクを使用できるのは、他のスレッドが作業の実行に参加する可能性がある場合です。Parallel.For と Parallel.ForEach のすべてのバリエーションは、複製可能タスクを使用して実装されます。たとえば、基本的な Parallel.For を次のように単純に実装できます。
static void For( int from, int to, Action<int> body )
{
int index = from;
ReplicableTask rtask = new ReplicableTask( delegate {
int i;
while ((i = Interlocked.Increment(ref index)-1) < to) {
body(i);
}
});
rtask.Wait();
}
すべての複製可能タスクはインデックス変数を共有するため、複製可能タスクのコンストラクタに渡される実際のアクション デリゲートは、必要な数のスレッドによって実行できます。実装では、これを使用してアイドル状態のプロセッサを作業に参加させることができます。
この実装では、各ワーカー スレッドは一度に 1 つのインデックスを要求します。これは、OpenMP の dynamic(1) に対応し、通常各インデックスの作業負荷が大幅に異なる場合に適切に機能します (詳細については、
msdn.microsoft.com/msdnmag/issues/05/10/OpenMP を参照してください)。ただし各インデックスの作業負荷が小さい場合は、この方法によってキャッシュの競合が発生することがあります。その場合は、すぐにインデックスのストライドを処理することをお勧めします。OpenMP の dynamic(n) に対応し、ストライドを引数として受け取る次の Parallel.For を見てみましょう。
static void ForWithStride( int stride, int from, int to, Action<int> body )
{
int index = from;
if (stride <= 0) stride = 1;
ReplicableTask rtask = new ReplicableTask( delegate {
int i;
while ((i = Interlocked.Add(ref index,stride)-stride) < to) {
int end = Math.Min(i+stride, to);
do {
body(i);
i++;
}
while (i < end)
}
});
rtask.Wait();
}
複製可能タスクは、さまざまな並列反復法を実装するための強力な抽象化ですが、経験から言うと、標準の Parallel.For 実装および Foreach 実装は多くのシナリオで十分に機能するので、複製可能タスクの追加表現は実際にはそれほど必要にならないでしょう。
タスク マネージャ
タスク マネージャに属するすべてのタスクは、その名前が表すとおり、タスクを管理し、タスクを実行するワーカー スレッドを監視します。使用可能な既定のタスク マネージャは常に存在しますが、アプリケーションで明示的にタスク マネージャを作成することもできます。タスク マネージャのインターフェイスは次のように定義されます。
class TaskManager : IDisposable
{
TaskManager();
TaskManager( int maxConcurrentThreads );
static TaskManager Current { get; }
int MaxConcurrentThreads { get; }
...
}
class Task
{
Task( TaskManager taskManager, Action action )
...
}
タスク マネージャには、MaxConcurrentThreads プロパティから返される、関連付けられた同時実行レベルがあります。これにより、タスクを実行する理想的なスレッド数が常時マネージャに指定されます。これは単に手掛かりであるため、先の処理を行うために追加のスレッドを使用する必要がある場合、マネージャは動的にこの作業を行います。タスク マネージャを作成するときに、この数を明示的に指定できます。既定では、プロセッサの数と同じです。
一般的に、既定のタスク マネージャが常に使用できるため、タスク マネージャを明示的に作成する必要はありません。ただし、各タスク マネージャの同時実行レベルが異なる場合や、各タスク マネージャが別個のタスクのセットを処理する場合は、複数のタスク マネージャを使用することもあります。その場合は、新しいタスク マネージャを作成し、タスク マネージャを最初の引数として受け取る特殊な Task コンストラクタを使用して、そのタスクと、そのタスクマネージャのすべての子タスクを実行します。たとえば、次のコードについて考えてみましょう。
using (TaskManager tm = new TaskManager(2)) { // only use 2 worker
// threads for tasks
new Task( tm, delegate {
// tasks created in this delegate use the tm task manager by default
...
// finally, show some statistics
Console.WriteLine( "statistics: " + tm );
}).Wait();
}
タスク マネージャ インターフェイスのもう 1 つの重要な点は、単一のワーカー スレッドを使用してすべてのコードを順番に実行することです。つまり、すべてのタスクと並列 for ループは順番に実行されます。これは、マルチプロセッサ コンピュータで並列実行する前に、コードを順番に実行したときにコードが正しく機能するかどうかを確認できるので、デバッグ目的で使用すると非常に便利です。
Daan Leijen は、Microsoft Research の調査員です。彼が現在関心を持っているのは、宣言型と関数型のプログラミング、型推論システム、および並列コンピューティングです。
Judd Hall は、マイクロソフトのプログラム マネージャ II です。