独立したループは並列化が可能なため、ループの独立性を把握することは重要です。独立したループの並列化は、OpenMP* の粗粒度の並列処理から、ベクトル化およびソフトウェアのパイプライン化のような細粒度の命令レベルの並列処理 (ILP) まで、さまざまな方法で可能です。
反復 X の計算と無関係にループの反復 Y の計算を行うことができる場合、ループは独立していると考えられます。別の言い方をすれば、ループの反復 1 を計算し、同時に反復 1 の結果を使用しないで反復 2 を計算できる場合、ループは独立しています。
ループの出力の結果と、インデックス・カウンターを減らして記述された同じループからの結果を比較して、ループが独立しているかどうかを判断できます。
例えば、2 つめの例のコードが同じ結果を生成する場合、1 つめの例に示すループは独立しています。
例 |
---|
#define MAX 1024 void loop_indep1(int a[MAX],int b[MAX]) { for (int j=0;j<MAX;j++) a[j] = b[j]; } #define MAX 1024 void loop_indep2(int a[MAX],int b[MAX]) { for (int j=MAX;j>0;j--) a[j] = b[j]; } |
ループが依存している (独立していない) 場合、ループのパフォーマンスを向上することはより困難になります。ループは、いくつかの一般的な方法に依存します。
以下のセクションでは、さまざまなループの依存性について説明します。
例 |
---|
void flow_dep(double A[]) { for (int j=1; j<1024; j++) A[j]=A[j-1]; } |
上記の例は、最初のいくつかの反復について、次の行に相当します。
反復のサンプル |
---|
A[1]=A[0]; A[2]=A[1]; |
再帰関係は、ある反復から次の反復に情報を次々に送ります。
例 |
---|
void time_stepping_loops(double a[], double b[]) { for(int j=1; j<MAX; j++) { a[j] = a[j-1] + b[j]; } } |
ほとんどの再帰は完全には並列化できません。代わりに、並列化の外または中へのループを探します。アンロールを行うことでパフォーマンスを向上させることができます。
例 |
---|
void anti_dep1(double A[]) { for (int j=1; j<1024; j++) A[j]=A[j+1]; } |
上記の例は、最初のいくつかの反復について、次の行に相当します。
反復のサンプル |
---|
A[1]=A[2]; A[2]=A[3]; |
クロス反復の出力依存は、変数が書き込まれた後、異なる反復で再度書き込まれたときに発生します。次に、出力依存性の例を示します。
例 |
---|
void anti_dep2(double A[], double B[], double C[]) { for (int j=1; j<1024; j++) { A[j]=B[j]; A[j+1]=C[j]; } } |
上記の例は、最初のいくつかの反復について、次の行に相当します。
反復のサンプル |
---|
A[1]=B[1]; A[2]=C[1]; A[2]=B[2]; A[3]=C[2]; |
インテル® コンパイラーは、乗算 (*)、加算 (+)、減算 (-)、および除算 (/) のような単純な算術演算子のリダクションを含む大部分のループをソフトウェアのパイプライン化 (SWP) またはベクトル化することができます。リダクションは、結合操作を使用して配列データをスカラーデータにします。
例 |
---|
void reduction(double * sum, double c[]) { for (int j=0; j<MAX; j++) { *sum = *sum + c[j]; } } |
コンパイラーは、リダクションを誤認識してフロー、アンチ、出力依存性またはループ伝播のメモリー依存エッジを報告することがあります。このような場合、コンパイラーはループのベクトル化またはソフトウェアのパイプライン化を行いません。この場合、プログラミング構造体を単にリダクションとして認識し、ループのベクトル化またはソフトウェアのパイプライン化を行うプラグマ (#pragma ivdep または #pragma swp など) を使用するようにコンパイラーに指示します。