RT info:eu-repo/semantics/conferenceObject
T1 A Tuned, Concurrent-Kernel Approach to Speed Up the APSP problem
A1 Ortega Arranz, Héctor
A1 Torres de la Sierra, Yuri
A1 González Escribano, Arturo
A1 Llanos Ferraris, Diego Rafael
K1 Informática
K1 APSP
K1 Concurrent-kernel
K1 Dijkstra
K1 GPU
K1 SSSP
K1 ThreadBlock size
K1 1203 Ciencia de Los Ordenadores
K1 3304 Tecnología de Los Ordenadores
AB The All-Pair Shortest-Path (APSP) problem is a well-known problem in graph theory whose objective is to find the shortest paths between any pair of nodes. Computing the distances from one source node to the rest and repeating this process for every node of the graph is an adequate solution for sparse graphs. During the last years the application of GPU devices have increased to accelerate this kind of problems. While the correctness of an NVIDIA CUDA implementation of this algorithm is easy to achieve, exploiting the GPU capabilities to obtain a good performance is a task for CUDA experienced programmers. A typical code tuning strategy is the selection of an appropriate threadBlocks size. Besides this, the concurrent deployment of several kernels that computes distances from different sources, also accelerates the execution times. In this paper we show that an adequate combination of both strategies represents a 11.5 % performance improvement between different, recommended CUDA configurations for the most costly kernel of the APSP problem.
PB Universidad de Salamanca
SN 978-84-616-2723-3
YR 2013
FD 2013
LK https://uvadoc.uva.es/handle/10324/71120
UL https://uvadoc.uva.es/handle/10324/71120
LA eng
NO Conference: Computational and Mathematical Methods in Science and Engineering, CMMSE 2013, Almería, Spain, ISBN 978-84-616-2723-3
NO Producción Científica
DS UVaDOC
RD 23-nov-2024