インテル® Cilk™ Plus の配列表記による外部ループのベクトル化

この記事は、インテル® デベロッパー・ゾーンに掲載されている「Outer Loop Vectorization via Intel Cilk Plus Array Notations」の日本語参考訳です。

はじめに

外部ループのベクトル化は、パフォーマンスを向上するテクニックの 1 つです。デフォルトでは、コンパイラーは入れ子のループ構造の最内ループをベクトル化しようと試みます。しかし、最内ループの反復回数が少ない場合、内部ループのベクトル化は効果的ではありません。外部ループに多くのワークが含まれている場合、C++ 配列表記を利用して外部ループのベクトル化を模倣できます。C++ 配列表記は、インテル® C++ Composer XE に含まれているインテル® Cilk™ Plus の機能です。

トピック

配列表記による外部ループのベクトル化について説明します。

C++ 配列表記を用いて、(内部ループの構造を維持しつつ外部ループをベクトル化する)「外部ループをベクトル化」するような方法でループをブロック化することができます。次に、マンデルブロー集合の計算例を示します。

シリアルコード:

void serial_mandel(

   float c_re[SIZE], float c_im[SIZE],
   unsigned int max_recurrences,
   char output[SIZE])
{
   for (int i = 0; i < SIZE; i++) {
       unsigned int iter = 0;
       float z_re = c_re[i];
       float z_im = c_im[i];

       // ループが max_recurrences に達した場合
       // c はマンデルブロー・セットの要素
       while (iter < max_recurrences) {
           if (z_re * z_re + z_im * z_im > 4.0) {
              break; // 半径 2 の円でエスケープ
           }

       float new_z_re = c_re[i] + z_re*z_re ? z_im*z_im;
       float new_z_im = c_im[i] + 2.*z_re*z_im;
       iter++;
      }

      // 8-bpp イメージの範囲で反復数をスケール
      output = static_cast<unsigned char>(static_cast<float>(iter) /
      max_recurrences * 255);
   }
}  

このコードには 2 重のループがあります。外部ループは、複素平面の座標を表す、入力セットのポイントを反復します。 各ポイントで、内部ループは座標を初期条件として再帰を計算し、飽和する反復数をカウントします。

内部ループの反復数は未知数の反復の合計であるため、内部ループはベクトル化の候補として適切ではありません。一方、外部ループは各ポイントで再帰を独立して計算できるため、適切なベクトル化の候補です。

外部ループにコードが存在するため、コンパイラーはループ変換を自動的に行いません (コンパイラーは干渉するコードがない「完全な」入れ子のループのみ自動的にループ変換を行います)。

配列表記を用いて外部ループのベクトル化を模倣できます。

void mandel_v(double c_re[SIZE], double c_im[SIZE], int max_recur, char output[SIZE])
{
   float count[VLEN];

   for (int i = 0; i < size; i += VLEN) {
       double z_re[VLEN], z_im[VLEN], new_z_re[VLEN], new_z_im[VLEN];
       int test[VLEN];
       z_re[:] = c_re[i:VLEN];
       z_im[:] = c_im[i:VLEN];
       int iter;

     // z を乗算できる回数をカウント (4 を超えるまで)
     // count[:] は結果
     count[:] = 0;
     for (iter=0; iter<max_recur; iter++) {
       test[:] = (z_re[:] * z_re[:] + z_im[:] * z_im[:]) <= 4.;

       if (__sec_reduce_all_zero(test[:])) {
              break;
       }

       count[:] += test[:];

       // z[:] が <= 4 かどうかに応じて 1 または 0 を追加
       new_z_re[:] = c_re[:] + z_re[:]*z_re[:] - z_im[:]*z_im[:];
       new_z_im[:] = c_im[:] + 2.*z_re[:]*z_im[:];
       z_re[:] = new_z_re[:];
       z_im[:] = new_z_im[:];
     }

     output[i:VLEN] = (char)((float)count[:] / max_recur*255);
   }
}

このコードは、スカラー値を VLEN サイズの部分配列へ再配置するという基本的な手法を使っています。配列全体の長さを広くすると、部分配列が大きくなり、最適でないコードが生成される原因となるため、配列全体の長さは大きくしません。このため、外部ループをなくすのではなく、VLEN サイズのチャンクでポイントを反復します。

この変換の興味深い点は、オリジナルコードの while ループを処理する方法にあります。オリジナルコードでは、飽和するまで各ポイントでループを実行してから停止しています。このコードでは複数の VLEN ポイントを並列に処理しているため、飽和したときに各ポイントの反復を停止して、同じポイントに同じコードを使用しなければいけません (SIMD セマンティクス)。このため、各ポイントの飽和を並列にテストして、結果を 1 または 0 にします。この 1 または 0 をカウントベクトルに追加します (ポイントが飽和していない場合は 1、飽和している場合は 0)。ポイントが飽和している場合、ベクトルカウンターはインクリメントされますが、そのベクトル要素は無操作 (no-op) となります。max_recur になるまで無操作加算 (no-op add) を行わないで済むように、__sec_reduce_all_zero() 組込み関数を利用して、すべてのポイントが飽和してループがブレークしたかどうかをテストします。

ベクトルのスピードアップは無操作加算 (no-op add) が生成された数 (指定された VLEN の結果値の均一性) に依存します。1 つを除くすべてのポイントが飽和し、その 1 つのポイントが最大値まで反復を繰り返す場合、すでに飽和したポイントの計算が無駄になります。この場合、マシンサイズより小さな VLEN のほうが適切に動作することになります。プログラマーは適切に動作するサイズを調べる必要があります。__sec_reduce_all_zero() では多少のオーバーヘッドが発生します。ある入力セットでカウンターの結果が常に max_recur に近くなる場合、そのセットは省略されます。

この手法は、実際に外部ループのベクトル化を行うことなく、外部ループをベクトル化した場合と同じ結果が得られます。VLEN サイズのチャンクで外部ループをブロックし、チャンクに基づいたベクトル演算 (各配列表記ステートメントは短い 1 ステートメントの内部ループ) を行うことで、コンパイラーを支援します。

外部ループのベクトル化に関するそのほかの例は、次の論文をご覧ください。

ISCA 2012 の論文: 「Can Traditional Programming Bridge the Ninja Performance Gap for Parallel Computing Applications?」(2012 年 6 月)

まとめ

デフォルトでは、コンパイラーは入れ子のループ構造の最内ループをベクトル化しようと試みます。この最内ループの反復回数が少ない場合、最内ループのベクトル化は効果的ではありません。しかし、外部ループの反復回数が多い場合、外部ループのベクトル化が効果的です。C++ 配列表記を利用して、外部ループのベクトル化を模倣するこができます。C++ 配列表記は、インテル® C++ Composer XE に含まれているインテル® Cilk™ Plus の機能です。

この記事は、「Programming and Compiling for IntelR Many Integrated Core Architecture」(英語) の一部「Outer Loop Vectorization via Intel Cilk Plus Array Notations」の翻訳です。インテル® Xeon Phi™ コプロセッサー上にアプリケーションを移植し、チューニングを行うには、各リンクのトピックを参照してください。アプリケーションのパフォーマンスを最大限に引き出すために必要なステップを紹介しています。

「ベクトル化の基本」に戻る

コンパイラーの最適化に関する詳細は、最適化に関する注意事項を参照してください。