Past Event: Oden Institute Seminar

A massively parallel adaptive fast-multipole method on heterogeneous architectures

George Biros, School of Computational Science & Engineering, College of Computing Department of Biomedical Engineering, Georgia Tech

Abstract

The fast multipole method (FMM) is an efficient algorithm for what are known as N-body problems. FMM was designated one of the top 10 algorithms of the 20th century in the January/February 2000 issue of Computing in Science & Engineering. N-body problems arise in solid and fluid mechanics, plasma physics, materials science, geophysics, computational biology, electromagnetics, computer graphics, molecular dynamics and spatial statistics. I will present a new scalable algorithm and a new implementation of the kernel-independent fast multipole method, in which both distributed memory parallelism (via MPI) and shared memory/SIMD parallelism (via GPU acceleration) are employed to rapidly evaluate two-body non-oscillatory potentials. On traditional CPU-only systems, our implementation scales well up to 30 billion unknowns on 65K cores (AMD/Cray-based Kraken system at NICS) for highly non-uniform point distributions. On GPU-enabled systems, we achieve 30X speedup for problems of up to 256 million points on 256 GPUs (Lincoln at NCSA) over a comparable CPU-only based implementations. We achieve scalability to such extreme core counts by adopting a new approach to scalable MPI-based tree construction and partitioning, and a new hybercube-based reduction algorithm for the evaluation phase. For the sub-components of the evaluation phase (the direct- and approximate-interactions, the target evaluation, and the source-to-multipole translations), we use NVIDIA's CUDA framework for GPU acceleration to achieve excellent performance. Taken together, these components show promise for ultrascalable FMM in the exascale era and beyond. (First of Two Seminars) Biography: George Biros holds Associate Professor appointments with the School of Computational Science and Engineering at Georgia Tech and The Wallace H. Coulter Department of Biomedical Engineering at Georgia Tech and Emory University. Prior to joining Georgia Tech, he was an assistant professor in Mechanical Engineering and Applied Mechanics, Bioengineering, and Computer and Information Science at the University of Pennsylvania. He received his BS in Mechanical Engineering from Aristotle University Greece (1995), his MS in Biomedical Engineering from Carnegie Mellon (1996), and his PhD in Computational Science and Engineering also from Carnegie Mellon (2000). He was a postdoctoral associate at the Courant Institute from 2000 to 2003. Host: Omar Ghattas