Oct 10 – 14, 2016
San Francisco Marriott Marquis
America/Los_Angeles timezone

Parallel metric trees for multi-billion body simulations

Oct 13, 2016, 3:30 PM
1h 15m
San Francisco Marriott Marquis

San Francisco Marriott Marquis

Poster Track 5: Software Development Posters B / Break


Peter Hobson (Brunel University (GB))


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

Primary author

Raul Cardoso Lopes (Brunel University (GB))


Peter Hobson (Brunel University (GB))

Presentation materials