学際大規模情報基盤共同利用・共同研究拠点 平成 27 年度共同研究 最終報告書 2016 年 5 月

jh150003-NA02

時間並列化アルゴリズムの新しい方向性と実用例の探索
萩田克美（防衛大学校）

本研究では、時間方向の並列化について、体系的に整理し、応用の範囲を広げることを目指した。時間方向並列化に成功した事例を基に、議論を深めた。時間方向並列の効果としては、利用ノード数を気にせず経過時間を短縮する第１種と、利用ノード数が同じままで経過時間を短縮する第２種に分類できる。第２種が成立する理由は、通信の削減や計算の効率向上がある。時間方向並列化は、予測－修正の組み合わせで実現している。大規模 RMC 法のケースは、Parallel Prediction-Serial Correction (PPSC)であり、Parareal や偏微分方程式系の時間方向並列化は Serial Prediction-Parallel Correction(SPPC)であると分類できる。本研究では、これまでの多くある SPPC 型ではない PPSC型の成功事例である大規模 RMC 解析の成果確立を目指した。

1.

共同研究に関する情報

2.

数年後の超大規模計算分野では、これまでの並(1) 共同研究を実施した拠点名
東京大学
九州大学

列化方針に加えて、新たな並列化軸による高い並情報基盤センター

名古屋大学研究の目的と意義列性能の実現が求められている。1 つの方向性と情報基盤センターして、時間軸での並列化が期待されている。研究

情報基盤研究開発センター

代表者および共同研究者らは、これまで、実アプリケーションの立場や基礎検討の立場で、個別に、(2) 共同研究分野■

超大規模数値計算系応用分野「時間並列化」を検討しているが、系統的な理解

超大規模データ処理系応用分野の下で検討しているわけではない。今後の発展の

超大容量ネットワーク技術分野

ため、JHPCN 拠点を核として研究者同士が連携し、



超大規模情報システム関連研究分野ネットワーク型共同研究として議論を深め、「時間(3) 参加研究者の役割分担並列化アルゴリズム」の新しい方向性と実用例の参加研究者
萩田 克美
（防衛大）

探索を行う。

高見 利也（九州大／大分大学）
室谷 浩平
（東京大）
荻野 正雄
（名古屋大）
中島 研吾
（東京大）
須田 礼仁
（東京大）
岡本 祐幸
（名古屋大）
杉田 有治
（理研）

役割分担
総括、時間方向並列のアルゴリズムに関する議論、実装検討、計算実施
総括、時間方向並列のアルゴリズムに関する議論、実装検討、計算実施
MPS 法における時間方向並列化の検討
MPS 法における時間方向並列化の検討
マルチグリッド CG 法の知見に基づくアルゴリズムの議論
時間方向並列のアルゴリズムに関する議論
生体高分子 MD 法における実応用に向けた議論・検討
生体高分子 MD 法における実応用に向けた議論・検討

時間方向並列化を、効果的に実現した事例報告は、まだ少ない。大規模な RMC 法の事例など、時間方向並列の分野で注目されうる研究結果を得ている。今後、系統的なベンチマーク報告のための大規模計算を実施し、当該分野の研究報告としてまとめる必要がある。準備段階の議論の１つとして、生体高分子 MD 法におけるクーロン力の 3d-FFT計算に関して、RESPA 法の改良（補正計算の導入）による計算コスト軽減が見込まれており、実装で実証検証することで、広い普及の可能性が期待される。これらの研究は、広く、意義があるものと考えられる。
また、時間方向並列化の一般理論についても、再整理の余地がある。1964 年の parallel time1

学際大規模情報基盤共同利用・共同研究拠点 平成 27 年度共同研究 最終報告書 2016 年 5 月

4. 前年度までに得られた研究成果の概要

integration（予測と修正の組み合わせ）論文を出発点として、2001 年の PARAREAL 論文で並列計算の高速化の理論的な可能性を示すまでに至ったが、研究代表者および副代表者は、時間方向並列化

