SCALLOP: A Highly Scalable Parallel Poisson Solver in Three Dimensions

ABSTRACT

SCALLOP is a highly scalable solver and library for elliptic partial differential equations on regular block-structured domains. SCALLOP avoids high communication overheads algorithmically by taking advantage of the locality properties inherent to solutions to elliptic PDEs. Communication costs are small, on the order of a few percent of the total running time on up to 1024 processors of NPACI's and NERSC's IBM Power-3 SP sytems. SCALLOP trades off numerical overheads against communication. These numerical overheads are independent of the number of processors for a wide range of problem sizes. SCALLOP is implicitly designed for infinite domain (free space) boundary conditions, but the algorithm can be reformulated to accommodate other boundary conditions. The SCALLOP library is built on top of the KeLP programming system and runs on a variety of platforms.

REFERENCES

• 1: Christopher R Anderson, A method of local corrections for computing the velocity field due to a distribution of vortex blobs, Journal of Computational Physics, v.62 n.1, p.111-123, Jan. 1986 [doi>10.1016/0021-9991(86)90102-6]
• 2: Scott B. Baden , Stephen J. Fink, Communication overlap in multi-tier parallel algorithms, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-20, November 07-13, 1998, San Jose, CA
• 3: Scott B. Baden , Stephen J. Fink, A Programming Methodology for Dual-Tier Multicomputers, IEEE Transactions on Software Engineering, v.26 n.3, p.212-226, March 2000 [doi>10.1109/32.842948]
• 4: Scott B. Baden , Daniel Shalit, Performance Tradeoffs in Multi-tier Formulation of a Finite Difference Method, Proceedings of the International Conference on Computational Sciences-Part I, p.785-794, May 28-30, 2001
• 5: Gregory Ted Balls , Phillip Colella, A finite-difference domain decomposition method using local corrections for the solution of poisson's equation, University of California, Berkeley, 1999
• 6: Gregory T. Balls , Phillip Colella, A finite difference domain decomposition method using local corrections for the solution of Poisson's equation, Journal of Computational Physics, v.180 n.1, p.25-53, July 20, 2002 [doi>10.1006/jcph.2002.7068]
• 7: Randolph E. Bank , Michael Holst, A New Paradigm for Parallel Adaptive Meshing Algorithms, SIAM Journal on Scientific Computing, v.22 n.4, p.1411-1443, 2000 [doi>10.1137/S1064827599353701]
• 8: M. J. Berger , P. Colella, Local adaptive mesh refinement for shock hydrodynamics, Journal of Computational Physics, v.82 n.1, p.64-84, May 1989 [doi>10.1016/0021-9991(89)90035-1]
• 9: [9] W. L. Briggs. A Multigrid Tutorial. SIAM, 1987.
• 10: Stephen J. Fink , Scott B. Baden , Scott R. Kohn, Efficient run-time support for irregular block-structured applications, Journal of Parallel and Distributed Computing, v.50 n.1-2, p.61-82, April 1998 [doi>10.1006/jpdc.1998.1437]
• 11: [11] M. Frigo and S. G. Johnson. FFTW: An adaptive software architecture for the FFT. In ICASSP Conference Proceedings, volume 3, pages 1381-1384. ICASSP, 1998.
• 12: L. Greengard , V. Rokhlin, A fast algorithm for particle simulations, Journal of Computational Physics, v.73 n.2, p.325-348, December 1, 1987 [doi>10.1016/0021-9991(87)90140-9]
• 13: [13] M. Holst. Applications of domain decomposition and partition of unity methods in physics and geometry. In I. Herrera, D. E. Keyes, O. B. Widlund, and R. Yates, editors, Proceedings of the Fourteenth International Conference on Domain Decomposition Methods, January 2002.
• 14: [14] R. A. James. The solution of Poisson's equation for isolated source distributions. Journal of Computational Physics, 25(2):71-93, October 1977.
• 15: [15] K. Lackner. Computation of ideal MHD equilibria. Computer Physics Communications, 12(1):33-44, 1976.
• 16: Barry F. Smith , Olof B. Widlund, A domain decomposition algorithm using a hierarchical basis, SIAM Journal on Scientific and Statistical Computing, v.11 n.6, p.1212-1220, November 1990 [doi>10.1137/0911069]
• 17: [17] A. Sohn and R. Biswas. Communication studies of DMP and SMP machines. Technical Report NAS-97-004, NAS, 1997.
• 18: Arun K. Somani , Allen M. Sansano, Minimizing overhead in parallel algorithms through overlapping communication/computation, Institute for Computer Applications in Science and Engineering (ICASE), 1997

INDEX TERMS

Keywords:
computation-intensive applications, parallel and distributedalgorithms, program optimization and performance programming