Lazy Work Stealing for Continuous Hierarchy Traversal on Deformable Bodies

Vinícius da Silva, Claudio Esperança, Ricardo Guerra Marroquim

2014

Abstract

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. Unfortunately, current grid-based GPU computing interfaces are not well suited for this type of computing and load balancing code can generate excessive overhead. This work 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.

Paper Citation

in Harvard Style

Silva V., Esperança C. and Guerra Marroquim R. (2014). Lazy Work Stealing for Continuous Hierarchy Traversal on Deformable Bodies . In Proceedings of the 9th International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2014) ISBN 978-989-758-002-4, pages 430-437. DOI: 10.5220/0004656904300437

in Bibtex Style

@conference{grapp14,
author={Vinícius da Silva and Claudio Esperança and Ricardo Guerra Marroquim},
title={Lazy Work Stealing for Continuous Hierarchy Traversal on Deformable Bodies},
booktitle={Proceedings of the 9th International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2014)},
year={2014},
pages={430-437},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004656904300437},
isbn={978-989-758-002-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 9th International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2014)
TI - Lazy Work Stealing for Continuous Hierarchy Traversal on Deformable Bodies
SN - 978-989-758-002-4
AU - Silva V.
AU - Esperança C.
AU - Guerra Marroquim R.
PY - 2014
SP - 430
EP - 437
DO - 10.5220/0004656904300437