実際に実測に基づく並列性能までは議論していなアルゴリズムを検討し、実装し高速化の効果があい。この２～３年で、具体的な修正アルゴリズムることを確かめている。その成果については、国を利用した研究成果が発表されるようになった。

際会議等で発表している。

実際の並列計算機の特性に対峙した形での実用的大規模な RMC 法（SC14 のポスターなど発表）で理論整理には、大きな意義があると考えられる。

は、逐次的なモンテカルロ探索法の評価関数計算

より概念を一般的に捉えて、適用対象を整理し、を、時間並列可能部分とそれ以外に分離し、時間一般化を図ることが求められている。本研究課題

並列化の副次効果として通信回数を削減すること

では、いくつかの時間方向並列化に成功した事例

で、同じ MPI プロセス数でも、高速化できることを基に、概念の一般化とその理解に基づく適用対を示している。
（ただし、より多数の MPI プロセス

象の探索と成功事例の創出を行う。今後、より高数に対する並列化効果としての経過時間削減のベ並列になるスーパーコンピュータの活用技術としンチマーク測定などは、未実施である。本研究課て、意義が大きいと考えられる。

題で実施したいと考えている。）
分子動力学に対する適用可能性の研究では、通3. 当拠点公募型共同研究として実施した意義

常用いられる近似時間発展計算を恒等変換として簡略化した場合でも実用的に適用可能であること

本研究は、大規模並列計算機での時間方向並列を示し、非同期通信を利用した高速化法など、大化アルゴリズムについて、萌芽的に検討するもの

規模並列計算時の効率的な実装についての成果をである。さらに、JHPCN 活動を通じて広く共同研

EuroMPI, ParCo などの国際会議で発表している。

究者を募り、多くのシミュレーション分野での横5. 今年度の研究成果の詳細

断的な検討で、理論的汎用化や応用対象の拡大を目指しており、JHPCN のネットワーク型拠点を活

平成２７年度前半は、議論や試験的検討を中心用することが、効果的であると考えている。
本研究を効果的に実施するための共同研究者とに行い、後半は、PPSC 型の成功事例とその意義して最適な人材が、JHPCN 拠点教員であることも、を広く周知させるため、大規模 RMC 解析の論文必要性の 1 つである。例えば、九州大学 高見先生化などに係る作業を実施した。

（副代表者）は、時間方向並列化の基礎論をすで(1)に検討している。東京大学 中島先生は、マルチグ

時間方向並列化の効用に関する分類整理の（理論的）議論

リッド CG 法など、時間方向並列化アルゴリズムと密接な手法を検討している。名古屋大学 荻野先生

本研究課題では、「一般に、因果律から時間方向は、MPS 法を用いた大規模計算を検討するなど、並列化は困難である」と考えられている中で、どアプリケーション応用面で貢献が期待される。のような形態で、事実上の時間方向並列化により、また、本研究では、一定の規模の大型計算機を多数ノードの並列環境下で、Elapsed time を削減利用した実証検討も行うためにも計算機リソースできるかについて整理することを試みた。代表者が必要であり、JHPCN 公募型共同研究として実施および副代表者（高見先生）が、主に、東大したいと考えている。

田先生、中島先生、Juelich Supercomputing Centre須

Dr. Robart Sperk、理研 AICS 小野チーム 飯塚先生らとディスカッションし、概念整理をした。
2

学際大規模情報基盤共同利用・共同研究拠点 平成 27 年度共同研究 最終報告書 2016 年 5 月

時間並列化の効果は、次の２つに分類できる。

法に焦点を当てると、隣接粒子間の力の計算の高速化のために、Neighboring list を作成するが、・第１種：利用ノード数の増加で経過時間を削

このリストは一定の寿命で利用される。この場合、減。（利用ノード数を固定せず）

