Título: GPU-Based Backtracking Strategies for Solving Permutation Combinatorial Problems

Data: 05/12/2017 Horário: 09h Local: Sala de Seminários / Bloco 952

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. This work proposes 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 performs an analysis of the memory required by the subsequent kernel generations. Unlikely related works from the literature, the proposed algorithm does not dynamically allocate memory on GPU. The required memory is preallocated based on an analysis of the partial backtracking tree. This approach has been extensively tested using the N-Queens Puzzle problem and instances of the Asymmetric Traveling Salesman Problem (ATSP) as test-cases. According to the experimental results, the proposed CDP-based backtracking may, under some conditions, outperform its non-CDP counterpart by a factor up to 25, and has much better worst-case execution times. However, it may also be up to twice slower. The second part of the present work proposes a set of algorithms to dynamically calculate the requirements of the search and setup CDP runtime variables: heap size and maximum synchronization depth. All CDP-based algorithms mentioned in this work can be implemented without using CDP, invoking CUDA kernels from the host. The final part of this thesis presents two implementations which have the semantics of the CDP-based strategies. According to the results, a smaller interference of the host combined with a block-based child search seems worthwhile for irregular GPU-based tree search algorithms. The present work has also identified some difficulties, limitations, and bottlenecks concerning the CDP programming model which may be useful for helping potential users.

Banca:

• Prof. Dr. Francisco Heron de Carvalho Junior (MDCC/UFC - Orientador)
• Prof. Dr. Nouredine Melab (Université Lille 1/França)
• Prof. Dr. Igor Machado Coelho (UERJ)
• Prof. Dr. Albert Einstein Fernandes Muritiba (UFC)
• Prof. Dr. Rafael Castro de Andrade (MDCC/UFC)