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

1(上海市高可信計算重點實驗室(華東師范大學),上海 200062)2(華東師范大學 計算機科學與技術(shù)學院,上海 200062)

在大數(shù)據(jù)以及人工智能技術(shù)飛速發(fā)展的今天,大數(shù)據(jù)分析技術(shù)可以對世間萬物所產(chǎn)生的數(shù)據(jù)進行分析,人工智能中學習算法可以對數(shù)據(jù)進行學習、分析、總結(jié).目前,由眾多嵌入式設(shè)備構(gòu)建的物聯(lián)網(wǎng)系統(tǒng)中,互聯(lián)設(shè)備之間收集與共享的數(shù)據(jù)已經(jīng)廣泛使用大數(shù)據(jù)分析及人工智能技術(shù)[1].其中,大數(shù)據(jù)泛指數(shù)據(jù)規(guī)模達到TB,甚至PB 級別,應(yīng)用均是數(shù)據(jù)密集型應(yīng)用,具有高度密集的海量數(shù)據(jù)讀寫的特點[2].隨著大數(shù)據(jù)及人工智能應(yīng)用逐漸向邊緣化設(shè)備發(fā)展,嵌入式設(shè)備的數(shù)據(jù)存儲訪問性能對系統(tǒng)性能的影響變得尤為重要.高速緩存和便箋式存儲器經(jīng)常應(yīng)用于嵌入式系統(tǒng)中,從而提升系統(tǒng)的數(shù)據(jù)訪問性能[3].相較于由硬件管理的高速緩存,便箋式存儲器具有更高的能量利用率和存儲面積[4].它采用軟件管理,因此,便箋式存儲器上的數(shù)據(jù)訪問行為具有可預(yù)測性[5,6].在面向應(yīng)用的實時嵌入式系統(tǒng)中,采用便箋式存儲器在能耗與性能方面更具優(yōu)勢[7].

非易失性存儲器(non-volatile memory,簡稱NVM)憑借其訪問速度快、低功耗、高密度以及字節(jié)尋址等優(yōu)點,被廣泛應(yīng)用在便箋式存儲器中[8],已經(jīng)成為嵌入式系統(tǒng)中備受歡迎的存儲技術(shù)候選對象[9,10].其中,磁疇壁存儲器(domain wall memory,簡稱DWM)是一種高密度、低功耗的新型非易失性存儲器[11].它采用賽道存儲技術(shù),使用磁疇中的磁矩表示數(shù)據(jù),利用自旋動量傳遞的效應(yīng),從磁性納米線中讀寫數(shù)據(jù)位[12].磁疇壁存儲器的密度比自旋力矩MRAM 高4 倍,最佳訪問性能可與SRAM 相媲美,與DRAM 相比,減少了92%的泄漏功率[13,14].磁疇壁存儲器已經(jīng)展示了可以替換目前存儲器的潛能,例如:文獻[15]研究了將磁疇壁存儲器作為通用計算平臺的片上存儲器;在文獻[16,17]中,將磁疇壁存儲器用作圖形圖像處理平臺的片上存儲器使用;文獻[18]研究在AES 平臺用磁疇壁存儲器替換SRAM 來提高加密方法的性能.除此之外,還有一種是斯格明子介質(zhì)的賽道存儲器,使用斯格明子表示數(shù)據(jù).

雖然磁疇壁存儲器具有高密度、低功耗、高讀寫速度的優(yōu)勢,但是由于賽道存儲技術(shù)的特點,每次訪問數(shù)據(jù)需要先移動納米線中的數(shù)據(jù),使得要訪問的數(shù)據(jù)與讀/寫頭對齊,然后才能進行數(shù)據(jù)訪問.其中:讀寫操作均是需要6.3ns,移動操作需要5.87ns[5,6].但是,移動操作需要較高的驅(qū)動電流,因此,頻繁的移動操作會極大地影響磁疇壁存儲器的性能與能耗,甚至導(dǎo)致存儲單元的損壞[19].特別是對于數(shù)據(jù)密集型應(yīng)用,海量的數(shù)據(jù)訪問需求會造成大量的移動操作.由于移動操作的次數(shù)可以由數(shù)據(jù)的放置位置以及訪問數(shù)據(jù)的順序決定,所以進行合理的數(shù)據(jù)放置以及指令調(diào)度,能夠極大地提高磁疇壁存儲器的存儲訪問性能,進而提升系統(tǒng)性能.

本文針對數(shù)據(jù)密集型應(yīng)用,面向配備多個讀/寫頭的磁疇壁存儲器的單核處理器系統(tǒng)研究最優(yōu)指令調(diào)度與數(shù)據(jù)放置方案來獲得最少的移動操作次數(shù),以提升磁疇壁存儲器的存儲訪問性能,進而提升系統(tǒng)性能.已經(jīng)有研究工作表明,在磁疇壁存儲器上進行數(shù)據(jù)分配是NP 完全問題[20],所以本文提出了能夠獲得最優(yōu)指令調(diào)度與數(shù)據(jù)放置方案的整數(shù)線性規(guī)劃(integer linear programming,簡稱ILP)模型和能夠獲得近似最優(yōu)方案的多項式時間的啟發(fā)式算法.本文的主要貢獻包括:

· 提出了可以在配備多個讀/寫頭的磁疇壁存儲器上生成最優(yōu)的指令調(diào)度和數(shù)據(jù)放置方案的ILP 模型,可以求得最小的移動次數(shù);

· 提出了可以在配備多個讀/寫頭的磁疇壁存儲器上,在多項式時間內(nèi)生成近似最優(yōu)的指令調(diào)度和數(shù)據(jù)放置(generation instruction scheduling and data placement,簡稱GISDP)方案的啟發(fā)式算法,以此來減小移動次數(shù);

