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

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

0 2 4 6 8 10 12 14 16 18 20 22 24
0 0 2 4 1 19 6
2 3 7 5 8 11 9 13 16 10 14 17 指令调度
3 12 15 顺序(步)
5
6 18 20 23 21 22
8
24
移动次数

(a) GISDP 得到的调度
位置段0 位置段1

0 1 2 3 4 5 6 7
A C E G B D F
Port0 Port1

(b) GISDP 得到的数据放置
Fig.5 Solution of GISDP
图 5 GISDP 的解决方案
0 2 4 6 8 10 12 14 16 18 20 22 24
0 10
2 0 4 2 指令调度
5 1 11 6 8 19 顺序(步)
4 3 7 12 15
6 9 13 16 14 17 18 23 20
7 21 22 24

移动次数

(a) ILP 得到的调度
位置段0 位置段1

0 1 2 3 4 5 6 7
G A B C F E D
Port0 Port1

(b) ILP 得到的数据放置
Fig.6 Solution of ILP
图 6 ILP 的解决方案

通过比较 4 种指令调度与数据放置方案所需的总移动次数,可以得出,本文所提算法的结果最接近 ILP 得
到的最优解.在该示例中:本文所提的方案与顺序调度和数据放置方案相比,总移动次数减少了 80%;与 S-DBC-P
相比,总移动次数减少了 20%.

4 整数线性规划模型与启发式算法

本节首先给出能够得到最优指令调度与数据放置方案的整数线性规划(integer linear programming,简称
ILP)模型.由于 ILP 模型时间复杂度呈指数级,不适合输入较大的情况,因此,本节还提出了启发式算法——生成
指令调度和数据放置(GISDP)算法,用以获得近似最优的指令调度与数据放置方案.