並列コンピューティング

並列コンピューティングは、多くの計算やプロセスが同時に実行されるタイプのコンピューティングです。 ^[1]大きな問題は多くの場合、小さな問題に分割され、同時に解決できます。 並列コンピューティングには、ビットレベル、命令レベル、データ、タスクの並列性など、いくつかの異なる形式があります。 並列性は長い間、高性能コンピューティングで採用されてきましたが、周波数スケーリングを妨げる物理的な制約のために、より広い関心を集めています。^[2]近年、コンピューターの電力消費（およびその結果としての発熱）が懸念されるようになったため、^{[3]並列コンピューティングは、主に}マルチコアプロセッサーの形で、コンピューターアーキテクチャにおける主要なパラダイムになりました。^[4]

コンピュータサイエンスでは、並列性と同時実行性は2つの異なるものです。並列プログラムは複数のCPUコアを使用し、各コアは独立してタスクを実行します。一方、同時実行性により、プログラムは単一のCPUコア上でも複数のタスクを処理できます。コアは、必ずしも各タスクを完了する必要はなく、タスク（つまりスレッド）を切り替えます。プログラムは、並列性と同時実行性の両方の特性を持つことも、どちらも持たないことも、組み合わせることもできます。^[5]

並列コンピュータは、ハードウェアが並列処理をサポートするレベルによって大まかに分類できます。マルチコアおよびマルチプロセッサコンピュータは、単一のマシン内に複数の処理要素を持ちますが、クラスタ、MPP、およびグリッドは、複数のコンピュータを使用して同じタスクを処理します。特殊な並列コンピュータ アーキテクチャは、特定のタスクを高速化するために、従来のプロセッサと併用されることがあります。

ビットレベルや命令レベルの並列処理など、並列処理はプログラマにとって透過的な場合もありますが、明示的に並列化されたアルゴリズム、特に並行処理を使用するアルゴリズムは、逐次的なアルゴリズムよりも記述が難しくなります。 ^{[6]並行処理によって潜在的な}ソフトウェアバグの新しいクラスがいくつか導入され、その中で最もよくあるのが競合状態です。異なるサブタスク間の通信と同期は、通常、並列プログラムのパフォーマンスを最適化する上で最大の障害の 1 つです。

並列化の結果としての単一プログラムの速度向上の理論的な上限は、並列化を利用できる時間の割合によって制限されるという アムダールの法則によって与えられます。

伝統的に、コンピュータソフトウェアはシリアル計算用に書かれてきました。問題を解決するために、アルゴリズムが構築され、シリアルな命令ストリームとして実装されます。これらの命令は、1台のコンピュータの中央処理装置で実行されます。一度に実行できる命令は1つだけで、その命令が終了すると次の命令が実行されます。^[7]

一方、並列コンピューティングでは、複数の処理要素を同時に使用して問題を解決します。これは、問題を独立した部分に分割して、各処理要素がアルゴリズムの自分の部分を他の部分と同時に実行できるようにすることで実現されます。処理要素は多様であり、複数のプロセッサを備えた単一のコンピューター、複数のネットワーク化されたコンピューター、専用のハードウェア、またはこれらの任意の組み合わせなどのリソースを含めることができます。^{[7]歴史的に、並列コンピューティングは、特に}気象学などの自然科学や工学科学における科学計算や科学的問題のシミュレーションに使用されていました。これにより、並列ハードウェアとソフトウェア、および高性能コンピューティングの設計が生まれました。^[8]

周波数スケーリングは、1980 年代半ばから 2004 年まで、コンピュータのパフォーマンス向上の主な理由でした。プログラムの実行時間は、命令の数と命令あたりの平均時間の積に等しくなります。他のすべての条件を一定に保ったまま、クロック周波数を上げると、命令の実行にかかる平均時間が短縮されます。したがって、周波数が増加すると、すべての計算依存プログラムの実行時間が短縮されます。^[9]ただし、チップの消費電力P は、 P = C × V ² × Fという式で表されます。ここで、Cはクロック サイクルごとに切り替えられる容量(入力が変化するトランジスタの数に比例)、Vは電圧、F はプロセッサ周波数 (1 秒あたりのサイクル数) です。^[10]周波数が増加すると、プロセッサで使用される電力量が増加します。プロセッサの消費電力の増加は、最終的にIntelが 2004 年 5 月 8 日にTejas および Jayhawkプロセッサをキャンセルする結果につながり、これが一般に、主要なコンピュータ アーキテクチャ パラダイムとしての周波数スケーリングの終焉として挙げられています。^[11]

電力消費と過熱の問題に対処するため、主要な中央処理装置（CPUまたはプロセッサ）メーカーは、複数のコアを備えた電力効率の高いプロセッサの製造を開始しました。コアはプロセッサのコンピューティングユニットであり、マルチコアプロセッサでは各コアが独立しており、同じメモリに同時にアクセスできます。マルチコアプロセッサにより、デスクトップコンピュータに並列コンピューティングが導入されました。したがって、シリアルプログラムの並列化は、プログラミングタスクの主流になりました。2012年には、クアッドコアプロセッサがデスクトップコンピュータの標準となり、サーバーには10コア以上のプロセッサが搭載されました。2023年までには、100を超えるコアを備えたプロセッサもあります。熱と設計の制約により、パフォーマンスコアと効率コアが混在する設計もあります（ARMのbig.LITTLE設計など）。^{[12] [出典が必要]}。ムーアの法則から、プロセッサあたりのコア数は18〜24か月ごとに倍増すると予測できます。

