An algebraic parallel treecode in arbitrary dimensions

William B. March, Bo Xiao, Chenhan D. Yu, George Biros
Institute for Computational Engineering and Sciences, The University of Texas at Austin, Austin, TX 78712
29st IEEE International Parallel & Distributed Processing Symposium (IPDPS15), 2015


   title={An algebraic parallel treecode in arbitrary dimensions},

   author={March, William B and Xiao, Bo and Chenhan, D Yu and Biros, George},

   booktitle={29th IEEE International Parallel and Distributed Processing Symposium},



Download Download (PDF)   View View   Source Source   



We present a parallel treecode for fast kernel summation in high dimensions – a common problem in data analysis and computational statistics. Fast kernel summations can be viewed as approximation schemes for dense kernel matrices. Treecode algorithms (or simply treecodes) construct low-rank approximations of certain off-diagonal blocks of the kernel matrix. These blocks are identified with the help of spatial data structures, typically trees. There is extensive work on treecodes and their parallelization for kernel summations in three dimensions, but there is little work on high-dimensional problems. Recently, we introduced a novel treecode, ASKIT, which resolves most of the shortcomings of existing methods. We introduce novel parallel algorithms for ASKIT, derive complexity estimates, and demonstrate scalability on synthetic, scientific, and image datasets. In particular, we introduce a local essential tree construction that extends to arbitrary dimensions in a scalable manner. We introduce data transformations for memory locality and use GPU acceleration. We report results on the "Maverick" and "Stampede" systems at the Texas Advanced Computing Center. Our largest computations involve two billion points in 64 dimensions on 32,768 x86 cores and 8 million points in 784 dimensions on 16,384 x86 cores.
Rating: 2.5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: