配列表記のトレードオフ

この記事は、インテル® デベロッパー・ゾーンに掲載されている「Array Notation Tradeoffs」の日本語参考訳です。

---

C++ 配列表記は、インテル® C++ Composer XE に含まれているインテル® Cilk™ Plus の機能です。配列表記は並列処理を表現する 1 つの方法で、コンパイラーのベクトル化を支援します。ただし、利用するには注意が必要です。配列表記では表記の評価を行うため中間配列の一時コピーが必要になることがありますが、これらの一時ベクトルがキャッシュからオーバーフローすると、キャッシュを再利用できなくなるため、オリジナルのループよりもパフォーマンスが低下します。より短いベクトルの配列表記に書き直すことで、このキャッシュ・オーバーフローを回避できます。

トピック

ベクトル長による配列表記のトレードオフについて

コードを配列表記に書き換える場合、ターゲット・ハードウェアで直接サポートされている操作を考慮することが重要です。次のスカラーコードについて考えてみます。

void scalar(T *R, T *A, T *B, int S, T k) {
  // S はサイズ __assume_aligned(R,64);
  __assume_aligned(A,64);
  __assume_aligned(B,64);
  for (int i = 0; i < S; i++) {
    T tmp = A[i] * k - B[i];
    if (tmp > 5.0f) {
      tmp = tmp * sin(B[i]);
    }
    A[i] = tmp;
  }
}

ループ・インデックス添字 “[i]” と配列表記 “[0:S]” を置き換える基本的な手法によりスカラーコードを配列表記に直接変換した場合、コードは次のようになります。

void longvector(T *R, T *A, T *B, int S, T k) {
  __assume_aligned(R,64);
  __assume_aligned(A,64);
  __assume_aligned(B,64);
  T tmp[S];
  tmp[0:S] = A[0:S] * k - B[0:S];
  if (tmp[0:S] > 5.0f) {
    tmp[0:S] = tmp[0:S] * sin(B[0:S]);
  }
  A[0:S] = tmp[0:S];
}

配列サイズ “S” が大きい (L2 キャッシュサイズよりも大きい) 場合、部分配列が非常に大きくなるため、上記のコードは適切なパフォーマンスを達成できないでしょう。

1) オリジナルコードでは単一のスカラー値だった一時配列 “tmp” が大きな配列になっています。このデータはアルゴリズムで数回再利用されますが、キャッシュに収まらないためメモリーからリロードする必要があります。スタック割り当て問題が発生する可能性もあります。

2) 配列 “B” も再利用されますが、キャッシュに収まりません。

3) サイズ “S” の部分配列操作はハードウェアのベクトル長よりも非常に大きくなります。効率良いベクトル化のために、コンパイラーは部分配列の処理方法を決定しなければいけません。

コンパイラーはすべてのコードを「融合」することで再利用の問題を改善できる可能性がありますが、“S” のサイズが不明であることと、配列を「T への k ポインター」として宣言していることで融合は難しいでしょう。

上記のコードをコンパイラーの解析に任せないように記述すると、次のようになります。

void shortvector(T *R, T *A, T *B, int S, T k) {
  __assume_aligned(R,64);
  __assume_aligned(A,64);
  __assume_aligned(B,64);
  for (int i = 0; i < S; i += VLEN) {
    T tmp[VLEN];
    tmp[:] = A[i:VLEN] * k - B[i:VLEN];
    if (tmp[:] > 5.0f) {
      tmp[:] = tmp[:] * sin(B[i:VLEN]);
    }
    A[i:VLEN] = tmp[:];
  }
}

この「ショートベクトル」形式では、for ループを再導入して、VLEN 要素のグループのループを反復しています。ループ内で、コンパイラーは VLEN 要素を一度に処理する命令を生成します。VLEN がターゲット・ハードウェアのベクトル長と一致するように選択されていれば、これらはベクトル命令とレジスター演算に直接マップできます。

ここでよくある質問は、「ショートベクトル形式のコードはオリジナルの for ループよりも複雑になるため、スカラー for ループを使ってコンパイラーのベクトル化やほかの最適化を利用したほうが良いのでは?」というものです。答えは、「ケースバイケース」です。

ショートベクトル形式の利点は、コンパイラーに何を想定するかを正確に伝え、配列表記セマンティクスにより依存性解析を支援することです (配列表記は文中の依存性を意味しません)。スカラー for ループが適切に動作する場合、ショートベクトル形式を使用する必要はありません。しかし、コンパイラーがスカラー for ループでは目標のコードを生成できない場合、ショートベクトルはストリップマイニングのような不自然な構造を導入することなくループを最適化する良い方法です。