オペレーティングシステムは、利用可能なコア上でさまざまなタスクやユーザープログラムを並列に実行できるようにします。ただし、シリアルソフトウェアプログラムがマルチコアアーキテクチャを最大限に活用するには、プログラマーがコードを再構築して並列化する必要があります。アプリケーションソフトウェアの実行時間の高速化は、周波数スケーリングでは達成できなくなり、代わりにプログラマーはソフトウェアコードを並列化して、マルチコアアーキテクチャの増加する計算能力を活用する必要があります。^[13]

主要記事:アムダールの法則

並列化による高速化は、最適には線形になります。つまり、処理要素の数を 2 倍にすると実行時間が半分になり、さらに 2 倍にすると実行時間がさらに半分になります。ただし、最適な高速化を実現する並列アルゴリズムはごくわずかです。ほとんどのアルゴリズムでは、処理要素の数が少ない場合はほぼ線形の高速化が実現され、処理要素の数が多い場合は一定値に平坦化されます。

システム全体の最大潜在的スピードアップは、アムダールの法則によって計算できます。^[14]アムダールの法則は、タスクの並列化可能なコンポーネントと並列化不可能なコンポーネントの両方の強化をバランスよく行うことで、最適なパフォーマンス向上が達成されることを示しています。さらに、プロセッサの数を増やすと収穫逓減が生じ、ある時点を超えるとスピードアップのメリットはほとんどなくなることも明らかにしています。^{[15] [16]}

アムダールの法則には、固定された作業負荷を前提としていること、プロセス間通信と同期のオーバーヘッドを無視していること、主に計算面に焦点を当てていること、データの永続性、I/O操作、メモリアクセスのオーバーヘッドなどの外的要因を無視していることなどの限界がある。^{[17] [18] [19]}

グスタフソンの法則とユニバーサルスケーラビリティ法則は、並列パフォーマンスのより現実的な評価を与える。^{[20] [21]}

データの依存関係を理解することは、並列アルゴリズムを実装する上で基本となります。連鎖内の前の計算に依存する計算は順番に実行する必要があるため、依存する計算の最長の連鎖 (クリティカル パスと呼ばれる) よりも速く実行できるプログラムはありません。ただし、ほとんどのアルゴリズムは、依存する計算の長い連鎖だけで構成されているわけではなく、通常は独立した計算を並列に実行する機会があります。

P _iとP _{j を}2つのプログラムセグメントとする。バーンスタインの条件[ ^22]は、2つが独立しており、並列実行できる場合を記述する。P i の場合、_I i をすべての入力変数、O i を出力変数とし、_P jについて_も同様とする。P _iとP jが独立_している場合、それらは次 の条件を満たす。

${\displaystyle I_{j}\cap O_{i}=\varnothing ,}$

${\displaystyle I_{i}\cap O_{j}=\varnothing ,}$

${\displaystyle O_{i}\cap O_{j}=\varnothing .}$

最初の条件に違反すると、最初のセグメントが2番目のセグメントで使用される結果を生成するというフロー依存性が発生します。2番目の条件は、2番目のセグメントが最初のセグメントに必要な変数を生成する場合の反依存性を表します。3番目で最後の条件は出力依存性を表します。2つのセグメントが同じ場所に書き込む場合、結果は論理的に最後に実行されたセグメントから取得されます。^[23]

いくつかの種類の依存関係を示す次の関数を検討してください。

1: 関数 Dep(a, b)
2: c := a * b
3: d := 3 * c
4: 終了関数

この例では、命令 3 は命令 2 の結果を使用するため、命令 2 より前に (または命令 2 と並行して) 実行することはできません。これは条件 1 に違反し、フロー依存性が生じます。

1: 関数NoDep(a, b)
2: c := a * b
3: d := 3 * b
4: e := a + b
5: 終了関数

この例では、命令間に依存関係がないため、すべて並列に実行できます。

バーンスタインの条件では、異なるプロセス間でメモリを共有することは許可されません。そのためには、セマフォ、バリア、またはその他の同期方法など、アクセス間の順序付けを強制する何らかの手段が必要です。

並列プログラム内のサブタスクは、しばしばスレッドと呼ばれます。並列コンピュータアーキテクチャの中には、ファイバーと呼ばれる小型軽量バージョンのスレッドを使用するものもあれば、プロセスと呼ばれる大型バージョンを使用するものもあります。ただし、「スレッド」はサブタスクの総称として一般的に受け入れられています。^[24]スレッドは、共有されている変数を更新する必要がある場合など、オブジェクトやその他のリソースへの同期アクセスを必要とすることがよくあります。同期がなければ、2つのスレッド間の命令は任意の順序でインターリーブされる可能性があります。たとえば、次のプログラムを検討してください。

命令 1B が 1A と 3A の間で実行される場合、または命令 1A が 1B と 3B の間で実行される場合、プログラムは不正なデータを生成します。これは競合状態と呼ばれます。プログラマーは相互排他性を提供するためにロックを使用する必要があります。ロックは、1 つのスレッドが変数を制御し、その変数がロック解除されるまで他のスレッドによる読み取りまたは書き込みを禁止できるようにするプログラミング言語構造です。ロックを保持しているスレッドは、クリティカル セクション(一部の変数への排他的アクセスを必要とするプログラム セクション) を自由に実行し、終了時にデータのロックを解除できます。したがって、正しいプログラム実行を保証するために、上記のプログラムをロックを使用するように書き直すことができます。

