GPU-based backtracking strategies for solving permutation combinatorial problems

Detalhes bibliográficos
Ano de defesa: 2017
Autor(a) principal: Pessoa, Tiago Carneiro
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: eng
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://www.repositorio.ufc.br/handle/riufc/29142
Resumo: 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.