Page 113 - 《软件学报》2020年第9期
P. 113
2734 Journal of Software 软件学报 Vol.31, No.9, September 2020
算法 2. GISDP 算法第 2 部分——修改数据放置.
输入:一个 IAFG G=〈V,E,D〉;
磁带的容量 N,M 个读/写头;
算法 1 的输出的 sch,place,shift,shift_count,shift_data;
输出:比算法 1 总移动次数少的数据放置顺序 place;
总的移动次数 shift;
一个记录移动次数的列表 shift_count.
1. shift←统计 shift_data 中每对连续访问数据的连续次数;
2. relate←计算 shift_data 中的每对连续访问数据的相关度,并根据相关度降序排序数据对;
3. while relate[i]>1 do
4. if 数据对(m,n)不在同一个位置段 then
5. 将数据 m 与在本位置段中和数据 n 偏移位置相同的数据 r 交换位置;
6. 对所有段中,将 r 所在域(及其等价域)到 m 所在域(及其等价域)之间的数据(包括 r,不包括 m),向 r
所在域的方向循环移动一个位置;
7. else then
8. 将其他任意一个位置段中与 n 偏移位置相同的数据 r 与 m 交换位置;
9. 对所有段中,将 m 原来放置域(及其等价域)到 m 当前放置域(及其等价域)之间的数据,向 m 原来放
置域的方向循环移动一个位置;
10. 统计交换位置后的移动次数;
11. if 本次统计移动次数<shift then
12. shift=本次统计移动次数;place=本次放置结果;
13. 重新统计相关度,更新 relate;i=0;
14. else then
15. shift 不变;place=之前放置结果;i=i+1;
16. end if
17. end while
18. return place,shift.
在算法 2 对数据的放置进行改进之后,算法 3 根据算法 2 的数据放置和 IAFG G 对指令进行了重调度,以获
得与新数据放置策略相适宜的指令调度.算法 3 的主要思想是:尽量将访问当前 port 所在域中数据的指令进行
调度,没有可调度的指令则移动一个位置.当 port 移动到有指令可调度的域的时候,将会更新 port 的状态.最后统
计该调度下的移动次数,与重调度之前的移动次数进行比较,如果移动次数减少,则保留此次的调度;否则不更
新调度.
算法 3. GISDP 算法第 3 部分——改进指令调度.
输入:一个 IAFG G=〈V,E,D〉;
磁带的容量 N,M 个读/写头;
算法 1 的输出 sch,算法 2 的输出 place,shift;
输出:一个指令调度列表 sch;
总的移动次数 shift.
1. list0←统计入度为 0 的节点;list1←统计入度不为 0 的节点;
2. i=1;
3. while len(sch)<len(V) do
4. if port 此时状态下有可调度的指令 then