一方のスレッドは変数Vを正常にロックしますが、もう一方のスレッドはロックアウトされ、 Vが再びロック解除されるまで続行できなくなります。これにより、プログラムが正しく実行されることが保証されます。スレッドがリソースへのアクセスをシリアル化する必要がある場合、ロックはプログラムの正しい実行を保証するために必要になる場合がありますが、ロックを使用するとプログラムが大幅に遅くなり、信頼性に影響を与える可能性があります。^[25]

非アトミックロックを使用して複数の変数をロックすると、プログラムデッドロックが発生する可能性があります。アトミックロックは一度に複数の変数をロックします。すべてをロックできない場合は、いずれもロックされません。2つのスレッドがそれぞれ非アトミックロックを使用して同じ2つの変数をロックする必要がある場合、1つのスレッドが1つの変数をロックし、2番目のスレッドが2番目の変数をロックする可能性があります。このような場合、どちらのスレッドも完了できず、デッドロックが発生します。^[26]

多くの並列プログラムでは、サブタスクが同期して動作する必要があります。これにはバリアを使用する必要があります。バリアは通常、ロックまたはセマフォを使用して実装されます。^[27]ロックフリーアルゴリズムとウェイトフリーアルゴリズムと呼ばれるアルゴリズムの1つのクラスでは、ロックとバリアの使用を完全に回避します。ただし、このアプローチは一般に実装が難しく、正しく設計されたデータ構造が必要です。^[28]

すべての並列化がスピードアップにつながるわけではありません。一般的に、タスクがより多くのスレッドに分割されるにつれて、それらのスレッドが互いに通信したり、リソースへのアクセスを互いに待機したりするのに費やす時間はますます長くなります。^{[29] [30]}リソースの競合や通信によるオーバーヘッドが他の計算に費やされる時間の大部分を占めるようになると、さらなる並列化（つまり、ワークロードをさらに多くのスレッドに分割すること）は、完了に必要な時間を短縮するのではなく、むしろ増加させます。この問題は並列スローダウンと呼ばれ、^[31]ソフトウェアの分析と再設計によって改善できる場合があります。^[32]

アプリケーションは、サブタスクが互いに同期または通信する必要がある頻度に応じて分類されることがよくあります。サブタスクが 1 秒間に何度も通信する必要がある場合、アプリケーションは細粒度の並列処理を示します。1 秒間に何度も通信しない場合は粗粒度の並列処理を示します。通信がほとんどまたはまったく必要ない場合は 、恥ずかしいほどの並列処理を示します。恥ずかしいほどの並列処理アプリケーションは、最も並列化しやすいと考えられています。

マイケル・J・フリン氏は、並列（および順次）コンピュータとプログラムの最も初期の分類システムの 1 つを作成しました。これは現在、フリンの分類法として知られています。フリン氏は、プログラムとコンピュータを、それらが単一の命令セットを使用して動作しているか、複数の命令セットを使用しているか、およびそれらの命令が単一のデータ セットを使用しているか、複数のデータ セットを使用しているかによって分類しました。

単一命令単一データ (SISD) 分類は、完全に順次的なプログラムに相当します。単一命令複数データ (SIMD) 分類は、大規模なデータ セットに対して同じ操作を繰り返し実行することに似ています。これは、信号処理アプリケーションでよく行われます。複数命令単一データ (MISD) 分類はあまり使用されません。これに対処するためのコンピューター アーキテクチャ (シストリック アレイなど) は考案されましたが、このクラスに適合するアプリケーションはほとんど実現されていません。複数命令複数データ (MIMD) プログラムは、並列プログラムの中で最も一般的なタイプです。

デイビッド・A・パターソンとジョン・L・ヘネシーによれば、「もちろん、いくつかのマシンはこれらのカテゴリのハイブリッドですが、この古典的なモデルはシンプルで理解しやすく、最初の近似値として優れているため生き残っています。また、おそらくその理解しやすさから、最も広く使用されている方式でもあります。」^[34]

並列コンピューティングは、主に複数のプロセスからのデータをマージすることに関連するコストのために、実際にはかなりのオーバーヘッドが発生する可能性があります。具体的には、プロセス間通信と同期により、単一のスレッドで同じデータを処理する場合と比較して、オーバーヘッドが大幅に高くなる可能性があります（多くの場合、2桁以上）。^{[35] [36] [37]}したがって、全体的な改善は慎重に評価する必要があります。

1970 年代に超大規模集積回路(VLSI)のコンピュータ チップ製造技術が登場してから1986 年頃まで、コンピュータ アーキテクチャの高速化は、コンピュータのワード サイズ(プロセッサが 1 サイクルあたりに処理できる情報量) を 2 倍にすることで推進されました。^[38]ワード サイズを大きくすると、ワードの長さよりも大きいサイズの変数に対する操作を実行するためにプロセッサが実行しなければならない命令の数が減ります。たとえば、8 ビットプロセッサが 2 つの16 ビット 整数を加算する必要がある場合、プロセッサは最初に標準の加算命令を使用して各整数の下位 8 ビットを加算し、次にキャリー付き加算命令と下位加算からのキャリー ビットを使用して上位 8 ビットを加算する必要があります。したがって、8 ビット プロセッサでは 1 つの操作を完了するのに 2 つの命令が必要ですが、16 ビット プロセッサでは 1 つの命令で操作を完了できます。

