Work stealing inside GPUs

Abstract

Unidades de processamento gráfico (GPU) tornaram-se ferramentas de grande valia no domínio da computação de alto desempenho. Graças as recentes inovações e melhoramentos do hardware é possível utilizar processadores gráficos de propósito genéricos (GPGPUS) em uma ampla gama de aplicações científicas. No entanto, os modelos de programação existentes usados em GPGPU não são ainda suficientemente adaptáveis `as diversas formas de paralelismo que uma aplicação possa expressar. Neste contexto, propomos um modelo híbrido de programação paralela para GPGPU usando paralelismo de tarefas e de dados. Em oposição ao que e advogado pelo modelo de programação CUDA, baseado apenas no paralelismo de dados, mostramos que ´e possível explorar o paralelismo de tarefas em GPUs e escaloná-las de forma eficiente usando a técnica do roubo de tarefas. Apresentamos neste trabalho a implementação de um escalonador por roubo de tarefas em CUDA e comparamos seu desempenho aos métodos de escalonamento estático e por lisa aplicados aos problemas de transformação em array e particionamento em octree.

Graphics Processing units have become a valuable support for High Performance Computing (HPC) applications. However, despite the many improvements on the General Purpose GPU, there is still the need of a generic programming model adaptable to the many forms of parallelism that an application can express. The CUDA programming model is widely used on the GPGPU domain, but is very limited in aspects like load balancing and task parallelism. This work introduces a new programming model to be used on general purpose graphics processors. We propose an hybrid model combining tasks and data parallelism which extends the domain of applications that can efficiently make use of graphics processors. We implement a work stealing scheduler to efficiently schedule tasks inside a GPU keeping an even load balance between its multiprocessors. Finally, we evaluate the performance of our work stealing scheduler comparing it with static and list scheduling methods applied to the problems of array transformation and octree partitioning.