自動ベクトル化でvgather系命令が出てくる時

はじめに

Haswellからvgather系の命令が出てきた訳ですが、遅いらしく"Will get improvement in Intel next generation CPU"とアナウンスされたほど。組み込み関数で書かない限りはvgather命令は出てこないと思っていたら、そうではなかったという話。アセンブラはintel形式で。ソースコードはgistにある。

コンパイラはicpc (ICC) 16.0.4 20160811で、コンパイルは

$ icpc -S -O3 -xHOST -std=c++11 -masm=intel gather.cpp

で行う。コンパイルしている環境はXeon(R) CPU E5-2680でHaswell世代のXeonである。

行列行列積

科学技術計算でよく見られる計算。以下のような3重ループでかける。ただし、配列cは0クリアされているとする。

for (int i = 0; i < N; i++) {
  for (int j = 0; j < N; j++) {
    for (int k = 0; k < N; k++) {
      c[i][j] += a[i][k] * b[k][j];
    }
  }
}

(もちろん、行列サイズが大きい場合にはこんな手で書かないで、ライブラリを使うべき)

上のコードではベクトル化されないが、以下のように書き換えるとベクトル化される。

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      int sum = 0;
      for (int k = 0; k < N; k++) {
        sum += a[i][k] * b[k][j];
      }
      c[i][j] = sum;
    }
  }

最内ループに相当するアセンブラを取り出してくるとこんな感じ。

..B4.10:                        # Preds ..B4.10 ..B4.9
        vmovdqa   ymm3, ymm0                                    #40.26
        lea       rsi, QWORD PTR [rax+r12]                      #40.26
        vpxor     ymm4, ymm4, ymm4                              #40.26
        lea       rdi, QWORD PTR [16384+rax+r12]                #40.9
        vpxor     ymm6, ymm6, ymm6                              #40.26
        vpgatherdd ymm4, DWORD PTR [rsi+ymm1*8], ymm3           #40.26
        vpmulld   ymm5, ymm4, YMMWORD PTR [r8+rdx*4]            #40.26
        add       rax, 32768                                    #39.7
        vpaddd    ymm7, ymm2, ymm5                              #40.9
        vmovdqa   ymm2, ymm0                                    #40.26
        vpgatherdd ymm6, DWORD PTR [rdi+ymm1*8], ymm2           #40.26
        vpmulld   ymm8, ymm6, YMMWORD PTR [32+r8+rdx*4]         #40.26
        add       rdx, 16                                       #39.7
        vpaddd    ymm2, ymm7, ymm8                              #40.9
        cmp       rdx, rcx                                      #39.7
        jb        ..B4.10       # Prob 99%                      #39.7

vpgatherddというvgather系命令が見られる。

C言語での二次元配列はrow major orderなので、最内ループで配列aはindex kについて連続アクセスになるが、配列bはindex kについて連続アクセスにはならない。そこで、不連続なメモリアクセスになる配列bのデータを8個取って来るためにvgatherを使っている。アセンブラを見る限りでは最内ループを2倍アンロールして16個のintデータについて処理をしていることがわかる。vpgatherddが2回呼ばれているのはそのため。

今、配列a, b, cのデータをintとしてるが、floatにするとどうなるか。
同じようにvgather系命令が見られる。

