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

割といい感じにかけて性能も悪くなくて、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