ループレベルの並列処理

inta,b;// s1a=2;// s2b=a+40;// s3

s2 ->T s3, meaning that s2 has a true dependence on s3 because s2 writes to the variable a, which s3 reads from.

inta,b=40;// s1a=b-38;// s2b=-1;// s3

s2 ->A s3, meaning that s2 has an anti-dependence on s3 because s2 reads from the variable b before s3 writes to it.

int a 、b = 40 ; // s1 a = b - 38 ; // s2a = 2 ; // s3

s2 ->O s3つまり、s2 は s3 の出力に依存しているということです。なぜなら、両方とも変数 に書き込むからですa。

int a , b , c = 2 ; // s1 a = c - 1 ; // s2 b = c + 1 ; // s3

s2 ->I s3つまり、s2とs3はどちらも変数から読み取るため、s2はs3に入力依存しているということですc。

ループには2種類の依存関係が存在する可能性があります。

• ループに渡される依存関係
• ループに依存しない依存関係

ループ独立依存性では、ループは反復処理間の依存性を持ちますが、反復処理間の依存性はありません。各反復処理はブロックとして扱われ、他の同期処理なしに並列実行できます。

長さ n の 2 つの配列の値を交換するために使用される次のサンプル コードでは、ループに依存しない依存関係がありますs1 ->T s3。

