ツリー法に関する論文のメモ。

Implications of hierarchical N-body methods for multiprocessor architectures by J.P.Singh, J.L.Hennessy & A.Guputa (1995)

doiのリンクはこれだが、検索するとPDFへのリンクがあった。

これは第一著者であるSinghの博士論文 “Parallel hierarchical N-body methods and their implications for multiprocessors” (Doctoral Dissertation, Stanford Univesity, 1993)を投稿したものと思われる。

すごく長い。以下、Section 9のメモを。

ここでは、SalmonのLETを使ったツリー法について色々と議論している。 論調は、LETとメッセージパッシングは使えねー、ってこと。 ただし、これは90年代前半の仕事なので、今とは対象としている問題のサイズが圧倒的に小さい。 この部分である意味かなりdisられている、Salmonの結果でも512プロセッサで10万粒子とからしい。

ちょっとおもしろかったので引用。

The difference is also demonstrated by our experience with having groups of graduate students implement the application on SAS-CC and message-passing machines, in a ten-week parallel programming project course at Stanford University. The SAS versions were produced very quickly, and yield very good speedups on the DASH multiprocessor. A message-passing version, however, is yet to be completed within the time allotted for the project

この部分の前に、Salmonの提案によるMPを使ったLETのツリー法は、 SASでの実装より数倍時間がかかったと書いてある(誰が？)。 その上で、ツリー法の実装をStanfordの大学院生に10週のプロジェクトとしてやらせてみたら、 共有メモリ(SAS-CC)とMessage-paasing(MP)の生産性の「違い」が示されたという。 SAS-CCとはshared address space-cache coherentの略。著者らはSAS-CCな計算を推しているのは言うまでもない。

まず、LETではメモリ使用量が非常に多くなる。 これはLETでは保守的にTreeを構築するので、 結果的には無駄な粒子とノードをLETに追加してしまうため。 よって、メモリ利用量も多いし、そのためのデータの交換に必要なデータ量も多いし、 それを実現するためのプログラミングも非常に複雑になる。ボロクソである。

一方SAS-CCでのツリーの実装では、データ交換は暗黙的のためプログラミングが簡単であり、 また、本当に必要最低限のデータ交換しか発生しない。 それは、SASでの実装では、LETを構築するのではなく、一つの共有されたtreeを実装するためで、 “Costzone”と呼ばれるロードバランスの手法と対になっている。 利用するメモリ量は、シリアルのコードとほとんど変わらない程度になる(はずである)。 ただし、彼らが議論している粒子数はたかだか16000粒子程度であり(Table 2参照)、 それのための必要なキャッシュ量は16KBとあり、現代には通用しない。 そもそも、現在でも128プロセッサを超えるような共有メモリ機を、 ハード的に実現するのは現実的には非常に難しい(性能が出ない)。

それでも、無理やり彼らの結論を敷衍すると、ハード的に共有メモリを実現することは難しくても、 N-bodyに専用の共有メモリフレームワークを改めて考えて、 まともに実装することには意味があるかもしれない、ということになる。 実際、彼らは仮想ポインタを利用したツリーの実装と、 ハッシュ値を使ったツリーの実装があり得ると提案していて、 これらはある種N-Bodyのための共有メモリフレームワークになっている。 脚注には、ハッシュ値を使ったツリーの実装を「この論文」を書いている時に、 Salmonらがおこなっているとある。 これはHashed Oct-treeと呼ばれるSalmonらの1993年の仕事である。