./note080.html

ToC

79. Anton (2010/1/14, 2010/1/16 追記)

Anton は、 D. E. Shaw Research (DESRES) で開発した古典 MD 専用計算機です。相互作用計算のところは専用パイプラインでやるというもので、その辺は MD-GRAPE と同じですが、結構違うのは、MD-GRAPE は相互作用計算以外はホスト計算機でやるのに対して Anton ではそれもやるためのプログラム可能なプロセッサコアも集積したことと、近距離相互作用計算を並列、高速に行うための専用ネットワークも設計して、ネットワークインターフェースまでチップに集積したことです。

そこまでやった理由は、比較的少ない、 10 万程度の粒子数で非常に高速に計算したい、というものでした。その成果は結構なもので、 2 万原子程度だったと思いますが1ステップを数十マイクロ秒というところまで高速化しています。これは SC09 でゴードンベル賞を獲得しています。他の普通の並列計算機では、 BG/P とかでもまだ 1 ステップ1ms 程度なので、桁違いに速いわけです。これだけ速くした、特にレイテンシを切り詰められたのはプログラム可能なプロセッサとネットワークまで作りこんで、前回、前々回に書いたようなメモリ階層によるオーバーヘッドを避けたことが大きな理由ではありますが、それだけでもありません。

論文にあるように、相互作用の計算の並列化に新しい方法を使っています。これにより、並列度を上げた時の通信負荷を大きく下げて、現実的な配線本数でシステムを構築可能にしています。

どういう方法かを以下にまとめます。近距離相互作用なので限界距離があります。今、簡単のために並列化のための領域分割の領域の大きさ(一辺の長さ)がこの限界距離と同じだとします。そうすると、ある1つのプロセッサは、自分への力を計算するためには基本的に周りの個のプロセッサから粒子をもらってくる必要があります。作用・反作用の法則を使うなら、もらってくるのは半分の13 個のプロセッサからにして、計算した力を送り返すようにすれば通信量はあまり減らないですが計算量は半分になります。

今、もっとプロセッサを沢山使うために、領域のサイズを限界距離の 1/2 にしたとします。プロセッサ数は 8倍です。この時には、 26 個ではなくて 124 個のプロセッサからデータをもらってくることになります。1プロセッサのデータ量は 1/8 になるので、1ステップ当りの通信量は 0.6 倍くらい、計算量は 1/8 になるので、計算に対して通信を5倍くらい速くしないといけないことになります。これはつまり、プロセッサ数を領域数より多くするのは結構困難である、ということを意味します。

DESRES のグループは、「あるプロセッサが、もらってきた粒子同士の相互作用計算もできるものはする」というふうにすれば全部をもらってくる必要がなくなる、ということを使って通信量を減らしています。最初の、領域の一辺の長さが限界距離と同じ場合を考えます。自分の横にあるものは斜めも含めて8個もらってくるけど、上下は真上と真下の2個だけをもらってきたとしましょう。そうすると、例えば真上の領域の粒子と、自分と同じ高さの9個の領域との相互作用を自分が計算することができるので、これを計算して上のプロセッサに送り返すことができます。また、下のプロセッサについても、同様に下のプロセッサの領域と自分とその横の領域の相互作用を計算して、合計して下に送り返すことができます。そうすると、逆に上下のプロセッサがそれぞれの横の領域と自分の領域の相互作用を計算してくれるので、その分は計算しなくても合計された力が帰ってきます。横の領域は対称性を使えば4個だけでよいので、結局6個の領域から粒子をもらってくればすむはずです。元々の13個に比べると半分以下です。さらに、プロセッサ数を8倍にした時には、もらってくる必要がある領域は16個で、元々の124 個に比べると 1/8 になるわけです。

漸近的には、プロセッサ数の大きな極限で元々の方法だとプロセッサ当りの通信量がプロセッサ数に依存しなくなるのに対して、変更後の方法だとプロセッサ数の 1/3 乗に比例して小さくなります。いいかたを変えると、プロセッサ数の 2/3 乗に比例して必要な通信速度が大きくなるわけです。これはそんなに大きな効果ではないようにもみえますが、そうはいってもプロセッサ数が100倍違うと5倍違うわけで、結構大きな効果になります。

まあ、そうはいっても通信は多いわけで、もっと減らす方法はないか、というのが今日のテーマです。

遠距離力の場合には、粒子数を固定してプロセッサ数を4倍にした時に、通信速度への要求は2倍にしかならないアルゴリズムが知られています。プロセッサ数の平方根でしか必要な通信速度が増えないわけです。これは似鳥君によって実用的なものに改良され、 Cray XT4 で 1万コアを超えるようなところで6万粒子程度で性能がでることを実証しています。

この方法の原理は、プロセッサを2次元の格子状に配置して、粒子を1方向のプロセッサの数に分割し、プロセッサ (i,j) はグループ i とグループ j の粒子の相互作用を計算する、というふうにすることです。対称性を利用するなら 2次元格子状といってもたとえ下半分の3角形だけプロセッサをおけばよくて、最初に対角線の位置のプロセッサ (i,i) がグループ i の粒子をもっていれば、それぞれが縦及び横に放送し、それから全プロセッサが相互作用計算し、計算した相互作用をまた縦横に合計すれば対角線上のプロセッサに合計の力が求まります。

