並列アルゴリズム
【英】：parallel algorithm
数理計画問題に対する並列アルゴリズムの多くは, 各反復で並列処理可能な部分問題を解かせるもので, 行列分割法や作用素分割法の考え方に基づいている. また, 凸計画問題の双対問題が変数の非負制約のみをもつことを利用した並列アルゴリズムも多い. 一方, ネットワーク構造やブロック構造をもつ問題に対する既存のアルゴリズムのなかには並列計算機上で効率的に実行できるものも少なくない.
並列アルゴリズム (数理計画問題の)
並列アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/22 17:07 UTC 版)
並列アルゴリズム（へいれつアルゴリズム、英: parallel algorithm）とは、アルゴリズムの各部分を異なる複数の処理装置（プロセッサ）上で実行し、最終的にそれらの結果を集めることで答えを得るアルゴリズム。
概要
一部のアルゴリズムはこのような分割が容易である。例えば、1 から数百数千といった範囲の数について、それぞれが素数かどうかを調べる場合、各プロセッサに部分範囲を割り当てればよく、最終的に結果のリストを連結すればよい。
また逆に円周率を求めるアルゴリズムの多くは、並列に動作可能な部分に分割するのは容易ではない。円周率を求める場合、前の結果を使わないと次のステップを効率的に実施できない。このような問題は本質的に逐次的であるといえる。同様に、数値解析におけるニュートン法や多体問題を解くアルゴリズムなども本質的に逐次的である。再帰的でありながら並列化が非常に難しい問題もある。例えば、グラフにおける深さ優先探索がある。
並列アルゴリズムは、問題の規模が大きくなるほど並列でないアルゴリズムよりもずっと速く問題を解くことができる。一般に単一プロセッサの極めて高速なコンピュータよりも、多数の遅いプロセッサで同等のスループットを実現するコンピュータを構築する方が容易である。また、単一プロセッサの性能には理論的な限界がある。並列アルゴリズムには並列化できない部分があり、並列度を上げていっても性能が上がらなくなる点が存在する（アムダールの法則参照）。その点を越えてプロセッサを追加してもスループットは向上せず、かえってオーバーヘッドとコストが増大する結果になる。
逐次アルゴリズムの計算量は使用する領域（メモリ）と時間（プロセッササイクル）で測る。並列アルゴリズムではもう1つの観点として、プロセッサ間の通信コストを考慮しなければならない。並列プロセッサの通信には、共有メモリを使う方法とメッセージパッシングによる方法がある。
共有メモリ処理では、データのロックが必要となり、オーバーヘッドを生じる。また、アルゴリズムの一部が逐次化されてしまう。
メッセージパッシング処理では、バス上をメッセージ転送するオーバーヘッドを生じ、キューやメッセージボックスのためのメモリも必要になり、キューイングすることでメッセージにレイテンシが生じる。クロスバースイッチのような特殊なバスを使うことで、プロセッサ間の通信オーバーヘッドを低減させることができるが、通信量は個々の並列アルゴリズムによって異なる。
もう1つ、並列アルゴリズムには負荷分散がうまく行われるかという問題がある。例えば、ある範囲の数が素数かどうかを調べる場合、割り当てが不公平だと一部のプロセッサが早めに処理を終えてしまい、何もしていない状態になる。
並列アルゴリズムの一種として分散アルゴリズムがある。分散アルゴリズムは、コンピュータ・クラスターや分散コンピューティング環境で動作するよう設計されており、古典的な並列アルゴリズムとは違った問題に対処する必要がある。
プログラミング言語の標準ライブラリ
| 高階関数 | C++ | Java | .NET |
|---|---|---|---|
| 並列foreach | std::for_each[1] | parallelなStream.forEach[2] | ParallelEnumerable.ForAll[3] |
| 並列map | std::transform[4] | parallelなStream.map[5] | ParallelEnumerable.Select[6] |
| 並列filter | std::copy_if[7] | parallelなStream.filter | ParallelEnumerable.Where[8] |
| 並列fold | std::reduce[9] | parallelなStream.reduce | ParallelEnumerable.Aggregate[10] |
| 並列scan (inclusive) | std::inclusive_scan[11] | Arrays.parallelPrefix[12] | |
| 並列scan (exclusive) | std::exclusive_scan[13] | ||
| 並列sort | std::sort[14] | parallelなStream.sorted | ParallelEnumerable.OrderBy[15] |
並列foldと並列scanは二項演算子が結合法則を満たす必要がある。NVIDIA CUDAのC++の場合はThrustでも実装されている[16]。
実装方法
並列foreachと並列mapの実装方法は自明。
並列foldは、二項演算子 
固有名詞の分類
- 並列アルゴリズムのページへのリンク
