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

Date

2017-09-15

Author

Taştan, Oğuzhan
Eryüksel, Oğul Can
Temizel, Alptekin

Metadata

Show full item record

Item Usage Stats

104
views

0
downloads

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

URI

https://hdl.handle.net/11511/82701

Conference Name

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

Collections

Graduate School of Informatics, Conference / Seminar

Suggestions

OpenMETU
Core

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.
The Floyd-Warshall all-pairs shortest paths algorithm for disconnected and very sparse graphs Toroslu, İsmail Hakkı (2023-01-01) The Floyd-Warshall algorithm is the most popular algorithm for determining the shortest paths between all vertex pairs in a graph. It is a very simple and an elegant algorithm. However, for graphs without any negative weighted edges, using Dijkstra's shortest path algorithm for every vertex as a source vertex to produce all-pairs shortest paths works significantly better than the Floyd-Warshall algorithm, especially for large graphs. Furthermore, for graphs with negative weighted edges, with no negative cyc...
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...

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.