ループレベルの並列処理

ループレベルの並列処理は、ソフトウェア プログラミングにおける並列処理の 1 つの形式で、ループから並列タスクを抽出することに関係しています。ループレベルの並列処理の機会は、データがランダム アクセスデータ構造に格納されているコンピューティング プログラムでよく発生します。順次プログラムがデータ構造を反復処理し、一度に 1 つのインデックスを操作するのに対し、ループレベルの並列処理を利用するプログラムでは、複数のスレッドまたはプロセスを使用して、一部またはすべてのインデックスを同時に操作します。このような並列処理により、プログラムの全体的な実行時間が高速化されます。これは通常、アムダールの法則と一致します。

各反復が他の反復から独立している単純なループの場合、並列化では各反復を処理するプロセスを割り当てるだけで済むため、ループレベルの並列化は驚くほど並列になる可能性があります。ただし、多くのアルゴリズムは順次実行するように設計されており、コード内の依存関係により並列プロセスが競合すると失敗します。順次アルゴリズムは、わずかな変更を加えることで並列コンテキストに適用できる場合があります。ただし、通常はプロセス同期が必要です。同期は、メッセージ パッシングを介して暗黙的に行うことも、セマフォなどの同期プリミティブを介して明示的に行うこともできます。

L長さのリストを操作する次のコードを考えてみますn。

( int i = 0 ; i < n ; ++ i ) { S1 : L [ i ] += 10 ; }の場合         
       

ループの各反復では、 の現在のインデックスから値を取得しL、それを 10 ずつ増やします。 文の実行に 時間S1がかかる場合T、ループは、ループ構造にかかる時間を無視して、順次実行するのに 時間がかかります。 ここで、 のプロセッサn * Tを備えたシステムについて考えます。 スレッドが並列に実行される場合、すべてのステップの実行時間は に短縮されます。 pp > nnnT

それほど単純でないケースでは、一貫性のない、つまりシリアル化できない結果が生成されます。同じリストに対して動作する次のループを検討してくださいL。

( int i = 1 ; i < n ; ++ i ) { S1 : L [ i ] = L [ i -1 ] + 10 ; }の場合         
         

各反復では、現在のインデックスが前の反復に 10 を加えた値に設定されます。各反復を順番に実行すると、前の反復が正しい値を持っていることが保証されます。複数のスレッドでは、プロセスのスケジュール設定やその他の考慮事項により、実行順序によって、依存関係が満たされた後にのみ反復が実行されることが保証されません。依存関係が満たされる前に発生する可能性が高く、予期しない結果につながります。同期を追加して、前の反復への依存関係を保持することで、直列化可能性を復元できます。

コード内にはいくつかの種類の依存関係が存在します。^{[1] [2]}

並列実行時にループの連続動作を維持するためには、真の依存性が維持されなければなりません。反依存性と出力依存性は、各プロセスに変数の独自のコピーを与えることによって対処できます（プライベート化と呼ばれます）。^[1]

S1 : int a , b ; S2 : a = 2 ; S3 : b = a + 40 ;   
   
     

S2 ->T S3つまり、S2 は変数 に書き込みa、S3 はその変数から読み取るため、S2 は S3 に真に依存します。

S1 : int a , b = 40 ; S2 : a = b - 38 ; S3 : b = -1 ;     
     
   

S2 ->A S3つまり、S3 が変数に書き込む前に S2 が変数から読み取るため、S2 は S3 に対して逆依存関係にあることになりますb。

S1 : int a , b = 40 ; S2 : a = b - 38 ; S3 : a = 2 ;     
     
   

S2 ->O S3つまり、両方とも変数 に書き込むため、S2 は S3 に出力依存性を持ちますa。

S1 : int a , b , c = 2 ; S2 : a = c - 1 ; S3 : b = c + 1 ;      
     
     

S2 ->I S3つまり、S2 と S3 は両方とも変数 から読み取るため、S2 は S3 に対して入力依存性を持ちますc。

ループには 2 種類の依存関係があります。

• ループによる依存性
• ループに依存しない依存関係

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

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

( int i = 1 ; i < n ; ++ i ) { S1 : tmp = a [ i ]; S2 : a [ i ] = b [ i ] ; S3 : b [ i ] = tmp ; }         
       
       
       

ループ搬送依存関係では、ループの反復内のステートメントは、ループの別の反復内のステートメントに依存します。ループ搬送依存関係では、前述の依存関係表記法の修正バージョンが使用されます。

ループ伝達依存関係の例。ここでS1[i] ->T S1[i + 1]、 はi現在の反復を示し、 はi + 1次の反復を示します。

( int i = 1 ; i < n ; ++ i ) { S1 : a [ i ] = a [ i -1 ] + 1 ; }​         
         

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

ループを並列化するためのさまざまな方法論があります。

• 分散ループ
• DOALL 並列処理
• DOACROSS パラレルリズム
• ヘリックス^[3]
• DOPIPE 並列処理

