アーキテクチャ・ジャーナル 並列プログラムの開発 Ranjan Sen 2010/02/03
Page1 Page2 Page3 Page4

■次世代のツール

　Java および.NET プログラミング言語には、管理ランタイムで並列プログラミングをサポートするためのプログラミング拡張機能が備わっています（参考資料の [Lea, 1999] を参照）。PFX（Parallel FX Library）は、.NET Framework 3.5 および今後リリースされる予定の新しい.NET Framework 4.0 上で稼働します *21。.NET Framework では、CLR と呼ばれるランタイムが提供されています。このランタイムは、管理環境でコードを実行し、自動ガーベッジ コレクション、ジャストインタイム実行、強化されたコード アクセス セキュリティを備えています。これにより、並列処理を、多数の最新.NET ベース テクノロジに組み込むことができます *22。

　PFX での基本的な手法は、匿名の関数を使用することです。つまり、匿名の関数を使用して式を構築し、それらの式を並列で実行することです。匿名の関数を、匿名デリゲート *23 またはラムダ式 *24 として表すと便利です。さらに、式のネスティングを利用することで、式ツリーを作成することもできます。また、ラムダ式を活用して、式ツリーで関数を使用することもできます。

*21　Microsoft .NET Framework。

*22　MSDN並列コンピューティング フォーラム、および並列コンピューティング開発者センター。

*23　デリゲートとは、型やシグネチャの情報を維持する関数へのポインターです。

*24　匿名メソッドは、C# 2.0 で導入されました。匿名メソッドにより、デリゲート関数でインライン メソッドを宣言できるようになりました。C# 3.0 では、同じ目的でさらに使いやすいラムダ式が利用できます。

　命令型タスクの並列性は、タスク並列ライブラリの System.Threading.dll によって実現されます。タスク並列ライブラリ（TPL）は、協調スケジューリングおよびワーク スティーリングを使用するスケジューラ上に構築され、高速で効率的なスケジューリングとプロセッサ使用率の最大化を実現します。

　TPL には、System.Threading.Parallel 型、System.Threading.Tasks.Task 型、および System.Threading.Tasks.Future<T> 型があります。最初の型は、ループおよび領域を並列化するために使用されます。Parallel 型で使用できる静的メソッドは、For、ForEach、Invoke です。次に例を示します。

// Task Parallel: for (int i=0; i < n; i++) results[i] = compute(i); Parallel.For(0, n, I => results[i] = compute(i)); // Data Parallel: // (IEnumerable<T> objects. Use of foreach and ForEach keywords): foreach(testClass t in data) compute (t); Parallel.ForEach(data, delegate(testClass t) { compute(c); });

　For および ForEach メソッドには、関数の定義を並列で適用するように、ラムダ式が含まれている点に注目してください。ステートメントを並列のステートメント ブロックで実行するために、Invoke 静的メソッドを使用できます。タスクを作成/操作するために Task クラスを使用できます。このクラスは、ThreadPool が提供する機能に似ています。デリゲートは、実行待ちのキューに入れられます。Task は簡単に使用できるうえに、さらに多くの機能があります。たとえば、タスクの待機およびステータス チェックのメソッドがあります。

　説明は C# で記述していますが、TPL は Visual Basic 2008 および関数型プログラミング言語の F# でも使用できます。（参考資料の [MacLennan, 1990] を参照）。

　Future<T> クラスは、Task から派生しています。このクラスには、関連付けられた値があります。その値とは、パラメーターとして指定されている System.Func<T> 型インスタンスの非同期実行の結果です。この値は、Future インスタンスからアクセスできます。また、値が使用できるようになるまで待機することもできます。Future は、データ駆動型またはデータ フロー コンピューティング アーキテクチャを定義するためのメカニズムを提供します *25。

*25　Jack Dennis の紹介とデータ フロー アーキテクチャに関する論文は、http://en.wikipedia.org/wiki/Jack_Dennis を参照してください。

　高レベルなコンストラクター（スレッド セーフなコレクション、より洗練されたロッキング プリミティブ、処理交換のためのデータ構造、変数の生産性を制御するためのタイプ、強力な同期プリミティブのレパートリーなど）には、CountEvent、LazyInit<T>、ManualResetEventSlim、SemaphoreSlim、SpinLock、SpinWait、WriteOnce<T>、Collections.BlockingCollection<T>、Collections.CouncurrentQueue<T>、および Collections.ConcurrentStack<T> が含まれます。

