Lab Home | Phone | Search
Center for Nonlinear Studies  Center for Nonlinear Studies
 Home 
 People 
 Current 
 Affiliates 
 Visitors 
 Students 
 Research 
 ICAM-LANL 
 Publications 
 Conferences 
 Workshops 
 Sponsorship 
 Talks 
 Colloquia 
 Colloquia Archive 
 Seminars 
 Postdoc Seminars Archive 
 Quantum Lunch 
 Quantum Lunch Archive 
 CMS Colloquia 
 Q-Mat Seminars 
 Q-Mat Seminars Archive 
 P/T Colloquia 
 Archive 
 Kac Lectures 
 Kac Fellows 
 Dist. Quant. Lecture 
 Ulam Scholar 
 Colloquia 
 
 Jobs 
 Postdocs 
 CNLS Fellowship Application 
 Students 
 Student Program 
 Visitors 
 Description 
 Past Visitors 
 Services 
 General 
 
 History of CNLS 
 
 Maps, Directions 
 CNLS Office 
 T-Division 
 LANL 
 
Tuesday, June 25, 2013
3:00 PM - 4:00 PM
CNLS Conference Room (TA-3, Bldg 1690)

Seminar

Shortest Path Computation on Multi-GPU Platforms

Guillaume Chapuis
University of Rennes

The All-Pair Shortest Path (APSP) problem asks to compute the shortest paths or distances between all pairs of nodes of a graph. Once computed, APSP distances allows linear computations of various other graph measures such as the betweenness centrality of the nodes of a network and the radius and diameter of the graph. These measures have applications in domains such as social network analysis, protein-protein interactions, and road network problems.

Unfortunately, the APSP problem is hard to efficiently implement on the GPU platform. Efficient sequential algorithms have number of operations roughly quadratic to the number of the nodes of the graph, but their data communication structure is unsuitable for the GPU architecture, while the algorithms that have nice structures run in cubic time.

We propose a novel algorithm for computing APSP and its efficient distributed GPU implementation. For graphs with good community structure, the total number of operations of our algorithm is almost optimal (close to quadratic), but it has a structure allowing both high parallelism and a regular data communication pattern suitable for GPU. Our implementation is geared towards solving APSP for large graphs. So far, instances of up to 512k vertices (corresponding to computing more than 200 billion shortest paths) have been solved in less than 6 minutes.

Host: Hristo Djidjev