for ( int i = 1 ; i < n ; ++ i ) { tmp = a [ i ]; // s1 a [ i ] = b [ i ]; // s2 b [ i ] = tmp ; // s3 }

ループ内依存関係では、ループのある反復処理内のステートメントが、同じループの別の反復処理内のステートメントに依存します。ループ内依存関係では、先に説明した依存関係表記法を修正したバージョンを使用します。

ループによって引き継がれる依存関係の例としてs1[i] ->T s1[i + 1]、 はi現在の反復、 はi + 1次の反復を示します。

for ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + 1 ; // s1 }

ループ依存グラフは、反復処理間のループ依存関係をグラフィカルに示します。各反復処理はグラフ上のノードとして表され、有向エッジは各反復処理間の真の依存、反依存、および出力依存を示します。

ループがループ間の依存関係を持つ場合、それを並列化する一つの方法は、ループを複数の異なるループに分割することです。互いに依存しないステートメントは分離され、これらの分割されたループは並列に実行できます。例えば、次のコードを考えてみましょう。

for ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + b [ i ]; // s1 c [ i ] += d [ i ]; // s2 }

このループにはループ依存性がありますs1[i] ->T s1[i + 1]が、s2とs1にはループ非依存性がないため、コードを次のように書き換えることができます。

// ループ1 for ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + b [ i ]; // s1 }// ループ2 for ( int i = 1 ; i < n ; ++ i ) { c [ i ] += d [ i ]; // s2 }

ここで、loop1とloop2は並列に実行できることに注意してください。データレベル並列処理のように、異なるデータに対して単一の命令を並列に実行するのではなく、ここでは異なるループが異なるデータに対して異なるタスクを実行します。s1とs2の実行時間を次のようにします。${\displaystyle T_{s_{1}}}$そして${\displaystyle T_{s_{2}}}$すると、上記のコードの逐次形式の実行時間は${\displaystyle n\cdot (T_{s_{1}}+T_{s_{2}})}$2 つのステートメントを分割して 2 つの異なるループに入れたため、実行時間は${\displaystyle n\cdot T_{s_{1}}+T_{s_{2}}}$私たちはこの種の並列処理を、機能並列処理またはタスク並列処理と呼びます。

DOALL並列処理は、ループ内のステートメントを独立して実行できる場合（ループによる依存関係がない場合）に存在します。^{[ 1 ]}例えば、次のコードは配列から読み取らずa、配列を更新しませんb, c。どの反復処理も他の反復処理に依存しません。

for ( int i = 0 ; i < n ; ++ i ) { a [ i ] = b [ i ] + c [ i ]; // s1 }

s1 の 1 回の実行時間を次のようにします。${\displaystyle T_{s_{1}}}$すると、上記のコードの逐次形式の実行時間は${\displaystyle n\cdot T_{s_{1}}}$DOALL並列処理はすべての反復が独立している場合に存在するため、すべての反復を並列に実行することで高速化が実現でき、実行時間は${\displaystyle T_{s_{1}}}$これは、逐次実行における1回の反復にかかる時間です。

以下の例は、簡略化された擬似コードを用いて、ループを並列化して各反復処理を独立して実行する方法を示しています。

beginParallelism ();for ( int i = 0 ; i < n ; ++ i ) { a [ i ] = b [ i ] + c [ i ]; // s1 endParallelism (); }ブロック（）;

DOACROSS並列処理では、ループの反復処理において、独立して実行できる計算を抽出し、それらを同時に実行することで並列化が行われます。^{[ 5 ]}

同期は、ループによって引き継がれる依存関係を強制するために存在する。

次の依存関係のある同期ループを考えてみましょうs1[i] ->T s1[i + 1]。

for ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + b [ i ] + 1 ; }

各ループ反復処理は2つのアクションを実行します

• 計算するa[i - 1] + b[i] + 1
• 値を割り当てるa[i]

値を計算しa[i - 1] + b[i] + 1、代入を実行する処理は、2行（ステートメントs1とs2）に分解できます。

int tmp = b [ i ] + 1 ; // s1 a [ i ] = a [ i - 1 ] + tmp ; // s2

最初の行には、int tmp = b[i] + 1;ループによる依存関係はありません。そのため、temp 値を並列に計算し、その後 への代入を同期させることで、ループを並列化できますa[i]。

post ( 0 ); for ( int i = 1 ; i < n ; ++ i ) { int tmp = b [ i ] + 1 ; // s1 wait ( i - 1 );a [ i ] = a [ i - 1 ] + tmp ; // s2 post ( i ); }

s1とs2の実行時間を次のようにします。${\displaystyle T_{s_{1}}}$そして${\displaystyle T_{s_{2}}}$すると、上記のコードの逐次形式の実行時間は${\displaystyle n\cdot (T_{s_{1}}+T_{s_{2}})}$DOACROSS並列処理が存在するため、反復処理をパイプライン方式で実行することで高速化を実現でき、実行時間は${\displaystyle T_{s_{1}}+n\cdot T_{s_{2}}}$。

DOPIPE 並列処理は、ループの反復処理が複数の同期ループに分散されるループ依存性に対してパイプライン並列処理を実装します。^{[ 1 ]} DOPIPE の目標は、前のステージから十分なデータが利用可能になるとすぐに次のステージが開始される組立ラインのように動作することです。^{[ 6 ]}

次の依存関係のある同期コードを考えてみましょうs1[i] ->T s1[i + 1]。

for ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + b [ i ]; // s1 c [ i ] += a [ i ]; // s2 }

s1は順次実行する必要がありますが、s2にはループによる依存関係はありません。s1に必要なすべての計算を直列に実行した後、DOALL並列処理を使用してs2を並列実行できます。ただし、この方法では速度向上は限定的です。より良いアプローチは、各s1に対応するs2が、そのs1の処理が完了したときに実行されるように並列化することです。

パイプライン並列処理を実装すると、次のようなループ群が生成されます。最初のループが対応するインデックスの処理を完了するとすぐに、2番目のループがそのインデックスに対して実行される可能性があります。

for ( int i = 1 ; i < n ; ++ i ) { a [ i ] = a [ i - 1 ] + b [ i ]; // s1 post ( i ); }for ( int i = 1 ; i < n ; i ++ ) { wait ( i ); c [ i ] += a [ i ]; // s2 }

s1とs2の実行時間を次のようにします。${\displaystyle T_{s_{1}}}$そして${\displaystyle T_{s_{2}}}$すると、上記のコードの逐次形式の実行時間は${\displaystyle n\cdot (T_{s_{1}}+T_{s_{2}})}$DOPIPE並列処理が存在するため、反復処理をパイプライン方式で実行することで高速化を実現でき、実行時間は${\displaystyle n\cdot T_{s_{1}}+({\frac {n}{p}})\cdot T_{s_{2}}}$ここで、pは並列処理されるプロセッサの数である。