SIMD re-convergence at thread frontiers
SIMD re-convergence at thread frontiers
复制标题
DOI：
10.1145/2155620.2155676
复制
发表时间：
2011-12
期刊：
影响因子：
--
通讯作者：
G. Diamos;Ben Ashbaugh;S. Maiyuran;Andrew Kerr;Haicheng Wu;S. Yalamanchili
中科院分区：
文献类型：
--
作者：
G. Diamos;Ben Ashbaugh;S. Maiyuran;Andrew Kerr;Haicheng Wu;S. Yalamanchili
用于将具有不同控制流的数据并行程序映射到SIMD体系结构的硬件和编译器技术最近使得新的GPGPU编程模型的出现成为可能，例如CUDA、OpenCL和DirectX Compute。分支分歧的影响可能有很大的不同，这取决于程序的控制流是结构化的还是非结构化的。在本文中，我们证明了非结构化控制流经常出现在应用程序中，当使用现有的方法处理分支分歧时，可能会导致显著的代码扩展。本文提出了一种将任意控制流自动映射到SIMD处理器上的新技术，该技术依赖于线程前沿的概念，线程前沿是程序的一个有界区域，包含从当前WARP分支出来的所有线程。该技术在配置成模拟i)商用GPU(Intel Sandybridge)和ii)当前GPU架构中未实现的定制硬件支持的GPU仿真器上进行评估。结果表明，该方法与已有的结构化控制流方法具有相同的性能，并且在执行非结构化控制流时能在尽可能早的时刻重新收敛。这导致i)用于几个真实应用的动态指令计数减少1.5%-633.2，ii)编译过程简化，以及iii)向现有数据并行语言有效地添加高级非结构化编程构造(例如，异常)的能力。
Hardware and compiler techniques for mapping data-parallel programs with divergent control flow to SIMD architectures have recently enabled the emergence of new GPGPU programming models such as CUDA, OpenCL, and DirectX Compute. The impact of branch divergence can be quite different depending upon whether the program's control flow is structured or unstructured. In this paper, we show that unstructured control flow occurs frequently in applications and can lead to significant code expansion when executed using existing approaches for handling branch divergence. This paper proposes a new technique for automatically mapping arbitrary control flow onto SIMD processors that relies on a concept of a Thread Frontier, which is a bounded region of the program containing all threads that have branched away from the current warp. This technique is evaluated on a GPU emulator configured to model i) a commodity GPU (Intel Sandybridge), and ii) custom hardware support not realized in current GPU architectures. It is shown that this new technique performs identically to the best existing method for structured control flow, and re-converges at the earliest possible point when executing unstructured control flow. This leads to i) between 1.5 – 633.2% reductions in dynamic instruction counts for several real applications, ii) simplification of the compilation process, and iii) ability to efficiently add high level unstructured programming constructs (e.g., exceptions) to existing data-parallel languages.