Research Highlights:
最小通信量を持つ多次元FFTの並列化手法

第一原理電子状態計算の効率的な実装において、高速フーリエ変換 (FFT) は重要な役割を果たしています。 とりわけ平面波基底に基づく実装ではFFTが計算の律速となり、効率的なFFTライブラリの開発が必要です。 現在では数十万コアから構成される超並列計算機が台頭しており、 広くFFTを用いたアプリケーションの適用限界を拡張するために、新しい並列化手法の開発が望まれます。

FFT3D-Row-Wise
図1: 三次元FFTに対するRow-Wise型の領域分割

我々は高次元FFTの超並列化を実現するために、MPIなどを用いた分散メモリ型の並列化において通信量を削減する 新しい領域分割法の開発に取り組みました [1]。その結果、Row-Wise型の領域分割法 (図1) を導入することで、 プロセス間の通信量が削減できることを見出しました。 この領域分割法では多次元のFFTグリッドはRow-Wise型のマッピングによって一次元化された後、計算量が均等化されるように 各プロセスに分割されます。 このマッピングの方法は一意ではなく、M次元のFFTにおいて、(M-1)!M通りの分割方法が考えられます。 我々は3、4、5次元のFFTにおいて全ての場合の通信量を詳細に調べ、 それぞれ4、4、96通りの等価な最小通信量を持つマッピング方法を見出しました。 さらに3次元FFTの場合に、これまでに提案された1、1.5、2、3次元領域分割法の通信量と比較した所、 任意の並列数において本手法が最小の通信量を持っていることが明らかとなりました。 通信量が削減される理由はデータの再利用にあります。 多次元のFFTでは各次元毎に一次元FFTを行い、次の次元での一次元FFTを実施するために、 データ分割を転置させます。この転置の際に通信が必要となりますが、各プロセスの持つデータが転置の前後で重なりが大きければ、 データを再利用することで、通信量が削減出来ます。 今回、見出したマッピング方法は転置の前後でデータの重なりが最大となっており、 その結果、通信量が最小化されています。

FFT3D-Benchmark
図2: 三次元FFTに対するベンチマーク計算(データ点数は128×128×128)

我々は本手法を実装し、OpenFFTと名付けたライブラリパッケージを開発し、GNU-GPLの規約の下で一般公開しました [2]。 OpenFFTはCもしくはFortranから利用可能であり、1次元のFFTを実行するためにFFTW3 [3] を使用しています。 北陸先端大のCray-XC30を使用し、経過時間に基づきGFLOP値を見積もり、性能評価を実施しました。 他の並列FFTパッケージ (2次元領域分割に基づく2DECOMP、並列化版FFTW3、MKL Cluster FFT) との比較結果を図2に示します。 OpenFFTは他のパッケージと比較しても、高い並列数まで良くスケールしていることが分かります。 第一原理電子状態計算への適用だけでなく、広く応用展開がなされることが期待されます。 一方で、我々が提案するRow-Wise型のマッピングによる領域分割法は、 通信グループを局所化できないという欠点を持っていることも明らかとなっています。 このため、OpenFFTは数千並列までスケールと考えられますが、数万コアを用いた並列計算ではスケーリングが低下すると推定されます。 Row-Wise型のマッピング方法において通信グループの局所化を実現する方法の開発が今後の課題です。 また本並列化手法は大規模電子状態計算コードOpenMX [4] にも組み込まれています。

  1. "A decomposition method with minimum communication amount for parallelization of multi-dimensional FFTs", T.V.T. Duy and T. Ozaki, Comput. Phys. Commun. 185, 153-164 (2014).
  2. OpenFFT, T.V.T. Duy and T. Ozaki.
  3. FFTW3, M. Frigo and S.G. Johnson.
  4. OpenMX