Lazy Work Stealing for Continuous Hierarchy Traversal
Autores
|
5420 |
2472,455
|
|
|
5421 |
2472,455
|
Informações:
Publicações do PESC
Este estudo apresenta os resultados de pesquisa em balanceamento de carga dinâmico para Detecção de Colisão Contínua (CCD) usando Hierarquias de Volumes Envoltórios (BVHs) em Unidades de Processamento Gráfico (GPUs). A travessia de hierarquia é um problema desafiador para a computação em GPU, pois a carga de trabalho de percurso tem uma natureza muito dinâmica. Pesquisas atuais resultaram em métodos para dinamicamente balancear a carga conforme a travessia é executada. Infelizmente, a atual interface baseada em grade para computação em GPU não é totalmente adequada para este tipo de computação e o código de balanceamento de carga pode gerar sobrecarga excessiva. Este trabalho compara métodos de balanceamento de carga conhecidos, apontando prós e contras e apresenta um novo algoritmo para resolver alguns dos problemas mais notórios.
O algoritmo usa o novo conceito de roubo preguiçoso de trabalho, que tenta obter o maximo de paralelismo através de roubo ganancioso de trabalho e transferência preguiçosa. Além disso, o algoritmo é projetado para aumentar o uso de memoria compartilhada por bloco e diminuir a penalidade de troca de contexto entre CPU e GPU.
This study presents the results of research in dynamic load balancing for Continuous Collision Detection (CCD) using Bounding Volumes Hierarchies (BVHs) on Graphics Processing Units (GPUs). Hierarchy traversal is a challenging problem for GPU computing, since the work load of traversal has a very dynamic nature. Current research resulted in methods to dynamically balance load as the traversal is evaluated. Unfortunatelly, current grid-based GPU computing interface is not well suited for this type of computing and load balancing code can generate excessive overhead. This work compares known load balancing methods, pointing pros and cons and presents a novel algorithm to address some of the most glaring problems.
The algorithm uses the new concept of lazy work stealing, which tries to get the most out of the parallel capabilities of GPUs by greedy work stealing and lazy work evaluation. Also, the algorithm is designed to augment shared memory usage per block and diminish CPU-GPU context exchange penalties.