歴史的に、4 ビットマイクロプロセッサは、8 ビット、16 ビット、32 ビットの順に置き換えられてきました。この傾向は、20 年間汎用コンピューティングの標準であった 32 ビット プロセッサの導入によって一般的に終わりました。2000 年代初頭にx86-64アーキテクチャが登場して初めて、64 ビットプロセッサが普及しました。

コンピュータプログラムは、本質的にはプロセッサによって実行される命令のストリームです。命令レベルの並列性がなければ、プロセッサはクロックサイクルごとに1つ未満の命令しか発行できません（IPC < 1 ）。これらのプロセッサはサブスカラプロセッサとして知られています。これらの命令は並べ替えられ、グループに結合され、プログラムの結果を変更することなく並列実行されます。これは命令レベルの並列性として知られています。命令レベルの並列性の進歩は、1980年代半ばから1990年代半ばまでコンピュータアーキテクチャを支配しました。^[39]

現代のプロセッサはすべて、多段命令パイプラインを備えています。パイプラインの各ステージは、プロセッサがそのステージでその命令に対して実行する異なるアクションに対応しています。N ステージのパイプラインを備えたプロセッサは、完了の異なるステージで最大N 個の異なる命令を持つことができるため、クロック サイクルごとに 1 つの命令を発行できます ( IPC = 1 )。これらのプロセッサはスカラープロセッサとして知られています。パイプライン プロセッサの標準的な例は、命令フェッチ (IF)、命令デコード (ID)、実行 (EX)、メモリ アクセス (MEM)、レジスタ ライト バック (WB) の 5 つのステージを持つRISCプロセッサです。Pentium 4プロセッサには 35 ステージのパイプラインがありました。^[40]

最近のプロセッサのほとんどには、複数の実行ユニットもあります。通常、この機能はパイプラインと組み合わされているため、1 クロック サイクルあたり複数の命令を発行できます ( IPC > 1 )。これらのプロセッサは、スーパースカラープロセッサと呼ばれます。スーパースカラー プロセッサは、複数の実行ユニットがプロセッサ全体 (つまり、処理ユニット) ではないという点で、マルチコア プロセッサと異なります。命令は、それらの間にデータ依存関係がない場合にのみグループ化できます。スコアボードとTomasulo アルゴリズム(スコアボードに似ていますが、レジスタの名前変更を使用します) は、アウトオブオーダー実行と命令レベルの並列処理を実装するための最も一般的な 2 つの手法です。

タスク並列性は、並列プログラムの特徴であり、「同じデータセットまたは異なるデータセットに対して、まったく異なる計算を実行できる」というものです。^[41]これは、同じ計算が同じデータセットまたは異なるデータセットに対して実行されるデータ並列性とは対照的です。タスク並列性では、タスクをサブタスクに分解し、各サブタスクをプロセッサに割り当てて実行します。プロセッサは、これらのサブタスクを同時に、そして多くの場合は協力して実行します。タスク並列性は通常、問題のサイズに応じて拡張されません。^[42]

スーパーワードレベルの並列処理は、ループアンローリングと基本ブロックベクトル化に基づくベクトル化技術である。座標やカラーチャンネルの操作、または手動で展開されたループなどのインラインコードの並列処理を利用できる点で、ループベクトル化アルゴリズムとは異なる。^[43]

並列コンピュータの主記憶は、共有メモリ（単一のアドレス空間内のすべての処理要素間で共有される）または分散メモリ（各処理要素が独自のローカルアドレス空間を持つ）のいずれかである。^[44]分散メモリとは、メモリが論理的に分散されていることを意味するが、多くの場合、物理的にも分散されていることを意味する。分散共有メモリとメモリ仮想化は、処理要素が独自のローカルメモリを持ち、非ローカルプロセッサ上のメモリにアクセスできる2つのアプローチを組み合わせたものである。ローカルメモリへのアクセスは、非ローカルメモリへのアクセスよりも通常高速である。スーパーコンピュータでは、 PGASなどのプログラミングモデルを使用して分散共有メモリ空間を実装できる。このモデルにより、1つの計算ノード上のプロセスが、別の計算ノードのリモートメモリに透過的にアクセスできる。すべての計算ノードは、 Infinibandなどの高速相互接続を介して外部共有メモリシステムにも接続されており、この外部共有メモリシステムはバーストバッファと呼ばれ、通常、複数のI/Oノードに物理的に分散された不揮発性メモリのアレイから構築される。

メイン メモリの各要素に同じレイテンシと帯域幅でアクセスできるコンピュータ アーキテクチャは、ユニフォーム メモリ アクセス(UMA) システムと呼ばれます。通常、これはメモリが物理的に分散されていない共有メモリシステムによってのみ実現できます。この特性を持たないシステムは、非ユニフォーム メモリ アクセス(NUMA) アーキテクチャと呼ばれます。分散メモリ システムでは、メモリ アクセスは非ユニフォームです。

