GPU-accelerated backtracking using CUDA dynamic parallelism - Archive ouverte HAL Access content directly
Journal Articles Concurrency and Computation: Practice and Experience Year : 2018

GPU-accelerated backtracking using CUDA dynamic parallelism

(1, 2) , (3) , (1) , (4) , (5)
1
2
3
4
5

Abstract

New GPGPU technologies, such as CUDA Dynamic Parallelism (CDP), can help dealing with recursive patterns of computation, such as divide-and-conquer, used by backtracking algorithms. In this paper, we propose a GPU-accelerated backtracking algorithm using CDP that extends a well-known parallel backtracking model. The search starts on CPU, processing the search tree until a first cutoff depth. Based on this partial backtracking tree, the algorithm analyzes the memory requirements of subsequent kernel generations. The proposed algorithm performs no dynamic allocation of memory on GPU, unlike related works from the literature. The proposed algorithm has been extensively tested using the N-Queens Puzzle problem and instances of the Asymmetric Traveling Salesman Problem (ATSP) as test-cases. The proposed CDP algorithm may, under some conditions, outperform its non-CDP counterpart by a factor up to 25. But, it may also be up to twice slower. The CDP-based implementation has much better worst case execution times and makes algorithm's performance less dependent on the tuning of parameters. Compared to other CDP-based strategies from the literature, the proposed algorithm is on average 8× faster. The proposed algorithm is also hybridized with another CDP-based strategy from the literature. The combination of strategies is in average 4.5× faster than the related strategy. We also identify some difficulties, limitations, and bottlenecks concerning the CDP programming model which may be useful for helping potential users.
Not file

Dates and versions

hal-01919514 , version 1 (12-11-2018)

Identifiers

Cite

Tiago Carneiro Pessoa, Jan Gmys, Francisco Heron de Carvalho Junior, Nouredine Melab, Daniel Tuyttens. GPU-accelerated backtracking using CUDA dynamic parallelism. Concurrency and Computation: Practice and Experience, 2018, 30 (9), ⟨10.1002/cpe.4374⟩. ⟨hal-01919514⟩
367 View
1 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More