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

许瑞 等:面向多读/写头磁畴壁存储器的优化研究 2731

SCH = i ∑ ||V l= 1 X × , i l , l i∈ [1,|V |] (3)
如果访存指令 i 与 j 之间存在依赖关系,即在 IAFG G 中存在 e(i,j)∈E,那么该依赖关系可以表示为
SCH i <SCH j ,e(i,j)∈E (4)
表示访存指令 i 要在访存指令 j 之前调度执行,因此可以满足其依赖关系.
(3) 数据放置约束.
定义一个二值变量 Y k,p ,其中,k 表示数据,p 表示磁畴壁存储器中的域.Y k,p 表示数据 k 放置在域 p 处.当数据
k 放置在域 p 处时,Y k,p =1;否则,Y k,p =0.假设一条磁带有 capacity 个域,那么每个数据会有 capacity 种放置的方法.
首先,每个数据必须放置在磁带的域中,该约束被线性表示为
∑ capacity− 1 Y , kp = 1,k ∈ D (5)
p=
0
不失一般性,每个域中最多只能放一个数据.当数据量小于磁带容量 capacity 时,有些域中不放置数据.假设
有|D|个数据需要被访问,那么将有|D|个数据需要被放在磁带的域中,该约束被线性表示为
∑ kD Y , kp ≤ 1, p∀∈ [0,capacity ) (6)
∈
假设数据量不会超过磁带容量 capacity,该约束线性表示为
kD∈ ∑∑ capacity− 1 Y , kp ≤ capacity (7)
p=
0
为了建模移动次数,需要知道指令调度、访存指令访问的数据以及数据放置位置.也就是说,需要知道每一
步所调度的访存指令访问的数据放置在磁畴壁存储器的磁带上哪个域中.因为在磁畴壁存储器中有两个读/写
头进行数据的读/写,分别为 port0 和 port1.并且磁带的前半部分域由 port0 进行访问,磁带的后半部分域由 port1
进行访问,因此需要建模每个位置与其对应读/写头的偏移位置.例如,磁带上有 8 个域,分别编号为域 0~域 7.
port0 访问域 0~域 3,port1 访问域 4~域 7.初始状态下,port0 与域 1 对齐,port1 与域 5 对齐.对于 port0 来说,域 1
是第 1 个位置;对于 port1 来说,域 5 是第 1 个位置.如果域 1 中的数据被访问之后,立即访问域 5 中的数据,那么
就不需要移动操作,此时移动次数为 0.如果使用的不是偏移位置进行计算,则是 5−1=4,会出现计算错误.因此,
建模移动次数需要获得偏移位置.
⎡ capacity capacity ⎤
定义一个列表 pos off 记录每个域的偏移位置,即 pos = 0,1,2,..., − 1,0,1,2,..., − 1 .例如:如果
off ⎢ ⎣ 2 2 ⎥ ⎦
磁带容量为 8,则 pos off =[0,1,2,3,0,1,2,3].
对于每个数据 k 和访存指令 i,如果访存指令 i 访问数据 k,那么数据 k 和访存指令 i 直接的映射关系为
k=access(i) (8)
定义 offset(i)表示访存指令 i 所访问数据的偏移位置,该约束可以表示为
||V
offset ()i = i= ∑∑ capacity− 1 Y access (),i p × pos off [ ]p (9)
p=
0
0
如果变量 X i,l =1 表示访存指令 i 在第 l 步调度执行,定义 position(l)来表示第 l 步调度执行的访存指令 i 所
访问数据的偏移位置,它可以表示为
position(l)=offset(i),iff X i,l =1 (10)
也就是说,当访存指令 i 在第 l 步调度执行时,就将访存指令 i 所访问数据的偏移位置赋值给 position(l).不
幸的是,该表达式是非线性的.根据定理 1,它可以线性表示为
position(l)≥offset(i)+(1−X i,l )×B (11)
position(l)≤offset(i)+(1−X i,l )×B (12)
position(l)≥0 (13)
position(l)∈Z (14)
其中,B 是一个大数.
假设 shift(l)记录的是从当前步 l 到下一步 l+1 所需要移动的次数,那么从第 l 步到第 l+1 步的移动次数可以
表示为