並列計算

**並列計算**（へいれつけいさん、）は、特定のコンピュータ作業をいくつかの独立した小さな処理に細分化し、複数の処理装置上でそれぞれの処理を同時に実行させることである。**並列コンピューティング**や**並列処理**ともいう。

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

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

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

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

並列処理の歴史を遡ると、1958年にIBMの研究者ジョン・コックと Daniel Slotnick は数値計算における並列性の利用について初めて話し合っている。1962年には、バロース社が4プロセッサのコンピュータ D825 を発表した。→#歴史

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

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

## 背景
従来、コンピュータソフトウェアは逐次的に計算されるものとして書かれてきた。問題を解くためにアルゴリズムが構築され、それによって逐次的に実行される命令列が生成される。その命令列は、コンピュータのCPU上で実行される。命令は一度に1つずつ実行される。

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

1980年代から2004年まで、コンピュータの性能向上の主たる要因はクロック周波数の向上にあった。プログラムの実行時間は、命令数と1命令あたりの平均実行時間をかけたものに比例する。他の要因が全く変化しないと仮定すると、クロック周波数の向上によって1命令あたりの平均実行時間が減少する。

一方で、マイクロプロセッサの消費電力は P = C \times V^2 \times F という式で与えられる。ここで、P は消費電力、C はクロックサイクル毎に切り替えられる静電容量（入力が変化するトランジスタの総数に比例）、V は電圧、F はプロセッサの周波数（正確には1秒あたりのサイクル数）である。従って、クロック周波数が高くなると、プロセッサの消費電力も増大する。プロセッサの消費電力の増大は、インテルが2004年5月に開発中だったプロセッサをキャンセルした最大の理由であり、この時点がクロック周波数向上が性能向上の主たる要因となっていた時代の終焉であった 。

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

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

:S = \frac{1}{(1 - P)}

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

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

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

:\displaystyle S(P) = P - \alpha(P-1)

ここで、Pはプロセッサ数、Sは性能向上、\alpha は処理の並列化できない部分である。アムダールの法則では問題のサイズが固定であり、逐次実行部分はプロセッサ数に依存しないと仮定されている。一方、グスタフソンの法則ではそのような仮定がない。

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

PiとPjというプログラムの断片があるとする。Bernstein's conditionsは、2つの部分が独立していて並列に実行できる条件を示している。Piへの入力変数の集合をIiで表し、Oiを出力変数の集合とする。Pjについても同様に表す。P iとPjが独立であるための条件は以下の通りである。

*  I_j \cap O_i  =  \emptyset
*  I_i \cap O_j  =  \emptyset
*  O_i \cap O_j  = \emptyset

最初の条件が成り立たない場合、フロー従属性 (flow dependency) が存在し、最初の文の結果を次の文で使う場合などに相当する。第二の条件は反従属性 (anti-dependency) を意味し、最初の文が書き換える変数の元の値を次の文の式で必要としている場合などに相当する。第三の条件は出力従属性 (output dependency) を表す。2つの変数が同じメモリ上の位置にある場合、それぞれの更新は元のプログラムの順序関係通りに行われる（後から書き込んだ方が残る）必要がある。

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

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

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

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

一方のスレッドが変数 V をロックできた場合、もう一方は V がアンロックされるまで待たされることになる。これによってプログラムの正しい実行が保証される。ロックはプログラムの正しい実行の保証には必須だが、それによってプログラムの実行速度は大幅に低下する。

複数の変数のロックには複数のロックが必要であり、それによってデッドロックが発生する可能性が生じる。不可分なロックは複数の変数を一度にロックするものである。その場合、対象変数群の一部がロックできなければ、全体のロックができないと見なされる。個別にロックされる2つの変数をロックする必要のあるスレッドが2つ存在したとして、一方のスレッドが一方の変数だけをロックし、もう一方のスレッドがもう一方の変数だけをロックするという状況が発生しうる。このような場合、双方のスレッドはロックできていない変数をロックしようとして待ち続け、結果としてデッドロックとなる。

多くの並列プログラムでは、サブタスク群が同期して動作することを要求する。この用途で使われるものとしてバリアがある。バリアは一般にソフトウェアロックを使って実装される。その種のアルゴリズムとしてLock-freeとWait-freeアルゴリズムがある。これはロックもバリアも使わずに全てを実現するものである。ただし、実装は難しく、データ構造の設計を慎重に行う必要がある。

並列化によって必ず性能が向上するとは限らない。一般にタスクを細分化してスレッド数を増やしていくと、スレッド間の通信に費やす時間が増大していく。すると、ある時点で通信オーバーヘッドが処理時間を支配するようになり、それ以上の並列化（スレッド数の増加）は単に処理時間の遅延を招くことになる。この現象を並列スローダウンと呼ぶ。

### 細粒度並列性、粗粒度並列性、自明な並列性
アプリケーションは、スレッド間で同期や通信を必要とする頻度で分類できる。細粒度並列性 (fine-graind parallelism) を持つものは、スレッド間で頻繁に通信する必要がある。粗粒度並列性（coarse-grained parallelism）を持つものはその逆である。自明な並列性を持つ (embarassingly parallel) ものは、ほとんど全くスレッド間の通信を必要とせず、したがって並列化も最も容易である。

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

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

最初に定義された一貫性モデルは、レスリー・ランポートの逐次一貫性モデルである。逐次一貫性とは、並列プログラムを並列実行したときの結果と、それと等価な逐次プログラムの結果が同じという特性である。プログラムが逐次一貫性を持つとは、「…任意の実行の結果が、それを全プロセッサが逐次的順序で実行された場合と同じであり、その順序がプログラム内で指定された順序と同じである」ことを意味する。

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

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

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

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

