Divergent Branch Threads Compaction for Efficient SIMD Control Flow

YANG Hui; CHEN Shuming; WAN Jianghua; XU Xiaolu

doi:10.1049/cje.2015.04.010

Volume 24 Issue 2

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2015 > 24(2): 288-294

YANG Hui, CHEN Shuming, WAN Jianghua, et al., “Divergent Branch Threads Compaction for Efficient SIMD Control Flow,” Chinese Journal of Electronics, vol. 24, no. 2, pp. 288-294, 2015, doi: 10.1049/cje.2015.04.010

Citation:

YANG Hui, CHEN Shuming, WAN Jianghua, et al., “Divergent Branch Threads Compaction for Efficient SIMD Control Flow,” Chinese Journal of Electronics, vol. 24, no. 2, pp. 288-294, 2015, doi: 10.1049/cje.2015.04.010

Citation:

PDF( 581 KB)

Divergent Branch Threads Compaction for Efficient SIMD Control Flow

doi: 10.1049/cje.2015.04.010

1.
School of Computer, National University of Defense Technology, Changsha 410073, China;
2.
Institute of Aeronautical Meteorology Equipment Academy of Air Force, Beijing 100085, China

Funds: This work is supported by the National Natural Science Foundation of China (No.61070036, No.61133007).

Publish Date: 2015-04-10

Abstract

Abstract

Wide Single instruction multiple data (SIMD) architectures are very important in the computeintensive applications. The SIMD execution model is inefficient when it suffers from the divergent control flow. The divergent execution paths across loop iterations take place sequentially on SIMD, which defeats part of the efficiency advantage of SIMD execution. This paper proposes a mechanism to compact the divergent branch threads to mitigate the impact of branch thread divergence on SIMD architectures. It relaxes the SIMD execution model by allowing the distinct instruction flows to be scheduled independently, instead of one single instruction flow. It increases flexibility and mitigates the synchronization cost of co-issuing instructions from different divergent branch threads by giving the Vector processing elements (VPEs) the ability to direct their own control flow. The proposed divergent branch threads compaction mechanism improves performance by 2.56x over traditional SIMD architecture for a wide variety of general purpose parallel applications while the area overhead only increases 6.48%.
- SIMD,
- Multiple instructionmultiple data (MIMD),
- Vector branch thread,
- Conditional operations,
- Control flow

FullText(HTML)

References(12)

References

W.J. Bouknight, S.A. Denenberg and D.E. Mclntyre, “The Illiac IV system”, Proceedings of the IEEE, Vol.60, No.4, pp.369-388, 1972.

H.Y. Dai and X.S. Wang, “A new polarimetric method by using spatial polarization characteristics of scanning antenna”, IEEE Trans. on Antennas and Propag., Vol.60, No.3, pp.1653-1656, 2012.

U.J. Kapasi, W.J. Dally and S. Rixner, “Efficient conditional operations for data-parallel architectures”, Proceedings of the 33rd Annual ACM/IEEE International Symposium on Microarchitecture, Monterey, CA ,USA, pp.159-170, 2000.

W.W.L. Fung, I. Sham and G. Yuan, “Dynamic warp formation: Dfficient MIMD control flow on SIMD graphics hardware”, ACM Transactions on Architecture and Code Optimization (TACO), Vol.6, No.2, pp.407-420, 2009.

W. Fung and T. Aamodt, “Thread block compaction for efficient SIMT control flow”, IEEE 17th International Symposium on High Performance Computer Architecture HPCA, San Antonio, TX, USA, pp.25-36, 2011.

V. Narasiman, M. Shebanow and C.J. Lee, “Improving GPU performance via large warps and two-level warp scheduling”, Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture, New York, NY, USA, pp.308-317, 2011.

A. Glew, Coherent Vector Lane Threading, Berkeley ParLab Seminar, USA, 2009.

R. Krashinsky, C. Batten and M. Hampton, “The vector-thread architecture”, Proceedings of the 31st Annual International Symposium on Computer Architecture, IEEE Computer Society Washington, DC, USA, pp.52-63, 2004.

N. Brunie, S. Collange and G. Diamos, “Simultaneous branch and warp interweaving for sustained GPU performance”, Proceedings of the 39th International Symposium on Computer Architecture, IEEE Computer Society, Washington, DC, USA, pp.49-60, 2012.

Yaohua Wang, Shuming Chen and Kai Zhang, “Instruction shuffle: Achieving MIMD-like performance on SIMD architectures”, IEEE Computer Architecture Letters, Vol.11, No.2, pp.37-40, 2012.

Hui Yang, Shuming Chen and Tiebin Wu, “Control-enhanced power-SIMD”, IEICE ELEX, Vol.9, No.14, pp.1147-1152, 2012.

Hui Yang, Shan Wu and Shuming Chen, “A novel dynamic SIMD-chain”, IEEE 11th International Conference on Solid-State and Intergrated Circuit Technology ICSICT, Xi'An, China, pp.1266-1268, 2012.

Relative Articles

Supplements(0)

Cited By

Proportional views