Abstract
The computer simulation of N-Body problems has a wide range of applications. It is known that simulations can take years to complete. This can be greatly improved by using efficient algorithms in force calculations and in applying the computing power of parallel computers to the problem. A tremendous amount of work has been devoted to parallelization of the fast multipole algorithm (FMA) which is one of the fastest algorithms in force calculations. However, most parallel implementations target a specific machine. We developed an efficient communication scheme for parallel FMA in a message passing environment and implemented it by using Message Passing Interface (MPI) which allows for greater portability. we also investigated the feasibility of running parallel FMA on a local area network (LAN) of workstations. Efficiencies of 62% and 82% were obtained on a 64-node SP2 and a LAN of workstations which were far superior than the reported peak efficiencies of 20% on a 32-node KSR-1 and 12% on a 256-node CM-2. An efficient massively parallel FMA algorithm is required when many processors present. We proposed an efficient group exchange scheme which substantially reduced the communication overhead. The force calculations of 1,000,000 particles can be done in 46 seconds using 128-node SP2 which is much faster than 180 seconds on a 256-node CM-2 and 1520 seconds on a 32-node KSR-1. A good partitioning technique is needed for highly non-uniform systems. Numerical results for weighted subtrees, a new partitioning technique proposed in this dissertation, showed that it greatly improved load balancing among processors.
Recommended Citation
Lu, Jui-Lin and Okunbor, Daniel, "Parallel Fast Multipole Algorithms for N-Body Simulations" (1996). Computer Science Technical Reports. 197.
https://scholarsmine.mst.edu/comsci_techreports/197
Department(s)
Computer Science
Report Number
CSc-96-09
Document Type
Technical Report
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 1996 University of Missouri - Rolla, All rights reserved
Publication Date
1996-12-01
Comments
The first Author is a Graduate Student
This report is substantially the text of the Ph.D. dissertation of the first author, completed December 1996.
Acknowledgements:
First, I thank Dr. Daniel Okunbor, my thesis advisor, for his guidance and encouragement to bring this work to completion. Secondly, I thank Dr. Bruce McMillin for bringing me into the wonderful world of high-performance scientific computing. I am also indebted to the other members of my advisory committee: Dr. George Zobrist, Dr. C. Y. Ho, and Dr. David Riggins.
Being a graduate student and a married man, financial support is critical. I thank the department for financially supporting me throughout my graduate study. It has been a pleasure to work with Dave Mentis, the departmental system manager. I am grateful for his friendship. Also, this work has been supported by National Science Foundation (Grant CCR-9408973) and Cornell Theory Center.
Very special thanks go to Mark Underwood for helping me collect part of the experimental results presented in this dissertation.
I am most grateful to my parents and my wife, Carol. Words cannot express how thankful I am for their love, support, understanding, and patience. Finally, thanks go to my two little devils - Ryan and Derek - for enriching my life.