A performance model for the communication in fast multipole methods on high-performance computing platforms

Abstract

Exascale systems are predicted to have approximately 1 billion cores, assuming gigahertz cores. Limitations on affordable network topologies for distributed memory systems of such massive scale bring new challenges to the currently dominant parallel programing model. Currently, there are many efforts to evaluate the hardware and software bottlenecks of exascale designs. It is therefore of interest to model application performance and to understand what changes need to be made to ensure extrapolated scalability. The fast multipole method (FMM) was originally developed for accelerating N-body problems in astrophysics and molecular dynamics but has recently been extended to a wider range of problems. Its high arithmetic intensity combined with its linear complexity and asynchronous communication patterns make it a promising algorithm for exascale systems. In this paper, we discuss the challenges for FMM on current parallel computers and future exascale architectures, with a focus on internode communication. We focus on the communication part only; the efficiency of the computational kernels are beyond the scope of the present study. We develop a performance model that considers the communication patterns of the FMM and observe a good match between our model and the actual communication time on four high-performance computing (HPC) systems, when latency, bandwidth, network topology, and multicore penalties are all taken into account. To our knowledge, this is the first formal characterization of internode communication in FMM that validates the model against actual measurements of communication time. The ultimate communication model is predictive in an absolute sense; however, on complex systems, this objective is often out of reach or of a difficulty out of proportion to its benefit when there exists a simpler model that is inexpensive and sufficient to guide coding decisions leading to improved scaling. The current model provides such guidance.

Keywords

fast multipole method communication complexity communication performance models

Get full access to this article

View all access options for this article.

References

Barnes

Hut

(1986) O(NlogN) force-calculation algorithm. Nature324: 446–449.

Beatson

Greengard

(1997) A short course on fast multipole methods. In: Light

Ainsworth

Levesley

. (eds) Wavelets, Multilevel Methods and Elliptic PDEs. Oxford: Oxford Science Publications, pp. 1–37.

Chandramowlishwaran

Madduri

Vuduc

(2010a) Diagnosis, tuning, and redesign for multicore performance: a case study of the fast multipole method. In: SC ‘10 Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis, New Orleans, LA, 2010. IEEE.

Chandramowlishwaran

Williams

Oliker

. (2010b) Optimizing and tuning the fast multipole method for state-of-the-art multicore architectures. In: Proceeding of the International Parallel Distributed Processing Symposium (IPDPS), Atlanta, GA, 2010, pp. 1–12. IEEE.

Cheng

Greengard

Rokhlin

(1999) A fast adaptive multipole algorithmin three dimensions. Journal of Computational Physics155(2): 468–498.

Clement

Quinn

(1995, April) Symbolic performance prediction of scalable parallel programs. In: Proceedings of the International Parallel Processing Symposium, Santa Barbra, CA, April 1995, pp. 635–639. IEEE.

DeRose

Reed

(1999) SvPablo: a multi-language, architecture-independent performance analysis system. In: Proceeding of the International Conference on Parallel Processing Aizu-Wakamatsu, Japan, August 1999, pp. 311–318. IEEE.

Dongarra

Sullivan

(2000) Guest editors introduction to the top 10 algorithms. Computing in Science and Engineering 2: 22–23.

Foster

(1995) Designing and Building Parallel Programs. Boston, MA: Addison-Wesley.

10.

Foster

Worley

(1997) Parallel algorithms for the spectral transform method. SIAM Journal on Scientific and Statistical Computing18(3): 806–837.

11.

Gahvari

Baker

Schulz

. (2011) Modeling the performance of an algebraic multigrid cycle on HPC platforms. In: ICS ‘11 Proceedings of the International Conference on Supercomputing, Tucson, Arizona, 2011, pp. 172–181. ACM.

12.

Gahvari

Gropp

Jordan

. (2014) Algebraic multigrid on a dragonfly network: first experience on a Cray XC30. In: Proceeding of the 5th International Workshop on Performance Modeling, Benchmarking and Simulation of High Performance Computer Systems (PMBS14), New Orleans, LA, November 2014. Springer.

