1.研究の背景

研究の背景としては、

超並列計算機の性能の向上
大規模なシミュレーションに対するニーズ

実際、現時点で最高性能を持つ計算機はベクトル型のスーパコンピュータから超並列計算機へと移行しつつあります。このような状況を背景に、今までスーパコンピュータで行なっていた大規模なシミュレーションを超並列計算機でも実行したいというニーズが高まってきています。

そこで、本研究では分子動力学法と呼ばれるシミュレーションを取り上げ、今まで実装が困難であると考えられていた物理条件下における並列実装を効果的に行なうための手法を提案します。

2.分子動力学法とは

簡潔に定義するとこのようになります。

多数の粒子から構成される仮想的な系を考え、与えられた粒子間相互作用を用いて各粒子に働く力を求め、運動方程式の時間に関する近似方程式により全粒子を一斉に運動させ、時間に対する粒子の位置と速度などの情報から種々のマクロ量を求める

粒子を対象としたシミュレーションは数多くありますが、分子動力学法は粒子1個1個の運動をトレースするという特徴から、時間に依存した構造、相転移、拡散の挙動などを扱うことが可能であるなど、広い分野で用いられています。

3.分子動力学法の処理

分子動力学法の処理の流れを示します。大まかに言うと、

シミュレーションの対象となる空間を考え
そこに粒子を配置し（通常数百から数万個）
各粒子に対して位置、速度などを設定する

計算機では連続時間を扱うことができないので、微小時間を1ステップとし
1ステップごとに粒子間の相互作用を計算し、次のステップの粒子の位置を決定

一般に計算量がかさむのは、どの粒子とどの粒子が相互作用するかを判定する部分にあると言われています。

本来、粒子間の相互作用は系の全ての粒子と計算することによって求めるべきですが、それではコストが粒子数の2乗に比例することになり大変です。

本研究では粒子間の相互作用はレナード・ジョーンズポテンシャルによって決定されるものとしています。このポテンシャルには粒子間の距離が増大すると相互作用の大きさが急激に0に近付くと言う性質があるため、上図のように切断距離という概念を導入し、それ以上の距離にある粒子間には力が働かないという近似を行ないます。

このことによって、各粒子は自分の近傍の粒子のみを相互対象にするという空間的な局所性が発生することになります。

4.並列環境

今回実装を行なったのは分散メモリ型の超並列計算機です。この種の計算機では、図のようにCPUとメモリが組になったPE(プロセッシングエレメント)が多数集まって一台の計算機を構成しています。各PEは自分のメモリのデータには高速にアクセスできますが、他のPEにあるデータへはアクセスはメッセージパッシングと呼ばれる通信を行ない、ローカルメモリにデータを持ってくる必要があるため、効率が低下します。そのため、各PEにおいて必要なデータはできるだけローカルメモリにおいておく、というデータ参照の局所性が必要となります。

5.従来手法

分子動力学法の空間的な局所性
分散メモリ型超並列計算機におけるメモリアクセスの局所性

並列分子動力学法に関する研究は数多くありますが、現時点においては、ほぼ全てといっていいほどの研究がセル分割法と呼ばれる手法をベースにしています。この手法について解説します。

まず、シミュレーション空間をメッシュ状に分割します。分割されたそれぞれの空間をセルと呼びます。セルのサイズを切断距離より大きくなるように取ることによって、粒子の相互作用を起こす可能性のある範囲は、自分の存在するセルとその近傍セルに限定されます。これは図のように2次元なら9セル、3次元なら 27セルということになります。

これをどう並列化するかということになりますが、図のようにまずシミュレーション空間をブロックと呼ばれる領域に分割し、このブロックをタスクの単位として各PEに割り振ってやります。各PEでは与えられたブロックに対してセル分割法を適用していきます。このように並列化すると先に挙げた2つの局所性をうまく結び付けることができるという利点はあるのですが、

ブロックの端のセルが隣のブロックのセルを必要とする
ブロック間を粒子が移動する

6.提案手法(1)

この手法は粒子登録法と呼ばれる手法です。

図を用いて説明します。

粒子の直径を1とし、切断距離を3とします。
シミュレーションの物理条件などから1ステップあたりの粒子の移動量を見積もった結果が0.1であったとします。
これらの結果から登録距離を5、登録ステップを10に設定します。

次にこの設定を適用していきます。このように設定し、中心の青い粒子が登録距離内にある赤い粒子を登録すると10ステップの間に青い粒子と相互作用する可能性のある粒子は赤い粒子に限られ、黄色い粒子が相互作用することはありません。それは10ステップ以内に緑の領域が点線にかかることはなく、また黄色い粒子が10ステップ以内に点線の内側に入ってくることがないからです。

この手法はこのまま並列化しても良い結果は得られません。それは空間的な局所性を考慮せずにタスクを割り振っているため、下図に見られるように近くにある粒子が異なるPEに割り振られる場合にPE間でデータの重複が起こるためです。

7.提案手法(2)

手法の説明をします。この手法は基本的には粒子登録法に基づいています。粒子登録法では登録ステップ毎に各粒子が独立に粒子登録と呼ばれる作業を行なっていましたが、提案手法ではグルーピングと呼ばれる作業を行ないます。グルーピングとは下図のようにお互いに登録距離内にある粒子が同じグループに属するように系を粒子のグループに分ける作業です。粒子登録とは粒子毎に登録テーブルを作成するのではなく、系全体を見て1つの統一的なグルーピングを行なうという点で異なっています。

8.評価

メッセージパッシングの発生を抑えられる
ロードバランスを取りやすい
データ並列がはかられる

お問い合わせ、質問、間違いの指摘などはこちらへ。

emaru@cc.hokudai.ac.jp

return