コンピュータシステムはキャッシュを使用します。キャッシュはプロセッサの近くに配置された小型で高速なメモリで、メモリ値の一時的なコピーを保存します (物理的にも論理的にも近くにあります)。並列コンピュータシステムでは、キャッシュに同じ値が複数の場所に保存され、プログラムが誤って実行される可能性があるという問題があります。これらのコンピュータには、キャッシュされた値を追跡し、戦略的に消去して、プログラムが正しく実行されるようにするキャッシュコヒーレンスシステムが必要です。バススヌーピングは、どの値がアクセスされているか (したがって消去する必要があるか) を追跡するための最も一般的な方法の 1 つです。大規模で高性能なキャッシュコヒーレンスシステムを設計することは、コンピュータアーキテクチャにおいて非常に難しい問題です。その結果、共有メモリコンピュータアーキテクチャは、分散メモリシステムほど拡張性がありません。^[44]

プロセッサ間通信およびプロセッサとメモリ間の通信は、共有（マルチポートまたは多重化）メモリ、クロスバー スイッチ、共有バス、またはスター、リング、ツリー、ハイパーキューブ、ファット ハイパーキューブ（ノードに複数のプロセッサがあるハイパーキューブ）、n 次元メッシュなどのさまざまなトポロジの相互接続ネットワークなど、さまざまな方法でハードウェアに実装できます。

相互接続されたネットワークに基づく並列コンピュータには、直接接続されていないノード間でメッセージを渡すために、何らかのルーティングが必要です。プロセッサ間の通信に使用される媒体は、大規模なマルチプロセッサ マシンでは階層化される傾向があります。

並列コンピュータは、ハードウェアが並列処理をサポートするレベルに応じて大まかに分類できます。この分類は、基本的なコンピューティング ノード間の距離にほぼ類似しています。これらは相互に排他的ではありません。たとえば、対称型マルチプロセッサのクラスターは比較的一般的です。

マルチコア プロセッサとは、同じチップ上に複数の処理ユニット(「コア」と呼ばれる) を含むプロセッサです。このプロセッサは、複数の実行ユニットを含み、1 つの命令ストリーム (スレッド) からクロック サイクルごとに複数の命令を発行できるスーパースカラープロセッサとは異なります。これとは対照的に、マルチコア プロセッサは、複数の命令ストリームからクロック サイクルごとに複数の命令を発行できます。ソニーのPlayStation 3用に設計されたIBMのCell マイクロプロセッサは、有名なマルチコア プロセッサです。マルチコア プロセッサの各コアは、スーパースカラーになる可能性もあります。つまり、各コアは、クロック サイクルごとに、1 つのスレッドから複数の命令を発行できます。

同時マルチスレッド (Intel のハイパースレッディングが最もよく知られています) は、疑似マルチコアの初期の形態でした。同時マルチスレッドが可能なプロセッサには、同じ処理ユニット内に複数の実行ユニットが含まれています (つまり、スーパースカラー アーキテクチャを備えています)。また、クロック サイクルごとに複数のスレッドから複数の命令を発行できます。一方、時間的マルチスレッドには、同じ処理ユニット内に 1 つの実行ユニットが含まれており、複数のスレッドから一度に 1 つの命令を発行できます。

対称型マルチプロセッサ（SMP）は、メモリを共有し、バスを介して接続された複数の同一プロセッサを備えたコンピュータシステムです。^[45] バスの競合により、バスアーキテクチャのスケーリングが妨げられます。その結果、SMPは通常32個を超えるプロセッサで構成されません。^[46]プロセッサのサイズが小さく、大容量のキャッシュによってバス帯域幅の要件が大幅に削減されるため、十分な量のメモリ帯域幅があれば、このような対称型マルチプロセッサは極めて費用対効果に優れています。^[45]

分散コンピュータ（分散メモリマルチプロセッサとも呼ばれる）は、処理要素がネットワークで接続された分散メモリコンピュータシステムです。分散コンピュータは拡張性に優れています。「同時コンピューティング」、「並列コンピューティング」、「分散コンピューティング」という用語は重複する部分が多く、明確な区別はありません。^[47]同じシステムが「並列」と「分散」の両方の特徴を持つ場合があります。一般的な分散システムのプロセッサは、同時に並列に実行されます。^[48]

クラスターは、疎結合されたコンピュータのグループであり、密接に連携して動作するため、いくつかの点で単一のコンピュータと見なすことができます。^[49]クラスターは、ネットワークで接続された複数のスタンドアロンマシンで構成されます。クラスター内のマシンは対称である必要はありませんが、対称でない場合は負荷分散が難しくなります。最も一般的なタイプのクラスターはBeowulfクラスターで、 TCP/IPイーサネットローカルエリアネットワークに接続された複数の同一の市販コンピュータ上に実装されたクラスターです。^[50] Beowulfテクノロジーは、もともとThomas SterlingとDonald Beckerによって開発されました。 Top500スーパーコンピュータの87％はクラスターです。^[51]残りは以下で説明する超並列プロセッサです。

