Article: Using program branch probability for the thread parallelisation of branch divergence on the CUDA platform Journal: International Journal of Autonomous and Adaptive Communications Systems (IJAACS) 2018 Vol.11 No.2 pp.171 - 191 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. Inderscience Publishers - linking academia, business and industry through research

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.

DOI: 10.1504/IJAACS.2018.092031

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: 30 May 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article

Title: Using program branch probability for the thread parallelisation of branch divergence on the CUDA platform

Keep up-to-date