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

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

5. 调度 list0 中访问当前 m 个域中数据的指令;更新 list0,list1;
6. else then
7. if port 左移 i 位不会移到其他位置段 then
8. if port 此时状态下没有可调度的指令 then
9. port 保持原状态;
10. if port 右移 i 位不会移到其他位置段 then
11. if port 此时状态下没有可调度的指令 then
12. port 保持原状态;i=i+1;
13. else then
14. 更新 port 状态,i=1;调度 list0 中访问当前 m 个域中数据的指令;更新 list0,list1;
15. end if
16. end if
17. else then
18. 更新 port 状态 i=1;调度 list0 中访问当前 m 个域中数据的指令;更新 list0,list1;
19. end if
20. end if
21. end if
22. end while
23. if 本次统计移动次数<shift then
24. shift=本次统计移动次数;sch=本次调度结果;
25. else then
26. shift 不变;sch=之前调度结果;
27. end if
28. return shift,sch.
算法 1 的时间复杂度为 O(|V|×|D|),在一个磁带中,|D|最大为磁带容量,即数据量,|V|为应用中访存指令数量;
⎛ |V | ⎞ |V |
算法 2 的时间复杂度为 O ⎜ × (|V + | 1) ,其中, × (|V | 1)+ 表示应用中连续访问数据的相关度大于 1 的数据
⎟
⎝ 2 ⎠ 2
对可能的最大个数;算法 3 的时间复杂度为 O(|V|).

5 实 验
本节首先介绍实验设置,然后通过实验对比展示本文所提出的 ILP 和 GISDP 算法的效率,并对实验结果进
行分析.
5.1 实验设置

本文从 MediaBench [26] 基准套件中选择 8 个应用程序进行实验,这 8 个应用程序分别为 epic,ghostscript,jpeg,
mesa,mpeg,pegwit,pgp 和 rasta.将本文所提出的 ILP 和 GISDP 算法与不同的算法进行比较:(1) SSDP 算法,将指
令进行顺序调度并且按照数据的访问顺序进行顺序放置的一种算法; (2) S-DBC-P 算法,Chen 等人 [20] 提出的在
固定调度的情况下,对数据进行分组放置的一个算法;(3) GISDP 算法,本文所提出的启发式算法;4) ILP 方法,本
文所提出的可以得到最优解的模型.将本文提出的算法与其他算法比较之后,本文继续对启发式算法自身的三
段算法进行性能提升的比较与讨论.
本文使用 SimpleScalar 模拟器 [27] 对基准程序进行指令提取并生产指令访问流图,同时,本文设计了磁畴壁
存储器访问行为模拟器.将指令访问流图以及每条指令所访问数据输入到模拟器中,使用不同的算法可以在模
拟器中生成指令调度与数据放置方案,并获得总的移动次数.在模拟器中,假设数据能够全部存储在磁畴壁存储