Dynamic Warp Formation and Scheduling for Efficient GPU Control Flow

TitleDynamic Warp Formation and Scheduling for Efficient GPU Control Flow
Publication TypeConference Paper
Year of Publication2007
AuthorsFung, W. W. L., I. Sham, G. Yuan, and T. M. Aamodt
Conference NameMicroarchitecture, 2007. MICRO 2007. 40th Annual IEEE/ACM International Symposium on
Pagination407 -420
Date Publisheddec.
Keywordscomputer graphic equipment, data flow computing, dynamic scheduling, dynamic warp formation, GPU control flow instructions, GPU instruction set architecture, graphics processing units, instruction sets, parallel architectures, pipeline processing, SIMD branch execution, SIMD pipelines, single-instruction multiple-data pipelines

Recent advances in graphics processing units (GPUs) have resulted in massively parallel hardware that is easily programmable and widely available in commodity desktop computer systems. GPUs typically use single-instruction, multiple-data (SIMD) pipelines to achieve high performance with minimal overhead incurred by control hardware. Scalar threads are grouped together into SIMD batches, sometimes referred to as warps. While SIMD is ideally suited for simple programs, recent GPUs include control flow instructions in the GPU instruction set architecture and programs using these instructions may experience reduced performance due to the way branch execution is supported by hardware. One approach is to add a stack to allow different SIMD processing elements to execute distinct program paths after a branch instruction. The occurrence of diverging branch outcomes for different processing elements significantly degrades performance. In this paper, we explore mechanisms for more efficient SIMD branch execution on GPUs. We show that a realistic hardware implementation that dynamically regroups threads into new warps on the fly following the occurrence of diverging branch outcomes improves performance by an average of 20.7% for an estimated area increase of 4.7%.


a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2021 The University of British Columbia