TY - GEN

T1 - GPU Parallelization of All-Pairs-Shortest-Path Algorithm in Low-Degree Unweighted Regular Graph

AU - Kawano, Ryuta

AU - Matsutani, Hiroki

AU - Koibuchi, Michihiro

AU - Amano, Hideharu

N1 - Funding Information:
A part of this work was supported by JSPS KAKENHI Grant Number JP20K19788.
Publisher Copyright:
© 2021 ACM.

PY - 2021/6/20

Y1 - 2021/6/20

N2 - The design of the network topology of a large-scale parallel computer system can be represented as an order/degree problem in the graph theory. To solve the order/degree problem, we have to obtain all-pairs-shortest-path (APSP) for the graph. A conventional APSP algorithm for GPUs is based on the adjacency matrix (ADJ-APSP). When focusing on low-degree and unweighted graphs, most of the matrix elements are zero in the first few iterations of the algorithm. We will further speed up the APSP algorithm by treating the adjacency matrix as a sparse matrix in the first iterations of the algorithm. Evaluation results show that our proposed algorithm on a single GPU (NVIDIA GeForce RTX 3080) reduces the execution time by up to 32.7 % compared to the conventional algorithm.

AB - The design of the network topology of a large-scale parallel computer system can be represented as an order/degree problem in the graph theory. To solve the order/degree problem, we have to obtain all-pairs-shortest-path (APSP) for the graph. A conventional APSP algorithm for GPUs is based on the adjacency matrix (ADJ-APSP). When focusing on low-degree and unweighted graphs, most of the matrix elements are zero in the first few iterations of the algorithm. We will further speed up the APSP algorithm by treating the adjacency matrix as a sparse matrix in the first iterations of the algorithm. Evaluation results show that our proposed algorithm on a single GPU (NVIDIA GeForce RTX 3080) reduces the execution time by up to 32.7 % compared to the conventional algorithm.

KW - GPU

KW - network topology

KW - shortest path algorithm

UR - http://www.scopus.com/inward/record.url?scp=85118300826&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85118300826&partnerID=8YFLogxK

U2 - 10.1145/3468081.3471122

DO - 10.1145/3468081.3471122

M3 - Conference contribution

AN - SCOPUS:85118300826

T3 - ACM International Conference Proceeding Series

SP - 51

EP - 55

BT - Proceedings - 8th International Conference on Applied Computing and Information Technology, ACIT 2021

PB - Association for Computing Machinery

T2 - 8th International Conference on Applied Computing and Information Technology, ACIT 2021

Y2 - 20 June 2021 through 22 June 2021

ER -