Loading article…
コンピュータサイエンスにおいて、並列アルゴリズムは、従来の逐次アルゴリズムとは対照的に、与えられた時間内に複数の操作を実行できるアルゴリズムです。コンピュータサイエンスでは、逐次アルゴリズムを抽象マシンモデル（多くの場合、ランダムアクセスマシンとして知られるモデル）で記述するのが伝統となっています。同様に、多くのコンピュータサイエンス研究者は、いわゆる並列ランダムアクセスマシン（PRAM）を並列抽象マシン（共有メモリ）として使用してきました。[ 1 ] [ 2 ]
多くの並列アルゴリズムは並行して実行されますが、一般的に並行アルゴリズムは別の概念です。そのため、これらの概念はしばしば混同され、アルゴリズムのどの部分が並列で、どの部分が並行なのかが明確に区別されないことがあります。さらに、並列でも並行でもないアルゴリズムは、並行アルゴリズムと対比して「逐次アルゴリズム」と呼ばれることがよくあります。
アルゴリズムの並列化のしやすさは大きく異なり、容易に並列化できるものから全く並列化できないものまで様々である。さらに、同じ問題でも、並列化のしやすさが異なる複数のアルゴリズムが適用できる場合がある。
問題の中には、このように簡単に分割できるものがあります。これらは「並列処理が容易な問題」と呼ばれます。例としては、ルービックキューブを解くアルゴリズムや、特定のハッシュ値になるような値を求めるアルゴリズムなどが挙げられます。
問題によっては、前のステップの結果が次のステップを効果的に進めるために必要となるため、並列に分割できないものがあります。これらは、本質的に逐次的な問題。ニュートン法などの反復数値法三体問題の反復解法、円周率（π）を計算するために利用可能なほとんどのアルゴリズムなどがある。自動並列化を使用して並列アルゴリズムに変換できる。 [ 3 ]
多くの場合、タスクを解決するための効果的な並列アルゴリズムを開発するには、同じ問題を解決するための逐次アルゴリズムの設計には必要ない新しいアイデアや方法を開発する必要があります。そのようなケースの例としては、データ構造内のターゲット要素の検索や代数式の評価といった、実用上重要な問題が挙げられます。[ 4 ]
2000年代初頭以降、マルチプロセッシングシステムの著しい進歩とマルチコアプロセッサの台頭により、個々のデバイス上で並列アルゴリズムを実行することが一般的になってきました。2004年末までは、シングルコアプロセッサの性能は周波数スケーリングによって急速に向上していたため、同じスループットを持つ多数の低速コアを持つコンピュータよりも、高速な単一コアを持つコンピュータを構築する方が容易でした。そのため、マルチコアシステムの利用は限定的でした。しかし、2004年以降、周波数スケーリングは限界に達し、マルチコアシステムが普及したことで、並列アルゴリズムの利用範囲が広がりました。
逐次アルゴリズムのコストまたは複雑さは、それらが消費する空間（メモリ）と時間（プロセッササイクル）の観点から推定されます。並列アルゴリズムでは、さらに別のリソース、つまり異なるプロセッサ間の通信を最適化する必要があります。並列プロセッサ間の通信方法には、共有メモリとメッセージパッシングの2種類があります。
共有メモリ処理では、データに追加のロックが必要となり、追加のプロセッササイクルとバスサイクルのオーバーヘッドが発生し、アルゴリズムの一部が直列化される。
メッセージパッシング処理ではチャネルとメッセージボックスが使用されますが、この通信方式ではバス上で転送オーバーヘッドが発生し、キューやメッセージボックスのための追加メモリが必要となり、メッセージの遅延も生じます。並列プロセッサの設計では、クロスバーなどの特殊なバスを使用することで通信オーバーヘッドを小さく抑えていますが、トラフィック量は並列アルゴリズムによって決まります。
プロセッサを追加することによる通信オーバーヘッドが、プロセッサを追加することによるメリットを上回る場合、並列処理の速度低下が発生します。
並列アルゴリズムのもう1つの問題は、入力サイズではなく負荷（全体の作業量）のバランスを取ることで、適切な負荷分散を確保することです。たとえば、1から10万までのすべての数を素数判定する処理は、プロセッサ間で簡単に分割できます。しかし、数を単純に均等に分割した場合（1～1,000、1,001～2,000など）、このアルゴリズムでは小さい数の方が処理しやすい（素数判定が容易）ため、作業量が不均衡になり、一部のプロセッサは他のプロセッサよりも多くの作業を行うことになり、負荷のかかったプロセッサの処理が完了するまでアイドル状態になります。
並列アルゴリズムの一種である分散アルゴリズムは、クラスタコンピューティングや分散コンピューティング環境で動作するように設計されたアルゴリズムであり、「古典的な」並列アルゴリズムの範囲を超える追加的な懸念事項に対処する必要がある。
分散アルゴリズムは、共有メモリやメッセージパッシングを介して通信する相互接続されたコンピュータのネットワーク上で動作することを想定しています。従来の並列アルゴリズムとは異なり、分散アルゴリズムは、限られたローカル情報、通信遅延、グローバル状態の欠如、ノード障害の可能性といった追加の制約の下で動作する必要があります。
分散アルゴリズムの焦点は、リーダー選出、相互排除、合意形成（コンピュータサイエンス）など、分散システムで発生する協調問題にあります。これらの問題は、システムが同期か非同期か、クラッシュ障害やビザンチン障害などの障害があるかどうかなど、さまざまな仮定を持つさまざまなシステムモデルの下で研究されています。[ 5 ]
分散アルゴリズムは、分散データベース、耐障害性システム、大規模ネットワークアプリケーションなど、多くの実用的な用途がある。