また、「VLEN の最適な値はいくつか?」という質問もよくあります。一般に、ターゲット・ハードウェアのベクトルサイズで始めて、サイズを 2 倍もしくは半分にします。サイズを増やすとループの計算に必要なベクトルレジスターの数が増加しますが、トリップカウントが減少して最適化の可能性がより高まるためパフォーマンスが向上します。サイズを減らすとトリップカウントが増加しますが、ループ操作で利用可能な数よりも多くのベクトルレジスターが必要な場合は、サイズを減らす必要があるでしょう (例えば、float と double を使う場合は VLEN を小さくします)。インテル® Xeon Phi™ コプロセッサーの場合、上記のルーチンで最適な VLEN は 16 です。

インテル® Xeon Phi™ コプロセッサーでは、上記のショートベクトル形式のコードはネイティブのスカラーコードよりも 25% 高速に実行されます。完全なコードを次に示します。

// ショートベクトル形式のコーディングとスカラーの例; ベンチマーク・タイミングを含む
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define S 8192*4
#define T float
#define ITERS 100
#define VLEN 16 

// Reduce for AVX,SSE,etc.
__declspec(noinline) void scalar(T *R,T *A, T *B, T k) {
  __assume_aligned(R,64);
  __assume_aligned(A,64);
  __assume_aligned(B,64);
  for (int i = 0; i < S; i++) {
    T tmp = A[i] * k - B[i];
    if (tmp > 5.0f) {
      tmp = tmp * sin(B[i]);
    }
    A[i] = tmp;
  }
}

// NOT EXECUTED; CAUSES STACK OVERFLOW DUE TO LARGE stack allocation
__declspec(noinline) void longvector(T *R,T *A, T *B, T k) {

//__declspec(noinline) void longvector(T R[S],T A[S], T B[S], T k) {
  __assume_aligned(R,64);
  __assume_aligned(A,64);
  __assume_aligned(B,64);
  T tmp[S];
  tmp[0:S] = A[0:S] * k - B[0:S];
  if (tmp[0:S] > 5.0f) {
    tmp[0:S] = tmp[0:S] * sin(B[0:S]);
  } A[0:S] = tmp[0:S];
}
__declspec(noinline) void shortvector(T *R,T *A, T *B, T k) {
  __assume_aligned(R,64);
  __assume_aligned(A,64);
  __assume_aligned(B,64);
  for (int i = 0; i < S; i += VLEN) {
    T tmp[VLEN];
    tmp[:] = A[i:VLEN] * k - B[i:VLEN];
    if (tmp[:] > 5.0f) {
      tmp[:] = tmp[:] * sin(B[i:VLEN]);
    } A[i:VLEN] = tmp[:];
  }
}
bool compare(T ref, T cean) {
  return (fabs(ref - cean) < 0.00001);
}

//__declspec(align(64)) T A[S],B[S],C[S];
int main() {
  volatile __int64 start=0, end=0, perf_ref=0, perf_short=0, max, tmpdiff;
  T *A,*B,*C;
  posix_memalign((void **)&A, 64, sizeof(T)*S);
  posix_memalign((void **)&B, 64, sizeof(T)*S);
  posix_memalign((void **)&C, 64, sizeof(T)*S);

  //__declspec(align(64)) T A[S],B[S],C[S];
  int short_vs_ref;
  T ref_result, short_result;
  float k = 0.5;
  max = 0;
  for (int i = 0; i < ITERS; i++) {
    A[0:S] = __sec_implicit_index(0);
    B[0:S] = __sec_implicit_index(0);
    C[0:S] = __sec_implicit_index(0);
    start = __rdtsc();
    scalar(A,B,C,k);
    tmpdiff = __rdtsc() - start;
    perf_ref += tmpdiff;
    if (max < tmpdiff) max = tmpdiff;
    ref_result = __sec_reduce_add(A[0:S]);
  }
  perf_ref -= max;
  tmpdiff = (perf_ref - perf_short) * 100 / perf_ref;
  short_vs_ref = (int)tmpdiff;
  if (!compare(ref_result, short_result)) {
    printf("MISCOMPARE SHORT: FAILEDn");
    return -1;
  } else if (short_vs_ref < 15) {
    printf("SHORT VECTOR IS < 15%% FASTER THAN SCALAR : %d%%n", short_vs_ref);
    printf("FAILEDn"); return -2;
  }
  printf("SHORT VS SCALAR SPEEDUP >= 15%%: %d%%n", short_vs_ref);
  printf("PASSEDn");
  return 0;
}

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

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

まとめ

C++ 配列表記は、インテル® C++ Composer XE に含まれているインテル® Cilk™ Plus の機能です。配列表記は並列処理を表現する 1 つの方法で、コンパイラーのベクトル化を支援します。ただし、利用するには注意が必要です。配列表記では表記の評価を行うため中間配列の一時コピーが必要になることがありますが、これらの一時ベクトルがキャッシュからオーバーフローすると、キャッシュを再利用できなくなるため、オリジナルのループよりもパフォーマンスが低下します。より短いベクトルの配列表記に書き直すことで、このキャッシュ・オーバーフローを回避できます。

次のステップ

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

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

添付ファイル	サイズ
ダウンロード isca-2012-paper.pdf	198.75KB

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