Tweet

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

Page1 Page2 Page3 Page4

■概要

　並列プログラミングとは、逐次プログラミングを拡張したものです。今日、並列プログラミングは、日常的な情報処理における主流のパラダイムとなりつつあります。並列プログラミングが目指しているのは、並列コンピューター上で高速に稼動するプログラムの構築です。並列プログラムの開発手法は、統合フレームワークに組み込むことができます。並列プログラムの開発では、アルゴリズムと言語、さらにはプログラムを並列コンピューターに展開する方法に重点が置かれています。

■はじめに

　並列プログラミングでは、同時にプログラムを実行することで、高いコンピューティング パフォーマンスを実現します。かつて、並列プログラミングといえばスーパー コンピューティングと相場は決まっていましたが、最近では日常的な情報処理において並列プログラミングが主流のパラダイムとなりつつあります。並列プログラミングは、マルチコア マルチプロセッサと、費用対効果の高いサーバー クラスターの普及によって広まっています。一般的なソフトウェア業界では、次世代の並行処理ツールによって、リッチなデスクトップとサーバー ソフトウェア開発ツールの統合が進んでいます。例としては、Microsoft Visual Studio および並列コンピューティング向け .NET 拡張、Microsoft Windows HPC Server、非集中/分散型のサービス指向プログラミング、グリッド コンピューティングなどがあります。これらには、数十年の研究に基づくさまざまなアイデア、すなわち副作用のない関数プログラミング、レース コンディションに対する保護、非フォン ノイマン アーキテクチャのデータフロー パラダイムなどのアイデアが豊富に含まれています。

　並列プログラムは、逐次プログラムを結合することで構築されます。その目的は、個別の逐次プログラムを並列で実行し、さまざまな組み合わせパターンを介して、各逐次プログラムの結果を最終的な解に結合することです。これを実現するに際して、バグのない正確な並列プログラムを開発し、パフォーマンスだけでなく、信頼性、可用性、既存のソフトウェア エコシステムで統合されているフォールト トレランスなどの他のメリットを手にすることを目的とします。

　並列プログラミングは、急速に重要な開発スキルの 1 つとなりつつあります。とはいえ、クライアントからサーバー クラスターに至るまで、さまざまな並列処理テクノロジが存在するため、開発ツールセットやランタイム環境は多種多様です。したがって、基本的な並列処理のコンセプトについて理解することは、複雑な並列処理テクノロジをより良く理解するうえで、開発者にとってかつてないほど重要になっています。

■正確性とパフォーマンス

　開発者は、常に正確で効率的なアプリケーションを作成する必要があります。正確性とパフォーマンスを両立することで、プログラムは決められた時間内に適切な結果を生成できるからです。これらを実現するために、逐次処理コンピューターで使用されてきた従来のモデルは、フォン ノイマンの“プログラム格納”モデルです。“プログラム格納”モデルでは、単一の実行スレッドが存在し、命令は一度に 1 つのプロセッサで実行されます。

　並列コンピューターでは、複数のプロセッサが存在し、各プロセッサが同時に実行スレッドを実行します。正確性およびパフォーマンスの分析に使用される並列コンピューター モデルは、プログラム格納モデルの簡単な拡張版です。使用される 2 つのモデルは、共有メモリ モデルと分散メモリ モデルです（図 1）。共有メモリ モデルでは、共通のメモリがすべてのプロセッサによって共有されています。一方、分散メモリ モデルでは、メモリが共有されていません。

図 1: 並列コンピューター: 共有メモリ モデルと分散メモリ モデル

　ハイパフォーマンスのアプリケーションを構築するという目標は、同じ問題を解く複数の逐次プログラムを同時に実行させることで達成できます。これには、分解およびパターンという 2 つの重要な概念が関係します。

■分解およびパターン

　“分解”とは、1 つの問題を、同時に解決できる個別の部分に分割（または分解）する手法です。これらの各部分は、それぞれ結果を生成します。それらの結果は、最終的な結果を生成するために結合されます。したがって、これらの部分には、結合するためのスキーム（または“パターン”）が必要になります。並列計算の全体的な正確性とパフォーマンスを検討するにあたっては、分解された各部分と、使用するパターンの両方の正確性とパフォーマンスを考慮します。