· 對配備不同數(shù)量讀/寫頭的磁疇壁存儲器的存儲訪問性能進行了設(shè)計探索與實驗.

實驗結(jié)果表明:本文所提出的ILP 模型和GISDP 算法,分別能夠生成最優(yōu)和近似最優(yōu)的指令調(diào)度與數(shù)據(jù)放置方案.與簡單指令調(diào)度和數(shù)據(jù)放置(simple instruction scheduling and data placement,簡稱SSDP)算法和Chen 等人[20]提出在固定調(diào)度的情況下對數(shù)據(jù)進行分組放置的S-DBC-P 算法相比,在配備2 個讀/寫頭的DWM 上的實驗結(jié)果表明:GISDP 相對于SSDP,移動次數(shù)平均減少了86.7%;GISDP 相對于S-DBC-P,移動次數(shù)平均減少了79.6%;ILP 模型在12 小時內(nèi)求出的局部最優(yōu)解,相較于SSDP 算法,移動次數(shù)平均減少了75.0%;相較于S-DBC-P算法,移動次數(shù)平均減少了61.8%.在配備4 個讀/寫頭的DWM 上的實驗結(jié)果表明:GISDP 相對于SSDP,移動次數(shù)平均減少了93.7%;GISDP 相對于S-DBC-P,移動次數(shù)平均減少了80.7%;ILP 模型在12 小時內(nèi)求出的局部最優(yōu)解,相較于SSDP 算法,移動次數(shù)平均減少了82.6.0%;相較于S-DBC-P 算法,移動次數(shù)平均減少了46.3%.在配備8 個讀/寫頭的DWM 上的實驗結(jié)果表明:GISDP 相對于SSDP,移動次數(shù)平均減少了97.3%;GISDP 相對于S-DBC-P,移動次數(shù)平均減少了85.6%;ILP 模型相較于SSDP 算法移動次數(shù)平均減少了94.8%;相較于S-DBC-P算法移動次數(shù)平均減少了75.6%.并且GISDP 算法的結(jié)果接近于ILP 模型的最優(yōu)解.

本文第1 節(jié)介紹對磁疇壁存儲器性能改進的相關(guān)工作.在第2 節(jié)中,先對本文目標系統(tǒng)架構(gòu)進行介紹,再對本文所解決的問題進行定義.第3 節(jié)通過一個示例闡述論文提出的相關(guān)算法.第4 節(jié)提出了ILP 模型與啟發(fā)式算法.第5 節(jié)展示實驗結(jié)果并對實驗結(jié)果進行分析.第6 節(jié)對文章進行總結(jié).

1 相關(guān)工作

在已有的工作中,有很多對磁疇壁存儲器進行性能提升的研究.他們有從硬件層次對磁疇壁存儲器進行改進,也有從軟件層次對磁疇壁存儲器性能進行提升.

對于硬件層次的優(yōu)化,在文獻[14]中,作者提出了一種電路架構(gòu)協(xié)同設(shè)計方案,針對讀取數(shù)據(jù)進行了優(yōu)化,并提出一種新的緩存組織和管理策略.文獻[21]研究了位元布局、磁頭定位、納米線利用率、移動功率、移動延時等電路設(shè)計難題,并提出了相應(yīng)的解決方案.文獻[22]使用斯格明子賽道存儲器錯位存儲單元進行了非易失性存儲器計算框架的研究與改進.文獻[23]通過改變兩個重金屬襯底的相對厚度來調(diào)整電流驅(qū)動的疇壁運動.

已有一些在磁疇壁存儲器及其他NVM 上對指令進行調(diào)度以及對數(shù)據(jù)進行分配的研究工作[8,11,24,25].在文獻[24]中,Hu 等人討論了在混合SPM 的NVM/SRAM 上的動態(tài)數(shù)據(jù)分配算法.在文獻[11]中,Chen 等人提出了在配備多個讀/寫頭的磁疇壁存儲器上數(shù)據(jù)分配的優(yōu)化技術(shù),但是他們沒有考慮同時優(yōu)化指令調(diào)度.文獻[8]使用遺傳算法對在磁疇壁存儲器上的數(shù)據(jù)進行分配,比較適用于不同訪問特性數(shù)據(jù)集.但是遺傳算法在時間上會計算較久,所以對于實時系統(tǒng)不是很適用.在文獻[25]中,Gu 等人提出了一種軟硬件協(xié)同優(yōu)化方法,以提高應(yīng)用專用嵌入式系統(tǒng)中磁疇壁存儲器的面積效率和性能.但是他們只是針對一個讀/寫頭進行研究,磁疇壁存儲器可以具有多個讀/寫頭,并且一定的讀/寫頭數(shù)量會對磁疇壁存儲器的性能提升有所幫助.

本文針對數(shù)據(jù)密集型應(yīng)用,面向配備多個讀/寫頭的磁疇壁存儲器的單核處理器系統(tǒng),研究最優(yōu)指令調(diào)度與數(shù)據(jù)放置方案來獲得最少的移動操作次數(shù),以提升磁疇壁存儲器的存儲訪問性能,進而提升系統(tǒng)性能.

2 架構(gòu)與問題定義

2.1 架 構(gòu)

本文的目標系統(tǒng)架構(gòu)是配備基于賽道存儲技術(shù)的磁疇壁存儲器的單核處理器系統(tǒng).磁疇壁存儲器用作便箋式存儲器,可以由軟件進行管理.磁疇壁存儲器是一種非易失性存儲器,它可以用比較低的功耗進行對數(shù)據(jù)的高速讀取.讀/寫數(shù)據(jù)的原理是:利用磁疇壁中自旋極化電流與電子磁矩之間的相互作用,由磁疇中磁矩的改變來記錄數(shù)據(jù)位.當要進行讀寫數(shù)據(jù)時,根據(jù)移動控制器產(chǎn)生的移動信號,電流驅(qū)動磁疇壁存儲器中所存儲的數(shù)據(jù)整體移動,使得要訪問的數(shù)據(jù)與讀/寫頭對齊,以便數(shù)據(jù)可以被讀/寫頭進行讀寫.

