並列アルゴリズム

並列アルゴリズム（へいれつアルゴリズム、英: parallel algorithm）とは、アルゴリズムの各部分を異なる複数の処理装置（プロセッサ）上で実行し、最終的にそれらの結果を集めることで答えを得るアルゴリズム。

概要

一部のアルゴリズムはこのような分割が容易である。例えば、1 から数百数千といった範囲の数について、それぞれが素数かどうかを調べる場合、各プロセッサに部分範囲を割り当てればよく、最終的に結果のリストを連結すればよい。

また逆に円周率を求めるアルゴリズムの多くは、並列に動作可能な部分に分割するのは容易ではない。円周率を求める場合、前の結果を使わないと次のステップを効率的に実施できない。このような問題は本質的に逐次的であるといえる。同様に、数値解析におけるニュートン法や多体問題を解くアルゴリズムなども本質的に逐次的である。再帰的でありながら並列化が非常に難しい問題もある。例えば、グラフにおける深さ優先探索がある。

並列アルゴリズムは、問題の規模が大きくなるほど並列でないアルゴリズムよりもずっと速く問題を解くことができる。一般に単一プロセッサの極めて高速なコンピュータよりも、多数の遅いプロセッサで同等のスループットを実現するコンピュータを構築する方が容易である。また、単一プロセッサの性能には理論的な限界がある。並列アルゴリズムには並列化できない部分があり、並列度を上げていっても性能が上がらなくなる点が存在する（アムダールの法則参照）。その点を越えてプロセッサを追加してもスループットは向上せず、かえってオーバーヘッドとコストが増大する結果になる。

逐次アルゴリズムの計算量は使用する領域（メモリ）と時間（プロセッササイクル）で測る。並列アルゴリズムではもう1つの観点として、プロセッサ間の通信コストを考慮しなければならない。並列プロセッサの通信には、共有メモリを使う方法とメッセージパッシングによる方法がある。

共有メモリ処理では、データのロックが必要となり、オーバーヘッドを生じる。また、アルゴリズムの一部が逐次化されてしまう。

メッセージパッシング処理では、バス上をメッセージ転送するオーバーヘッドを生じ、キューやメッセージボックスのためのメモリも必要になり、キューイングすることでメッセージにレイテンシが生じる。クロスバースイッチのような特殊なバスを使うことで、プロセッサ間の通信オーバーヘッドを低減させることができるが、通信量は個々の並列アルゴリズムによって異なる。

もう1つ、並列アルゴリズムには負荷分散がうまく行われるかという問題がある。例えば、ある範囲の数が素数かどうかを調べる場合、割り当てが不公平だと一部のプロセッサが早めに処理を終えてしまい、何もしていない状態になる。

並列アルゴリズムの一種として分散アルゴリズムがある。分散アルゴリズムは、コンピュータ・クラスターや分散コンピューティング環境で動作するよう設計されており、古典的な並列アルゴリズムとは違った問題に対処する必要がある。

プログラミング言語の標準ライブラリ

並列foldと並列scanは二項演算子が結合法則を満たす必要がある。NVIDIA CUDAのC の場合はThrustでも実装されている。

実装方法

並列foreachと並列mapの実装方法は自明。

並列foldは、二項演算子 $\oplus$ が結合法則を満たすことを使用して、 $(A\oplus B)\oplus (C\oplus D)=E\oplus F=G$ と計算すれば良い。

並列filterは、以下の方法などがある。

方法1
1. 入力配列をチャンクに分け、並列mapを使いそれぞれのチャンクで逐次filterを行う。
2. 1の計算結果を、逐次foreachで動的配列に追記していく。シングルスレッド（逐次foreach）でもメモリコピーが遅くなければ問題ないが、並列度の高いシステムだとここがボトルネックになる。
方法2
1. 並列mapを使い、入力配列の各要素に対して、残すものは1、残さないものは0に変換する。
2. 並列exclusive scanを使い、1のmap結果の累積和を計算する。
3. 累積和の最後の値から出力配列の長さが分かるので、この長さで出力配列を確保する。
4. 並列foreachを使い、1で残すとしたものに対して、2で計算した番地の出力配列に書き込む。

並列scanの実装方法は累積和を参照。

対応ハードウェア

以下のハードウェアを使い実装できる。

CPU
GPU - 例えばNVIDIA GeForce RTX 5090は21,760CUDAコア搭載している
コンピュータ・クラスター
FPGA - 通常、一つの演算で複数のロジック・エレメントを必要とするが、アルテラのStratix Vで最大359,200アダプティブ・ロジック・モジュール、最大3,926可変精度DSPブロック。これらが並列で動く。