13.

Gorn

Berkov

(2004) Adaptation and performance of the fast multipole method for dipolar systems. Journal of Magnetism and Magnetic Materials 272–276: 698–700.

14.

Greengard

Kropinski

Mayo

(1996) Integral equation methods for Stokes flow and isotropic elasticity in the plane. Journal of Computational Physics 125: 403–414.

15.

Greengard

Rokhlin

(1987) A fast algorithm for particle simulations. Journal of Computational Physics 73(2): 325–348.

16.

Greengard

Rokhlin

(1988) On the efficient implementation of the fast multipole algorithm. Research Report RR-602. New Haven: Yale University.

17.

Gropp

Kaushik

Keyes

. (1999, May) Toward realistic performance bounds for implicit CFD codes. In: Proceedings of Parallel CFD’99, Williamsburg, Virginia, May 1999, pp. 23–26. Elsevier.

18.

Ibeid

Yokota

Pestana

. (2016) Fast multipole preconditioners for sparse matrices arising from elliptic equations. Available at: http://arxiv.org/abs/1308.3339

19.

Jetley

Wesolowski

Gioachin

. (2010) Scaling hierarchical N-body simulations on GPU clusters. In: SC ‘10 Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis, New Orleans, LA, 2010, pp. 1–11. IEEE.

20.

Kerbyson

Alme

Hoisie

. (2001) Predictive performance and scalability modeling of a large-scale application. In: Proceedings of the 2001 ACM/IEEE Conference on Supercomputing, Denver, CO, 2011, pp. 1–12. IEEE.

21.

Lashuk

Chandramowlishwaran

Langston

. (2009) A massively parallel adaptive fast multipole method on heterogeneous architectures. In: Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, Portland, OR, 2009, pp. 1–12. IEEE.

22.

Lee

Malaya

Moser

(2013) Petascale direct numerical simulation of turbulent channel flow on up to 768k cores. In: Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, Denver, CO, 16–22 November 2013. IEEE.

23.

Luszczek

Dongarra

(2005, March) Introduction to the HPC challenge benchmark suite. Technical Report ICL-UT-05-01. Knoxville: University of Tennessee.

24.

Mendes

(1997, May) Performance scalability prediction on multicomputers. PhD Thesis, University of Illinois, Urbana-Champaign.

25.

Mendes

Reed

(1998, October) Integrated compilation and scalability analysis for parallel systems. In: International Conference on Parallel Architectures and Compilation Techniques (PACT’98), Paris, France, October 1998, pp. 385–392. IEEE.

26.

Perez-Jorda

Yang

(1998) On the scaling of multipole methods for particle-paticle interactions. Chemical Physics Letters282: 71–78.

27.

Rankin

(1999) Efficient parallel implementations of multipole based N-body algorithm. PhD Thesis, Duke University.

28.

Snavely

Wolter

Carrington

(2001) Modeling application performance by convolving machine signatures with application profiles. In Proceeding of the IEEE Workshop on Workload Characterization, Austin, TX, December 2001, pp. 149–156. IEEE.

29.

Van de Wiele

Olyslager

Dupre

(2008) Application of the fast multipole method for the evaluation of magneto-static fields in micromagnetic computations. Journal of Computational Physics227: 9913–9932.

30.

Wolf

Lele

(2011) Aeroacoustic integrals accelerated by fast multipole method. AIAA Journal49(7): 1466–1477.

31.

Worley

(2000) Performance evaluation of the IBM SP and the Compaq AlphaServer SC. In: Proceeding of the ACM International Conference of Supercomputing 2000, Santa Fe, New Mexico, pp. 235–244. ACM.

32.

Yokota

Turkiyyah

Keyes

(2014b) Communication complexity of the fast multipole method and its algebraic variants. Supercomputing Frontiers and Innovations1(1): 63–84.

33.

Zhao

J-S

Chew

W-C

(2000) Three-dimensional multilevel fast multipole algorithm from static to electrodynamic. Microwave and Optical Technology Letters26(1): 43–48.