在磁疇壁存儲器中,數(shù)據(jù)(即磁疇中的磁矩)存儲于磁性介質(zhì)中.由于在該存儲器中,數(shù)據(jù)的移動類似于磁帶的移動,均是數(shù)據(jù)去找讀寫磁頭進行數(shù)據(jù)訪問,區(qū)別是磁疇壁存儲器是數(shù)據(jù)進行移動,磁帶是存儲數(shù)據(jù)的介質(zhì)進行移動,因此磁性介質(zhì)在本文中也可以稱為磁帶.每條磁帶上有n個域(也可以稱為位置),每個域可以存儲1bit數(shù)據(jù).對數(shù)據(jù)進行訪問的端口稱為讀/寫頭.本文的磁疇壁存儲架構(gòu)如圖1 所示,包括一條存儲多個數(shù)據(jù)的磁帶、兩個訪問數(shù)據(jù)的讀/寫頭(分別稱為port0 和port1)以及一個移動控制器.假設(shè)port0 和port1 各自擁有訪問范圍:port0 的訪問范圍為0～n/2-1,如圖1 中的域0～域3;port1 的訪問范圍為n/2～n-1,如圖1 中的域4～域7.在該假設(shè)條件下,磁帶的左邊需要冗余n/2-1 個位置供磁帶內(nèi)數(shù)據(jù)的移動,避免數(shù)據(jù)在移動中丟失.假設(shè)port0 和port1 初始時指向訪問范圍的最左側(cè)位置處,即分別指在域0 和域4 處.移動控制器根據(jù)當前讀/寫頭的位置和需要訪問數(shù)據(jù)的地址對讀/寫頭進行選擇并生產(chǎn)移動信號.

磁疇壁存儲器中,讀/寫頭對數(shù)據(jù)進行讀寫操作的速度可以與SRAM 的讀寫速度相媲美,然而磁疇壁存儲器進行讀寫操作之前必須將所訪問數(shù)據(jù)移動到讀/寫頭的位置.而磁疇壁存儲器中的數(shù)據(jù)移動是所有數(shù)據(jù)沿著磁帶進行整體移動的,因此移動操作需要花費較長時間并且有較高的功耗.特別是對于數(shù)據(jù)密集型應(yīng)用,所需的大量移動操作將會大幅度地降低系統(tǒng)的整體性能.所以移動操作直接影響了磁疇壁存儲器的訪問性能,進而影響系統(tǒng)性能.本文將磁帶中的數(shù)據(jù)移動一個bit 距離稱為移動一次.在圖1 所示的架構(gòu)中,磁帶中數(shù)據(jù)發(fā)生移動后,兩個讀/寫頭所指向的位置會同時改變.例如圖1 中,port0 從域0 指向域2,它的移動次數(shù)是2,此時port1 也從域4 指向域6.為了提升系統(tǒng)性能、降低功耗,可以通過調(diào)度程序中的加載和存儲指令以及決策數(shù)據(jù)在磁帶中的存儲位置,即通過優(yōu)化指令調(diào)度和數(shù)據(jù)放置策略,使得移動次數(shù)最小.

本文假設(shè)計算操作完成之后,數(shù)據(jù)會立即被寫回到磁疇壁存儲器.

2.2 問題定義

針對數(shù)據(jù)密集型應(yīng)用程序,本文采用指令訪問流圖(instruction access flow graph,簡稱IAFG)進行建模.首先對程序進行指令提取,然后生成指令訪問流圖,指令訪問流圖的定義如定義1 所示.

定義1(指令訪問流圖).IAFGG=〈V,E,D〉表示一個有向圖,其中:V是訪存指令的集合;E?V×V是邊的集合,表示訪存指令之間的依賴關(guān)系;D是每條訪存指令V所訪問的數(shù)據(jù),假設(shè)每個數(shù)據(jù)都為1bit.在IAFGG中,v∈V表示從磁疇壁存儲器中加載數(shù)據(jù)或是往磁疇壁存儲器中存儲數(shù)據(jù)的指令.

在此基礎(chǔ)上,對本文中需要解決的問題進行問題定義.

定義2.指令調(diào)度和數(shù)據(jù)放置問題(instruction scheduling and data placement problems (ISDPP)).給定一個IAFGG以及目標系統(tǒng)架構(gòu)(磁疇壁存儲器容量、讀/寫頭數(shù)量),找到一個指令調(diào)度和數(shù)據(jù)在磁疇壁存儲器中的放置策略,使得在數(shù)據(jù)訪問過程中磁疇壁存儲器的總移動次數(shù)最少.

3 示 例

假設(shè)目標系統(tǒng)架構(gòu)是一個包含8 個域的基于賽道存儲技術(shù)的磁疇壁存儲器,讀/寫頭數(shù)量為2,分別是port0和port1.域0～域3 由讀/寫頭port0 訪問,域4～域7 由讀/寫頭port1 訪問.兩個讀/寫頭的初始位置分別為域0 和域4.

圖2(a)是一個C 語言代碼的基礎(chǔ)塊,包含9 個加法運算,該基礎(chǔ)塊需要訪問7 個數(shù)據(jù):A,B,C,D,E,F和G.將C語言代碼按照圖2(b)所示的方式,首先轉(zhuǎn)化成匯編偽代碼,然后提取訪存指令.圖2(c)是根據(jù)訪存指令之間的依賴關(guān)系生成的指令訪問流圖G,其中,深色的圈表示加載指令(即load 指令),白色的圈表示存儲指令(即store 指令),圈中的內(nèi)容表示該訪存指令所要訪問的數(shù)據(jù).簡單起見,本文對每個圈進行編號.

