ギャザーによる構造化されたデータのベクトル化

同カテゴリーの次の記事

組込み開発におけるガイド付き自動並列化の利用

この記事は、インテル® デベロッパー・ゾーンに掲載されている「Best Known Method: Coaxing the Compiler to Vectorize Structured Data via Gathers」の日本語参考訳です。


最も一般的な手法

コンパイラーがより効率の良いベクトルコードするのを支援する手法として、コンパイラーがコードの並列化およびベクトル化をよく理解できるように複雑なデータ構造を分解する方法があります。クリティカルな処理カーネルをベクトル化することはパフォーマンスの向上につながるため一般に推奨されますが、インテル® Xeon Phi™ コプロセッサーをターゲットにする場合は特に重要です。データアクセスを分解することで、コンパイラーはベクトルギャザーやベクトルスキャッターのような、より高度な機能を使用できます。ベクトルロードとベクトルストアのパフォーマンスを最大限に引き出すには、隣接するデータ要素をアクセスするのが最適ですが、インデックスによるデータアクセスが必要なこともあるでしょう。ベクトルギャザーとベクトルスキャッターは、一般にベクトルロードとベクトルストアよりも遅くなります。ただし、ベクトルデータの生成に続くベクトル計算の量が、ベクトルギャザーによる遅延を相殺するのに十分であれば、使用するメリットはあります。コンパイラーは必要に応じてベクトルギャザーとベクトルスキャッター命令を生成しますが、複素数データ構造の場合はそれが困難です。これらの複素数データ構造へのアクセス方法をコンパイラーに知らせることで、ベクトルギャザーとベクトルスキャッター命令を生成できるようになります。

オリジナルのコード

最も一般的な手法は、分子動力学 (MD) コードの解析から考案されたものです。MD コードで、原子の力は通常 3 つの値 (x、y、z) で表現されます。これらの力量は、すべての原子を含む位置配列に格納されます。

// 原子の力量
typedef struct float3 {
   float x;
   float y;
   float z;
} float3;
 
// 位置は float3 の配列
float3* position; 

指定された原子の力量の計算は、この配列で隣接する原子によって決定されます。各原子について、隣接する原子のリストがあります。指定された原子の力量を計算するには、このリストにアクセスして隣接する原子をすべて調べます。

次のコードは、原子をすべて含む位置配列に neighList 配列のインデックスを介してアクセスしています。隣接する値は、構造 jpos に配置されます。続いて、この隣接する値を用いて原子の力量を計算します。

