5 第一の問題への対策

銀河、銀河団のシミュレーションでは、ソフトニングが使えるためにタイムス ケールの問題は無い。このために微惑星とか球状星団にくらべれば話は簡単で あり、第一の問題、すなわち計算量が粒子数の2乗に比例して増えるという問 題だけ考えればいい。

とはいえ、これは大きな問題である。例えば普通の渦巻銀河を、２体緩和によっ て壊れてしまわないように表現するためには少なくとも$10^5$個程度の粒子が 必要である。このような銀河 1000 個から銀河団を作れば粒子数は 1億個とな り、1ステップ計算するのに $10^{17}$演算程度が必要になる。これは例えば 100 Gflops の超並列計算機で10日程度であり、 1万ステップ計算するのに300 年かかってしまう。

もう少し速く計算するためにひろく使われているのが Barnes-Hut アルゴリズ ムあるいはツリーコードと呼ばれる方法である。原理は簡単で、遠くのほうの 粒子はグループにまとめ、グループからの力は多重極展開（といっても普通に 使うのはせいぜい1次または2次、1次の展開は要するに重心で置き換えること） で計算する。

グループ分けは粒子毎に作っていてはしょうがないので、空間を階層的な立方 体からなるツリー構造に組織してあらかじめすべての階層で多重極展開を計算 しておく。ある粒子へのある立方体からの力は、それらが「十分に離れて」い れば多重極展開を計算して得られる。そうでなければ下の階層に再帰的に降り ていって、十分離れているとみなせるところまでいって計算する。系全体から の力も、単に系全体に対応する立方体からの力を計算することで求められる。

この方法では計算量が $O(N^2)$から $(ON\log N)$になる。もう少し（原理的 には）賢い方法として、 $O(N)$ になるアルゴリズムが知られている。この方 法では、力を及ぼすほうだけでなく受ける方もまとめて計算する。つまり、力 を及ぼすほうの回りで有効なポテンシャルの多重極展開を、受ける方の中心で のテイラー展開に変換し、そのテイラー展開を各粒子の位置で計算することで 力が求められる。

5.1 計算量の減少と計算効率の減少

$O(N\log N)$ の計算法は天文シミュレーションでは広く使われている。また パイプライン型ベクタプロセッサや並列計算機での実行もかなりよく研究され ている。これに対し$O(N)$のアルゴリズム (Fast Multipole Method, FMM)は まだ天文の問題に使えるような実用的な実装（実際に走るプログラム）を作っ た人がいないので、以下ツリーコードについてその実装上の問題点を簡単にま とめる。

ツリーコードでどのような問題が発生するかを考えるためには、比較の対象と して $O(N^2)$の直接計算アルゴリズムを考えることが有用である。これは、 ベクタプロセッサでは非常に高い効率で走る。またほとんどいかなる並列計算 機でも、マシンの理論ピークに近い性能を出すことができる。

もっともピーク性能を出すのが困難であると考えられる分散メモリ MIMD 型の 時にどのような計算法を使えるかを簡単に説明すると以下のようになる。

まず各プロセッサに（大体）同じ数の粒子を割り当てる。自分ので持っている 粒子同士の相互作用はそのまま計算すればいい。それ以外の他のところとの総 誤差用は、プロセッサを1次元的なリングとみなして、粒子をたらい回しにし て順次計算することができる。また、あるプロセッサのデータを全プロセッサ に効率良く放送できる場合にはその機能を使ったほうがプログラムが容易であ る。

計算速度に対し必要な通信速度は、プロセッサ数を$p$としてオーダとしては $p/N$ になるので、$p<<N$（普通成り立つ）では通信速度は問題にならない。 共有メモリならば話はもっと簡単になる。

さて、ツリーコードの場合、演算量は減るが計算速度（1秒に何回浮動小数点 演算をするかという意味での）は、普通のスカラープロセッサでも低下する。 これは、ある粒子への力を計算する時の配列のアクセスの仕方が不規則であり、 キャッシュミスの確率が高いことが大きな理由である。また、そもそも分岐自 体が多いことも性能低化の理由となる。

ベクタプロセッサではより困難な問題、すなわち再帰呼び出しがあるようなルー プはベクトル処理できないという問題が発生する。これは87年頃にいくつかの アプローチによって解決された。 （詳細は省く）

これらのアプローチは、アルゴリズムの変更による計算量の増大またはメモリ アクセスの不連続性による計算速度の低下というペナルティを持つものの、もっ とましな方法は知られていないということもあり現在も広く使われている。

共有メモリ MIMD 型の並列計算機の場合、再帰呼び出しも並列化可能で特に問 題なく実行可能となる。ただし、分散共有メモリ（仮想共有メモリ）の場合、 物理的には分散メモリなので後に述べる分散メモリのマシンと同じ配慮が必要 になる。

分散メモリでツリーコードを実行する方法については、Caltech のグループは 87年頃からいくつかの方法を試み、まあまあの結果を得ている。基本的なアイ ディアは、粒子を空間的に近いグループに分けるということである。分けるの には、それ自体にツリーによる空間分割を利用する方法や、適当に空間を半分 に切っていく方法などが知られている。