並列アルゴリズム

並列アルゴリズムとは

並列アルゴリズムとは、一つの問題を複数のプロセッサで分担して処理し、最終的に結果を統合することで答えを得るアルゴリズムです。この手法は、大規模な問題を高速に解決するために非常に重要です。

並列化が容易な問題と困難な問題

並列アルゴリズムは、すべての問題に有効なわけではありません。例えば、与えられた数値範囲で素数を判定するような問題は、各プロセッサに異なる範囲を割り当てることで簡単に並列化できます。しかし、円周率を求めるアルゴリズムのように、前の結果を次の計算に使う必要がある問題は、並列化が困難です。これらの問題は、本質的に逐次的であると言えます。ニュートン法や多体問題の解析も同様です。また、グラフの深さ優先探索のように、再帰的な構造を持ちながら並列化が難しい問題も存在します。

並列アルゴリズムの利点と限界

並列アルゴリズムは、問題の規模が大きくなるほど、逐次アルゴリズムよりも高速に問題を解決できます。一般的に、単一の高性能プロセッサよりも、多数のプロセッサを持つシステムの方が構築が容易です。しかし、並列アルゴリズムには並列化できない部分が存在し、プロセッサを増やしても性能向上が頭打ちになることがあります。これはアムダールの法則として知られています。プロセッサの追加は、オーバーヘッドとコストを増大させるだけになることもあります。

並列アルゴリズムにおける計算量

逐次アルゴリズムの計算量は、使用するメモリ量と処理時間で測られます。並列アルゴリズムでは、これらに加えてプロセッサ間の通信コストも考慮する必要があります。通信方式には、共有メモリ方式とメッセージパッシング方式があります。共有メモリ方式では、データのロックによるオーバーヘッドや、アルゴリズムの一部の逐次化が起こりえます。メッセージパッシング方式では、メッセージ転送のオーバーヘッド、キューやメッセージボックスのためのメモリが必要になり、メッセージに遅延が生じる可能性があります。クロスバースイッチのような特殊なバスを用いることで通信オーバーヘッドを低減できますが、その効果はアルゴリズムによって異なります。

負荷分散の問題

並列アルゴリズムでは、プロセッサ間の負荷分散も重要な課題です。例えば、素数判定のように各プロセッサに処理を割り当てる際、割り当てが不公平だと、一部のプロセッサが早く処理を終えてしまい、他のプロセッサが処理を終えるまで待機することになります。このような事態を避けるためには、適切な負荷分散アルゴリズムが不可欠です。

分散アルゴリズムとの関連

並列アルゴリズムの一種として、分散アルゴリズムがあります。分散アルゴリズムは、コンピュータクラスタや分散コンピューティング環境で動作するように設計されています。分散アルゴリズムは、古典的な並列アルゴリズムとは異なる問題に対処する必要があり、より複雑なシステム構成を前提とします。

実装

並列アルゴリズムは、以下のハードウェア上で実装できます。

コンピュータ・クラスタ: 複数のコンピュータをネットワークで接続し、並列処理を行う。
GPUやメニーコアCPU: 多数の処理コアを持つプロセッサを使用し、並列処理を行う。
FPGA: 論理回路を再構成できるデバイスを使用し、特定の問題に特化した並列処理を行う。

関連文献

フレデリック・マグレス、フランソワ＝グザヴィエ・ルー、桑原拓也（訳）：「並列計算の数理とアルゴリズム」、森北出版、ISBN 978-4-627-80711-2 (2015年2月18日).

関連項目

マルチエージェントシステム
ニューラルネットワーク
並列コンピューティング

外部リンク

Designing and Building Parallel Programs アルゴンヌ国立研究所

もう一度検索