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

作者简介:

通讯作者:

赵家程,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 classic problem in the research of processor architecture. VLIW architecture is a common architecture to enhance Instruction level parallelism in the field of digital signal processor. The instruction issue order is determined by the compiler for VLIW architecture, so VLIW’s Instruction level parallelism performance strongly depends on the instruction scheduling of compiler. In order to explore the performance poteneial of RISC-V VLIW architecture and enrich the RISC-V ecosystem, this paper studies the optimization of instruction scheduling algorithm of RISC-V VLIW architecture. For a single scheduling region, the integer linear programming scheduling can obtain the optimal scheduling solution with high complexity, and the list scheduling, which has low complexity, cannot obtain the optimal scheduling solution. In order to combine the advantages of the two scheduling algorithms, this paper proposes an IPC theoretical model guided hybrid instruction scheduling algorithm. The scheduling region where the list scheduling has not reached the optimal solution can be located with 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 and considers both instruction dependency and hardware resources, and can give the theoretical upper bound of IPC in linear complexity. The core of hybrid scheduling lies in the accuracy of IPC theoretical model, which is 95.74% in this paper. On the given benchmark, the IPC theoretical model can identify that 94.62% of the scheduling region has reached the optimal solution under list scheduling, so only 5.38% of the scheduling region needs to be further scheduled by integer linear programming. The hybrid scheduling algorithm can achieve the scheduling effect of integer linear programming scheduling with the complexity close to that of list scheduling.

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

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

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

京公网安备 11040202500063号