（様式 20）成果報告書
TSUBAME 共同利用

令和 4 年度

学術利用

成果報告書

利用課題名 LRnLA アルゴリズムを用いた物理シミュレーション
英文：Simulation of Physical Processes with LRｎLA Algorithm
善甫 康成
Yasunari Zempo
法政大学 情報科学部
Computer and Information Sciences
http://cis.k.hosei.ac.jp/
邦文抄録（300 字程度）
計算の中で CPU と GPU を同時に使い並列処理を行うヘテロな計算を行えば、利用可能なすべての処理能力を活用することができる．もちろん CPU のピーク性能とメモリ帯域幅が GPU と比べ 20 倍程度の低いので、シミュレーションに CPU と GPU の両方を同時に使用することは非効率的な場合が多い．
そこで CPU の並列化効率を向上させ、GPU と同等の性能を発揮できる新しい時間ブロックアルゴリズ
ムを考案した．空間と時間にまたがるサブタスク間でデータを交換するようにデータ構造を工夫し、利用することとした．我々がこれまで開発してきた LRnLA 型の 1 つの有用なアルゴリズムとなる．
英文抄録（100 words 程度）
A heterogeneous computation can engage both CPU and GPU parallelism at the same time, andtake advantage of all available processing power. But CPU peak performance and memory bandwidth
are at least 20 times lower than that of GPU, so simultaneous use of both CPU and GPU for
simulation may be inefficient. We propose a new temporal blocking algorithm of the LRnLA family
that can increase the efficiency of CPU parallelization so that the performance is on par with GPU.
The algorithm uses the data structure designed specifically to exchange data between subtasksspanning space and time.

Keywords: LRnLA ・temporal blocking・LBM・hwloc・many-core
背景と目的
GPU を搭載したマシンにおいて、GPU ばかりでなく CPU の計算処理能力も利用したヘテロな計算が行えれば、すべての計算処理能力を使うことができる．しかし奈良が、GPU と CPU のピーク性能やメモリーバンド幅には大きな差がある．大規模な数値計算を GPU を用いて計算を行うときでも、CPUも当然利用している．この CPU をどれほど効率的に行うのが、今回の研究テーマであった．
前回までの報告で、CPU 制御下の RAM に保存されているデータを GPU で処理しても計算速度が落ちない計算手法の開発の報告を行った[1,2]. その手法を使うと、GPU グロバールメモリに入れるほどの計算ばかりではなく、CPU 制御下の RAM やSSD に入れなければならないほどの数 TB のサイズの計算までできるようになった．さらに計算性能を向上させるてめには、CPU の処理能力まで利用するが望ましい．さて TSUBAME3.0 で設置されている CPU の性能は、GPU に比べるとかなり低く、その性能は約 20 分の 1 程度である．この環境で CPU性能を利用し、CPU でも GPU 並みのパフォーマンスで同じ計算できるような新しいアルゴリズムを開発することが目的である．