根據(jù)圖2(c),使用簡單指令調(diào)度和數(shù)據(jù)放置算法可以得到一個簡單的指令調(diào)度序列以及磁疇壁存儲器上簡單的數(shù)據(jù)放置策略,分別如圖3(a)和圖3(b)所示.其中:圖3(a)中,每個填有序號的小格子表示指令,格子中的序號對應(yīng)于圖 2(c)中指令的編號.橫坐標表示指令調(diào)度順序,對應(yīng)指令訪問數(shù)據(jù)的順序為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.縱坐標表示在移動幾次之后讀/寫頭可以與該指令所要訪問的數(shù)據(jù)對齊,其中所需移動次數(shù)可以根據(jù)圖3(b)的數(shù)據(jù)放置以及指令調(diào)度順序獲得.如指令2 和指令3,分別需要訪問數(shù)據(jù)A和數(shù)據(jù)C,在訪問完數(shù)據(jù)A之后要移動2 次,讀/寫頭才能與指令3 所要訪問的數(shù)據(jù)C對齊.而在執(zhí)行指令2 之前,已經(jīng)有2 次移動操作.所以加上此次的2 次移動操作,在執(zhí)行指令3 之前磁帶中的數(shù)據(jù)共需移動4 次,對應(yīng)于縱坐標值為4 處.在如圖3 所示的順序調(diào)度和數(shù)據(jù)順序放置的方案中,一共需要36 次移動操作,如圖3(b)所示.

Chen 等人[20]所提出的在磁疇壁存儲器上進行數(shù)據(jù)放置的S-DBC-P 算法是針對已經(jīng)固定指令調(diào)度.首先,用本文所提的算法生成指令調(diào)度;然后,用S-DBC-P 算法進行數(shù)據(jù)放置,得到的結(jié)果如圖4 所示.根據(jù)數(shù)據(jù)放置的結(jié)果及指令調(diào)度,對應(yīng)訪問數(shù)據(jù)的順序為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)所示的指令調(diào)度順序-移動次數(shù)圖,看到采用這種指令調(diào)度與數(shù)據(jù)放置方案一共需要10 次移動操作.

圖5 是通過本文所提出的生成指令調(diào)度和數(shù)據(jù)放置算法(GISDP)得到的結(jié)果.圖6(a)是GISDP 生成的指令調(diào)度,對應(yīng)訪問數(shù)據(jù)的順序為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 得到的數(shù)據(jù)放置.通過該算法,最終得到的總移動次數(shù)為8 次.

通過本文所提的ILP 模型得到的最優(yōu)指令調(diào)度和數(shù)據(jù)放置方案如圖6 所示.圖6(a)是通過ILP 得到的最優(yōu)指令調(diào)度序列,對應(yīng)訪問數(shù)據(jù)的順序為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得到的最優(yōu)數(shù)據(jù)放置.通過ILP 得到的總移動次數(shù)最少,為7 次.

通過比較4 種指令調(diào)度與數(shù)據(jù)放置方案所需的總移動次數(shù),可以得出,本文所提算法的結(jié)果最接近ILP 得到的最優(yōu)解.在該示例中:本文所提的方案與順序調(diào)度和數(shù)據(jù)放置方案相比,總移動次數(shù)減少了80%;與S-DBC-P相比,總移動次數(shù)減少了20%.

4 整數(shù)線性規(guī)劃模型與啟發(fā)式算法

本節(jié)首先給出能夠得到最優(yōu)指令調(diào)度與數(shù)據(jù)放置方案的整數(shù)線性規(guī)劃(integer linear programming,簡稱ILP)模型.由于ILP 模型時間復(fù)雜度呈指數(shù)級,不適合輸入較大的情況,因此,本節(jié)還提出了啟發(fā)式算法——生成指令調(diào)度和數(shù)據(jù)放置(GISDP)算法,用以獲得近似最優(yōu)的指令調(diào)度與數(shù)據(jù)放置方案.

4.1 整數(shù)線性規(guī)劃模型

首先給出構(gòu)建ILP 模型所需的兩個定理以及符號(見表1).

Table 1 Notations and definitions表1 符號及定義

定理1.假設(shè)u和v是正整數(shù)變量,x是一個二值變量.描述“u=v,iffx=1”可以被線性建模為

其中,B是一個大數(shù).

定理2.假設(shè)a,b,c是正整數(shù)變量,則描述“c≥|a-b|”可以被線性建模為

根據(jù)上述定理,可以通過對指令約束、依賴約束和數(shù)據(jù)放置約束進行建模,從而構(gòu)建ILP 模型.

(1) 指令約束

每一條訪存指令在每一步都有執(zhí)行和不執(zhí)行兩種狀態(tài),因此,定義一個二值變量Xi,l表示訪存指令i在第l步是否執(zhí)行,其中,i表示訪存指令,l表示第幾步.對于任一條指令i,在第l步執(zhí)行時,Xi,l=1;否則,Xi,l=0.

目標系統(tǒng)架構(gòu)是單核處理器,因此指令調(diào)度步驟的上限為訪存指令的總數(shù)量.假設(shè)共有|V|條訪存指令,則指令調(diào)度上限為|V|.

對于指令約束,分為兩種.

· 第1 種是每一步至少有一條訪存指令執(zhí)行,該約束可以線性表示為

· 第2 種是每條訪存指令只能執(zhí)行一次,將其線性表示為

(2) 依賴約束