過去の情報を用いて、未来に利用する内容を、別→ 演算処理の分散並列化で高速化。に独立に作成すること（演算のオーバーラップに・第２種：時間方向並列度の増加で経過時間を近いこと）が可能なり、時間方向並列化が実現で短縮。（利用ノード数固定）

きることになる。GENESIS 開発チームとの議論で、→ 並列化による演算効率向上・通信回数

この「非同期化」による高速化は、GPU を利用し削減などで高速化。

た高速化においても、活用できる概念であることが示唆された。

時間方向並列化の実装としては、Prediction（予現在、時間方向並列化が導入可能となる箇所に測）と Correction（修正）の組み合わせたアプロ関する仮説（見通し）として、「元の物理に近い部ーチが主である。PDE/ODE 系の Parallel in Time

分よりも、物理から離れた人為的な（高精度）近(PIT) integration による時間方向並列化は、似手法の部分に時間方向並列化が適用しやすい」、

Serial 計算で予測を素早く行い、その修正計算を特に、「演算そのものではなく、演算高速化のユー

Parallel に実施する Serial Prediction-Parallel

ティリティ部分」が対象になりやすいのではない

Correction (SPPC)型であった。一方で、代表者がかと考えて、議論・整理を進めている。

実現した大規模 RMC 法での時間方向並列化は、予測計算を Parallel に行い、修正計算を素早く(2)大規模 RMC 法解析の更なる高速化

Serial 計算で行うものである。これは、Parallel

逆モンテカルロ法（RMC 法）は、SPring-8 など

Prediction-Serial Correction (PPSC)型と分類での極小角散乱データから３次元構造を推定（モンきる。従って、概念レベルの分類は以下の通り。

テカルロ探索）する手法である（図１）。概要から・PPSC: Parallel Prediction-Serial Correction

逐次的なモンテカルロ探索であることがわかる。

・SPPC: Serial Prediction-Parallel Correction

我々は、Parallel Prediction- Serial Correction

実装を考えると、Serial の意味は、非並列ではな型の時間方向並列化を施した。この時間方向並列く、時間依存があるという意味である。ここでの化は、第 2 種の効果を示す事例である。図２には、Serial 計算は、OpenMP 並列化や、局所化した MPIS(q)の差分計算に必要なヒストグラムの差分の大Communicator での部分並列化の方が、実情に近い部分の計算を時間方向で並列化した概念図を示しと考えられる。このような整理や議論を通じて、ている。結果に、Global 通信の回数が削減された

実際に、次節の大規模 RMC 法計算の更なる高速化ことにより、高速化が実現している。

では、階層的な時間方向並列化や Serial 計算部の高並列化対応を検討するに至った。
時間方向並列化の一種として、「過去の情報で代用する『非同期化』」が考えられる。予測―修正の予測計算も、この非同期化の一種とも見なせる。
例えば、分子動力学法などハミルトニアンの時間発展で記述される系での RESPA 法などは、変化の遅い力は長周期で計算し、変化の激しい力を短周期（毎回）計算するなどの手法が用いられている。
これは、一種の非同期化とみなせる。分子動力学

図１
3

RMC 法の概要図

学際大規模情報基盤共同利用・共同研究拠点 平成 27 年度共同研究 最終報告書 2016 年 5 月

M=256 ではメモリが不足し、M=128 とする必要があった。時間方向並列化の性能発揮には、結果、大規模なメモリ空間を必要とする点もポイントと考えられる。
予測計算パートと修正計算パートのオーバーラップによる高速化が理論的に考えられたため、改図２

時間方向並列化による経過時間短縮

良を検討した。修正計算の規模が、M から 2M に増加し、M の最適値やメモリ要求が大幅に変わる。

2014 年度「京」産業利用トライアルユース等で現在、利点が出るパラメータ領域を検討している。