グリッドコンピューティングシステム（後述）は並列処理が困難な問題を簡単に処理できるため、現代のクラスターは通常、より困難な問題、つまりノードが中間結果をより頻繁に共有する必要がある問題を処理するように設計されています。これには、高帯域幅と、さらに重要な低遅延の相互接続ネットワークが必要です。多くの歴史的および現在のスーパーコンピューターは、Cray Geminiネットワークなど、クラスターコンピューティング用に特別に設計されたカスタマイズされた高性能ネットワークハードウェアを使用しています。^{[52] 2014年の時点で、現在のほとんどのスーパーコンピューターは、} Myrinet、InfiniBand、またはギガビットイーサネットなどの市販の標準ネットワークハードウェアを使用しています。

超並列プロセッサ (MPP) は、多数のネットワーク プロセッサを備えた単一のコンピュータです。MPP はクラスタと同じ特性を多く備えていますが、MPP には特殊な相互接続ネットワークがあります (クラスタはネットワークに汎用ハードウェアを使用します)。また、MPP はクラスタよりも大きく、通常は 100 個を超えるプロセッサを備えています。^[53] MPP では、「各 CPU には独自のメモリとオペレーティング システムおよびアプリケーションのコピーが含まれています。各サブシステムは高速相互接続を介して他のサブシステムと通信します。」^[54]

2009 年 6 月のTOP500ランキングで世界で5 番目に速いスーパーコンピュータであるIBMのBlue Gene/L はMPP です。

グリッド コンピューティングは、並列コンピューティングの最も分散化された形式です。インターネット経由で通信するコンピューターを利用して、特定の問題に取り組みます。インターネットで利用できる帯域幅は狭く、待ち時間は非常に長いため、分散コンピューティングでは通常、非常に並列化された問題のみを扱います。

ほとんどのグリッドコンピューティングアプリケーションはミドルウェア（オペレーティングシステムとアプリケーションの間に存在し、ネットワークリソースを管理し、ソフトウェアインターフェイスを標準化するソフトウェア）を使用します。最も一般的なグリッドコンピューティングミドルウェアは、Berkeley Open Infrastructure for Network Computing（BOINC）です。多くの場合、ボランティアコンピューティングソフトウェアは「スペアサイクル」を利用して、コンピュータがアイドル状態のときに計算を実行します。^[55]

インターネットの普及により、大規模なクラウド コンピューティングの可能性が生まれました。

並列コンピューティングには、ニッチな関心領域として残っている特殊な並列デバイスがあります。ドメイン固有ではありませんが、並列問題のいくつかのクラスにのみ適用できる傾向があります。

再構成可能なコンピューティングとは、汎用コンピュータのコプロセッサとして フィールド プログラマブル ゲート アレイ(FPGA)を使用することです。FPGA は、本質的には、特定のタスクに合わせて配線を再構成できるコンピュータ チップです。

FPGAは、 VHDL ^[56]やVerilog ^[57]などのハードウェア記述言語を使用してプログラムできます。いくつかのベンダーは、ほとんどのプログラマが使い慣れているCプログラミング言語の構文とセマンティクスをエミュレートしようとするCからHDLへの言語を作成しました。最もよく知られているCからHDLへの言語は、Mitrion-C、Impulse C、およびHandel-Cです。C++に基づくSystemCの特定のサブセットもこの目的に使用できます。

AMD がHyperTransport技術をサードパーティ ベンダーに公開するという決定は、高性能な再構成可能なコンピューティングを実現する技術となりました。^[58] DRC Computer Corporation の最高執行責任者である Michael R. D'Amour 氏によると、「最初に AMD に足を踏み入れたとき、彼らは私たちを『ソケット泥棒』と呼びました。今では彼らは私たちをパートナーと呼んでいます。」^[58]

グラフィックス処理装置（GPGPU）上の汎用コンピューティングは、コンピュータ工学研究におけるごく最近のトレンドです。GPUは、コンピュータグラフィックス処理用に高度に最適化されたコプロセッサです。^{[59]コンピュータグラフィックス処理は、データ並列演算、特に}線形代数 行列演算が主流の分野です。

初期の頃、GPGPU プログラムはプログラムを実行するために通常のグラフィックス API を使用していました。しかし、NvidiaとAMD の両社がそれぞれCUDAとStream SDKを使用したプログラミング環境をリリースしたことで、GPU 上で汎用計算を行うための新しいプログラミング言語とプラットフォームがいくつか構築されました。他の GPU プログラミング言語には、BrookGPU、PeakStream、RapidMindなどがあります。Nvidia は、 Tesla シリーズで計算専用の製品もリリースしています。テクノロジ コンソーシアムの Khronos Group は、CPU と GPU で構成されるプラットフォーム間で実行されるプログラムを作成するためのフレームワークであるOpenCL仕様をリリースしました。AMD 、Apple、Intel、NvidiaなどがOpenCL をサポートしています。

並列アプリケーションを扱うために、いくつかの特定用途向け集積回路（ASIC）アプローチが考案されている。^{[60] [61] [62]}

ASIC は（定義上）特定のアプリケーションに特化しているため、そのアプリケーションに完全に最適化することができます。その結果、特定のアプリケーションでは、ASIC は汎用コンピュータよりも優れた性能を発揮する傾向があります。しかし、ASIC はUV フォトリソグラフィーによって作成されます。このプロセスにはマスク セットが必要であり、非常に高価になる場合があります。マスク セットの価格は 100 万ドルを超える場合があります。^[63]（チップに必要なトランジスタが小さいほど、マスクは高価になります。）一方、汎用コンピューティングのパフォーマンスは時間の経過とともに向上しますが（ムーアの法則で説明されているように）、1 世代か 2 世代のチップでこれらの向上が帳消しになる傾向があります。^{[58]初期コストが高く、ムーアの法則主導の汎用コンピューティングに追い抜かれる傾向があるため、ASIC はほとんどの並列コンピューティング アプリケーションでは実現不可能になっています。ただし、いくつかは構築されています。1 つの例は、}分子動力学シミュレーション にカスタム ASIC を使用するPFLOPS RIKEN MDGRAPE-3マシンです。

