1-2 ループの最適化によるデータの並列パフォーマンスの強化

データ並列アプリケーションでは、独立した同じ演算が異なるデータを繰り返し実行します。データ並列を行うループは、通常、計算量の最も多いコード領域であるため、ループを最適化することで直接パフォーマンスに効果をもたらします。入れ子構造のループでは、スレッドに割り当てる計算粒度が直接パフォーマンスに影響します。入れ子構造のループを分割 (ループ・フィッション) や結合 (ループ融合) などのループ変換によって、効率良く簡単に並列化できます。

この記事は、「マルチスレッド・アプリケーションの開発のためのインテル・ガイド」の一部で、インテル^® プラットフォーム向けにマルチスレッド・アプリケーションを効率的に開発するための手法について説明します。

ループを最適化することで、データ並列アプリケーションのパフォーマンス向上の機会を見出すことができます。ループ融合、ループ交換、ループアンロールといった最適化では、同期や並列化のオーバーヘッドを最小限に抑えつつ、粒度、ロードバランス、データの局所性の向上を図ります。通常、反復回数の多いループ (スレッド数が比較的少ない場合は特に) は、並列化に最適な候補です。反復回数が多いと、スレッド間で分配できるタスクの数が増えて、ロードバランスが向上します。とはいえ、反復の処理量も考慮する必要があります。特に明記しない限り、ここでは 1 回あたりのループの各反復で行われる計算量はほぼ等しいとします。

OpenMP* のワークシェアリング構造を使用した下記のコード例で考えてみましょう。この場合、ループ全体の反復回数が少ないと、それらの反復が 4 つのスレッドに分配されたときにロード・インバランスを引き起こします。1 回の反復が数マイクロ秒しかかからない場合、影響は大きくありません。しかし、それぞれの反復に 1 時間かかるとなると、4 番目のスレッドの計算中は残り 3 つのスレッドは 60 分間アイドル状態になります。1 時間かかる反復処理を 1,003 回行う同じループを 4 つのスレッドで行うとしましょう。この場合、1 時間のアイドル時間でも 10 日間実行した場合には非常に大きな影響があります。

#pragma omp for
for (i = 0; i < 13; i++)
{...}

ループの入れ子構造が複数段ある場合は、安全に並列化できる一番外側のループ (最外ループ) を選ぶと良いでしょう。たいてい、粒度は最大になります。各スレッドに均等に処理を分配できるようにしてください。最外ループの反復回数が少なく処理を均等に分配できない場合は、反復回数の多い内側のループがスレッド化に適しているかもしれません。たとえば、次のような 4 段の入れ子になったループのコードを考えてみましょう。

void processQuadArray (int imx, int jmx, int kmx,
  double**** w, double**** ws)
{
  for (int nv = 0; nv < 5; nv++)
    for (int k = 0; k < kmx; k++)
      for (int j = 0; j < jmx; j++)
        for (int i = 0; i < imx; i++)
          ws[nv][k][j][i] = Process(w[nv][k][j][i]);
}

スレッド数が 5 つの場合を除き、外側のループを並列化するとロード・インバランスとアイドルスレッドが生じます。これは、配列次元 imx、jmx、kmx が非常に大規模なケースは、特に深刻です。この場合、内側のループの 1 つを並列化すると良いでしょう。

ワークシェアリング構造の終わりにある暗黙のバリアを無効にしても安全な場合は、無効にしてください。OpenMP のワークシェアリング構造 (for、sections、single) には、構造ブロックの最後に暗黙のバリアがあります。スレッドは、実行を続ける前にこのバリアで待機します。このようなバリアは不要であり、パフォーマンスに悪影響を及ぼす場合もあります。OpenMP では nowait 節でこのバリアを無効にできます。

void processQuadArray (int imx, int jmx, int kmx,
  double**** w, double**** ws)
{
  #pragma omp parallel shared(w, ws)
  {
    int nv, k, j, i;
    for (nv = 0; nv < 5; nv++)
      for (k = 0; k < kmx; k++) // kmx is usually small
        #pragma omp for shared(nv, k) nowait
          for (j = 0; j < jmx; j++)
            for (i = 0; i < imx; i++)
              ws[nv][k][j][i] = Process(w[nv][k][j][i]);
  }
}

最内ループの計算は独立しているため、スレッドは次の k の反復に進む前に暗黙のバリアで待機する必要がありません。処理量が均等でない場合は、nowait 節によりスレッドは暗黙のバリアで待機せずに、処理を続けることができます。

並列実行を妨げるループ伝播の依存性がある場合、並列実行が可能なようにループ本体を分割できることがあります。このように、ループ本体を複数に分割することを「ループ・フィッション」と言います。次の例では、依存性のあるループをループ・フィッションし、作成された新しいループが並列で実行できるようになっています。

float *a, *b;
int i;
for (i = 1; i < N; i++) {
  if (b[i] > 0.0) 
    a[i] = 2.0 * b[i];
  else 
    a[i] = 2.0 * fabs(b[i]);
  b[i] = a[i-1];
}

a 配列の要素の代入は、対応する b の要素の符号と関係なくすべて独立しています。b の要素のそれぞれの代入はほかの代入とは独立していますが、a で必要な要素の代入の完了に依存しています。したがって、上記のループは並列化できません。

