面向多讀/寫頭磁疇壁存儲器的優化研究?

許 瑞 , 谷守珍 , 沙行勉 , 諸葛晴鳳 , 石 亮 , 高思遠

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 算法能夠生成最優和近似最優的指令調度與數據放置方案.

由于研究問題的復雜性,本文主要考慮的是配備多個讀/寫頭的磁疇壁存儲器的單核處理器系統,但在實際用中,多核處理器系統使用更加廣泛.在未來的工作中,將會研究配備多個讀/寫頭的磁疇壁存儲器的多核處理器系統中指令調度與數據放置策略,減少移動次數并提高磁疇壁存儲器的存儲訪問性能,進而提高整個體統的性能.