Intel AVX命令を用いた並列FFTの実現と評価高橋大介筑波大学システム情報系 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 1 発表手順 • • • • • • • • 背景目的 Six-Step FFTアルゴリズム In-Cache FFTアルゴリズム Intel AVX命令 FFTカーネルのベクトル化性能評価まとめ 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 2 背景（1/2） • 高速Fourier変換（FFT）は，科学技術計算において今日広く用いられているアルゴリズム． • 浮動小数点演算をより高速に処理するために，最近のプロセッサではShort Vector SIMD命令を搭載しているものが多い． – Intel: SSE, SSE2, SSE3, SSSE3, SSE4およびAVX – Motorola: AltiVec – Fujitsu: SPARC64 ViiifxにおけるHPC-ACE • しかし，これらのShort Vector SIMD命令を用いたとしても，最近のプロセッサのデータ供給能力はキャッシュに頼っているのが現状． 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 3 背景（2/2） • Short Vector SIMD命令を搭載したプロセッサで FFTを計算する際には，以下の2点が性能を引き出す上で大きな鍵となる． – Short Vector SIMD命令を有効に活用する． – かつキャッシュミスの回数を減らす． • これまでに，Short Vector SIMD命令を用いたFFT の実装がいくつか行われているが，これらのFFTは，データがキャッシュに収まるような場合を想定しているものが多い． • キャッシュに収まりきらないような大規模なデータを扱う場合には必ずしも性能が発揮できていない． 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 4 関連研究 • FFTW 3.3 [Frigo and Johnson] – AVX命令をサポートしている（version 3.3より）． – 自動チューニングの手法をFFTに適用． – FFTを再帰的に二分木状に分割することにより，最終的に小さな点数のDFTに帰着している． – http://www.fftw.org/ • SPIRAL [Pueschel et al.] – AVX命令をサポートしている． – 自動チューニングによりFFTプログラムを自動生成する． – http://www.spiral.net/ 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 5 目的 • AVX命令を用いてFFTカーネル部分の性能を向上させる． • ブロックSix-Step FFTアルゴリズム [Takahashi01]を用いることで，データがキャッシュに収まらない場合にも高い性能を維持する． • AVX命令を搭載したマルチコアプロセッサ上でブロックSix-Step FFTに基づいた並列FFT を実現し，性能評価を行う． 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 6 離散Fourier変換（DFT） • 離散Fourier変換の定義 n 1 y ( k )   x ( j ) j 0 jk n 0  k  n  1,  n  exp( 2i / n ) 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 7 • 2次元表現もし，n が n1 と n2に分解できるとすると， j  j1  j 2 n1 j1  0 , 1,  , n1  1 j 2  0 , 1,  , n 2  1 k  k 2  k1 n 2 k1  0 , 1,  , n1  1 k 2  0 , 1,  , n 2  1 • 上記の式を用いると，DFTの定義式は以下のように書き換えることができる．  n2 1  j1k1 j2 k 2 j1 k 2 y ( k 2 , k1 )     x ( j1 , j 2 ) n2  n1n2   n1 j1  0  j 2  0  • n 点FFTが n1点FFTと n2点FFTに分解できるこ n1 1 とを示している． 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 8 Six-Step FFTアルゴリズム • 2次元表現を用いて，以下のようなSix-Step FFTアルゴリズム[Bailey90, VanLoan92]が導かれる． • Step 1: 行列の転置 • Step 2: n1組の n2 点multicolumn FFT j1k 2 • Step 3: ひねり係数（ n n ）の乗算 1 2 • Step 4: 行列の転置 • Step 5: n2組の n1 点multicolumn FFT • Step 6: 行列の転置 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 9 ブロックSix-Step FFTアルゴリズム • オリジナルのSix-Step FFTアルゴリズム [VanLoan92] multicolumn FFTと行列の転置が分離されている． • 行列の転置は，キャッシュブロッキングを行うことでキャッシュミスを削減することができる． • さらに，multicolumn FFTと行列の転置を統合することで，キャッシュに載っているデータを再利用することができる． • この手法はブロックSix-Step FFTアルゴリズムと呼ばれている[Takahashi01]． 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 10 ブロックSix-Step FFTに基づく並列1次元FFTアルゴリズム n 2 部分的な行列の転置 nB nB nB nB 最外側ループを複数のプロセッサに分配 n2 n1 P0 P1 P2 P3 nB nB nB nB n1 行列の転置 n2 P0 P1 P2 P3 2012/3/17 部分的な行列の転置 n1 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 11 In-Cache FFTアルゴリズム • 問題サイズがキャッシュに収まっている場合には， Stockham autosort FFTアルゴリズムを用い，問題サイズがキャッシュサイズを超えた場合にブロック Six-Step FFTアルゴリズムを用いる． • Byte/Flop値の観点からは，基数8のFFTが基数2， 4のFFTよりも有利になる． • 高い基数のFFTでは中間結果を保持するために多くの浮動小数点レジスタを必要とする． • Sandy Bridgeプロセッサでは16個の256ビットレジスタを搭載しているので，基数8のFFTが最も高速． 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 12 Intel AVX命令 • Intel Advanced Vector Extensions（AVX）とは， Sandy Bridgeプロセッサから導入された，SSE系命令の流れを汲むSIMD命令． – 256ビット長のデータに対して，SIMD処理を行うことができる． • AVX命令を用いるためには，アセンブラで直接記述する方法もあるが，コーディングが複雑になる． • Intel C/C++およびFortranコンパイラの最新版（ver. 12.1）ではAVX命令を用いた自動ベクトル化を行うことができる． – 複素数演算も自動ベクトル化が可能． 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 13 ベクトル化可能な基数2の FFTカーネルの例 SUBROUTINE FFT2(A,B,W,M,L) COMPLEX*16 A(M,L,*),B(M,2,*),W(*) COMPLEX*16 C0,C1 DO J=1,L !DIR$ VECTOR ALIGNED ディレクティブ“!DIR$ VECTOR DO I=1,M ALIGNED”は，ループ内のメモ C0=A(I,J,1) リ参照が既に最適化（AVXの場 C1=A(I,J,2) 合，32バイト境界にalign）され B(I,1,J)=C0+C1 ていることをコンパイラに伝える． B(I,2,J)=W(J)*(C0-C1) END DO END DO RETURN END 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 14 ベクトル化された基数2のFFT カーネルのアセンブリコード（抜粋） vmovupd vmovupd vsubpd vaddpd vmulpd vmovupd vshufpd vmulpd vmovupd vmovupd 2012/3/17 (%edx,%ecx), %ymm3 (%edx,%ebx), %ymm4 %ymm4, %ymm3, %ymm5 %ymm4, %ymm3, %ymm2 %ymm5, %ymm1, %ymm7 %ymm2, (%edx,%edi) $5, %ymm5, %ymm5, %ymm6 %ymm6, %ymm0, %ymm2 32(%edx,%ecx), %ymm5 32(%edx,%ebx), %ymm6 vaddsubpd %ymm2, %ymm7, %ymm3 vsubpd %ymm6, %ymm5, %ymm7 vaddpd %ymm6, %ymm5, %ymm4 vmovupd %ymm3, (%edx,%eax) vmulpd %ymm7, %ymm1, %ymm2 vmovupd %ymm4, 32(%edx,%edi) vshufpd $5, %ymm7, %ymm7, %ymm7 vmulpd %ymm7, %ymm0, %ymm3 vaddsubpd %ymm3, %ymm2, %ymm4 vmovupd %ymm4, 32(%edx,%eax) 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 15 性能評価 • 実現した並列1次元FFTの性能評価にあたっては，以下のFFTライブラリの性能を比較した． – 実現した並列1次元FFT（FFTE 5.0，AVX命令および OpenMPを使用） – FFTW 3.3（AVX命令およびOpenMPを使用） • 評価環境 – Intel Xeon E3-1230 PC（Sandy Bridge 3.2 GHz, 8 MB L3 cache, 1 CPU, 4コア, 4 GB DDR3-SDRAM） – Intel Core i5-2520M PC（Sandy Bridge 2.5 GHz, 3 MB L3 cache, 1 CPU, 2コア, 4 GB DDR3-SDRAM） – Intel CおよびFortranコンパイラ（ver. 12.1）を使用． • コンパイルオプション：”-O3 –xHOST –openmp” 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 16 M 16 8M 4M 2M 1M 2K 51 6K 25 8K 12 64 K GFlops Intel Xeon E3-1230 （Sandy Bridge 3.2 GHz）における1次元FFTの性能 40 FFTE 5.0 35 (1 core) FFTE 5.0 30 (2 cores) 25 FFTE 5.0 20 (4 cores) 15 FFTW 3.3 (1 core) 10 FFTW 3.3 5 (2 cores) 0 FFTW 3.3 (4 cores) Length of Transform 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 17 GFlops Intel Core i5-2520M （Sandy Bridge 2.5 GHz）における1次元FFTの性能 14 FFTE 5.0 12 (1 core) FFTE 5.0 10 (2 cores) 8 FFTW 3.3 6 (1 core) FFTW 3.3 4 (2 cores) M 16 8M 4M 2M 1M 2K 51 6K 25 8K 12 64 K 2 0 Length of Transform 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 18 考察 • Intel Xeon E3-1230（1 CPU，4コア）では，FFTEは以下のケースを除いてFFTWよりも高速． – n <= 256K，n = 8M（1 CPU，1コア） – n <= 256K（1 CPU，2コア） – n <= 512K，n = 16M（1 CPU，4コア） • Intel Core i5-2520M（1 CPU，2コア）では，FFTEは n <= 256Kを除いてFFTWよりも高速． • FFTWでは，自動チューニングの手法を用いて高速化を図っており，データがキャッシュに収まるような場合については高い性能を発揮できていると考えられる． • FFTEではキャッシュブロッキングを行っており，全てのデータがキャッシュに収まりきれない場合についても，ある程度高い性能が維持できている． 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 19 まとめ • AVX命令を用いた並列FFTの実現および評価を行った． • FFTカーネルをAVX命令を用いてベクトル化すると共に，キャッシュメモリを効果的に利用できるブロックSix-Step FFTをOpenMPを用いて並列化した． • その結果，FFTWに比べて，特にデータがキャッシュに収まらないような場合に対して性能が改善されることを示した． • 同様の手法は，多次元FFTにおいても有効であると考えられる． 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 20