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

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

一个数据放置 place;
移动次数 shift;
一个记录产生移动操作的连续访问的数据对列表 shift_data;
一个记录产生移动操作的移动次数的列表 shift_count.
1. list0←统计入度为 0 的节点;list1←统计入度不为 0 节点的入度;
2. while len(sch)<len(V) do
3. while D 不为空 do
4. if list0 中有访问此时 port 所指向域中数据的指令 then
5. sch←满足条件的指令;更新 list0,list1;
6. elif list0 中无访问此时 port 所指向域中数据的指令且此时 port 所指向域有空闲域 then
7. sch←随机取一条满足条件的指令;更新 list0,list1;
8. 被调度指令所访问的数据 d 放置在此时 port 所指向的任一空闲域;
9. D=D−{d};
10. else then
11. 磁带上的数据整体左移一次,重复第 4 行~第 9 行;
12. endif
13. endwhile
14. if list0 中有访问此时 port 所指向域中数据的指令 then
15. sch←满足条件的指令;更新 list0,list1;
16. else then
17. sch←选取 list0 中访问数据所在域距离此时 port 所指向域最近的域中数据的指令;
18. 更新 port 的状态;重复第 14 行~第 18 行;
19. endif
20. endwhile
21. 根据 sch 和 place 统计总移动次数 shift,产生移动操作的连续访问的数据对 shift_data 及其移动次数
shift_count;
22. return sch,place,shift,shift_count,shift_data.
算法 2 的主要思想是:根据算法 1 生成的结果计算连续访问数据对的相关度,依据将相关度大的数据放在
等价位置的原则对数据放置进行改进.如算法 2 所描述,输入为 IAFG G、目标系统架构以及算法 1 的输出;输出
为比算法 1 总移动次数少的数据放置顺序 place、总的移动次数 shift、一个记录移动次数的列表 shift_count.
算法第 1 行,根据算法 1 生成的产生移动操作时连续访问的数据对的列表 shift_data 计算数据对连续访问
的次数,并存入列表 count 中.第 2 行,根据列表 count,shift_count 和 shift_data,将连续次数 count 与对应数据对的
总移动距离相乘得到数据对的相关度,并根据数据对的相关度的降序排列将相关度和数据对存入列表 relate
中.从最大相关度的数据对入手,如果数据对(m,n)中的数据 m 和 n 放置在同一个位置段,则执行第 8 行和第 9 行;
否则,执行第 5 行和第 6 行.在将数据 m 放在等价位置处后,则原位置处的数据 r 被交换到数据 m 的原位置处.
进行数据交换之后,就会导致 r 与原来相邻位置及等价位置处的数据的距离增加,所以需要将 r 当前所在域到 m
当前所在域之间的数据(包括 r,不包括 m)向 r 所在域的方向循环移一个位置.为了减少 r 与之前相邻域及等价
域中数据的相对距离,需要对所有段中该区间的域中的数据循环移动一个位置.在进行交换位置及移动操作之
后,会重新计算总的移动次数:如果移动次数减少,则会保留此次交换,更新数据放置 place,并重新计算相关度;如
果移动次数不变或者增加,则本次交换取消,进行下一个相关度数据对的位置重置.
在交换到数据对的相关度为 1 的时候,则停止位置重置,此时的数据放置作为新的放置策略进行输出.