概要
Finite Difference と Lattice Boltzmann などの数値計算スキームを CPU で効率的に実行するために、実装したアルゴリズムは ConeTorre (CT)というLRnLA(LocallyRecursive
nonLocallyAsynchronous) である[1, 3]．並列ではない計算でも、メモリバンド幅が性能ボトルネックになる場合、CT は L1, L2, L3 キャッシュでデータを局在化させることができ、データアクセス時間を減少させることができるという特徴を持っている．CT は𝑁𝑁と𝑁𝑁𝑇𝑇という引数がある関数かサブルーチンとして理解するとわかりやすい．図 1 に示したように、時空間次元𝐷𝐷の計算で、𝐶𝐶(𝑁𝑁)を計算領域とする．つまり各辺に 𝑁𝑁 個 の セ ル を 持 つ 立 方 体 と す る ． ConeTorre
𝐶𝐶𝐶𝐶(𝑁𝑁, 𝑁𝑁𝑇𝑇 ) という関数で、𝐶𝐶(𝑁𝑁)の中のスキーム計算実行していく．時間軸が1から𝑁𝑁𝑇𝑇 まで分割されている．各軸で１セルずつずれて𝑁𝑁𝑇𝑇 回繰り返し、𝐶𝐶(𝑁𝑁)の計算を実行する．
さらに𝐶𝐶𝐶𝐶(𝑁𝑁, 𝑁𝑁𝑇𝑇 )は、𝐶𝐶𝐶𝐶(𝑛𝑛, 𝑛𝑛 𝑇𝑇 ) (𝑛𝑛 < 𝑁𝑁, 𝑛𝑛 𝑇𝑇 < 𝑁𝑁𝑇𝑇 )というサブタスクに分解できる(図 1)．𝐶𝐶𝐶𝐶(𝑁𝑁, 𝑁𝑁𝑇𝑇 )で計算すべき時空間を覆い、全計算を実行する．𝑁𝑁と𝑁𝑁𝑇𝑇 というパレメターがあるため、𝐶𝐶𝐶𝐶(𝑁𝑁, 𝑁𝑁𝑇𝑇 )というサブタスクのデータ量を調整できる．分解方法を上手 く 選 択 す れ ば 、 L2 キ ャ ッ シ ュ に 入 れ る
𝐶𝐶𝐶𝐶(𝑛𝑛𝐿𝐿2 , 𝑛𝑛 𝑇𝑇 𝐿𝐿2 )が得られる．これをさらに分解すれば L1 に入れるタスクが得られる．これによりキャッシュでのデータの局在性を十分活用することができ、計算のパーフォマンスを向上させることができる．

（様式 20）成果報告書

タを L1 キャシュに入れるという方法である．

図 3:

図 1. 𝐶𝐶𝐶𝐶(𝑁𝑁, 𝑁𝑁)の数値計算領域と更に分解した𝐶𝐶𝐶𝐶の様
子．矢印はデータ依存を示す．

現在の CPU ではマルチコアが一般的である．従って、マルチコアによる並列処理を行う場合、コアあたりの L2, L3 キャッシュ量が減少するため、データの局在化によるパーフォマンス向上が期待できない．そこで、この課題を解決するため、新しい
FArShFold という並列法を開発した．
FArShFold というアルゴリズムを導入するため、FArSh (Functionally Arranged Shadow) というデータ配置が必須である[4]． FArSh データは、隣にある CT の間の交換のために考案されたデータ配列である．CT 計算を行うための元の計算領域の𝐶𝐶(𝑁𝑁)のデータは、主メモリストレージ（RAM か SSD)からロードし、処理後同じのメモリストレージに保存される．CT 計算が行われる時空間での斜めのスロープのデータは、FArSh データ配列からロードしCT 計算の後、同じ FArSh データ配列に上書きされる (図 2)．

FArShFold の並列化

図 4．FArShFold の並列化とデータ依存の様子

その結果、𝐶𝐶𝐶𝐶の間のデータ交換では、𝐶𝐶𝐶𝐶スロー
プのデータは各コアの L2 および L3 キャッシュに残る．コア間の交換には、𝐶𝐶(2) のデータしか送らないことになるので、並列化の効率は飛躍的に高まる.
TSUBAME3.0 ノードの場合は Intel Xeon E52680 V4 が 2 台ある． 各 CPU の L2 キャッシュは256KB であって、L3 は L2 より 10 倍大きい．コア数は 14 で(5 + 5 + 4)の 3 コアクラスター構成である．これらのコアは L3 キャッシュを共有している．
そこで𝑛𝑛’ = 3𝑛𝑛𝑠𝑠 として𝐶𝐶𝐶𝐶(𝑁𝑁, 𝑛𝑛𝑠𝑠 )を5(4)スレッドで処理すれば、その5(4)スレッドが L3 キャッシュに局在化することになるので、FArSh を共有できるはずである(図 4)．
結果および考察考 案 し た FArShFold ア ル ゴ リ ズ ム を 実 際 のFDTD コードに実装した．Hwloc ライブラリを使用してコアあたりの処理を分ける.AVX ベクトル演算を使用も実装した．数値スキームとして、LBM を選択した．LBM で、セルあたりのデータとセル更新あたりの浮動小数点演算（FLOP)を詳しく調べることができる．具体的には LBM 法のステンシル（Q)と衝突演算子を変更する．それによりセルデータ量によってパーフォマンスの変化を調べることができる．

