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

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

算法相较于 SSDP 算法移动次数平均减少了 97.3%,相较于 S-DBC-P 算法移动次数平均减少了 85.6%;本文提出
的 ILP 模型相较于 SSDP 算法移动次数平均减少了 94.8%,相较于 S-DBC-P 算法移动次数平均减少了 75.6%.
Table 4 Performance comparison for 8-port
表 4 8 个 port 的性能比较
SSDP S-DBC-P GISDP ILP
基准 移动 移动 相对 移动 相对 相对 移动 相对 相对
测试 操作 操作 SSDP 操作 SSDP S-DBC-P 操作 SSDP S-DBC-P
程序 次数 次数 减少(%) 次数 减少(%) 减少(%) 次数 减少(%) 减少(%)
epic 8 342 1 019 87.8 165 98.0 83.8 434 94.8 57.4
ghostscript 3 275 618 81.1 64 98.0 89.6 204 93.8 67.0
jpeg 4 111 630 84.6 116 97.2 81.6 84 * 98.0 86.7
mesa 5 207 719 86.2 136 97.4 81.1 98 * 98.1 86.4
mpeg 8 888 1 383 84.4 250 97.2 81.9 156 * 98.2 86.4
pegwit 1 688 455 73.0 65 96.1 85.7 50 * 97.0 88.7
pgp 2 991 1 024 65.8 89 97.0 91.3 383 87.2 62.6
rasta 3 208 829 74.2 82 97.4 90.1 273 91.5 67.1
平均减少(%) − − 79.6 − 97.3 85.6 − 94.8 75.6

从 3 个表中可以看出:ILP 只有在配备 8 个读/写头的磁畴壁存储器上的实验结果有求出最优结果的情况,
且本文的 GISDP 算法所求得结果与 ILP 最优结果相近.如表 4 中基准测试程序 pegwit 的结果,GISDP 算法的移
动次数分别相较于 SSDP 算法和 S-DBC-P 算法减少了 96.1%和 85.7%,ILP 模型的移动次数分别相较于 SSDP
算法和 S-DBC-P 算法减少了 97.0%和 88.7%,所以本文的 GISDP 算法可以在多项式时间内求得近似最优解.在
配备 2 个读/写头和 4 个读/写头的磁畴壁存储器上的实验结果均没有在 12 小时内找到最优解,所以这两个表中
的 ILP 结果均是 12 小时得到的局部最优解.
在本文提出的 ILP 模型中,ILP 的约束条件的数量是固定的,影响 ILP 求解效率的主要因素是输入的 IAFG
G 中|V|,|E|和|D|的大小以及读/写头的数量.当读/写头的数量为 2 时,在满足依赖关系的前提下,对指令进行调度
和数据进行放置,相当于是进行全排列,并选择最优的情况.当|E|很小,即依赖关系很少,满足依赖的排列数接近
全排列.当|V|和|D|很大时,全排列的复杂度使得 ILP 无法在多项式时间内求得最优解决策略.不过,当读/写头的
数量为 8 时,一部分基准测试程序的 ILP 收敛速度有所提高(如表 4),但是所需时间仍不能与启发式算法所需的
时间相比.可以看出:ILP 模型虽然可求最优解,但是不能在多项式时间内完成,不适合用在数据密集型应用的系
统中.
表 5 是在配备 2 个读/写头的磁畴壁存储器上 GISDP 算法中三段算法分别得到的结果,其中,算法 2 相对于
算法 1 移动次数平均减少了 9.81%,算法 3 相对于算法 2 移动次数平均减少了 9.43%.从表 5 中可以看出:部分基
准测试程序在算法 2 及算法 3 中,移动次数减少了 0%,是因为不同的测试程序具有不同的数据访问特性;并且算
法 2 和算法 3 均是在自身所求得的结果与前一段算法所求得的结果中选取更优的结果.因此对于部分应用,会
在算法 1 或算法 2 中就求得近优解.
Table 5 Performance comparison for 3-segment of GISDP (2-port)
表 5 GISDP 的三段算法性能比较(2 个 port)
算法 1 算法 2 算法 3
基准测试程序 移动次数 移动次数 相对算法 1 减少(%) 移动次数 相对算法 2 减少(%)
epic 630 630 0 630 0
ghostscript 356 254 28.7 208 18.1
jpeg 911 784 13.9 525 33.0
mesa 943 883 6.4 883 0
mpeg 1 860 1 860 0 1 630 12.4
pegwit 277 243 12.3 217 10.7
pgp 522 501 4.0 495 1.2
rasta 598 519 13.2 519 0
平均减少(%) − − 9.81 − 9.43

实验结果显示:本文所提的算法可以找到较优的指令调度和数据放置策略,并且有效地减少了总的移动次