6 第二の問題への対策

6.1 独立時間刻み

第二の問題、すなわちタイムスケールの問題には、粒子毎に別々の時間刻みを 与えることで対応することになる。この場合、時間積分は 「次の時刻」すなわち現在の時刻と時間刻みの和がもっとも短い粒子を選び、 それの軌道を積分してその時刻と時間刻みを改めて計算し、最初に戻って次の 粒子を選ぶという具合にすすむことになる。

この方法の場合、ベクタプロセッサでの実行は容易である。というのは、ベク トルの総和というのはすべての現存のベクタプロセッサで効率良く実行できる 処理であるからである。

並列計算機の場合、一旦各プロセッサで自分の分を計算し、その総和をとって から軌道積分に進むということになる。これは $p<<N$ であれば不可能ではな いが、時間刻み共通の場合に比べて難しい。これは、一回の通信でのデータ転 送量が小さいため、ピーク転送速度ではなくメッセージレイテンシ（最初のデー タを送り出してからつくまでの時間）が問題になるからである。実際に、必ず しも高い性能が得られないことがわかっている。

6.2 2重時間刻み

「独立時間刻み」法の改良として、「独立2重時間刻み」あるいは neighbor scheme といわれる方法がある。これは、ある粒子への力をその回り の粒子からの分と遠くからの分に分割し、遠くからの分は長い時間刻みで積分 するという方法である。理論的には、単純な方法に比べた時の計算量の減少が $N^{1/4}$ に比例するということになっている。

この方法の並列化は困難である。近くの粒子からの力の計算ではメモリアク セスが不規則でしかもループ長が短くなるので、ベクタプロセッサでも効率が 大きく低下することが知られている。

6.3 ブロック時間刻み

並列計算機上で効率をあげるには、一度に1つの粒子しか動かさないのではな く、なるべくたくさんの粒子を並列に積分できることが望ましい。これは時間 刻みを2のベキ乗に離散化することで可能になる。このようにすれば、ある粒 子が積分される時にそれと同じかあるいは短い時間刻みを持つ粒子は並列に積 分して良く、並列度は劇的に向上できる（理論的には $N^{2/3}$ と見積もら れている）。現在までの分散メモリ型並列計算機への独立時間刻み法の実装は、 すべてこの方法（ブロック時間刻み）によっている。