図 2. FArSh データ配列の使い方

マルチコアの並列化で L2, L3 上のデータ局在性を保つため、次のような並列化法が考えられる．まず、𝐶𝐶𝐶𝐶(𝑁𝑁, 𝑁𝑁)で計算領域を確保する(図 1)．次に、𝐶𝐶𝐶𝐶(𝑁𝑁, 𝑁𝑁)を𝐶𝐶𝐶𝐶(𝑁𝑁, 𝑛𝑛’)に分解する(𝑛𝑛’ < 𝑁𝑁)．𝐶𝐶𝐶𝐶(𝑁𝑁, 𝑛𝑛’)をさらに𝐶𝐶𝐶𝐶(𝑁𝑁, 𝑛𝑛𝑠𝑠 ) に分解する (𝑛𝑛𝑠𝑠 < 𝑛𝑛’) (図 3)．こ
こで𝐶𝐶𝐶𝐶(𝑁𝑁, 𝑛𝑛𝑠𝑠 )それぞれ処理はスレッド並列により実施する．その結果、空間並列化ではなく、時間軸で並列化を行うことが可能になる．その時 FArSh
データ配列はスレッド数に合わせて分解し、1 コアの L2 キ ャ ッ シ ュ 分 を 各 コ ア に 割 り 付 け る ．
𝐶𝐶𝐶𝐶(𝑁𝑁, 𝑛𝑛𝑠𝑠 )を更に𝐶𝐶𝐶𝐶(2, 𝑛𝑛𝑠𝑠 )に分解する．これに対応する元の計算領域（𝐶𝐶(2)という立方体）にあるデー

図 5．パフォーマンスベンチマーク

基本的なベンチマークは Ryzen R9 5950X で行った ( 図 5) ． 測 定 単 位 は Pups (LBM populationupdate per second)を用いた．これは 1 秒あたりのセル更新数 (LUps - Lattice cell Update per second)に𝑄𝑄を掛けたものである．
時空間ブロッキングを使用していない LRnLA の場合、パフォーマンスピークは~6 Pups であるが、CT を用いた場合、その 5 倍約 30Pups となりかなりの性能向上が期待できる(図 5)．またこのベンチマークで𝑛𝑛’の最適値を得ることもできる．最適パーフォマンスは１GLUps を超えることも分かった．
まとめ、今後の課題新しいアルゴリズム ConeTorre を考案した．このアルゴリズムを FDTD コードに実装して、１個のマルチコアの CPU において GPU と同等のパーフォマンスを得た．これはマルチコアの並列化において各コアに対応する L2, L3 にデータを局在化させることができたためである．
今回は基礎検討の段階であるが、GPU でも計算処理を実行する場合、同じ CT の時空間データ領域を分解できる．今回考案したアルゴリズムを用いれば GPU と CPU 組み合わせたヘテロ計算を実行できるはずであり、GPU だけの計算のパーフォマン
スより更に向上させるものと期待できる．
参考文献[1] Zakirov, A, V Levchenko, A Perepelkina, andYasunari Zempo. "High performance FDTD
algorithm for GPGPU supercomputers." In
Journal of Physics: Conference Series, vol. 759,
no. 1, p. 012100. IOP Publishing, 2016.
[2] Shimokawabe, T., Endo, T., Onodera, N.,
Aoki, T.: A stencil framework to realize largescale computations beyond device memory
capacity on GPU supercomputers. In: 2017
IEEE International Conference on Cluster
Computing (CLUSTER), pp. 525–529 (2017).
IEEE[3] Levchenko, V., Perepelkina, A. Locally
Recursive
Non-LocallyAsynchronous
Algorithms
forStencil
Computation.
Lobachevskii J Math 39, 552–561 (2018).
https://doi.org/10.1134/S1995080218040108[4] Perepelkina, A., Levchenko, V.D. (2021).
Functionally Arranged Data for Algorithms
with Space-Time Wavefront. In: Parallel
Computational Technologies. PCT 2021. CCIS,
vol 1437.

（様式 20）成果報告書