並列計算
最初の条件が成り立たない場合、フロー従属性 (flow dependency) が存在し、最初の文の結果を次の文で使う場合などに相当する。第二の条件は反従属性 (anti-dependency) を意味し、最初の文が書き換える変数の元の値を次の文の式で必要としている場合などに相当する。第三の条件は出力従属性 (output dependency) を表す。2つの変数が同じメモリ上の位置にある場合、それぞれの更新は元のプログラムの順序関係通りに行われる(後から書き込んだ方が残る)必要がある。
例として以下の関数を考える。
Dep(a,b) の3行目は、2行目の前に実行できないし、並列して実行することもできない。何故なら3行目は2行目の結果を利用しているからである。これは上述の第一の条件に反しており、フロー従属性があると言える。
こちらの例では、各命令には従属関係はないので、並列に実行可能である。
Bernstein’s conditionsでは、異なるプロセス間でメモリは共有されないと仮定している。そのため、アクセスの順序性を確保する手段として、セマフォなどの同期機構が必要となる。
並列計算を行う場合、もっともパフォーマンスを発揮するのはこれら複数のプロセッサが全て100%使い切られた時と考えられるが、従来のプログラムの多くは、複数のプロセッサを均等に全て使い切るようにはできておらず、また、そういったプログラミングは難しい。
一般に、プログラムの処理全体のうち、複数のプロセッサで均等に処理できる部分の割合をプログラムの並列度と言う。並列コンピュータの処理性能を活かすには、プログラムの並列度が高くなければならない。
買い物を例にとろう。まず買い物の前に、財布の中身を確かめなければならないし、足りなければ銀行で補充もしなければならない。その後はじめてお店にも行かなければならない。銀行に行くのと、お店に訪れるのは同時にできないし、財布の中身を確認してからでなければ、お店には行けない。プログラムもこれと似て、実行順番が変えられなかったり、同時に実行できなかったりする部分がどうしてもできてしまう。このため複数のプロセッサで同時に、かつ実行順番に依存しないようなプログラムのみでプログラムを構成することは難しい。
並列計算では、処理の「ある瞬間」ではそれぞれのプロセッサは実質まったく別に動作しており、そのため実行順番が全く問題にならないプログラムなら性能は引き出しやすい。
真の並列性 (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 というマルチプロセッサ開発プロジェクトが行われ、大規模と言える初のマルチプロセッサであった。