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

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

和 port1.域 0~域 3 由读/写头 port0 访问,域 4~域 7 由读/写头 port1 访问.两个读/写头的初始位置分别为域 0 和
域 4.
图 2(a)是一个 C 语言代码的基础块,包含 9 个加法运算,该基础块需要访问 7 个数据:A,B,C,D,E,F 和 G.将 C
语言代码按照图 2(b)所示的方式,首先转化成汇编伪代码,然后提取访存指令.图 2(c)是根据访存指令之间的依
赖关系生成的指令访问流图 G,其中,深色的圈表示加载指令(即 load 指令),白色的圈表示存储指令(即 store 指
令),圈中的内容表示该访存指令所要访问的数据.简单起见,本文对每个圈进行编号.

0 A 2 A 4 A 10 F
1 B 3 C 5 D
19 B 6 B 7 C 8 D 11 D

9 E 12 C

16 E 13 E 15 C
C代码: B=A+3 14 F
B=A+3 17
C=A+6 18 G F
D=A+5 Load R0,& A
E=B+C+D 汇编 Add R1,R0,R3 21 E 20 G 23 G
C=F+D 伪代码: Store & B,R1
F=E+7
G=C+E+F 22 E
E=B+G
A=E+G 访存指令: Load A 24 A
Store B
(a) C 语言的基础块 (b) 汇编伪代码 (c) 指令访问流图 G
Fig.2 A motivation example
图 2 示例
根据图 2(c),使用简单指令调度和数据放置算法可以得到一个简单的指令调度序列以及磁畴壁存储器上简
单的数据放置策略,分别如图 3(a)和图 3(b)所示.其中:图 3(a)中,每个填有序号的小格子表示指令,格子中的序号
对应于图 2(c)中指令的编号.横坐标表示指令调度顺序,对应指令访问数据的顺序为 A,B,A,C,A,D,B,C,
D,E,F,D,C,E,F,C,E,F,G,B,G,E,E,G,A.纵坐标表示在移动几次之后读/写头可以与该指令所要访问的数据对齐,其
中所需移动次数可以根据图 3(b)的数据放置以及指令调度顺序获得.如指令 2 和指令 3,分别需要访问数据 A 和
数据 C,在访问完数据 A 之后要移动 2 次,读/写头才能与指令 3 所要访问的数据 C 对齐.而在执行指令 2 之前,
已经有 2 次移动操作.所以加上此次的 2 次移动操作,在执行指令 3 之前磁带中的数据共需移动 4 次,对应于纵
坐标值为 4 处.在如图 3 所示的顺序调度和数据顺序放置的方案中,一共需要 36 次移动操作,如图 3(b)所示.
Chen 等人 [20] 所提出的在磁畴壁存储器上进行数据放置的 S-DBC-P 算法是针对已经固定指令调度.首先,
用本文所提的算法生成指令调度;然后,用 S-DBC-P 算法进行数据放置,得到的结果如图 4 所示.根据数据放置的
结果及指令调度,对应访问数据的顺序为 A,A,A,B,B,B,C,C,D,D,D,E,E,E,F,F,F,C,C,G,G,G,E,E,A.可以得到如图
4(a)所示的指令调度顺序-移动次数图,看到采用这种指令调度与数据放置方案一共需要 10 次移动操作.
图 5 是通过本文所提出的生成指令调度和数据放置算法(GISDP)得到的结果.图 6(a)是 GISDP 生成的指令
调度,对应访问数据的顺序为 A,A,A,B,B,B,C,C,D,D,D,E,E,E,F,F,F,C,C,G,G,G,E,E,A.图 6(b)是 GISDP 得到的数据
放置.通过该算法,最终得到的总移动次数为 8 次.
通过本文所提的 ILP 模型得到的最优指令调度和数据放置方案如图 6 所示.图 6(a)是通过 ILP 得到的最优
指令调度序列,对应访问数据的顺序为 F,A,A,A,D,B,D,B,D,B,C,C,C,C,E,E,E,F,F,G,G,G,E,E,A.图 6(b)是通过 ILP