面向多读/写头磁畴壁存储器的优化研究∗

许 瑞 , 谷守珍 , 沙行勉 , 诸葛晴凤 , 石 亮 , 高思远

1(上海市高可信计算重点实验室(华东师范大学),上海 200062)2(华东师范大学 计算机科学与技术学院,上海 200062)

在大数据以及人工智能技术飞速发展的今天,大数据分析技术可以对世间万物所产生的数据进行分析,人工智能中学习算法可以对数据进行学习、分析、总结.目前,由众多嵌入式设备构建的物联网系统中,互联设备之间收集与共享的数据已经广泛使用大数据分析及人工智能技术[1].其中,大数据泛指数据规模达到TB,甚至PB 级别,应用均是数据密集型应用,具有高度密集的海量数据读写的特点[2].随着大数据及人工智能应用逐渐向边缘化设备发展,嵌入式设备的数据存储访问性能对系统性能的影响变得尤为重要.高速缓存和便笺式存储器经常应用于嵌入式系统中,从而提升系统的数据访问性能[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)方案的启发式算法,以此来减小移动次数;

· 对配备不同数量读/写头的磁畴壁存储器的存储访问性能进行了设计探索与实验.

实验结果表明:本文所提出的ILP 模型和GISDP 算法,分别能够生成最优和近似最优的指令调度与数据放置方案.与简单指令调度和数据放置(simple instruction scheduling and data placement,简称SSDP)算法和Chen 等人[20]提出在固定调度的情况下对数据进行分组放置的S-DBC-P 算法相比,在配备2 个读/写头的DWM 上的实验结果表明:GISDP 相对于SSDP,移动次数平均减少了86.7%;GISDP 相对于S-DBC-P,移动次数平均减少了79.6%;ILP 模型在12 小时内求出的局部最优解,相较于SSDP 算法,移动次数平均减少了75.0%;相较于S-DBC-P算法,移动次数平均减少了61.8%.在配备4 个读/写头的DWM 上的实验结果表明:GISDP 相对于SSDP,移动次数平均减少了93.7%;GISDP 相对于S-DBC-P,移动次数平均减少了80.7%;ILP 模型在12 小时内求出的局部最优解,相较于SSDP 算法,移动次数平均减少了82.6.0%;相较于S-DBC-P 算法,移动次数平均减少了46.3%.在配备8 个读/写头的DWM 上的实验结果表明:GISDP 相对于SSDP,移动次数平均减少了97.3%;GISDP 相对于S-DBC-P,移动次数平均减少了85.6%;ILP 模型相较于SSDP 算法移动次数平均减少了94.8%;相较于S-DBC-P算法移动次数平均减少了75.6%.并且GISDP 算法的结果接近于ILP 模型的最优解.

本文第1 节介绍对磁畴壁存储器性能改进的相关工作.在第2 节中,先对本文目标系统架构进行介绍,再对本文所解决的问题进行定义.第3 节通过一个示例阐述论文提出的相关算法.第4 节提出了ILP 模型与启发式算法.第5 节展示实验结果并对实验结果进行分析.第6 节对文章进行总结.

1 相关工作

在已有的工作中,有很多对磁畴壁存储器进行性能提升的研究.他们有从硬件层次对磁畴壁存储器进行改进,也有从软件层次对磁畴壁存储器性能进行提升.

对于硬件层次的优化,在文献[14]中,作者提出了一种电路架构协同设计方案,针对读取数据进行了优化,并提出一种新的缓存组织和管理策略.文献[21]研究了位元布局、磁头定位、纳米线利用率、移动功率、移动延时等电路设计难题,并提出了相应的解决方案.文献[22]使用斯格明子赛道存储器错位存储单元进行了非易失性存储器计算框架的研究与改进.文献[23]通过改变两个重金属衬底的相对厚度来调整电流驱动的畴壁运动.