..B7.4:                         # Preds ..B7.4 ..B7.3                                                                                                         
        vmovdqa   ymm11, ymm0                                   #58.26
        lea       r15, QWORD PTR [r10+rbx]                      #58.26
        vxorps    ymm12, ymm12, ymm12                           #58.26
        vgatherdps ymm12, DWORD PTR [r15+ymm9*8], ymm11         #58.26
        lea       r15, QWORD PTR [16384+rbx+r10]                #58.26
        vxorps    ymm14, ymm14, ymm14                           #58.26
        vmovdqa   ymm13, ymm0                                   #58.26
        vgatherdps ymm14, DWORD PTR [r15+ymm9*8], ymm13         #58.26
        lea       r15, QWORD PTR [32768+rbx+r10]                #58.26
        vfmadd231ps ymm7, ymm12, YMMWORD PTR [r14+r11*4]        #58.9 
        vfmadd231ps ymm1, ymm14, YMMWORD PTR [32+r14+r11*4]     #58.9 
        vxorps    ymm11, ymm11, ymm11                           #58.26
        vmovdqa   ymm15, ymm0                                   #58.26
        vgatherdps ymm11, DWORD PTR [r15+ymm9*8], ymm15         #58.26
        lea       r15, QWORD PTR [49152+rbx+r10]                #58.26
        vxorps    ymm13, ymm13, ymm13                           #58.26
        vmovdqa   ymm12, ymm0                                   #58.26
        vgatherdps ymm13, DWORD PTR [r15+ymm9*8], ymm12         #58.26
        lea       r15, QWORD PTR [65536+rbx+r10]                #58.26
        vfmadd231ps ymm6, ymm11, YMMWORD PTR [64+r14+r11*4]     #58.9 
        vfmadd231ps ymm5, ymm13, YMMWORD PTR [96+r14+r11*4]     #58.9 
        vxorps    ymm11, ymm11, ymm11                           #58.26
        vmovdqa   ymm14, ymm0                                   #58.26
        vgatherdps ymm11, DWORD PTR [r15+ymm9*8], ymm14         #58.26
        lea       r15, QWORD PTR [81920+rbx+r10]                #58.26
        vxorps    ymm13, ymm13, ymm13                           #58.26
        vmovdqa   ymm12, ymm0                                   #58.26
        vgatherdps ymm13, DWORD PTR [r15+ymm9*8], ymm12         #58.26
        lea       r15, QWORD PTR [98304+rbx+r10]                #58.26
        vfmadd231ps ymm4, ymm11, YMMWORD PTR [128+r14+r11*4]    #58.9 
        vfmadd231ps ymm3, ymm13, YMMWORD PTR [160+r14+r11*4]    #58.9 
        vxorps    ymm11, ymm11, ymm11                           #58.26
        vmovdqa   ymm15, ymm0                                   #58.26
        vgatherdps ymm11, DWORD PTR [r15+ymm9*8], ymm15         #58.26
        lea       r15, QWORD PTR [114688+rbx+r10]               #58.26
        vxorps    ymm13, ymm13, ymm13                           #58.26
        add       rbx, 131072                                   #57.7 
        vmovdqa   ymm12, ymm0                                   #58.26
        vgatherdps ymm13, DWORD PTR [r15+ymm9*8], ymm12         #58.26
        vfmadd231ps ymm2, ymm11, YMMWORD PTR [192+r14+r11*4]    #58.9 
        vfmadd231ps ymm10, ymm13, YMMWORD PTR [224+r14+r11*4]   #58.9 
        add       r11, 64                                       #57.7
        cmp       r11, 512                                      #57.7
        jb        ..B7.4        # Prob 99%                      #57.7

しかしながら、floatからdoubleやint64_tに変えるとvgatherは見られなくなる。

doubleの場合

