基于国产GPGPU非一致控制流的分支优化

doi:10.19678/j.issn.1000-3428.0070570

摘要/Abstract

摘要：

目前, 通用图形处理单元(GPGPU)因其强大的并行处理能力而被广泛应用于各种计算任务。然而, 采用单指令多线程(SIMT)并行执行模型的GPGPU在程序执行时, 核函数会产生非一致控制流行为, 从而引发线程束分化, 降低加速器的整体性能。针对核函数执行过程中因非一致控制流引起的性能下降问题, 提出一种特定场景下的分支编译优化方法——连续分支合并MergeCFG。在编译器中间代码优化阶段, 通过控制流分析识别出控制流图中含相同条件跳转的连续分支结构, 以确定潜在的优化机会。接着, 基于指令分析, 评估优化的可行性, 判断是否存在能够减少分支跳转的优化空间。最后, 运用基本块复制与合并技术, 对控制流结构进行优化, 以减少程序中的分支跳转操作, 从而简化控制流, 提高程序执行效率。在国产GPGPU上使用7个合适的基准测试套件验证所提方法的可行性。仿真实验结果表明, 该方法有效减少程序中的分支跳转操作, 优化后的测试用例在性能上获得了显著提升。所测用例的平均加速比提高了2%~12%, 个别测试用例的性能提升超过5倍。

关键词: 通用图形处理单元, 单指令多线程, 控制流, 线程束分化, 编译优化

Abstract:

General-Purpose Graphics Processing Units (GPGPUs) are widely utilized for various computational tasks owing to their robust parallel processing capabilities. However, GPGPUs employing the Single Instruction Multiple Threads (SIMT) execution model often encounter non-consistent control flows during kernel execution, leading to warp divergence and a subsequent decline in the overall accelerator performance. To address the performance degradation caused by non-consistent control flows in kernel execution, this study introduces MergeCFG, a branch compilation optimization technique tailored for specific scenarios. During the intermediate code optimization phase in the compiler, MergeCFG conducts a control flow analysis to identify consecutive branch structures in the control flow graph that share identical conditional branches, thereby identifying potential optimization opportunities. Subsequently, based on instruction analysis, it assesses the feasibility of optimization to determine whether opportunities for reducing branch operations exist. Finally, by employing basic block duplication and merging techniques, it optimizes the control flow structure to minimize branch operations, thereby simplifying the control flow and enhancing the program execution efficiency. Experiments are conducted using a domestic GPGPU system with seven suitable benchmark test suites to validate the feasibility of this method. The results demonstrate that this method effectively reduces branch operations within programs, leading to significant performance improvements in optimized test cases. The average speedup across the evaluated cases ranges from 2% to 12%, with certain test cases exhibiting performance enhancements exceeding fivefold.

Key words: General-Purpose Graphics Processing Unit (GPGPU), Single Instruction Multiple Threads (SIMT), control flow, warp divergence, compilation optimization

吴艺鹏, 霍志坤, 韩孟之. 基于国产GPGPU非一致控制流的分支优化[J]. 计算机工程, 2026, 52(8): 225-237.

WU Yipeng, HUO Zhikun, HAN Mengzhi. Branch Optimization Based on Domestic GPGPU Non-Consistent Control Flow[J]. Computer Engineering, 2026, 52(8): 225-237.

https://www.ecice06.com/CN/Y2026/V52/I8/225

图/表 17

图1 LLVM架构

Fig.1 LLVM architecture

图2 非一致控制流执行过程示例

Fig.2 Example of non-consistent control flow execution procedure

图3 MergeCFG示例

Fig.3 MergeCFG example

图4 MergeCFG合并思想

Fig.4 MergeCFG merges ideas

图5 指令use-def处理

Fig.5 Instruction use-def processing

图6 MergeCFG整体流程

Fig.6 Overall procedure of MergeCFG

图7 连续分支合并优化前后程序的实际执行过程

Fig.7 The actual execution process of the program before and after continuous branch merging optimization

图8 MergeCFG合并流程

Fig.8 MergeCFG merging process

图9 MergeCFG合并应用

Fig.9 MergeCFG merging application

图10 Dgemm用例控制流图优化对比

Fig.10 Comparison of control flow graph optimization for Dgemm use case

图11 codesize变化

Fig.11 codesize variation

参考文献 25