ベクトルプロセッサは、大量のデータに対して同じ命令を実行できるCPUまたはコンピュータシステムです。ベクトルプロセッサには、数値またはベクトルの線形配列に対して機能する高レベルの演算があります。ベクトル演算の例はA = B × Cで、A、B、Cはそれぞれ64ビット浮動小数点数の64要素ベクトルです。^[64]これらは、FlynnのSIMD分類と密接に関連しています。^[64]

Crayコンピュータは、1970 年代から 1980 年代にかけて、ベクトル処理コンピュータとして有名になりました。しかし、ベクトル プロセッサは、CPU としても完全なコンピュータ システムとしても、一般的に姿を消しました。最新のプロセッサ命令セットには、 Freescale SemiconductorのAltiVecやIntelのStreaming SIMD Extensions (SSE)などのベクトル処理命令がいくつか含まれています。

並列コンピュータのプログラミングのために、並行プログラミング言語、ライブラリ、API、並列プログラミングモデル（アルゴリズムスケルトンなど）が作成されてきました。これらは通常、基盤となるメモリアーキテクチャ（共有メモリ、分散メモリ、共有分散メモリ）についての仮定に基づいてクラスに分類できます。共有メモリプログラミング言語は、共有メモリ変数を操作することで通信します。分散メモリはメッセージパッシングを使用します。POSIXスレッドとOpenMPは、最も広く使用されている2つの共有メモリAPIであり、メッセージパッシングインターフェイス（MPI）は、最も広く使用されているメッセージパッシングシステムAPIです。^{[65]並列プログラムのプログラミングで使用される概念の1つに}未来概念があり、これはプログラムの一部が将来のある時点でプログラムの別の部分に必要なデータを渡すことを約束するものです。

並列プログラミングを標準化する取り組みには、ハイブリッド マルチコア並列プログラミング用のOpenHMPPと呼ばれるオープン標準が含まれます。OpenHMPP ディレクティブ ベースのプログラミング モデルは、ハードウェア アクセラレータで計算を効率的にオフロードし、リモート プロシージャ コールを使用してハードウェア メモリとの間のデータ移動を最適化する構文を提供します。

コンシューマー GPU の普及により、グラフィックス API (コンピューティング シェーダーと呼ばれる)、専用 API ( OpenCLなど)、またはその他の言語拡張で コンピューティング カーネルがサポートされるようになりました。

コンパイラによる逐次プログラムの自動並列化は、特に前述のプロセッサ周波数の制限を考慮すると、並列コンピューティングの「聖杯」です。コンパイラ研究者による数十年にわたる研究にもかかわらず、自動並列化は限られた成功しか収めていません。^[66]

主流の並列プログラミング言語は、明示的に並列化されているか、（せいぜい）部分的に暗黙的であり、プログラマがコンパイラに並列化の指示を与えるかのいずれかです。完全に暗黙的な並列プログラミング言語は、SISAL、Parallel Haskell、SequenceL、System C（FPGA用）、Mitrion-C、VHDL、Verilogなど、いくつかあります。

コンピュータ システムが複雑になるにつれて、平均故障間隔は短くなるのが普通です。アプリケーション チェックポイントとは、コンピュータ システムがアプリケーションの「スナップショット」 (コア ダンプに似た、現在のすべてのリソース割り当てと変数の状態の記録) を取得する手法です。この情報は、コンピュータが故障した場合にプログラムを復元するために使用できます。アプリケーション チェックポイントとは、プログラムが最初からではなく、最後のチェックポイントからのみ再起動する必要があることを意味します。チェックポイントはさまざまな状況で利点をもたらしますが、特に高性能コンピューティングで使用される多数のプロセッサを備えた高度に並列化されたシステムで役立ちます。^[67]

並列コンピュータが大型化、高速化するにつれ、これまでは実行に時間がかかりすぎた問題を解決できるようになりました。バイオインフォマティクス（タンパク質の折り畳みや配列解析）や経済学など、さまざまな分野で並列コンピューティングが活用されています。並列コンピューティングアプリケーションでよく見られる問題には次のようなものがあります。^[68]

• 密な線形代数
• スパース線形代数
• スペクトル法（ Cooley-Tukey高速フーリエ変換など）
• N体問題（バーンズ・ハットシミュレーションなど）
• 構造化グリッド問題（格子ボルツマン法など）
• 非構造化グリッド問題（有限要素解析などで見られるもの）
• モンテカルロ法
• 組み合わせ論理（ブルートフォース暗号技術など）
• グラフトラバーサル（ソートアルゴリズムなど）
• 動的プログラミング
• 分岐限定法
• グラフィカルモデル（隠れマルコフモデルの検出やベイジアンネットワークの構築など）
• HBJモデル、簡潔なメッセージパッシングモデル^[69]
• 有限状態機械シミュレーション

