データ従属性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/25 13:20 UTC 版)
データ従属性 (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 } 最初の条件が成り立たない場合、フロー従属性 (flow dependency) が存在し、最初の文の結果を次の文で使う場合などに相当する。第二の条件は反従属性 (anti-dependency) を意味し、最初の文が書き換える変数の元の値を次の文の式で必要としている場合などに相当する。第三の条件は出力従属性 (output dependency) を表す。2つの変数が同じメモリ上の位置にある場合、それぞれの更新は元のプログラムの順序関係通りに行われる（後から書き込んだ方が残る）必要がある。 例として以下の関数を考える。 1: function Dep(a, b)2: c := a·b3: d := 2·c4: end function Dep(a,b) の3行目は、2行目の前に実行できないし、並行して実行することもできない。何故なら3行目は2行目の結果を利用しているからである。これは上述の第一の条件に反しており、フロー従属性があると言える。 1: function NoDep(a, b)2: c := a·b3: d := 2·b4: e := a+b5: end function こちらの例では、各命令には従属関係はないので、並列に実行可能である。 Bernstein’s conditionsでは、異なるプロセス間でメモリは共有されないと仮定している。そのため、アクセスの順序性を確保する手段として、セマフォなどの同期機構が必要となる。
※この「データ従属性」の解説は、「並列計算」の解説の一部です。
「データ従属性」を含む「並列計算」の記事については、「並列計算」の概要を参照ください。
- データ従属性のページへのリンク
