高速フーリエ変換(FFT)は現在様々なアプリケーションで用いられている最も重要な計算の一つである。FFTの高速化は直接これらの多くのアプリケーションの実行時間短縮に繋がるため大きな意義がある。現在様々なCPUアーキテクチャが乱立しているが、各アーキテクチャに対応した多くの高速化手法などが提案されており、また高度に最適化されたFFTライブラリも多く提供されている。

FFTの計算はメモリアクセスの比重が高く、その高速化には高いメモリバンド幅を持つ非常に高価な計算機システムが必要になる。そこで近年注目されているのがGPUによる汎用計算(GPGPU)である。多数のコアを搭載することによる高い浮動小数演算性能と多数のメモリコントローラによる高いメモリバンド幅によって多くのアプリケーションがGPUにより高速化を実現している。特に高いメモリバンド幅はFFTの計算に有効である。

しかしながらGPUによりFFTの計算を高速化することは容易ではない。CPUとGPUのアーキテクチャの違いが大きく、またGPUではプログラミングの制約も多いため、既存のCPU用の手法ではGPUの性能を引き出すことができない。CPUとは異なり多数のプロセッサコアを搭載するGPUの場合、従来のマルチスレッド型手法ではGPUの計算資源をほとんど活用することができないために性能が低い。GPUメモリは高いバンド幅を持つが、連続アクセスや局所性の高いメモリアクセスパターンに最適化されているため、従来の多次元FFTアルゴリズムにおける転置処理のメモリアクセス効率が著しく低い。またFFTの計算は入力サイズに大きく依存するため、それぞれの入力サイズに対してコードのチューニングを行うことは非現実的である。GPUアーキテクチャは2のべき乗サイズのFFT計算の効率がよいが、それ以外では計算資源の無駄が生じる。FFT計算を複数GPUで行うこともある。この場合、クラスタ上での並列FFT計算と同様にGPUメモリ間での全対全通信が必要となり、特にGPU内での計算がGPUにより高速化されているため全対全通信が占める時間の割合が8割以上と非常に大きい。

本論文では、このようなGPUを利用したFFT計算に関わる課題に対して以下のような手法を提案し、高い性能を実現した。(1) GPUの多数のコアやshared memoryを介したスレッド間データ交換やハードウェアによる同期などの機能を活用する細粒度並列なFFTアルゴリズムを提案した。(2) GPUで効率よく計算するため、転置の代わりにブロック化したmulti-row FFTを拡張したカーネルを用いる多次元FFTアルゴリズムを提案した。(3) 任意の入力サイズに対応するため、入力サイズの因数分解方法、スレッド数、shared memoryで生じるバンクコンフリクトを回避するためのパディングの自動挿入などのパラメータについて網羅的探索により最適なものを決定する自動チューニング手法を提案し、多くの入力サイズにおいてCUFFTライブラリの何倍もの性能を達成した。(4) 2のべき乗以外のサイズに対しても、GPUの計算資源を無駄なく利用することができるWarp単位のスケジューリング手法を提案した。(5) 複数GPUを搭載するシステムにおいて、P2P機能を活用したスケジューリングの最適化手法を提案し、複数GPUを利用した高速化を実現した。(6) 複数ノードのシステムにおいてもGPU間の全対全通信性能の向上及び安定化のため、低レベルのIBverbs APIを利用して小さいメッセージの送受信時のオーバヘッド削減、複数のRDMA通信の同時実行によるネットワーク競合時のペナルティ軽減、複数のInfiniBandレールへの動的なRDMA転送割り当てによりネットワーク競合を最小化、などの最適化手法を提案し、その結果ノード数が多い場合にも高い性能を確保し、最大256ノード(768GPU)で4.8TFLOPSの性能を達成した。

以上のように、高速フーリエ変換の計算をGPUによって高速化するために必要な様々なアルゴリズムを提案した。様々な入力サイズや、様々な世代のGPU、シングルGPU構成だけでなくGPUメモリから溢れるデータサイズ、単一ノードの複数GPUを使う場合、大規模なGPUクラスタまであらゆる環境に対応可能であることを示した。

高速フーリエ変換(FFT)は,コンピュータ科学・計算科学なかでも特異な重要性を持つアルゴリズムである.離散フーリエ変換としての自然な定義では入力サイズ N に対して O(N^2) の計算量がかかる計算を,FFT は O(N log N) の計算量で実現する.この圧倒的な性能向上のため,数値計算や信号処理のみならず,多数のコンピュータ科学のアルゴリズムの基礎となっている.FFT が高速化されれば,多くのアプリケーションが多大な恩恵を受ける.