..B7.10:                        # Preds ..B7.10 ..B7.9                
        vmovsd    xmm10, QWORD PTR [rcx+r9]                     #60.26
        vmovsd    xmm11, QWORD PTR [8192+rcx+r9]                #60.26
        vmovhpd   xmm12, xmm10, QWORD PTR [4096+rcx+r9]         #60.26
        vmovhpd   xmm13, xmm11, QWORD PTR [12288+rcx+r9]        #60.26
        vmovsd    xmm15, QWORD PTR [16384+rcx+r9]               #60.26
        vmovsd    xmm10, QWORD PTR [24576+rcx+r9]               #60.26
        vmovhpd   xmm11, xmm15, QWORD PTR [20480+rcx+r9]        #60.26
        vmovsd    xmm15, QWORD PTR [40960+rcx+r9]               #60.26
        vinsertf128 ymm14, ymm12, xmm13, 1                      #60.26
        vfmadd231pd ymm8, ymm14, YMMWORD PTR [r10+rax*8]        #60.9 
        vmovsd    xmm14, QWORD PTR [32768+rcx+r9]               #60.26
        vmovhpd   xmm12, xmm10, QWORD PTR [28672+rcx+r9]        #60.26
        vmovhpd   xmm10, xmm14, QWORD PTR [36864+rcx+r9]        #60.26
        vmovsd    xmm14, QWORD PTR [57344+rcx+r9]               #60.26
        vinsertf128 ymm13, ymm11, xmm12, 1                      #60.26
        vmovhpd   xmm11, xmm15, QWORD PTR [45056+rcx+r9]        #60.26
        vfmadd231pd ymm5, ymm13, YMMWORD PTR [32+r10+rax*8]     #60.9 
        vmovsd    xmm13, QWORD PTR [49152+rcx+r9]               #60.26
        vmovhpd   xmm15, xmm13, QWORD PTR [53248+rcx+r9]        #60.26
        vmovsd    xmm13, QWORD PTR [73728+rcx+r9]               #60.26
        vinsertf128 ymm12, ymm10, xmm11, 1                      #60.26
        vfmadd231pd ymm4, ymm12, YMMWORD PTR [64+r10+rax*8]     #60.9 
        vmovsd    xmm12, QWORD PTR [65536+rcx+r9]               #60.26
        vmovhpd   xmm10, xmm14, QWORD PTR [61440+rcx+r9]        #60.26
        vmovhpd   xmm14, xmm12, QWORD PTR [69632+rcx+r9]        #60.26
        vmovsd    xmm12, QWORD PTR [81920+rcx+r9]               #60.26
        vinsertf128 ymm11, ymm15, xmm10, 1                      #60.26
        vmovhpd   xmm10, xmm13, QWORD PTR [77824+rcx+r9]        #60.26
        vmovsd    xmm13, QWORD PTR [90112+rcx+r9]               #60.26
        vmovhpd   xmm15, xmm12, QWORD PTR [86016+rcx+r9]        #60.26
        vfmadd231pd ymm3, ymm11, YMMWORD PTR [96+r10+rax*8]     #60.9 
        vmovsd    xmm12, QWORD PTR [98304+rcx+r9]               #60.26
        vinsertf128 ymm11, ymm14, xmm10, 1                      #60.26
        vmovhpd   xmm10, xmm13, QWORD PTR [94208+rcx+r9]        #60.26
        vmovsd    xmm13, QWORD PTR [106496+rcx+r9]              #60.26
        vmovhpd   xmm14, xmm12, QWORD PTR [102400+rcx+r9]       #60.26
        vfmadd231pd ymm2, ymm11, YMMWORD PTR [128+r10+rax*8]    #60.9 
        vmovsd    xmm12, QWORD PTR [114688+rcx+r9]              #60.26
        vinsertf128 ymm11, ymm15, xmm10, 1                      #60.26
        vmovhpd   xmm10, xmm13, QWORD PTR [110592+rcx+r9]       #60.26
        vmovsd    xmm13, QWORD PTR [122880+rcx+r9]              #60.26
        vmovhpd   xmm15, xmm12, QWORD PTR [118784+rcx+r9]       #60.26
        vfmadd231pd ymm1, ymm11, YMMWORD PTR [160+r10+rax*8]    #60.9 
        vinsertf128 ymm11, ymm14, xmm10, 1                      #60.26
        vmovhpd   xmm10, xmm13, QWORD PTR [126976+rcx+r9]       #60.26
        add       rcx, 131072                                   #59.7 
        vfmadd231pd ymm0, ymm11, YMMWORD PTR [192+r10+rax*8]    #60.9 
        vinsertf128 ymm11, ymm15, xmm10, 1                      #60.26
        vfmadd231pd ymm6, ymm11, YMMWORD PTR [224+r10+rax*8]    #60.9 
        add       rax, 32                                       #59.7 
        cmp       rax, rdx                                      #59.7 
        jb        ..B7.10       # Prob 99%                      #59.7 

