Accelerating Johnson’s All-Pairs Shortest Paths Algorithm on GPU

2017-09-15
Taştan, Oğuzhan
Eryüksel, Oğul Can
Temizel, Alptekin
In graph theory finding shortest paths from each node to all the others is a common problem, known as all-pairs shortest path (APSP). However, it is challenging to process large graphs containing hundreds of thousands nodes and vertices in feasible time for real world applications. In this paper, we present a parallel implementation of Johnson's algorithm, which solves APSP problem on recent GPU architecture. Proposed algorithmic and architectural optimizations results in more than 4.5 times speed up of all-pairs shortest path calculation for large graphs with respect to the CPU. The source code is publicly available at

Suggestions

Efficient Surface Integral Equation Methods for the Analysis of Complex Metamaterial Structures
Yla-Oijala, Pasi; Ergül, Özgür Salih; Gurel, Levent; Taskinen, Matti (2009-03-27)
Two approaches, the multilevel fast multipole algorithm with sparse approximate inverse preconditioner and the surface equivalence principle algorithm, are applied to analyze complex three-dimensional metamaterial structures. The efficiency and performance of these methods are studied and discussed.
Frequent itemset minning with trie data structure and parallel execution with PVM
Guner, Levent; Karagöz, Pınar (2007-10-03)
Apriori algorithm is one of the basic algorithms introduced to solve the problem of frequent itemset mining (FIM). Since there is a new generation of affordable computers with parallel processing capability and it is easier to set up computer clusters, we can develop more efficient parallel FIM algorithms for these new systems. This paper investigates the use of trie data structure in parallel execution of Apriori algorithm, the potential problems during implementation, performance comparison of several par...
Two-dimensional unsteady Navier-Stokes solution method with moving overset grids
Tuncer, İsmail Hakkı (American Institute of Aeronautics and Astronautics (AIAA), 1997-03-01)
A simple numerical algorithm to localize intergrid boundary points and to interpolate unsteady solution variables across two-dimensional, structured overset grids is presented. Overset grids are allowed to move in time relative to each other. Intergrid boundary points are localized in a triangular stencil on the donor grid by a directional search algorithm. The final parameters of the search algorithm give the interpolation weights at the intergrid boundary point. Numerical results are presented for steady ...
Near-field performance analysis of locally-conformal perfectly matched absorbers via Monte Carlo simulations
Ozgun, Ozlem; Kuzuoğlu, Mustafa (2007-12-10)
In the numerical solution of some boundary value problems by the finite element method (FEM), the unbounded domain must be truncated by an artificial absorbing boundary or layer to have a bounded computational domain. The perfectly matched layer (PML) approach is based on the truncation of the computational domain by a reflectionless artificial layer which absorbs outgoing waves regardless of their frequency and angle of incidence. In this paper, we present the near-field numerical performance analysis of o...
A 2-0 navier-stokes solution method with overset moving grids
Tuncer, İsmail Hakkı (1996-01-01)
A simple, robust numerical algorithm to localize moving boundary points and to interpolate uniteady solution variables across 2-D, arbitrarily overset computational grids is presented. Overset grids are allowed to move in time relative to each other. The intergrid boundary points are localized in terms of three grid points on the donor grid by a directional search algorithm. The parameters of the search algorithm give the interpolation weights at the localized boundary point. The method is independent of nu...
Citation Formats
O. Taştan, O. C. Eryüksel, and A. Temizel, “Accelerating Johnson’s All-Pairs Shortest Paths Algorithm on GPU,” presented at the Accelerating Johnson’s All-Pairs Shortest Paths Algorithm on GPU”, Ulusal Yüksek Başarımlı Hesaplama Konferansı, Türkiye, 14 - 15 Eylül 2017, Türkiye, 2017, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/82701.