並列アルゴリズム
並列アルゴリズム（へいれつアルゴリズム、英語: parallel algorithm）とは、アルゴリズムの各部分を異なる複数の処理装置（プロセッサ）上で実行し、最終的にそれらの結果を集めることで答えを得るアルゴリズム。
概要
[編集]一部のアルゴリズムはこのような分割が容易である。例えば、1 から数百数千といった範囲の数について、それぞれが素数かどうかを調べる場合、各プロセッサに部分範囲を割り当てればよく、最終的に結果のリストを連結すればよい。
また逆に円周率を求めるアルゴリズムの多くは、並列に動作可能な部分に分割するのは容易ではない。円周率を求める場合、前の結果を使わないと次のステップを効率的に実施できない。このような問題は本質的に逐次的であるといえる。同様に、数値解析におけるニュートン法や多体問題を解くアルゴリズムなども本質的に逐次的である。再帰的でありながら並列化が非常に難しい問題もある。例えば、グラフにおける深さ優先探索がある。
並列アルゴリズムは、問題の規模が大きくなるほど並列でないアルゴリズムよりもずっと速く問題を解くことができる。一般に単一プロセッサの極めて高速なコンピュータよりも、多数の遅いプロセッサで同等のスループットを実現するコンピュータを構築する方が容易である。また、単一プロセッサの性能には理論的な限界がある。並列アルゴリズムには並列化できない部分があり、並列度を上げていっても性能が上がらなくなる点が存在する（アムダールの法則参照）。その点を越えてプロセッサを追加してもスループットは向上せず、かえってオーバーヘッドとコストが増大する結果になる。
逐次アルゴリズムの計算量は使用する領域（メモリ）と時間（プロセッササイクル）で測る。並列アルゴリズムではもう1つの観点として、プロセッサ間の通信コストを考慮しなければならない。並列プロセッサの通信には、共有メモリを使う方法とメッセージパッシングによる方法がある。
共有メモリ処理では、データのロックが必要となり、オーバーヘッドを生じる。また、アルゴリズムの一部が逐次化されてしまう。
メッセージパッシング処理では、バス上をメッセージ転送するオーバーヘッドを生じ、キューやメッセージボックスのためのメモリも必要になり、キューイングすることでメッセージにレイテンシが生じる。クロスバースイッチのような特殊なバスを使うことで、プロセッサ間の通信オーバーヘッドを低減させることができるが、通信量は個々の並列アルゴリズムによって異なる。
もう1つ、並列アルゴリズムには負荷分散がうまく行われるかという問題がある。例えば、ある範囲の数が素数かどうかを調べる場合、割り当てが不公平だと一部のプロセッサが早めに処理を終えてしまい、何もしていない状態になる。
並列アルゴリズムの一種として分散アルゴリズムがある。分散アルゴリズムは、コンピュータ・クラスターや分散コンピューティング環境で動作するよう設計されており、古典的な並列アルゴリズムとは違った問題に対処する必要がある。
実装
[編集]以下のハードウェアを使い実装できる。
- コンピュータ・クラスター
- GPUやメニーコアのCPU - NVIDIA Tesla K80 は4,992コア
- FPGA - 通常、一つの演算で複数のロジック・エレメントを必要とするが、アルテラのStratix Vで最大359,200アダプティブ・ロジック・モジュール、最大3,926可変精度DSPブロック。これらが並列で動く。