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

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

∪ −−→
A[x] = (B[p]∪( d p,x > 0?{p} : ∅)) (4)
p∈pred[x]

∪
B[x] = A[x]∪{x}∪ {p} (5)
p∈pred[x]
一个调度区域 R 中的指令可以表示为集合 (i, j, k, l), 分别表示 R 中 ALU、LOAD、STORE、JUMP 这 4 种类
型指令的数量. 由于不同的执行单元支持的指令类型不同, 因此在进行指令调度时首先需要对资源约束进行考虑.
若只考虑指令的数量和种类而不考虑指令间依赖关系, 则具体到本文架构 (图 1) 完成调度区域 R 中指令所需的最
小 cycle 数 φ(i, j,k,l) 的计算公式为:
( )
i+ j+k
φ(i, j,k,l) = max , j,k,l (6)
3
定义指令节点 x 的最小发射 cycle, 简记为 MIC[x], 表示指令 x 的最小发射 cycle, 即该指令最早能够发射的
cycle. 则根据必经指令集合 A[x] 和 B[x] 可以计算出 MIC[x].

−−→
MIC[x] = max (MIC[p]+d p,x , φ(A[x]) + 1 , φ(B[x])) (7)
p∈pred[x]
定义一个调度区域 R 的最小发射 cycle 为该调度区域内各指令节点最小发射 cycle 的最大值, 即:

MIC[R] = maxMIC[x] (8)
x∈I
基于必经指令集合公式 (4)、(5) 和 MIC 公式 (6)–公式 (8), 本文提出了一种线性复杂度的 IPC 理论模型, 该算
法可以给出单个调度区域内的 cycle 下界, 即 IPC 上界. 注意这里的下 (上) 界非下 (上) 确界.

5.2 IPC 理论模型计算示例
下面通过图 5 的 3 个例子给出根据必经指令集合公式 (4)、(5) 及 MIC 公式 (6)–公式 (8) 计算 cycle 下界的
示例.

MIC=1 0: A
→
d=1
MIC=2 1: A
MIC=1 MIC=1 MIC=1 MIC=1 MIC=1 MIC=1
→
d=1
0: L 1: L 2: L 0: A 1: S 2: S
MIC=3 2: A 3: A MIC=1
→ → → → → →
d=1 d=1 d=1 d=1 d=1 d=1
→ →
d=1 d=1
MIC=4 4: A 3: S EXIT
MIC=4 MIC=3
(a) 资源约束计算示例 (b) 前驱节点约束计算示例 (c) 虚拟退出节点计算示例
图 5 指令节点 MIC 值计算示例

(1) 资源约束计算
图 5(a) 中节点 4 的 MIC 值取决于其直接前驱节点 2 和节点 3 的 MIC 值, 因此节点 4 的 MIC 为 4.
(2) 前驱节点约束计算
图 5(b) 中节点 3 的 MIC 值取决于所有前驱指令类型. 因为节点 0–2 为 3 条 LOAD 指令, 因此至少需要 3 个
cycle 完成 0–2, 因此节点 3 的 MIC 为 4.
(3) 虚拟退出节点的计算
图 5(c) 中由于不存在统一的退出节点, 无法根据节点的 MIC 值给出 DAG 图的 MIC 值. 因此通过引入虚拟退
出节点这一编译器的常用技术来得到 DAG 图的 MIC 值. 根据节点 0–2, 可得虚拟退出节点的 MIC 值为 3.