已有一些在磁畴壁存储器及其他NVM 上对指令进行调度以及对数据进行分配的研究工作[8,11,24,25].在文献[24]中,Hu 等人讨论了在混合SPM 的NVM/SRAM 上的动态数据分配算法.在文献[11]中,Chen 等人提出了在配备多个读/写头的磁畴壁存储器上数据分配的优化技术,但是他们没有考虑同时优化指令调度.文献[8]使用遗传算法对在磁畴壁存储器上的数据进行分配,比较适用于不同访问特性数据集.但是遗传算法在时间上会计算较久,所以对于实时系统不是很适用.在文献[25]中,Gu 等人提出了一种软硬件协同优化方法,以提高应用专用嵌入式系统中磁畴壁存储器的面积效率和性能.但是他们只是针对一个读/写头进行研究,磁畴壁存储器可以具有多个读/写头,并且一定的读/写头数量会对磁畴壁存储器的性能提升有所帮助.

本文针对数据密集型应用,面向配备多个读/写头的磁畴壁存储器的单核处理器系统,研究最优指令调度与数据放置方案来获得最少的移动操作次数,以提升磁畴壁存储器的存储访问性能,进而提升系统性能.

2 架构与问题定义

2.1 架 构

本文的目标系统架构是配备基于赛道存储技术的磁畴壁存储器的单核处理器系统.磁畴壁存储器用作便笺式存储器,可以由软件进行管理.磁畴壁存储器是一种非易失性存储器,它可以用比较低的功耗进行对数据的高速读取.读/写数据的原理是:利用磁畴壁中自旋极化电流与电子磁矩之间的相互作用,由磁畴中磁矩的改变来记录数据位.当要进行读写数据时,根据移动控制器产生的移动信号,电流驱动磁畴壁存储器中所存储的数据整体移动,使得要访问的数据与读/写头对齐,以便数据可以被读/写头进行读写.

在磁畴壁存储器中,数据(即磁畴中的磁矩)存储于磁性介质中.由于在该存储器中,数据的移动类似于磁带的移动,均是数据去找读写磁头进行数据访问,区别是磁畴壁存储器是数据进行移动,磁带是存储数据的介质进行移动,因此磁性介质在本文中也可以称为磁带.每条磁带上有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 处.移动控制器根据当前读/写头的位置和需要访问数据的地址对读/写头进行选择并生产移动信号.

磁畴壁存储器中,读/写头对数据进行读写操作的速度可以与SRAM 的读写速度相媲美,然而磁畴壁存储器进行读写操作之前必须将所访问数据移动到读/写头的位置.而磁畴壁存储器中的数据移动是所有数据沿着磁带进行整体移动的,因此移动操作需要花费较长时间并且有较高的功耗.特别是对于数据密集型应用,所需的大量移动操作将会大幅度地降低系统的整体性能.所以移动操作直接影响了磁畴壁存储器的访问性能,进而影响系统性能.本文将磁带中的数据移动一个bit 距离称为移动一次.在图1 所示的架构中,磁带中数据发生移动后,两个读/写头所指向的位置会同时改变.例如图1 中,port0 从域0 指向域2,它的移动次数是2,此时port1 也从域4 指向域6.为了提升系统性能、降低功耗,可以通过调度程序中的加载和存储指令以及决策数据在磁带中的存储位置,即通过优化指令调度和数据放置策略,使得移动次数最小.

本文假设计算操作完成之后,数据会立即被写回到磁畴壁存储器.

2.2 问题定义

针对数据密集型应用程序,本文采用指令访问流图(instruction access flow graph,简称IAFG)进行建模.首先对程序进行指令提取,然后生成指令访问流图,指令访问流图的定义如定义1 所示.

定义1(指令访问流图).IAFGG=〈V,E,D〉表示一个有向图,其中:V是访存指令的集合;E⊆V×V是边的集合,表示访存指令之间的依赖关系;D是每条访存指令V所访问的数据,假设每个数据都为1bit.在IAFGG中,v∈V表示从磁畴壁存储器中加载数据或是往磁畴壁存储器中存储数据的指令.

在此基础上,对本文中需要解决的问题进行问题定义.

定义2.指令调度和数据放置问题(instruction scheduling and data placement problems (ISDPP)).给定一个IAFGG以及目标系统架构(磁畴壁存储器容量、读/写头数量),找到一个指令调度和数据在磁畴壁存储器中的放置策略,使得在数据访问过程中磁畴壁存储器的总移动次数最少.

3 示 例

