| 引用本文: | 李奕瑾,杜绍敏,赵家程,王雪莹,查永权,崔慧敏.基于RISC-V VLIW架构的混合指令调度算法.软件学报,2025,36(9):3937-3953 |
| |
|
| |
|
|
| 本文已被：浏览 2193次 下载 1976次 |
码上扫一扫！ |
|
|
| 基于RISC-V VLIW架构的混合指令调度算法 |
|
李奕瑾1,2,3, 杜绍敏1,3, 赵家程1,2,3, 王雪莹4, 查永权1,2,3, 崔慧敏1,2,3
|
|
1.中国科学院 计算技术研究所, 北京 100190;2.中国科学院大学, 北京 100049;3.处理器芯片全国重点实验室(中国科学院 计算技术研究所), 北京 100190;4.北京邮电大学, 北京 100088
|
|
| 摘要: |
| 指令级并行是处理器体系结构研究的经典难题. VLIW架构是数字信号处理器领域中提升指令级并行的一种常用架构. VLIW架构的指令发射顺序是由编译器决定的, 因此其指令级并行的性能强依赖于编译器的指令调度. 为了探索RISC-V VLIW架构的扩展潜力, 丰富RISC-V生态, 研究RISC-V VLIW架构的指令调度算法优化. 针对单个调度区域, 整数线性规划调度算法能够得到调度最优解但复杂度较高, 表调度算法复杂度较低但无法得到调度最优解. 为了结合两种调度算法的优点, 提出了一种IPC理论模型指导的混合指令调度算法, 即通过IPC理论模型定位到表调度未达最优解的调度区域, 再对该调度区域进一步实施整数线性规划调度算法. 该理论模型基于数据流分析技术协同考虑指令依赖和硬件资源, 能够以线性复杂度给出IPC的理论上界. 混合调度的核心在于IPC理论模型的准确性, 理论模型准确率为95.74%. 在给定的测评基准上, 提出的理论模型应用于混合指令调度时, 能够平均认定94.62%的调度区域在表调度下已达最优解, 因此仅有5.38%的调度区域需再进行整数线性规划调度. 该混合调度算法能够以接近表调度的复杂度达到整数线性规划调度的调度效果. |
| 关键词: RISC-V 超长指令字(VLIW) 整数线性规划(ILP) 表调度 理论模型 |
| DOI：10.13328/j.cnki.jos.007357 |
| 分类号:TP314 |
| 基金项目:新一代人工智能国家科技重大专项(2021ZD0110504); 国家自然科学基金(U23B2020, 62090024, 62302479); 中国科学院计算技术研究所创新课题(E361010, E261110) |
|
| Hybrid Instruction Scheduling Algorithm for RISC-V VLIW Architecture |
|
LI Yi-Jin1,2,3, DU Shao-Min1,3, ZHAO Jia-Cheng1,2,3, WANG Xue-Ying4, ZHA Yong-Quan1,2,3, CUI Hui-Min1,2,3
|
|
1.Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China;2.University of Chinese Academy of Sciences, Beijing 100049, China;3.State Key Lab of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190, China;4.Beijing University of Posts and Telecommunications, Beijing 100088, China
|
| Abstract: |
| Instruction-level parallelism is a fundamental challenge in processor architecture research. Very long instruction word (VLIW) architecture is widely used in the field of digital signal processing to enhance instruction-level parallelism. In VLIW architecture, the instruction issue order is determined by the compiler, making its performance highly dependent on the compiler’s instruction scheduling. To explore the potential of RISC-V VLIW architecture and further enrich the RISC-V ecosystem, this study focuses on optimizing instruction scheduling algorithms for RISC-V VLIW architecture. For a single scheduling region, the integer linear programming (ILP) scheduling can achieve optimal solutions but suffers from high computational complexity, whereas list scheduling offers lower complexity at the cost of potentially suboptimal solutions. To leverage the strengths of both approaches, this study proposes a hybrid instruction scheduling algorithm. The scheduling region where the list scheduling has not reached the optimal solution can be located with the IPC theoretical model, and then the integer linear programming scheduling algorithm further processes the located scheduling region. The theoretical model is based on data flow analysis, accounting for both instruction dependencies and hardware resources, and provides a theoretical upper bound for IPC with linear complexity. The accuracy of the IPC theoretical model is a critical factor for the success of hybrid scheduling and achieves 95.74% accuracy in this study. On the given benchmark, the IPC model identifies that 94.62% of scheduling regions has reached optimal solution with list scheduling, leaving only 5.38% requiring further refinement with ILP scheduling. The proposed hybrid scheduling algorithm achieves the scheduling quality of ILP scheduling while maintaining a complexity comparable to that of list scheduling. |
| Key words: RISC-V very long instruction word (VLIW) integer linear programming (ILP) list schedule theoretical model |
|
|
|
|
