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

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

类型指令, 如表 1 中 LOAD 执行单元仅能执行 LOAD 类型和 ALU 类型的指令.
执行完一个调度区域 R 中指令所需的 cycle 受源程序、编译器以及硬件资源这 3 个方面的影响, 具体来说是
受指令类型、指令间依赖关系和硬件执行单元的限制. 每条指令有 Issue Cycle、Execute Unit、Execute Cycle、
Available Units 这 4 个属性. Issue Cycle 为该指令的发射 cycle; Execute Unit 指的是当前指令分配的执行单元;
Execute Cycle 是每条指令执行所需的 cycle 数, 该属性对同一条指令而言是确定的常量; Available Units 指当前指
令能够在哪些执行单元上执行, 其值为一个整数集合. 例如, 一条 ALU 指令的 Available Units 为{0, 1, 2}, 表示该
指令可以在 0, 1, 2 这 3 个执行单元上执行. 当硬件架构固定时, Available Units 对每类指令也是固定的.
min maxIssueCycle(x), 即求得一个调度策略, 使得调度区域 R 内所有指令 Issue
指令调度的最优化目标为
s∈S x∈I
Cycle 的最大值最小, 其中 I 表示调度区域 R 内所有指令的集合. 下面给出该最优化问题需要满足的约束条件.
(1) 指令间依赖关系约束
指令间的依赖关系分为 4 种: 数据依赖、反依赖、输出依赖和控制依赖. 定义指令 x 和指令 y 之间的依赖距
−−→ −−→
离为 d x,y , 当指令 x 和指令 y 之间为数据依赖时 d x,y = 1, 当指令 x 和指令 y 之间为反依赖、输出依赖或控制依赖时
−−→
d x,y = 0. 不同依赖类型导致指令间执行顺序需要满足的约束也有所区别: 如果指令 x 和指令 y 之间存在数据依赖,
则要求满足 IssueCycle(x) < IssueCycle(y); 如果指令 x 和指令 y 之间存在输出依赖、反依赖或者控制依赖, 则要求
IssueCycle(x) ⩽ IssueCycle(y).
满足
(2) 硬件资源约束
VLIW 架构的硬件资源约束源自同一个 cycle 中最多能够执行的不同类型指令的数量, 这受限于硬件的执行
单元数量及类型, 对不同的 VLIW 架构可以得到不同的约束. 以图 1 中的硬件架构配置为例, 其对应的约束如下:

∀x,y ∈ I t , ExecuteUnit(x) , ExecuteUnit(y) (1)
其中, I t 表示指令集合 I 中任意 t 时刻发射的指令, 即对于任意在 t 时刻发射的指令 x 和指令 y, 其分配的执行单元
不同.
结合上述两个约束及本文的最优化目标, 本文的最优化问题可以总结为公式 (2)、(3):
最优化目标:

min maxIssueCycle(x) (2)
s∈S x∈I
约束条件:

 −−→
 ∀x,y ∈ I, IssueCycle(x)+d x,y ⩽ IssueCycle(y)

(3)

 ∀x,y ∈ I t , ExecuteUnit(x) , ExecuteUnit(y)

4.2 表调度算法的启发式规则
第 4.1 节的规划调度算法由于遍历了所有满足约束的情况, 因此能得到调度单元内的最优解, 但复杂度较高.
因此实际编译器中常使用表调度算法进行指令调度. 但是现有表调度的启发式规则仅考虑指令依赖关系, 如入度、
出度等, 而没有考虑硬件资源限制, 本文从 RISC-V VLIW 架构的硬件资源限制出发, 提出了硬件资源适配的启发
式规则, 从而提升表调度算法的性能.
当前通用的启发式规则中只考虑了关键路径的深度、出度等概念, 并没有考虑硬件资源相关的优先级. 结合
硬件执行单元的实际情况进行考虑, LOAD 单元能够执行 LOAD 指令和 ALU 指令, 但是反过来不成立, 即 ALU
单元仅能执行 ALU 指令. 这说明 LOAD 指令执行受到的限制更多, 因此在同等条件下, 应先调度受限制更多的
LOAD 指令. 该条规则适用于满足“LOAD/STORE 计算资源比 ALU 紧张”特征的硬件架构, 但该规则不一定对任
何调度区域都有效果, 只有在调度区域中 LOAD/STORE 类指令会互相抢占资源的情况下才可能会有优化作用,
因此启发式规则一般看整体的统计效果.
对于本文架构, 根据硬件架构特点为表调度算法添加启发式规则如下.
● 规则 1: 优先调度 LOAD/STORE 类指令.