假设目标系统架构是一个包含8 个域的基于赛道存储技术的磁畴壁存储器,读/写头数量为2,分别是port0和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 指令),圈中的内容表示该访存指令所要访问的数据.简单起见,本文对每个圈进行编号.

根据图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得到的最优数据放置.通过ILP 得到的总移动次数最少,为7 次.

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

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

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

4.1 整数线性规划模型

首先给出构建ILP 模型所需的两个定理以及符号(见表1).

Table 1 Notations and definitions表1 符号及定义

定理1.假设u和v是正整数变量,x是一个二值变量.描述“u=v,iffx=1”可以被线性建模为

其中,B是一个大数.

定理2.假设a,b,c是正整数变量,则描述“c≥|a-b|”可以被线性建模为

根据上述定理,可以通过对指令约束、依赖约束和数据放置约束进行建模,从而构建ILP 模型.

(1) 指令约束

每一条访存指令在每一步都有执行和不执行两种状态,因此,定义一个二值变量Xi,l表示访存指令i在第l步是否执行,其中,i表示访存指令,l表示第几步.对于任一条指令i,在第l步执行时,Xi,l=1;否则,Xi,l=0.

目标系统架构是单核处理器,因此指令调度步骤的上限为访存指令的总数量.假设共有|V|条访存指令,则指令调度上限为|V|.

对于指令约束,分为两种.

· 第1 种是每一步至少有一条访存指令执行,该约束可以线性表示为

· 第2 种是每条访存指令只能执行一次,将其线性表示为

(2) 依赖约束

因为一些访存指令之间存在依赖,如写后读、读后写、写后写等依赖.所以进行访存指令调度时,需要满足所有依赖关系.也就是说,如果访存指令j依赖于访存指令i,即i→j,那么访存指令i需要在访存指令j之前调度执行.定义变量SCHi,表示访存指令i在第SCHi步调度执行.对于任意访存指令i,SCHi可以被线性表示为

如果访存指令i与j之间存在依赖关系,即在IAFGG中存在e(i,j)∈E,那么该依赖关系可以表示为

表示访存指令i要在访存指令j之前调度执行,因此可以满足其依赖关系.

(3) 数据放置约束.

定义一个二值变量Yk,p,其中,k表示数据,p表示磁畴壁存储器中的域.Yk,p表示数据k放置在域p处.当数据k放置在域p处时,Yk,p=1;否则,Yk,p=0.假设一条磁带有capacity个域,那么每个数据会有capacity种放置的方法.首先,每个数据必须放置在磁带的域中,该约束被线性表示为

不失一般性,每个域中最多只能放一个数据.当数据量小于磁带容量capacity时,有些域中不放置数据.假设有|D|个数据需要被访问,那么将有|D|个数据需要被放在磁带的域中,该约束被线性表示为

假设数据量不会超过磁带容量capacity,该约束线性表示为

为了建模移动次数,需要知道指令调度、访存指令访问的数据以及数据放置位置.也就是说,需要知道每一步所调度的访存指令访问的数据放置在磁畴壁存储器的磁带上哪个域中.因为在磁畴壁存储器中有两个读/写头进行数据的读/写,分别为port0 和port1.并且磁带的前半部分域由port0 进行访问,磁带的后半部分域由port1进行访问,因此需要建模每个位置与其对应读/写头的偏移位置.例如,磁带上有8 个域,分别编号为域0～域7.port0 访问域0～域3,port1 访问域4～域7.初始状态下,port0 与域1 对齐,port1 与域5 对齐.对于port0 来说,域1是第1 个位置;对于port1 来说,域5 是第1 个位置.如果域1 中的数据被访问之后,立即访问域5 中的数据,那么就不需要移动操作,此时移动次数为0.如果使用的不是偏移位置进行计算,则是5-1=4,会出现计算错误.因此,建模移动次数需要获得偏移位置.

定义一个列表posoff记录每个域的偏移位置,即.例如:如果磁带容量为8,则posoff=[0,1,2,3,0,1,2,3].

对于每个数据k和访存指令i,如果访存指令i访问数据k,那么数据k和访存指令i直接的映射关系为

定义offset(i)表示访存指令i所访问数据的偏移位置,该约束可以表示为

