Skip navigation
Please use this identifier to cite or link to this item: http://uvadoc.uva.es/handle/10324/29105
Title: Comprehensive evaluation of a New GPU-based approach to the shortest-path problem
Authors: Ortega Arranz, Hector
Torres, Yuri
Llanos, Diego R.
González Escribano, Arturo
Issue Date: 2015
Publisher: Springer
Description: Producción Científica
Citation: International Journal of Parallel Programming, 44(3), pp 407-426, June 2016, ISSN 0885-7458
Abstract: The Single-Source Shortest Path (SSSP) problem arises in many different fields. In this paper, we present a GPU SSSP algorithm implementation. Our work significantly speeds up the computation of the SSSP, not only with respect to a CPU-based version, but also to other state-of-the-art GPU implementations based on Dijkstra. Both GPU implementations have been evaluated using the latest NVIDIA architectures. The graphs chosen as input sets vary in nature, size, and fan-out degree, in order to evaluate the behavior of the algorithms for different data classes. Additionally, we have enhanced our GPU algorithm implementation using two optimization techniques: The use of a proper choice of threadblock size; and the modification of the GPU L1 cache memory state of NVIDIA devices. These optimizations lead to performance improvements of up to 23% with respect to the non-optimized versions. In addition, we have made a platform comparison of several NVIDIA boards in order to distinguish which one is better for each class of graphs, depending on their features. Finally, we compare our results with an optimized sequential implementation of Dijkstra's algorithm included in the reference Boost library, obtaining an improvement ratio of up to 19x for some graph families, using less memory space.
Peer Review: SI
DOI: 10.1007/s10766-014-0347-0
Sponsor: Ministerio de Economía y Competitividad (Spain) and ERDF program of the European Union: CAPAP-H5 network (TIN2014-53522- REDT), MOGECOPP project (TIN2011-25639); Junta de Castilla y León (Spain): ATLAS project (VA172A12-2); and the COST Program Action IC1305: NESUS.
Publisher Version: http://link.springer.com/article/10.1007%2Fs10766-014-0347-0
Rights Owner: Springer
Language: spa
URI: http://uvadoc.uva.es/handle/10324/29105
Rights: info:eu-repo/semantics/restrictedAccess
Appears in Collections:DEP41 - Artículos de revista

Files in This Item:
File Description SizeFormat 
comprehensive.pdf228,93 kBAdobe PDFThumbnail
View/Open

This item is licensed under a Creative Commons License Creative Commons

Suggestions
University of Valladolid
Powered by MIT's. DSpace software, Version 5.5
UVa-STIC