並列計算
並列処理の歴史を遡ると、1958年にIBMの研究者ジョン・コックと Daniel Slotnick は数値計算における並列性の利用について初めて話し合っている。1962年には、バロース社が4プロセッサのコンピュータ D825 を発表した。→#歴史
関連する概念に並行計算(へいこうけいさん)があるが、並行計算は一つのタスクの計算を並列化することにとどまらず、複数の相互作用しうるタスクを、プロセスやスレッドなどをもちいて単一または複数の計算資源にスケジューリングするといった、より汎用性の高い処理をさす。並列計算は物理的に計算資源が複数なければ効果が得られないが、並行計算はたとえ計算資源が1つだけだったとしても、マルチタスクに対応したオペレーティングシステムがプロセッサ時間をスライスして各タスクの処理に割り当てることで効果が得られる。
特に、並列計算専用に設計されたコンピュータを用いずに、複数のパーソナルコンピュータやサーバ、スーパーコンピュータを接続することで並列計算を実現するものをコンピュータ・クラスターと呼ぶ。このクラスターをインターネットなどの広域ネットワーク上に分散させるものも、広義には並列計算に属すが、分散コンピューティングあるいはグリッド・コンピューティングと呼び、並列計算とは区別することが多い。
データ従属性 (data dependency) を理解することが、並列アルゴリズムの実装法を知る基礎の一つとなる。計算と計算の間に従属関係があるということは実行の順序性が生じるということである。したがってプログラムは、従属性のある計算の連鎖のうちで最長のものより高速に実行することはできない(これをクリティカルパスと呼ぶ)。幸運なことに、多くのアルゴリズムにはそのような従属関係の長い連鎖は存在せず、計算のほとんどの部分は並列に実行できる。
PiとPjというプログラムの断片があるとする。Bernstein's conditionsは、2つの部分が独立していて並列に実行できる条件を示している。Piへの入力変数の集合をIiで表し、Oiを出力変数の集合とする。Pjについても同様に表す。P iとPjが独立であるための条件は以下の通りである。
I j ∩ O i = ∅ {\displaystyle I_{j}\cap O_{i}=\emptyset }
I i ∩ O j = ∅ {\displaystyle I_{i}\cap O_{j}=\emptyset }
O i ∩ O j = ∅ {\displaystyle O_{i}\cap O_{j}=\emptyset }
従来、コンピュータソフトウェアは逐次的に計算されるものとして書かれてきた。問題を解くためにアルゴリズムが構築され、それによって逐次的に実行される命令列が生成される。その命令列は、コンピュータのCPU上で実行される。命令は一度に1つずつ実行される。
一方並列計算では、複数の計算ノードが同時並列的に動作して問題を解く。問題は独立した部分に分割され、各計算ノードがアルゴリズムの一部を同時並列的に実行する。計算ノードの実体は様々であり、マルチプロセッサ型のコンピュータの各CPUだったり、ネットワーク上のコンピュータだったり、専用ハードウェアだったり、それらの組合せだったりする。
1980年代から2004年まで、コンピュータの性能向上の主たる要因はクロック周波数の向上にあった。プログラムの実行時間は、命令数と1命令あたりの平均実行時間をかけたものに比例する。他の要因が全く変化しないと仮定すると、クロック周波数の向上によって1命令あたりの平均実行時間が減少する。