Abstract: General-purpose graphics processing unit (GPGPU) adopts the single instruction multiple- thread (SIMT) model, which allows a large number of threads to execute the same instruction simultaneously, thereby significantly improving computing efficiency. Under the SIMT model, GPGPUs organize a group of threads into logical execution units called warps. Since hardware must perform time-division multiplexing among multiple warps, warp scheduling is crucial for achieving efficient parallel computing. By adding new checkpoint instructions, a checkpoint-based multi-level warp scheduler (CPWS) is introduced. CPWS can track the execution progress of each warp and dynamically adjust its scheduling strategy based on this progress, with relatively low overall hardware overhead. Experimental results show that CPWS improves performance by 11% compared with the greedy then oldest (GTO) scheduler, 16.7% compared with the loose round robin (LRR) scheduler, and 10.6% compared with the two-level round robin scheduler. In addition, synthesis results on FPGA indicate that the logic unit overhead added by CPWS compared with GTO is only 0.8%.

Key words: general-purpose graphics processing unit(GPGPU), checkpoint, warp scheduler