因為一些訪存指令之間存在依賴,如寫后讀、讀后寫、寫后寫等依賴.所以進行訪存指令調(diào)度時,需要滿足所有依賴關(guān)系.也就是說,如果訪存指令j依賴于訪存指令i,即i→j,那么訪存指令i需要在訪存指令j之前調(diào)度執(zhí)行.定義變量SCHi,表示訪存指令i在第SCHi步調(diào)度執(zhí)行.對于任意訪存指令i,SCHi可以被線性表示為

如果訪存指令i與j之間存在依賴關(guān)系,即在IAFGG中存在e(i,j)∈E,那么該依賴關(guān)系可以表示為

表示訪存指令i要在訪存指令j之前調(diào)度執(zhí)行,因此可以滿足其依賴關(guān)系.

(3) 數(shù)據(jù)放置約束.

定義一個二值變量Yk,p,其中,k表示數(shù)據(jù),p表示磁疇壁存儲器中的域.Yk,p表示數(shù)據(jù)k放置在域p處.當數(shù)據(jù)k放置在域p處時,Yk,p=1;否則,Yk,p=0.假設(shè)一條磁帶有capacity個域,那么每個數(shù)據(jù)會有capacity種放置的方法.首先,每個數(shù)據(jù)必須放置在磁帶的域中,該約束被線性表示為

不失一般性,每個域中最多只能放一個數(shù)據(jù).當數(shù)據(jù)量小于磁帶容量capacity時,有些域中不放置數(shù)據(jù).假設(shè)有|D|個數(shù)據(jù)需要被訪問,那么將有|D|個數(shù)據(jù)需要被放在磁帶的域中,該約束被線性表示為

假設(shè)數(shù)據(jù)量不會超過磁帶容量capacity,該約束線性表示為

為了建模移動次數(shù),需要知道指令調(diào)度、訪存指令訪問的數(shù)據(jù)以及數(shù)據(jù)放置位置.也就是說,需要知道每一步所調(diào)度的訪存指令訪問的數(shù)據(jù)放置在磁疇壁存儲器的磁帶上哪個域中.因為在磁疇壁存儲器中有兩個讀/寫頭進行數(shù)據(jù)的讀/寫,分別為port0 和port1.并且磁帶的前半部分域由port0 進行訪問,磁帶的后半部分域由port1進行訪問,因此需要建模每個位置與其對應(yīng)讀/寫頭的偏移位置.例如,磁帶上有8 個域,分別編號為域0～域7.port0 訪問域0～域3,port1 訪問域4～域7.初始狀態(tài)下,port0 與域1 對齊,port1 與域5 對齊.對于port0 來說,域1是第1 個位置;對于port1 來說,域5 是第1 個位置.如果域1 中的數(shù)據(jù)被訪問之后,立即訪問域5 中的數(shù)據(jù),那么就不需要移動操作,此時移動次數(shù)為0.如果使用的不是偏移位置進行計算,則是5-1=4,會出現(xiàn)計算錯誤.因此,建模移動次數(shù)需要獲得偏移位置.

定義一個列表posoff記錄每個域的偏移位置,即.例如:如果磁帶容量為8,則posoff=[0,1,2,3,0,1,2,3].

對于每個數(shù)據(jù)k和訪存指令i,如果訪存指令i訪問數(shù)據(jù)k,那么數(shù)據(jù)k和訪存指令i直接的映射關(guān)系為

定義offset(i)表示訪存指令i所訪問數(shù)據(jù)的偏移位置,該約束可以表示為

如果變量Xi,l=1 表示訪存指令i在第l步調(diào)度執(zhí)行,定義position(l)來表示第l步調(diào)度執(zhí)行的訪存指令i所訪問數(shù)據(jù)的偏移位置,它可以表示為

也就是說,當訪存指令i在第l步調(diào)度執(zhí)行時,就將訪存指令i所訪問數(shù)據(jù)的偏移位置賦值給position(l).不幸的是,該表達式是非線性的.根據(jù)定理1,它可以線性表示為

其中,B是一個大數(shù).

假設(shè)shift(l)記錄的是從當前步l到下一步l+1 所需要移動的次數(shù),那么從第l步到第l+1 步的移動次數(shù)可以表示為

該公式可以根據(jù)定理2 重寫為線性公式,如下:

(4) 目標函數(shù).

整數(shù)線性規(guī)劃的目標函數(shù)是總移動次數(shù)最小,線性公式表示為

4.2 生成指令調(diào)度和數(shù)據(jù)放置(GISDP)算法

本節(jié)提出了一個啟發(fā)式算法——生成指令調(diào)度和數(shù)據(jù)放置(GISDP)算法,該算法可以生成一個指令調(diào)度和數(shù)據(jù)放置方案,使得總移動次數(shù)達到近似最優(yōu).由于提出的GISDP 算法基于賽道存儲技術(shù)的存儲器,所以適用于本文所提到的磁疇壁存儲介質(zhì)的存儲器,也同樣適用于斯格明子介質(zhì)的存儲器.

GISDP 算法是一個三段式算法,其主要思想是:首先由算法1 根據(jù)IAFGG同時生成指令調(diào)度序列和數(shù)據(jù)放置策略;然后,算法2 在算法1 結(jié)果的基礎(chǔ)上對數(shù)據(jù)放置進行改進;最后,算法3 根據(jù)算法2 改進的結(jié)果對指令調(diào)度進行改進.

在介紹GISDP 算法細節(jié)之前,先介紹等價類的概念.在有多個讀/寫頭的磁疇壁存儲器上,磁帶上的域被m個讀/寫頭平均分成m段,每段都有相同的偏移地址.因此在任何時刻,m個讀/寫頭所處域的偏移地址相同.例如:假設(shè)P和Q分別是讀/寫頭port1 和port3 所管轄段中域的集合,那么如果P中的域p和Q中的域q有相同的偏移位置,則域p和域q是等價的,即,數(shù)據(jù)放在域p和放在域q中的效果是一樣的.由于讀/寫頭的數(shù)量為m,因此等價類的大小是m.

