データ依存性

コンピュータサイエンスにおけるデータ依存性とは、プログラム文（命令）が先行する文のデータを参照する状況を指します。コンパイラ理論では、文（または命令）間のデータ依存性を発見するために使用される手法は依存性分析と呼ばれます。

文および を仮定すると、は次に依存します。 ${\displaystyle S_{1}}$${\displaystyle S_{2}}$${\displaystyle S_{2}}$${\displaystyle S_{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 }$

どこ：

• ${\displaystyle I(S_{i})}$は、によって読み取られるメモリ位置の集合である。${\displaystyle S_{i}}$
• ${\displaystyle O(S_{j})}$は、によって書き込まれたメモリ位置の集合であり、${\displaystyle S_{j}}$
• からまでの実行可能なランタイム実行パスが存在します。${\displaystyle S_{1}}$${\displaystyle S_{2}}$

これらの条件はアーサー・J・バーンスタインにちなんでバーンスタインの条件と呼ばれています。^[1]

3 つのケースが存在します。

• 反依存：上書きする前に何かを読み取る${\displaystyle I(S_{1})\cap O(S_{2})\neq \varnothing }$${\displaystyle S_{1}\rightarrow S_{2}}$${\displaystyle S_{1}}$${\displaystyle S_{2}}$
• フロー（データ）依存性：、およびは、何かが読み取られる前に書き込みます。${\displaystyle O(S_{1})\cap I(S_{2})\neq \varnothing }$${\displaystyle S_{1}\rightarrow S_{2}}$${\displaystyle S_{1}}$${\displaystyle S_{2}}$
• 出力の依存関係: 、両方とも同じメモリ位置に書き込みます。${\displaystyle O(S_{1})\cap O(S_{2})\neq \varnothing }$${\displaystyle S_{1}\rightarrow S_{2}}$

真の依存関係 (フロー 依存関係またはデータ依存関係とも呼ばれる) は、命令が前の命令の結果に依存する場合に発生します。真の依存関係に違反すると、書き込み後読み取り (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

例：

マルチR3、R1、R2
 R2、R5、R6を追加

これら 2 つの命令の間には反依存関係があることは明らかです。最初に R2 を読み取り、次に 2 番目の命令でそれに新しい値を書き込みます。

反依存性は名前依存性の一例です。つまり、次の例のように、変数の名前を変更すると依存性が削除される可能性があります。

1. B = 3
注: B2 = B
2.A = B2 + 1
3. B = 7

新しい変数 B2 は、新しい命令である命令 N で B のコピーとして宣言されています。2 と 3 の間の反依存性は削除され、これらの命令は並列に実行できるようになりました。ただし、この変更により新しい依存性が導入されました。命令 2 は命令 N に真に依存し、命令 N は命令 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 つの命令のみが実行される）次々に実行されます。

ただし、ステートメントまたは命令間の依存関係は、並列化コンパイラまたは命令レベルの並列化を活用するプロセッサによる、複数の命令の並列実行である並列化を妨げる可能性があります。関連する依存関係を考慮せずに複数の命令を無謀に実行すると、間違った結果、つまりハザードが発生する危険があります。

データ依存性は、コンピューティングのさまざまな領域、特にプロセッサ設計、コンパイラ構築、並列コンピューティング、並行プログラミングに関連しています。

• 命令パイプライン: パイプライン化されたプロセッサでは、複数の命令が複数のパイプライン ステージで並列に実行されます。そのため、レジスタ間のデータ依存関係はプロセッサ パイプラインで考慮され、処理される必要があります。最も重要なのは、パイプラインの停止やオペランドの転送などによって解決される真の依存関係です。
• アウトオブオーダー実行: 現代のプロセッサは、パフォーマンスを向上させるために、命令を元の順序どおりに実行しないことがよくあります。そのため、レジスタ間の名前の依存関係 (データの依存関係に加えて) を考慮する必要があり、レジスタ名の変更やスコアボードなどによって解決されます。データの依存関係はメモリ アクセスにも関連しており、メモリアクセス命令(ロードとストア) をプログラム順序どおりに実行しないメモリの曖昧性解消技術によって考慮する必要があります。

データ依存性は、さまざまなコンパイラ最適化に関係します。例えば、

• 命令のスケジュール: コンパイラは、データの依存関係を尊重する方法で命令をスケジュールする必要があります。これは、パフォーマンスを向上させるためにコードを再配置するコンパイラを最適化する上で非常に重要です。
• ループ変換: ループを最適化する場合、コンパイラーは、プログラムのセマンティクスを変更せずに、ループの展開、融合、タイリングなどの変換を適用するために、データの依存関係を考慮する必要があります。
• コードの移動: コンパイラがコードの一部を移動することを検討する場合、データの依存関係が違反されていないことを確認する必要があります。

• 依存関係分析
• 制御依存性
• ループ依存性解析 § データ依存性
• ハザード（コンピュータアーキテクチャ）§ データハザード