並列アルゴリズム
並列アルゴリズム(へいれつアルゴリズム、英語: parallel algorithm)とは、アルゴリズムの各部分を異なる複数の処理装置(プロセッサ)上で実行し、最終的にそれらの結果を集めることで答えを得るアルゴリズム。
一部のアルゴリズムはこのような分割が容易である。例えば、1 から数百数千といった範囲の数について、それぞれが素数かどうかを調べる場合、各プロセッサに部分範囲を割り当てればよく、最終的に結果のリストを連結すればよい。
また逆に円周率を求めるアルゴリズムの多くは、並列に動作可能な部分に分割するのは容易ではない。円周率を求める場合、前の結果を使わないと次のステップを効率的に実施できない。このような問題は本質的に逐次的であるといえる。同様に、数値解析におけるニュートン法や多体問題を解くアルゴリズムなども本質的に逐次的である。再帰的でありながら並列化が非常に難しい問題もある。例えば、グラフにおける深さ優先探索がある。
並列アルゴリズムは、問題の規模が大きくなるほど並列でないアルゴリズムよりもずっと速く問題を解くことができる。一般に単一プロセッサの極めて高速なコンピュータよりも、多数の遅いプロセッサで同等のスループットを実現するコンピュータを構築する方が容易である。また、単一プロセッサの性能には理論的な限界がある。並列アルゴリズムには並列化できない部分があり、並列度を上げていっても性能が上がらなくなる点が存在する(アムダールの法則参照)。その点を越えてプロセッサを追加してもスループットは向上せず、かえってオーバーヘッドとコストが増大する結果になる。