並列計算
並列計算（へいれつけいさん、テンプレート:Lang-en）は、コンピュータにおいて複数のプロセッサで1つのタスクを動作させること。並列コンピューティングや並列処理とも呼ばれる。問題を解く過程はより小さなタスクに分割できることが多い、という事実を利用して処理効率の向上を図る手法である。また、このために設計されたコンピュータを並列コンピュータという。ディープ・ブルーなどが有名。
関連する概念に並行計算（へいこうけいさん）があるが、並行計算は一つのタスクの計算を並列化することにとどまらず、複数の相互作用しうるタスクをスレッドなどをもちいて複数の計算資源にスケジューリングするといった、より汎用性の高い処理をさす。
特に、並列計算専用に設計されたコンピュータを用いずに、複数のパーソナルコンピュータやサーバ、スーパーコンピュータを接続することで並列計算を実現するものをコンピュータ・クラスターと呼ぶ。このクラスターをインターネットなどの広域ネットワーク上に分散させるものも、広義には並列計算に属すが、分散コンピューティングあるいはグリッド・コンピューティングと呼び、並列計算とは区別することが多い。
可能性と問題点
並列計算は、プロセッサ同士が独立して同時に仕事をするため、理想的な状況下ではプロセッサの回路規模を大きくすること無く、プロセッサの数に比例して性能が得られると考えられ、スーパーコンピュータなどで古くからとられた手法である。
しかし、問題点もある。並列計算を行う場合、もっともパフォーマンスを発揮するのはこれら複数のプロセッサが全て100%使い切られた時と考えられるが、従来のプログラムの多くは、複数のプロセッサを均等に全て使い切るようにはできておらず、また、そういったプログラミングは難しい。
買い物を例にとろう。まず買い物の前に、財布の中身を確かめなければならないし、足りなければ銀行で補充もしなければならない。その後はじめてお店にも行かなければならない。銀行に行くのと、お店に訪れるのは同時にできないし、財布の中身を確認してからでなければ、お店には行けない。プログラムもこれと似て、実行順番が変えられなかったり、同時に実行できなかったりする部分がどうしてもできてしまう。このため複数のプロセッサで同時に、かつ実行順番に依存しないようなプログラムのみでプログラムを構成することは難しい。
並列計算では、処理の"ある瞬間"ではそれぞれのプロセッサは実質まったく別に動作しており、そのため実行順番が全く問題にならないプログラムなら性能は引き出しやすい。しかし、先の例のように実行順番が強く束縛される場合は、あるプロセッサだけが働き、ほかのプロセッサはすることがなくなってしまうといった状態になり、性能が引き出しにくい。そのため，並列計算はそうでない場合と比べて性能を引き出すプログラミングが困難となる。
一般に、プログラムの処理が複数のプロセッサで均等に処理できる割合をプログラムの並列度と言うが、地球シミュレータの高い性能はこの並列度が他に比べて極めて高いことも重要な要因である。
以上のように、並列計算では高い性能を発揮する為にはソフトウェアの並列環境への最適化が重要な鍵となる（詳しくは並列化を参照）。
背景
従来、コンピュータソフトウェアは逐次的に計算されるものとして書かれてきた。問題を解くためにアルゴリズムが構築され、それによって逐次的に実行される命令列が生成される。その命令列は、コンピュータのCPU上で実行される。命令は一度に1つずつ実行される[1]。
一方並列計算では、複数の計算ノードが同時並行的に動作して問題を解く。問題は独立した部分に分割され、各計算ノードがアルゴリズムの一部を同時並行的に実行する。計算ノードの実体は様々であり、マルチプロセッサ型のコンピュータの各CPUだったり、ネットワーク上のコンピュータだったり、専用ハードウェアだったり、それらの組合せだったりする[1]。
1980年代から2004年まで、コンピュータの性能向上の主たる要因はクロック周波数の向上にあった。プログラムの実行時間は、命令数と1命令あたりの平均実行時間をかけたものに比例する。他の要因が全く変化しないと仮定すると、クロック周波数の向上によって1命令あたりの平均実行時間が減少する[2]。
一方で、マイクロプロセッサの消費電力は <math>P = C \times V^2 \times F</math> という式で与えられる。ここで、P は消費電力、C はクロックサイクル毎に切り替えられる静電容量（入力が変化するトランジスタの総数に比例）、V は電圧、F はプロセッサの周波数（正確には1秒あたりのサイクル数）である[3]。従って、クロック周波数が高くなると、プロセッサの消費電力も増大する。プロセッサの消費電力の増大は、インテルが2004年5月に開発中だったプロセッサをキャンセルした最大の理由であり、この時点がクロック周波数向上が性能向上の主たる要因となっていた時代の終焉であった[4] 。
ムーアの法則は、マイクロプロセッサでのトランジスタの実装密度が18カ月から24カ月毎に倍になるという経験則である。消費電力の問題は以前から指摘されていたが、ムーアの法則は未だに有効である。クロック周波数向上の時代が終わると共に、増大したトランジスタ数は周波数向上以外に利用されることになり、並列計算をマイクロプロセッサ上で実装する時代が到来した。
アムダールの法則とグスタフソンの法則
並列計算のプラットフォームにおけるアルゴリズムの性能は、そのアルゴリズムをどれだけ並列化できるかに依存する。そのため、1960年代にジーン・アムダールが定式化したアムダールの法則が重要となってくる[5]。それによると、プログラムの中の並列化できない部分が並列化による性能向上を制限する。大規模な工学的問題や数学問題には、一般に並列化可能な部分と並列化不可能な部分（逐次実行部分）がある。アムダールの法則によれば、以下のような関係が成り立つ。
- <math>S = \frac{1}{(1 - P)}</math>
ここで、S はプログラムの性能向上率（逐次実行版での実行時間を1としたときの倍率）、P は並列化可能な部分の比率である。逐次実行部分がプログラムの実行時間の10%を占めている場合、性能向上は10倍となり、それ以上の多くの計算ノードを追加しても意味はない。これにより、並列実行ユニットを追加して意味のある個数の上限が得られる。
グスタフソンの法則は、アムダールの法則とも密接に関連する計算機工学における法則である。グスタフソンの法則は以下の式で表される。
- <math>\displaystyle S(P) = P - \alpha(P-1)</math>
ここで、P はプロセッサ数、S は性能向上、<math>\alpha</math> は処理の並列化できない部分である[6]。アムダールの法則では問題のサイズが固定であり、逐次実行部分はプロセッサ数に依存しないと仮定されている。一方、グスタフソンの法則ではそのような仮定がない。
データ従属性
データ従属性（data dependency）を理解することが、並列アルゴリズムの実装法を知る基礎の一つとなる。計算と計算の間に従属関係があるということは実行の順序性が生じるということである。したがってプログラムは、従属性のある計算の連鎖のうちで最長のものより高速に実行することはできない（これをクリティカルパスと呼ぶ）。幸運なことに、多くのアルゴリズムにはそのような従属関係の長い連鎖は存在せず、計算のほとんどの部分は並列に実行できる。
Pi と Pj というプログラムの断片があるとする。Bernstein's conditions[7]は、2つの部分が独立していて並列に実行できる条件を示している。Pi への入力変数の集合を Ii で表し、Oi を出力変数の集合とする。Pj についても同様に表す。P i と Pj が独立であるための条件は以下の通りである。
- <math> I_j \cap O_i = \emptyset</math>
- <math> I_i \cap O_j = \emptyset</math>
- <math> O_i \cap O_j = \emptyset</math>
最初の条件が成り立たない場合、フロー従属性（flow dependency）が存在し、最初の文の結果を次の文で使う場合などに相当する。第二の条件は反従属性（anti-dependency）を意味し、最初の文が書き換える変数の元の値を次の文の式で必要としている場合などに相当する。第三の条件は出力従属性（output dependency）を表す。2つの変数が同じメモリ上の位置にある場合、それぞれの更新は元のプログラムの順序関係通りに行われる（後から書き込んだ方が残る）必要がある[8]。
例として以下の関数を考える。
1: function Dep(a, b) 2: c := a·b 3: d := 2·c 4: end function
Dep(a,b) の3行目は、2行目の前に実行できないし、並行して実行することもできない。何故なら3行目は2行目の結果を利用しているからである。これは上述の第一の条件に反しており、フロー従属性があると言える。
1: function NoDep(a, b) 2: c := a·b 3: d := 2·b 4: e := a+b 5: end function
こちらの例では、各命令には従属関係はないので、並列に実行可能である。
Bernstein’s conditions では、異なるプロセス間でメモリは共有されないと仮定している。そのため、アクセスの順序性を確保する手段として、セマフォなどの同期機構が必要となる。
競合状態、相互排他、同期、並列スローダウン
並列プログラムにおけるサブタスクをスレッドと呼ぶ。システムによってはさらに小さく軽量なスレッドであるファイバーを使っており、もっと大きな単位であるプロセスを使っているシステムもある。いずれにしても、並列プログラムのサブタスクをここではスレッドと呼ぶ。
スレッドは、スレッド間で共有している何らかの変数を更新することがよくある。2つのスレッドの命令実行順序は一定ではない。例えば、次のようなプログラムを考える。
| スレッド A | スレッド B |
| 1A: 変数 V を読む | 1B: 変数 V を読む |
| 2A: 変数 V の値に1を加算 | 2B: 変数 V の値に1を加算 |
| 3A 変数 V に値を書き戻す | 3B: 変数 V に値を書き戻す |
命令1Bが1Aと3Aの間に実行された場合、または命令1Aが1Bと3Bの間に実行された場合、このプログラムは間違ったデータを生成する。これを競合状態と呼ぶ。プログラマは相互排他のためにロックを使わなければならない。ロックとはプログラミング言語の構成要素であり、あるスレッドが変数の制御権を獲得すると、それがアンロックされるまで他のスレッドから読み書きできないようにする。ロックを獲得したスレッドはクリティカルセクション（プログラムの中で何らかの変数に排他的にアクセスする必要がある部分）を実行でき、それが完了したらそのデータをアンロックする。
従って、プログラムを正しく実行するには、上のプログラムを以下のようにロックを使って書き直す必要がある。
| スレッド A | スレッド B |
| 1A: 変数 V をロック | 1B: 変数 V をロック |
| 2A: 変数 V を読む | 2B: 変数 V を読む |
| 3A: 変数 V の値に1を加算 | 3B: 変数 V の値に1を加算 |
| 4A 変数 V に値を書き戻す | 4B: 変数 V に値を書き戻す |
| 5A: 変数 V をアンロック | 5B: 変数 V をアンロック |
一方のスレッドが変数 V をロックできた場合、もう一方は V がアンロックされるまで待たされることになる。これによってプログラムの正しい実行が保証される。ロックはプログラムの正しい実行の保証には必須だが、それによってプログラムの実行速度は大幅に低下する。
複数の変数のロックには複数のロックが必要であり、それによってデッドロックが発生する可能性が生じる。不可分なロックは複数の変数を一度にロックするものである。その場合、対象変数群の一部がロックできなければ、全体のロックができないと見なされる。個別にロックされる2つの変数をロックする必要のあるスレッドが2つ存在したとして、一方のスレッドが一方の変数だけをロックし、もう一方のスレッドがもう一方の変数だけをロックするという状況が発生しうる。このような場合、双方のスレッドはロックできていない変数をロックしようとして待ち続け、結果としてデッドロックとなる。
多くの並列プログラムでは、サブタスク群が同期して動作することを要求する。この用途で使われるものとしてバリアがある。バリアは一般にソフトウェアロックを使って実装される。その種のアルゴリズムとしてLock-freeとWait-freeアルゴリズムがある。これはロックもバリアも使わずに全てを実現するものである。ただし、実装は難しく、データ構造の設計を慎重に行う必要がある。
並列化によって必ず性能が向上するとは限らない。一般にタスクを細分化してスレッド数を増やしていくと、スレッド間の通信に費やす時間が増大していく。すると、ある時点で通信オーバーヘッドが処理時間を支配するようになり、それ以上の並列化（スレッド数の増加）は単に処理時間の遅延を招くことになる。この現象を並列スローダウンと呼ぶ。
細粒度並列性、粗粒度並列性、自明な並列性
アプリケーションは、スレッド間で同期や通信を必要とする頻度で分類できる。細粒度並列性（fine-graind parallelism）を持つものは、スレッド間で頻繁に通信する必要がある。粗粒度並列性（coarse-grained parallelism）を持つものはその逆である。自明な並列性を持つ（embarassingly parallel）ものは、ほとんど全くスレッド間の通信を必要とせず、したがって並列化も最も容易である。
一貫性モデル
並列プログラミング言語と並列コンピュータにはテンプレート:仮リンク（メモリモデルとも呼ぶ）が必須である。一貫性モデルとは、メモリ上の操作に関する規則を定義したものであり、どのように結果が生成されるかを定義したものである。
最初に定義された一貫性モデルは、レスリー・ランポートの逐次一貫性モデルである。逐次一貫性とは、並列プログラムを並列実行したときの結果と、それと等価な逐次プログラムの結果が同じという特性である。プログラムが逐次一貫性を持つとは、「…任意の実行の結果が、それを全プロセッサが逐次的順序で実行された場合と同じであり、その順序がプログラム内で指定された順序と同じである」ことを意味する[9]。
ソフトウェアトランザクショナルメモリは、一貫性モデルの典型例である。ソフトウェアトランザクショナルメモリは、データベース理論から不可分操作の概念を借り、それをメモリアクセスに適用したものである。
数学的にこれらのモデルを表現する方法はいくつか存在する。プロセス計算は並行性を扱う数学の一分野である。プロセス計算はさらにテンプレート:仮リンク、calculus of communicating systems、Communicating Sequential Processesなどに分類される。ペトリネットは一貫性モデルの定式化を試みた初期の例である。それに基づいて後にデータフロー理論が構築された。そして、データフローの考え方を物理的に実装したデータフロー・アーキテクチャが開発された。
フリンの分類
マイケル・J・フリンは、並列（および逐次）コンピュータ/プログラムの分類であるフリンの分類を提案した。フリンは命令列が単一か複数かという点と、その命令列（群）が扱うデータが単一か複数かによって4種類に分類した。
SISD（単一命令、単一データ）は、完全に逐次的なプログラムと等価である。SIMD（単一命令、複数データ）は同じ操作を多数のデータに対して行う場合を意味する。これは信号処理などで一般的である。MISD（複数命令、単一データ）はあまり使われない分類だが、フォールトトレラントシステムの冗長構成を指すことがある。シストリックアレイのようなアーキテクチャがこれに相当するが、実際の応用例は少ない。MIMD（複数命令、複数データ）は、ほとんどの並列プログラムに対応する。
デイビッド・パターソンとジョン・ヘネシーの著書には「もちろん一部のマシンはこれらの混成であるが、単純で分かりやすく、とりあえずの近似としては最適であるが故にこの分類が今も使われている」とある[10]。
並列性の分類
ビットレベルの並列性
1970年代のマイクロプロセッサの開発以来、コンピュータの主なアーキテクチャ上の進化はワードサイズ（プロセッサが一度に処理できるビット幅）を倍々にしていくことで成されてきた[11]。ワードを大きくすることで、従来のワードサイズでは多数の命令を必要としていた大きな変数の処理が、より少ない命令数で実行可能となる。例えば、8ビットのプロセッサで2つの16ビットの整数を加算する場合を考える。まず、2つのデータの下位8ビットを通常の加算命令で加算し、その後上位8ビットをキャリー付き加算命令で加算することで、下位8ビットで発生したキャリーを考慮する。つまり、8ビットプロセッサでは1つの演算に2つの命令を必要とし、16ビットプロセッサならそれを1命令で実行できる。
マイクロプロセッサの歴史を見れば、8ビット、16ビット、32ビットとワードサイズは大きくなっていった。32ビットとなった段階で汎用コンピュータのワードサイズの大型化は約20年間止まり、32ビットが標準的とされる時代が続いた。そして近年になってx86-64アーキテクチャが登場し、64ビットプロセッサが一般化した。
命令レベルの並列性
コンピュータプログラムは、基本的にプロセッサが実行すべき命令の列である。この命令列はプログラムの結果に影響を与えない形で並べ替え可能であり、同時並行的に実行できる命令毎にグループ化することができる。これを命令レベルの並列性と呼ぶ。命令レベルの並列性によるアーキテクチャの改良は1980年代中ごろから1990年代中ごろに盛んに行われた[12]。
最近のプロセッサは多段命令パイプラインを備えている。パイプラインの各ステージは、命令に対して行うべき異なる処理に対応している。N段のパイプラインを持つプロセッサでは、N個の命令について同時にそれぞれ異なる段階の処理をしていることになる。典型的なパイプラインの例としてRISCプロセッサの5段のパイプラインがある（各段は命令フェッチ、命令デコード、実行、メモリアクセス、ライトバック）。Pentium 4 は35段のパイプラインを持つ[13]。
パイプライン化による命令レベルの並列性だけでなく、同時に複数の命令を処理できるプロセッサもある。これをスーパースケーラプロセッサという。命令はデータ従属性がない場合にのみ、同時に実行可能なものとしてグループ化できる。
アウト・オブ・オーダー実行と命令レベルの並列性を実装する技法としては、スコアボードやトマスロのアルゴリズム（スコアボードと似ているがレジスタ・リネーミングを利用）が一般的である。
データ並列性
テンプレート:Main データ並列性はプログラムのループが本質的に備えている並列性であり、ループの各周回が各ノードで並列に処理されるようデータを配布する部分が中心となる。並列化されるループは、大きなデータ構造の各要素について似たような処理を行うものである[14]。科学技術計算にはデータ並列性があることが多い。
ループ伝搬依存（loop-carried dependency）とは、ループにおいて以前の周回の結果に依存して新たな周回の計算が行われる性質をいう。ループ伝搬依存があると、ループの並列化はできない。例えば、以下のフィボナッチ数の一部を計算する擬似コードを考えてみよう。
1: prev := 0 2: cur := 1 3: do: 4: PREV := CUR 5: CUR := CUR + PREV 6: while (CUR < 10)
このループでは、CUR が以前の CUR の値と PREV に依存しており、その値は周回ごとに再計算されるため、並列化できない。つまり、ある周回での計算は、それ以前の周回の計算結果に依存しているため、周回ごとに並列化することはできないのである。
問題が大きくなるほど、可能なデータ並列性も多くなる傾向がある[15]。
タスク並列性
テンプレート:Main タスク並列性は、「同じまたは異なるデータ群に関する全く異なる計算は並列に実行可能である」という並列プログラムの特性である[14]。データ並列性がほぼ同じ計算を並列に実行するのとは対照的である。問題が大きくなっても、それに比例してタスク並列性が高くなることはない[15]。
ハードウェア
メモリと通信
並列コンピュータの主記憶は、共有メモリ型（全プロセッサが単一の物理アドレス空間を共有する）と分散メモリ型（各プロセッサがローカルな独自の物理アドレス空間を持つ）に分けられる[16]。分散メモリは、メモリが論理的に分散しているためにそのように呼ばれるが、実際には物理的にも分散していることが多い。分散共有メモリはこの2つの方式を組み合わせたものであり、各プロセッサはローカルなメモリとローカルでないメモリの両方にアクセスできる。この場合、ローカルなメモリへのアクセスはローカルでないメモリへのアクセスよりも一般に高速である。
全主記憶に同じレイテンシおよび帯域幅でアクセスできるコンピュータアーキテクチャを UMA（Uniform Memory Access）と呼ぶ。これは共有メモリシステム（メモリが物理的に分散していない場合）しか実現できない。それ以外のアーキテクチャはNUMA（Non-Uniform Memory Access）と呼ぶ。分散メモリシステムはNUMAである。
コンピュータにはキャッシュメモリが使われていることが多く、（物理的にも論理的にも）プロセッサの近くに高速かつ小容量のメモリを配置し、主記憶の内容のコピーを一時的に保持する。共有メモリ型の並列コンピュータでは、主記憶上の同じアドレスの内容のコピーが複数のキャッシュメモリ上に存在する可能性があり、その内容が食い違うとプログラムの実行に支障が発生する。そのような問題への対処としてキャッシュコヒーレンシシステムがあり、プロセッサが常に最新の内容を得られるようキャッシュの内容を制御する。よく使われる方式としては、バススヌーピングがある。大型かつ高性能のキャッシュコヒーレンシシステムの設計は、コンピュータアーキテクチャの中でも非常に難しい問題である。そのため、共有メモリ型のシステムは分散メモリ型ほどスケーラブルではない[16]。
プロセッサ同士またはプロセッサとメモリの通信のハードウェア実装方式は様々であり、マルチポート型の共有メモリ、クロスバースイッチ、共有バス、スター型、リング型、ツリー型、ハイパーキューブ型、ファット・ハイパーキューブ型（ハイパーキューブの頂点に複数のノードが接続される形態）、メッシュ型などの様々なネットワーク構成のインターコネクト・ネットワークがある。
インターコネクト・ネットワークを使った並列コンピュータは、直接接続されていないノード間でメッセージパッシングできるように何らかのルーティング機構が必要となる。大規模なマルチプロセッサ機では、プロセッサ間の通信媒体は複数の階層を構成することもある。
並列コンピュータの分類
並列コンピュータは、ハードウェアのどのレベルで並列性をサポートするかによって大まかに分類できる。これは、基本計算ノード間の距離とも大まかに対応している。
なお、以下の分類は相互排他的ではない。例えば、対称型マルチプロセッサを複数束ねたクラスターというのもよくある構成である。
マルチコア・コンピューティング
テンプレート:Main マルチコアプロセッサは、複数の実行ユニット（コア）を持つプロセッサである。マルチコアとスーパースケーラは異なる概念である。どちらも複数の命令を同時並行的に実行可能だが、スーパースケーラが1つの命令ストリーム（スレッド）から複数の命令を取り出して実行するのに対して、マルチコアでは複数の命令ストリームから複数の命令を取り出して実行する。マルチコアの個々のコアがスーパースケーラになっていることもある。
初期の擬似マルチコア方式として同時マルチスレッディングがあった。この場合のプロセッサにはコア（実行ユニット）は1つしかないが、キャッシュミス時などコアが待ち状態になったときに、別のスレッドを実行できる。
インテルのマルチコアアーキテクチャは Core と Core 2 プロセッサから始まった。別の有名なマルチコアプロセッサとしては、ソニー・コンピュータエンタテインメントのPlayStation 3用に設計されたIBMのCellがある。
対称型マルチプロセッシング
テンプレート:Main 対称型マルチプロセッサ（SMP）は、複数個のプロセッサがメモリを共有し、バスで相互接続された形態のコンピュータである[17]。バスがボトルネックとなるため、スケーラビリティは制限される。そのため、SMPは一般に32プロセッサを越えることはない[18]。大型のキャッシュメモリを使って必要なバス帯域幅を低減して十分なメモリ帯域幅が確保できるなら、対称型マルチプロセッサは極めて費用対効果が高い[17]。
分散コンピューティング
テンプレート:Main 分散（メモリ）コンピュータは、処理ノード間をネットワークで相互接続した分散メモリ型のコンピュータシステムである。分散コンピュータはスケーラビリティが良い。
クラスターコンピューティング
クラスターは複数のコンピュータをネットワークで相互接続して、全体として1つのシステムとして機能させるものであり、多くの面で単一のコンピュータであるかのように見ることができる[19]。クラスターの構成は対称的である必要はないが、対称性がないと負荷分散が難しくなる。クラスター方式においても、システムリソースを共有する密結合型とリソースを共有しない疎結合型が存在する。
典型的なクラスター方式として Beowulf がある。これはTCP/IPイーサネットLANで普通のコンピュータ群を相互接続してクラスターを構成できる[20]。Beowulf の当初の開発者は Thomas Sterling と Donald Becker であった。
TOP500に掲載されているスーパーコンピュータの多くはクラスターである[21]。
超並列プロセッサ
超並列プロセッサ（MPP）は、非常に多数のプロセッサで構成される単一のコンピュータである。MPP はクラスターと多くの面で共通する特性を示すが、より大規模であり、100プロセッサよりずっと多数のプロセッサを装備していることが多い[22]。各CPUにはメモリがあり、オペレーティングシステムとアプリケーションのコピーがそこに格納される。CPU間の通信は非常に高速なインターコネクトで行われる[23]。
TOP500で2007年まで世界最高速のスーパーコンピュータとされていた Blue Gene/L はMPPである。
グリッド・コンピューティング
テンプレート:Main グリッド・コンピューティングは、並列計算の中でも最も分散された形態である。遠隔にあるコンピュータをインターネットで相互接続して構成され、1つの問題を共同して解く。インターネットは利用可能な帯域幅が低く、レイテンシが大きいため、自明な並列性を持つ問題に使われることが多い。グリッド・コンピューティングを利用した分散コンピューティングプロジェクトが数多くあり、SETI@homeやFolding@homeがよく知られている。
多くのグリッド・コンピューティングは、オペレーティングシステムとアプリケーションの間に特有のミドルウェアを置き、ネットワークリソースの管理やアプリケーション向けのインタフェースの標準化を行っている。よく知られたグリッド・コンピューティング用ミドルウェアとして、Berkeley Open Infrastructure for Network Computing (BOINC) がある。グリッド・コンピューティング用ソフトウェアでは、コンピュータが何もしていない時間を使うため、その時間を「スペアサイクル（spare cycles）」と呼ぶことが多い。
専用並列コンピュータ
並列計算では、ごく狭い用途に使われる専用並列機器も存在する。利用分野が限定されているというだけでなく、特定の並列問題のクラスしか解けないものが多い。
- FPGAと再構成型コンピューティング
- 再構成型コンピューティングとは、FPGAを汎用コンピュータのコプロセッサとして利用するものである。FPGA は、内部の配線を変更可能な集積回路である。
- FPGA内の配線は、VHDL や Verilog のようなハードウェア記述言語（HDL）でプログラム可能である。しかし、これらの言語でのプログラミングは手間がかかる。そこで、多くのプログラマが親しんでいるC言語のソースをHDLのソースに変換するソフトウェアがいくつも開発されている。例えば、Mitrion-C、Impluse C、DIME-C、Handel-C などがある。
- AMDはHyperTransport技術をオープン規格としたため、サードパーティがこれを再構成型コンピューティングを使った高性能計算に応用している。
- GPU上での汎用処理（GPGPU）
- GPGPU（General-purpose computing on GPU）は、情報工学での新たな傾向である[24]。GPU はコンピュータグラフィックス処理に最適化されたコプロセッサであり、その処理は、線形代数行列演算をデータ並列で処理する部分がほとんどである。
- CUDAはGPGPU用プログラミング言語であり、NVIDIAが同社のグラフィックスカード向けに開発した。CTM（Close to Metal）はAMD/ATIのGPGPU用APIである。他にも、BrookGPU、PeakStream、RapidMind などのGPGPU用プログラミング言語がある。
- AMD Streamは、AMD社のGPGPU専用カードである。
- NVIDIA Tesla は、NVIDIA初のGPGPU専用カードである。
- ASIC（Application Specific Integrated Circuit）
- ASICを使って並列処理を行おうとする試みがいくつか行われている[25][26][27]。
- ASIC は本質的に特定用途を想定して設計されるため、その用途向けに完全に最適化される。結果として、その用途に関しては汎用コンピュータより高速に処理できることが多い。しかし、ASIC作成にはフォトマスクが必要であり、その設計は非常に費用がかかる。1つのマスクはアメリカ合衆国ドルで百万ドル以上になる[28]（設計ルールが小さくなるほど、フォトマスク開発には費用が多くかかる）。一方ムーアの法則に従って、汎用コンピュータの性能は急激に向上しているため、1世代か2世代のプロセッサの進歩によってASICに追いつくという傾向がある。初期投資が大きいこと、汎用コンピュータに対する優位性が長続きしないことから、ASIC を使った並列計算はあまり現実的でないことが多い。
- ベクトル計算機ファイル:Cray-1-p1010221.jpgCray-1は、最も有名なベクトル計算機である。
- ベクトル計算機とは、多数のデータ群に対して同じ命令を実行できるCPUまたはコンピュータシステムである。数値の配列またはベクトルに対して高度な操作を実行できる。例えば、A、B、C がそれぞれ64個の64ビット浮動小数点数の配列としたとき、<math>A = B \times C</math> を一度に行う[29]。ベクトル計算機は、フリンの分類におけるSIMDと密接に関連している[29]。
- 1970年代から1980年代にかけて、クレイはベクトル計算機で有名になった。しかし、最近ではベクトル計算機という呼び方をすることは少なくなっている。最近のプロセッサの命令セットには、AltiVec や Streaming SIMD Extensions (SSE) などのベクトル処理命令が含まれている。
ソフトウェア
テンプレート:Main 並列型コンピュータでのプログラミング向けに、プログラミング言語、ライブラリ、API、並列プログラミングモデルが生み出されてきた。
それらは、前提とするメモリアーキテクチャ（共有メモリ、分散メモリ、分散共有メモリ）によって分類できる。共有メモリ型プログラミング言語は、共有メモリ上の変数を更新することで相互の通信を実現している。分散メモリ型ではメッセージパッシングが使われる。共有メモリ型APIとしては、POSIXスレッドと OpenMP が広く使われている。一方メッセージパッシング型のAPIとしては、Message Passing Interface (MPI) がよく使われている。
自動並列化
逐次型プログラムのコンパイラによる自動並列化は、並列計算の最終目標の1つでもある。コンパイラ研究者が長年に渡って研究しているが、限定的な成果しか得られていない。
一般に使われている並列プログラミング言語では、プログラマが並列化する部分を明記するか、せいぜい部分的な自動並列化ができる程度である。並列化を全く明記する必要のない言語も少数ながら存在し、SISAL、Parallel Haskell、Mitrion-C（FPGA用）などがあるが、これらはいずれも広く普及しているとは言い難い。
アプリケーション・チェックポインティング
コンピュータが大規模かつ複雑になると、平均故障間隔は小さくなる。並列計算では、多数のプロセッサを使っても長時間かかるような処理を行うことがある。このため、アプリケーションの実行中の状態（全てのリソース確保状況や変数群の状態など）をコアダンプのような形で定期的に保持しておき、障害が発生したときに最初から処理をやり直すのではなく、途中までの保存された状態から再開できるようにする必要がある。この技法をアプリケーション・チェックポインティングと呼ぶ。時には数ヶ月もかかる処理もあり、その場合アプリケーション・チェックポインティングは非常に重要となる。また、この技法はプロセスマイグレーションにも応用できる。
歴史
真の並列性（MIMD）という概念の起源は、イタリア人数学者ルイジ・メナブレアの "Sketch of the Analytic Engine Invented by Charles Babbage" に遡る[30][31]。1954年、IBMが IBM 704 をリリースしたが、この開発プロジェクトにはジーン・アムダールもアーキテクトとして参加していた。このコンピュータは完全自動浮動小数点演算が行える初の商用マシンとなった[32]。1958年、IBMの研究者ジョン・コックと Daniel Slotnick は数値計算における並列性の利用について初めて話し合っている[33]。1962年、バロース社は4プロセッサのコンピュータ D825 を発表した。これは、クロスバースイッチ経由で最大16個のメモリモジュールにアクセス可能であった[34]。1967年、アムダールと Slotnick は、アメリカ情報処理学会連合会の会議で並列処理の可能性について公開討論を行った[33]。アムダールはこのとき、後に「アムダールの法則」と呼ばれる考え方に基づいて、並列性の限界について述べた。
1969年、ハネウェルが最初の Multics システムを発表した。これは、最大8プロセッサまでが並列に動作可能な対称型マルチプロセッサシステムであった[33]。カーネギーメロン大学では1970年代に C.mmp というマルチプロセッサ開発プロジェクトが行われ、大規模と言える初のマルチプロセッサであった[31]。同期機能を持ったキャッシュ（MESIプロトコル参照）を持ったプロセッサ群をバスで接続する形態のマルチプロセッサ機としては、1984年の Synapse N+1 が最初である[31]。
SIMD型並列コンピュータの起源は1970年代に遡る。初期のSIMD型コンピュータは、命令列を実行するときのプロセッサの制御装置におけるゲート遅延への対策という意味合いが強かった[35]。1964年、Slotnick はローレンス・リバモア国立研究所向けの超並列コンピュータ構築を提案している[33]。その提案に対してアメリカ空軍が資金を提供し、それが最初のSIMD並列マシン ILLIAC IV となった[33]。設計の鍵となったのは、最大256プロセッサによる高い並列性であり、それらプロセッサが後にベクトル計算機と呼ばれる方式で大きなデータを処理するものであった。しかし、プロジェクトは11年もかけて当初の4分の1の規模までしか構築できず、事前の見積もりの4倍の費用がかかってしまった[36]。1976年にアプリケーションを実行可能になったが、既に発売されていた商用のスーパーコンピュータ Cray-1 に性能で負けていた。
関連項目
- 並列ランダムアクセス機械 (PRAM) - 並列計算向け計算模型
- マルチプロセッシング
- 排他制御
- 並列化
- コンピュータ・クラスター
- スーパーコンピュータ
- サーバファーム
脚注
外部リンク
- テンプレート:Dmoz
- Introduction to Parallel Computing ローレンス・リバモア国立研究所
- Designing and Building Parallel Programs by Ian Foster
- Internet Parallel Computing Archive
- Parallel processing topic area at IEEE Distributed Computing Online
- Parallel Computing Works フリーなオンライン書籍
- Frontiers of Supercomputing フリーなオンライン書籍
- Multiprocessing Traps & Pitfalls 開発者向けテンプレート:並列コンピューティング
- ↑ 1.0 1.1 テンプレート:Cite web
- ↑ John L. Hennessy and David A. Patterson. Computer Architecture: A Quantitative Approach. 3rd edition, 2002. Morgan Kaufmann, ISBN 1558607242. Page 43.
- ↑ J. M. Rabaey. Digital Integrated Circuits. Prentice Hall, 1996.
- ↑ Laurie J. Flynn. Intel Halts Development of 2 New Microprocessors. New York Times, 2004年5月8日
- ↑ G. Amdahl. The validity of the single processor approach to achieving large-scale computing capabilities. In Proceedings of AFIPS Spring Joint Computer Conference, pages 483–485, Atlantic City, N.J., April 1967. AFIPS Press.
- ↑ Reevaluating Amdahl's Law Communications of the ACM 31(5), 1988. pp. 532-533
- ↑ A. J. Bernstein, "Program Analysis for Parallel Processing,' IEEE Trans. on Electronic Computers, EC-15, Oct 66, 757-762.
- ↑ K. Hwang and F. A. Briggs. Computer architecture and parallel processing. McGraw-Hill, 1984.
- ↑ Leslie Lamport. "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", IEEE Transactions on Computers, C-28,9 (September 1979), 690–691.
- ↑ Patterson and Hennessy, pg 748
- ↑ David E. Culler, Jaswinder Pal Singh, Anoop Gupta. Parallel Computer Architecture - A Hardware/Software Approach. Morgan Kaufmann Publishers, 1999. ISBN 1558603433, pg 15
- ↑ Culler et al, pg 15
- ↑ Yale Patt. "The Microprocessor Ten Years From Now: What Are The Challenges, How Do We Meet Them? (wmv). カーネギーメロン大学での講義（2004年4月）、2007年11月7日閲覧
- ↑ 14.0 14.1 Culler et al, pg 124
- ↑ 15.0 15.1 Culler et al, pg 125
- ↑ 16.0 16.1 Patterson and Hennessy, pg 713
- ↑ 17.0 17.1 Hennessy and Patterson, pg 549
- ↑ Patterson and Hennessy, pg 714
- ↑ What is clustering? Webopedia computer dictionary. 2007年11月7日閲覧
- ↑ Beowulf definition. PC Magazine. 2007年11月7日閲覧
- ↑ Architecture share for 06/2007. TOP500 Supercomputing Sites. ここでは、74.60%のマシンがクラスターとされている。2007年11月7日閲覧
- ↑ Hennessy and Patterson, pg 537
- ↑ MPP Definition. PC Magazine. 2007年11月7日閲覧
- ↑ SIGGRAPH 2005 - GPUをCPU的に活用するGPGPUの可能性 マイコミジャーナル、2005年9月6日。2008年4月5日閲覧
- ↑ Oleg Maslennikov (2002). Systematic Generation of Executing Programs for Processor Elements in Parallel ASIC or FPGA-Based Systems and Their Transformation into VHDL-Descriptions of Processor Element Control Units. Lecture Notes in Computer Science, 2328/2002:272.
- ↑ Y. Shimokawa, Y. Fuwa, N. Aramaki. A parallel ASIC VLSI neurocomputer for a large number of neurons and billion connections per second speed. IEEE International Joint Conference on Neural Networks, 1991年11月18日-11月21日. 3: 2162–2167.
- ↑ K.P. Acken, M.J. Irwin, R.M. Owens. A Parallel ASIC Architecture for Efficient Fractal Image Coding. The Journal of VLSI Signal Processing, July 1998, 19(2):97–113(17)
- ↑ Andrew B. Kahng. "Scoping the Problem of DFM in the Semiconductor Industry." University of California, San Diego. 2004年6月21日
- ↑ 29.0 29.1 Patterson and Hennessy, pg 751
- ↑ L.F. Menabrea, Sketch of the Analytic Engine Invented by Charles Babbage. Bibliothèque Universelle de Genève, 1842. 2007年11月7日閲覧
- ↑ 31.0 31.1 31.2 Patterson and Hennessy, pg 753
- ↑ テンプレート:Cite web
- ↑ 33.0 33.1 33.2 33.3 33.4 テンプレート:Cite web
- ↑ テンプレート:Cite web
- ↑ Patterson and Hennessy, pg 749
- ↑ Patterson and Hennessy, pgs 749–750: 「いくつかの有益な技術を生み出したが、ILLIAC IV はコンピュータとしては失敗であった。当初計画した規模の4分の1しか構築できなかったにも関わらず、1966年に800万ドルと見積もられていた費用は1972年には3100万ドルにまで膨れ上がった。（中略）おそらく最も悪名高いスーパーコンピュータであろう。プロジェクトは1965年に開始され、実際のアプリケーションが実行可能になったのは1976年だった」
