Page 27 - 《软件学报》2025年第9期

3938 软件学报 2025 年第 36 卷第 9 期

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

1 引 言

RISC-V 是一种开放的、基于精简指令集 (RISC) 的架构, 其设计目标是提供一种灵活、可扩展且高性能的
[1]
[6]
计算机体系结构, 适用于各种应用场景. 近年来, RISC-V 发展迅速, 在通用 CPU [2−5] 、开源 GPU 等多个领域获得
成功的应用. 目前, 超长指令字 (very long instruction word, VLIW) 架构在数字信号处理器 (digital signal processor,
[7]
[8]
DSP) 领域有着广泛的应用, 如高通 Hexagon 、德州仪器 [9] 、魂芯 [10] 、Kalray [11] 等. 其中, 高通 Hexagon 芯片可应
用于图像处理、物联网等领域, Kalray K200 数据加速卡可用于高性能计算. 与通用领域相比, DSP 芯片需要较低
的功耗和较高的处理速度, VLIW 作为一种无需硬件调度器的多核架构, 能够在保持低功耗的同时得到较高的处
理速度. 因此, 研究 RISC-V 的 VLIW 架构能够扩展 RISC-V 的使用场景, 促进 RISC-V 在 DSP 领域, 如移动设备、
物联网设备、通信基站等嵌入式系统的发展, 提高 RISC-V 处理器的可用性及覆盖面, 促进 RISC-V 的生态建设.
然而由于 RISC-V 的研究还在发展中, 目前少有使用 RISC-V 指令集进行 VLIW 架构处理器实现的工作. 文献 [12]
的工作虽然提出了基于 RISC-V 的 256 比特 VLIW 架构, 但是该工作关注硬件设计且是定长 VLIW, 并未对 RISC-V
指令集的编译工具链及指令调度相关问题进行研究. 定长 VLIW 需要插入冗余空指令, 会造成代码膨胀. 代码膨胀
会导致内存占用增加, 造成存储空间和计算资源的浪费, 降低设备的整体效能. 同时, 可能会导致指令缓存的命中
率下降, 进而影响性能. 而变长 VLIW 通过指令编码显式标记指令包的结束, 无需插入空指令, 能够显著降低代码
体积, 从而避免存储空间浪费, 增加指令缓存命中率, 提升整体性能.
VLIW 架构拥有多个执行单元, 如何通过指令调度有效利用 VLIW 的指令级并行能力是发挥 VLIW 架构性能
的关键. 指令调度必须考虑数据依赖性及硬件资源限制, 以最小化指令序列执行所需的 cycle. 指令调度后, 指令执
行顺序重新排列, 无依赖关系的指令被分组打包在一起发射执行, 同一个指令包 (也称指令 bundle) 内的指令并行
执行, 指令的发射和执行均以指令包为单位. 对于 VLIW 处理器, 一般采用表调度方法结合启发式规则的方式进行
指令调度.
为了探索 RISC-V 在 VLIW 架构的扩展潜力, 本文研究该架构的指令调度算法优化. 为了给该研究提供基础,
本文提出了基于 RISC-V 的变长 VLIW 架构, 并为此架构实现了相应的工具链及模拟器. 指令调度的效果与调度
区域的扩展和单个调度区域的调度相关, 本文专注于研究单个调度区域的指令调度. 常用的指令调度算法有整数
线性规划调度 (简称为规划调度) 和表调度. 这两种调度算法的优缺点如下: 针对单个调度区域, 规划调度能够得
n O(n ) 但无法得到最优解. 本文期望结合两种调度算法的优点, 设计一
2
到最优解但复杂度为 O(2 ), 表调度复杂度为
种新的调度算法, 使得针对单个调度区域, 既能确保得到最优解, 又能保证复杂度可接受. 假设能够判断一个调度
区域的表调度结果是否为最优解, 对是最优解的调度区域采用表调度结果, 对不是最优解的调度区域再进行规划
调度, 则可以降低计算最优解的复杂度. 由于调度的目标为最大化每周期指令 (instructions per cycle, IPC), 本文拟
用 IPC 判断调度解是否达最优. 因此, 为了以较低的复杂度得到单个调度区域的最优解, 本文提出了一种 IPC 理论