Intel AVX命令を用いた並列FFTの実現と評価 高橋大介 筑波大学システム情報系 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 発表手順 背景 目的 Six-Step FFTアルゴリズム In-Cache FFTアルゴリズム Intel AVX命令 FFTカーネルのベクトル化 性能評価 まとめ 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 背景（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 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 背景（2/2） Short Vector SIMD命令を搭載したプロセッサでFFTを計算する際には，以下の2点が性能を引き出す上で大きな鍵となる． Short Vector SIMD命令を有効に活用する． かつキャッシュミスの回数を減らす． これまでに，Short Vector SIMD命令を用いたFFTの実装がいくつか行われているが，これらのFFTは，データがキャッシュに収まるような場合を想定しているものが多い． キャッシュに収まりきらないような大規模なデータを扱う場合には必ずしも性能が発揮できていない． 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 関連研究 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 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 目的 AVX命令を用いてFFTカーネル部分の性能を向上させる． ブロックSix-Step FFTアルゴリズム[Takahashi01]を用いることで，データがキャッシュに収まらない場合にも高い性能を維持する． AVX命令を搭載したマルチコアプロセッサ上でブロックSix-Step FFTに基づいた並列FFTを実現し，性能評価を行う． 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 離散Fourier変換（DFT） 離散Fourier変換の定義 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 2次元表現 もし， が と に分解できるとすると， 上記の式を用いると，DFTの定義式は以下のように書き換えることができる． 点FFTが 点FFTと 点FFTに分解できることを示している． 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 2012/3/17

「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 Six-Step FFTアルゴリズム 2次元表現を用いて，以下のようなSix-Step FFTアルゴリズム[Bailey90, VanLoan92]が導かれる． Step 1: 行列の転置 Step 2: 組の 点multicolumn FFT Step 3: ひねり係数（ ）の乗算 Step 4: 行列の転置 Step 5: 組の 点multicolumn FFT Step 6: 行列の転置 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

ブロックSix-Step FFTアルゴリズム オリジナルのSix-Step FFTアルゴリズム[VanLoan92] multicolumn FFTと行列の転置が分離されている． 行列の転置は，キャッシュブロッキングを行うことでキャッシュミスを削減することができる． さらに，multicolumn FFTと行列の転置を統合することで，キャッシュに載っているデータを再利用することができる． この手法はブロックSix-Step FFTアルゴリズムと呼ばれている[Takahashi01]． 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

ブロックSix-Step FFTに基づく 並列1次元FFTアルゴリズム 部分的な 行列の転置 最外側ループを複数のプロセッサに分配 部分的な 行列の転置 行列の転置 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 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 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 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 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

ベクトル化可能な基数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 DO I=1,M C0=A(I,J,1) C1=A(I,J,2) B(I,1,J)=C0+C1 B(I,2,J)=W(J)*(C0-C1) END DO RETURN END ディレクティブ“!DIR$ VECTOR ALIGNED”は，ループ内のメモリ参照が既に最適化（AVXの場合，32バイト境界にalign）されていることをコンパイラに伝える． 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

ベクトル化された基数2のFFT カーネルのアセンブリコード（抜粋） vmovupd (%edx,%ecx), %ymm3 vmovupd (%edx,%ebx), %ymm4 vsubpd %ymm4, %ymm3, %ymm5 vaddpd %ymm4, %ymm3, %ymm2 vmulpd %ymm5, %ymm1, %ymm7 vmovupd %ymm2, (%edx,%edi) vshufpd $5, %ymm5, %ymm5, %ymm6 vmulpd %ymm6, %ymm0, %ymm2 vmovupd 32(%edx,%ecx), %ymm5 vmovupd 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) 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 性能評価 実現した並列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 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 考察 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 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会

「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会 まとめ AVX命令を用いた並列FFTの実現および評価を行った． FFTカーネルをAVX命令を用いてベクトル化すると共に，キャッシュメモリを効果的に利用できるブロックSix-Step FFTをOpenMPを用いて並列化した． その結果，FFTWに比べて，特にデータがキャッシュに収まらないような場合に対して性能が改善されることを示した． 同様の手法は，多次元FFTにおいても有効であると考えられる． 2012/3/17 「コンピューティクスによる物質デザイン：複合相関と非平衡ダイナミクス」研究会