ループを独立した 2つの演算に分割することによって、双方の演算を並列実行できます。たとえば、インテル^® スレッディング・ビルディング・ブロック (インテル^® TBB) の parallel_for アルゴリズムを使用すると次のようになります。

float *a, *b;
parallel_for (1, N, 1, 
  [&](int i) {
    if (b[i] > 0.0) 
      a[i] = 2.0 * b[i];
    else 
      a[i] = 2.0 * fabs(b[i]);
    });
parallel_for (1, N, 1, 
  [&](int i) {
    b[i] = a[i-1];
  });

2 番目の実行の前に、最初の parallel_for 呼び出しによって戻り値が得られることで、b の配列で更新が開始される前に、a 配列のすべての更新が完了します。

ループ・フィッションをデータ局所性の向上に使うこともできます。次のコードを見てみましょう。

for (i = 0; i < list_len; i++)
  for (j = prime[i]; j < N; j += prime[i])
    marked[j] = 1;

外側のループは、素数配列から内側のループの開始インデックスとステップを選択しています。その後、内側のループは marked 配列のその範囲において、選択された要素に値 1 を設定します。marked 配列が十分に大きい場合は、外側のループの後続の反復で必要となる marked の初期の要素からのキャッシュラインを、内側のループの実行によって追い出してしまいます。この動作は、ループのシリアル版と並列版の双方でキャッシュヒット率の低下を招きます。

ループ・フィッションによりキャッシュに収まるように内側のループの反復を分割して、一旦取り込まれたキャッシュラインを再利用できるようにします。フィッションを達成するには、最内ループによって実行される範囲を制御する別のループを追加します。

for (k = 0; k < N; k += CHUNK_SIZE)
  for (i = 0; i < list_len; i++) {
    start = f(prime[i], k);
    end = g(prime[i], k);
    for (j = start; j < end; j += prime[i])
      marked[j] = 1;
  }

上記のコードの最外ループの反復で、i ループのセットが実行されます。素数配列の要素から、(外側のループによって制御される) マークされた配列のチャンクの開始インデックスと終了インデックスを見つける必要があります。この処理は、f() ルーチンと g() ルーチン内でカプセル化されています。このように、次のチャンクが処理される前にマークされた同じチャンクが処理されます。チャンクは互いに独立して処理されるため、外側のループの反復を並列で実行できるようになります。

入れ子構造のループを結合して反復回数を増やすという最適化手法は、ループの反復を効果的に並列化するのに役立ちます。たとえば、反復回数が 23 回と 1,000 回の 2 段の入れ子ループのコードを考えてみましょう。23 は素数のため、外側のループの反復を均等に分けることができません。また、1,000 回は、内側のループのみをスレッド化した場合に生じるオーバーヘッドを最小限に抑えるには十分な処理量とは言えません。反対に、ループを 23,000 回の反復処理を行う 1 つのループに融合すると、オリジナルのコードを並列化し、問題を軽減できます。

#define N 23
#define M 1000
. . .
for (k = 0; k < N; k++)
  for (j = 0; j < M; j++)
    wn[k][j] = Work(w[k][j], k, j);

#define N 23
#define M 1000
. . .
for (kj = 0; kj < N*M; kj++) {
  k = kj / M;
  j = kj % M;
  wn [k][j] = Work(w[k][j], k, j);
}

しかし、反復変数がそれぞれループ本体内で使用される場合 (インデックス配列など) 、新しいループカウンターは対応する成分値に変換して戻さなければならず、元のアルゴリズムにはなかったオーバーヘッドが生じます。

同じようなインデックスのループを融合 (または結合) することで、粒度とデータの局所性を向上し、並列化のオーバーヘッドを最小限に抑えます。最初の 2 つのループの例は、簡単に結合することができます。

  for (j = 0; j < N; j++)
    a[j] = b[j] + c[j];
  for (j = 0; j < N; j++)
    d[j] = e[j] + f[j];
  for (j = 5; j < N - 5; j++)
    g[j] = d[j+1] + a[j+1];

  for (j = 0; j < N; j++)
  {
    a[j] = b[j] + c[j];
    d[j] = e[j] + f[j];
  }
  for (j = 5; j < N - 5; j++)
    g[j] = d[j+1] + a[j+1];

これらのループを結合することで、反復ごとの処理量 (例えば、粒度) が増し、ループのオーバーヘッドが抑えられます。3 番目のループは反復回数が異なるため簡単には結合できません。さらに、3 番目のループと前の 2 つのループの間にはデータの依存性があります。

OpenMP の if 節を使用して、ランタイム情報に基づいてシリアル実行または並列実行を指示できます。実行時までループの反復回数が特定できないことがあります。OpenMP の並列領域を複数のスレッドで実行する際にパフォーマンスに悪影響がある場合 (例えば、少ない反復回数)、次の例で示すように、最小しきい値を指定するとパフォーマンスの維持に役立ちます。

#pragma omp parallel for if(N >= threshold)
  for (i = 0; i < N; i++) { ... }

このコード例では、反復回数 (N) が指定したしきい値 (threshold) を超えた場合のみ並列でループが実行されます。

インテル^®TBB にはこれに相当するものがないため、明示的な条件付きテストを行って並列実行かシリアル実行を決定します。または、並列アルゴリズムを呼び出し、低い N の値に対してシングルスレッドの使用を決定する自由をインテル^®TBB のタスク・スケジューラーに与えます。ただし、この方法には、いくらかのオーバーヘッドが生じます。