各実装は、スレッドの同期方法（同期の有無）が若干異なります。さらに、並列タスクは何らかの方法でプロセスにマッピングする必要があります。これらのタスクは、静的または動的に割り当てることができます。研究によると、負荷分散は、静的に行うよりも、動的割り当てアルゴリズムによってより効果的に達成できることがわかっています。^[4]

シーケンシャルプログラムを並列化するプロセスは、次の個別のステップに分解できます。^[1]以下の具体的なループ並列化はそれぞれ暗黙的に実行されます。

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

( int i = 1 ; i < n ; ++ i ) { S1 : a [ i ] = a [ i -1 ] + b [ i ]; S2 : c [ i ] += d [ i ] ; }         
         
       

ループにはループ伝達依存関係がありますS1[i] ->T S1[i+1]が、S2 と S1 にはループに依存しない依存関係がないため、コードを次のように書き直すことができます。

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

          
       

ここで、loop1 と loop2 を並列に実行できることに注意してください。データ レベルの並列処理のように、1 つの命令を異なるデータに対して並列に実行する代わりに、ここでは異なるループが異なるデータに対して異なるタスクを実行します。S1 と S2 の実行時間を、上記のコードの順次形式の実行時間を とします。2 つのステートメントを分割して 2 つの異なるループに配置したため、実行時間は になります。このタイプの並列処理を関数並列処理またはタスク並列処理と呼びます。 ${\displaystyle T_{S_{1}}}$${\displaystyle T_{S_{2}}}$${\displaystyle n*(T_{S_{1}}+T_{S_{2}})}$${\displaystyle n*T_{S_{1}}+T_{S_{2}}}$

DOALL並列性は、ループ内の文が独立して実行できる場合（ループによる依存関係がない状況）に存在します。^[1]たとえば、次のコードは配列から読み取りを行わずa、配列を更新しませんb, c。どの反復も他の反復に依存しません。

( int i = 0 ; i < n ; ++ i ) { S1 : a [ i ] = b [ i ] + c [ i ] ; }         
         

S1 の 1 回の実行時間が であるとすると、上記のコードの順次形式の実行時間は になります。ここで、すべての反復が独立している場合に DOALL 並列処理が存在するため、すべての反復を並列に実行することで高速化が達成され、実行時間は になります。これは、順次実行で 1 つの反復にかかる時間です。 ${\displaystyle T_{S_{1}}}$${\displaystyle n*T_{S_{1}}}$${\displaystyle T_{S_{1}}}$

次の例では、簡略化された疑似コードを使用して、ループを並列化して各反復を個別に実行する方法を示します。

begin_parallelism (); 
for ( int i = 0 ; i < n ; ++ i ) { S1 : a [ i ] = b [ i ] + c [ i ]; end_parallelism (); } block ();         
         
    

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

同期はループによる依存関係を強制するために存在します。

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

( 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) に分解できます。

S1 : int tmp = b [ i ] + 1 ; S2 : a [ i ] = a [ i -1 ] + tmp ;      
     

最初の行int tmp = b[i] + 1;にはループ伝達依存関係がありません。 temp 値を並列に計算し、 への割り当てを同期することで、ループを並列化できますa[i]。

post ( 0 ); 
for ( int i = 1 ; i < n ; ++ i ) {         

    S1 : int tmp = b [ i ] + 1 ;待機( i -1 );      
    

    S2 : a [ i ] = a [ i -1 ] + tmp ; post ( i ); }     
    

S1 と S2 の実行時間が で、上記コードの順次形式の実行時間が であるとします。DOACROSS 並列処理が存在するため、反復をパイプライン方式で実行することで高速化が達成され、実行時間が になります。 ${\displaystyle T_{S_{1}}}$${\displaystyle T_{S_{2}}}$${\displaystyle n*(T_{S_{1}}+T_{S_{2}})}$${\displaystyle T_{S_{1}}+n*T_{S_{2}}}$

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

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

( int i = 1 ; i < n ; ++ i ) { S1 : a [ i ] = a [ i -1 ] + b [ i ]; S2 : c [ i ] + = a [ i ]; }         
         
       

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

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

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


for ( int i = 1 ; i < n ; i ++ ) { wait ( i ); S2 : c [ i ] += a [ i ]; }         
        
       

S1 と S2 の実行時間が で、上記コードの順次形式の実行時間が であるとします。DOPIPE並列処理が存在するため、反復をパイプライン方式で実行することで高速化が達成され、実行時間が になります。ここで、p は並列プロセッサの数です。 ${\displaystyle T_{S_{1}}}$${\displaystyle T_{S_{2}}}$${\displaystyle n*(T_{S_{1}}+T_{S_{2}})}$${\displaystyle n*T_{S_{1}}+(n/p)*T_{S_{2}}}$

• データの並列処理
• DOACROSS 並列処理
• タスクの並列処理
• 共有、分散、メッセージパッシングなどの異なるタイプのメモリモデルを使用した並列処理