Loading article…
コンピュータサイエンスにおけるデータ依存性とは、プログラム文（命令）が先行する文のデータを参照する状況を指します。コンパイラ理論では、文（または命令）間のデータ依存性を検出するために用いられる手法を依存性解析と呼びます。
前提となる記述そして、に依存するもし：
どこ：
これらの条件は、アーサー・J・バーンスタインにちなんでバーンスタイン条件と呼ばれています。[ 1 ]
3つのケースが存在する。
データハザードは、データ依存性を示す命令がパイプラインの異なるステージでデータを変更する場合に発生します。潜在的なデータハザードを無視すると、競合状態（レースハザードとも呼ばれる）が発生する可能性があります。データハザードが発生する可能性のある状況は次の3つです。
リード・アフター・リード（RAR）は危険なケースではありません。
プログラムの順序では、 i1がi2より前に出現する2 つの命令i1とi2を考えます。
( i1が書き込む前にi2がソースを読み取ろうとする) 書き込み後読み出し(RAW)データハザードとは、命令がまだ計算または取得されていない結果を参照する状況を指します。これは、命令が前の命令の後に実行されたとしても、前の命令がパイプラインで部分的にしか処理されていないために発生する可能性があります。
例えば：
i1. R2 <- R5 + R8 i2. R4 <- R2 + R8
最初の命令はレジスタR2に保存する値を計算し、2番目の命令はこの値を使用してレジスタR4の結果を計算します。しかし、パイプライン処理では、2番目の演算のオペランドがフェッチされる時点で、最初の演算の結果はまだ保存されていないため、データ依存性が発生します。
命令i2は命令i1の完了に依存しているため、データ依存性が発生します。
( i2 がi1によって読み取られる前に宛先に書き込もうとする) 書き込み後読み取り (WAR) データハザードは、並行実行の問題を表します。
例えば：
i1. R4 ← R1 + R5 i2。R5 ← R1 + R2
i2がi1より先に終了する可能性がある状況（つまり、同時実行の場合）では、 i1がオペランドを取得する前にレジスタR5の結果が格納されないようにする必要があります。
( i2 がi1によって書き込まれる前にオペランドを書き込もうとする)並行実行環境では、書き込み後書き込み (WAW) データハザードが発生する可能性があります。
例えば：
i1. R5 <- R4 + R7 i2. R5 <- R1 + R3
i2のライトバック（WB）は、i1の実行が完了するまで遅延させる必要がある。
真の依存関係（フロー依存関係またはデータ依存関係とも呼ばれる）は、ある命令が前の命令の結果に依存する場合に発生します。真の依存関係に違反すると、書き込み後読み出し（RAW）ハザードが発生します。
1. A = 3 2. B = A 3. C = B
命令 3 は命令 2 に真に依存しています。なぜなら、C の最終値は B を更新する命令に依存するからです。命令 2 は命令 1 に真に依存しています。なぜなら、B の最終値は A を更新する命令に依存するからです。命令 3 は命令 2 に真に依存し、命令 2 は命令 1 に真に依存しているため、命令 3 も命令 1 に真に依存しています。 したがって、この例では命令レベルの並列処理は選択肢になりません。[ 2 ]
逆依存性とは、ある命令が後で更新される値を必要とする場合に発生するものです。逆依存性に違反すると、書き込み後読み出し（WAR）ハザードが発生します。
次の例では、命令 2 は命令 3 に逆依存しています。これらの命令の順序は変更できず、並列実行 (命令の順序を変更する可能性あり) もできません。これは、A の最終値に影響するためです。
1. B = 3 2. A = B + 1 3. B = 7
例：
MUL R3、R1、R2 R2、R5、R6を追加
これら2つの命令の間には、明らかに逆依存関係が存在する。まず最初にR2を読み込み、次に2番目の命令でR2に新しい値を書き込んでいる。
逆依存関係は、名前依存性の例です。つまり、次の例のように、変数の名前を変更することで依存関係を解消できます。
1. B = 3 N. B2 = B 2. A = B2 + 1 3. B = 7
A new variable, B2, has been declared as a copy of B in a new instruction, instruction N. The anti-dependency between 2 and 3 has been removed, meaning that these instructions may now be executed in parallel.
書き込み後の読み取り依存関係がまだ存在することに注意してください。命令 2 は命令 N に真に依存しており、命令 N は命令 1 に真に依存しています。この依存関係は元のバージョンにも存在しており、命令 2 は命令 1 に真に依存していました。この依存関係は安全に削除できません。[ 2 ]
出力依存性とは、命令の実行順序が変数の最終的な出力値に影響を与える場合に発生するものです。出力依存性に違反すると、書き込み後書き込み（WAW）ハザードが発生します。
以下の例では、命令3と命令1の間には出力依存関係があります。この例で命令の順序を変更すると、Aの最終値が変わるため、これらの命令は並列実行できません。
1. B = 3 2. A = B + 1 3. B = 7
アンチ依存関係と同様に、出力依存関係も名前依存関係です。つまり、上記の例を以下のように変更することで、変数名を変更して削除できます。
1. B2 = 3 2. A = B2 + 1 3. B = 7
従来のプログラムは、逐次実行モデルを前提として記述されています。このモデルでは、命令はプログラムで指定された順序で、アトミックに（つまり、任意の時点では1つの命令のみが実行される）、1つずつ順番に実行されます。
しかし、ステートメントや命令間の依存関係は、並列処理（並列コンパイラや命令レベル並列性を活用するプロセッサによる複数の命令の並列実行）を妨げる可能性があります。関連する依存関係を考慮せずに複数の命令を無謀に実行すると、誤った結果、すなわちハザードが発生する危険性があります。
データ依存性は、コンピューティングのさまざまな分野、特にプロセッサ設計、コンパイラ構築、並列コンピューティング、および並行プログラミングにおいて重要である。
データ依存性は、さまざまなコンパイラ最適化に関連しています。
![{\displaystyle \left[I(S_{1})\cap O(S_{2})\right]\cup \left[O(S_{1})\cap I(S_{2})\right]\cup \left[O(S_{1})\cap O(S_{2})\right]\neq \varnothing }](https://wikimedia.org/api/rest_v1/media/math/render/svg/13fdc02edb503210d422c4633250b657703f395c)
{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク)