ループ依存性分析

コンピュータサイエンスにおいて、ループ依存性分析は、ループの反復内で依存性を見つけ、文間のさまざまな関係を判断するために使用できるプロセスです。これらの依存関係は、さまざまな文がメモリ位置にアクセスする順序に関連付けられています。これらの関係の分析を使用すると、ループの実行を整理して、複数のプロセッサがループのさまざまな部分を並行して処理できるようにすることができます。これは、並列処理として知られています。一般に、ループはシリアルコードとして実行されると、多くの処理時間を消費する可能性があります。並列処理により、複数のプロセッサ間で処理負荷を共有することで、プログラムの合計実行時間を短縮できます。

複数のプロセッサがループの異なる部分を処理できるようにステートメントを編成するプロセスは、しばしば並列化と呼ばれます。並列化をどのように活用できるかを確認するには、まず個々のループ内の依存関係を分析する必要があります。これらの依存関係は、ループ内のどのステートメントが他のステートメントを開始する前に完了する必要があるか、およびループ内のどのステートメントがループ内の他のステートメントに対して並列に実行できるかを判断するのに役立ちます。ループ内で分析される依存関係の 2 つの一般的なカテゴリは、データ依存関係と制御依存関係です。

ループ依存性の分析は、次の形式の 正規化されたループで行われます。

i 1からU 1まで
  i 2からU 2まで
    ...
    for i n until U n do
      本体
    終わり
    ...
  終わり
終わり

どこ体以下が含まれる場合があります:

S1 a[f 1 (i 1 , ..., i n ), ..., f m (i 1 , ..., i n )] := ...
    ...
S2 ... := a[h 1 (i 1 , ..., i n ), ..., h m (i 1 , ..., i n )]

ここでaはm次元配列であり、フン_​、h _{n等は、すべての反復インデックス (i n} ) から配列の特定の次元のメモリ アクセスに マッピングする関数です。

たとえば、C の場合:

i = 0 ; i < U1 ; i ++ )の場合、j = 0 ; j < U2 ; j ++ )の場合、a [ i + 4 - j ] = b [ 2 * i - j ] + i * j ;       
         
        

f ₁はi+4-j、 aとh ₂の最初の次元への書き込みを制御することは、2*ijbの最初の次元の読み取りを制御します。

この問題の範囲は、S1とS2の間のすべての可能な依存関係を見つけることです。保守的に考えると、誤りであると証明できない依存関係はすべて真であると仮定する必要があります。

独立性は、 S1とS2の2つのインスタンスが配列内の同じ場所にアクセスしたり変更したりしないことを示すことによって示されます。1つの依存関係の可能性が見つかった場合、ループ依存関係の解析では通常、依存インスタンス間の関係を特徴付けるためにあらゆる試みが行われます。これは、まだ最適化が可能な場合があるためです。また、ループを 変換して依存関係を削除または変更することも可能です。

このような依存性を証明または反証する過程で、ステートメントSはそれがどの反復から来たかに応じて分解されることがある。例えば、S [1,3,5]は、i1 = 1、i2 = 3そしてi3 = 5もちろん、S [ d1 +1, d2 , d3 ] などの抽象的な反復への参照は許可されており、一般的です。

データ依存関係は、コード内の変数間の関係を示します。データ依存関係には 3 つの種類があります。

• 真の依存（フロー依存とも呼ばれる）
• 反依存
• 出力依存性

真の依存関係は、メモリ内の場所が読み取られる前に書き込まれるときに発生します。^{[1] [2] [3]メモリ内の場所から読み取る命令は、前の命令によって書き込まれるまで待機する必要があり、そうしないと読み取り命令が間違った値を読み取るため、}書き込み後読み取り (RAW) ハザードが発生します。^[2]真の依存関係の例は次のとおりです。

S1 : a = 5 ; S2 : b = a ;   
   

この例では、変数 a が最初にステートメント S1 で書き込まれ、次に変数 a がステートメント S2 によって読み取られるため、S1 と S2 の間には真の依存関係があります。この真の依存関係は、S1 →T S2 で表すことができます。真の依存関係は、ループ内の異なる反復間での読み取りと書き込みでも確認できます。次の例は、異なる反復間の真の依存関係を示しています。

( j = 1 ; j < n ; j ++ )の場合、S1 : a [ j ] = a [ j -1 ];       
       

この例では、j 番目の反復のステートメント S1 と j+1 番目の反復の S1 の間に真の依存関係が存在します。1 つの反復で a[j] に値が書き込まれ、次の反復で a[j-1] によって読み取りが行われるため、真の依存関係が存在します。この真の依存関係は、S1[j] →T S1[j+1] で表すことができます。

逆依存性は、メモリ内のある場所が、その同じ場所に書き込まれる前に読み取られる場合に発生します。^{[1] [2] [3]}これにより、書き込み後読み取り (WAR) の危険性が発生します。これは、メモリの場所にデータを書き込む命令は、そのメモリの場所が前の命令によって読み取られるまで待機する必要があるためです。そうしないと、読み取り命令は間違った値を読み取ってしまうことになります。^[2]逆依存性の例は次のとおりです。

S1 : a = b ; S2 : b = 5 ;   
   

