分支优化Reducing Branch Divergence in GPU Programs.pdf

Reducing Branch Divergence in GPU Programs Tianyi David Han Tarek S. Abdelrahman The Edward S. Rogers Sr. Department of Electrical and Computer Engineering University of Toronto Toronto, Ontario M5S 3G4, Canada {han, tsa}@ ABSTRACT managed cache and adjusting the pattern of accesses to the Branch divergence has a significant impact on the perfor- off-chip device memory [1, 5–7, 14–18]. mance of GPU programs. We propose two novel software- In contrast, there has been less work on optimizations that based optimizations, called iteration delaying and branch target another fundamental aspect of GPU performance, distribution that aim to reduce branch divergence. Itera- namely its Single Instruction Multiple Data (SIMD) exe- cution model. While this model enables simpler control tion delaying targets a divergent branch enclosed by a loop within a kernel. It improves performance by executing loop hardware, it imposes heavy performance penalties on ker- nels with control flow. In such kernels, SIMD threads di- iterations that take the same branch direction and delay- ing those that take the other direction until later iterations. verge, i.e., follow different paths of execution. The hard- Branch distribution reduces the length of divergent code ware makes all these paths e