近距離力の場合に同じことをすることを考えてみます。最初の話のように限界距離の領域分割をしたとして、領域数の2乗のプロセッサを用意すれば遠距離力の場合と同じように近距離力も計算できますが、近距離力なので計算が発生するのは対角要素以外のところは縦、横ともに13個しか要素がない疎行列の形になります。なので、これらの、計算する必要があるところ以外のプロセッサを全部とっぱらってしまえば、必要なプロセッサ数は領域数の14倍ですみます。この時に、対角プロセッサの通信量を考えると、縦横に放送して結果が帰ってくるだけなので領域2個分ですんで、 Anton で使われているアルゴリズムに比べてさらに半分です。ここでは 14 倍の数のプロセッサを使っていますから、計算量は 1/14 になってしまっていて、 Anton でプロセッサ数を14 倍にすれば通信量はやはり 1/2 程度になってあまり変わらないともいえます。

ここで、領域の1辺を 1/2 にした場合を考えます。そうすると。通信量は 1/8 になるのに対して、計算量は、プロセッサ数が 64 倍になるので 1/64 です。従って、遠距離相互作用の場合と同じく、必要な通信速度がプロセッサ数の平方根でしか増大しない、ということになり、 Anton の方法の 2/3 乗に比べてさらに良いスケーリングとなっています。

(ここから2010/1/16 追記)

と、書いたら Anton 関係の論文をちゃんと読んでなかったのがばれて似鳥君の twitter で嘘なところを指摘されました。プロセッサ数を 8 倍でなくて16倍にすることを考えて、z方向だけ 1/4 にするんだそうで、そうすると通信量は 1/4 になってプロセッサ数の平方根になり、スケーリングは同じです。通信量がプロセッサ数の平方根というのはおそらく原理的な限界だと思うので、スケーリングという意味では同じです。

Anton の方法(NT法)で、単純な分割だと z 方向の通信が xy 方向よりも少ないので、z 方向を増やすことで xy 方向を減らすことができれば得になります。そのためには、領域を z 方向に薄いものにするべきなわけです。

というわけでスケーリングは同じなので、係数がどうか？というところです。どちらの方法でも、相互作用計算は基本的に全部、外からデータをもらってきて相互作用を計算し、結果を全部外に送り出す、ということになります。なので、通信量自体は同じです。実際に、それぞれが多数の領域を担当する(多数のプロセッサをもつ)複数のチップからなるシステムを考えた時にどうなるか、を考えても、まあ、あんまり変わらないです。

ハードウェア設計の手間は、 NT 法に比べて上の方法のほうが小さくはなります。通信が固定パターンでの放送と総和だけなので、それ専用のハードワイヤドなネットワークでよいからです。NT 法では、効率を上げる、つまり通信レイテンシを下げるには3次元トーラスの中で結構フレキシブルに通信制御を行う必要があります。かなり複雑なルーティングと、ルーティングしながらの加算を行うからです。

(ここまで2010/1/16 追記)

まあ、上に述べた方法の問題というか未解決なところは、ネットワークのトポロジ自体が領域サイズと限界距離の比に依存する、ということです。但し、限界距離は、分子間力なら定数ですが、クーロン力を PME (P3M) でやるなら変数であり、そっちのほうが限界距離が大きいのが普通なので、PM のほうを調整すればよい、というところはあります。

Anton ではの FFT を数マイクロ秒でやっています。1メッシュあたりの演算を 150 とすれば、これはテラフロップス程度で演算速度は大したことはありません。問題は例によって通信です。データ量は単精度とすれば128 kB ですが、これをマイクロ秒で通信するには 128GB/s の転送速度が必要なわけです。

まあ、これについては、今考えたのは前のステップとの密度分布の差分をとって、それを低精度の FFT で評価する、という方法です。1ステップが 1fs くらいだとすると、原子は 1 pm くらい動く計算です。これに対して、シミュレーションボックスは 10nm とかの程度ですから、程度、メッシュサイズに比べて 1/300 程度、カットオフ波長に比べると 1/1000 以下です。なので、まあ 10ビットも精度があればいいと思うと、固定小数点なら通信が 1/3 ですが、まだそれほど嬉しいわけではないですね。

密度場については時間の高階差分から予測子を構成するようにすれば、予測子の精度に応じて必要な FFT の精度を下げることができるはずです。例えば、 3ステップの予測子ならおそらく3桁程度の精度があるので、 FFT の精度はさらに3桁下げることができて 2-3 ビットですむはずです。こうなると、通信速度が 10GB/s、演算速度が 2-3bit の演算で Tops ということになって今の FPGA 1つでもできる程度です。丸め誤差の累積が気になりますが、これは時々諦めて高い精度で FFT をすればよいでしょう。

ここでの予測は FFT の必要精度を下げるだけなので、時間積分の安定性や長時間誤差には影響しないはずです。まあ、適当な実装を作って精度評価してみる必要はあります。

Previous ToC Next