デイビッド・パターソンとジョン・ヘネシーの著書には「もちろん一部のマシンはこれらの混成であるが、単純で分かりやすく、とりあえずの近似としては最適であるが故にこの分類が今も使われている」とある。

## 並列性の分類
### ビットレベルの並列性
1970年代のマイクロプロセッサの開発以来、コンピュータの主なアーキテクチャ上の進化はワードサイズ（プロセッサが一度に処理できるビット幅）を倍々にしていくことで成されてきた。ワードを大きくすることで、従来のワードサイズでは多数の命令を必要としていた大きな変数の処理が、より少ない命令数で実行可能となる。例えば、8ビットのプロセッサで2つの16ビットの整数を加算する場合を考える。まず、2つのデータの下位8ビットを通常の加算命令で加算し、その後上位8ビットをキャリー付き加算命令で加算することで、下位8ビットで発生したキャリーを考慮する。つまり、8ビットプロセッサでは1つの演算に2つの命令を必要とし、16ビットプロセッサならそれを1命令で実行できる。

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

### 命令レベルの並列性

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

最近のプロセッサは多段命令パイプラインを備えている。パイプラインの各ステージは、命令に対して行うべき異なる処理に対応している。N段のパイプラインを持つプロセッサでは、N個の命令について同時にそれぞれ異なる段階の処理をしていることになる。典型的なパイプラインの例としてRISCプロセッサの5段のパイプラインがある（各段は命令フェッチ、命令デコード、実行、メモリアクセス、ライトバック）。Pentium 4 は35段のパイプラインを持つ。

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

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

### データ並列性

データ並列性はプログラムのループが本質的に備えている並列性であり、ループの各周回が各ノードで並列に処理されるようデータを配布する部分が中心となる。並列化されるループは、大きなデータ構造の各要素について似たような処理を行うものである。科学技術計算にはデータ並列性があることが多い。

ループ伝搬依存（loop-carried dependency）とは、ループにおいて以前の周回の結果に依存して新たな周回の計算が行われる性質をいう。ループ伝搬依存があると、ループの並列化はできない。例えば、以下のフィボナッチ数の一部を計算する擬似コードを考えてみよう。

 1:    prev := 0
 2:    cur := 1
 3:    do:
 4:       PREV := CUR
 5:       CUR := CUR + PREV
 6:    while (CUR A = B \times C を一度に行う。ベクトル計算機は、フリンの分類におけるSIMDと密接に関連している。
: 1970年代から1980年代にかけて、クレイはベクトル計算機で有名になった。しかし、最近ではベクトル計算機という呼び方をすることは少なくなっている。最近のプロセッサの命令セットには、AltiVecやストリーミングSIMD拡張命令 (SSE) などのベクトル処理命令が含まれている。

## ソフトウェア

並列型コンピュータでのプログラミング向けに、プログラミング言語、ライブラリ、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側のメモリにコピー（リードバック）する必要があるなど、プログラミングモデルは分散メモリ環境に近く、煩雑である。

AMDはCPUとGPUを統合したAPUを開発しているが、さらにCPUとGPUのメモリ空間までをも統合し、データ転送の手間を減らしてGPGPUアプリケーションソフトウェアの実装を容易にするための仕組みとしてHeterogeneous System Architecture (HSA) を提唱・推進している。

## 歴史
[right|thumbnail|[ILLIAC IVは、おそらく最も悪名高いスーパーコンピュータである。]]
真の並列性 (MIMD) という概念の起源は、イタリア人数学者ルイジ・メナブレアの "Sketch of the Analytic Engine Invented by Charles Babbage" に遡る。 1958年、IBMの研究者ジョン・コックと Daniel Slotnick は数値計算における並列性の利用について初めて話し合っている。1962年、バロース社は4プロセッサのコンピュータ D825 を発表した。これは、クロスバースイッチ経由で最大16個のメモリモジュールにアクセス可能であった。1967年、アムダールと Slotnick は、アメリカ情報処理学会連合会の会議で並列処理の可能性について公開討論を行った。アムダールはこのとき、後に「アムダールの法則」と呼ばれる考え方に基づいて、並列性の限界について述べた。

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

SIMD型並列コンピュータの起源は1970年代に遡る。初期のSIMD型コンピュータは、命令列を実行するときのプロセッサの制御装置におけるゲート遅延への対策という意味合いが強かった。1964年、Slotnick はローレンス・リバモア国立研究所向けの超並列コンピュータ構築を提案している。その提案に対してアメリカ空軍が資金を提供し、それが最初のSIMD並列マシン ILLIAC IV となった。設計の鍵となったのは、最大256プロセッサによる高い並列性であり、それらプロセッサが後にベクトル計算機と呼ばれる方式で大きなデータを処理するものであった。しかし、プロジェクトは11年もかけて当初の4分の1の規模までしか構築できず、事前の見積もりの4倍の費用がかかってしまった。1976年に実際のアプリケーションが実行可能になったが、その性能は当時既に発売されていた商用のスーパーコンピュータ Cray-1 に劣っていた。

## 課題

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

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

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

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

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

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

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

## 脚注

## 外部リンク
* 
* 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 開発者向け
* MPI「超」入門（Ｃ言語編）、東京大学情報基盤センター作成の教材資料.
* MPI「超」入門（FORTRAN編）、東京大学情報基盤センター作成の教材資料.
* HPCプログラミングセミナーで使用する資料の公開ページです。(HPCI=High Performance Computing Initiative)
* The Art of HPC: Texbooks by Victor Eijkhout of TACC