この例では、ステートメント S1 と S2 の間に逆依存関係があります。これは、変数 b がステートメント S1 で最初に読み取られ、次に変数 b がステートメント S2 で書き込まれるため、逆依存関係です。これは、S1 →A S2 で表すことができます。逆依存関係は、ループ内の異なる反復によって確認できます。次の例は、このケースの例を示しています。

( j = 0 ; j < n ; j ++ )の場合、S1 : b [ j ] = b [ j + 1 ];       
       

この例では、S1 の j 番目の反復と S1 の j+1 番目の要素の間に逆依存関係があります。ここでは、j+1 番目の要素は、j の次の反復で同じ要素が書き込まれる前に読み取られます。この逆依存関係は、S1[j] →A S1[j+1] で表すことができます。

出力依存性は、メモリ内のある場所に書き込まれた後に、別のステートメントで同じ場所に再度書き込まれる場合に発生します。^{[1] [2] [3]} これにより、書き込み後書き込み (WAW) ハザードが発生します。これは、メモリの場所に値を書き込む 2 番目の命令は、最初の命令が同じメモリの場所へのデータの書き込みを完了するまで待機する必要があるためです。そうしないと、後でメモリの場所が読み取られたときに、間違った値が格納されます。^[2]出力依存性の例を次に示します。

S1 : c = 8 ; S2 : c = 15 ;    
   

この例では、ステートメント S1 と S2 の間に出力の依存関係があります。ここでは、変数 c は最初に S1 で書き込まれ、次に変数 c はステートメント S2 で再度書き込まれます。この出力の依存関係は、S1 →O S2 で表すことができます。出力の依存関係は、ループ内の異なる反復によって確認できます。次のコード スニペットは、このケースの例を示しています。

( j = 0 ; j < n ; j ++ )の場合{ S1 : c [ j ] = j ; S2 : c [ j + 1 ] = 5 ; }        
         
       

この例では、S1 の j 番目の要素と S2 の j+1 番目の要素の間に出力依存関係があります。ここでは、ステートメント S2 の c[j+1] が 1 回の反復で書き込まれます。次の反復では、ステートメント S2 の c[j] (前の反復の c[j+1] と同じメモリ位置) が再度書き込まれます。この出力依存関係は、S1[j] →O S2[j+1] と表すことができます。

ループ内の異なるステートメント間の依存関係を分析する際には、制御依存関係も考慮する必要があります。制御依存関係は、コードまたはプログラミング アルゴリズム自体によって導入される依存関係です。コードの実行中に命令が発生する順序を制御します。^[4]一般的な例の 1 つは、「if」ステートメントです。「if」ステートメントはプログラムに分岐を作成します。「if」ステートメントの「then」部分は、実行するアクションを明示的に指示または制御します。^[3]

この例では、制御フローの制約が示されています。コード ブロック 1 は、C プログラミング言語で if ステートメントを使用する場合の正しい順序を示しています。コード ブロック 2 は、if ステートメントによって制御されるはずのステートメントが、if ステートメントによって制御されなくなった問題を示しています。コード ブロック 3 は、"if" ステートメントによって制御されるはずのないステートメントが、if ステートメントによって制御されるようになった問題を示しています。これら 2 つの可能性はどちらも、不適切なプログラム実行につながる可能性があるため、ループ内でこれらのステートメントを並列化するときに考慮する必要があります。

ループ搬送依存関係とループ非依存依存関係は、ループの反復内の文間の関係によって決まります。ループの 1 つの反復内の文が、同じループの別の反復内の文に何らかの形で依存している場合、ループ搬送依存関係が存在します。^{[1] [2] [3]}ただし、ループの 1 つの反復内の文が、同じループの反復内の文にのみ依存している場合は、ループ非依存依存関係が作成されます。^{[1] [2] [3]}

この例では、コード ブロック 1 は、ステートメント S2 反復 i とステートメント S1 反復 i-1 間のループ依存の依存関係を示しています。つまり、ステートメント S2 は、前の反復のステートメント S1 が終了するまで続行できません。コード ブロック 2 は、同じ反復のステートメント S1 と S2 間のループに依存しない依存関係を示しています。

反復空間トラバーサルグラフ (ITG) は、ループの反復を通過するときにコードがたどるパスを示します。^[1]各反復はノードで表されます。ループ伝達依存グラフ (LDG) は、ループ内の異なる反復間に存在するすべての真の依存関係、反依存関係、および出力依存関係を視覚的に表現します。^[1]各反復はノードで表されます。

ネストされた for ループを使用すると、2 つのグラフの違いを示すのが簡単になります。

 i = 0 ; i < 4 ; i ++ )の場合、j = 0 ; j < 4 ; j ++の場合、S1 : a [ i ] [ j ] = a [ i ][ j -1 ] * x ;       
           
            

この例では、ステートメント S1 の j 回目の反復と S1 の j+1 番目のステートメントの間に真の依存関係があります。これは、S1[i,j] →T S1[i,j+1] と表すことができます。反復空間トラバーサル グラフとループ搬送依存グラフは次のとおりです。反復空間トラバーサル グラフ: ループ搬送依存グラフ:

• 依存分析
• バネルジーテスト
• エイリアス分析
• ドピペ
• ループレベルの並列処理
• ループ変換
• ループ分割
• ループ融合
• ループインターチェンジ
• ループの傾斜
• 自動並列化
• 自動ベクトル化