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

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

shift(l)=|position(l+1)−position(l)| (15)
该公式可以根据定理 2 重写为线性公式,如下:
shift(l)≥position(l+1)−position(l) (16)
shift(l)≥position(l)−position(l+1) (17)
shift(l)∈Z (18)
(4) 目标函数.
整数线性规划的目标函数是总移动次数最小,线性公式表示为
min ∑ || 1V − shift ( )l (19)
l= 0
4.2 生成指令调度和数据放置(GISDP)算法
本节提出了一个启发式算法——生成指令调度和数据放置(GISDP)算法,该算法可以生成一个指令调度和
数据放置方案,使得总移动次数达到近似最优.由于提出的 GISDP 算法基于赛道存储技术的存储器,所以适用于
本文所提到的磁畴壁存储介质的存储器,也同样适用于斯格明子介质的存储器.
GISDP 算法是一个三段式算法,其主要思想是:首先由算法 1 根据 IAFG G 同时生成指令调度序列和数据放
置策略;然后,算法 2 在算法 1 结果的基础上对数据放置进行改进;最后,算法 3 根据算法 2 改进的结果对指令调
度进行改进.
在介绍 GISDP 算法细节之前,先介绍等价类的概念.在有多个读/写头的磁畴壁存储器上,磁带上的域被 m
个读/写头平均分成 m 段,每段都有相同的偏移地址.因此在任何时刻,m 个读/写头所处域的偏移地址相同.例如:
假设 P 和 Q 分别是读/写头 port1 和 port3 所管辖段中域的集合,那么如果 P 中的域 p 和 Q 中的域 q 有相同的偏
移位置,则域 p 和域 q 是等价的,即,数据放在域 p 和放在域 q 中的效果是一样的.由于读/写头的数量为 m,因此
等价类的大小是 m.
GISDP 算法第 1 部分(算法 1)的主要思想是:将需要访问但还未被放置的数据放置在读/写头当前所指向的
域中,如果当前所有读/写头指向的域均已放置数据,那么进行移动操作,使得读/写头和相邻的下一个域对齐,将
数据放置到距离读/写头最近的空闲域中.然后再将访问该数据且不依赖于其它未执行指令的所有指令进行调
度.如算法 1 所述,输入为 IAFG G 和目标系统架构;输出为一个指令调度 sch、一个数据放置 place、移动次数
shift、一个记录产生移动操作的连续访问的数据对列表 shift_data、一个记录产生移动操作的移动次数的列表
shift_count.
算法第 1 行,统计 G 中入度为 0 的指令和不为 0 指令及其入度,分别存入列表 list0 和 list1 中;在算法初始
阶段,指令调度 sch 和数据放置 place 为空,并且所有 port 均指向偏移位置为 0 的域处,此时的状态需要执行第 6
行~第 9 行,随机选取满足条件的指令调度,并把指令所访问数据放置在此时 port 所指向域中的任一空闲域,同时
更新列表 list0,list1 以及数据 D 集合.另一种状态,在 port 所指向域中有数据且 list0 中有访问这些数据的指令时,
则执行第 5 行.当以上两种状态下均未在 list0 中找到可调度指令,则要执行第 11 行,进行移动操作之后的状态将
会是前两种状态中的一种,则重复执行第 4 行~第 9 行.在数据 D 集合为空的情况下,说明数据均已被放置.接下
来只需要将剩余指令调度完成.调度过程中,先调度访问当前 port 所指向域中数据的指令,即第 15 行;没有满足
条件的指令,则需要执行第 17 行和第 18 行,调度 list0 中访问距离当前域最近的域中数据的指令.直至所有指令
调度完成.
生成了调度 sch 和数据放置 place 后,执行第 21 行,将统计得到总移动次数 shift,产生移动操作的连续访问
的数据对,存入列表 shift_data,及数据对所对应移动次数,存入列表 shift_count 进行输出.
算法 1. GISDP 算法第 1 部分——由 IAFG 同时生成调度和数据放置.
输入:一个 IAFG G=〈V,E,D〉;
磁带的容量 N,M 个读/写头;
输出:一个指令调度 sch;