どうやら4Byteデータを8個持ってくる場合にはvgather命令が積極的に使われるけど、8Byteデータを4個持ってくる場合には使われないみたいだ。

ストライド幅が一定ではない場合

行列行列積の場合だとストライド幅一定のアクセスになっているので、一定でない場合にもvgatherが見られるかどうかを検証してみた。ひとまず、次のようなコードを書いてvgather命令がみられるかどうか見る。

double sum = 0.0;
for (int i = 0; i < num; i++) {
  const auto v = val[idx[i]];
  sum += v;
}

飛び飛びでアクセスし値を読み込み、読み込んだ値をすべて足しこむ。
idxは実行時に定まる変数で、コンパイルタイムには定まらない変数だとする。
この時も同じように4Byteデータの場合にはvgatherが使われるが、8Byteデータの場合には使われない。

int32_tの場合

..B3.13:                        # Preds ..B3.13 ..B3.12                                                                                                       
        vmovdqu   ymm2, YMMWORD PTR [rdi+rax*4]                 #18.24                                                                                        
        vpxor     ymm4, ymm4, ymm4                              #18.20                                                                                        
        vpxor     ymm7, ymm7, ymm7                              #18.20                                                                                        
        vmovdqa   ymm3, ymm0                                    #18.20                                                                                        
        vpgatherdd ymm4, DWORD PTR [rcx+ymm2*4], ymm3           #18.20                                                                                        
        vpaddd    ymm6, ymm1, ymm4                              #19.5                                                                                         
        vmovdqu   ymm1, YMMWORD PTR [32+rdi+rax*4]              #18.24                                                                                        
        vmovdqa   ymm5, ymm0                                    #18.20                                                                                        
        add       rax, 16                                       #17.3                                                                                         
        vpgatherdd ymm7, DWORD PTR [rcx+ymm1*4], ymm5           #18.20                                                                                        
        vpaddd    ymm1, ymm6, ymm7                              #19.5                                                                                         
        cmp       rax, rsi                                      #17.3                                                                                         
        jb        ..B3.13       # Prob 82%                      #17.3

int64_tの場合

..B3.4:                         # Preds ..B3.4 ..B3.3                                                                                                         
        movsxd    r8, DWORD PTR [rdi+rax*4]                     #18.20                                                                                        
        movsxd    r10, DWORD PTR [8+rdi+rax*4]                  #18.20                                                                                        
        movsxd    r9, DWORD PTR [4+rdi+rax*4]                   #18.20                                                                                        
        movsxd    r11, DWORD PTR [12+rdi+rax*4]                 #18.20                                                                                        
        vmovq     xmm2, QWORD PTR [rsi+r8*8]                    #18.20                                                                                        
        vmovq     xmm3, QWORD PTR [rsi+r10*8]                   #18.20                                                                                        
        movsxd    r8, DWORD PTR [16+rdi+rax*4]                  #18.20                                                                                        
        movsxd    r10, DWORD PTR [24+rdi+rax*4]                 #18.20                                                                                        
        vpinsrq   xmm6, xmm2, QWORD PTR [rsi+r9*8], 1           #18.20                                                                                        
        vpinsrq   xmm7, xmm3, QWORD PTR [rsi+r11*8], 1          #18.20                                                                                        
        vmovq     xmm4, QWORD PTR [rsi+r8*8]                    #18.20                                                                                        
        vmovq     xmm5, QWORD PTR [rsi+r10*8]                   #18.20                                                                                        
        movsxd    r9, DWORD PTR [20+rdi+rax*4]                  #18.20                                                                                        
        movsxd    r11, DWORD PTR [28+rdi+rax*4]                 #18.20                                                                                        
        add       rax, 8                                        #17.3                                                                                         
        vpinsrq   xmm9, xmm4, QWORD PTR [rsi+r9*8], 1           #18.20                                                                                        
        vpinsrq   xmm10, xmm5, QWORD PTR [rsi+r11*8], 1         #18.20                                                                                        
        vinserti128 ymm8, ymm6, xmm7, 1                         #18.20                                                                                        
        vinserti128 ymm11, ymm9, xmm10, 1                       #18.20                                                                                        
        vpaddq    ymm1, ymm1, ymm8                              #19.5                                                                                         
        vpaddq    ymm0, ymm0, ymm11                             #19.5                                                                                         
        cmp       rax, rdx                                      #17.3                                                                                         
        jb        ..B3.4        # Prob 82%                      #17.3

