MapReduceとN体問題

天体や分子動力学（MD）といったN体問題は計算量が多い問題としてよく知られている．近年流行しているHadoopのMapReduceの計算モデルがN体問題にも適用できると気づいたので，記録しておく．

N体問題とは，複数の質点が各々相互に作用して運動する系について解く問題である．この問題がやっかいなのは，位置と運動量が与えられた１個の質点に関して，次の瞬間の位置と運動量を求めるためには，他のN-1個の質点の位置を知る必要があることだ．１個の質点に関してN-1個の質点との作用を計算しなければならないので，全体ではN*(N-1)回の計算を行う必要がある．計算量の多い問題は，複数のマシンで並列に計算をしたいが，１ステップの計算に全ての質点の情報が必要なので，マシン間の通信が問題となる．こういったプログラミングをするのは非常に面倒だ．

最近にわかに注目を集めているHadoopはMapReduceという計算モデルに落とし込める計算に関しては，簡単に並列分散処理を行うプログラムを作ることができる．MapReduceは演算をMapとShuffleとReduceの３段階に分ける．Map，ReduceフェイズにもちいるMap関数とReduce関数はユーザーが独自にプログラミングできる．

Map関数は，KeyとValueのデータの組から，異なるKeyとValueの組のリストを作成する．

Map(<K1, V1>) -> list <K2, V2>

Shuffleのフェイズで同じKeyをもつ組が集められ，<K2, list V2 >の形になる．

Reduce関数で，Valueが一つの値になる．

Reduce(<K2, list V2>) –> <K2, V3>

この一連のMapReduceの流れをN体問題に置き換える．iが質点の番号，xi, piが質点iの位置と運動量である．

Map関数で，質点iの位置を全てのj = 0…N-1に対して割り当てる．

Map(<i, xi>)　-> list <j, xi> (0<j<N-1, j != i)

そうするとShuffleで全ての質点の位置が集まるので，Reduce関数で質点jの次のステップでの位置と運動量を求めることができる．

Reduce(<j, list xi>, xj, pj) –> <j, x’j, p’j>

Reduce関数の入力値には，当然質点jの現在の位置と運動量が必要とされる．

MapReduceジョブ１回が１ステップの計算となる．現実的には，HadoopではMap, ReduceでそれぞれN回JVMを立ち上げることになるので（JVMの再利用を行うならプロセス数分），1ステップで2N回JVMを起動して落とす．また，MapReduceの度にHDFSに書き込みが行われる．インメモリで計算すべきだが，HDFSのキャッシュ機能がどう働くかは分からない．MapReduceジョブはオーバーヘッドが大きいから，現実的ではないと思う．