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

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

● 规则 2: 优先调度出度大的指令.
● 规则 3: 优先调度关键路径上的指令.
从图 3 的指令 DAG 图可以看出, 在计算调度优先级时, 由于指令 0–4 的出度和深度都相同, 在原始启发式规
则下优先级相同, 因此若仍按照原始指令顺序调度, 图 3 中的 6 条指令将打包为 4 个指令包, 分为 4 个 cycle 执行,
如图 3(a) 所示. 在增加了“优先调度 LOAD/STORE 类指令”的启发式规则后, 由于指令 0–4 的出度和深度都相同,
而指令 3、4 为 LOAD 指令, 指令 0、1、2 为 ALU 指令, 若优先考虑 LOAD/STORE 类型指令, 则调度顺序变为
{3, 4, 0, 1, 2}, 图 3 中的 6 条指令打包为 3 个指令包, 分为 3 个 cycle 执行, 如图 3(b) 所示. 可以看出, 在增加了新
的启发式规则后, 执行所需 cycle 从 4 减少为 3, IPC 从 1.5 提升为 2.0.

0: A 1: A 2: A 3: L 4: L 0: A 1: A 3: L 2: A 4: L

5: S 5: S

(a) 未增加启发式 (b) 增加启发式
图 3 指令调度结果

5 IPC 理论模型指导的混合指令调度算法

第 4 节给出的规划调度能够在一个调度区域内求得调度最优解, 但复杂度较高; 表调度算法虽然复杂度较低,
但无法确保得到最优解. 为了能够以较低的复杂度得到最优解, 本节提出了 IPC 理论模型指导的混合指令调度算
法. 该混合指令调度算法的流程图如图 4 所示.

开始 表调度
IPC 是 表调度解 调度区域
调度区域 相等 内最优解
IPC 否
理论模型
规划调度 结束

图 4 混合指令调度算法流程图

这里需要指出的是, 理论模型得到的 IPC 上界并非上确界. 也就是说, 对于一个调度区域而言, 如果表调度的
解对应的 IPC 等于理论模型给出的 IPC, 则说明表调度在该调度区域上得到了最优解. 反之, 如果不相等, 并不意
味着表调度得到的解一定不是最优解. 也就是说, 混合调度中需要再次进行规划调度的调度区域有可能已经得到
了最优解.

5.1 基于数据流的 IPC 理论模型
该混合调度的核心在于 IPC 理论模型. 本文提出的 IPC 理论模型从指令依赖约束和硬件资源约束出发, 基于
编译技术中经典的数据流分析, 可以以 O(n) 复杂度给出一个调度区域 R 内的 IPC 上界. 由第 4 节可知, 由于一个
调度区域内的指令是固定的, 求一个调度区域 R 内 IPC 的最大值等价于求调度区域的 cycle 的最小值, 即要对调
度区域 R 的 cycle 计算下界.
d x,y > 0 的必经指令集合, 用
我们用 A[x] 表示指令 x 的所有依赖距离 −−→ B[x] 表示指令 x 的所有依赖距离 −−→
d x,y ⩾ 0
的必经指令集合, pred[x] 表示指令 x 所有前驱指令的集合. 则根据数据流的顺序求得 A[x] 和 B[x] 的公式为: