外部ループのベクトル化

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

---

はじめに

外部ループのベクトル化は、パフォーマンスを向上するテクニックの 1 つです。デフォルトでは、コンパイラーは入れ子のループ構造の最内ループをベクトル化しようと試みます。しかし、最内ループの反復回数が少ない場合、内部ループのベクトル化は効果的ではありません。しかし、外部ループに多くのワークが含まれている場合、要素関数、ストリップマイニング、プラグマ/宣言子 SIMD を組み合わせて、効果的に外部ループをベクトル化できます。

トピック

外部ループのベクトル化の例を次に示します。

入れ子のループの例:

以下のスパース-行列-ベクトルパターンについて考えてみます。

for(LocalOrdinalType row=ib*BLOCKSIZE; row<top; ++row) {
    local_y[row]=0.0;

    for(LocalOrdinalType i=Arowoffsets[row]; i<Arowoffsets[row+1]; ++i) {
      local_y[row] += Acoefs[i]*local_x[Acols[i]];
    }
}

内部ループのベクトル化と外部ループのベクトル化:

内部の i ループをベクトル化できます。デフォルトのベクトル化では、配列 “Acoefs” と “Acols” のユニットストライド方式のロードと、配列 “local_x” の要素のギャザーが行われます。”local_y” ストレージアクセスはループの外に移動され、コンパイラーによりベクトル化されたループにリダクション temp が追加されます。

あるいは、(要素関数を利用して) 外部ループをベクトル化することができます。この場合、コンパイラーは内部ループ本体に対して、”local_y”、”Acoefs”、”Acols” ロードがギャザーになり、”local_x” が引き続きギャザーになるようにユニットストライド方式のロード/ストア命令を生成します。

このアプローチが効果的な理由: 内部ループのトリップカウントの平均が小さく (ベクトル化するには小さすぎる)、外部ループのトリップカウントが大きい場合、ベクトル化の効率が向上します。
その他の考慮事項: 外部ループのベクトル化により、ベクトル化された外部ループで (ループ分割などの) 処理コストが増加していないか?　内部ループのベクトル化と比較して、パフォーマンスの向上率と余分なギャザー/スキャッターのコストを比較検討する必要があります (アライメントを指定すると、外部ループのベクトル化はより困難になります)。

外部ループをベクトル化する方法:

1) 内部ループの本体をベクトル要素関数として抽出し、simd プラグマを用いて外部ループを直接ベクトル化します。

2) 外部ループの反復をストリップマイニングし、ストリップで動作するようにループ本体の各ステートメントを変更します。プログラマーは、インテル® Cilk™ Plus の配列表記を利用することで、このアプローチを自然に表現できます。

3) 外部ループに simd プラグマ (と正しい節) を追加すると、コンパイラーはこれらのサブセットをベクトル化できる可能性があります。ただし、可能な場合は上記の 2 つのアプローチのいずれかを使用することを推奨します。そのほうが、コンパイラーはより適切なベクトル化を行えるでしょう。

前の例では、以下のように 1 番目の方法で外部ループをベクトル化できます。

#pragma simd
    for(LocalOrdinalType row=ib*BLOCKSIZE; row<top; ++row) {
       local_y[row]=0.0;
       Inner_loop_elem_function(local_y, row, Acoefs, local_x,
                                Acols, Arowoffsets);
   }


__declspec(vector(uniform(Arowoffsets, Acoefs, local_x, Acols, local_y),
                  linear(row))))
Inner_loop_elem_function(float *local_y, int row, float *Acoefs,
                         float *local_x, int *Acols, int *Arowoffsets)
{
    for(LocalOrdinalType i=Arowoffsets[row]; i<Arowoffsets[row+1]; ++i) {
        local_y[row] += Acoefs[i]*local_x[Acols[i]];
    }
}

要素関数を使った外部ループのベクトル化の別の例を次に示します。

#pragma simd // 要素関数の呼び出し位置の外部ループの simd プラグマ 
for (int i = beg*16; i < end*16; ++i) { 
    particleVelocity_block(px[i], py[i], pz[i], destvx + i, destvy + i, 
                           destvz + i, vel_block_start, vel_block_end); 
}

要素関数の定義:

__declspec(vector(uniform(start,end), linear(velx,vely,velz)))
static void particleVelocity_block(const float posx, const float posy,
                                   const float posz, float *velx,
                                   float *vely, float *velz,
                                   int start, int end) {
    __assume_aligned(velx,64);
    __assume_aligned(vely,64);
    __assume_aligned(velz,64);
    for (int j = start; j < end; ++j) {
        const float del_p_x  = posx - px[j];
        const float del_p_y  = posy - py[j];
        const float del_p_z  = posz - pz[j];
        const float dxn = del_p_x * del_p_x + del_p_y * del_p_y +
                          del_p_z * del_p_z +pa[j]* pa[j];
        const float dxctaui  = del_p_y * tz[j] - ty[j] * del_p_z;
        const float dyctaui  = del_p_z * tx[j] - tz[j] * del_p_x;
        const float dzctaui  = del_p_x * ty[j] - tx[j] * del_p_y;
        const float dst      = 1.0f/std::sqrt(dxn);
        const float dst3     = dst*dst*dst;
        *velx               -= dxctaui * dst3;
        *vely               -= dyctaui * dst3;
        *velz               -= dzctaui * dst3;
    }
}

ベクトル要素関数の uniform 節と linear 節の使用に注意してください。最後の 2 つの関数の引数 vel_block_start と vel_block_end はすべての i で同じであるため、これらの 2 つの引数は uniform としてマークされます。ポインター引数 velx、vely、velz は、単一の呼び出し位置に対応する linear としてマークされます。

これらのポインター変数は、要素関数内部の適切な節を用いて (呼び出し位置でポインターのアライメント情報を利用することにより) アラインとしてもマークされます。

外部ループのベクトル化に関するそのほかの例は、次の論文をご覧ください。
ISCA 2012 の論文: 「Can Traditional Programming Bridge the Ninja Performance Gap for Parallel Computing Applications?」 (2012 年 6 月)

まとめ

デフォルトでは、コンパイラーは入れ子のループ構造の最内ループをベクトル化しようと試みます。この最内ループの反復回数が少ない場合、最内ループのベクトル化は効果的ではありません。しかし、外部ループの反復回数が多い場合、外部ループのベクトル化が効果的です。外部ループをベクトル化するには、要素関数とプラグマ/宣言子 SIMD を組み合わせてベクトル化を外部レベルに移動します。

次のステップ

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

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

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