Thread block compaction for efficient SIMT control flow

Manycore accelerators such as graphics processor units (GPUs) organize processing units into single-instruction, multiple data “cores ” to improve throughput per unit hardware cost. Programming models for these acceler-ators encourage applications to run kernels with large groups of parallel scalar threads. The hardware groups these threads into warps/wavefronts and executes them in lockstep—dubbed single-instruction, multiple-thread (SIMT) by NVIDIA. While current GPUs employ a per-warp (or per-wavefront) stack to manage divergent control flow, it incurs decreased efficiency for applications with nested, data-dependent control flow. In this paper, we propose and evaluate the benefits of extending the sharing of resources in a block of warps, already used for scratchpad mem-ory, to exploit control flow locality among threads (where such sharing may at first seem detrimental). In our pro-posal, warps within a thread block share a common block-wide stack for divergence handling. At a divergent branch, threads are compacted into new warps in hardware. Our simulation results show that this compaction mechanism provides an average speedup of 22 % over a baseline per-warp, stack-based reconvergence mechanism, and 17 % ver-sus dynamic warp formation on a set of CUDA applications that suffer significantly from control flow divergence. 1