高速化した SimpleRMC コードについて、時間方向さらに、上記の 1 次元散乱スペクトルに対する並列化法の並列計算特性評価の観点から、多数のRMC 法に加えて、（複数の実験研究者からの要請が計算ノードを利用した高速化効果（経過時間削減ある）2 次元散乱パターンに対する RMC 法につい効果）の評価した。
「京」産業利用トライアルユーて、新プログラムコードが完成したので、時間方スでは、規定のノード時間積内での解析実施を優向並列化を適用の準備検討を行った。H28 年度に、先し、経過時間削減の観点でのベンチマーク評価

2 次元散乱パターンに対する RMC 法を検討する課は行っていない。本研究課題では、並列性能評価

題の中で、時間方向並列かを含めたチューニングの観点でのベンチマーク計算や更なる高速化（時作業を実施していく予定である。

間軸並列度の増大と、Serial Correction 部の局所並列化等）を、東大 FX10 で行った。

(3)

約 3000 万粒子の系で、200 万回の RMC trials

拡散方程式・非圧縮流体・分子動力学計算における時間方向並列化を実施した経過時間を計測した。昨年度のコード

拡散方程式・非圧縮流体・分子動力学計算におの経過時間（表１）と、現在作業中のコードの結ける時間方向並列化を検討した。Parareal などに果（表２）を示す。M は時間方向の並列度である。

近い Serial Prediction-Parallel Correction の昨年度にくらべ、修正計算で局所並列化を強化し事例である。この節の事例は、時間発展問題でのM を増大させて、高速化することができた。

時間方向並列化の第１種効果を示す事例である。
拡散方程式の系では、以下の方針で、時間方向

表１ 昨年度のコードの経過時間
Nodes
M=326412864613.7
601.4
626.4
128516.4
496.0
513.0
256509.5
459.2
466.9
512538.9484.1474.4

並列化することで、経過時間の短縮ができた。
・試行は、Coarse Grid (例えば 2 倍の grid 間隔)での計算。
・３次元の場合、1/8(=1/2^3)の計算量で試行が完了。
・時間ステップは、4(=2^2)倍大きく取れる。

表２ 現在最適化作業中コードの経過時間
Nodes
M=128
256
51264567.8
577.3
582.0
128447.4
441.7
437.8
256389.4
387.3
392.3

二次元非圧縮流体(渦度・流れ関数表現)の系では、以下の方針で、時間方向並列化することで、経過時間の短縮ができた。
・速い計算(渦度移流方程式)と遅い計算(Poisson 方程式)の組み合わせ。
（図３）

また、実際に 3 億粒子の系での高速化検討も実・速い部分を試行、遅い部分を修正とする。

施した。M=256 や 512 が好ましい値となった。応さらに、Multi-grid 表現の導入でさらに収束性向

用先の「京」産業利用課題で、「京」を利用した所、上させる検討を行っている。
4学際大規模情報基盤共同利用・共同研究拠点 平成 27 年度共同研究 最終報告書 2016 年 5 月

析、プロトタイプの検討を行う前段階として、下記の３点について、現在の計算機・アーキテクチ
ャでの実効実利の見通しの議論を行った。実際、Particle-Particle 計算と Particle-Mesh 計算のsplit を前提とすると、精度による計算時間の違いや補正計算との負荷バランスも入り、煩雑になる。労力の割にメリットが小さいと判断した。
・クーロン力の 3d-FFT で大きな計算コストを要している。実用上クーロン力の計算は、RESPA法に基づいて、短距離相互作用の計算 4 ステッ
図３

二次元非圧縮流体の時間方向並列化

プあたりに、1 回の計算で済ましている。（時間方向並列化の文脈では、過去の位置情報を 4

分子動力学計算については、Identity Parareal