GISDP 算法第1 部分(算法1)的主要思想是:將需要訪問但還未被放置的數(shù)據(jù)放置在讀/寫頭當前所指向的域中,如果當前所有讀/寫頭指向的域均已放置數(shù)據(jù),那么進行移動操作,使得讀/寫頭和相鄰的下一個域?qū)R,將數(shù)據(jù)放置到距離讀/寫頭最近的空閑域中.然后再將訪問該數(shù)據(jù)且不依賴于其它未執(zhí)行指令的所有指令進行調(diào)度.如算法1 所述,輸入為IAFGG和目標系統(tǒng)架構(gòu);輸出為一個指令調(diào)度sch、一個數(shù)據(jù)放置place、移動次數(shù)shift、一個記錄產(chǎn)生移動操作的連續(xù)訪問的數(shù)據(jù)對列表shift_data、一個記錄產(chǎn)生移動操作的移動次數(shù)的列表shift_count.

算法第1 行,統(tǒng)計G中入度為0 的指令和不為0 指令及其入度,分別存入列表list0 和list1 中;在算法初始階段,指令調(diào)度sch和數(shù)據(jù)放置place為空,并且所有port 均指向偏移位置為0 的域處,此時的狀態(tài)需要執(zhí)行第6行～第9 行,隨機選取滿足條件的指令調(diào)度,并把指令所訪問數(shù)據(jù)放置在此時port 所指向域中的任一空閑域,同時更新列表list0,list1 以及數(shù)據(jù)D集合.另一種狀態(tài),在port 所指向域中有數(shù)據(jù)且list0 中有訪問這些數(shù)據(jù)的指令時,則執(zhí)行第5 行.當以上兩種狀態(tài)下均未在list0 中找到可調(diào)度指令,則要執(zhí)行第11 行,進行移動操作之后的狀態(tài)將會是前兩種狀態(tài)中的一種,則重復(fù)執(zhí)行第4 行～第9 行.在數(shù)據(jù)D集合為空的情況下,說明數(shù)據(jù)均已被放置.接下來只需要將剩余指令調(diào)度完成.調(diào)度過程中,先調(diào)度訪問當前port 所指向域中數(shù)據(jù)的指令,即第15 行;沒有滿足條件的指令,則需要執(zhí)行第17 行和第18 行,調(diào)度list0 中訪問距離當前域最近的域中數(shù)據(jù)的指令.直至所有指令調(diào)度完成.

生成了調(diào)度sch和數(shù)據(jù)放置place后,執(zhí)行第21 行,將統(tǒng)計得到總移動次數(shù)shift,產(chǎn)生移動操作的連續(xù)訪問的數(shù)據(jù)對,存入列表shift_data,及數(shù)據(jù)對所對應(yīng)移動次數(shù),存入列表shift_count進行輸出.

算法1.GISDP 算法第1 部分——由IAFG 同時生成調(diào)度和數(shù)據(jù)放置.

輸入:一個IAFGG=〈V,E,D〉;

磁帶的容量N,M個讀/寫頭;

輸出:一個指令調(diào)度sch;

算法2 的主要思想是:根據(jù)算法1 生成的結(jié)果計算連續(xù)訪問數(shù)據(jù)對的相關(guān)度,依據(jù)將相關(guān)度大的數(shù)據(jù)放在等價位置的原則對數(shù)據(jù)放置進行改進.如算法2 所描述,輸入為IAFGG、目標系統(tǒng)架構(gòu)以及算法1 的輸出;輸出為比算法1 總移動次數(shù)少的數(shù)據(jù)放置順序place、總的移動次數(shù)shift、一個記錄移動次數(shù)的列表shift_count.

算法第1 行,根據(jù)算法1 生成的產(chǎn)生移動操作時連續(xù)訪問的數(shù)據(jù)對的列表shift_data計算數(shù)據(jù)對連續(xù)訪問的次數(shù),并存入列表count中.第2 行,根據(jù)列表count,shift_count和shift_data,將連續(xù)次數(shù)count與對應(yīng)數(shù)據(jù)對的總移動距離相乘得到數(shù)據(jù)對的相關(guān)度,并根據(jù)數(shù)據(jù)對的相關(guān)度的降序排列將相關(guān)度和數(shù)據(jù)對存入列表relate中.從最大相關(guān)度的數(shù)據(jù)對入手,如果數(shù)據(jù)對(m,n)中的數(shù)據(jù)m和n放置在同一個位置段,則執(zhí)行第8 行和第9 行;否則,執(zhí)行第5 行和第6 行.在將數(shù)據(jù)m放在等價位置處后,則原位置處的數(shù)據(jù)r被交換到數(shù)據(jù)m的原位置處.進行數(shù)據(jù)交換之后,就會導(dǎo)致r與原來相鄰位置及等價位置處的數(shù)據(jù)的距離增加,所以需要將r當前所在域到m當前所在域之間的數(shù)據(jù)(包括r,不包括m)向r所在域的方向循環(huán)移一個位置.為了減少r與之前相鄰域及等價域中數(shù)據(jù)的相對距離,需要對所有段中該區(qū)間的域中的數(shù)據(jù)循環(huán)移動一個位置.在進行交換位置及移動操作之后,會重新計算總的移動次數(shù):如果移動次數(shù)減少,則會保留此次交換,更新數(shù)據(jù)放置place,并重新計算相關(guān)度;如果移動次數(shù)不變或者增加,則本次交換取消,進行下一個相關(guān)度數(shù)據(jù)對的位置重置.