　PLINQ（Parallel LINQ）は、PFX のコンポーネントの 1 つです。データ並列の特性により、データが増加するに従ってプログラムを効率的に拡大できます。PLINQ により、既存の問題に対する既存のソリューションとして、並列処理のメリットを漸進的に活用することができます。PLINQ を使用するには、System.Linq.ParallelEnumerable.AsParallel 拡張メソッドを呼び出して、データ ソースを IParallelEnumerable<T> にラップする必要があります（IParallelEnumerable は IEnumerable<T> の拡張版）。

　var q でクエリを定義し、foreach でデータ ソース q に対して実際にクエリを実行します。この宣言型クエリにより、アクション a によって foreach で実際にクエリが実行されるまで、PLINQ は最適なリソースの使用に関する決定（クエリを実行するプロセッサ数など）を遅らせることができます。PLINQ は、複数のスレッドを使用することで、使用可能なプロセッサで実行するクエリ部分の準備を行います。ユーザーがこの処理について意識する必要はありません。

■MPI.NET

　MPI.NET *26 は、C# のネイティブ MPI ライブラリを使用するための効率的なインターフェイスです。MPI.NET は、C# の機能とマネージド/アンマネージドの相互運用メカニズムを活用することで、インターフェイスを簡略化し、MPI を拡張します。パフォーマンスにおける抽象化のペナルティを抑制するために、さまざまな革新的な方法が採用されています。たとえば、一般的なバージョンのポイント ツー ポイントの Send により、すべてのユーザー定義型を伝送に使用できます。一般的に、ポイント ツー ポイントの Send はすべてのタイプの通信操作に拡張されています。詳細については、参考資料の [MPI.NET, 2008] を参照してください。

*26　PPoPP ホームページの MPI.NET。

■プログラミング環境とツール

　マルチコア システムでは、オペレーティング システムは、さまざまなパラダイムにより、最適なリソース使用率を実現するために刷新されています。クラスターでは、これらのサポートが開発や展開サービス/ツール（サービス指向ジョブ スケジューリングなど *27）に統合されています。

　Visual Studio などのツールでは、両方のソース レベルでのデバッグがサポートされています。Visual Studio には、並列デバッガー拡張機能もあります *28。ログのトレースは、これらの問題を診断するうえで役立ちます *29。Portland Group は、Windows クラスターのデバッガーを提供しています *30。他に、TotalView *31 などのプロバイダーもあります。

　最も一般的なプロセスは、分析と調整の後に、トレース ツールを使用して動作をプロファイルすることです。MPI は、トレースを念頭に置いて開発されました。トレース ライブラリの MPE は、MPI の配布サイトから入手できます *32。また、Windows HPC Cluster にも含まれています *33。トレースは、Jumpshot *34 などの表示ツールを使用して表示できます。他にも、Intel Trace Analyzer and Collector Vampir *35、MPICL と ParaGraph *36、Epilog/KOJAK *37 などのツールがあります。

*27　Windows HPC Server 2008 の新機能。

*28　Visual Studio を使用した Windows クラスター上の MPI のデバッグについては、Windows HPC ホームページを参照してください。

*29　WHPC での MPI トレース ログ。

*30　PGDBG および PGPROF については、Portland Group Web サイトを参照してください。

*31　TotalView Technologies。

*32　MPE（MPI Parallel Environment）、Argonne National Lab。

*33　Windows HPC Cluster は、Windows CCS 2003 または Windows HPC Server 2008 製品を指します。

*34　Jumpshot。

*35　Intel Trace Analyzer and Collector。

*36　MPICL（MPI のインスツルメンテーション ライブラリ）、および ParaGraph（MPIのパフォーマンス視覚化ツール）。

*37　Epilog、および KOJAK。

■まとめ

　並列プログラミングとは、逐次プログラミングを拡張したものです。並列アルゴリズムの出来は、逐次プログラムを構成するアルゴリズムと、それらのアルゴリズをまとめるパターンによって決まります。逐次プログラミングを分析するためのプログラミング モデルは、共有メモリ モデルおよび分散メモリ モデルへと拡張されています。並列コンピューティングをサポートするさまざまなプロセッサおよびクラスター アーキテクチャは、これら 2 つのモデルのバリエーションです。

　並列プログラムの正確性は、逐次プログラムの正確性を維持し、逐次プログラムの解を組み合わせるパターンを工夫することで実現できます。並列プログラムのパフォーマンスは、アルゴリズム、実装の詳細、対象となるコンピューターのアーキテクチャによって異なります。並列コンピューターは、マルチコア プロセッサから、クラスター、コンピューター グリッド、クラウド コンピューターまで多岐にわたります。

