パラダイム シフト
並列プログラミングの設計上の考慮事項
David Callahan
この記事は、Visual Studio ツールのプレリリース版を基にしています。ここに記載されているすべての情報は、変更される場合があります。
この記事では、次の内容について説明します。
- 並列コンピューティング
- 同時実行プログラミング
- パフォーマンスの向上
|
この記事では、次のテクノロジを使用しています。
マルチスレッド
|
目次
1986 年ごろから 2002 年にかけて、マイクロプロセッサの処理能力は年 52% の割合で向上しました。この驚くべきテクノロジの進化は、ムーアの法則どおりの継続的なトランジスタのコスト低下と、プロセッサ ベンダの優れたエンジニアリングという 2 つの要素のたまものです。この組み合わせのことを、マイクロソフトの研究員 Jim Larus は "ムーアの配当" と呼んでいます。彼は、この "ムーアの配当" が、今日のソフトウェア産業の誕生およびコンピュータの普及に果たした役割について考察しています (
go.microsoft.com/fwlink/?LinkId=124628 を参照)。
ソフトウェアを開発する側では、この状況を "フリー ランチ (無料で支給される昼食)" と呼んでいます。ハードウェアをアップグレードするだけでアプリケーションのパフォーマンスが向上するからです (このテーマの詳細については、
ddj.com/184405990 で公開されている「A Fundamental Turn Toward Concurrency in Software (ソフトウェアにおける同時実行への大きな転換)」を参照してください)。
ただし、このモデルは変化しつつあり、近ごろはプロセッサを追加することによってパフォーマンスの改善が図られています。いわゆるマルチコア システムが広く使用されるようになりました。もちろん、マルチコアのアプローチでパフォーマンスを向上させるには、複数のアクティビティを同時に実行できるソフトウェアが必要です。そこで、逐次処理の手法で問題なく動作する機能も、複数のプロセッサを使用して実行できるように記述する必要があります (ただし、マルチプロセッサ コンピュータで実行した場合にパフォーマンスの向上が見込める場合)。
同時実行と並列処理
随分以前から、プログラマは並列処理 (同時実行) に関連するプログラミング上の課題に取り組まざるを得なくなっています。応答性を維持するため、入力イベントに応答するスレッドから待ち時間の長いアクティビティをオフロードする手段が必要だったからです。かつては、オフロード対象のアクティビティのほとんどがファイル入出力に関係するものでした。ところが最近は、Web サービスとの対話に関係するアクティビティであるケースがますます増えてきています。
この一般的なプログラミング上の懸念を解消するため、Microsoft .NET Framework には、非同期プログラミング モデルとバックグラウンド ワーカーの概念が用意されています。並列プログラミングにおける複雑な処理の多くについて、同時実行プログラミングにも類似の処理が存在しますが、その基本的なパターンと目的は異なります。マルチコア プロセッサを導入しても、同時実行プログラミングの必要性が抑えられるわけではありません。むしろ、その目的はパフォーマンスの向上にあり、システムで実行されるバックグラウンド アクティビティとその他の計算を最適化する手法として使用できます。
また、同時実行の手法が取り入れられている身近な例として、サーバー アプリケーションがあります。Web サーバーなどのアプリケーションには、独立した要求のストリームが渡されます。各プログラムでは、多数の要求を同時に実行してシステムのスループットを向上させるために、通常、要求ごとに個別のスレッドを使用します。ただし、それぞれの要求は逐次処理されます。結果として、1 秒あたりに処理できる要求の数は増えますが、個別の要求の待ち時間 (要求ごとの秒数) は改善されません。
これらのアプリケーションも、"フリー ランチ" の恩恵に浴してきました。マルチコア処理によって追加のコストが抑えられ、スループットが向上するため、しばらくはその状態が続くでしょう。とはいえ、サーバー環境においても、待ち時間の影響を大きく受ける要求のパフォーマンスを許容範囲まで引き上げるために、ゆくゆくは並列プログラミングの手法を使用しなければならなくなるはずです。
ご存知のとおり、同時実行プログラミングは専門家にとっても難しい手法です。論理的に独立した要求がさまざまなリソース (ディクショナリ、バッファ プール、データベース接続など) を共有する場合、プログラマはその調整を行う必要がありますが、その際に新たな問題が生じます。これらの問題 (データ競合、デッドロック、ライブロックなど) は、通常、同時実行タスクがプログラムの同じデータ オブジェクトを操作しようとしたときに生じるさまざまな不確定動作に起因しています。Rahul Patil と Boby George による最近の記事「同時実行の問題を特定するためのツールと手法」(MSDN Magazine 2008 年 6 月号、
msdn.microsoft.com/magazine/cc546569) で述べられているように、これらの問題が原因で、テストやデバッグなどの基本的なソフトウェア開発作業はきわめて難しくなります。
並列プログラミングが同時実行プログラミングと異なるのは、論理的には単一のタスクであるもの (これは、すべての主要な言語でサポートされている一般的な逐次構造体を使用して表現できます) を利用して同時実行の機会を確保する必要があるという点です (このような機会を確保するためのさまざまなアプローチについては、この記事の後半で説明します)。ただし、同時実行の機会がデータ オブジェクトを共有するサブタスクと共に得られた場合は、ロックと競合に注意する必要があります。したがって、並列プログラミングにおいては、逐次プログラムに伴う正確性とセキュリティの課題に加えて、並列処理と共有リソースへの同時アクセスに伴う難しい課題に対処しなければなりません。
追加の概念、新たなエラー処理、テストの難しさが組み合わさると、どんな開発者も尻込みしてしまいます。開発者は本当にこのようなものを求めているのでしょうか。答えは明らかにノーです。しかし、必要なパフォーマンスを確保するために、多くの開発者がこの泥沼にはまり込む羽目になります。マイクロソフトは主要な問題の一部に対処できるソリューションの開発に努めていますが、生産性の高いソリューション セットはまだ完成していません。
昨年、マイクロソフトは、並列プログラムの作成方法と効率的な実行方法を示すと共に、ムーアの配当を顧客への価値に転換できる次世代アプリケーションの作成を奨励するために、並列コンピューティング イニシアティブ (
go.microsoft.com/fwlink/?LinkId=124050) を発表しました。並列処理の考え方については、後ほど検討します。今月号に掲載されている Stephen Toub と Hazim Shafi の記事「
次期バージョンの Visual Studio で強化される並列処理のサポート」では、これらのアプローチをサポートするためにマイクロソフトが提供しているライブラリとツールの一部が紹介されています。同じく今月号の Joe Duffy の記事「
マルチスレッド コードでよく見られる 11 の問題を解決する」では、同時実行アプリケーションの安全性を高めるための手法とアプローチについて説明されています。
先ほど "同時実行の機会" というフレーズを使いましたが、これは、並列プログラミングと同時実行プログラミングの違いをさらに明確にするものです。開発者が非同期プログラミング パターンやバックグラウンド ワーカーを使用する場合、またはサーバーで同時要求を処理する場合、すべてのスレッドによる処理が進行することを想定しています。オペレーティング システムのスケジューラは、すべてのスレッドによってリソースが公平に共有されるようにします。ただし、これは並列プログラミングにおいては役に立ちません。特に、新しいハードウェア システムに合わせて拡張できるアプリケーションを開発する場合には、適切な動作とは言えません。
"フリー ランチ" の恩恵に浴する (つまり、ハードウェアをアップグレードするだけでソフトウェアのパフォーマンス向上を達成する) には、将来にわたって利用できるような方法で並列処理の機会を提供する必要があります。並列処理の実装におけるこのようなシフトと、それに対する筆者の考え方 (筆者は、並列プログラミングに取り組む開発者は、問題をこれまでよりもずっと多くのタスクに切り分ける必要があると考えています) を強調するため、この記事では、"スレッド" の代わりに "タスク" という用語を使用します。
並列プログラミング システムの実装では、必要に応じて、それらのタスクをシステム スレッドとプロセッサにマッピングしなければなりません。並列プログラムを効率的に実行するためにシステム リソースをオペレーティング システムから取得し、プロセス内で管理する方法は、根本から異なっています。これに気が付くのは、ごくわずかなプログラマだけです。これはスレッド プールの強化版のようなものですが、並列プログラムによって指定されたとおりに単純にスレッドを管理することではなく、アプリケーションにおける並列処理の機会を現在のハードウェアで使用できるリソースと一致させることに重きが置かれています。
同時実行プログラミング (特にサーバー関連のプログラミング) における問題のほとんどは、実行時間の長いスレッドによる共有変数へのアクセスをロックなどのツールを使用して調整する際に生じます。タスクを利用する並列プログラミングにシフトすると、新しい概念を使用できるようになります。この概念は、"タスク A の後に実行されるタスク B" という処理の流れと、コーディネーション プリミティブを用いて説明できます。この概念によって、プログラマは作業のスケジュールについて考えることができるようになります。通常、このスケジュールは、プログラムのアルゴリズム構造に必然的に合致し、並列プログラミングの抽象化の構造化された使用に基づきます。プログラムの抽象化と並列アルゴリズムが適合していれば、従来の同時実行メカニズム (ロックやイベントなど) の必要性が大幅に減り、同時実行プログラムに伴う多くのリスクを (完全に取り除くことはできませんが) 回避することができます。
次に、並列プログラミングに対するいくつかの主要なアプローチについて説明し、その利用方法を開発中の抽象化を通じて解説します。特に、C++ PPL (Parallel Pattern Library) と C# を使用した Parallel Extensions to .NET (
go.microsoft.com/fwlink/?LinkId=124621 からダウンロード可能) を取り上げます。
構造化マルチスレッド
私たちが最も頻繁に利用する問題解決パターンは、分割統治です。分割統治とは、大きな問題を明確なやり取りを通じて小さな問題に分割し、個別に対処してから、その結果を組み合わせて元の問題を解決する手法です。この手法は、大企業の事業から、近所の一品持ち寄りパーティーに至るまで、さまざまな場面の問題を解決するために使用されています。もちろん、この考え方を再帰的に適用したものが並列プログラミングの基盤にもなっています。
構造化マルチスレッドとは、ブロック構造化された主要な逐次実行ステートメントを並列化したものを提供することを意味します。具体的には、"A が評価されてから B が評価される" というセマンティクスを持つ逐次実行型の複合ステートメント { A; B; } を、A と B を同時に評価できるようにすることによって、並列ステートメント化するような場合を言います。ただし、この場合は構造体全体の処理は完了しません。両方のサブタスクが終了するまでは、制御が次の構造体に移ります。これは古くからある概念で、これまで並列実行 (cobegin) ステートメントとして教えられてきました。構造を強調するために、"fork と join の並列実行" と呼ばれることもあります。この基本的な考え方は、各反復処理によって、タスクを他のすべての反復処理と同時に評価できるように定義されるループにも当てはめることができます。このような並列ループが完了するのは、すべての反復タスクが完了したときです。
分割統治の概念の身近な例が、有名なクイック ソート アルゴリズムです。ここでは、このアルゴリズムの単純な並列処理について、C++ 構造体を使用して説明します。この基本的なアルゴリズムは、データの配列を受け取り、最初の要素を基準として使用します。そしてデータを 2 つに分け、基準値よりも小さい値が前に、基準値よりも大きい値が後にくるように配列を変更します。さらに、この処理を再帰的に行ってデータを並べ替えます。対象データが少なくなると、オーバーヘッドを抑えるために、この処理を中止して挿入ソートなどの非再帰アルゴリズムが使用される場合もあります。
図 1 に、マイクロソフトで開発中の 2 つの機能を示します。図中の最初の機能は、新しい C++ ラムダ構文です。これを使用することで、式またはステートメント リストを関数オブジェクトとして非常に簡単にキャプチャできます。次の構文は、呼び出されたときに中かっこ内のコードを評価する関数オブジェクトを作成します。
[=] { ParQuickSort(data, mid); }
図 1 クイック ソート
// C++ using the Parallel Pattern Library
template<class T>
void ParQuickSort(T * data, int length, T* scratch) {
if(length < Threshold) InsertionSort(data,length)
else {
int mid = ParPartition(data[0], data,
length, scratch, /*inplace*/true);
parallel_invoke(
[=] { ParQuickSort(data, mid); },
[=] { ParQuickSort(data+mid, length-mid); });
}
}
先頭の [=] でラムダ式であることを示すと共に、式で参照される外のスコープの変数をオブジェクトにコピーし、ラムダ式本体のそれらの変数への参照でそれらのコピーを参照するように指定しています。
parallel_invoke はテンプレート アルゴリズムです。この場合は、2 つの関数オブジェクトを受け取り、それぞれを個別のタスクとして評価することで、それらのタスクを同時に実行できるようにしています。両方のタスクが完了すると (この場合は両方の再帰的並べ替えが完了すると)、parallel_invoke が値を返し、並べ替えが完了します。
この例の並列処理は、分割統治型並列処理の再帰的な適用に基づいています。各レベルで生成される子タスクは 2 つだけですが、計算の末端に近づくにつれ、並べ替えているデータのサイズに比例して多数のタスクが生成されるようになります。このコードは同時実行のすべてを表しています。このようなプログラムは、より大きな問題に対処する必要が生じた場合や、コアの数が増加した場合に、直ちに拡張することができます。ただし、問題の規模が一定であっても、オーバーヘッドの生じる実際のコンピュータには、スケーラビリティの制限が必ず存在します。これは、有名なアムダールの法則の結果です。そこで、こうしたオーバーヘッドを継続的に削減することが、プラットフォーム ベンダのエンジニアリング上の重要な目標となります。これは、システムが変わると、Threshold (図 1 を参照) のような値の選択が難しくなる場合があることと、時間の経過と共に予測がさらに困難になる可能性があることを示しています。これらのプログラムは、過剰なオーバーヘッドが生じないように十分大きくなければなりませんが、将来の拡張の妨げとならない程度にしておく必要もあります。
このテンプレート アルゴリズムは、今月号の Stephen Toub と Hazim Shafi の記事で紹介されている PPL に含まれています。PPL には、parallel_invoke に加えて、標準テンプレート ライブラリ (STL) の for_each に似た parallel_for_each も用意されています。parallel_for_each の場合、すべての反復処理が他の反復タスクと同時に実行できる個別のタスクとなり、すべての反復タスクが完了すると、parallel_for_each が値を返します。また、共通のタスク グループに関連付けられている個別のタスクを作成し、それらすべてが完了するのを待機する、それほど構造化されていない手法も利用できます。これは Cilk 生成プリミティブ (supertech.csail.mit.edu/cilk) と同様の基本的な機能を提供しますが、標準的な C++ 機能に基づいて構築されています。
並列ループは、レイトレーシングの問題を処理するためのコードで使用されることがあります。このような問題は各出力ピクセルで並列的であり、図 2 のようなコードでキャプチャできます。これは、Parallel Extensions to .NET の Parallel.For メソッドを使用して表したものです。Parallel Extensions to .NET には、C++ 開発者向けの PPL でサポートされているパターンと同様の、マネージ開発者向けの基本的なパターンが含まれています。ここでは、入れ子になったシンプルなループを使用して、長方形の画面上の各ピクセルに対応するタスクの空間を説明します。このコードは、ループ本体で呼び出されるさまざまなメソッドが同時実行に対して安全であることを前提にしています。
図 2 並列ループ
// C# using Parallel Extensions to the .NET Framework
public void RenderParallel(Scene scene, Int32[] rgb)
{
Parallel.For(0, screenHeight, y =>
{
Parallel.For (0, screenWidth, x =>
{
Color color = TraceRay(new Ray(camera.Pos,
GetPoint(x, y, scene.Camera)), scene, 0);
rgb[x + y*screenWidth] = color.ToInt32();
});
});
}
同時実行の安全性に関する Joe Duffy の記事をもう一度参照してください。並列プログラミングの黎明期には、開発者はこうした懸念事項に頭を悩ませることになります。用心を怠らないようにしてください。
構造化マルチスレッドは、データ構造が自然な場合 (再帰的な構造をしていることが少なく、不規則な構造をしていることはほとんどない場合) の並列処理の操作に最適です。並列処理はこうした構造を反映できます。また、問題の至る所にデータ フローがある場合にも対応可能です。次の例では、グラフを位相的順序でトラバースすることで、すべての先行要素が見つかるまではノードに到達しないようにしています。各ノードには、先行要素の数に初期化されるカウント フィールドがあります。ノードに到達すると、後続要素の数がデクリメントされます (複数の先行タスクがこの操作を同時に実行しようとすることがあるため、安全性を確保しておいてください)。カウントがゼロになったら、そのノードに到達できます。
// C++
void topsort(Graph * g, void (*action)(Node*)) {
g->forall_nodes([=] (Node *n) {
n->count = n->num_predecessors();
n->root = (n->count == 0);
});
g->forall_nodes([=] (Node *n) {
if(n->root) visit(n, action);
});
}
ここでは、関数オブジェクトによってパラメータ化されるメソッドをグラフがエクスポートすることを想定しています。このメソッドは、グラフ内のすべてのノードを並列でトラバースし、関数を適用します。その関数は、PPL を内部で使用してその同時実行を実装します。この場合、次の 2 段階の処理を行います。まず、先行要素をカウントし、ルート ノードを特定します。次に、各ルートから深さ優先の検索を開始します。この検索で後続要素の数がデクリメントされ、最終的に後続要素に到達します。その関数は図 3 のようになります。
図 3 深さ優先の検索
// C++ using the Parallel Pattern Library
// Assumes all predecessors have been visited.
void visit(Node *n, void (*action)(Node*)) {
(*action)(n);
// assume n->successors is some kind of STL container
parallel_for_each(n->successors.begin(),
n->successors.end(),
[=](Node *s) {
if(atomic_decrement(s->count) == 0) // safely does "-- s->count"
visit(s, action);
});
}
parallel_for_each メソッドは、後続要素の一覧をトラバースし、関数オブジェクトをそれぞれに適用し、それらの操作を並列に実行できるようにします。ここには、同時アクセスを調整するための方法を使用する atomic_decrement 関数は示されていません。ここで、こうした新しい並列アルゴリズムにも、従来からある同時実行に関する問題が忍び寄ってくることにお気付きになるでしょう。これらの問題は、レイトレーシングの例のように、要素の操作が複雑化するに従っていっそう厄介になります。
このアルゴリズムの構造では、"action" にそのパラメータへの排他アクセスが与えられるので、アクションがそれらのフィールドを更新する場合に追加のロックは必要ありません。また、すべての先行要素が既に更新されており、変更中ではないことと、後続要素は更新されておらず、このアクションが完了するまでは変更されないことが保証されます。適切な並列アルゴリズムを構築するには、どの状態が安定しており、どの状態が同時に更新される可能性があるかを推測する能力が欠かせません。
構造化マルチスレッドの場合、並列処理の機会 (部分的に順序付けられている計算の機会も含む) を簡単に表現できます。作業をワーカー スレッドにマッピングするための多数のメカニズムによって、基本的なアルゴリズムがわかりにくくなることはありません。これが構造化マルチスレッドの強みです。こうした特徴により、ここで紹介した強力な構成モードが実現されます。この構成モードでは、データ構造でいくつかの基本的な並列トラバーサル メソッド (Graph::forall_nodes など) を提供できます。これらのメソッドは、より高度な並列アルゴリズムを構築する際に再利用可能です。さらに、並列処理を完全に記述する方が、2 つまたは 4 つのプロセッサに十分な量を模索するよりも簡単です。そのうえ、来年のコンピュータには 8 つのプロセッサが搭載される可能性がありますが、それに合わせて自然に拡張できるようになります。これこそ "フリー ランチ" の恩恵です。
データ並列処理
データ並列処理とは、データの集計に対する一般的な操作を応用したものです。新しい集計データを生成したり、集計をスカラ値まで減らしたりするために使用されます。並列処理では、同じ論理操作を周囲の要素から独立した各要素に対して実行します。集計操作をさまざまなレベルでサポートしている言語は数多くありますが、最も成功を収めているのは、データベースで使用される SQL です。LINQ は、C# と Visual Basic の両方で SQL スタイルの演算子を直接サポートしており、LINQ で表現されたクエリを ADO.NET などのデータ プロバイダに渡したり、オブジェクトのメモリ内コレクションや XML ドキュメントに対して評価したりできます。
Parallel Extensions to .NET の一部は、クエリの並列評価を含む LINQ to Objects と LINQ to XML の実装です。この実装は PLINQ と呼ばれます。これを使用すると、データの集計を簡単に操作できます。次の例は、統計的クラスタリングのための標準的な K-means アルゴリズムの中心概念を示しています。各ステップにおいて、領域内にクラスタ中心の候補である K 個のポイントが存在します。すべてのポイントを最も近いクラスタにマッピングし、クラスタ内のポイント (同じクラスタにマッピングされているすべてのポイント) の位置の平均を計算することで、そのクラスタの中心を再計算します。この計算は、収束条件が満たされるまで、つまりクラスタ中心の位置が安定するまで繰り返されます。図 4 に示すように、このアルゴリズム記述の重要なループは、PLINQ にかなり直接的に変換されています。
図 4 中心を探す
// C# using PLINQ
var q = from p in points.AsParallel()
let center = nearestCenter(p, clusters)
// "index" of nearest cluster to p
group p by center into g
select new
{
index = g.Key,
count = g.Count(),
position = g.Aggregate(new Vector(0, 0, 0),
(accumulated, element) => accumulated + element,
(accumulated1, accumulated2) =>
accumulated1 + accumulated2,
(accumulated) => accumulated
) / g.Count()
};
var newclusters = q.ToList();
LINQ と PLINQ の違いは、データ コレクション ポイントの AsParallel メソッドにあります。この例は、LINQ にはマッピングを減らす重要なパターンが含まれていること、また、主流言語に完全に統合されていることも示しています。この例で難しいポイントの 1 つが、Aggregate 演算子の動作です。3 番目のパラメータは、部分和を結合するためのメカニズムを提供するデリゲートです。このメソッドが提供されると、チャンクへの入力をブロックし、各チャンクを並列的に減らしてから、部分ごとの結果を結合することで、実装が並列的に行われます。
データ並列処理には大きな強みがあります。それは、データ構造の想定が複雑化することのある構造化マルチスレッドのアプローチを適用した場合に比べて、通常は、適切なアルゴリズムをはるかに簡潔かつ読みやすい形で表現できるという特徴です。また、より抽象的な記述を行うことでシステムを最適化する機会が得られます (同じ方法を手動で行うとアルゴリズムが完全に不明確になります)。さらに、こうした高レベルの表現によって、実行対象 (マルチコア CPU、GPU、またはクラスタへのスケールアウト) と共に優れた柔軟性が提供されます。また、nearestCenter などのリーフ関数を使用する限り副作用がなく、スレッド指向プログラミングに伴うデータ競合やデッドロックなどの問題に一切悩まされずに済みます。
並列処理を活用するためによく使用されるのが、パイプライン処理を使用する手法です。このモデルでは、データ アイテムがパイプラインのさまざまなステージ間を移動し、各ステージで検証および変換されてから次のステージに渡されます。データ値にグラフのノード間を移動させ、入力データを使用できるかどうかに基づいて計算をトリガするというアイデアを一般化したものが、データ フローです。各ノードを同時に実行するか、1 つのノードを異なる入力データに対して複数回アクティブ化することで、並列処理が行われます。
Parallel Extensions to .NET は、個別のタスク (Task 型) を明示的に作成し (これは、構造化マルチタスクを実装するための基本的なメカニズムです)、最初のタスクの完了時に実行が開始された 2 番目のタスクを特定する機能をサポートしています。フューチャの概念は、命令型プログラミングの世界とデータ フロー型プログラミングの世界をつなぐものとして利用されています。フューチャは、計算によって最終的に生成される値の名前です。このような区別があるため、値が判明する前にその値の処理方法を定義することができるのです。
フューチャの continueWith メソッドは、タスク (フューチャ値を使用できる場合に実行されるタスク) を作成するために使用されるデリゲートによってパラメータ化されます。continueWith の呼び出しの結果は、デリゲート パラメータの結果を識別する新しいフューチャです。命令型プログラミングでは、タスクの評価を通じて副作用が調べられることが多いため、continueWith は Task のメソッドとしても使用できます。
このスタイルの例として、Strassen 行列乗算アルゴリズムにおける並列処理について考えてみます。これは、基本的な行列乗算アルゴリズムのブロック指向バージョンです。2 つの入力行列はそれぞれ 4 つのサブブロックに分割され、その後、出力行列のサブブロックを作成するために代数的に結合されます (詳細については、Strassen アルゴリズムに関する Wikipedia の記事 (
wikipedia.org/wiki/Strassen_algorithm) を参照してください)。
これらのタスクの 1 つは、次のようになります。
// C# using Parallel Extensions to the .NET Framework
var m1 = Future.StartNew(() => (A(1,1)+B(1,1))*(A(2,2)+B(2,2));
計算がわかりやすいように、コードの代わりにデリゲート内部で数学的な表記を使用しました。A と B は入力行列を、A(1,1) は行列 A の左上のサブブロックを表します。加算には行列で一般的な方法を、乗算には Strassen アルゴリズムを再帰的に適用する方法を使用しています。出力は、この式の結果に相当する一時的な行列です。
最初の 7 つのサブタスクは独立していますが、最後の 4 つは入力として使用される最初の 7 つのサブタスクに依存しています。基本的なデータ フローのグラフは、図 5 のようになります。このとき、タスク c11 は、タスク m2 およびタスク m3 の結果に依存しています。入力を使用できる場合にそのタスクを実行できるようにしてみましょう。C# では、これを次のように表現できます。
var c11 = Task.ContinueWhenAll(delegate { ... }, m2, m3);
.gif)
図 5 サブタスク (クリックすると拡大画像が表示されます)
これは、中粒度のデータ フローと呼ばれるデータ フローを表しています。各演算が単一の算術演算ということもあり得る細粒度のデータ フローとは対照的に、中粒度のデータ フローでは、数百から数千の演算が計算の単位となります。"when all (すべての...が...したとき)" および "when any (いずれかの...が...したとき)" という概念を処理できるいくつかの便利なメソッドを使用するとそのコードがわかりやすくなりますが、Stephen Toub のブログ記事 (
blogs.msdn.com/pfxteam/archive/2008/07/23/8768673.aspx を参照) で説明されているように、これらのメソッドは基本的なメカニズムに基づいて実装することができます。
筆者は、構造化マルチスレッドの場合と同じように、並列処理の機会を特定しました。シングル プロセッサしかない場合は、サブタスクは作成順に逐次実行するとよいでしょう。ただし、追加リソースがある場合は、サブタスク間の実行順序の制約をキャプチャしておくことで、追加リソースのメリットを享受するチャンスが生まれます。構造化マルチスレッドの場合とは異なり、基本的に 1 つのタスクがデータ フロー グラフを列挙できるようにし、個々のサブタスクがその結果の使用方法と結合方法に関知しないようにしておくと便利です。これは、並列アルゴリズムの処理に対する一般的なメカニズムの別の面です。
アプリケーションに流れ込んだデータを、そのフロー中に処理しなければならないことはよくあります。この場合、データが移動するパスはかなり安定しています。そこで、タスクを他のタスクの完了に関連付けずに、次のデータ アイテムの可用性と関連付けることをお勧めします。このモデルは、異なるレートで受信したセンサ データのストリームが合流する地点でアルゴリズムによる決定が行われる、ロボット工学の特定の領域で特に役立ちます。
Microsoft Robotics SDK (
go.microsoft.com/fwlink/?LinkId=124622) はこのアプローチを採用しており、その中核となる概念には、データのストリーム (ポートと呼ばれます) と、データ (メッセージ) の着信時にアクティブ化されるタスクのバインドが含まれています。当然のことながら、今ここで考察しているのは、マルチコアへのシフトではなく Web サーバーなどへのシフトに起因する問題です。Web サーバーの重要な特徴は同時実行です。これには、アプリケーションのアーキテクチャ全体の一部分として対処しなければなりません。同様の懸念事項は、ロボット工学の領域に含まれていない分散アプリケーションにも当てはまりますが、ここでの話題には直接関係ありません。
ストリーミング並列処理
複数のコアだけでなく、複数層のメモリ階層 (レジスタ、1 つ以上のレベルのオンチップ キャッシュ、DRAM メモリ、およびディスクに対するデマンド ページング) もコンピュータ アーキテクチャの重要な特徴です。さいわいなことに、ほとんどのプログラマは、システム アーキテクチャのこの側面についてはあまり詳しくありません (少なくとも関心を払っていません)。作成するプログラムがそれほど大きくなく、ほとんどのメモリ参照がすぐに返されるキャッシュにそれらが十分収まるためです。ただし、データ値がオンチップ キャッシュに含まれていない場合、そのデータ値を DRAM から取得するのに数百サイクル費やしてしまうことがあります。このデータを提供する際の遅延により、プロセッサがデータを長時間待機するため、プログラムの実行速度が低下しているように見えます。
一部のプロセッサ アーキテクチャは、物理的な処理コアごとに複数の論理プロセッサをサポートしています。これは一般に (ハードウェア) マルチスレッドと呼ばれ、その一部が主流のプロセッサで使用されてきました (たとえば、Intel では一部の製品でこれをハイパースレッドと呼んでいます)。マルチスレッドの目的は、メモリ アクセスの遅延を許容することにあります。マルチスレッドの場合、ある論理ハードウェア スレッドがメモリで待機しているときに、他のハードウェア スレッドから命令を出すことができます。この手法は現在の GPU にも取り入れられていますが、CPU の場合と比べて、より積極的に使用されています。
処理コアの数が増加すると、メモリ システム上でより多くの要求を行うことができるようになるため、帯域幅の制限などの新たな問題が発生します。プロセッサが 1 秒あたりに DRAM メモリとの間で実行できる転送処理は限られています。この制限に達した場合、並列処理をそれ以上使用しても効果はありません。単に追加のスレッドが追加のメモリ要求を生成し、その要求はキューの最後尾に登録され、メモリ コントローラによる処理を待機することになります。通常、GPU はより高い総帯域幅 (ギガバイト/秒で測定) をサポートするメモリ サブシステムを備えています。GPU ははるかに多くの並列処理をサポートしており (また、実際に実装するものと思われます)、帯域幅を追加することでパフォーマンスの向上を期待できるためです。
現在のマルチコア チップ アーキテクチャでは、メモリ帯域幅を広げるよりもコアの数を増やす方が簡単です。したがって、データ セットがメモリに収まらない事態に対処する場合は、メモリ階層の使用を検討することが重要です。こうした不均衡を解消するために活用できるのが、ストリーム処理と呼ばれるプログラミング スタイルです。このプログラミング スタイルでは、データ ブロックをオンチップ キャッシュ (またはプライベート メモリ) に展開し、そのデータに対してできるだけ多くの操作を実行してから次のブロックに置き換えます。それらの操作は、複数のコアを使用して内部で並列的に処理されるか、または、データ フロー スタイルでパイプライン処理されますが、重要なのは、データがキャッシュ内にある間に最大限の作業を行うことです。
専用言語を使用することで、ストリーミング アルゴリズムを指定し、その実行を綿密に計画できるようにする案もありましたが、多くの場合、慎重なスケジューリングでもこれを実現することができます。たとえば、この手法は QuickSort の例に適用できます。並べ替えるデータ セットのサイズが大きすぎてキャッシュに収まらない場合、単純な Work-stealing (ワーク スティーリング) のアプローチでは、最も大きく粒度が粗い下位の問題を異なるコアに分けてスケジュールする傾向にあります。コアでは独立したデータ セットを処理し、共有オンチップ キャッシュは活用しません。
ただし、アルゴリズムを変更してキャッシュに収まるデータ セットにのみ並列処理を行うようにすると、図 6 に示すように、ストリーミングのメリットを得ることができます。この例でも大きな問題をより小さな問題に分割していますが (また、分割ステップで並列処理を使用しています)、下位の問題が両方同時にキャッシュに収まらない場合は逐次実行します。つまり、キャッシュに小さなデータ セットが配置された場合、そのデータ セットがキャッシュ内にある間に使用可能なすべてのリソースを使って完全に並べ替え、メモリには渡しません。並べ替えが終わってから、次のデータ セットの処理を開始します。
図 6 より小さなデータ セットでの並列処理の使用
// C++ using the Parallel Pattern Library
template<class T>
void ParQuickSort(T * data, int length, T* scratch, int cache_size) {
if(length < Threshold) InsertionSort(data,length)
else {
int mid = ParPartition(data[0], data,
length, scratch, /*inplace*/true);
if(sizeof(*data)*length < cache_size)
parallel_invoke(
[=]{ ParQuickSort(data, mid, cache_size); },
[=]{ ParQuickSort(data+mid, length-mid, cache_size);});
else {
ParQuickSort(data, mid, cache_size);
ParQuickSort(data+mid, length-mid, cache_size);
}
}
}
このコードは、キャッシュのサイズで明示的にパラメータ化する必要がありました。これは実装固有の特徴です。これは好ましくない特徴ですが、計算でシステムを他のジョブまたは同じジョブ内の他のタスクと共有している場合には問題になります。これは、複雑な並列システムのパフォーマンスを引き出す際の難しさの一部を如実に表しています。すべての問題にこうした厄介な点があるわけではありません。しかし、マルチコア チップでのパフォーマンスを向上させるためには、開発者は、一部のケースにおける並列処理とメモリ階層の相互作用を十分に考慮する必要があります。
単一のプログラム、複数のデータ
高パフォーマンス コンピューティングの領域では、1980 年代に行われた数多くの取り組みをベースに、技術および科学の分野のアプリケーションで並列処理が使用されてきました。問題の種類はデータの配列に対する並列ループに依存します。このとき、一般にループ本体のコード構造はかなり単純です。
その例として、前述のレイトレーシング フラグメントが挙げられます。登場した主流の並列処理モデルは、"単一のプログラム、複数のデータ" と呼ばれました。これはよく SPMD と略されます。この用語は、Michael Flynn によるコンピュータ アーキテクチャの古典的な分類 ("単一の命令、複数のデータ (SIMD)"、"複数の命令、複数のデータ (MIMD)" など) が基になっています。このモデルでは、プログラマは、単一の問題に論理的に関与するが作業を共有するプロセッサのセットとして各プロセッサ (ワーカー、スレッド) をとらえて、その動作について考えます。一般に、作業とは、配列の異なる部分を処理する独立したループの反復のことを表します。
SPMD スタイルにおける作業の共有の概念は、C、C++、および Fortran に対する拡張セットである OpenMP (
openmp.org) の心臓部です。OpenMP の中核概念は、アクティビティの単一のスレッドがスレッドのグループにフォークし、それらが協調して共有ループを実行する並列領域です。このグループを調整するためにバリア同期メカニズムが使用され、グループ全体をループの入れ子から次のループの入れ子に移動させることで、グループのメンバよるデータ値の計算が終わる前にそのデータ値が読み取られないようにします。並列領域の最後にグループ全体が戻り、次の並列領域が開始されるまでは元の単一のスレッドが継続されます。
このスタイルの並列プログラミングは、メッセージ渡しをベースに構築されているノード間通信がデータをコピー (コピー先は、そのデータが必要なフェーズ境界) するために使用される、非共有メモリ システムでも使用できます。この手法は、膨大な数のプロセッサ ノードを使用することで、気候モデリングや薬剤設計などの問題への対処に必要なきわめて高いパフォーマンスを実現する場合に利用されています。
構造化マルチスレッドの場合と同じように、OpenMP の並列領域は関数の内部に位置することがあります。したがって、その関数の呼び出し元は、実装における並列処理の使用を認識している必要はありません。ただし、SPMD モデルでは、問題の作業がグループ内のワーカーにどのようにマッピングされているかを注意深く確認する必要があります。
負荷が均等ではない場合、たとえば、あるワーカーに他のグループ メンバのタスクよりも処理に時間がかかるタスクが割り当てられているような場合は、そのワーカーの処理が完了するまで他のグループ メンバには待機状態が強いられます。システム リソースが他のジョブと共有されることのある環境においても、同様の事態が考えられます。たとえば、OS が他の何らかのタスクを実行するために、あるワーカーの処理を中止した場合、残りのワーカーにこうした負荷の不均衡による影響が及びます。
将来のハードウェア システムには、種類の異なるプロセッサ コアが搭載される可能性があります (大量の電力を消費するが、単一のスレッドの処理が速い大きなコアと、消費電力が少なく、並列操作に最適化されている小さなコアの組み合わせなど)。こうした環境では、ワーカーへの作業のマッピング方法がきわめて複雑になるため、SPMD モデルを使用するのは非常に困難です。これらの問題は構造化マルチスレッドのアプローチによってうまく回避することができますが、その分、スケジューリングのオーバーヘッドが若干増え、OpenMP が適しているコードのメモリ階層を制御できなくなる可能性があります。
同時実行データ構造
ここまでは、もっぱら制御並列処理に重点を置いて、使用可能な複数のコアにマッピングできる独立したタスクの特定方法と記述方法を説明してきましたが、データ側に焦点を当てた並列処理もあります。タスクによってデータ構造が変更される場合、たとえば値がハッシュテーブルに挿入されるような場合には、その操作は同時実行タスクから論理的に独立している可能性があります。
データ構造の標準的な実装は同時アクセスをサポートしておらず、わかりにくく予測が不可能な、再現の難しいさまざまな方法で分割されることがあります。単純に単一のロックをデータ構造全体の周囲に配置すると、すべてのタスクがシリアル化されるようなボトルネックがプログラムに生まれ、並列処理が行われなくなることがあります (同時に使用されるデータ位置があまりに少なくなるため)。
そのため、並列制御の抽象化に加えて、一般的なデータ構造 (ハッシュテーブル、スタック、キュー、さまざまなセット表現) の新しい同時実行バージョンを作成することが重要です。これらのバージョンについては、同時に呼び出すことのできるサポート対象のメソッドのセマンティクスが既に定義されています。また、複数のタスクによってアクセスされたときにボトルネックが生じないように設計されます。
例として、接続されているグラフ コンポーネントを並列的に探すときの標準的なアプローチを考えてみましょう。基本的な方針として、グラフに対して深さ優先のトラバーサルを多数開始し、衝突が起きているノードを特定し、より小さいグラフを作成します。最上位の関数の基本的な構造は、図 7 のようになります。
図 7 深さ優先のトラバーサル
// C++
// assign to each Node::component a representative node in
// the connected component containing that node
void components(Graph * g) {
g->forall_nodes([=] (Node * n) {
n->component = UNASSIGNED;
});
Roots roots;
EdgeTable edges;
g->forall_nodes([&roots, &edges] (Node * n) {
if(atomic_claim(n, n)) {
roots.add(n);
component_search(n,n, &edges);
}
});
// recusively combine reduced graph (roots, edges)
...
}
各ノード ポイントに代表要素をポイントさせることで、コンポーネントを暗黙的に表現してみます。入力はグラフです。そのグラフは、構造化マルチスレッドの手法を使用してグラフをトラバースするために使用できる forall_nodes メソッドをサポートしているものとします。このメソッドは、各ノードに適用される関数オブジェクトによってパラメータ化されます。このインターフェイスでは並列アルゴリズムをグラフの構造の詳細から切り離していますが、構造化マルチスレッドの主要なプロパティは保持しています。同時実行はメソッドの内部に位置し、高度に構造化できます。
まず、コンポーネント フィールドを識別値に初期化します。次に、すべてのノードから並列的な深さ優先の検索を論理的に開始します。各検索では、最初に開始ノードを要求します。ノードに到達する検索は 1 つではないので、この要求は、そのノードに最初に到達する検索を特定するためのアトミック テストであると言えます。その関数は次のようになります。
// C++
// atomically set n->commponent to component if it is UNASSIGNED
// return true if and only this transition was made.
bool atomic_claim(Node * n, Node * component) {
n->lock();
Node * c = n->component;
if(c == UNASSINGED) n->component = n;
n->unlock();
return c == UNASSIGNED;
}
筆者はノードごとのロックを想定しましたが、このシンプルな例では、Windows プリミティブを使用して、ポインタ値にインタロックされた比較交換を実行することもできます。ここでの重要な問題は、制御並列処理を十分確保していても、複数のタスクからの同時アクセスを防ぐための単一のグローバル ロックによってデータ並列処理が無効になり、並列処理の試みが妨げられることがあるということです。
必ずしもノードごとに 1 つのロックが必要というわけではありません。ノードをより少ないロックにマッピングすることもできますが、現在のプロセッサ数に合った数のロックを使用することで、スケーリングのボトルネックを招いてしまわないように注意する必要があります。そこで、明示的なロックを使用する代わりに、Jim Larus が提唱した "トランザクション メモリ" を使用することを検討してください。"トランザクション メモリ" のねらいは、同時に実行されるコードから独立させるべきコード区間を開発者が単純に宣言できるようにすることです。その実装では、これらのセマンティクスを保証するために、必要に応じてロックが導入されます。
新しいルート コンポーネントを特定したら、それを共有データ構造のルートに追加します。これは、論理的にはアルゴリズムの最初のステップで見つかったすべてのルート コンポーネントのセットです。ここでも、このコンテナのインスタンスが論理的に 1 つしかない場合は、並列的に追加できるようにその実装を最適化する必要があります。マイクロソフトは、PPL と Parallel Extensions to .NET の一部として、ビルディング ブロックとして使用できるベクタ、キュー、およびハッシュテーブルの適切な実装を提供する予定です。
あるノードから開始された深さ優先の検索は、隣接するノードに対して反復実行されます。また、そのコンポーネントに追加するノードの要求を試みます。これが成功した場合は、そのノードを再帰処理します (図 8 を参照)。
Figure 8 再帰検索
// C++ using the Parallel Pattern Library
// a depth first search from "n" through currently
// unassigned nodes which are
// set to refer to "component". Record inter-component edges in "edges"
void component_search(Node * n, Node * component, EdgeTable * edges) {
parallel_for_each(n->adjacents.begin(),
n->adjacents.end(),
[=] (Node * adj) {
if(atomic_claim(adj, component)
component_search(adj, component, edges);
else if(adj->component != component) {
edges->insert(adj->component, component);
}
});
}
要求が失敗した場合、つまりこのタスクまたは別のタスクがそのノードに既に到達している場合は、それが別のコンポーネントに追加されていないかどうかを確認する必要があります。別のコンポーネントに追加されていた場合は、その 2 つのコンポーネントを共有データ構造 (EdgeTable) に記録します。このテーブルは、情報の重複を避けるために、同時ハッシュテーブルを使用して作成できます。この場合も、この構造は論理的に共有されるため、競合を防ぎ、効果的な並列処理を実行できるように、同時アクセスが適切にサポートされていることを確認する必要があります。
2 つの構造、ルート、およびエッジによって、当初の推定のコンポーネント間の接続を記録する論理グラフが構成されます。アルゴリズムを完了するには、この論理グラフ上で接続されているコンポーネントを探し、そのノード レベルの情報を最終的な代表要素 (ここでは示しません) で更新します。
まとめ
並列プログラミングの際には、パフォーマンスに関連する数多くの驚くべき事態が発生します。当然のことながら、データ並列性の損失はその 1 つにすぎません。この新しい問題に対する初めての取り組みが不可解な理由で失敗したり (原因の 1 つとして、ロックの使い忘れが挙げられます)、逐次実行の場合と比べて処理速度が遅くなったり (タスクが小さすぎる、ロックが多すぎる、キャッシュの有効性が失われている、メモリ帯域幅が十分でない、データが競合しているなどの理由が考えられます) したとしても、驚くに値しません。
マイクロソフトが並列プログラミングへの投資を続けていくうちに、抽象化だけでなく、関連して起こる問題の診断や回避に役立つツールの質も着実に高まるでしょう。また、ハードウェア自体の性能が向上し、さまざまなコストを抑える機能が組み込まれるものと思われますが、それには時間がかかります。
並列処理へのシフトは、ソフトウェア業界にとっての転換点です。新しい手法の採用を避けて通ることはできません。開発者は、アプリケーションの特定の部分 (現時点で時間の制約のある部分や、将来的により大きなデータ セットで実行されると予測される部分) に並列処理を取り入れる必要があります。この記事では、アプリケーションにおける並列処理の考え方とその使用方法をいくつか紹介し、幅広い並列コンピューティング イニシアティブの一環としてマイクロソフトで開発が進められている新しいツールを使用して、それらを具体的に説明しました。
1975 年以降、マイクロプロセッサの処理能力は、クロック周波数とトランジスタ数の指数関数的な増加 (それぞれ 3,000 倍と 300,000 倍) に支えられて、10 年で 100 倍の割合で成長を続けてきました。命令の "効力" は 8 ～ 100 倍になり (8 ビットの ADD と SSE4.1 DPPS (dot-product of packed-4-SP-float-vectors) を比べてみてください)、ダイ上のキャッシュはかつてのハード ディスクほどの大きさになっています。事業として、次から次に押し寄せる波のごとく魅力的な新しいエクスペリエンスを提供するために、私たちは 100 倍の努力を続けてきました。こうした処理能力の向上は、船の帆を膨らませる風に例えることができます。
ただし、"次の 100 倍" を実現するためには、別の方角に向けて船を出さなければなりません。私たちは、2 年のサイクルでダイ (32、22、16、11 nm のノード) あたりのトランジスタの数が 16 倍になることで得られる "ムーアの法則の配当" を、まだまだ期待できます。とはいえ、私たちは、いくつかの成長曲線 (特に、電圧スケーリングと消費電力 (消費電力の壁)、命令レベルの並列性 (複雑性の壁)、メモリ待機時間 (メモリの壁)) が漸近的に落ち込んでいくポイントに立っていることに気が付いています。
消費電力の壁 マイクロプロセッサの動的消費電力は、NCV2f (トランジスタの開閉の数 × コンデンサの開閉 × 電圧の 2 乗 × 周波数) に比例します。各リソグラフィ ノードが小さくなると、ダイあたりのトランジスタの数はおそらく倍増し (↑N)、トランジスタのサイズは小さくなり (↓C)、開閉電圧は低くなります (↓V)。今日、電源電圧は 15V から 1V にまで下がっており、開閉電力は 1/100 以下に減っています。残念なことに、CMOS の最小しきい値電圧は 0.7 V なので、節約できるのは多くても (1.0/0.7)2=2X となります。こうした節約にもかかわらず、マイクロプロセッサの複雑性 (↑N) と 周波数 (↑f) は増したため、ダイの消費電力は、数平方センチメートルのシリコンごとに 1 W から 100 W に増え、今や実用的な冷却装置の限界に達しています。これ以上の余裕はありません。消費電力は、進行中のゼロサム ゲームと言えます。クロック周波数は、かつてのペースで増加することはありません。この領域では、"次の 100 倍" を実現することはできません。
複雑性の壁 高パフォーマンス マイクロプロセッサは、スレッドにおける命令レベルの並列性を活用するために、大胆なアウト オブ オーダー実行を使用しています。ただし、このアプローチからさらに大きな効果を得るのには、現実的に限界があります。連続しているコード自体と、そのデータの依存関係により、利用できる並列処理は制限されます。ハードウェアの側では、N 個の操作を並列して行うには、最大 N2 個の回路が余分に必要になることがあります。したがって、事前の設計と検証のコストがそれに比例して高くなります。並列処理ソフトウェアが登場したと仮定して、最も重要な点に触れましょう。消費電力の壁が示しているのは、エネルギー効率の良いマイクロアーキテクチャこそが優れたアーキテクチャであるということです。これは、"ナノ秒あたりの結果" よりも "ジュールあたりの結果" の方が重要視されることを表しています。
メモリの壁 DRAM アクセスの待機時間 (遅延) の改善は比較的ゆっくりとしたペースで行われています。そのため、CPU はキャッシュを使用することで DRAM の使用を避けています。ただし、キャッシュは負荷の大きい処理です。現在、フルキャッシュ ミスの場合は 300 クロックが費やされることがあります。経験から言うと、キャッシュ サイズを 4 倍にするとミスの割合は半分になります。CPU コアの複雑さの大部分は、時間のかかる予測不可能なメモリ アクセスに対処するためのものです。より簡単な手段は、メモリ帯域幅を拡張する方法です。そこで、メモリレベルの並列処理を適用できます。並列処理ソフトウェアのスレッドは、一度に多数の同時メモリ アクセスを発行します。各スレッドは、アクセスできるまで長時間待機しなければならない場合もありますが、並列計算の全体的なスループットは非常に高くなります。
今後 10 年の間、逐次プロセッサの処理能力は向上し続けるでしょうが、その勢いはこれまでと比べて著しく低下します。賢明な CPU デザイナとコンパイラ ライタは、どうにかして 5% や 10% の向上を実現するさまざまな手段を考え出すでしょう。これは好ましい取り組みです。数々の有用なソフトウェアは逐次処理型であり、それらにはアムダールの法則を適用できるためです。ただし、これでは私たちが真に求める "次の 100 倍" を実現するには至りません。そこで、並列処理を活用するソフトウェアが必要なのです。十分に魅力的なソフトウェアが登場したら、プロセッサ ベンダはすぐさま多数のコアを搭載した並列処理プロセッサと高帯域幅メモリ ソリューションを提供することでしょう。並列処理プロセッサの登場は、私たちの肩にかかっています。
—マイクロソフトの並列コンピューティング プラットフォーム チームのソフトウェア アーキテクト、Jan Gray
David Callahan は、Visual Studio の並列コンピューティング プラットフォーム チームの Distinguished Engineer 兼リード アーキテクトです。彼は、スーパーコンピュータ製造企業である Cray Inc. からマイクロソフトに移ってきました。並列化コンパイラ、並列アルゴリズム、並列アーキテクチャ、および並列言語を専門としています。