本論文では,近年高性能計算アーキテクチャとして非常に高い注目を集めている GPU (グラフィックプロセッシングユニット)を用いた FFT の高性能実装技術について論じている.GPU はもともとグラフィックス用の付加プロセッサとして設計されていたが,近年はグラフィックス以外の汎用計算にも使えるようにアーキテクチャおよびプログラミングモデルが改善されている.GPU は多数の演算コアを持ち,さらに各演算コアは大規模な SIMD 型の並列処理を行う.このため GPU は,大規模 FFT のような大規模並列性を持つ計算において CPU をはるかに上回る性能を達成する.

しかし,GPU において実際に高い性能を実現するために必要なのは,並列性だけではない.GPU の演算能力は非常に高いが,FFT は入力サイズ N に対して計算量が O(N log N) しかないため,メモリと演算器の間のデータ転送が所要時間の主要な要因となる.従って,メモリアクセスを最適化することが高性能実装の本質になる.また,複数 GPU を用いる場合は GPU 間でのデータ転送,GPU を複数搭載する GPU クラスタを用いる場合にはノード間のデータ転送が性能を決める重要要因となる.

本論文では,単一 GPU,複数 GPU,GPU クラスタのそれぞれの場合に対して有効な新規手法を開発しており,それぞれ世界最高水準の FFT を実現している.本論文は以下の 8 つの章から成る.

第1章は導入部であり,課題の表明,本研究の貢献を概論している.

第2章は背景説明であり,FFT および GPU についての基本的知識を説明している.

第3章は単一 GPU のための 3 次元高速 FFT のアルゴリズムとして,Bandwidth Intensive 3-D FFT を提案,評価している.通常,メモリアクセスの最適化のためにはブロック化が行われるが,FFT をブロック化した six-step FFT には 3 回の行列転置演算が必要である.しかし GPU には連続したスレッドが連続したアドレスにアクセスするコアレッシングと呼ばれる条件が成り立たないデータアクセスは格段に遅くなってしまうという性質がある.しかし行列転置はこのような GPU の性質に向かず,行列転置のために FFT は遅くなってしまう.これに対し本論文では,あえてブロック化によるメモリアクセス最適化を用いず,コアレッシングを優先するアルゴリズムを提案している.これによりベンダー提供の CUFFT3D の 3 倍以上という性能を達成した.

第4章では,単一 GPU のための FFT ライブラリの自動チューニングによる最適化が述べられている.基底とその順序の選択,スレッドブロック数の選択,シェアードメモリのパディングについて網羅的検査によるオフライン自動チューニングを行い,2, 3, 5 のべきを含む FFT に対して常に高性能を達成する.

第5章では,単一 GPU の FFT のためのワープレベル最適化について述べている.GPU は SIMD 型計算機であるが,多数の基底を含む FFT では必要とするスレッド数が異なる.実行のためには必要数の最大値にあわせてスレッドを準備する必要があるが,一部の基底では不要なスレッドが発生するため,それによるオーバーヘッドを削減する手法を論じている.

第6章では,複数 GPU による FFT のためのデータ交換の最適化が論じられている.CPU と GPU は PCI Express により接続されているが,単一ノードに実装された複数 GPU を用いて FFT を行う場合,GPU 間でのデータ通信がオーバーヘッドとなる.本研究では,GPU 間直接通信,および PCI Express レーンの衝突を避けるスケジューリングにより,高い実効性能を実現する手法を提案している.

第7章では,GPU クラスタを用いた FFT のためのデータ交換の最適化手法が論じられている.本研究で用いたプラットフォームは GPU スーパーコンピュータである TSUBAME 2.0 である.TSUBAME 2.0 はノード間を 2 組の QDR x4 インフィニバンドで接続している.本論文では,ノード間データ転送と CPU-GPU 間データ転送を最適なチャンクサイズでパイプライン化するのみならず,2 組のレールの使用方法をオンラインで最適化することにより,高いスケーラビリティを達成している.

第8章は本論文の貢献と議論とをまとめている.

以上のように,本論文は GPU を用いた FFT について,単一 GPU,単一ノード複数 GPU,複数ノード GPU のいずれについても新規性のある手法を開発し,世界最高水準の高性能を達成している.今後プロセッサ性能のさらなる向上により,所要時間の主要部分はデータ移動となる傾向は一層強まると考えられ,メモリ律速な FFT というアルゴリズムにおけるこれらの多大な成果は,今後の高性能計算・スーパーコンピューティング,ひいては計算科学の発展に寄与することが極めて大である.

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。