Efficient Warp Execution in Presence of Divergence with Collaborative Context Collection

GPU’s SIMD architecture is a double-edged sword con-fronting parallel tasks with control flow divergence. On the one hand, it provides a high performance yet power-efficient platform to accelerate applications via massive parallelism; however, on the other hand, irregularities induce inefficiencies due to the warp’s lockstep traver-sal of all diverging execution paths. In this work, we present a software (compiler) technique named Collab-orative Context Collection (CCC) that increases the warp execution efficiency when faced with thread diver-gence incurred either by different intra-warp task as-signment or by intra-warp load imbalance. CCC col-lects the relevant registers of divergent threads in a warp-specific stack allocated in the fast shared mem-ory, and restores them only when the perfect utiliza-tion of warp lanes becomes feasible. We propose code transformations to enable applicability of CCC to va-riety of program segments with thread divergence. We also introduce optimizations to reduce the cost of CCC and to avoid device occupancy limitation or memory divergence. We have developed a framework that au-tomates application of CCC to CUDA generated inter-mediate PTX code. We evaluated CCC on real-world applications and multiple scenarios using synthetic pro-grams. CCC improves the warp execution efficiency of real-world benchmarks by up to 56 % and achieves an average speedup of 1.69x (maximum 3.08x)