基于RISC-V VLIW架构的混合指令调度算法
作者:
作者单位:

作者简介:

通讯作者:

赵家程,E-mail:zhaojiacheng@ict.ac.cn

中图分类号:

TP314

基金项目:

新一代人工智能国家科技重大专项(2021ZD0110504); 国家自然科学基金(U23B2020, 62090024, 62302479); 中国科学院计算技术研究所创新课题(E361010, E261110)


Hybrid Instruction Scheduling Algorithm for RISC-V VLIW Architecture
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    指令级并行是处理器体系结构研究的经典难题. VLIW架构是数字信号处理器领域中提升指令级并行的一种常用架构. VLIW架构的指令发射顺序是由编译器决定的, 因此其指令级并行的性能强依赖于编译器的指令调度. 为了探索RISC-V VLIW架构的扩展潜力, 丰富RISC-V生态, 研究RISC-V VLIW架构的指令调度算法优化. 针对单个调度区域, 整数线性规划调度算法能够得到调度最优解但复杂度较高, 表调度算法复杂度较低但无法得到调度最优解. 为了结合两种调度算法的优点, 提出了一种IPC理论模型指导的混合指令调度算法, 即通过IPC理论模型定位到表调度未达最优解的调度区域, 再对该调度区域进一步实施整数线性规划调度算法. 该理论模型基于数据流分析技术协同考虑指令依赖和硬件资源, 能够以线性复杂度给出IPC的理论上界. 混合调度的核心在于IPC理论模型的准确性, 理论模型准确率为95.74%. 在给定的测评基准上, 提出的理论模型应用于混合指令调度时, 能够平均认定94.62%的调度区域在表调度下已达最优解, 因此仅有5.38%的调度区域需再进行整数线性规划调度. 该混合调度算法能够以接近表调度的复杂度达到整数线性规划调度的调度效果.

    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.

    参考文献
    相似文献
    引证文献
引用本文

李奕瑾,杜绍敏,赵家程,王雪莹,查永权,崔慧敏.基于RISC-V VLIW架构的混合指令调度算法.软件学报,2025,36(9):3937-3953

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2024-08-23
  • 最后修改日期:2024-10-15
  • 录用日期:
  • 在线发布日期: 2024-12-10
  • 出版日期: 2025-09-06
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号