如果变量Xi,l=1 表示访存指令i在第l步调度执行,定义position(l)来表示第l步调度执行的访存指令i所访问数据的偏移位置,它可以表示为

也就是说,当访存指令i在第l步调度执行时,就将访存指令i所访问数据的偏移位置赋值给position(l).不幸的是,该表达式是非线性的.根据定理1,它可以线性表示为

其中,B是一个大数.

假设shift(l)记录的是从当前步l到下一步l+1 所需要移动的次数,那么从第l步到第l+1 步的移动次数可以表示为

该公式可以根据定理2 重写为线性公式,如下:

(4) 目标函数.

整数线性规划的目标函数是总移动次数最小,线性公式表示为

4.2 生成指令调度和数据放置(GISDP)算法

本节提出了一个启发式算法——生成指令调度和数据放置(GISDP)算法,该算法可以生成一个指令调度和数据放置方案,使得总移动次数达到近似最优.由于提出的GISDP 算法基于赛道存储技术的存储器,所以适用于本文所提到的磁畴壁存储介质的存储器,也同样适用于斯格明子介质的存储器.

GISDP 算法是一个三段式算法,其主要思想是:首先由算法1 根据IAFGG同时生成指令调度序列和数据放置策略;然后,算法2 在算法1 结果的基础上对数据放置进行改进;最后,算法3 根据算法2 改进的结果对指令调度进行改进.

在介绍GISDP 算法细节之前,先介绍等价类的概念.在有多个读/写头的磁畴壁存储器上,磁带上的域被m个读/写头平均分成m段,每段都有相同的偏移地址.因此在任何时刻,m个读/写头所处域的偏移地址相同.例如:假设P和Q分别是读/写头port1 和port3 所管辖段中域的集合,那么如果P中的域p和Q中的域q有相同的偏移位置,则域p和域q是等价的,即,数据放在域p和放在域q中的效果是一样的.由于读/写头的数量为m,因此等价类的大小是m.

GISDP 算法第1 部分(算法1)的主要思想是:将需要访问但还未被放置的数据放置在读/写头当前所指向的域中,如果当前所有读/写头指向的域均已放置数据,那么进行移动操作,使得读/写头和相邻的下一个域对齐,将数据放置到距离读/写头最近的空闲域中.然后再将访问该数据且不依赖于其它未执行指令的所有指令进行调度.如算法1 所述,输入为IAFGG和目标系统架构;输出为一个指令调度sch、一个数据放置place、移动次数shift、一个记录产生移动操作的连续访问的数据对列表shift_data、一个记录产生移动操作的移动次数的列表shift_count.

算法第1 行,统计G中入度为0 的指令和不为0 指令及其入度,分别存入列表list0 和list1 中;在算法初始阶段,指令调度sch和数据放置place为空,并且所有port 均指向偏移位置为0 的域处,此时的状态需要执行第6行～第9 行,随机选取满足条件的指令调度,并把指令所访问数据放置在此时port 所指向域中的任一空闲域,同时更新列表list0,list1 以及数据D集合.另一种状态,在port 所指向域中有数据且list0 中有访问这些数据的指令时,则执行第5 行.当以上两种状态下均未在list0 中找到可调度指令,则要执行第11 行,进行移动操作之后的状态将会是前两种状态中的一种,则重复执行第4 行～第9 行.在数据D集合为空的情况下,说明数据均已被放置.接下来只需要将剩余指令调度完成.调度过程中,先调度访问当前port 所指向域中数据的指令,即第15 行;没有满足条件的指令,则需要执行第17 行和第18 行,调度list0 中访问距离当前域最近的域中数据的指令.直至所有指令调度完成.

生成了调度sch和数据放置place后,执行第21 行,将统计得到总移动次数shift,产生移动操作的连续访问的数据对,存入列表shift_data,及数据对所对应移动次数,存入列表shift_count进行输出.

算法1.GISDP 算法第1 部分——由IAFG 同时生成调度和数据放置.

输入:一个IAFGG=〈V,E,D〉;

磁带的容量N,M个读/写头;

输出:一个指令调度sch;

算法2 的主要思想是:根据算法1 生成的结果计算连续访问数据对的相关度,依据将相关度大的数据放在等价位置的原则对数据放置进行改进.如算法2 所描述,输入为IAFGG、目标系统架构以及算法1 的输出;输出为比算法1 总移动次数少的数据放置顺序place、总的移动次数shift、一个记录移动次数的列表shift_count.

