並列計算のソースを表示

あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
あなたのIPアドレスは、すべてのウィキメディア財団のウィキで投稿ブロックされているIPアドレス範囲に入っています。
ブロックは‪EPIC‬により行われました。ブロックの理由はOpen proxy/Webhost: See the help page if you are affectedです。
ブロック開始日時: 2024年7月2日 (火) 08:48
ブロック解除予定: 2025年7月2日 (水) 08:48
あなたの現在のIPアドレスは206.189.44.186です。ブロックされている範囲は206.189.32.0/20です。
お問い合わせの際は、上記の詳細情報をすべて含めてください。
もし、この投稿ブロックが錯誤によるものだと考えているのであれば、グローバル方針のNo open proxies（公開プロキシの規制）で詳細情報などが入手できます。あるいは、投稿ブロックに関して議論したい場合は、メタウィキでブロックの見直しを依頼してください。スチュワード用 VRT キューにメールを送信する (宛先: stewards@wikimedia.org) こともできます。
このページのソースの閲覧やコピーができます。
{{出典の明記|date=2018年10月}}
'''並列計算'''（へいれつけいさん、{{lang-en|parallel computing}}）は、[[コンピュータ]]において特定の処理をいくつかの独立した小さな処理に細分化し、複数の処理装置（[[プロセッサ]]）上でそれぞれの処理を同時に実行させることである<ref>[http://ossforum.jp/node/578 I-10-8. 並列処理プログラミングの基本、並列化処理 | 日本OSS推進フォーラム]</ref>。'''並列コンピューティング'''や'''並列処理'''ともいう。

== 概要 ==
大きな問題を解いたり、大量のデータを処理したりする過程は、より小さなサブタスクやサブデータグループの処理に分割できることが多い、という事実を利用して単位時間あたりの処理効率（[[スループット]]）の向上を図る手法である。

並列処理（並列計算）は[[スーパーコンピュータ]]では以前から採られている手法である。スーパーコンピュータの高い性能は、プロセッサ数やノード数がパーソナルコンピュータに比べて極めて多く、並列処理性能が高いことで実現している。

並列計算のために設計されたコンピュータは並列コンピュータという。並列コンピュータは当初[[スーパーコンピュータ]]などの高価で大規模なシステムのみに見られる設計だったが、[[パーソナルコンピュータ]]や[[携帯機器]]でも[[CPU]]を[[マルチコア]]化し並列処理をさせることが当たり前になってきた。CPUのクロック周波数を上げることで処理性能向上させることには限界や問題が見えてきたからこの手法が採用されるようになった。

また並列処理に特化した[[コプロセッサ]]である[[Graphics Processing Unit|GPU]]も、個人が（比較的気軽に）購入できる価格帯で販売されるようになってきており、PCに後付で搭載する形での使用も広まっている。GPUは当初は主に、コンピュータゲームの[[3DCG]][[レンダリング (コンピュータ)|レンダリング]]などの[[画像処理]]に使われていたので「GPU」と呼ばれることになったが、実際には並列処理全般に使うことができるものであり、こうした使用法を[[GPGPU]]といい、今では[[ディープラーニング]]や[[暗号通貨]]の[[マイニング (仮想通貨)|マイニング]]など、現実的な時間内に処理しようとすると並列処理が必要となるさまざまな用途で使われるようになっている。

並列処理の歴史を遡ると、1958年にIBMの研究者[[ジョン・コック]]と Daniel Slotnick は数値計算における並列性の利用について初めて話し合っている<ref name=G_Wilson>{{cite web | url = http://ei.cs.vt.edu/~history/Parallel.html | title = The History of the Development of Parallel Computing | accessdate = 2008年1月8日 | first = Gregory V. | last = Wilson | date = 1994年}}</ref>。1962年には、[[バロース]]社が4プロセッサのコンピュータ D825 を発表した。→[[#歴史]]

関連する概念に'''[[並行計算]]'''（へいこうけいさん）があるが、並行計算は一つのタスクの計算を並列化することにとどまらず、複数の相互作用しうるタスクを、[[プロセス]]や[[スレッド (コンピュータ)|スレッド]]などをもちいて単一または複数の計算資源にスケジューリングするといった、より汎用性の高い処理をさす。並列計算は物理的に計算資源が複数なければ効果が得られないが、並行計算はたとえ計算資源が1つだけだったとしても、[[マルチタスク]]に対応した[[オペレーティングシステム]]がプロセッサ時間をスライスして各タスクの処理に割り当てることで効果が得られる。

特に、並列計算専用に設計されたコンピュータを用いずに、複数の[[パーソナルコンピュータ]]や[[サーバ]]、[[スーパーコンピュータ]]を接続することで並列計算を実現するものを[[コンピュータ・クラスター]]と呼ぶ。このクラスターを[[インターネット]]などの広域ネットワーク上に分散させるものも、広義には並列計算に属すが、[[分散コンピューティング]]あるいは[[グリッド・コンピューティング]]と呼び、並列計算とは区別することが多い。

== 背景 ==
従来、コンピュータソフトウェアは逐次的に計算されるものとして書かれてきた。問題を解くために[[アルゴリズム]]が構築され、それによって逐次的に実行される命令列が生成される。その命令列は、コンピュータの[[CPU]]上で実行される。命令は一度に1つずつ実行される<ref name="llnltut">{{cite web |url= http://www.llnl.gov/computing/tutorials/parallel_comp/ |title=Introduction to Parallel Computing |accessdate=2007年11月9日 |author=Blaise Barney |publisher=Lawrence Livermore National Laboratory}}</ref>。

一方並列計算では、複数の計算ノードが同時並列的に動作して問題を解く。問題は独立した部分に分割され、各計算ノードがアルゴリズムの一部を同時並列的に実行する。計算ノードの実体は様々であり、マルチプロセッサ型のコンピュータの各CPUだったり、ネットワーク上のコンピュータだったり、専用ハードウェアだったり、それらの組合せだったりする<ref name="llnltut" />。

1980年代から2004年まで、コンピュータの性能向上の主たる要因はクロック周波数の向上にあった。プログラムの実行時間は、命令数と1命令あたりの平均実行時間をかけたものに比例する。他の要因が全く変化しないと仮定すると、クロック周波数の向上によって1命令あたりの平均実行時間が減少する<ref>[[ジョン・ヘネシー|John L. Hennessy]] and [[デイビッド・パターソン (計算機科学者)|David A. Patterson]]. Computer Architecture: A Quantitative Approach. 3rd edition, 2002. Morgan Kaufmann, ISBN 1558607242. Page 43.</ref>。

一方で、[[マイクロプロセッサ]]の[[消費電力]]は <math>P = C \times V^2 \times F</math> という式で与えられる。ここで、P は消費電力、C はクロックサイクル毎に切り替えられる[[静電容量]]（入力が変化するトランジスタの総数に比例）、V は[[電圧]]、F はプロセッサの周波数（正確には1秒あたりのサイクル数）である<ref>J. M. Rabaey. Digital Integrated Circuits. Prentice Hall, 1996.</ref>。従って、クロック周波数が高くなると、プロセッサの消費電力も増大する。プロセッサの消費電力の増大は、[[インテル]]が2004年5月に開発中だったプロセッサをキャンセルした最大の理由であり、この時点がクロック周波数向上が性能向上の主たる要因となっていた時代の終焉であった<ref>Laurie J. Flynn. [http://www.nytimes.com/2004/05/08/business/08chip.html?ex=1399348800&en=98cc44ca97b1a562&ei=5007 Intel Halts Development of 2 New Microprocessors]. ''New York Times'', [[2004年]][[5月8日]]</ref> 。

[[ムーアの法則]]は、マイクロプロセッサでのトランジスタの実装密度が18ヶ月から24ヶ月毎に倍になるという経験則である。消費電力の問題は以前から指摘されていたが、ムーアの法則は未だに{{いつ|date=2024年9月}}有効である。しかしムーアの法則の一部とも言える[[デナード則#2006年ごろのデナード則の崩壊|デナード則の一部の崩壊]]が、前述のようにクロック周波数向上の時代の終焉であった。そして残った微細化により増大するトランジスタ数の有効利用として、並列計算をマイクロプロセッサ上で実装する時代が到来した。具体的には、本格的な[[マルチコア]]の時代が訪れた。

=== アムダールの法則とグスタフソンの法則 ===
並列計算のプラットフォームにおけるアルゴリズムの性能は、そのアルゴリズムをどれだけ[[並列化]]できるかに依存する。そのため、1960年代に[[ジーン・アムダール]]が定式化した[[アムダールの法則]]が重要となってくる<ref>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.</ref>。それによると、プログラムの中の並列化できない部分が並列化による性能向上を制限する。大規模な工学的問題や数学問題には、一般に並列化可能な部分と並列化不可能な部分（逐次実行部分）がある。[[アムダールの法則]]によれば、以下のような関係が成り立つ。

:<math>S = \frac{1}{(1 - P)}</math>

ここで、Sはプログラムの性能向上率（逐次実行版での実行時間を1としたときの倍率）、Pは並列化可能な部分の比率である。逐次実行部分がプログラムの実行時間の10%を占めている場合、性能向上は10倍となり、それ以上の多くの計算ノードを追加しても意味はない。これにより、並列実行ユニットを追加して意味のある個数の上限が得られる。

[[画像:Amdahl_law1.png|thumb|400px|[[アムダールの法則]]の概念を図示したもの。タスクが独立した二つの部分AとBから構成されている。Bは計算時間の約30%を占めている。がんばってBを改良して5倍の性能にしても、全体としての性能向上は少しでしかない。逆にAを2倍の性能に改良した方が全体性能はより向上する。]]

[[グスタフソンの法則]]は、アムダールの法則とも密接に関連する[[計算機工学]]における法則である。グスタフソンの法則は以下の式で表される。

:<math>\displaystyle S(P) = P - \alpha(P-1)</math>

ここで、Pはプロセッサ数、Sは性能向上、<math>\alpha</math> は処理の並列化できない部分である<ref>[http://www.scl.ameslab.gov/Publications/Gus/AmdahlsLaw/Amdahls.html Reevaluating Amdahl's Law] {{webarchive|url=https://web.archive.org/web/20070927040654/http://www.scl.ameslab.gov/Publications/Gus/AmdahlsLaw/Amdahls.html |date=2007年9月27日 }} Communications of the ACM 31(5), 1988. pp. 532-533</ref>。アムダールの法則では問題のサイズが固定であり、逐次実行部分はプロセッサ数に依存しないと仮定されている。一方、グスタフソンの法則ではそのような仮定がない。

=== データ従属性 ===
[[データ従属性]] (data dependency) を理解することが、[[並列アルゴリズム]]の実装法を知る基礎の一つとなる。計算と計算の間に従属関係があるということは実行の順序性が生じるということである。したがってプログラムは、従属性のある計算の連鎖のうちで最長のものより高速に実行することはできない（これを[[クリティカルパス]]と呼ぶ）。幸運なことに、多くのアルゴリズムにはそのような従属関係の長い連鎖は存在せず、計算のほとんどの部分は並列に実行できる。

P<sub>i</sub>とP<sub>j</sub>というプログラムの断片があるとする。Bernstein's conditions<ref> A. J. Bernstein, "Program Analysis for Parallel Processing,' IEEE Trans. on Electronic Computers, EC-15, Oct 66, 757-762.</ref>は、2つの部分が独立していて並列に実行できる条件を示している。P<sub>i</sub>への入力変数の集合をI<sub>i</sub>で表し、O<sub>i</sub>を出力変数の集合とする。P<sub>j</sub>についても同様に表す。P <sub>i</sub>とP<sub>j</sub>が独立であるための条件は以下の通りである。

* <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つの変数が同じメモリ上の位置にある場合、それぞれの更新は元のプログラムの順序関係通りに行われる（後から書き込んだ方が残る）必要がある<ref>K. Hwang and F. A. Briggs. Computer architecture and parallel processing. McGraw-Hill, 1984.</ref>。

例として以下の関数を考える。

 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つのスレッドの命令実行順序は一定ではない。例えば、次のようなプログラムを考える。

{| class="wikitable" 
|-
|スレッド A
|スレッド B
|-
|1A: 変数 V を読む
|1B: 変数 V を読む
|-
|2A: 変数 V の値に1を加算
|2B: 変数 V の値に1を加算
|-
|3A 変数 V に値を書き戻す
|3B: 変数 V に値を書き戻す     
|}

命令1Bが1Aと3Aの間に実行された場合、または命令1Aが1Bと3Bの間に実行された場合、このプログラムは間違ったデータを生成する。これを[[競合状態]]と呼ぶ。プログラマは[[排他制御|相互排他]]のために[[ロック (情報工学)|ロック]]を使わなければならない。ロックとはプログラミング言語の構成要素であり、あるスレッドが変数の制御権を獲得すると、それがアンロックされるまで他のスレッドから読み書きできないようにする。ロックを獲得したスレッドは[[クリティカルセクション]]（プログラムの中で何らかの変数に排他的にアクセスする必要がある部分）を実行でき、それが完了したらそのデータをアンロックする。

従って、プログラムを正しく実行するには、上のプログラムを以下のようにロックを使って書き直す必要がある。

{| class="wikitable" 
|-
|スレッド 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) ものは、ほとんど全くスレッド間の通信を必要とせず、したがって並列化も最も容易である。

=== 一貫性モデル ===
[[画像:Leslie Lamport.jpg|right|upright|thumbnail|[[レスリー・ランポート]]は初めて[[逐次一貫性]]の概念を定義した。また、[[LaTeX]]の開発でも知られている。]]

{{Main|一貫性モデル (ソフトウェア)}}

並列プログラミング言語と並列コンピュータには{{仮リンク|一貫性モデル|en|Consistency model}}（メモリモデルとも呼ぶ）が必須である。一貫性モデルとは、[[記憶装置|メモリ]]上の操作に関する規則を定義したものであり、どのように結果が生成されるかを定義したものである。

最初に定義された一貫性モデルは、[[レスリー・ランポート]]の[[逐次一貫性]]モデルである。逐次一貫性とは、並列プログラムを並列実行したときの結果と、それと等価な逐次プログラムの結果が同じという特性である。プログラムが逐次一貫性を持つとは、「…任意の実行の結果が、それを全プロセッサが逐次的順序で実行された場合と同じであり、その順序がプログラム内で指定された順序と同じである」ことを意味する<ref>Leslie Lamport. "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", IEEE Transactions on Computers, C-28,9 (September 1979), 690–691.</ref>。

[[ソフトウェアトランザクショナルメモリ]]は、一貫性モデルの典型例である。ソフトウェアトランザクショナルメモリは、[[データベース管理システム|データベース理論]]から[[不可分操作]]の概念を借り、それをメモリアクセスに適用したものである。

数学的にこれらのモデルを表現する方法はいくつか存在する。[[プロセス計算]]は並行性を扱う数学の一分野である。プロセス計算はさらに{{仮リンク|アンビエント計算|en|Ambient calculus}}、[[:en:calculus of communicating systems|calculus of communicating systems]]、[[Communicating Sequential Processes]]などに分類される。[[ペトリネット]]は一貫性モデルの定式化を試みた初期の例である。それに基づいて後に[[データフロー]]理論が構築された。そして、データフローの考え方を物理的に実装した[[データフロー#ハードウェアアーキテクチャ|データフロー・アーキテクチャ]]が開発された。

=== フリンの分類 ===
マイケル・J・フリンは、並列（および逐次）コンピュータ/プログラムの分類である[[フリンの分類]]を提案した。フリンは命令列が単一か複数かという点と、その命令列（群）が扱うデータが単一か複数かによって4種類に分類した。

[[SISD]]（単一命令、単一データ）は、完全に逐次的なプログラムと等価である。[[SIMD]]（単一命令、複数データ）は同じ操作を多数のデータに対して行う場合を意味する。これは[[信号処理]]などで一般的である。[[MISD]]（複数命令、単一データ）はあまり使われない分類だが、[[フォールトトレラントシステム]]の冗長構成を指すことがある。[[シストリックアレイ]]のようなアーキテクチャがこれに相当するが、実際の応用例は少ない。MIMD（複数命令、複数データ）は、ほとんどの並列プログラムに対応する。

[[デイビッド・パターソン (計算機科学者)|デイビッド・パターソン]]と[[ジョン・ヘネシー]]の著書には「もちろん一部のマシンはこれらの混成であるが、単純で分かりやすく、とりあえずの近似としては最適であるが故にこの分類が今も使われている」とある<ref>Patterson and Hennessy, pg 748</ref>。

== 並列性の分類 ==
=== ビットレベルの並列性 ===
1970年代の[[マイクロプロセッサ]]の開発以来、コンピュータの主なアーキテクチャ上の進化は[[ワード]]サイズ（プロセッサが一度に処理できるビット幅）を倍々にしていくことで成されてきた<ref>David E. Culler, Jaswinder Pal Singh, Anoop Gupta. Parallel Computer Architecture - A Hardware/Software Approach. Morgan Kaufmann Publishers, 1999. ISBN 1558603433, pg 15</ref>。ワードを大きくすることで、従来のワードサイズでは多数の命令を必要としていた大きな変数の処理が、より少ない命令数で実行可能となる。例えば、8ビットのプロセッサで2つの16ビットの[[整数]]を加算する場合を考える。まず、2つのデータの下位8ビットを通常の加算命令で加算し、その後上位8ビットをキャリー付き加算命令で加算することで、下位8ビットで発生したキャリーを考慮する。つまり、8ビットプロセッサでは1つの演算に2つの命令を必要とし、16ビットプロセッサならそれを1命令で実行できる。

マイクロプロセッサの歴史を見れば、8ビット、16ビット、32ビットとワードサイズは大きくなっていった。32ビットとなった段階で汎用コンピュータのワードサイズの大型化は約20年間止まり、32ビットが標準的とされる時代が続いた。そして近年になって[[x64|x86-64]]アーキテクチャが登場し、[[64ビット]]プロセッサが一般化した。

=== 命令レベルの並列性 ===
{{main|命令レベルの並列性}}
[[画像:Fivestagespipeline.png|thumb|300px|典型的な[[RISC]]における5段階のパイプライン（IF = 命令フェッチ、ID = 命令デコード、EX = 実行、MEM = メモリアクセス、WB = レジスタライトバック）]]
[[画像:Superscalarpipeline.png|thumb|300px|5段パイプラインのスーパースケーラプロセッサ。一度に2つの命令を実行可能。各段で2つの命令を処理でき、全体としては同時並列的に最大10個の命令を処理できる。]] 
コンピュータプログラムは、基本的にプロセッサが実行すべき命令の列である。この命令列はプログラムの結果に影響を与えない形で[[アウト・オブ・オーダー実行|並べ替え可能]]であり、同時並列的に実行できる命令毎にグループ化することができる。これを命令レベルの並列性と呼ぶ。命令レベルの並列性によるアーキテクチャの改良は1980年代中ごろから1990年代中ごろに盛んに行われた<ref>Culler et al, pg 15</ref>。

最近のプロセッサは多段[[命令パイプライン]]を備えている。パイプラインの各ステージは、命令に対して行うべき異なる処理に対応している。N段のパイプラインを持つプロセッサでは、N個の命令について同時にそれぞれ異なる段階の処理をしていることになる。典型的なパイプラインの例としてRISCプロセッサの5段のパイプラインがある（各段は命令フェッチ、命令デコード、実行、メモリアクセス、ライトバック）。[[Pentium 4]] は35段のパイプラインを持つ<ref>Yale Patt.  "[http://users.ece.utexas.edu/~patt/Videos/talk_videos/cmu_04-29-04.wmv The Microprocessor Ten Years From Now: What Are The Challenges, How Do We Meet Them?] {{webarchive|url=https://web.archive.org/web/20080414141000/http://users.ece.utexas.edu/~patt/Videos/talk_videos/cmu_04-29-04.wmv |date=2008年4月14日 }} (wmv). [[カーネギーメロン大学]]での講義（2004年4月）、[[2007年]][[11月7日]]閲覧</ref>。

パイプライン化による命令レベルの並列性だけでなく、同時に複数の命令を処理できるプロセッサもある。これを[[スーパースケーラ]]プロセッサという。命令は[[データ従属性]]がない場合にのみ、同時に実行可能なものとしてグループ化できる。

アウト・オブ・オーダー実行と命令レベルの並列性を実装する技法としては、[[Scoreboarding|スコアボード]]や[[Tomasuloのアルゴリズム|トマスロのアルゴリズム]]（スコアボードと似ているが[[レジスタ・リネーミング]]を利用）が一般的である。

=== データ並列性 ===
{{main|データ並列性}}
データ並列性は[[ループ (プログラミング)|プログラムのループ]]が本質的に備えている並列性であり、ループの各周回が各ノードで並列に処理されるようデータを配布する部分が中心となる。並列化されるループは、大きなデータ構造の各要素について似たような処理を行うものである<ref name=Culler124>Culler et al, pg 124</ref>。科学技術計算にはデータ並列性があることが多い。

ループ伝搬依存（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 に依存しており、その値は周回ごとに再計算されるため、並列化できない。つまり、ある周回での計算は、それ以前の周回の計算結果に依存しているため、周回ごとに並列化することはできないのである。

問題が大きくなるほど、可能なデータ並列性も多くなる傾向がある<ref name=Culler125>Culler et al, pg 125</ref>。

=== タスク並列性 ===
{{main|タスク並列性}}
タスク並列性は、「同じまたは異なるデータ���に関する全く異なる計算は並列に実行可能である」という並列プログラムの特性である<ref name=Culler124/>。データ並列性がほぼ同じ計算を並列に実行するのとは対照的である。問題が大きくなっても、それに比例してタスク並列性が高くなることはない<ref name=Culler125/>。

== ハードウェア ==
=== メモリと通信 ===
並列コンピュータの主記憶は、[[共有メモリ]]型（全プロセッサが単一の物理[[アドレス空間]]を共有する）と[[分散メモリ]]型（各プロセッサがローカルな独自の物理アドレス空間を持つ）に分けられる<ref name=PH713>Patterson and Hennessy, pg 713</ref>。分散メモリは、メモリが論理的に分散しているためにそのように呼ばれるが、実際には物理的にも分散していることが多い。[[分散共有メモリ]]はこの2つの方式を組み合わせたものであり、各プロセッサはローカルなメモリとローカルでないメモリの両方にアクセスできる。この場合、ローカルなメモリへのアクセスはローカルでないメモリへのアクセスよりも一般に高速である。

全主記憶に同じ[[レイテンシ]]および[[帯域幅]]でアクセスできるコンピュータアーキテクチャを UMA (Uniform Memory Access) と呼ぶ。これは[[共有メモリ]]システム（メモリが物理的に分散していない場合）しか実現できない。それ以外のアーキテクチャは[[NUMA]] (Non-Uniform Memory Access) と呼ぶ。分散メモリシステムはNUMAである。

コンピュータには[[キャッシュメモリ]]が使われていることが多く、（物理的にも論理的にも）プロセッサの近くに高速かつ小容量のメモリを配置し、主記憶の内容のコピーを一時的に保持する。共有メモリ型の並列コンピュータでは、主記憶上の同じアドレスの内容のコピーが複数のキャッシュメモリ上に存在する可能性があり、その内容が食い違うとプログラムの実行に支障が発生する。そのような問題への対処として[[キャッシュコヒーレンシ]]システムがあり、プロセッサが常に最新の内容を得られるようキャッシュの内容を制御する。よく使われる方式としては、[[バススヌーピング]]がある。大型かつ高性能のキャッシュコヒーレンシシステムの設計は、コンピュータアーキテクチャの中でも非常に難しい問題である。そのため、共有メモリ型のシステムは分散メモリ型ほど[[スケーラビリティ|スケーラブル]]ではない<ref name=PH713/>。

プロセッサ同士またはプロセッサとメモリの通信のハードウェア実装方式は様々であり、マルチポート型の共有メモリ、[[クロスバースイッチ]]、共有[[バス (コンピュータ)|バス]]、スター型、リング型、ツリー型、[[超立方体|ハイパーキューブ]]型、ファット・ハイパーキューブ型（ハイパーキューブの頂点に複数のノードが接続される形態）、メッシュ型などの様々な[[ネットワーク構成]]のインターコネクト・ネットワークがある。

インターコネクト・ネットワークを使った並列コンピュータは、直接接続されていないノード間でメッセージパッシングできるように何らかの[[ルーティング]]機構が必要となる。大規模なマルチプロセッサ機では、プロセッサ間の通信媒体は複数の階層を構成することもある。

=== 並列コンピュータの分類 ===
並列コンピュータは、ハードウェアのどのレベルで並列性をサポートするかによって大まかに分類できる。これは、基本計算ノード間の距離とも大まかに対応している。

なお、以下の分類は相互排他的ではない。例えば、対称型マルチプロセッサを複数束ねたクラスターというのもよくある構成である。

==== マルチコア・コンピューティング ====
{{main|マルチコア}}
マルチコアプロセッサは、複数の[[実行ユニット]]（コア）を持つプロセッサである。マルチコアとスーパースケーラは異なる概念である。どちらも複数の命令を同時並列的に実行可能だが、スーパースケーラが1つの命令ストリーム（スレッド）から複数の命令を取り出して実行するのに対して、マルチコアでは複数の命令ストリームから複数の命令を取り出して実行する。マルチコアの個々のコアがスーパースケーラになっていることもある。

初期の擬似マルチコア方式として[[同時マルチスレッディング]]があった。この場合のプロセッサにはコア（実行ユニット）は1つしかないが、[[キャッシュメモリ|キャッシュ]]ミス時などコアが待ち状態になったときに、別のスレッドを実行できる。

[[インテル]]のマルチコアアーキテクチャは [[Intel Core|Core]] と [[Intel Core 2|Core 2]] プロセッサから始まった。別の有名なマルチコアプロセッサとしては、[[ソニー・コンピュータエンタテインメント]]の[[PlayStation 3]]用に設計された[[IBM]]の[[Cell Broadband Engine|Cell]]がある。

==== 対称型マルチプロセッシング ====
{{main|対称型マルチプロセッシング}}
対称型マルチプロセッサ（SMP）は、複数個のプロセッサがメモリを共有し、バスで相互接続された形態のコンピュータである<ref name=HP549>Hennessy and Patterson, pg 549</ref>。バスが[[ボトルネック]]となるため、スケーラビリティは制限される。そのため、SMPは一般に32プロセッサを越えることはない<ref>Patterson and Hennessy, pg 714</ref>。大型のキャッシュメモリを使って必要なバス帯域幅を低減して十分なメモリ帯域幅が確保できるなら、対称型マルチプロセッサは極めて費用対効果が高い<ref name=HP549/>。

==== 分散コンピューティング ====
{{main|分散コンピューティング}}
分散（メモリ）コンピュータは、処理ノード間をネットワークで相互接続した分散メモリ型のコンピュータシステムである。分散コンピュータはスケーラビリティが良い。

===== クラスターコンピューティング =====
{{main|コンピュータ・クラスター}}
[[画像:Beowulf.jpg|right|thumbnail|upright|[[Beowulf]]方式のクラスター]]
クラスターは複数のコンピュータをネットワークで相互接続して、全体として1つのシステムとして機能させるものであり、多くの面で単一のコンピュータであるかのように見ることができる<ref>[http://www.webopedia.com/TERM/c/clustering.html What is clustering?] Webopedia computer dictionary. [[2007年]][[11月7日]]閲覧</ref>。クラスターの構成は対称的である必要はないが、対称性がないと[[サーバロードバランス|負荷分散]]が難しくなる。クラスター方式においても、システムリソースを共有する[[密結合クラスター|密結合型]]とリソースを共有しない[[疎結合クラスター|疎結合型]]が存在する。

典型的なクラスター方式として [[Beowulf]] がある。これは[[インターネット・プロトコル・スイート|TCP/IP]][[イーサネット]][[Local Area Network|LAN]]で普通のコンピュータ群を相互接続してクラスターを構成できる<ref>[http://www.pcmag.com/encyclopedia_term/0,2542,t=Beowulf&i=38548,00.asp Beowulf definition.] ''PC Magazine''. [[2007年]][[11月7日]]閲覧</ref>。Beowulf の当初の開発者は Thomas Sterling と Donald Becker であった。

[[TOP500]]に掲載されているスーパーコンピュータの多くはクラスターである<ref>[http://www.top500.org/stats/list/29/archtype Architecture share for 06/2007] {{webarchive|url=https://web.archive.org/web/20071114212716/http://www.top500.org/stats/list/29/archtype |date=2007年11月14日 }}. TOP500 Supercomputing Sites. ここでは、74.60%のマシンがクラスターとされている。[[2007年]][[11月7日]]閲覧</ref>。

===== 超並列プロセッサ =====
{{main|超並列マシン}}
[[画像:BlueGeneL cabinet.jpg|right|thumbnail|upright|超並列マシン [[Blue Gene]]/L の筐体。2007年11月現在、世界最高速である。]]
超並列プロセッサ（MPP）は、非常に多数のプロセッサで構成される単一のコンピュータである。MPP はクラスターと多くの面で共通する特性を示すが、より大規模であり、100プロセッサよりずっと多数のプロセッサを装備していることが多い<ref>Hennessy and Patterson, pg 537</ref>。各CPUにはメモリがあり、オペレーティングシステムとアプリケーションのコピーがそこに格納される。CPU間の通信は非常に高速なインターコネクトで行われる<ref>[http://www.pcmag.com/encyclopedia_term/0,,t=mpp&i=47310,00.asp MPP Definition.] ''PC Magazine''. [[2007年]][[11月7日]]閲覧</ref>。

TOP500で2007年まで世界最高速のスーパーコンピュータとされていた [[Blue Gene|Blue Gene/L]] はMPPである。

===== グリッド・コンピューティング =====
{{main|グリッド・コンピューティング}}
グリッド・コンピューティングは、並列計算の中でも最も分散された形態である。遠隔にあるコンピュータを[[インターネット]]で相互接続して構成され、1つの問題を共同して解く。インターネットは利用可能な帯域幅が低く、レイテンシが大きいため、[[自明な並列性]]を持つ問題に使われることが多い。グリッド・コンピューティングを利用した[[分散コンピューティング]]プロジェクトが数多くあり、[[SETI@home]]や[[Folding@home]]がよく知られている。

多くのグリッド・コンピューティングは、オペレーティングシステムとアプリケーションの間に特有の[[ミドルウェア]]を置き、ネットワークリソースの管理やアプリケーション向けのインタフェースの標準化を行っている。よく知られたグリッド・コンピューティング用ミドルウェアとして、[[Berkeley Open Infrastructure for Network Computing]] (BOINC) がある。グリッド・コンピューティング用ソフトウェアでは、コンピュータが何もしていない時間を使うため、その時間を「スペアサイクル（spare cycles）」と呼ぶことが多い。

==== 専用並列コンピュータ ====
並列処理専用のマシンには、利用分野が限定されているものや、特定の並列問題のクラスしか解けないものもある。

; [[Graphics Processing Unit|GPU]]上での汎用処理 (GPGPU)
: [[GPGPU]]（General-purpose computing on GPU）は、CPUを遥かに凌駕する理論演算性能および電力効率を持つGPUを汎用計算に用いるものである<ref>[https://news.mynavi.jp/articles/2005/09/06/siggraph2/ SIGGRAPH 2005 - GPUをCPU的に活用するGPGPUの可能性] マイコミジャーナル、2005年9月6日。[[2008年]][[4月5日]]閲覧</ref>。GPUはリアルタイム[[コンピュータグラフィックス]]処理に最適化されたコプロセッサであり、[[線型代数学|線形代数]]演算（[[行列]]演算・ベクトル演算）をデータ並列で処理することに特化しているが、[[プログラマブルシェーダー]]の出現と発展により汎用計算への応用の道が開いた。GPGPUは、もともとGPUが得意とする画像処理全般への適用や、大量の演算が必要となる[[機械学習]]の分野における活用が進んでいる。ただしCPUとGPUは設計思想の違いからそれぞれ得意分野が異なるため、（スパコンを使っても必ずしも高速にならないのと同様に）ありとあらゆる処理をGPUによる並列計算で高速化しようと試みることは現実的ではない。
: [[NVIDIA GeForce]]/[[NVIDIA Quadro]]、[[AMD Radeon]]/[[AMD FirePro]]といったパーソナルコンピュータやワークステーション向けのグラフィックスプロセッサをGPGPU目的に利用できるほか、[[NVIDIA Tesla]]シリーズやAMD FirePro Sシリーズ（旧[[AMD FireStream]]）といったGPGPU専用のサーバ向けハードウェアも出現している。
; [[FPGA]]と[[再構成型コンピューティング]]
: 再構成型コンピューティングとは、FPGAを汎用コンピュータのコプロセッサとして利用するものである。FPGAは、内部の配線を変更可能な[[集積回路]]である。
: FPGA内の配線は、[[VHDL]]や[[Verilog]]のような[[ハードウェア記述言語]] (HDL) でプログラム可能である。しかし、これらの言語でのプログラミングは手間がかかる。そこで、多くのプログラマが親しんでいる[[C言語]]のソースをHDLのソースに変換するソフトウェアがいくつも開発されている。例えば、Mitrion-C、Impluse C、DIME-C、Handel-Cなどがある。
: AMDは[[HyperTransport]]技術をオープン規格としたため、[[サードパーティー]]がこれを再構成型コンピューティングを使った高性能計算に応用している。
;ASIC（Application Specific Integrated Circuit）
: [[ASIC]]を使って並列処理を行おうとする試みがいくつか行われている<ref>Oleg Maslennikov (2002). [http://www.springerlink.com/content/jjrdrb0lelyeu3e9/ 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.</ref><ref> Y. Shimokawa, Y. Fuwa, N. Aramaki. [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=170708 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.</ref><ref> K.P. Acken, M.J. Irwin, R.M. Owens. [http://www.ingentaconnect.com/content/klu/vlsi/1998/00000019/00000002/00167697?crawler=true A Parallel ASIC Architecture for Efficient Fractal Image Coding.]  ''The Journal of VLSI Signal Processing'', July 1998, '''19'''(2):97–113(17)</ref>。
: ASIC は本質的に特定用途を想定して設計されるため、その用途向けに完全に最適化される。結果として、その用途に関しては汎用コンピュータより高速に処理できることが多い。しかし、ASIC作成には[[フォトマスク]]が必要であり、その設計は非常に費用がかかる。1つのマスクは[[アメリカ合衆国ドル]]で百万ドル以上になる<ref>Andrew B. Kahng. "[http://www.future-fab.com/documents.asp?grID=353&d_ID=2596 Scoping the Problem of DFM in the Semiconductor Industry] {{webarchive|url=https://web.archive.org/web/20080131221732/http://www.future-fab.com/documents.asp?grID=353&d_ID=2596 |date=2008年1月31日 }}." University of California, San Diego. [[2004年]][[6月21日]]</ref>（設計ルールが小さくなるほど、フォトマスク開発には費用が多くかかる）。一方[[ムーアの法則]]に従って、汎用コンピュータの性能は急激に向上しているため、1世代か2世代のプロセッサの進歩によってASICに追いつくという傾向がある。初期投資が大きいこと、汎用コンピュータに対する優位性が長続きしないことから、ASIC を使った並列計算はあまり現実的でないことが多い。
;[[ベクトル計算機]][[画像:Cray-1-p1010221.jpg|right|thumbnail|[[Cray-1]]は、最も有名なベクトル計算機である。]]
: ベクトル計算機とは、多数のデータ群に対して同じ命令を実行できる[[CPU]]またはコンピュータシステムである。数値の配列またはベクトルに対して高度な操作を実行できる。例えば、A、B、C がそれぞれ64個の64ビット[[浮動小数点数]]の配列としたとき、<math>A = B \times C</math> を一度に行う<ref name=PH751>Patterson and Hennessy, pg 751</ref>。ベクトル計算機は、フリンの分類におけるSIMDと密接に関連している<ref name=PH751/>。
: 1970年代から1980年代にかけて、[[クレイ (コンピュータ企業)|クレイ]]はベクトル計算機で有名になった。しかし、最近ではベクトル計算機という呼び方をすることは少なくなっている。最近のプロセッサの[[命令セット]]には、[[AltiVec]]や[[ストリーミングSIMD拡張命令]] (SSE) などのベクトル処理命令が含まれている。

== ソフトウェア ==
{{main|並列化}}
並列型コンピュータでのプログラミング向けに、[[プログラミング言語]]、[[ライブラリ]]、[[アプリケーションプログラミングインタフェース|API]]、並列プログラミングモデルが生み出されてきた。

それらは、前提とするメモリアーキテクチャ（共有メモリ、分散メモリ、分散共有メモリ）によって分類できる。共有メモリ型プログラミング言語は、共有メモリ上の変数を更新することで相互の通信を実現している。分散メモリ型では[[メッセージ (コンピュータ)|メッセージパッシング]]が使われる。共有メモリ型APIとしては、[[POSIXスレッド]]と[[OpenMP]]が広く使われている。一方メッセージパッシング型のAPIとしては、[[Message Passing Interface]] (MPI) がよく使われている。

=== 自動並列化 ===
逐次型プログラムの[[コンパイラ]]による自動並列化は、並列計算の最終目標の1つでもある。コンパイラ研究者が長年に渡って研究しているが、限定的な成果しか得られていない。

一般に使われている並列プログラミング言語では、プログラマが並列化する部分を明記するか、せいぜい部分的な自動並列化ができる程度である。並列化を全く明記する必要のない言語も少数ながら存在し、[[SISAL]]、Parallel [[Haskell]]、Mitrion-C（FPGA用）などがあるが、これらはいずれも広く普及しているとは言い難い。

=== アプリケーション・チェックポインティング ===
コンピュータが大規模かつ複雑になると、[[平均故障間隔]]は小さくなる。並列計算では、多数のプロセッサを使っても長時間かかるような処理を行うことがある。このため、アプリケーションの実行中の状態（全てのリソース確保状況や変数群の状態など）を[[コアダンプ]]のような形で定期的に保持しておき、障害が発生したときに最初から処理をやり直すのではなく、途中までの保存された状態から再開できるようにする必要がある。この技法をアプリケーション・チェックポインティングと呼ぶ。時には数ヶ月もかかる処理もあり、その場合アプリケーション・チェックポインティングは非常に重要となる。また、この技法は[[プロセスマイグレーション]]にも応用できる。

=== GPGPU ===
GPGPUに関しては、[[統合型シェーダーアーキテクチャ]]の出現以降、[[NVIDIA]]社による[[CUDA]]、Khronosグループによる[[OpenCL]]、[[マイクロソフト]]社による[[DirectCompute]]といったAPIの整備・標準化も進んでいる。APIごとに特色はあるが、カーネル記述方式などに概ね似通った特徴を持つ。ただしCPUとGPUはメモリ空間が異なるため、まずCPU側のメモリからGPU側のメモリに入力データをコピーしてGPUに処理を実行させ、さらに処理後の結果を出力データとしてGPU側のメモリからCPU側のメモリにコピー（リードバック）する必要があるなど、プログラミングモデルは分散メモリ環境に近く、煩雑である<ref>[https://www.softek.co.jp/SPG/Pgi/TIPS/public/accel/multiGPU.html PGI アクセラレータにおけるマルチ GPU の使用]</ref>。

[[アドバンスト・マイクロ・デバイセズ|AMD]]はCPUとGPUを統合した[[AMD Accelerated Processing Unit|APU]]を開発しているが、さらにCPUとGPUのメモリ空間までをも統合し、データ転送の手間を減らしてGPGPUアプリケーションソフトウェアの実装を容易にするための仕組みとして[[Heterogeneous System Architecture]] (HSA) を提唱・推進している。
{{see also|GPGPU}}
<!-- NOTE: 以前の版にはCTM (Close to Metal)、BrookGPU、PeakStream、RapidMindなどに関する記載があったが、一般的に定着・普及していないものや研究開発状況が活発でないものに関しては削除している。 -->

== 歴史 ==
[[画像:ILLIAC 4 parallel computer.jpg|right|thumbnail|[[ILLIAC IV]]は、おそらく最も悪名高いスーパーコンピュータである。]]
真の並列性 (MIMD) という概念の起源は、イタリア人数学者ルイジ・メナブレアの "Sketch of the [[解析機関|Analytic Engine]] Invented by [[チャールズ・バベッジ|Charles Babbage]]" に遡る<ref>L.F. Menabrea, [http://www.fourmilab.ch/babbage/sketch.html Sketch of the Analytic Engine Invented by Charles Babbage]. Bibliothèque Universelle de Genève, 1842. [[2007年]][[11月7日]]閲覧</ref><ref name=PH753>Patterson and Hennessy, pg 753</ref>。<!--IBM 704は並列計算するマシンではないのでは？　英語版の記事の歴史の節ではIBM 704への言及は無い。並列計算を実現していないマシンを混入させないほうがよい。

1954年、[[IBM]]が [[IBM 704]] をリリースしたが、この開発プロジェクトには[[ジーン・アムダール]]もアーキテクトとして参加していた。このコンピュータは完全自動[[浮動小数点数|浮動小数点演算]]が行える初の商用マシンとなった<ref>{{cite web | url = http://www.columbia.edu/acis/history/704.html | title = Columbia University Computing History: The IBM 704 | accessdate = 2008年1月8日 | date = 2003年 | first = Frank | last = da Cruz | publisher = Columbia University }}</ref>。--> 1958年、IBMの研究者[[ジョン・コック]]と Daniel Slotnick は数値計算における並列性の利用について初めて話し合っている<ref name=G_Wilson>{{cite web | url = http://ei.cs.vt.edu/~history/Parallel.html | title = The History of the Development of Parallel Computing | accessdate = 2008年1月8日 | first = Gregory V. | last = Wilson | date = 1994年}}</ref>。1962年、[[バロース]]社は4プロセッサのコンピュータ D825 を発表した。これは、[[クロスバースイッチ]]経由で最大16個のメモリモジュールにアクセス可能であった<ref>{{Cite web | url = http://www.computerworld.com/action/article.do?command=viewArticleBasic&articleId=65878 | title = The Power of Parallelism | first = Gary | last = Anthes | accessdate = 2008-01-08 | date = 2001-11-19 | publisher = Computerworld | archiveurl = https://web.archive.org/web/20080131205427/http://www.computerworld.com/action/article.do?command=viewArticleBasic&articleId=65878 | archivedate = 2008-01-31 | url-status=dead|url-status-date=2017-09 }}</ref>。1967年、アムダールと Slotnick は、アメリカ情報処理学会連合会の会議で並列処理の可能性について公開討論を行った<ref name=G_Wilson/>。アムダールはこのとき、後に「アムダールの法則」と呼ばれる考え方に基づいて、並列性の限界について述べた。

1969年、[[ハネウェル]]が最初の Multics システムを発表した。これは、最大8プロセッサまでが並列に動作可能な対称型マルチプロセッサシステムであった<ref name=G_Wilson/>。[[カーネギーメロン大学]]では1970年代に [[C.mmp]] というマルチプロセッサ開発プロジェクトが行われ、大規模と言える初のマルチプロセッサであった<ref name=PH753/>。同期機能を持ったキャッシュ（[[MESIプロトコル]]参照）を持ったプロセッサ群をバスで接続する形態のマルチプロセッサ機としては、1984年の Synapse N+1 が最初である<ref name=PH753/>。

SIMD型並列コンピュータの起源は1970年代に遡る。初期のSIMD型コンピュータは、命令列を実行するときのプロセッサの[[制御装置]]におけるゲート遅延への対策という意味合いが強かった<ref>Patterson and Hennessy, pg 749</ref>。1964年、Slotnick は[[ローレンス・リバモア国立研究所]]向けの超並列コンピュータ構築を提案している<ref name=G_Wilson/>。その提案に対して[[アメリカ空軍]]が資金を提供し、それが最初のSIMD並列マシン [[ILLIAC IV]] となった<ref name=G_Wilson/>。設計の鍵となったのは、最大256プロセッサによる高い並列性であり、それらプロセッサが後に[[ベクトル計算機]]と呼ばれる方式で大きなデータを処理するものであった。しかし、プロジェクトは11年もかけて当初の4分の1の規模までしか構築できず、事前の見積もりの4倍の費用がかかってしまった<ref>Patterson and Hennessy, pgs 749–750: 「いくつかの有益な技術を生み出したが、ILLIAC IV はコンピュータとしては失敗であった。当初計画した規模の4分の1しか構築できなかったにもかかわらず、1966年に800万ドルと見積もられていた費用は1972年には3100万ドルにまで膨れ上がった。（中略）おそらく最も悪名高いスーパーコンピュータであろう。プロジェクトは1965年に開始され、実際のアプリケーションが実行可能になったのは1976年だった」</ref>。1976年に実際のアプリケーションが実行可能になったが、その性能は当時既に発売されていた商用のスーパーコンピュータ [[Cray-1]] に劣っていた。

== 課題 ==
{{出典の明記|section=1|date=2023年1月}}
並列計算を行う場合、もっともパフォーマンスを発揮するのはこれら複数のプロセッサが全て100%使い切られた時と考えられるが、従来のプログラムの多くは、複数のプロセッサを均等に全て使い切るようにはできておらず、また、そういったプログラミングは難しい{{要出典|date=2023年1月}}。

一般に、プログラムの処理全体のうち、複数のプロセッサで均等に処理できる部分の割合をプログラムの'''並列度'''と言う。並列コンピュータの処理性能を活かすには、プログラムの並列度が高くなければならない{{要出典|date=2023年1月}}。

買い物を例にとろう。まず買い物の前に、財布の中身を確かめなければならないし、足りなければ銀行で補充もしなければならない。その後はじめてお店にも行かなければならない。銀行に行くのと、お店に訪れるのは同時にできないし、財布の中身を確認してからでなければ、お店には行けない。プログラムもこれと似て、実行順番が変えられなかったり、同時に実行できなかったりする部分がどうしてもできてしまう。このため複数のプロセッサで'''同時に、かつ実行順番に依存しないような'''プログラムのみでプログラムを構成することは難しい{{要出典|date=2023年1月}}。

並列計算では、処理の「ある瞬間」ではそれぞれのプロセッサは実質まったく別に動作しており、そのため実行順番が全く問題にならないプログラムなら性能は引き出しやすい。しかし、先の例のように実行順番が強く束縛される場合は、あるプロセッサだけが働き、ほかのプロセッサはすることがなくなってしまうといった状態になり、性能が引き出しにくい。そのため，並列計算はそうでない場合と比べて性能を引き出すプログラミングが困難となる{{要出典|date=2023年1月}}。

また、並列化のためのオーバーヘッドが、並列化によって得られる性能向上の恩恵を上回ってしまうこともありえる。例えば複数の[[プロセス]]や[[スレッド (コンピュータ)|スレッド]]上で並列処理しようとする場合、各プロセスやスレッドの起動／終了処理およびデータ分割／統合処理などにかかる時間の合計が、並列化によって短縮された時間の合計を上回ってしまうと、並列化することで逆に処理性能が低下してしまうことになる。そのほか、物理的なプロセッサコアの数を上回るプロセスやスレッドを起動して並列処理をしても、コンテキスト切り替えのオーバーヘッドなどがかさむことで、かえって性能が低下してしまう{{要出典|date=2023年1月}}。

以上のように、並列計算によって高い性能を発揮するためには、ソフトウェア側の並列コンピューティング環境への最適化が重要な鍵となる{{要出典|date=2023年1月}}（詳しくは[[並列化]]を参照）。

== 関連項目 ==
* [[並列ランダムアクセス機械]] (PRAM) - 並列計算向け[[計算模型]]
* [[マルチプロセッシング]]
** [[対称型マルチプロセッシング]] (SMP)
** [[NUMA]]
** [[マルチコア]], [[メニイコア]]
** [[SIMD]], [[MIMD]]（[[フリンの分類]]）
* [[排他制御]]
* [[並列化]]
** [[Parallel Virtual Machine]]
** [[Message Passing Interface]]
** [[OpenMP]]
* [[コンピュータ・クラスター]]
* [[スーパーコンピュータ]]
** [[超並列マシン]]
* [[サーバファーム]]

== 脚注 ==
{{脚注ヘルプ}}
{{reflist|2}}

== 外部リンク ==
* {{Curlie|Computers/Parallel_Computing/}}
* [http://www.llnl.gov/computing/tutorials/parallel_comp/ Introduction to Parallel Computing] ローレンス・リバモア国立研究所
* [http://www-unix.mcs.anl.gov/dbpp/ Designing and Building Parallel Programs] by Ian Foster
* [https://web.archive.org/web/20021012122919/http://wotug.ukc.ac.uk/parallel/ Internet Parallel Computing Archive]
* [http://dsonline.computer.org/portal/site/dsonline/index.jsp?pageID=dso_level1_home&path=dsonline/topics/parallel&file=index.xml&xsl=generic.xsl Parallel processing topic area] at [[IEEE]] Distributed Computing Online
* [http://www.new-npac.org/projects/cdroms/cewes-1998-05/copywrite/pcw/book.html Parallel Computing Works] フリーなオンライン書籍
* [http://ark.cdlib.org/ark:/13030/ft0f59n73z/ Frontiers of Supercomputing] フリーなオンライン書籍
* [http://asyncop.com/MTnPDirEnum.aspx?treeviewPath=%5ba%5d+Multiprocessing+Traps+%26+Pitfalls Multiprocessing Traps & Pitfalls] 開発者向け
* [http://www.cc.u-tokyo.ac.jp/support/kosyu/13/MPIprog.pdf MPI「超」入門（Ｃ言語編）]、東京大学情報基盤センター作成の教材資料.
* [http://nkl.cc.u-tokyo.ac.jp/seminars/T2Kfvm/MPIprogf.pdf MPI「超」入門（FORTRAN編）]、東京大学情報基盤センター作成の教材資料.
* [https://www.hpci-office.jp/pages/seminar_texts HPCプログラミングセミナーで使用する資料の公開ページです。(HPCI=High Performance Computing Initiative)]
* [https://theartofhpc.com/ The Art of HPC: Texbooks by Victor Eijkhout of TACC]

{{Normdaten}}
{{デフォルトソート:へいれつけいさん}}
[[Category:並列コンピューティング|*]]
[[Category:並行計算]]
[[Category:スーパーコンピュータ]]
{{並列コンピューティング}}{{コンピュータ科学}}
このページで使用されているテンプレート:
Template:Abbr (ソースを閲覧) (拡張半保護)
Template:Accessdate (ソースを閲覧) (保護)
Template:Accessdate/core (ソースを閲覧) (保護)
Template:Ambox (ソースを閲覧) (保護)
Template:Checkdate (ソースを閲覧) (保護)
Template:Citation/showdate (ソースを閲覧) (保護)
Template:Citation/showdateCore (ソースを閲覧) (保護)
Template:Cite web (ソースを閲覧) (保護)
Template:Column-count (ソースを閲覧) (拡張半保護)
Template:Column-width (ソースを閲覧) (拡張半保護)
Template:Curlie (編集)
Template:DMC (ソースを閲覧) (保護)
Template:DMC/core (ソースを閲覧) (保護)
Template:En icon (ソースを閲覧) (拡張半保護)
Template:Find sources mainspace (ソースを閲覧) (保護)
Template:Fix (ソースを閲覧) (拡張半保護)
Template:Fix/title (ソースを閲覧) (拡張半保護)
Template:ISO639言語名 (ソースを閲覧) (保護)
Template:ISO date/day (ソースを閲覧) (拡張半保護)
Template:ISO date/ja (ソースを閲覧) (拡張半保護)
Template:ISO date/month (ソースを閲覧) (拡張半保護)
Template:ISO date/ymd (ソースを閲覧) (保護)
Template:ISO dateJA (ソースを閲覧) (保護)
Template:Icon (ソースを閲覧) (拡張半保護)
Template:Ifempty (ソースを閲覧) (保護)
Template:Ill (編集)
Template:Lang (ソースを閲覧) (保護)
Template:Lang-en (ソースを閲覧) (拡張半保護)
Template:LangWithName (ソースを閲覧) (保護)
Template:Languageicon (ソースを閲覧) (保護)
Template:Main (ソースを閲覧) (拡張半保護)
Template:Main other (ソースを閲覧) (保護)
Template:Navbox (ソースを閲覧) (保護)
Template:Normdaten (ソースを閲覧) (保護)
Template:Reflist (ソースを閲覧) (保護)
Template:See also (ソースを閲覧) (拡張半保護)
Template:Tooltip (ソースを閲覧) (拡張半保護)
Template:Webarchive (ソースを閲覧) (拡張半保護)
Template:いつ (ソースを閲覧) (拡張半保護)
Template:いつ/dateHandler (ソースを閲覧) (拡張半保護)
Template:コンピュータ科学 (編集)
Template:並列コンピューティング (編集)
Template:仮リンク (ソースを閲覧) (保護)
Template:出典の明記 (ソースを閲覧) (保護)
Template:出典の明記/dateHandler (ソースを閲覧) (保護)
Template:出典の明記/dateHandlerSection (ソースを閲覧) (拡張半保護)
Template:脚注ヘルプ (ソースを閲覧) (保護)
Template:要出典 (ソースを閲覧) (拡張半保護)
Template:要出典/dateHandler (ソースを閲覧) (拡張半保護)
モジュール:Arguments (ソースを閲覧) (保護)
モジュール:Authority control (ソースを閲覧) (保護)
モジュール:Authority control/config (ソースを閲覧) (保護)
モジュール:Check for unknown parameters (ソースを閲覧) (保護)
モジュール:EditAtWikidata (ソースを閲覧) (保護)
モジュール:Find sources (ソースを閲覧) (保護)
モジュール:Find sources/config (ソースを閲覧) (保護)
モジュール:Find sources/links/J-STAGE (ソースを閲覧) (保護)
モジュール:Find sources/links/NDL (ソースを閲覧) (保護)
モジュール:Find sources/links/cinii (ソースを閲覧) (保護)
モジュール:Find sources/links/dlib.jp (ソースを閲覧) (保護)
モジュール:Find sources/links/google (ソースを閲覧) (保護)
モジュール:Find sources/links/google books (ソースを閲覧) (保護)
モジュール:Find sources/links/google news (ソースを閲覧) (保護)
モジュール:Find sources/links/google scholar (ソースを閲覧) (保護)
モジュール:Find sources/links/japan search (ソースを閲覧) (保護)
モジュール:Find sources/links/wikipedia library (ソースを閲覧) (保護)
��ジュール:Find sources/templates/Find sources mainspace (ソースを閲覧) (保護)
モジュール:Hatnote (ソースを閲覧) (拡張半保護)
モジュール:Hatnote list (編集)
モジュール:ISO639言語名 (ソースを閲覧) (保護)
モジュール:Icon (ソースを閲覧) (保護)
モジュール:Icon/data (ソースを閲覧) (保護)
モジュール:If empty (ソースを閲覧) (保護)
モジュール:Labelled list hatnote (編集)
モジュール:Message box (ソースを閲覧) (保護)
モジュール:Message box/ambox.css (ソースを閲覧) (保護)
モジュール:Message box/configuration (ソースを閲覧) (保護)
モジュール:Navbar (ソースを閲覧) (保護)
モジュール:Navbar/configuration (ソースを閲覧) (保護)
モジュール:Navbox (ソースを閲覧) (保護)
モジュール:Navbox/former (ソースを閲覧) (保護)
モジュール:Webarchive (ソースを閲覧) (拡張半保護)
モジュール:Wikipedia言語名 (ソースを閲覧) (保護)
モジュール:Yesno (ソースを閲覧) (保護)
モジュール:仮リンク (ソースを閲覧) (保護)
モジュール:仮リンク/link (ソースを閲覧) (保護)
並列計算に戻る。
「https://ja.wikipedia.org/wiki/並列計算」から取得