GPU-based backtracking strategies for solving permutation combinatorial problems

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.Novas extensões ao modelo de programação GPGPU, tais como o Paralelismo Dinâmico (CUDA Dynamic Parallelism - (CDP)), podem facilitar a programação para GPUs de padrões recursivos de computação, como o de divisão-e-conquista, utilizado por algoritmos backtracking. O presente trabalho propõe um novo algoritmo backtracking que utiliza CDP, baseado em um modelo paralelo para buscas não estruturadas. Diferentemente dos trabalhos da literatura, o algoritmo proposto não realiza alocação dinâmica em GPU. A memória requerida pela gerações de kernel subsequentes é previamente alocada de acordo com uma análise de uma árvore backtracking parcial. A Segunda parte desta tese generaliza as ideias do algoritmo inicial para abordagens que realizam alocação dinâmica em GPU e lançam mais que duas gerações de kernels. Essa generalização é necessária para que tais estratégias não apresentem erros em tempo de execução. A parte final desta tese investiga, no escopo dos algoritmos de busca não estruturada, se o uso de CDP é vantajoso ou não, comparando uma versão CDP e a versão equivalente que realiza várias chamadas do kernel através do host. Todos os algoritmos propostos foram extensamente validados utilizando o problema das N-Rainhas e o Problema do Caixeiro Viajante Assimétrico como casos de teste. A presente tese também identificou dificuldades, limitações e gargalos relacionadas ao modelo de programação CDP que podem ser úteis para ajudar potenciais usuários