在交換到數(shù)據(jù)對的相關(guān)度為1 的時候,則停止位置重置,此時的數(shù)據(jù)放置作為新的放置策略進行輸出.

算法2.GISDP 算法第2 部分——修改數(shù)據(jù)放置.

輸入:一個IAFGG=〈V,E,D〉;

磁帶的容量N,M個讀/寫頭;

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

輸出:比算法1 總移動次數(shù)少的數(shù)據(jù)放置順序place;

總的移動次數(shù)shift;

一個記錄移動次數(shù)的列表shift_count.

在算法2 對數(shù)據(jù)的放置進行改進之后,算法3 根據(jù)算法2 的數(shù)據(jù)放置和IAFGG對指令進行了重調(diào)度,以獲得與新數(shù)據(jù)放置策略相適宜的指令調(diào)度.算法3 的主要思想是:盡量將訪問當前port 所在域中數(shù)據(jù)的指令進行調(diào)度,沒有可調(diào)度的指令則移動一個位置.當port 移動到有指令可調(diào)度的域的時候,將會更新port 的狀態(tài).最后統(tǒng)計該調(diào)度下的移動次數(shù),與重調(diào)度之前的移動次數(shù)進行比較,如果移動次數(shù)減少,則保留此次的調(diào)度;否則不更新調(diào)度.

算法3.GISDP 算法第3 部分——改進指令調(diào)度.

輸入:一個IAFGG=〈V,E,D〉;

磁帶的容量N,M個讀/寫頭;

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

輸出:一個指令調(diào)度列表sch;

總的移動次數(shù)shift.

算法1 的時間復(fù)雜度為O(|V|×|D|),在一個磁帶中,|D|最大為磁帶容量,即數(shù)據(jù)量,|V|為應(yīng)用中訪存指令數(shù)量;算法2 的時間復(fù)雜度為表示應(yīng)用中連續(xù)訪問數(shù)據(jù)的相關(guān)度大于1 的數(shù)據(jù)對可能的最大個數(shù);算法3 的時間復(fù)雜度為O(|V|).

5 實 驗

本節(jié)首先介紹實驗設(shè)置,然后通過實驗對比展示本文所提出的ILP 和GISDP 算法的效率,并對實驗結(jié)果進行分析.

5.1 實驗設(shè)置

本文從MediaBench[26]基準套件中選擇8 個應(yīng)用程序進行實驗,這8 個應(yīng)用程序分別為epic,ghostscript,jpeg,mesa,mpeg,pegwit,pgp 和rasta.將本文所提出的ILP 和GISDP 算法與不同的算法進行比較:(1) SSDP 算法,將指令進行順序調(diào)度并且按照數(shù)據(jù)的訪問順序進行順序放置的一種算法; (2) S-DBC-P 算法,Chen 等人[20]提出的在固定調(diào)度的情況下,對數(shù)據(jù)進行分組放置的一個算法;(3) GISDP 算法,本文所提出的啟發(fā)式算法;4) ILP 方法,本文所提出的可以得到最優(yōu)解的模型.將本文提出的算法與其他算法比較之后,本文繼續(xù)對啟發(fā)式算法自身的三段算法進行性能提升的比較與討論.

本文使用SimpleScalar 模擬器[27]對基準程序進行指令提取并生產(chǎn)指令訪問流圖,同時,本文設(shè)計了磁疇壁存儲器訪問行為模擬器.將指令訪問流圖以及每條指令所訪問數(shù)據(jù)輸入到模擬器中,使用不同的算法可以在模擬器中生成指令調(diào)度與數(shù)據(jù)放置方案,并獲得總的移動次數(shù).在模擬器中,假設(shè)數(shù)據(jù)能夠全部存儲在磁疇壁存儲器中.本文分別對讀/寫頭數(shù)量為2,4,8 時的磁疇壁存儲器進行了設(shè)計空間的探索實驗.

對于ILP 模型,使用python3 調(diào)用Gurobi 中的接口[28]對ILP 模型進行編寫,并運行ILP 程序.對于某些測試程序,ILP 不能在可接受的時間范圍內(nèi)找到最優(yōu)解,所以本文設(shè)定在ILP 模型被執(zhí)行12 小時(43 200 秒)之后便停止執(zhí)行,并將當前的結(jié)果輸出.其中,最優(yōu)解使用“*”標記.其他的算法均是可以在幾百毫秒時間內(nèi)完成的.

5.2 實驗結(jié)果與分析

本節(jié)對我們的實驗結(jié)果進行展示與分析.

表2 是在配備2 個讀/寫頭的磁疇壁存儲器上不同算法產(chǎn)生的實驗結(jié)果.其中:“SSDP”列表示SSDP 算法得到的移動次數(shù);“S-DBC-P”列是Chen 等人[20]提出的算法得到的移動次數(shù),以及相較于SSDP 算法移動次數(shù)減少的百分比;“GISDP”列是本文所提出的啟發(fā)式算法求得的移動次數(shù),以及分別相較于SSDP 算法和S-DBC-P 算法移動次數(shù)減少的百分比;“ILP”列是整數(shù)線性規(guī)劃在12 小時內(nèi)求得的移動次數(shù),以及分別相較于SSDP 算法和S-DBC-P 算法移動次數(shù)減少的百分比.從表2 可以看出:本文所提的GISDP 算法相較于SSDP 算法,移動次數(shù)平均減少了86.7%,相較于S-DBC-P 算法,移動次數(shù)平均減少了79.6%;本文所提出的ILP 模型雖然沒有在12 小時內(nèi)求出最優(yōu)解,但是相較于SSDP 算法,移動次數(shù)平均減少了75.0%,相較于S-DBC-P 算法,移動次數(shù)平均減少了61.8%.

Table 2 Performance comparison for 2-port表2 2 個port 的性能比較

