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 -