算法第1 行,根据算法1 生成的产生移动操作时连续访问的数据对的列表shift_data计算数据对连续访问的次数,并存入列表count中.第2 行,根据列表count,shift_count和shift_data,将连续次数count与对应数据对的总移动距离相乘得到数据对的相关度,并根据数据对的相关度的降序排列将相关度和数据对存入列表relate中.从最大相关度的数据对入手,如果数据对(m,n)中的数据m和n放置在同一个位置段,则执行第8 行和第9 行;否则,执行第5 行和第6 行.在将数据m放在等价位置处后,则原位置处的数据r被交换到数据m的原位置处.进行数据交换之后,就会导致r与原来相邻位置及等价位置处的数据的距离增加,所以需要将r当前所在域到m当前所在域之间的数据(包括r,不包括m)向r所在域的方向循环移一个位置.为了减少r与之前相邻域及等价域中数据的相对距离,需要对所有段中该区间的域中的数据循环移动一个位置.在进行交换位置及移动操作之后,会重新计算总的移动次数:如果移动次数减少,则会保留此次交换,更新数据放置place,并重新计算相关度;如果移动次数不变或者增加,则本次交换取消,进行下一个相关度数据对的位置重置.

在交换到数据对的相关度为1 的时候,则停止位置重置,此时的数据放置作为新的放置策略进行输出.

算法2.GISDP 算法第2 部分——修改数据放置.

输入:一个IAFGG=〈V,E,D〉;

磁带的容量N,M个读/写头;

算法1 的输出的sch,place,shift,shift_count,shift_data;

输出:比算法1 总移动次数少的数据放置顺序place;

总的移动次数shift;

一个记录移动次数的列表shift_count.

在算法2 对数据的放置进行改进之后,算法3 根据算法2 的数据放置和IAFGG对指令进行了重调度,以获得与新数据放置策略相适宜的指令调度.算法3 的主要思想是:尽量将访问当前port 所在域中数据的指令进行调度,没有可调度的指令则移动一个位置.当port 移动到有指令可调度的域的时候,将会更新port 的状态.最后统计该调度下的移动次数,与重调度之前的移动次数进行比较,如果移动次数减少,则保留此次的调度;否则不更新调度.

算法3.GISDP 算法第3 部分——改进指令调度.

输入:一个IAFGG=〈V,E,D〉;

磁带的容量N,M个读/写头;

算法1 的输出sch,算法2 的输出place,shift;

输出:一个指令调度列表sch;

总的移动次数shift.

算法1 的时间复杂度为O(|V|×|D|),在一个磁带中,|D|最大为磁带容量,即数据量,|V|为应用中访存指令数量;算法2 的时间复杂度为表示应用中连续访问数据的相关度大于1 的数据对可能的最大个数;算法3 的时间复杂度为O(|V|).

5 实 验

本节首先介绍实验设置,然后通过实验对比展示本文所提出的ILP 和GISDP 算法的效率,并对实验结果进行分析.

5.1 实验设置

本文从MediaBench[26]基准套件中选择8 个应用程序进行实验,这8 个应用程序分别为epic,ghostscript,jpeg,mesa,mpeg,pegwit,pgp 和rasta.将本文所提出的ILP 和GISDP 算法与不同的算法进行比较:(1) SSDP 算法,将指令进行顺序调度并且按照数据的访问顺序进行顺序放置的一种算法; (2) S-DBC-P 算法,Chen 等人[20]提出的在固定调度的情况下,对数据进行分组放置的一个算法;(3) GISDP 算法,本文所提出的启发式算法;4) ILP 方法,本文所提出的可以得到最优解的模型.将本文提出的算法与其他算法比较之后,本文继续对启发式算法自身的三段算法进行性能提升的比较与讨论.

本文使用SimpleScalar 模拟器[27]对基准程序进行指令提取并生产指令访问流图,同时,本文设计了磁畴壁存储器访问行为模拟器.将指令访问流图以及每条指令所访问数据输入到模拟器中,使用不同的算法可以在模拟器中生成指令调度与数据放置方案,并获得总的移动次数.在模拟器中,假设数据能够全部存储在磁畴壁存储器中.本文分别对读/写头数量为2,4,8 时的磁畴壁存储器进行了设计空间的探索实验.

