📑 Table of Contents▼

並列アルゴリズム（へいれつアルゴリズム、英: 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は、二項演算子 が結合法則を満たすことを使用して、 と計算すれば良い。

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

  • 方法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コア搭載している[18]
  • コンピュータ・クラスター
  • FPGA - 通常、一つの演算で複数のロジック・エレメントを必要とするが、アルテラのStratix Vで最大359,200アダプティブ・ロジック・モジュール、最大3,926可変精度DSPブロック。これらが並列で動く。

関連文献

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

関連項目

編集

出典

編集
  1. ^ “std::for_each - cppreference.com”. en.cppreference.com. 2025年3月22日閲覧。
  2. ^ “Stream (Java SE 21 & JDK 21)”. docs.oracle.com. 2025年3月22日閲覧。
  3. ^ “ParallelEnumerable.ForAll Method (System.Linq)”. 2025年3月19日閲覧。
  4. ^ “std::transform - cppreference.com”. en.cppreference.com. 2025年3月18日閲覧。
  5. ^ “java.util.stream (Java SE 21 & JDK 21)”. docs.oracle.com. 2025年3月19日閲覧。
  6. ^ “ParallelEnumerable.Select Method (System.Linq)”. 2025年3月19日閲覧。
  7. ^ “std::copy, std::copy_if - cppreference.com”. en.cppreference.com. 2025年3月18日閲覧。
  8. ^ “ParallelEnumerable.Where Method (System.Linq)”. 2025年3月19日閲覧。
  9. ^ “std::reduce - cppreference.com”. en.cppreference.com. 2025年3月18日閲覧。
  10. ^ “ParallelEnumerable.Aggregate Method (System.Linq)”. 2025年3月19日閲覧。
  11. ^ “std::inclusive_scan - cppreference.com”. en.cppreference.com. 2025年3月18日閲覧。
  12. ^ “Arrays (Java SE 21 & JDK 21)”. docs.oracle.com. 2025年3月19日閲覧。
  13. ^ “std::exclusive_scan - cppreference.com”. en.cppreference.com. 2025年3月19日閲覧。
  14. ^ “std::sort - cppreference.com”. en.cppreference.com. 2025年3月18日閲覧。
  15. ^ “ParallelEnumerable.OrderBy Method (System.Linq)”. 2025年3月19日閲覧。
  16. ^ “Thrust: The C++ Parallel Algorithms Library — thrust 3.0 documentation”. nvidia.github.io. 2025年3月22日閲覧。
  17. ^ “Implementing Parallel copy_if in C++”. C++ Stories. 2025年3月22日閲覧。
  18. ^ “NVIDIA GeForce RTX 5090 Graphics Cards”. NVIDIA. 2025年3月19日閲覧。

外部リンク

編集

📚 Artikel Terkait di Wikipedia

数値線形代数

Modified Discrete Lotka-Volterra with Shift Algorithm」 『In Proceedings of 2011 International Conference on Parallel and Distributed Processing Techniques and

固有値問題の数値解法

An algorithm for generalized matrix eigenvalue problems. en:SIAM Journal on Numerical Analysis, 10(2), 241-256. ^ Paul N. Swarztrauber:A parallel algorithm

分割統治法

conquer algorithm for the symmetric tridiagonal eigenproblem. arXiv preprint arXiv:1506.08517. Tisseur, F., & Dongarra, J. (1999). A parallel divide and

CUDA

documentation”. nvidia.github.io. 2025年3月18日閲覧。 ^ NVIDIA HPC Compilers C++ Parallel Algorithm ^ “thrust::transform — thrust 2.5 documentation”. nvidia.github.io

ランダムフォレスト

to configure. ALGLIB contains implementation of modified random forest algorithm in C#, C++, Pascal, VBA. FastRandomForest Efficient implementation in

Zstandard

Real-time data compression algorithm”. facebook.github.io. 2024年5月4日閲覧。 ^ Sergio De Simone, Facebook Open-Sources New Compression Algorithm Outperforming Zlib

エドワーズ曲線デジタル署名アルゴリズム

エドワーズ曲線デジタル署名アルゴリズム（エドワーズきょくせんデジタルしょめいあるごりずむ、英語: Edwards-curve Digital Signature Algorithm、略称：EdDSA）は、公開鍵暗号において、ツイステッドエドワーズ曲線（英語版）に基づくシュノア署名（英語版）の一種を用いたデジタル署名の一

ジーン・ゴラブ

は、数値解析・数値線形代数を専門とするアメリカ合衆国の数学者。 Numerical Linear Algebra, Digital Signal Processing and Parallel Algorithms, Gene H. Golub, Published by Springer-Verlag (1991) ISBN 0387523006