Page 109 - 《软件学报》2020年第9期

2730 Journal of Software 软件学报 Vol.31, No.9, September 2020

4.1 整数线性规划模型
首先给出构建 ILP 模型所需的两个定理以及符号(见表 1).
Table 1 Notations and definitions
表 1 符号及定义
符号 定义
|V| 图 G 中节点的个数
E 图 G 中的边的集合
capacity 磁带上域的个数
D 数据的集合
|D| 数据的个数
e(i,j) 从 i 到 j 的边
X i,l =1,当且仅当指令 i 在第 l 步执行
Y k,p =1,当前仅当数据 k 放置在位置 p 中
SCH i 指令 i 在第 SCH i 步调度执行
access(i) 被节点 i 访问的数据
pos off 磁带上每个域的偏移地址列表
offset(i) 指令 i 访问数据在磁带上的偏移位置
position(l) 第 l 步被调度的访存指令所访问的数据的偏移位置
shift(l) 第 l 步到第 l+1 步的移动次数

定理 1. 假设 u 和 v 是正整数变量,x 是一个二值变量.描述“u=v,iff x=1”可以被线性建模为
−
u ≥ v + (1 x × ) B ,
−
u ≤ v + (1 x × ) B ,

u ≥ 0,
u ∈ , Z
其中,B 是一个大数.
定理 2. 假设 a,b,c 是正整数变量,则描述“c≥|a−b|”可以被线性建模为
c≥ a − , b
c≥ b − , a
c∈ , Z
min( ).c
根据上述定理,可以通过对指令约束、依赖约束和数据放置约束进行建模,从而构建 ILP 模型.
(1) 指令约束
每一条访存指令在每一步都有执行和不执行两种状态,因此,定义一个二值变量 X i,l 表示访存指令 i 在第 l
步是否执行,其中,i 表示访存指令,l 表示第几步.对于任一条指令 i,在第 l 步执行时,X i,l =1;否则,X i,l =0.
目标系统架构是单核处理器,因此指令调度步骤的上限为访存指令的总数量.假设共有|V|条访存指令,则指
令调度上限为|V|.
对于指令约束,分为两种.
• 第 1 种是每一步至少有一条访存指令执行,该约束可以线性表示为
∑ ||V i= 1 X ≤ 1,l ∈ [1,|V |] (1)
, il
• 第 2 种是每条访存指令只能执行一次,将其线性表示为
∑ ||V l= 1 X , il = 1,i∈ [1,|V |] (2)
(2) 依赖约束
因为一些访存指令之间存在依赖,如写后读、读后写、写后写等依赖.所以进行访存指令调度时,需要满足
所有依赖关系.也就是说,如果访存指令 j 依赖于访存指令 i,即 i→j,那么访存指令 i 需要在访存指令 j 之前调度
执行.定义变量 SCH i ,表示访存指令 i 在第 SCH i 步调度执行.对于任意访存指令 i,SCH i 可以被线性表示为