hhd0%gte.com@RELAY.CS.NET (Horace Dediu) (10/11/89)
Since my 26 Sep 89 posting asking for references to solutions to the n-body problem, I have received 7 replies as well as some requests for summaries. Here is a list of responses, followed by a list of addresses of the contribuotrs, followed by my own reference list. The result of this research will be an implementation of an n-body solver on a NCUBE 6 hypercube. Thanks to all who replied, I hope this will be of some use to someone beside myself. ******* Subject: Re: N-body problem on parallel machines Reply-to: aboulanger@bbn.com Here is some work that had an implementation on the CM: "On O(N) Algorithm for Three-dimensional N-body Simulations" Feng Zhao, MIT AI LAB TR 995 Cheers, Albert Boulanger BBN Systems & Technologies Corp. aboulanger@bbn.com ******* >From argosy!fyodor@decwrl.dec.com Wed Sep 27 00:14:25 1989 From: Chris Kuszmaul <argosy!fyodor@decwrl.dec.com> Message-Id: <8909262203.AA22260@idiot.MasPar.Com> Subject: Re: N-body problem on parallel machines Newsgroups: comp.parallel Organization: MasPar Computer Corporation, Santa Clara, CA "An O(N) Algorithm for Three-dimensional N-body Simulations" by Feng Zhao gives a good theoretical coverage of the latest ideas in N-body simulations in parallel. I worked for 2 years on a CM at the Perkin Elmer Advanced Developement Center, and my favorite hobby was n-body solvers. I discovered that, unfortunatly, the performance Zhao gets is not really too great. I would reccomend that, on an hypercube, you extract a ring topology, and just cycle the position and mass information around the ring. It's groody order N with N processors - but the constant is small enough that it is actually faster for 10,000 or so bodies than the order logN method. Another option is to use fast poisson solvers (FFT's) to get 0(logn) perofmance - which is, of course, the same order as you can get in the best theoretical solvers, but may also have a smaller time constant. It depends on what you want: Good order of growth performance for arbitrary mass distributions, good wall clock performance for a specific set of distributions, or something in between... CLK ******* >From panoff@hubcap.clemson.edu Tue Sep 26 17:17:26 1989 From: panoff@hubcap.clemson.edu (Robert M. Panoff) Sender: fpst@hubcap.clemson.edu The expert in this area is probably Paul Hertz at NRL in Washington. Try reaching him at hertz@cmf.nrl.navy.mil as he has working codes and has done some impressive timing tests (512 stars in each of 2 clusters colliding in "real" (as you watch it) time). Hope this helps. Also, check out the Fox/Walker/Johnson et al. book on solving problems on concurrent processors. rmp ******* >From tom@harvard.harvard.edu Wed Sep 27 10:35:50 1989 From: tom@harvard.harvard.edu Subject: Re: N-body on || machines; molecular dynamics, simulated annealing At Harvard, I know of two projects which are considering this problem (sort of) on the connection machine, and parallel computers in general. Martin Karplus' group in the Chemistry department has long been working with modeling the molecular dynamics of proteins and nucleic acids. This is basically a N-body problem, as each atom interacts with every other atom. Paul Bash, a post-doc, has a program (written in CM Fortran) running on the CM-2, with 15x Cray performance for a simulation with 4000 atoms, and 5x Cray performance when we only consider interactions with atoms within a certain cutoff range. In the group I am working with, we are in the beginning phases of work on a new project that would attempt to model and hopefully almost optimally map, a N-body simulation considering interactions only with a specified set of "neighbors" to parallel machines. Our first target is the CM-2, as we just received a little 4K processor version. This isn't a full n-body simulation, but I think it could apply to one, if we consider the "neighbors" to be all n bodies. We don't tout our project as simulating n-body interactions, but more formally, mapping general grid computations, where the computation depends on a set of "neighbors" (grid points close in communication, so as to speed up the computation), to various target parallel machines. Interestingly, our first example may be a simplified molecular dynamics simulation. I do not know if this is the information you want, but ask me for in- depth details if it is. I would appreciate it if you would send me any responses you receive to your query (that don't get posted to comp.parallel) to tom@endor.harvard.edu Thanks, Thomas Cheatham III ******* >From @boulder.colorado.edu:jakob@chapel.colorado.edu Wed Sep 27 11:35:47 1989 Return-Path: <jakob@chapel.Colorado.EDU> From: Jakob Ruediger <jakob@chapel.colorado.edu> Subject: N body problem I remember that at the Univ. of Erlangen-Nuernberg, West-Germany, someone was working on that problem for the distributed-shared memory DIRMU multiprocessor. Since this was two years ago, I don't remember names now, but if you are seriously interested, you should contact Prof. Haendler there, he'll probably be able to help you further: email: haendler@informatik.uni-erlangen.de Ruediger Jakob ******* >From gropp-bill@YALE.EDU Wed Sep 27 08:50:48 1989 Subject: Re: N-body problem on parallel machines Date: 27 Sep 89 12:50:48 GMT Sender: fpst@hubcap.clemson.edu In article <6588@hubcap.clemson.edu> hhd0@gte.com (Horace Dediu) writes: >Could someone mail or post references to work on solving the n-body problem >on parallel machines. I'm especially interested in implementation of >algorithms for hypercubes or the Connection Machine. Here are two that were implemented on an Encore multimax (in a TeX format) \refbody{L.~Greengard and W.~Gropp, {\it A Parallel Version of the Fast Multipole Method,} Technical Report YALE/DCS/RR-640, Yale University, Department of Computer Science, August\ 1988. } \refbody{L.~Greengard and W.~Gropp, {\it A Parallel Implementation of the Fast Multipole Method,} in "Parallel Processing for Scientific Computing," Ed.~G.~Rodrigue. SIAM, Philadelphia, 1989.} A hypercube implementation of these is fairly straightforward. I also have a vector version of the 2-d FMM. A version of a 3-d fast n-body algorithm has been done on the Connection Machine by F. Zhao. Both the 2-d and 3-d n-body algorithms are O((n/p)log n) on a machine with p processors, and are preferable to the obvious O(n*n/p) algorithm. Bill Gropp ******* >From @RELAY.CS.NET,@cunyvm.cuny.edu:jacob@techsel.bitnet Tue Oct 3 18:43:42 1989 From: Jacob Katzenelson <jacob%TECHSEL.BITNET@cunyvm.cuny.edu> Subject: n-body on parallel machimne Your e-mail inquiry has been forwarded to me. J. Katzenelson, "the computational structure of the n- body problem" SIAM J. on stat. and Sc comp. june or July 1989. I can send you a reprint but it will take longer than the library. Please let me know about similar work I have not referenced. Jacob ******* Here is a list of interested individuals who might be of help: aboulanger@bbn.com argosy!fyodor@decwrl.dec.com fpst@hubcap.clemson.edu tom@endor.harvard.edu jakob@chapel.colorado.edu markv@acm.princeton.edu gropp-bill@YALE.EDU mdm@alliant.alliant.com brianm%garfield.cs.wisc.edu@cs.wisc.edu jacob%TECHSEL.BITNET@cunyvm.cuny.edu To the references above I have added: J. Makino, On an O(NlogN) Algorithm for the Gravitational N-body Simulation and Its Vectorization, Japanese Supercomputing: architecture, algorithms and applications, pp. 84-96, springer-Verlag, New York, NY, USA Andrew A. Berlin, A Compilation Strategy for Numerical Programs Based on Partial Evaluation, Technical Report 1144, MIT Artificial Intelligence Lab (This is a thesis and has *Lisp source code for nbody on CM. You can contact Mr. Berlin at rm. 434, 545 Technology Square, Cambridge, MA 02139) Geraly Jay Sussman, Jack Wisdom, Numerical Evidence that the Motion of Pluto is Chaotic, AI Memo 1039, MIT AI Lab, April 27, 1988. (This has been published in Science magazine) James H. Applegate, Michael R. Douglas, Yeketa Gursel, Peter Hunter, Charles L .Seitz, Gerald Jay Sussman, A Digital Orrery, IEEE Transactions on Computers, Vol. C-34, no. 9, September 1985. (beautiful paper, a special-purpose computer used to model the solar system) Mike Warren, John Salmon, An O(NlogN) Hypercube N-body Integrator, ACM 1988 0-9791-278-0/88/0007/0971. I don't know what publication this paper is from.