ループの独立性

独立したループは並列化が可能なため、ループの独立性を把握することは重要です。独立したループの並列化は、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];

}

ループが依存している (独立していない) 場合、ループのパフォーマンスを向上することはより困難になります。ループは、いくつかの一般的な方法に依存します。

以下のセクションでは、さまざまなループの依存性について説明します。

フロー依存性 - WRITE の後の READ

クロス反復のフロー依存は、次の例で示されているように、変数が読み取られた後、異なる反復で書き込まれたときに発生します。

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];

  }

}

ほとんどの再帰は完全には並列化できません。代わりに、並列化の外または中へのループを探します。アンロールを行うことでパフォーマンスを向上させることができます。

アンチ依存性 - READ の後の WRITE

クロス反復のアンチ依存は、次の例で示されているように、変数が書き込まれた後、異なる反復で読み取られたときに作成されます。

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];

出力依存性 - WRITE の後の WRITE

クロス反復の出力依存は、変数が書き込まれた後、異なる反復で再度書き込まれたときに発生します。次に、出力依存性の例を示します。

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 など) を使用するようにコンパイラーに指示します。