　例として、16 個のデータの最大値を特定する問題について考えてみます。この場合、全データを 4 つのデータから成る 4 つの部分に分割し、4 つのプロセッサ上で、これら各部分の最大値を同時に特定します。その後、4 つの各部分の最大値から全体の最大値を特定できます。この問題で使用される逐次部分は、4 つのデータの最大値を特定するメソッドです。一方、この問題で使用されるパターンは、4 つの暫定最大値を並列で特定し、その後実際の最大値を特定するというものです。図 2 に、このスキームを示します。

図 2: 16 個のデータの最大値を特定する問題を示すスキーム

　分解とパターンの使用は、目新しいものではありません（参考資料の [Quinn,2004] などの標準テキストを参照）。分解は、複数のプロセッサ上で同時に実行できる 1 つ以上の逐次アルゴリズム（逐次プログラム）を特定することと見なすことができます。通常、このような逐次部分は、“処理粒度”、または単に並列計算の“粒度”と呼ばれます。同様に、パターンは高度な調整アルゴリズム、または“合成”スキームと見なすことができます。いくつかの有用なパターンが知られています（参考資料の [Mattson, 2005] を参照）。

■並列プログラムの分析

　並列アルゴリズムとそれに伴うプログラムの正確性とパフォーマンスを分析するには、並列コンピューター モデルを使用できます。並列アルゴリズムは、使用する逐次プログラムとパターンの両方が正しい場合に、正確であると言えます。正確性を実現するには、逐次プログラム/アルゴリズムに似た手法をとることができます。これにより、欠陥のある並列プログラムの“デバッグおよび診断”に、逐次プログラムと同じ手法を使うことができます。

　正確性を確認するにあたり、プログラムが変換するデータのメモリ状態を調べます。並列プログラムでは、並列で実行される“プログラムの逐次部分で、依存性が線形”になります。しかし、“パターンでは依存性が非線形になる”場合があります。たとえば、16 個の整数の最大値を特定する前述のアルゴリズムで使用されるパターンは、正確なスキームといえます。なぜなら、プログラム Max1、Max2、および runMax によって指定される合成スキームのすべてが正確だからです。図 2 は、runMax.bat で記述されている逐次実行プログラム（Max1 および Max2 によって実行される）の依存性を表しています。通常、これらの図表のノードは、データまたはタスク（計算）、あるいはそれら両方を表します。前者は“データフロー グラフ”、後者は“タスク グラフ”と呼ばれます。

　同様に、アルゴリズム的なアプローチにより、パフォーマンスの予測もできます。たとえば、並列計算の最初の段階、つまり 4 つのプロセッサ上で実行される Max1 の 4 つの実行インスタンス（4 つの整数の最大値を特定する）には、同時実行で時間 T がかかるとします。2 番目の段階では、1 つのプロセッサ上で Max2 の 1 つの実行インスタンスが必要になります。したがって、使用されるアルゴリズムの合計時間は 4 つのプロセスで 2T になります（“プロセス”とは、プログラムの実行インスタンスを指します）。この予測は、期待できるパフォーマンスの基準となります。

■性能向上率: パフォーマンスの測定

　逐次プログラムで要する時間と、並列プログラムで要する時間の比率は、性能向上率と呼ばれます。一般的に、問題の解決に使用される並列アルゴリズムには、さまざまなものが存在します。したがって、どの並列アルゴリズムで最も高いパフォーマンスを実現できるかを知ることが重要です。アムダールの法則によると、性能向上率は最大で 1/[S + (1-S) /n] になります（S はアプリケーション内で並列化できないコードの割合を表し、n はプロセッサの数を表します）。たとえば、前述の最大値特定プログラムの場合、割合 S はプログラム Max1.c によって求められます。16 個の整数の最大値を特定する例では、割合 S は 0.2（Max1 のインスタンス 4 つと、Max2 のインスタンス 1 つを逐次実行した場合を 100 % とする）になり、アムダールの法則によると、性能向上率は 4 つのプロセッサで最大 2.5 になります。

　性能向上率が比例するという考え方は、グスタフソンの法則によって示されています。グスタフソンの法則によると、性能向上率は n + (1-n) * s の制限を受けます（n はプロセッサ数、s は合計実行時間に対する、プログラムの並列部分に必要な時間の比率）。前述の例では、s = 1/(log416) = 0.5 となります。したがって、n = 4 の場合は 2.5 になります。同様に、n = 16 (s = 0.3) の場合は 11.5、n = 64 (s = 0.25) の場合は 49 のようになります。

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

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

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