Opportunistic Inter-path Reconvergence for GPUs

Back to all technologies
Download as PDF
2020-KULK-68820
Researchers at Purdue University have developed a new method to improve the speed of general purpose GPUs (GPGPUs) running irregular applications. GPGPUs batch a group of threads and execute the batch, known as a warp, in lockstep in order to amortize the cost of fetch, decode and accessing the register files. Applications with threads following different control paths are known as irregular applications. Irregular applications, when running on a GPU, alter the lockstep execution since different threads follow different paths. Baseline GPUs serialize the execution of diverging threads within a warp, resulting in loss of thread-level parallelism and decreased processing speed. The Purdue researchers found that on average 62% of divergent instructions, threads executing the different code paths, are opcode convergent. Using this finding, the researchers proposed a novel compiler analysis that identifies opportunities for re-convergence of traditionally divergent basic blocks and transforms the code accordingly. The researchers couple their compiler analysis to the instruction set architecture (ISA) and double the number of operands. The researchers also propose a technique for managing the single-instruction multiple thread (SIMT) reconvergence stack of GPUs to avoid overheard due to the increased information passed. Importantly, the researchers' transformations do not impose any loss on regular workloads since no opportunity for re-convergence would be found by the complier. Finally, the researchers' transformation can be implemented in software, providing existing GPUs with improved performance without requiring hardware modification.

Technology Validation: In a simulation, the researchers' extended ISA and redesigned SIMT stack achieved 17% speedup over baseline GPUs executing irregular applications.

Advantages:
- Increased speed in running irregular applications
- Does not increase memory requirement of a warp
- Does not impose any loss on regular workloads
- Transformations can be implemented in software

Applications:
- Improving GPU function on irregular applications
Sep 30, 2021
Utility-Gov. Funding
United States
(None)
(None)

Sep 30, 2020
Provisional-Patent
United States
(None)
(None)
Purdue Office of Technology Commercialization
The Convergence Center
101 Foundry Drive, Suite 2500
West Lafayette, IN 47906

Phone: (765) 588-3475
Fax: (765) 463-3486
Email: otcip@prf.org