对于ILP 模型,使用python3 调用Gurobi 中的接口[28]对ILP 模型进行编写,并运行ILP 程序.对于某些测试程序,ILP 不能在可接受的时间范围内找到最优解,所以本文设定在ILP 模型被执行12 小时(43 200 秒)之后便停止执行,并将当前的结果输出.其中,最优解使用“*”标记.其他的算法均是可以在几百毫秒时间内完成的.

5.2 实验结果与分析

本节对我们的实验结果进行展示与分析.

表2 是在配备2 个读/写头的磁畴壁存储器上不同算法产生的实验结果.其中:“SSDP”列表示SSDP 算法得到的移动次数;“S-DBC-P”列是Chen 等人[20]提出的算法得到的移动次数,以及相较于SSDP 算法移动次数减少的百分比;“GISDP”列是本文所提出的启发式算法求得的移动次数,以及分别相较于SSDP 算法和S-DBC-P 算法移动次数减少的百分比;“ILP”列是整数线性规划在12 小时内求得的移动次数,以及分别相较于SSDP 算法和S-DBC-P 算法移动次数减少的百分比.从表2 可以看出:本文所提的GISDP 算法相较于SSDP 算法,移动次数平均减少了86.7%,相较于S-DBC-P 算法,移动次数平均减少了79.6%;本文所提出的ILP 模型虽然没有在12 小时内求出最优解,但是相较于SSDP 算法,移动次数平均减少了75.0%,相较于S-DBC-P 算法,移动次数平均减少了61.8%.

Table 2 Performance comparison for 2-port表2 2 个port 的性能比较

表3 是在配备4 个读/写头的磁畴壁存储器上不同算法产生的实验结果.从表3 可以看出:本文所提的S-DBC-P 算法相较于SSDP 算法移动次数平均减少了93.7%,相较于S-DBC-P 算法移动次数平均减少了80.7%;本文所提出的ILP 模型在12 小时内求出的局部最优解,相较于SSDP 算法,移动次数平均减少了82.6%,相较于S-DBC-P 算法,移动次数平均减少了46.3%.

Table 3 Performance comparison for 4-port表3 4 个port 的性能比较

表4 是在配备8 个读/写头的磁畴壁存储器上不同算法产生的实验结果,从表4 可以看出:本文的S-DBC-P算法相较于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 的性能比较

从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 求解效率的主要因素是输入的IAFGG中|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 中就求得近优解.

实验结果显示:本文所提的算法可以找到较优的指令调度和数据放置策略,并且有效地减少了总的移动次数.因为考虑了连续访问数据对的相关度对数据放置进行了改进,同时根据放置进行了指令重调度,所以本文所提的算法可以到达较好的性能.

6 结 论

本文针对数据密集型应用,面向配备多个读/写头的磁畴壁存储器的单核处理器系统研究最优指令调度与数据放置方案来获得最少的移动操作次数,以提升磁畴壁存储器的存储访问性能,进而提升系统性能.本文提出了可以在配备多个读/写头的磁畴壁存储器上生成最优的指令调度和数据放置方案的ILP 模型,可以求得最小的移动次数.因为ILP 模型的时间复杂度呈指数级,本文提出了可以在配备多个读/写头的磁畴壁存储器上,在多项式时间内生成近似最优的指令调度和数据放置方案(GISDP)的启发式算法,以此来减小移动次数.对配备不同数量读/写头的磁畴壁存储器的存储访问性能进行设计探索与实验,表明本文所提出的ILP 模型和GISDP 算法能够生成最优和近似最优的指令调度与数据放置方案.

由于研究问题的复杂性,本文主要考虑的是配备多个读/写头的磁畴壁存储器的单核处理器系统,但在实际用中,多核处理器系统使用更加广泛.在未来的工作中,将会研究配备多个读/写头的磁畴壁存储器的多核处理器系统中指令调度与数据放置策略,减少移动次数并提高磁畴壁存储器的存储访问性能,进而提高整个体统的性能.