Speakers
Dr
Ivan Reid
(Brunel University)Prof.
Peter Hobson
(Brunel University)Dr
Raul Lopes
(Brunel University)
Description
We consider standard parallel computing operations in the context
of algorithms for solving 3D graph problems, which have applications
in vertex finding in HEP. Exploiting GPU acceleration for tree accumulation and graph algorithms poses a challenge: GPUs offer extreme computational power and high memory access bandwidth, combined with a fine-grained parallelism that may not fit the irregular distribution of the linked representation of graph data structures. Assuming n vertices, the computation of minimum spanning trees for 2D graphs has efficient O(n log n) solutions through Delaunay triangulations; these, however, are not applicable for three or more dimensions. General minimum spanning tree computations are limited by lower bounds (Setti and Ramanchadran) demanding work
linear in the number of edges, quadratic in the number of vertices
for dense graphs. Practical efficient implementations for either the
Setti and Ramachadran or the Chazelle algorithms have been elusive,
and without parallel architecture formulations. We consider first the
efficiency of tree accumulation algorithms by Reif and Vishkin. We
use tree accumulations as a tool in 3D graph connected components
evaluation by combining them with the classical Shiloach-Vishkin algorithm and a randomized tree contraction phase. We also use tree
accumulation in an approximation algorithm for minimum spanning
trees, comparing it with parallel variations of the Boruvka minimum
spanning forest calculation.
Minimum spanning trees are at the core of the ZVMST vertex finding algorithm. We discuss implementations for graph connected
components and spanning trees calculation on GPU and multi-core
architectures.
Primary authors
Dr
Ivan Reid
(Brunel University)
Dr
Raul Lopes
(Brunel University)
Co-author
Prof.
Peter Hobson
(Brunel University)