floatの場合

..B3.13:                        # Preds ..B3.13 ..B3.12                                                                                                       
        vmovups   ymm3, YMMWORD PTR [rdi+rax*4]                 #18.24                                                                                        
        vmovups   ymm5, YMMWORD PTR [32+rdi+rax*4]              #18.24                                                                                        
        vxorps    ymm7, ymm7, ymm7                              #18.20                                                                                        
        add       rax, 16                                       #17.3                                                                                         
        vmovdqa   ymm4, ymm0                                    #18.20                                                                                        
        cmp       rax, rdx                                      #17.3                                                                                         
        vxorps    ymm8, ymm8, ymm8                              #18.20                                                                                        
        vmovdqa   ymm6, ymm0                                    #18.20                                                                                        
        vgatherdps ymm7, DWORD PTR [rsi+ymm3*4], ymm4           #18.20                                                                                        
        vgatherdps ymm8, DWORD PTR [rsi+ymm5*4], ymm6           #18.20                                                                                        
        vaddps    ymm2, ymm2, ymm7                              #19.5                                                                                         
        vaddps    ymm1, ymm1, ymm8                              #19.5                                                                                         
        jb        ..B3.13       # Prob 82%                      #17.3

doubleの場合

..B3.4:                         # Preds ..B3.4 ..B3.3                                                                                                         
        movsxd    r9, DWORD PTR [rdi+rdx*4]                     #18.20                                                                                        
        movsxd    r10, DWORD PTR [4+rdi+rdx*4]                  #18.20                                                                                        
        movsxd    r11, DWORD PTR [8+rdi+rdx*4]                  #18.20                                                                                        
        vmovsd    xmm2, QWORD PTR [rsi+r9*8]                    #18.20                                                                                        
        movsxd    r9, DWORD PTR [12+rdi+rdx*4]                  #18.20                                                                                        
        vmovhpd   xmm4, xmm2, QWORD PTR [rsi+r10*8]             #18.20                                                                                        
        movsxd    r10, DWORD PTR [16+rdi+rdx*4]                 #18.20                                                                                        
        vmovsd    xmm3, QWORD PTR [rsi+r11*8]                   #18.20                                                                                        
        movsxd    r11, DWORD PTR [20+rdi+rdx*4]                 #18.20                                                                                        
        vmovhpd   xmm5, xmm3, QWORD PTR [rsi+r9*8]              #18.20                                                                                        
        movsxd    r9, DWORD PTR [24+rdi+rdx*4]                  #18.20                                                                                        
        vmovsd    xmm6, QWORD PTR [rsi+r10*8]                   #18.20                                                                                        
        movsxd    r10, DWORD PTR [28+rdi+rdx*4]                 #18.20                                                                                        
        vmovhpd   xmm8, xmm6, QWORD PTR [rsi+r11*8]             #18.20                                                                                        
        movsxd    r11, DWORD PTR [32+rdi+rdx*4]                 #18.20                                                                                        
        vmovsd    xmm7, QWORD PTR [rsi+r9*8]                    #18.20                                                                                        
        movsxd    r9, DWORD PTR [36+rdi+rdx*4]                  #18.20                                                                                        
        vmovhpd   xmm9, xmm7, QWORD PTR [rsi+r10*8]             #18.20                                                                                        
        movsxd    r10, DWORD PTR [40+rdi+rdx*4]                 #18.20                                                                                        
        vinsertf128 ymm10, ymm4, xmm5, 1                        #18.20                                                                                        
        vaddpd    ymm2, ymm1, ymm10                             #19.5                                                                                         
        vmovsd    xmm1, QWORD PTR [rsi+r11*8]                   #18.20                                                                                        
        vmovhpd   xmm12, xmm1, QWORD PTR [rsi+r9*8]             #18.20                                                                                        
        movsxd    r11, DWORD PTR [44+rdi+rdx*4]                 #18.20                                                                                        
        movsxd    r9, DWORD PTR [48+rdi+rdx*4]                  #18.20                                                                                        
        vinsertf128 ymm11, ymm8, xmm9, 1                        #18.20                                                                                        
        vaddpd    ymm3, ymm0, ymm11                             #19.5                                                                                         
        vmovsd    xmm0, QWORD PTR [rsi+r10*8]                   #18.20                                                                                        
        vmovhpd   xmm13, xmm0, QWORD PTR [rsi+r11*8]            #18.20                                                                                        
        movsxd    r11, DWORD PTR [56+rdi+rdx*4]                 #18.20                                                                                        
        movsxd    r10, DWORD PTR [52+rdi+rdx*4]                 #18.20                                                                                        
        vmovsd    xmm14, QWORD PTR [rsi+r9*8]                   #18.20                                                                                        
        movsxd    r9, DWORD PTR [60+rdi+rdx*4]                  #18.20                                                                                        
        add       rdx, 16                                       #17.3                                                                                         
        vmovsd    xmm15, QWORD PTR [rsi+r11*8]                  #18.20                                                                                        
        vmovhpd   xmm1, xmm14, QWORD PTR [rsi+r10*8]            #18.20                                                                                        
        vmovhpd   xmm14, xmm15, QWORD PTR [rsi+r9*8]            #18.20                                                                                        
        vinsertf128 ymm0, ymm12, xmm13, 1                       #18.20                                                                                        
        vinsertf128 ymm12, ymm1, xmm14, 1                       #18.20                                                                                        
        vaddpd    ymm1, ymm0, ymm2                              #19.5                                                                                         
        vaddpd    ymm0, ymm12, ymm3                             #19.5                                                                                         
        cmp       rdx, rcx                                      #17.3
        jb        ..B3.4        # Prob 82%                      #17.3

命令としてvgatherqpdなどがあるけれども、int64_tやdoubleの場合にはどうやら使われないみたいだ。

まとめ

自動ベクトル化の場合、8要素の場合にはかなり積極的にvgather命令を使ったベクトル化をやろうと試みるが、4要素の場合には別のやり方を検討する模様。4要素のvgatherによるロードを使う場合は性能を出せないことが多いということなのか?

追記

調べていたらVGATHER系命令の速さあるいは遅さという記事を見つけた。intelの最適化マニュアルにvgather命令を使うべきときとそうでないときが書いてあるみたいだ。それによると使うべきときは

  1. 4要素以上で固定でないマスク – 固定でないマスクを普通のロードで行おうとすると、分岐予測が失敗することによる性能低下がある
  2. 8要素でベクタインデックス(SIMD演算した結果がそのままインデックスになる) – そもそもこれこそがVGATHERの目的とするところである

とあるらしい。見事に2のケースに当てはまる場合のみ自動ベクトル化されており、4要素の2のケースに当てはまらない場合には自動ベクトル化されていない。なるほど。