Free Launch: Optimizing GPU Dynamic Kernel Launches through Thread Reuse

Supporting dynamic parallelism is important for GPU to benefit a broad range of applications. There are cur-rently two fundamental ways for programs to exploit dy-namic parallelism on GPU: a software-based approach with software-managed worklists, and a hardware-based approach through dynamic subkernel launches. Neither is satisfactory. The former is complicated to program and is often subject to some load imbalance; the latter su↵ers large runtime overhead. In this work, we propose free launch, a new software approach to overcoming the shortcomings of both meth-ods. It allows programmers to use subkernel launches to express dynamic parallelism. It employs a novel compiler-based code transformation named subkernel launch removal to replace the subkernel launches with the reuse of parent threads. Coupled with an adaptive task assignment mechanism, the transformation reas-signs the tasks in the subkernels to the parent threads with a good load balance. The technique requires no hardware extensions, immediately deployable on exist-ing GPUs. It keeps the programming convenience of the subkernel launch-based approach while avoiding its large runtime overhead. Meanwhile, its superior load balancing makes it outperform manual worklist-based techniques by 3X on average