Abstract


The Fast Multipole Method (FMM) is a robust technique for the rapid evaluation of the combined effect of pairwise interactions of n data sources. Parallel computation of the FMM is considered a challenging problem due to the dependence of the computation on the distribution of the data sources, usually resulting in dynamic data decomposition and load balancing problems. However, the algorithm we discuss does not require any dynamic data decomposition and load balancing steps. While parallel implementations of the uniform FMM are straight forward, the adaptive version complicates the task of obtaining effective parallel performance owing to the non-uniform nature of the problem domains to which it is applied.

Traditionally, Graphics Processing Units (GPUs) were designed for performing graphics specific computations. However, with rapid improvements in the performance and programmability, GPUs have fostered considerable interest in doing computations that go beyond computer graphics; general purpose computation on GPUs, or "GPGPU". One such GPGPU application is implementation of parallel adaptive FMM.

References


  1. S. Seal and S. Aluru. Spatial Domain Decomposition Methods in Parallel Scientific Computing. Book chapter
  2. B. Hariharan, S. Aluru, and B. Shanker. A Scalable Parallel Fast Multipole Method for Analysis of Scattering from Perfect Electrically Conducting Surfaces. Proc. Super- computing, page 42, 2002.
  3. R. Beatson and L. Greengard. A Short Course on Fast Multipole Methods.
  4. J. Carrier, L. Greengard, and V. Rokhlin. A Fast Adaptive Multipole Algorithm for Particle Simulations. SIAM Journal of Scientific and Statistical Computing, 9:669- 686, July 1988.
  5. B. Hariharan and S. Aluru. Efficient parallel algorithms and software for compressed octrees with apllications to hierarchical methods. Parallel Computing, 31:311-331, 2005.
  6. H. Sagan. Space Filling Curves. Springer-Verlag, 1994.
  7. M. Harris. Parallel Prefix Sum (Scan) with CUDA. http://developer.download.nvidia.com/compute/cuda/sdk/website/samples.html
  8. S. Lefebvre, S. Hornus, and F. Neyret. GPU Gems 2, Octree Textures on the GPU, pages 595-614. Addison Wesley, 2005.
  9. T. W. Christopher. Bitonic Sort Tutorial. http://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htm