回使い回しているが、補正計算をしていない処の構成で、時間刻みと誤差の関係（図４）からも、方となっている。）本研究では、電荷密度の変十分実用になる[T. Takami and D. Fukudome, LNCS化などに対する補正計算を施すことにより、こ8384, pp.67-75 (2014).]と考えられる。の 4 回をより長時刻化する実装を検討する。
・Neighboring リストは、上記と同じように寿命を持った人為的なものである。Neighboring
リストの作成を、2 系列化するなど並列化増大で、力の計算とオーバーラップさせて高速化する方法の有効性を検討する。
・3d-FFT について、過去の差分とし単精度計算を用いることでの近似的高速化が可能である。

図４

時間刻みと誤差の関係

上記の他に、高見（副代表者）らによる時間方向並列化の検討に基づき、過去の座標の時系列デ

一方で、生体高分子の MD 計算では、高い精度のータからの予測・修正することで、力の計算のパMD 計算が必要とされない場合が多いため、この手イプライン並列化（複数の MD ステップの力を、同法を適用した場合のメリットの検討が必要である。 時並列的に計算する）により、演算量は増加する
現在その方向の検討について、理研 AICS 杉田チーが、並列性の増大で経過時間の短縮を目指した。

ムの GENESIS の公開コードをベースに検討を開始

現在、検討中である。

した。今後、さらに作業を行う予定である。

MPS 法の高速化においても、同様の手法の有効性を議論・検討した。引き続き検討中である。

(4)

生体高分子 MD 計算や MPS 法計算への適用

生体高分子 MD 法などの古典分子動力学法では、(5)

短距離力とクーロン力の計算が行われている。広

PPSC 型の成功事例としての大規模 RMC 法の成果とりまとめ作業

い意味での時間方向並列化の概念に基づいて、超PPSC 型の時間法並列化の成功を広く周知するに高並列計算機環境下で経過時間を短縮するアルゴは、応用事例を論文として成果確立させることがリズム案を検討した。平成２７年度は、アルゴリ重要である。平成２７年度の後半は、大規模 RMCズムの詳細開発、実用的な計算でのデータ特性分法の成果とりまとめ・論文化作業を実施した。論5

学際大規模情報基盤共同利用・共同研究拠点 平成 27 年度共同研究 最終報告書 2016 年 5 月

文化のプロダクトラン（3000 万粒子サイズ）は、末端変性 SBR（赤枠）と未変性 SBR（青枠）の場

京産業利用課題（hp140239, hp150064）の枠で、合で凝集状態が異なるため、凝集体の界面にあるJSR（株）冨永博士・曽根博士との共同研究として粒子の数や、界面粒子付近の空間の大きさが異な実施した。

ると考えられる。その１つの解析方法として、ボ本研究課題では、２つの異なるゴム材料におけロノイ分割したセルの体積のヒストグラムを調べるシリカナノ粒子の SPring-8 実験データ（X 線極る方法を考案した。ボロノイ分割には、VORO++パ小角散乱）について、400 万粒子サイズでの予備ッケージを用いた。図７に、ボロノイ体積のヒス的検討や、解析手法の準備研究を実施した。図５トグラムを示す。末端変性 SBR の場合には、大きには、RMC 解析で得た 400 万粒子の座標を一部切な体積の頻度が、未変性 SRB の場合に比べて、小り出した図（左図）と、実験で撮影した TEM（透さいことがわかる。これは、凝集体間のフリース過型電子顕微鏡）図とが、末端変性 SBR（赤枠）ペースが小さいことに対応すると考えられる。と未変性 SBR（青枠）の場合のそれぞれで類似している様子を見ることができた。なお、図６に示すように、スライスの厚さに応じ、見た目の印象が異なることから、解釈には注意が必要である。
しかしながら、末端変性 SBR（赤枠）と未変性 SBR（青枠）の場合で凝集状態に違いがあることはス
ライスの厚さに依らず、共通である。

図７

ボロノイ体積のヒストグラムの比較

本研究課題で得た 400 万粒子系で予備的な検討を踏まえて、京のプロダクトランの結果について種々の解析を実施し、論文としてとりまとめた。
現在、投稿中である。

6.

図５ TEM 像と、RMC 結果のスライス像の比較

