TY - GEN
T1 - Accelerating BFS shortest paths calculations using CUDA for Internet topology measurements
AU - Klukovich, Eric
AU - Hadi Gunes, Mehmet
AU - Barford, Lee
AU - Harris, Frederick C.
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/9/13
Y1 - 2016/9/13
N2 - Within the last decade, the number of devices connected to the Internet has seen immense growth and it has grown to be a large and complex network. To analyze this network, Internet topology analysis has become a popular research area and the analysis can be computationally expensive for such a large scale network. In this paper, we have implemented algorithms to find the shortest paths on large scale Internet topology graphs based on real topology data using breadth-first search. The algorithms have been implemented on graphical processing units (GPUs) using the CUDA platform. We performed our performance measurements on graph sizes ranging from 1,100 to 6.8 million nodes and achieved a maximum speed up of 47x on a single GPU and 124x speed up using 8 GPUs for 100 different starting points.
AB - Within the last decade, the number of devices connected to the Internet has seen immense growth and it has grown to be a large and complex network. To analyze this network, Internet topology analysis has become a popular research area and the analysis can be computationally expensive for such a large scale network. In this paper, we have implemented algorithms to find the shortest paths on large scale Internet topology graphs based on real topology data using breadth-first search. The algorithms have been implemented on graphical processing units (GPUs) using the CUDA platform. We performed our performance measurements on graph sizes ranging from 1,100 to 6.8 million nodes and achieved a maximum speed up of 47x on a single GPU and 124x speed up using 8 GPUs for 100 different starting points.
UR - http://www.scopus.com/inward/record.url?scp=84991608350&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84991608350&partnerID=8YFLogxK
U2 - 10.1109/HPCSim.2016.7568317
DO - 10.1109/HPCSim.2016.7568317
M3 - Conference contribution
AN - SCOPUS:84991608350
T3 - 2016 International Conference on High Performance Computing and Simulation, HPCS 2016
SP - 66
EP - 73
BT - 2016 International Conference on High Performance Computing and Simulation, HPCS 2016
A2 - Zeljkovic, Vesna
A2 - Smari, Waleed W.
T2 - 14th International Conference on High Performance Computing and Simulation, HPCS 2016
Y2 - 18 July 2016 through 22 July 2016
ER -