Int. J. of Autonomous and Adaptive Communications Systems   »   2018 Vol.11, No.2

 

 

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

 

Int. J. of Autonomous and Adaptive Communications Systems, 2018 Vol.11, No.2, pp.171 - 191

 

Available online: 22 May 2018

 

 

Editors Full text accessAccess for SubscribersPurchase this articleComment on this article