　並列プログラムの開発手法は、すべて統合フレームワークに組み込むことができます。並列プログラムの開発では、アルゴリズムと言語、さらにはプログラムを並列コンピューターに展開する方法に重点が置かれています。

■参考資料

[Akl, 1989] Selim G. Akl『The Design and Analysis of Parallel Algorithms（並列アルゴリズムの設計と分析）』、米国ニュージャージー州、イングルウッドクリフ、Prentice Hall、1989 年

[Dongarra, 2003] Jack J. Dongarra 他『Sourcebook of Parallel Computing（並列コンピューティングのソースブック）』、米国サンフランシスコ、 Morgan Kaufman Publishers、2003 年

[Foster, 1995] Ian Foster『Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering（並列プログラムの設計と構築: 並列ソフトウェア エンジニアリングの概念とツール）』、米国マサチューセッツ州レディング、Addison-Wesley、1995 年

[Gropp, 1999] William Gropp 他『Using MPI: Portable Parallel Programming with the Message-Passing Interface（MPI の使用: メッセージパッシングインターフェイスによるポータブル並列プログラミング）』、米国マサチューセッツ州ケンブリッジ、MIT Press、1999 年

[Lea, 1999] Doug Lea『Concurrent Programming in Java: Design Principles and Patterns（Java での同時実行プログラミング: 設計原則とパターン）』、第 2 版、米国マサチューセッツ州レディング、Addison-Wesley、1999 年

[Leighton, 1992] Frank Thomson Leighton『Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes（並列アルゴリズムとアーキテクチャの手引き: アレイ、ツリー、ハイパーキューブ）』、米国カリフォルニア州サンマテオ、M. Kaufmann Publishers、1992 年

[MacLennan, 1990] Bruce J. MacLennan『Functional Programming: Practice and Theory（関数プログラミング :理論と実践）』、米国マサチューセッツ州レディング、Addison-Wesley、1990 年

[Mattson, 2005] Timothy G. Mattson 他『Patterns for Parallel Programming（並列プログラミングのパターン）』、米国ボストン、AddisonWesley、2005 年

[Miller, 2005] Russ Miller 他『Algorithms Sequential and Parallel: A Unified Approach（逐次および並列アルゴリズムの統一されたアプローチ）』、第 2 版、米国マサチューセッツ州ヒンガム、Charles River Media、2005 年

[MPI.NET, 2008] Douglas Gregor、Andrew Lumsdaine「Design and Implementation of a High-Performance MPI for C# and the Common Language Infrastructure（C# および他の一般的な言語インフラストラクチャ向けに、High-Performance MPI の設計と実装を行う）」、MPI.NET Publications、並列プログラミングの原則と実践に関する第 13 回 ACM SIGPLAN シンポジウムの議事録、米国ソルトレークシティー、2008 年 2 月

[Quinn, 2004] Michael J. Quinn『Parallel Programming in C with MPI and OpenMP（MPI および OpenMP を使用した C での並列プログラミング）』、米国アイオワ州ドゥビューク、McGraw-Hill、2004 年

[Sterling, 2002] Thomas L. Sterling『Beowulf Cluster Computing with Windows（Windows を使用したベオウルフ クラスター コンピューティング）』、米国マサチューセッツ州ケンブリッジ、MIT Press、2002 年

著者について Ranjan Sen は、マイクロソフトのシニアソリューション アーキテクトです。2001 年にマイクロソフトに入社しました。1981 年以来、ハイパフォーマンス コンピューティング、並列処理およびアーキテクチャの分野で経験を積んできました。Ranjan は、1978 年カルカッタ大学でコンピューター サイエンスの博士号を取得し、1979 年以降はインド工科大学、ラトガーズ大学、ハンプトン大学をはじめとするいくつかの大学の学部に勤務しました。Ranjan は、アルゴリズム/アーキテクチャ間マッピングのグラフ理論的なモデリングを専門にしており、この分野に関する書籍を多数執筆しています。

■このトピックに関する最新情報

• 並列コンピューティングに関する MSDN Magazine、2008 年 10 月
• ハイパフォーマンス コンピューティングの実例
• .NET Parallel 拡張機能
• Windows HPC Server 2008

INDEX
	［アーキテクチャ・ジャーナル］
	並列プログラムの開発
	1．並列プログラムのパフォーマンス
	2．並列コンピューティングのプラットフォーム
	3．並列プログラムの開発
	4．次世代のツール

「アーキテクチャ・ジャーナル」

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）