GPU-based backtracking strategies for solving permutation combinatorial problems

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. The initial part of this thesis proposes a GPU-accelerated backtracking algorithm using CDP that extends a well-known parallel backtracking model. Unlike related works from the literature, the proposed algorithm does not dynamically allocate memory on GPU. The memory required by the subsequent kernel generations is preallocated based on the analysis of a partial backtracking tree. The second part of this work generalizes the ideas of the first algorithm for approaches that dynamically allocate memory on GPU and launch more than two kernel generations. The final part of this thesis investigates whether the use of CDP is advantageous over a non-CDP and equivalent counterpart. All approaches have been extensively validated using the N-Queens Puzzle problem and instances of the Asymmetric Traveling Salesman Problem as test-cases. This thesis has also identified some difficulties, limitations, and bottlenecks concerning the CDP programming model which may be useful for helping potential users.