Previous ToC Next

152. 富岳の上での「データ構造とアルゴリズム」(2021/10/5)


FDPS を使ったプログラムが富岳の上でいまひとつ速くない、というのがみえ てきてて、色々中身をみてわかってきたことを漫然と書いてみます。

まず、富岳である程度以上のノード数でMPIでちょっとややこしい通信が起こ るプログラムを速く走らせるには、1プロセス1ノード、48スレッドでやること が好ましいです。これは何故かというと、通信が本当に近傍だけで終わるので はなくて少し遠いノードまで通信することが必要なアプリケーションでは、 同じ規模の計算を同じノード数でするなら、プロセス数が少ないほうが通信相 手を減らすことができるからです。

通信にかかる時間には、データ量に比例する成分の他に必ず通信する相手の数 に比例する成分があり、これは特にノード数が大きいと無視できなくなります。 FDPS ではツリー法を使っている関係上、あるプロセスは他の全プロセスから 少なくとも1粒子(というかそのプロセスの粒子全体の多重極展開)をもらう 必要があり、さらに物理的に近いプロセスからはより詳しい構造をもらう 必要があります。プロセス数が少なくなると、大雑把にいって少なくとも1粒 子をもらう部分については通信量が比例して減るし、近くの分も、隣接する プロセスが重複して同じようなデータをもらうのを避けることができて減るこ とになります。

まあこれは、隣接プロセスで同じものを受け取るようなことがあるならちゃん とそれを利用した通信をしろ、ということだし、そもそもツリー法じゃなくて FMM 使えば?という話だったりもしますがそれはちょっとここではおいておき ます。

あと、富岳は1ノードのメモリがあんまり多くないので、非常にノード数が大 きい計算では、4プロセス1ノードとかでは MPI がとるメモリが無視できなく なってきます。プロセス数に比例した成分があり、システム全体からみると プロセス数の2乗に比例したメモリがMPIに喰われるからです。1ノード1プロセ スにできれば、MPIが消費するメモリを1ノード4プロセスの場合の 1/16にでき、 非常に大きなメリットがあります。

富岳の通信性能は決して悪くはないのですが、「京」に比べると劇的に向上し ているわけではないのにノード単体の性能は劇的にあがっているので、通信ネッ クにならないようにするのは「京」に比べると難しくなっています。

とはいえ、1プロセス48スレッドというのは2重の意味で難しいです。第一に、 そもそもほとんどの HPC アプリケーションはそんなところで動かしたことが なくて、何が起こるかわからない。もうひとつは、富岳のプロセッサ A64fx の1ノードはNUMA の4クラスタからなっていて、クラスタ内では2次キャッシュ が共有されている上にハードウェアバリア機構があるのでハイブリッド並列で ある程度の性能がでますが、4クラスタまとめで1プロセスとなるとNUMA の欠 点がみえてまともな性能になるかどうかわからない、ということです。 クラスタ毎にメモリコントローラがあって、HBM メモリにつながっていて 200GB/s でますが、クラスタ関は 120GB/s (くらい)のリングでレイテンシも 増えるので性能低下する可能性があります。

とはいえ、フルノード計算というような話になるとユーザーに残されたメモリ 空間が全然違うので、それだけの理由でも 1 ノード1プロセスが望ましいし、 そうするとそれでちゃんと性能がでるようにする必要があります。

1プロセス48スレッドのプログラムと1プロセス例えば 2-4スレッドのプログラ ムでは性能をあげるために必要なアプローチが大きく違ってきます。これは 単純にアムダールの法則のの問題で、並列化されてない部分が例えば5%でもあ ると、4スレッドくらいでは大した問題にならないですが48スレッドでは致命 的だからです。

まあ、この状況は実は、中国の Sunway TaihuLight によく似ています。 TaihuLight は1チップ4クラスタで、1クラスタが1つのマネジメントコアと 64個の計算コアからなっていてマネジメントコアでメインスレッドが走ります。 これにやらせるとあらゆることが遅いので、計算コア側に渡す必要があるわけ です。富岳を48スレッドで使うと同じような話になります。とはいえ、大きく 違うのは、ちゃんと共有メモリでキャッシュコヒーレンシもあるので OpenMP で並列化するだけでそれなりの性能はでることです。

FDPS の内部実装で問題になったことの一つは粒子のソートで、元々ソートはあんま りいい感じのノード内並列ライブラリがなくて並列マージソートが実装されて いたんですがこれが何故か富岳ではとても遅くなってしまっていました。 マージソートを改良してもいいのですが、原理的に NUMA で別クラスタへのア クセスが少なそうなアルゴリズムがよかろうということで、分散メモリでも性 能がでるサンプルソートを実装しました。

実装してわかったことは、48スレッドの場合には parallel for の起動オーバー ヘッドはかなり大きい、それに比べるとバリア同期のオーバーヘッドはずっと 小さい、ということです。なので、なるべく起動オーバーヘッドを減らすため に、ソートルーチンの最初に一度だけパラレルセクションを開いて、その後可 能な限り閉じないようにして、シリアライズが必要な処理はバリアとスレッド番号依存の 処理で実装しました。さらに、ソート時のメモリフットプリントを小さくする ため、ソートルーチンの中でソートキー+インデックスの構造体を作って、こっ ちをソートして、最後に並べ変えたキーを使ってソートします。

