Accelerating BFS shortest paths calculations using CUDA for Internet topology measurements

Eric Klukovich, Mehmet Hadi Gunes, Lee Barford, Frederick C. Harris

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    1 Scopus citations

    Abstract

    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.

    Original languageEnglish
    Title of host publication2016 International Conference on High Performance Computing and Simulation, HPCS 2016
    EditorsVesna Zeljkovic, Waleed W. Smari
    Pages66-73
    Number of pages8
    ISBN (Electronic)9781509020881
    DOIs
    StatePublished - 13 Sep 2016
    Event14th International Conference on High Performance Computing and Simulation, HPCS 2016 - Innsbruck, Austria
    Duration: 18 Jul 201622 Jul 2016

    Publication series

    Name2016 International Conference on High Performance Computing and Simulation, HPCS 2016

    Conference

    Conference14th International Conference on High Performance Computing and Simulation, HPCS 2016
    Country/TerritoryAustria
    CityInnsbruck
    Period18/07/1622/07/16

    Fingerprint

    Dive into the research topics of 'Accelerating BFS shortest paths calculations using CUDA for Internet topology measurements'. Together they form a unique fingerprint.

    Cite this