181    for (int k=0; k<dis; k++){

183        jpos = position[ neighList[j*dis + k + maxNeighbors * i] ];

192        float delx = ipos.x - jpos.x;
193        float dely = ipos.y - jpos.y;
194        float delz = ipos.z - jpos.z;
195        float r2inv = delx*delx + dely*dely + delz*delz;

次のコードは、上記のコードのアセンブリー・コードの一部です。ベクトル命令が使用された場合でも、位置配列の要素が一度に 1 つだけアクセスされていることが分かります。neighList は位置配列のインデックスを取得するためにアクセスされ (行 #183)、このインデックスはレジスター %rax にロードされます。%rax の x、y、z でインデックスされた位置の 3 つの隣接する要素は、vsubps 減算命令で別々にメモリーからロードされます (行 #192、#193、#194)。vsubps 命令の {1to16} 命令修飾子は、減算でソースベクトルの 16 の要素すべてに 1 つのデータ値をブロードキャストすることを示しています。ベクトル命令が使用された場合でも、後の計算はすべてスカラー演算で行われています。

    movl      8(%r14,%r15,4), %eax                          #183.30 c1
    movslq    %eax, %rax                                    #183.21 c3
    shlq      $4, %rax                                      #183.21 c5
    vsubps    (%rax,%rbx){1to16}, %zmm19, %zmm28{%k4}       #192.28 c8
    vsubps    4(%rax,%rbx){1to16}, %zmm18, %zmm27{%k4}      #193.28 c10
    vsubps    8(%rax,%rbx){1to16}, %zmm22, %zmm26{%k4}      #194.32 c12
    vmulps    %zmm27, %zmm27, %zmm0{%k4}                    #195.41 c14
    vmovaps   %zmm28, %zmm1                                 #195.53 c16
    vmovaps   %zmm26, %zmm2                                 #195.53 c18
    vfmadd213ps %zmm0, %zmm28, %zmm1{%k4}                   #195.53 c20
    nop                                                     #195.53 c22
    vfmadd213ps %zmm1, %zmm26, %zmm2{%k4}                   #195.53 c24

変更後のコード

パフォーマンスを向上させるため、コンパイラーがスカラー値ではなくフルベクトルを使用するベクトル・メモリー・アクセスおよびベクトル命令を利用するようにコードを変更しました。位置配列から隣接する値をロードした後、(コード領域で示されていない) 多くの力量の計算を完了する必要があります。これらの計算をスカラー値ではなくフルベクトルで行うのが理想的です。

neighList は位置配列にアクセスするために使用されるインデックスの連続するリストであることを思い出してください。これはベクトルギャザーに理想的です。インデックスがロード直後の neighList のベクトルであれば、ベクトルギャザー命令により位置配列にアクセスできます。

複雑なデータ型のベクトルを作成することは、将来考慮すべきコンパイラーの課題です。現時点では、コンパイラーを支援するため、個々のデータ要素に明示的にアクセスするように、複雑なデータ型のインデックスを再構成しました。このコード変更により、コンパイラーはベクトルギャザーを使用してコードを完全にベクトル化できます。以下のコードで、位置配列の要素へのアクセスは明示的に行われます。

181     for (int k=0;k<dis;k++){ 

184         jposx = position[ neighList[j*dis + k + maxNeighbors * i] ].x;
185         jposy = position[ neighList[j*dis + k + maxNeighbors * i] ].y;
186         jposz = position[ neighList[j*dis + k + maxNeighbors * i] ].z;


192         float delx = iposx - jposx;
193         float dely = iposy - jposy;
194         float delz = iposz - jposz;
195         float r2inv = delx*delx + dely*dely + delz*delz;

次のコードは、上記のコードのアセンブリー・コードの一部です。位置配列がベクトルギャザー命令でアクセスされていることが分かります (行 #184、#185、#186)。ベクトルギャザー命令は、x、y、z データ値を 3 つのベクトルレジスター %zmm21、%zmm22、%zmm23 に配置します。ベクトル減算 (vsubps) 命令 (行 #192、#193、#194) は、スカラー値ではなくフルベクトルを使用するようになりました。

        vgatherdps 4(%r13,%zmm20,4), %zmm22{%k4}                #185.22
        jkzd      ..L318, %k4   # Prob 50%                      #185.22
 ..L319 vgatherdps 4(%r13,%zmm20,4), %zmm22{%k4}                #185.22
        jknzd     ..L319, %k4   # Prob 50%                      #185.22
 ..L318 vgatherdps (%r13,%zmm20,4), %zmm21{%k3}                 #184.22
        jkzd      ..L320, %k3   # Prob 50%                      #184.22
 ..L321 vgatherdps (%r13,%zmm20,4), %zmm21{%k3}                 #184.22
        jknzd     ..L321, %k3   # Prob 50%                      #184.22
 ..L320 vsubps    %zmm22, %zmm11, %zmm2                         #193.27 c27
        vgatherdps 8(%r13,%zmm20,4), %zmm23{%k5}                #186.22
        jkzd      ..L322, %k5   # Prob 50%                      #186.22
 ..L323 vgatherdps 8(%r13,%zmm20,4), %zmm23{%k5}                #186.22
        jknzd     ..L323, %k5   # Prob 50%                      #186.22
 ..L322 vsubps    %zmm21, %zmm12, %zmm3                         #192.27 c33
        cmpl      %r15d, %r10d                                  #158.9  c33
        vmulps    %zmm2, %zmm2, %zmm31                          #195.41 c35
        vsubps    %zmm23, %zmm9, %zmm1                          #194.31 c37
        vfmadd231ps %zmm3, %zmm3, %zmm31                        #195.41 c39
        vfmadd231ps %zmm1, %zmm1, %zmm31                        #195.41

このコードを理解するには、ベクトルギャザー命令が演算を開始する命令と演算が完了するまで継続する命令のペアで動作することに注意してください。この例の残りのベクトル命令は、個々の値のベクトルで演算を行い、%zmm1 にフルベクトルの結果を格納します。

このコード変更により、力量の計算がスカラー値ではなくフルベクトルで行われるようになったことで、MD アプリケーション全体のパフォーマンスは 2.5 倍も向上しました。

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

関連記事

  • とらえどころのないアルゴリズム – 並列スキャン (追記)とらえどころのないアルゴリズム – 並列スキャン (追記) この記事は、インテル® デベロッパー・ゾーンに公開されている「Elusive Algorithms - Parallel Scan」の日本語参考訳です。 先月、IDZ の MIC フォーラムでの問い合わせ "C 言語でインテル® Cilk™ Plus を使用して包括的なスキャンを行うには? […]
  • インテル® MIC アーキテクチャーの準備インテル® MIC アーキテクチャーの準備 この記事は、インテル® デベロッパー・ゾーンに掲載されている「Preparing for the Intel® Many Integrated Core Architecture」の日本語参考訳です。 インテル® MIC アーキテクチャー向けのコンパイラー手法 インテル® […]
  • Linux* ホスト上でインテル® Xeon Phi™ コプロセッサー向けアプリケーションをデバッグLinux* ホスト上でインテル® Xeon Phi™ コプロセッサー向けアプリケーションをデバッグ この記事は、インテル® デベロッパー・ゾーンに掲載されている「Debugging Intel® Xeon Phi™ Applications on Linux* Host」の日本語参考訳です。 目次 はじめに インテル® MIC 向けデバッグ・ソリューション 入手方法 インテルから提供される GNU* GDB […]
  • インテル® C++ コンパイラーのオフロード機能を効率良く使用するにはインテル® C++ コンパイラーのオフロード機能を効率良く使用するには この記事は、インテル® デベロッパー・ゾーンに掲載されている「Effective Use of the Intel Compiler's Offload Features」の日本語参考訳です。 はじめに ここでは、インテル® メニー・インテグレーテッド・コア (インテル® MIC) アーキテクチャー向けのインテル® […]
  • ループのベクトル化によるプログラムの最適化ループのベクトル化によるプログラムの最適化 この記事は、インテル® デベロッパー・ゾーンに掲載されている「Program Optimization through Loop Vectorization」の日本語参考訳です。 はじめに この記事では、有限差分ステンシル計算を例に、インテル® メニー・インテグレーテッド・コア (インテル® MIC) […]