割といい感じにかけて性能も悪くなくて、24スレッドで1スレッドの std::sort の20倍くらいの性能になったので、 ここでソートルーチンだけ 公開しました。富岳で速いプロセス内ソートが欲しいという人は使ってみると 幸せになれるかもしれません。なお、インデックスソートなので、比較関数で はなくて比較するキーを生成する関数を与えるので、比較用キーが生成できる 必要があります。FDPSではキーは 128ビット整数で、自前のクラスと比較関数 で実装されていて、そういうものでも扱えます。

FDPS 内部はそうはいってもできるとこは OpenMP 並列処理をするようになっ ていて、本質的な問題はあまりないのですが、FDPSを使って書かれたアプリケー ションとなるとまた色々なことが起こります。粒子数全部になんかす る、例えばもとまった加速度から時間積分するとか、タイムステップに関係し た何かを計算するとかがあって、それが OpenMP 化されてないとなにしろ 50倍くらい遅いわけですからたちまちボトルネックになります。

Vampir とかの実行可視化ツールが使えれば何がおこっているかわかりやすい のですが、富岳ではまだ(?)利用可能ではないようなので自分でプログラムに タイマーいれて測定していくのが確実です。まあその、面倒ですがやればでき る話で、想定より実行時間がかかっているところを直していけばいいわけでで す。

さらに、アプリケーションプログラムをみていくと、ちゃんと OpenMP化さ れているのに非常に遅い箇所がでてくることがあります。以下のような例があ りました。N体プログラムで、粒子の自己同一性を維持するためシステムワイ ドでユニークなidをつけているとします。ぶつかって合体したら新しい粒子に なりますが、またユニークな番号をつけるわけです。この時、時間積分プログ ラムの中でもこのid を使って色々な処理を書くことでわかりやすいプログラ ムにできます。(実際のところは使わなくてもいいかもですがあるプログラム がそう書かれていたということです)

そうすると、例えばある粒子は、自分の近くにある粒子をこの id で知ってい ますが、 id からはその粒子が粒子の配列のどこにあるかは分からないので、 それを教えてくれる連想配列がほしくなります。で、 C++ は std::map でそ のような機能を提供しています。

しかし、 std::map は、要素を追加する処理を並列化できません。

このことがどういう結果をもたらすかというと、富岳で 1プロセス1ノードで 動かすと、FDPSを使った相互作用計算全部(領域分割、粒子交換、ツリー構築、 相互作用計算に必要な情報交換、実際の相互作用計算をあわせた全部)よりも この粒子 id の連想配列を作るほうが遅くて、性能が半分以下になっていまし た。 EPYC で32スレッドでじっくりしてもそこまで性能落ちないのですが、こ の辺は CPU のシングルスレッド性能、特に条件分岐とかポインタチェースの 性能の差がでます。

抜本的な解決は「std::map 的な連想配列は計算時間的にクリティカルになる 可能性があるなら使わない」ですし、他のアプローチは使うなら更新を最小限 にすることです。後者はしかし領域分割のMPI並列である都合上かなり面倒で、 ステップ毎に粒子がでたりはいったりします。また、配列の中での粒子の位置 も変わります。今回は、とりあえず std::map の代わりの、並列に要素セット できるものを実装しました。使いかたが、時間ステップの始めに全部粒子を 登録、その後はそれを使うだけ、だったので、動的な要素の追加は不要で B-tree 的な構造を動的に作る必要はなく、全部セットしてから1度ソート をかければあとはそれを2分探索すれば十分です。そうすると、あらかじめ 配列のサイズを確保すれば、並列にセットできるしできた配列は 上の並列ソートを使えば十分高速にソートできます。というわけで、 このような変更で十分な速度になりました。

私が C++ よくわかってないので見かけレベルで std::map との互換性が維持で きてなくて、イテレータを返せてなくて、、、と書いてたらできるやり方が わかりましたが、あとキーを指定した map[key]=value; みたいな書き方も できてなく書換えが必要な箇所が多いのですが。とりあえず速いので許して下 さい的なものです。

なお、他に粒子の std::vector の std::vector とかも使われていて、確か に便利で間違いの少ないプログラムが書けるのですが性能的にには問題で、要 素追加のしかたによって大きく速度が低下していました。具体的には、粒子を push_back すると非常に遅くて、最初に resize して[]= でいれると速くなり ました。これは push_back ではなくて reserve を不用意に使ったのが問題だっ たかもしれませんが詳しくはみてないです。

このように、STL コンテナタイプは非常に便利なのですが、特にスレッド数が 多い並列実行では性能的な問題がおきがちであることに十分な注意を払う必 要があります。まあ、言い換えると、どうしても必要でなければ実行時にタイ ムステップ毎にサイズ決めてもいいので可能な限り普通の配列を使うほうが無 難だ、ということです。メモリアロケーションが裏で起こり、そこに潜在的に シリアルボトルネックがあるようではスレッド数が多いと使い物にならないの です。

メモリアロケーションがボトルネックになるのは、スタックにデータをおけば避 けることができます。スタックはスレッド毎に存在しているからです。とはい え、そうするともちろん作った関数内でしか存在しないわけでスコープに 注意する必要があります。 まあ、メモリリークしないので逆にいいのかも しれません。そういうことのための stack_allocというのもあるようです。
Previous ToC Next