今年度の進捗状況と今後の展望

時間方向並列化の概念整理や個別事例での検討は、概ね予定通りである。しかしながら、アウトカムの１つとして想定した分子動力学での時間方向並列化の効果発揮については、他の高速化手法の適用により、相対的に困難（コスト対効果での目減り）と判断した。
平成２７年８月に、偏微分方程式系の時間方向並列化で著名な Dr. Robert Sperk（ドイツユーリッヒ
図６

スライスの厚さの違いスパコンセンター）と、時間方向並列化に関する長時間ディスカッションを行い、時間方向並列化の類型について、整理することができた。
6

学際大規模情報基盤共同利用・共同研究拠点 平成 27 年度共同研究 最終報告書 2016 年 5 月

その結果をとして、PPSC 型の時間方向並列化のからの逆問題的構造推定への挑戦”, 第 2 回宣伝として、成功事例である大規模 RMC 法解析の大型実験施設とスーパーコンピュータとの連携結果を広く周知させる事とした。そのために、論利用シンポジウム, 秋葉原, (2015.9)

文として確立させるための作業を実施した。現在

・高見利也，“非線形・マルチスケールと時間並列化法”，研究会「非線形現象の捉え方」， FIT投稿中である。

セミナーハウス (2015.10)

今後、時間方向並列化の成功例や考え方（本研究課題の議論を通じて整理したもの）を広く成果

・ T. Takami ， “Future Prospects for the

発表するとともに、特に、PPSC 型の時間方向並列

Parallel-in-Time Algorithm”，第 19 回環瀬戸化のさらなる応用を広げていく考えである。

内応用数理部会シンポジウム，天瀬公民館(2016.1)

7.

研究成果リスト・萩田克美, “粗視化 MD によるフィラー充填高分(1) 学術論文

子系の２次元散乱パターン評価と可視化”, バーチャルリアリティ技術などを用いた可視化表

・K. Hagita, “Supercomputer aided analysis of

現法の研究会 (2016.1)

polymer nano-composites by X-ray scattering・萩田克美, “LAMMPS 粗視化 MD によるフィラー

analysis and large-scale coarse-grained MD

充填高分子系の２次元小角散乱パターン評価”,

simulations”, Journal of the Imaging Society

第 1 回「京」における材料系ワークショップ〜

of Japan, Vol., No. 6 570-577 (2015).

LAMMPS を中心として〜 (2016.2)
of・萩田克美, “大規模可視化と HPC の活用で促進

sequential reverse Monte Carlo analysis withさせる高分子ナノ複合材料研究”,大阪大学

prediction-correction computing ” , HPCI

Cyber HPC Symposium (2016.3)

・ K.

Hagita,“Time-parallelization

Research Report, Vol. 1, 9-15 (2016).
・ K. Hagita, T. Tominaga, and S. Sone,(5) その他（特許，プレス発表，著書等）“Large-scale reverse Monte Carlo analysis
for ultra-small-angle X-ray scattering data

・高見利也，“Parallel-in-Time 法の現状と今後，of silica nanoparticles in end-modified

数理構造保存を接点とした数学・HPC・実科学のrubbers”, submitted.

クロスオーバー(ディスカッションセッションでの情報提供)”，2015 年 11 月 24-25 日，電気通(2) 国際会議プロシーディングス

信大学 (東京都調布市)・理研にて、2015 年 8 月 20 日に、Dr. Robert Sperk(3) 国際会議発表に時間方向並列化のセミナーを実施した。時間方向並列化について、広く周知するとともに、関心(4) 国内会議発表を持つ研究領域を把握することができた。

・A. Naribayashi and T. Takami, “PerformanceMeasurement of Parareal-in-time Method by
Spatial Coarse Graining”, 情報技術，応用数学そして教育に関するワークショップ，津和野
町コミュニティセンター (2015.8)
・萩田克美, “モンテカルロ探索による散乱関数7