Paper Info
Title
Calculating average shortest path length using Compute Unified Design Architecture (CUDA)
Abstract
Large graphs with millions and even billions of vertices are found in many real-life network analysis, the processing of which is challenging. One of the toughest tasks is computing the average shortest path length in a large network, which requires a lot of memory and processing time while calculating many independent paths. Hence, this task becomes a good candidate for parallelizing. The idea of using graphics processing units (GPUs) for general purpose computing is not new, and with recent increases in performances and memory capacity, they make a perfect candidate for working with graphs. We will explore how the Dijkstra's algorithm can be used to calculate the average shortest-path length, and how it can be used in a massively parallelized system and compare the performance gains and drawbacks.
Year
DOI
Venue
2019
10.23919/MIPRO.2019.8757008
2019 42nd International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO)
Keywords
Field
DocType
graph,path length,CUDA
Graphics,Graph,Shortest path problem,Path length,Vertex (geometry),Computer science,CUDA,Parallel computing,Computer network,Network analysis,Dijkstra's algorithm
Conference
ISBN
Citations 
PageRank 
978-1-5386-9296-7
0
0.34
References 
Authors
4
3
Name
Order
Citations
PageRank
Stefan Petrushevski100.34
Marjan Gusev229268.27
Vladimir Zdraveski374.69