Parallel GPU algorithms for compressed implicit octrees

Abstract

Resumo: O algoritmo Barnes-Hut é um método aproximado amplamente usado para na simulação gravitacional de N-Corpos, que envolve a construção e eaminliamento de árvores esparsas a cada passo de simulação e assim reduzindo a complexidade computacional e possibilitando a solução de problemas práticos de grande escala, A natureza irregular desse código de eaminliamento em árvore apresenta desafios interessantes na sua computação em sistemas paralelos. Desafios adicionais ocorrem nesse tipo de padrão de computação paralela quando se deseja utilizar de maneira eficaz a capacidade computacional de arquiteturas de GPUs (processadores gráficos multieore de propósito geral), Oetrees são estruturas de dados que representam de maneira eficiente as informações de dados espaciais em várias áreas tais como computação científica, computação gráfica, processamento de imagens, dentre outras. Nosso enfoque nesse trabalho é de tratar explicitamente os padrões dinâmicos irregulares de acesso a dados em memória com o remapeamento de dados e transformações de lavouts, dependendo das estruturas acessadas. Também é feito o controle explicito, por programa, de fluxos divergentes de execuções em threads. Apresentamos uma nova estrutura de dados compacta para lavouts de oetrees esparsas, bem como algoritmos paralelos para GPUs, tanto para transformações de lavouts como para eaminliamento paralelo usando a técnica de simulação de "warps"-largos (SWW, Simulated Wide-Warps), Os benefícios de nossas técnicas ocorrem devido à transposição do algoritmo de eamin- nhamento na árvore para execução em padrões mais regulares, possibilitando uma melhor adaptação ao modelo GPU paralelo, A estrutura de dados permite explorar localidades de acessos à memória durante os percursos, ao mesmo tempo conservando espaço em memória eaehe ou em memória compartilhada (scratchpad). Desta forma a memória rápida intra-eore pode ser dedicada a acelerar eaminliamentos. Controle divergência de fluxos também é delimitado de maneira algorítmica, impondo uma execução uniforme na maior parte dos segmentos de execução. Nossos experimentos mostram melhoria de desempenho significativa em relação às soluções em GPU mais conhecidas para este algoritmo. Desenvolvemos um novo algoritmo paralelo eficiente que gera diretamente de uma só vez as oetrees implícitas comprimidas, como um método massivamente paralelo. Este método traz uma nova visão para tratar de forma eficiente com a natureza irregular também presente na construção de oetrees esparsas, O algoritmo proposto de geração massivamente paralela de oetrees esparsas tem aplicação imediata em nossa implementação GPU paralela da simulação Barnes-Hut e em outros métodos de N-eorpos, As técnicas e algoritmos propostos nesta tese também poderão ser aplicadas em outros contextos.

Abstract: The Barnes-Hut algorithm is a widely used approximation method for the N-Body simulation problem, which involves the construction and traversal of sparse trees at each simulation step and thus reducing the complexity to solve large/praetieal problems. The irregular nature of this tree walking code presents interesting challenges for its computation on parallel systems. Additional problems arise in effectively exploiting the processing capacity of GPU architectures. Octrees are data structures that efficiently represent spatial data in many fields such as scientific computing, computer graphics and image processing, among others. In this work we explicitly deal with dynamic irregular patterns in data accesses with data remapping and data transformation, depending on the data structures being accessed, and by controlling the execution flow divergence of threads. We present a new compact data-strueture for sparse octree layouts, and also GPU parallel algorithms for tree transformation and parallel walking using software Simulated Wide-Warps (SWW), Benefits of our techniques are in transposing the tree algorithm to execute regular patterns to match the GPU parallel model. The data structure allows exploring localities during traversals, at the same time conserving space in caches or scratchpad memory. This way fast intra-eore memory can be dedicated to speed up traversals. Control flow divergence is also algorithmically constrained, enforcing a mostly uniform execution of threads. Our experiments show significant performance improvement over the best known GPU solutions to this algorithm. We have developed a novel efficient parallel algorithm that directly generates entire compressed implicit octrees at once, as a massively parallel method. This method brings new insight on how to efficiently deal with the irregular nature of algorithms for constructing sparse octrees. The proposed algorithm has immediate application to our GPU parallel Barnes-Hut implementation and other N-Body methods. We envision that the techniques and algorithms proposed in this dissertation can also be applied in other contexts.