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

2726 Journal of Software 软件学报 Vol.31, No.9, September 2020

行移动,因此磁性介质在本文中也可以称为磁带.每条磁带上有 n 个域(也可以称为位置),每个域可以存储 1bit
数据.对数据进行访问的端口称为读/写头.本文的磁畴壁存储架构如图 1 所示,包括一条存储多个数据的磁带、
两个访问数据的读/写头(分别称为 port0 和 port1)以及一个移动控制器.假设 port0 和 port1 各自拥有访问范围:
port0 的访问范围为 0~n/2−1,如图 1 中的域 0~域 3;port1 的访问范围为 n/2~n−1,如图 1 中的域 4~域 7.在该假设
条件下,磁带的左边需要冗余 n/2−1 个位置供磁带内数据的移动,避免数据在移动中丢失.假设 port0 和 port1 初
始时指向访问范围的最左侧位置处,即分别指在域 0 和域 4 处.移动控制器根据当前读/写头的位置和需要访问
数据的地址对读/写头进行选择并生产移动信号.
磁畴壁内存磁带
位置段0 位置段1

域0 域1 域2 域3 域4 域5 域6 域7
Port0 Port1
冗余域
移动使能信号
当前port 移动 将要访问
位置 控制器 数据的地址

Fig.1 Architecture of domain wall memory
图 1 磁畴壁存储器结构

磁畴壁存储器中,读/写头对数据进行读写操作的速度可以与 SRAM 的读写速度相媲美,然而磁畴壁存储器
进行读写操作之前必须将所访问数据移动到读/写头的位置.而磁畴壁存储器中的数据移动是所有数据沿着磁
带进行整体移动的,因此移动操作需要花费较长时间并且有较高的功耗.特别是对于数据密集型应用,所需的大
量移动操作将会大幅度地降低系统的整体性能.所以移动操作直接影响了磁畴壁存储器的访问性能,进而影响
系统性能.本文将磁带中的数据移动一个 bit 距离称为移动一次.在图 1 所示的架构中,磁带中数据发生移动后,
两个读/写头所指向的位置会同时改变.例如图 1 中,port0 从域 0 指向域 2,它的移动次数是 2,此时 port1 也从域
4 指向域 6.为了提升系统性能、降低功耗,可以通过调度程序中的加载和存储指令以及决策数据在磁带中的存
储位置,即通过优化指令调度和数据放置策略,使得移动次数最小.
本文假设计算操作完成之后,数据会立即被写回到磁畴壁存储器.
2.2 问题定义
针对数据密集型应用程序,本文采用指令访问流图(instruction access flow graph,简称 IAFG)进行建模.首先
对程序进行指令提取,然后生成指令访问流图,指令访问流图的定义如定义 1 所示.
定义 1(指令访问流图). IAFG G=〈V,E,D〉表示一个有向图,其中:V 是访存指令的集合;E⊆V×V 是边的集合,表
示访存指令之间的依赖关系;D 是每条访存指令 V 所访问的数据,假设每个数据都为 1bit.在 IAFG G 中,v∈V 表
示从磁畴壁存储器中加载数据或是往磁畴壁存储器中存储数据的指令.
在此基础上,对本文中需要解决的问题进行问题定义.
定义 2. 指令调度和数据放置问题(instruction scheduling and data placement problems (ISDPP)). 给定
一个 IAFG G 以及目标系统架构(磁畴壁存储器容量、读/写头数量),找到一个指令调度和数据在磁畴壁存储器
中的放置策略,使得在数据访问过程中磁畴壁存储器的总移动次数最少.
3 示 例

假设目标系统架构是一个包含 8 个域的基于赛道存储技术的磁畴壁存储器,读/写头数量为 2,分别是 port0