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

李奕瑾 等: 基于 RISC-V VLIW 架构的混合指令调度算法 3939

模型指导的混合指令调度算法. 该 IPC 理论模型基于数据流分析技术协同考虑指令依赖和硬件资源, 能够以
O(n) 复杂度给出 IPC 的理论上界. 混合调度首先对调度区域进行 IPC 理论模型分析和表调度, 将表调度结果的
IPC 与 IPC 理论模型所得 IPC 不一致的调度区域进一步实施规划调度. 混合调度通过 IPC 理论模型的指导, 能够
以接近表调度的复杂度达到调度最优解.
为了实现混合调度, 本文设计了与该架构适配的规划调度和表调度算法. 现有的规划调度算法无法直接用于
该架构的原因在于, VLIW 架构多用于 DSP 领域, 其执行单元多为功能受限的, 即单个执行单元只能执行特定类
型的指令, 而不能执行所有类型指令. 现有的表调度算法的启发式规则仅考虑了指令依赖关系 (如入度、出度等),
而没有考虑硬件资源限制. 本文首先提出了 RISC-V VLIW 架构的整数线性规划调度算法 (简称为规划调度算法)
和表调度算法. 在规划调度方面, 本文为该架构设计了新的约束求解条件和最优化目标. 在表调度方面, 本文从该
架构的硬件资源限制出发, 提出了硬件资源适配的启发式规则, 提升表调度算法的性能.
本文的主要贡献如下.
(1) 设计了基于 RISC-V 的变长 VLIW 扩展, 实现了相应的指令编码、工具链和模拟器支持.
(2) 针对 RISC-V VLIW 架构提出了规划调度算法, 并基于表调度算法提出了该 VLIW 架构适配的启发式
规则.
(3) 针对规划调度复杂度过高和表调度无法得到最优解的问题, 提出了 IPC 理论模型指导的混合指令调度算
法. 混合调度通过 IPC 理论模型的指导, 能够以接近表调度的复杂度达到规划调度的调度效果.
本文第 2 节介绍相关工作. 第 3 节对基于 RISC-V 的 VLIW 架构进行介绍, 包括整体架构设计和指令集
VLIW 扩展. 第 4 节介绍规划调度算法及表调度算法的启发式规则优化. 第 5 节介绍 IPC 理论模型指导的混合指
令调度算法. 第 6 节介绍实验环境及分析实验结果.

2 相关工作

2.1 VLIW 指令调度
指令调度问题本身是一个复杂的问题, 已经证明在任意约束下自动找到代码序列的最优调度结果是 NP 完全
问题 [13] , 要确定最佳调度方案, 必须检查所有合法的调度. 只有在确定 1 个 cycle 的指令延迟时, 问题才能在小于
指数的时间中得到最优解 [14] . 指令调度分为编译时调度和运行时动态调度. 编译时调度偏重于静态分析和优化,
而运行时调度则通过动态决策来适应实际执行情况. 一般来说, 运行时调度能够获取当前的执行环境和资源现状,
如数据的实时可用性等, 因此相比于编译时能够进行更优的调度. 但运行时调度需要硬件调度器的支持. 因此,
VLIW 架构只进行编译时调度. 对于 VLIW 处理器, 由于指令调度问题本身的复杂性, 在编译器中一般采用表调度 [15]
方法进行简化求解, 并添加启发式规则对调度进行优化. 目前指令调度方式根据调度方法是否跨越基本块边界, 可
分为局部调度和全局调度两类; 根据是否在寄存器分配之前进行调度, 可分为前遍调度和后遍调度两类 [16] . 对于
算法决策应用的启发式规则, 一般需要考虑关键路径、依赖关系. 除使用表调度方法外, 也可采用数学建模和动态
规划 [17] 等方法, 但是由于其复杂度太高无法直接用于编译器中.
局部调度多以基本块作为调度单元, 但由于分支指令的存在基本块往往较小, 难以实现足够的指令级并行性
来充分利用 VLIW 处理器的多个执行单元. 因此全局调度尝试将多个执行效率高的基本块合并成一个更大的调度
单元或进行跨区域调度, 例如轨迹调度 [18,19] 、超块 (superblock [20] /hyperblock [21] ) 调度等. 该类算法可以扩大指令调
度空间, 但是会使控制流更加复杂, 特别是当存在复杂的控制流结构时会增加分支预测错误的风险, 增加编译器的
处理时间和资源消耗. 由于全局调度专注于通过某些编译技术跨越或合并调度区域, 对于单个调度区域的调度算
法仍然是局部调度算法. 因此, 本文专注于局部调度研究, 其与全局调度的跨区域调度技术是正交的.
指令调度多以表调度算法作为基础算法, 包括表调度算法的各种变体, 变体的核心在于不同的启发式规则设
计. 启发式规则包括静态启发式和动态启发式两类, 静态启发式即根据程序依赖特征和硬件架构特征预先定义启
发式规则, 动态启发式是在调度过程中调整启发式规则. 常用的动态启发式包括基于遗传算法 [22] 、进化算法 [23] 、