Speaker
Description
This work combines metric and parallel computing on both multi-GPU and distributed memory architectures when applied to
multi-million or even billion bodies simulations.
Metric trees are data structures for indexing multidimensional sets of points in arbitrary metric spaces. First proposed by Jeffrey
K. Uhlmann [1], as a structure to efficiently solve neighbourhood queries, they have been considered, for example, by Sergey Brin
for indexing very large databases.
We propose a parallel algorithm for the construction of metric trees that preserves the theoretical work bound of order n log(n), for indexing a set of n points.
We discuss possible applications of the parallel algorithms obtained in the context of probabilistic Hough Transform applications
for line detection and multi billion body simulations.
N-body simulations are of particular interest for beam dynamics simulations in the context of particle accelerator design.
We use a parallel metric tree and a variation of a parallel Fast Multipole Method and evaluate its efficiency in
a multi-billion points simulation on three different architectures: a multi-GPU cluster; a 256 core Infiniband,
distributed memory cluster; and a multi-core architecture. Of particular interest is the evaluation of effects of locality on
communication and performance overall.
[1] Uhlmann, Jeffrey (1991). "Satisfying General Proximity/Similarity Queries with Metric Trees". Information Processing Letters 40 pp175-179 doi:10.1016/0020-0190(91)90074-r.
[2] Brin, Sergey (1995). "Near Neighbor Search in Large Metric Spaces".
VLDB '95 Proceedings of the 21th International Conference on Very Large Data Bases 574-584 Morgan Kaufmann Publishers Inc. San Francisco USA
| Primary Keyword (Mandatory) | Algorithms |
|---|---|
| Secondary Keyword (Optional) | Parallelizarion |