並列コンピューティングは、特に同じ操作を並列に実行するロックステップシステムを介して、フォールトトレラントコンピュータシステムの設計にも適用できます。これにより、1つのコンポーネントに障害が発生した場合に冗長性が得られ、結果が異なる場合に自動エラー検出とエラー修正が可能になります。これらの方法は、一時的なエラーによって引き起こされるシングルイベントアップセットを防ぐために使用できます。^[70]組み込みシステムや特殊なシステムでは追加の対策が必要になる場合がありますが、この方法は、市販の既製システムでnモジュール冗長性を実現するための費用対効果の高いアプローチを提供できます。

真の（MIMD）並列処理の起源は、ルイジ・フェデリコ・メナブレアとチャールズ・バベッジが発明した解析エンジンのスケッチに遡ります。^{[72] [73] [74]}

1957年、Compagnie des Machines Bull社は並列処理に特化した初のコンピュータアーキテクチャであるGamma 60を発表しました。^[75]これはフォークジョインモデルと「プログラムディストリビュータ」を利用して、中央メモリに接続された独立した処理ユニット間でデータを送信および収集しました。^{[76] [77]}

1958年4月、スタンレー・ギル（フェランティ）は並列プログラミングと分岐および待機の必要性について議論した。^[78]また1958年には、IBMの研究者であるジョン・コックとダニエル・スロットニックが初めて数値計算における並列処理の使用について議論した。^[79] バローズ社は1962年にD825を発表した。これはクロスバースイッチを介して最大16個のメモリモジュールにアクセスできる4プロセッサコンピュータである。^[80] 1967年、アムダールとスロットニックはアメリカ情報処理学会連合会議で並列処理の実現可能性に関する議論を発表した。^[79]この議論の中で、並列処理による速度向上の限界を定義するアムダールの法則が作られた。

1969年、ハネウェルは最大8つのプロセッサを並列に実行できる対称型マルチプロセッサシステムである最初のMulticsシステムを発表しました。 ^{[79] 1970年代の} カーネギーメロン大学のマルチプロセッサプロジェクトであるC.mmpは、数個以上のプロセッサを搭載した最初のマルチプロセッサの1つでした。スヌーピングキャッシュを備えた最初のバス接続マルチプロセッサは、1984年のSynapse N+1でした。^[73]

SIMD並列コンピュータの歴史は1970年代に遡る。初期のSIMDコンピュータの背後にある動機は、プロセッサの制御装置のゲート遅延を複数の命令に分散させることだった。^{[81] 1964年、Slotnickは}ローレンス・リバモア国立研究所向けに超並列コンピュータの構築を提案した。^{[79]彼の設計は}米国空軍の資金提供を受け、これが最初期のSIMD並列コンピューティングの取り組みであるILLIAC IVとなった。^{[79]その設計の鍵は、最大256個のプロセッサによるかなり高い並列性であり、これによりマシンは後に}ベクトル処理として知られることになる大規模なデータセットを処理できた。しかし、ILLIAC IVは「最も悪名高いスーパーコンピュータ」と呼ばれた。プロジェクトは4分の1しか完成しなかったが、11年かかり、当初の見積もりの​​ほぼ4倍の費用がかかったためである。^{[71] 1976年にようやく最初の実際のアプリケーションを実行する準備が整ったとき、その性能は}Cray-1などの既存の商用スーパーコンピュータよりも優れていました。

1970年代初頭、MITコンピュータ科学および人工知能研究所で、マービン・ミンスキーとシーモア・パパートは、生物学的脳を超並列コンピュータとみなす心の社会理論の開発に着手した。1986年にミンスキーは「心の社会」を出版し、「心は多くの小さなエージェントから形成され、それぞれは単独では心を持たない」と主張した。^[82]この理論は、いわゆる知性が、知性のない部分の相互作用の産物である可能性を説明しようとするものである。ミンスキーは、この理論に関するアイデアの最大の源は、ロボットアーム、ビデオカメラ、コンピュータを使用して子供用ブロックで構築するマシンを作成しようとした仕事から生まれたと述べている。^[83]

同様のモデル（生物学的脳を超並列コンピュータと見なす、つまり脳は独立したエージェントまたは半独立したエージェントの集合で構成されている）は、次のようにも説明されています。

• トーマス・R・ブレイクスリー、^[84]
• マイケル・S・ガザニガ^[85] [ ^86]
• ロバート・E・オーンスタイン、^[87]
• アーネスト・ヒルガード、^{[88] [89]}
• ミチオ・カク、^[90]
• ジョージ・イワノビッチ・グルジェフ、^[91]
• ニューロクラスター脳モデル^[92]

• Rodriguez, C.; Villagra, M.; Baran, B. (2008 年 8 月 29 日)。「ブール充足可能性のための非同期チーム アルゴリズム」。バイオにヒントを得たネットワーク、情報、コンピューティング システム モデル、2007 年。Bionetics 2007。第 2 版: 66– 69。doi :10.1109/ BIMNICS.2007.4610083。S2CID 15185219  。
• Sechin, A.; 写真測量における並列コンピューティング。GIM International。#1、2016、pp. 21–23。

• ローレンス・リバモア国立研究所: 並列コンピューティング入門
• 並列プログラムの設計と構築、Ian Foster 著
• インターネット並列コンピューティングアーカイブ