1	庞文豪, 王嘉伦, 翁楚良. GPGPU和CUDA统一内存研究现状综述. 计算机工程, 2024, 50 (12): 1- 15. doi: 10.19678/j.issn.1000-3428.0068694
	PANG W H , WANG J L , WENG C L . Survey on GPGPU and CUDA unified memory research status. Computer Engineering, 2024, 50 (12): 1- 15. doi: 10.19678/j.issn.1000-3428.0068694
2	LINDHOLM E , NICKOLLS J , OBERMAN S , et al. NVIDIA Tesla: a unified graphics and computing architecture. IEEE Micro, 2008, 28 (2): 39- 55. doi: 10.1109/MM.2008.31
3	STEFFEN M, ZAMBRENO J. Improving SIMT efficiency of global rendering algorithms with architectural support for dynamic micro-kernels[C]//Proceedings of the 43rd Annual IEEE/ACM International Symposium on Microarchitecture. Washington D.C., USA: IEEE Press, 2011: 237-248.
4	NUGTEREN C, VAN DEN BRAAK G J, CORPORAAL H. Future of GPGPU micro-architectural parameters[C]//Proceedings of the Design, Automation & Test in Europe Conference & Exhibition (DATE). Washington D.C., USA: IEEE Press, 2013: 392-395.
5	KHORASANI F, GUPTA R, BHUYAN L N. Efficient warp execution in presence of divergence with collaborative context collection[C]//Proceedings of the 48th International Symposium on Microarchitecture. New York, USA: ACM Press, 2015: 204-215.
6	RHU M, EREZ M. CAPRI: prediction of compaction-adequacy for handling control-divergence in GPGPU architectures[C]//Proceedings of the 39th Annual International Symposium on Computer Architecture (ISCA). Washington D.C., USA: IEEE Press, 2012: 61-71.
7	蒋奎. 面向嵌入式系统优化安全加固的程序控制流静态分析关键问题研究[D]. 西安: 西安电子科技大学, 2023.
	JIANG K. Research on key problems of static analysis of program control flow for embedded system optimization security hardening[D]. Xi'an: XIDIAN UNIVERSITY, 2023. (in Chinese)
8	CHEN W K, LI B G, GUPTA R. Code compaction of matching single-entry multiple-exit regions[M]//Static Analysis. Berlin, Germany: Springer, 2003: 401-417.
9	COUTINHO B, SAMPAIO D, PEREIRA F M Q, et al. Divergence analysis and optimizations[C]//Proceedings of the International Conference on Parallel Architectures and Compilation Techniques. Washington D.C., USA: IEEE Press, 2011: 320-329.
10	SAUMYA C, SUNDARARAJAH K, KULKARNI M. DARM: control-flow melding for SIMT thread divergence reduction[C]//Proceedings of the IEEE/ACM International Symposium on Code Generation and Optimization (CGO). Washington D.C., USA: IEEE Press, 2022: 1-13.
11	SMITH T F , WATERMAN M S . Identification of common molecular subsequences. Journal of Molecular Biology, 1981, 147 (1): 195- 197. doi: 10.1016/0022-2836(81)90087-5
12	LATTNER C, ADVE V. LLVM: a compilation framework for lifelong program analysis & transformation[C]//Proceedings of the International Symposium on Code Generation and Optimization. Washington D.C., USA: IEEE Press, 2004: 75-86.
13	LLVM Foundation. The LLVM compiler infrastructure[EB/OL]. [2024-09-20]. https://llvm.org/.
14	NVIDIA. NVIDIA CUDA Toolkit documentation[EB/OL]. [2024-09-20]. https://docs.nvidia.com/cuda/archive/11.2.1/cuda-compiler-driver-nvcc/.
15	LOZANO R C, CARLSSON M, DREJHAMMAR F, et al. Constraint-based register allocation and instruction scheduling[M]//Principles and Practice of Constraint Programming. Berlin, Germany: Springer, 2012: 750-766.
16	杨太龙, 赵红朋, 张磊. 基于国产异构平台的奇异值分解法. 计算机工程, 2024, 50 (9): 216- 225. doi: 10.19678/j.issn.1000-3428.0068183
	YANG T L , ZHAO H P , ZHANG L . Singular value decomposition method based on domestic heterogeneous platforms. Computer Engineering, 2024, 50 (9): 216- 225. doi: 10.19678/j.issn.1000-3428.0068183
