＊ここに掲載するのは、HECToRレポート「Improving the performance of GWW A dCSE Project, I. Bethune, EPCC, The University of Edinburgh, August 9, 2010」を要約したものです。
概要
この報告書は、エジンバラ大学EPCCで行われたdCSEプロジェクトです。この作業は、GWW計算の主要なカーネルであるFFT Tranpose操作の通信パフォーマンスを改善することを目標にしています。この作業と並行して、シェフィールド大学（Merlyne De Souza教授）において、FFTグリッドの既存の1Dドメイン分割が2D分割で置き換えられてスケーラビリティが改善されました。このタイプの最適化に関する包括的な議論は、例えばJagode [1]とSigrist [2]を参照してください。
この作業はHECToRフェーズ2a (Quad-core XT4)および2b (24-core XT6)システムを用いて行われました。HECToRシステムの詳細はWebサイト[3]を参照してください。
Quantum Espresso[4] (opEn Source Package for Research in Electronic Structure, Simulation,
and Optimization)は、GPLライセンスのフリーソースで密度汎関数法DFTによる物性研究に用いられます。その応用には、基底状態の計算、構造最適化、分子動力学、線形応答（フォノン）、分光学などがあります。これは、CASTEPやCPMDのような類似のパッケージと同様に平面波をベースとし、Hartree-Fockやハイブリッド関数（PBE0、B3LYP、HSE）を含む一連の擬ポテンシャルと交換相関関数が実装されています。 DEMOCRITOS国立シミュレーションセンター（Trieste）と欧州および米国の他の複数の材料科学センターとの国際協力によって開発されました。
他のパッケージとは異なり、Quantum Espressoはモノリシックな単一実行可能ファイルではなく、それぞれが特定の機能を実行する独立した実行可能ファイルのセットです。このプロジェクトでは、PW.x（MDを含む電子とイオン構造）とPH.x（密度汎関数摂動理論を用いたフォノン）が対象となりました。Quantum EspressoはFortan 90で書かれており、約1000のソースファイルに30万行以上のコードが含まれています。各実行ファイルのソースに加えて、すべての実行ファイルで共有される共通のModulesディレクトリがあります。これには、I / O、並列化、データ型、FFTなどの一般的な機能が含まれます。線形代数演算のためのBLAS、LAPACKおよびScaLAPACKの他に、FFTライブラリ（例えば、FFTW3）を含む多くの外部ライブラリが必要とされます。
GWW（Wannier関数を使用したGW計算）は、Quantum Espressoパッケージに最近追加されたものです。Paulo Umari博士によって開発されたこのコードは、GW近似の中で局所的なWannier軌道基底を用いて分極を計算します。この方法は通常の平面波基底による方法より約2桁高速です。
プロファイル分析から、計算時間の大部分（50%以上）は3D FFTであり、その中でもFFT transposeでのMPI_Alltoallvが大部分を占めていました。
下記のデータをベンチマークに使用しました：
| 1. | CNT40 - 長さ8.5Åの単位格子内の16C原子の小さなナノチューブ |
| 2. | シリコン - 長さ20.5Åの単位格子内の結晶バルクシリコンの64個の原子 |
| 3. | CNT80 - 長さ24.3Åの単位セルにおける96C原子のさらに大きなナノチューブ |
CNT40テストケースは小さすぎて実用的ではありませんが、実行時間が非常に短いというメリットがあり開発中に便利なテストです。他の2つ、特にCNT80は、これまでのコードで達成できるものの最先端に近いものです。
FFT実装
概念的には、FFTグリッドは実空間ではスライス(平面)、フーリエ空間では列として分散されます。フーリエ空間での列分散（2D分割で利用される）の理由は、すべての列が必ずしも同じ数（または任意の）の非ゼロフーリエ係数を持つわけではないからです。列を分割することによって、列の数は通常MPIプロセスの数よりもはるかに多くなり、プロセス間で列を分散させてプロセス当たりの非ゼロフーリエ係数の数を負荷分散することができます。この技術の完全な説明は、Giannozzi et al、2004 [5]を参照してください。Quantum Espressoは、解像度の異なる2つのグリッドを維持します。細密グリッドは通常、粗グリッドの約2倍のグリッドポイントを含みます。しかしながら、各タイムステップでは粗グリッド上のFFTが多く実行されます。この分割により、3D FFTは、平面内のローカルデータに対して実行する2D FFTと、全プロセスを用いたMPI_Alltoallvによるグローバルト転置と、列内の新たにローカライズされたデータに対する1D FFT変換で構成されることになります（逆変換も同様）。
·FFT転置操作
フーリエ・グリッドの各列は、実空間グリッドの全ての平面と交差するので、原理的には、各プロセスは2つのローカルFFTステップ間の全てのプロセスにあるデータを転送する必要があります。 ですが実際には、必ずしもそうではありません。 プロセス数がスライス数より大きい場合は、一部のプロセスはデータを受信しません（または逆FFT変換では送信）。 一般に各プロセスは、プロセス数が平面または列の数に正確に分割されないため、他の全てのプロセスに異なる量のデータを送受信します。例として、16コアのCNT40テストケースを考えます。ここでは粗グリッドを30x30x30要素として、この場合30面および900列ありますが、そのうち657面を非ゼロフーリエ係数とします。
例えば、16のコアの間でこれらを分割すると、14プロセスには2面、残りには1面が割り当てられます。15プロセスには41列、残りに42列が割り当てられます。領域サイズの全ての組み合わせを考慮に入れると、Alltoallvには4種のメッセージサイズを考えることが出来ます：84要素、82要素、42要素、および41要素。また、各グリッド要素は倍精度複素数、すなわち要素当たり16バイトです。
既存コードでは、この他に、非同期1対1通信の選択があります。
·共有メモリ型Alltoallv
このアプローチは、同じSMPノード上のプロセス（XT4ではノード当たり4プロセス、XT6ではノード当たり最大24プロセス）でUnix SHM APIを使用して共有バッファを実装します。これは、Incompact3Dで使用されている2Decompライブラリ[6]のアプローチに従い、どのプロセスがどのSMPノードに属しているかを識別して共有バッファを設定するためにCrayのDavid Tanquerayのコードを使用します。
HECToRフェーズ2aの64コアを使用すると、メッセージ数が4032から240に減少します。また、メッセージを集約することで、メッセージ数に比例したネットワーク待ち時間の影響を軽減します。
·パディング付きAlltoall
このやり方は、異なる量のデータが各プロセスによって送受信される場合はMPI_Alltoallvを使用する必要がありますが、もしデータが同じ量のデータを送受信するようにパディングされている場合は、代わりにMPI_Alltoallを使用できるという事実から動機づけられました。メッセージが小さい場合にはMPI_Alltoallは、` store and forward'と呼ばれる最適化されたアルゴリズムを使用します。これは、メッセージ待ち時間を短縮するために帯域幅の使用量を増加させるものです。具体的には、デフォルトアルゴリズムのコストはO（p + n）となりますが（pはプロセス数、nはメッセージサイズ）、store and forwardアルゴリズムはO（log（p）+ nlog（p））となります。プロセス数が多く、メッセージサイズが小さい場合は、余分なパディングデータを送信するコストを克服する必要もありますが、パフォーマンスが大幅に向上することが予想されます。メッセージサイズが十分に小さいとき、MPI_AlltoallはMPI_Alltoallvよりもはるかに高速です - 256コアの256Bメッセージでは最大5倍高速です。
具体的に、以前の例（16コアのCNT40）と同じ例を使用すると、全てのプロセスによって送信される合計データサイズは1232要素（20kB）です。 各プロセスに最大の送信サイズに等しい追加のパディングが追加された場合、送信される合計データは1344要素になり、合計データ量はわずかに9％増加します。このサイズのメッセージ（1kB）の場合、個々のメッセージの帯域幅は、10-6のオーダーのレイテンシと比較して10-7オーダであるため、パディングに伴う余分なコストは無視できます。
このやり方は、各プロセスが既にグローバル最大メッセージサイズを計算するために必要なすべてのデータを持っているので、SHMアプローチよりもはるかに少ない追加計算で済みます。
·Scatter/Gather Alltoallv
第3のやり方として、MPI_GathervとMPI_Scattervを使用して各SMPのルートノードでデータを収集する方法を実装しました。これはCASTEP [7]における同様の実装に倣ったものです。SHM実装と同様の構造ですが、パッキング段階とアンパック段階の両方で追加の手順が必要です。
ベンチマーク結果
·FFT
HECToR Phase 2aでは、CNT80ベンチマークはすべてのアルゴリズムが良好にスケールします。SHM Alltoallvが明らかに最良の選択であり、128コアまで良好なパフォーマンスを示します。
シリコンのベンチマークは、CNT80の場合と非常に似ています。最高のパフォーマンスは90コアで達成されています。また、新しいFFT実装がスケーリングを停止する領域（例えば、シリコンベンチマークの場合は128コア）では、元の実装より約4倍高速です。
HECToR Phase 2bでは、CNT80ケースはAlltoall通信を用いる方法は24コアを超えると性能は急激に劣化します。これはノードが24コアを搭載して、ネットワークを使用しないためです。パディング付きの場合はそれよりは性能が上回りますが、十分ではありません。SHMとScatter/gatherコードは、CNT40よりもこの大きな例ではいくらか優れています。288コア（12ノード）までの妥当なスケーラビリティを提供します（SHMコードは1コア性能に比べて約10倍の高速化）。これは、全メッセージ数が82656（そのうち79488はネットワークを横切る）から132に減少するためで、通信にノード当たり1プロセスだけを通信に用いる事は明確な利点があります。
シリコンケースでは、同様に既存コードは24コアを超えてスケールアップされず、同じくスケーラビリティのためにはSHMコードが必要です。
·アプリケーションのベンチマーク
これらの変更の利点を明らかにするために、元のAlltoallv実装と、新しいパッディングされたAlltoallおよびSHM alltoallvを用いて完全なPW.X実行ファイルをコンパイルしました。これを用いてGWW計算の最初の2段階（HECToR Phase 2a上）を実行しました。
いずれの場合でも、パッディングされたalltoallとSHM alltoallv手法は、元のalltoallv実装よりも高速でした。シリコンケースでは、SHM手法は25〜29％高速でした。
文献
| [1] | Fourier Transforms for the BlueGene/L Communication Network, Heike Jagode, 2006, http://www2.epcc.ed.ac.uk/msc/dissertations/dissertations-0506/hjagode.pdf |
| [2] | Optimizing parallel 3D Fast Fourier Transformations for a cluster of IBM POWER5 SMP nodes, Ulrich Sigrist, 2007, http://www2.epcc.ed.ac.uk/msc/dissertations/dissertations-0607/2298876-27h-d07rep1.1.pdf |
| [3] | HECToR website, http://www.hector.ac.uk |
| [4] | Quantum Espresso, http://www.quantum-espresso.org/ |
| [5] | First-principle molecular dynamics with ultrasoft pseudopotentials: Parallel implementation and application to extended bioinorganic systems, P. Giannozzi, F. De Angelis and R. Car, J. Chem. Phys. 120 (2004) |
| [6] | 2DECOMP&FFT User Guide, Ning Li, 2010, http://www.hector.ac.uk/cse/distributedcse/reports/incompact3d/UserGuide.html |
| [7] | An LPAR-customized MPI_AllToAllV for the Materials Science code CASTEP, Martin Plummer and Keith Refson, 2004, http://www.hpcx.ac.uk/research/hpc/technical_reports/HPCxTR0401.pdf |