Title: Using program branch probability for the thread parallelisation of branch divergence on the CUDA platform
Authors: Hong Yao; Huifang Deng; Caifeng Zou
Addresses: School of Computer Science and Engineering, South China University of Technology, Guangzhou, 510006, China ' School of Computer Science and Engineering, South China University of Technology, Guangzhou, 510006, China ' School of Computer Science and Engineering, South China University of Technology, Guangzhou, 510006, China
Abstract: Virtualisation environment can bring more flexibility for parallel optimisation. In view of this, we focus on the divergent branch problem within a SIMT architecture, where threads with branch divergence should be serially executed. Existing approaches are normally costly and not so satisfactory in vectorising these threads due to the constraints of private variables. However, on the other hand, these constraints can be released in a virtualised environment, because the private resources can be avoided putting in use directly by applications. For virtualised CUDA platforms, our approach can converge isomorphic threads into same redundant warps to eliminate divergence. We introduce the algorithms for the thread recombination models of binary branches, single branch and multiple branches respectively, and each number of redundant warps can be determined by a program branch probability. Without redesigning hardware needed, we obtained a load balance schema for parallelisation of divergent branch threads.
Keywords: GPGPU; SIMT architecture; compute unified device architecture; CUDA; branch divergence; performance optimisation; code structure; program branch probability; PBP; thread recombination; redundant warp; hash table; warp lane.
International Journal of Autonomous and Adaptive Communications Systems, 2018 Vol.11 No.2, pp.171 - 191
Received: 24 Feb 2016
Accepted: 25 Jul 2016
Published online: 22 May 2018 *