17	LIU J , WU Z H , FU D L , et al. HeterPS: distributed deep learning with reinforcement learning based scheduling in heterogeneous environments. Future Generation Computer Systems, 2023 (c): 106- 117.
18	张军, 魏继桢, 沈凡凡, 等. 基于GPGPU-sim的多kernel场景下GPGPU性能优化实验方法. 实验技术与管理, 2024, 41 (7): 87- 93.
	ZHANG J , WEI J Z , SHEN F F , et al. Experimental method for optimizing GPGPU performance in a multiple-kernel environment based on GPGPU-sim. Experimental Technology and Management, 2024, 41 (7): 87- 93.
19	AMD. AMD ROCm^TM Documentation[EB/OL]. [2024-09-20]. https://rocm.docs.amd.com/en/latest/.
20	CYTRON R , FERRANTE J , ROSEN B K , et al. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 1991, 13 (4): 451- 490. doi: 10.1145/115372.115320
21	LLVM PassManager. llvm: : PassManager < IRUnitT, AnalysisManagerT, ExtraArgTs> Class Template Reference[EB/OL]. [2024-09-20]. https://llvm.org/doxygen/classllvm_1_1PassManager.html.
22	HUANG J C, LENG T. Generalized loop-unrolling: a method for program speedup[C]//Proceedings of IEEE Symposium on Application-Specific Systems and Software Engineering and Technology. Washington D.C., USA: IEEE Press, 1999: 51-60.
23	RODRIGUEZ-CANCIO M, COMBEMALE B, BAUDRY B. Automatic microbenchmark generation to prevent dead code elimination and constant folding[C]//Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering. New York, USA: ACM Press, 2016: 132-143.
24	JIN Z M, VETTER J S. A benchmark suite for improving performance portability of the SYCL programming model[C]//Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). Washington D.C., USA: IEEE Press, 2023: 325-327.
25	GitHub. AMD ROCm^TM software[EB/OL]. [2024-09-20]. https://github.com/ROCm/Tensile.

[1]	高山, 王诚昱, 毕成铭, 朱铁英. 基于符号执行的智能合约重入漏洞检测[J]. 计算机工程, 2024, 50(10): 196-204.
[2]	高秀武, 姜军, 白书敬, 黄亮明. 一种加速访存地址计算的编译优化[J]. 计算机工程, 2023, 49(1): 173-180.
[3]	李扬, 戴紫彬, 李军伟. 面向RISC处理器的控制流认证方案[J]. 计算机工程, 2019, 45(12): 134-140,146.
[4]	陈建,沈潇军,姚一杨,邢雅菲,琚小明. 基于表驱动的纯软件签名错误检测算法[J]. 计算机工程, 2018, 44(4): 187-192.
[5]	秦振华,牟永敏. 面向C程序的环形复杂度自动化计算方法[J]. 计算机工程, 2018, 44(12): 102-107,114.
[6]	侯小静,姬孟洛,黄辰林,舒云星,阎奔. 实时控制系统程序模式的WCET自动分析方法[J]. 计算机工程, 2017, 43(8): 56-62,68.
[7]	李双全,杜亚娟,刘凌锋. 空间对接仿真试验台对接机构测控系统设计[J]. 计算机工程, 2017, 43(6): 24-29.
[8]	孙贺,吴礼发,洪征,颜慧颖,张亚丰. 一种结合动态与静态分析的函数调用图提取方法[J]. 计算机工程, 2017, 43(3): 154-162.
[9]	张鹏,朱利,杜小智,贺朝会,陈皓. 基于结构化标签的控制流错误检测算法[J]. 计算机工程, 2016, 42(6): 37-42.
[10]	王磊,侯整风,向润昭,史兆鹏. 基于嵌套复杂度的控制流混淆算法[J]. 计算机工程, 2016, 42(11): 177-181,188.
[11]	廉玉龙,史峥,李春强,王会斌,尚云海. 基于C-SKY CPU的地址立即数编译优化方法[J]. 计算机工程, 2016, 42(1): 46-50.
[12]	叶雁秋,王震宇,赵利军. ARM 架构中控制流完整性验证技术研究[J]. 计算机工程, 2015, 41(3): 151-155,171.
[13]	徐东,狄效国,孟宇龙,冯晓宁. 基于依赖图等价代换的SSDG构建算法[J]. 计算机工程, 2015, 41(12): 91-95,100.
[14]	黄荷洁,康绯,舒辉. 基于动态数据流分析的虚拟机保护破解技术[J]. 计算机工程, 2014, 40(9): 59-65.
[15]	曹晓，李莹. 基于反馈的JCVM指令预调度方案[J]. 计算机工程, 2014, 40(1): 78-82.

选择文件类型/文献管理软件名称

选择包含的内容