Loading article…
DOPIPE 並列処理は、ループ内のステートメントをパイプライン化することでループレベルの並列処理を実行する方法です。パイプライン化された並列処理は、ループ、関数、アルゴリズムの段階など、さまざまな抽象化レベルで存在する可能性があります。並列処理の範囲は、プログラマーがこの概念を最大限に活用できるかどうかに依存します。また、独立したタスクを識別して分離し、それらを並列に実行するなどの要因にも依存します。[1]
背景
ループレベルの並列処理を採用する主な目的は、プログラムの順次タスクを検索して分割し、アルゴリズムに関する事前情報なしでそれらを並列タスクに変換することです。繰り返し実行され、実行時間を大幅に消費するデータ部分は、ループレベルの並列処理に適しています。ループレベルの並列処理の一般的な用途としては、ネストされたループで反復される多次元行列を使用する数学的分析が挙げられます。[2]
データ ストレージのオーバーヘッド、並列化の度合い、データの依存性に基づいて使用されるさまざまな種類の並列化手法があります。既知の手法には、DOALL、DOACROSS、DOPIPEなどがあります。
DOALL:この手法は、ループの各反復を反復間の相互作用なしに並列化できる場合に使用されます。したがって、全体の実行時間は N * T (シリアル プロセッサの場合、T は各反復の実行時間) から T のみに短縮されます (N 回の反復がすべて並列で実行されるため)。
DOACROSS:この手法は、データ依存性の可能性がある場合に使用されます。したがって、データに依存しないタスクはすべて並列で実行され、依存するタスクは順番に実行されるようにタスクを並列化します。並列プロセッサ間で依存タスクを同期するために、ある程度の同期が使用されます。
説明
DOPIPE は、各反復中に生成された各要素が後の反復で消費されるプログラムで使用されるパイプライン並列化手法です。次の例は、ループ内のタスクを分割してパイプライン方式で実行することで、合計実行時間を短縮する DOPIPE 手法の実装方法を示しています。タスクの分割は、ループ内のすべての依存関係が一方向になるように行われます。つまり、次の反復は前の反復に依存しません。
例
以下のプログラムはDOPIPE並列化の疑似コード[2]を示しています。
jこのコードでは、 1 から まで反復するループ内に 3 つのタスク (F0、F1、F2) があることがわかりますN。コード内の依存関係のリストは次のとおりです。
F1[j] → T F1[j+1]は、反復内の文F1がj+1反復内の文F1の後に実行されなければならないことを意味しますj。これは真の依存関係とも呼ばれます。
F1[j] → T F2[j]は、反復内の文F2がj反復内の文F1の後に実行されなければならないことを意味しますj。
(j=1; j<=N; j++) の場合 {
F0: o[j] = x[j] - a[j];
F1: z[j] = z[j-1] * 5;
F2: y[j] = z[j] * w[j];
}
このコードが順番に実行された場合、消費される合計時間は N * (T F0 + T F1 + T F2 ) に等しくなります。ここで、T F0、T F1、T F2 は、それぞれ関数 F0、F1、F2 の反復ごとの実行時間を表します。ここで、ループ内のステートメントを次のようにパイプライン化してループを並列化するとします。
(j=1; j<=N; j++) の場合 {
F0: o[j] = x[j] - a[j]; // DOALL並列処理
}
(j=1; j<=N; j++) の場合 {
F1: z[j] = z[j-1] * 5; // DOPIPE並列処理
post(j); // F1の結果が投稿され、使用可能になります
}
(j=1; j<=N; j++) の場合 {
wait(j); // F1が完了するまで待機し、F2が使用する値z[j]を生成します
F2: y[j] = z[j] * w[j];
}
F0 は独立した関数であるため、ループに依存することはありません (j+1またはj-1反復に依存しません)。また、ループ内の他のステートメントにも依存しません。したがって、この関数を完全に分離し、DOALL並列処理を使用して並列に実行できます。一方、ステートメント F1 と F2 は依存しているため (上記で説明)、これらを 2 つの異なるループに分割し、パイプラインpost(j)方式で実行します。とを使用して、 wait(j)F1 ループと F2 ループを同期します。
の最初の反復から始めて、文 F1 は T F1j時間で実行されます。一方、 F2 はF1 によって値が生成されるのを待っているため実行されません。 F1 は反復 の実行を完了すると、 を使用して値を投稿します。 F2 は、 F1 の実行を待機した後、 を使用し、使用可能な値があるため実行を開始します。また、 F1 の実行は F2 によって制限されないため、 F1 は同時に実行されます。下の図は、すべての文の実行タイムラインを示しています。
z[j]jpost(j)wait(j)z[j]j+1
図から、F0 のすべての反復が並列に実行されるため、F0 の実行にかかる合計時間は T F0であることがわかります。一方、F1 と F2 の場合、合計実行時間は N * T F1 + T F2に等しくなります(同期時間は無視できると仮定)。
これは、順次実行中に得られる時間よりもかなり短くなります。
他のモデルとの比較
DOALL並列処理は、主に分割統治の原理に基づいて動作します。ここでは、すべてのタスクが、一意のデータ セットを使用する異なる反復で実行されます。したがって、この実装の問題は、大量のデータ作業が一緒に計算される場合、異なるスレッドで動作するために大きなキャッシュスペースが必要になることです。スレッドには依存関係がないため、スレッド間通信のオーバーヘッドはありません。
DOPIPEでは、スレッド間の同期オーバーヘッドが発生します。しかし、パイプライン構造のため、生成されたデータは消費者によってすぐに消費されるため、必要なキャッシュスペースは少なくなります。[2]