Dynamic Selective Compaction for Branch Scheduling of Graphics Processing Units

Abstract

In recent years, Graphics Processing Units (GPUs) with significantly enhanced processing capabilities have started to emerge, and these high performance GPUs are increasingly used in applications, besides graphics, that require extremely high computing performance. However, in order to more fully utilize the computational capabilities of these powerful GPUs, threads must be efficiently scheduled specifically for these GPU architectures. This paper proposes a new and powerful scheduling method specifically targeted for modern high performance GPUs, which use hierarchical single-instruction multiple-data (SIMD) architectures. Programs developed for these architectures are partitioned into clusters of thread groups, referred to as warps. Due to the SIMD architecture used to process the threads within a warp, all threads must either wait or execute the same instructions in lock step. Thus, the manner in which warps are grouped and scheduled significantly impact the overall performance achieved. The proposed scheduling method is based on dynamic warp grouping for efficient warp compaction and scheduling of warps based on branch divergence and reconvergence points. In order to implement this method, we propose prior branch information unit to make control flows of each warps synchronized. In addition, we propose basic block aware warp scheduling method to reduce time difference of warp arrival time at branch divergence. The proposed method is shown to improve performance by up to 12% over previously proposed GPU core scheduling methods.