Newsgroups: comp.parallel From: G Pringle Subject: Thesis on O(N) N-body solver for vortex methods in CFD. Keywords: N-body, FMM, vortex methods, CFD, parallel computers. Organization: Edinburgh University Date: Mon, 27 Jun 1994 13:42:57 GMT Message-ID: Hi, I have recently completed my thesis, which I think may be of interest. Briefly stated, I have investigated the Greengard_Rokhlin O(N) Fast N-body solver, in both 2 and 3 dimenaions, and I have ported them onto a MIMD computer. The 3D code was then employed to speed up a vortex simulation of a turbulent fluid flow problem (non-viscous, incompressible). Attention has been paid to the error which arises from the Greengard-Rokhlin solver, and the exectution time has been reduced, by various 'tricks', without compromising the prescribed tolerance. If you are interested, please e-mail me and I will post a postscript version to you. If you have any comments/questions about the text, I would be happy to communicate on this subject. I've included the abstract below. Cheers, Gavin P.S. If you have any trouble with THIS email address, please use gavin@uk.ac.edinburgh.festival --------------------------------------------------------------------------- Numerical Study of Three-Dimensional Flow using Fast Parallel Particle Algorithms. Gavin J. Pringle. Maths Dept., Napier University, Edinburgh, EH14 1DJ, SCOTLAND. Tel: +44 31 455 4631 email: gavin@uk.ac.edinburgh.festival Doctor of Philosophy. Abstract Numerical studies of turbulent flows have always been prone to crude approximations due to the limitations in computing power. With the advent of supercomputers, new turbulence models and fast particle algorithms, more highly resolved models can now be computed. Vortex Methods are grid-free and so avoid a number of shortcomings of grid-basedbased methods for solving turbulent fluid flow equations; these include such problems as poor resolution and numerical diffusion. In these methods, the continuum vorticity field is discretised into a collection of Lagrangian elements, known as vortex elements, which are free to move in the flow field they collectively induce. The vortex element interaction constitutes an $N$-body problem, which may be calculated by a direct pairwise summation method, in a time proportional to $N^2$. This time complexity may be reduced by use of fast particle algorithms. The most common algorithms are known as the $N$-body Treecodes and have a hierarchical structure. An in-depth investigation of one high performance Treecode, namely the Fast Multipole Method, or FMM, is conducted for uniform distributions in both 2 and 3 dimensions. This method has a complexity of $O(N)$ and is most suited to $N$-body simulations characterised by large $N$ anda high precision. The precision of the FMM may be known {\it a priori}, and a tolerance parameter is determined in terms of this this prescribed precision. The most commonly used expression to determine this tolerance parameter is shownto be too conservative, which results in an excess of computational effort. Thus, through an investigation of the error-bounds, the value of the tolerance parameter may be reduced, and hence the time for execution may be reduced without compromising the required precision. Other methods of optimising the FMM parameters are also discussed. It is found that a number of rough approximations, such as `super-nodes', have been introduced to the FMM which, under certain conditions, reduce the time for execution at the cost of losing control over the accuracy. A parallel version of the FMM in both 2 and 3 dimensions is implemented on the Meiko Computer Surface, CS-1, which is a Multiple-Instruction-Multiple-Data, or MIMD, distributed memory parallel computer using a Single-Program-Multiple-Data,or SPMD, local domain decomposition, explicit message-passing paradigm. Two scalable communication algorithms are required; a systolic loop and nearest- neighbour processor inter-communication. The latter algorithm exhibits poor load balancing, as the boundary processors will lie idle for some of the time. The `break-even' point between the FMM and the `direct' method, i.e. the point the two methods take the same amount of time to execute, is $N \approx 180$ and $N \approx 5000$ particles for the sequential 2D and 3D respectively. For the parallel versions the corresponding points are $N \approx 70$ for 2D and $N \approx 1000$ for 3D. In the context of one particular Vortex Method it is shown how the FMM can be embedded within a simulation of a 3-dimensional vortex ring. This simulation dictates a highly non-uniform distribution of vortex elements, thus this parallel version of the FMM exhibits poor load balancing.