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

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

performance further. In that case, reducing shift operations of DWM can significantly improve the system performance. This study aims at
data-intensive application specific embedded systems with multi-port DWM, and explores optimal instruction schedule and data
placement strategy which achieve minimum shift operations. An integer linear programming (ILP) model is firstly proposed to obtain
minimum number of shifts. Since ILP model cannot find the optimal solution in polynomial time, a heuristic algorithm is proposed to
reduce the number of shifts on DWM—generation instruction scheduling and data placement (GISDP) algorithm. The experimental results
show that ILP model and GISDP algorithm can effectively reduce shift operation. On target system with 8 read/write ports DWM, GISDP
can reduce shift operations by 89.7% on average when compared with other algorithms, and the results of GISDP are close to the optimal
solutions of ILP.
Key words: domain wall memory; data-intensive applications; instruction scheduling; data placement; shift operation

在大数据以及人工智能技术飞速发展的今天,大数据分析技术可以对世间万物所产生的数据进行分析,人
工智能中学习算法可以对数据进行学习、分析、总结.目前,由众多嵌入式设备构建的物联网系统中,互联设备
[1]
之间收集与共享的数据已经广泛使用大数据分析及人工智能技术 .其中,大数据泛指数据规模达到 TB,甚至
[2]
PB 级别,应用均是数据密集型应用,具有高度密集的海量数据读写的特点 .随着大数据及人工智能应用逐渐向
边缘化设备发展,嵌入式设备的数据存储访问性能对系统性能的影响变得尤为重要.高速缓存和便笺式存储器
[3]
经常应用于嵌入式系统中,从而提升系统的数据访问性能 .相较于由硬件管理的高速缓存,便笺式存储器具有
[4]
更高的能量利用率和存储面积 .它采用软件管理,因此,便笺式存储器上的数据访问行为具有可预测性 [5,6] .在
[7]
面向应用的实时嵌入式系统中,采用便笺式存储器在能耗与性能方面更具优势 .
非易失性存储器(non-volatile memory,简称 NVM)凭借其访问速度快、低功耗、高密度以及字节寻址等优
[8]
点,被广泛应用在便笺式存储器中 ,已经成为嵌入式系统中备受欢迎的存储技术候选对象 [9,10] .其中,磁畴壁存
储器(domain wall memory,简称 DWM)是一种高密度、低功耗的新型非易失性存储器 [11] .它采用赛道存储技术,
使用磁畴中的磁矩表示数据,利用自旋动量传递的效应,从磁性纳米线中读写数据位 [12] .磁畴壁存储器的密度比
自旋力矩 MRAM 高 4 倍,最佳访问性能可与 SRAM 相媲美,与 DRAM 相比,减少了 92%的泄漏功率 [13,14] .磁畴壁
存储器已经展示了可以替换目前存储器的潜能,例如:文献[15]研究了将磁畴壁存储器作为通用计算平台的片
上存储器;在文献[16,17]中,将磁畴壁存储器用作图形图像处理平台的片上存储器使用;文献[18]研究在 AES 平
台用磁畴壁存储器替换 SRAM 来提高加密方法的性能.除此之外,还有一种是斯格明子介质的赛道存储器,使用
斯格明子表示数据.
虽然磁畴壁存储器具有高密度、低功耗、高读写速度的优势,但是由于赛道存储技术的特点,每次访问数
据需要先移动纳米线中的数据,使得要访问的数据与读/写头对齐,然后才能进行数据访问.其中:读写操作均是
需要 6.3ns,移动操作需要 5.87ns [5,6] .但是,移动操作需要较高的驱动电流,因此,频繁的移动操作会极大地影响磁
畴壁存储器的性能与能耗,甚至导致存储单元的损坏 [19] .特别是对于数据密集型应用,海量的数据访问需求会造
成大量的移动操作.由于移动操作的次数可以由数据的放置位置以及访问数据的顺序决定,所以进行合理的数
据放置以及指令调度,能够极大地提高磁畴壁存储器的存储访问性能,进而提升系统性能.
本文针对数据密集型应用,面向配备多个读/写头的磁畴壁存储器的单核处理器系统研究最优指令调度与
数据放置方案来获得最少的移动操作次数,以提升磁畴壁存储器的存储访问性能,进而提升系统性能.已经有研
究工作表明,在磁畴壁存储器上进行数据分配是 NP 完全问题 [20] ,所以本文提出了能够获得最优指令调度与数
据放置方案的整数线性规划(integer linear programming,简称 ILP)模型和能够获得近似最优方案的多项式时间
的启发式算法.本文的主要贡献包括:
• 提出了可以在配备多个读/写头的磁畴壁存储器上生成最优的指令调度和数据放置方案的 ILP 模型,
可以求得最小的移动次数;
• 提出了可以在配备多个读/写头的磁畴壁存储器上,在多项式时间内生成近似最优的指令调度和数据
放置(generation instruction scheduling and data placement,简称 GISDP)方案的启发式算法,以此来减小
移动次数;
• 对配备不同数量读/写头的磁畴壁存储器的存储访问性能进行了设计探索与实验.