表3 是在配備4 個讀/寫頭的磁疇壁存儲器上不同算法產(chǎn)生的實驗結(jié)果.從表3 可以看出:本文所提的S-DBC-P 算法相較于SSDP 算法移動次數(shù)平均減少了93.7%,相較于S-DBC-P 算法移動次數(shù)平均減少了80.7%;本文所提出的ILP 模型在12 小時內(nèi)求出的局部最優(yōu)解,相較于SSDP 算法,移動次數(shù)平均減少了82.6%,相較于S-DBC-P 算法,移動次數(shù)平均減少了46.3%.

Table 3 Performance comparison for 4-port表3 4 個port 的性能比較

表4 是在配備8 個讀/寫頭的磁疇壁存儲器上不同算法產(chǎn)生的實驗結(jié)果,從表4 可以看出:本文的S-DBC-P算法相較于SSDP 算法移動次數(shù)平均減少了97.3%,相較于S-DBC-P 算法移動次數(shù)平均減少了85.6%;本文提出的ILP 模型相較于SSDP 算法移動次數(shù)平均減少了94.8%,相較于S-DBC-P 算法移動次數(shù)平均減少了75.6%.

Table 4 Performance comparison for 8-port表4 8 個port 的性能比較

從3 個表中可以看出:ILP 只有在配備8 個讀/寫頭的磁疇壁存儲器上的實驗結(jié)果有求出最優(yōu)結(jié)果的情況,且本文的GISDP 算法所求得結(jié)果與ILP 最優(yōu)結(jié)果相近.如表4 中基準測試程序pegwit 的結(jié)果,GISDP 算法的移動次數(shù)分別相較于SSDP 算法和S-DBC-P 算法減少了96.1%和85.7%,ILP 模型的移動次數(shù)分別相較于SSDP算法和S-DBC-P 算法減少了97.0%和88.7%,所以本文的GISDP 算法可以在多項式時間內(nèi)求得近似最優(yōu)解.在配備2 個讀/寫頭和4 個讀/寫頭的磁疇壁存儲器上的實驗結(jié)果均沒有在12 小時內(nèi)找到最優(yōu)解,所以這兩個表中的ILP 結(jié)果均是12 小時得到的局部最優(yōu)解.

在本文提出的ILP 模型中,ILP 的約束條件的數(shù)量是固定的,影響ILP 求解效率的主要因素是輸入的IAFGG中|V|,|E|和|D|的大小以及讀/寫頭的數(shù)量.當讀/寫頭的數(shù)量為2 時,在滿足依賴關(guān)系的前提下,對指令進行調(diào)度和數(shù)據(jù)進行放置,相當于是進行全排列,并選擇最優(yōu)的情況.當|E|很小,即依賴關(guān)系很少,滿足依賴的排列數(shù)接近全排列.當|V|和|D|很大時,全排列的復(fù)雜度使得ILP 無法在多項式時間內(nèi)求得最優(yōu)解決策略.不過,當讀/寫頭的數(shù)量為8 時,一部分基準測試程序的ILP 收斂速度有所提高(如表4),但是所需時間仍不能與啟發(fā)式算法所需的時間相比.可以看出:ILP 模型雖然可求最優(yōu)解,但是不能在多項式時間內(nèi)完成,不適合用在數(shù)據(jù)密集型應(yīng)用的系統(tǒng)中.

表5 是在配備2 個讀/寫頭的磁疇壁存儲器上GISDP 算法中三段算法分別得到的結(jié)果,其中,算法2 相對于算法1 移動次數(shù)平均減少了9.81%,算法3 相對于算法2 移動次數(shù)平均減少了9.43%.從表5 中可以看出:部分基準測試程序在算法2 及算法3 中,移動次數(shù)減少了0%,是因為不同的測試程序具有不同的數(shù)據(jù)訪問特性;并且算法2 和算法3 均是在自身所求得的結(jié)果與前一段算法所求得的結(jié)果中選取更優(yōu)的結(jié)果.因此對于部分應(yīng)用,會在算法1 或算法2 中就求得近優(yōu)解.

實驗結(jié)果顯示:本文所提的算法可以找到較優(yōu)的指令調(diào)度和數(shù)據(jù)放置策略,并且有效地減少了總的移動次數(shù).因為考慮了連續(xù)訪問數(shù)據(jù)對的相關(guān)度對數(shù)據(jù)放置進行了改進,同時根據(jù)放置進行了指令重調(diào)度,所以本文所提的算法可以到達較好的性能.

6 結(jié) 論

本文針對數(shù)據(jù)密集型應(yīng)用,面向配備多個讀/寫頭的磁疇壁存儲器的單核處理器系統(tǒng)研究最優(yōu)指令調(diào)度與數(shù)據(jù)放置方案來獲得最少的移動操作次數(shù),以提升磁疇壁存儲器的存儲訪問性能,進而提升系統(tǒng)性能.本文提出了可以在配備多個讀/寫頭的磁疇壁存儲器上生成最優(yōu)的指令調(diào)度和數(shù)據(jù)放置方案的ILP 模型,可以求得最小的移動次數(shù).因為ILP 模型的時間復(fù)雜度呈指數(shù)級,本文提出了可以在配備多個讀/寫頭的磁疇壁存儲器上,在多項式時間內(nèi)生成近似最優(yōu)的指令調(diào)度和數(shù)據(jù)放置方案(GISDP)的啟發(fā)式算法,以此來減小移動次數(shù).對配備不同數(shù)量讀/寫頭的磁疇壁存儲器的存儲訪問性能進行設(shè)計探索與實驗,表明本文所提出的ILP 模型和GISDP 算法能夠生成最優(yōu)和近似最優(yōu)的指令調(diào)度與數(shù)據(jù)放置方案.

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