Irregular nested loop sizes lead to hardware underutilization Irregular Nested Loops

The effective parallelization of applications exhibiting irregular nested parallelism is still an open problem. In particular, a naïve mapping of irregular codes to the GPU hardware may lead to resource underutilization and, thereby, limited performance. In this work, we focus on two computational patterns exhibiting nested parallelism: irregular nested loops and recursive algorithms operating on tree and graph data structures. We propose different parallelization templates aimed at increasing the GPU utilization of these codes. Specifically, we investigate different mechanisms to effectively distribute irregular work to streaming multiprocessors and GPU cores. We target the Fermi and the Kepler architecture; in the latter case, we also study parallelization templates relying on dynamic parallelism and propose mechanisms to maximize the work performed by nested kernels and minimize the overhead due to their launch. Our results show that our parallelization templates can achieve 2~6x speedup as compared to baseline code variants based on simple parallelization templates