一種基于改進的動態(tài)規(guī)劃思路的眾核軟件映射算法

覃志東, 馮 瑩, 肖芳雄

(1.東華大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，上海 201620；2.金陵科技學(xué)院 軟件工程學(xué)院，江蘇 南京 211169)

0 引 言

服務(wù)器多線程程序在操作系統(tǒng)調(diào)度下并發(fā)執(zhí)行，其執(zhí)行狀態(tài)具有固有的不確定性，并在訪問共享資源時，易導(dǎo)致競爭與死鎖等問題.Lee等[1]認為，一些具有更細粒度并行性的嵌入式程序需用數(shù)據(jù)流圖描述，并遵循任務(wù)間的結(jié)構(gòu)和依賴關(guān)系，采取離線分配與調(diào)度方式向處理器映射，可有效提升系統(tǒng)的可預(yù)測性和可靠性.眾核軟件映射屬于NP-hard問題，當(dāng)前無法設(shè)計出多項式時間復(fù)雜度的確切解算法.對此，研究者往往結(jié)合問題實際，設(shè)計出近似算法或者啟發(fā)式算法進行求解[2-3].此外，眾核軟件映射的具體方式有兩種：一是處理器核心流水線執(zhí)行方式[4]；二是處理器核心并發(fā)執(zhí)行方式[5].就如何最大化系統(tǒng)吞吐率的問題，文獻[4]通過對任務(wù)圖的多次均衡雙劃分來達到提升系統(tǒng)吞吐率的目的.但該方法一方面可能會導(dǎo)致任務(wù)分配不均衡性的累積效應(yīng)；另一方面無法適用于處理器核心是奇數(shù)的場景.文獻[6]提出了基于模擬退火思路和貪心法則的任務(wù)圖劃分算法(SAATSA)，但該算法屬于啟發(fā)式近似算法，在求解過程中易陷入局部最優(yōu)解.動態(tài)規(guī)劃通過拆分問題，以遞推的方式求解，易獲得全局最優(yōu)解，在諸如庫存管理、資源分配等問題求解方面取得較好的效果.此外，在軟硬件劃分方面，文獻[7]也基于動態(tài)規(guī)劃思路提出了一種優(yōu)化的算法.

本研究在剖析了眾核軟件基于流水線方式映射問題的基礎(chǔ)上，提出了一種基于改進的動態(tài)規(guī)劃思路的眾核軟件映射算法，該算法在獲得最大吞吐率方面獲得了較好的效果.

1 軟件映射問題

1.1 基于處理器核心的流水線映射方式

眾核軟件內(nèi)部結(jié)構(gòu)與任務(wù)模塊之間的依賴關(guān)系可以用有向無循環(huán)圖G(V,E)表示.其中，V代表任務(wù)負載，E表示任務(wù)間的通信量與方向.對任務(wù)集的分配即是在滿足任務(wù)之間的依賴關(guān)系的基礎(chǔ)上對圖G(V,E)進行劃分.如圖1所示，對邊(ab,bd,ce)進行切割，可得任務(wù)子圖G1(V1,E1)、G2(V2,E2)、G3(V3,E3)、G4(V4,E4).用C代表切割邊集合，則該圖的劃分可表達為，

圖1 任務(wù)圖劃分示意圖

(1)

任務(wù)圖劃分后，得到的各任務(wù)子圖向處理器平臺上的對應(yīng)核心映射，便實現(xiàn)了任務(wù)子集向核心的映射，如圖2所示.而處理器核心按照任務(wù)子圖間的依賴關(guān)系先后執(zhí)行，便構(gòu)成了核心的執(zhí)行流水線[4-6]，其流水周期由最長執(zhí)行處理器核心2決定，如圖3所示.顯然，流水線填滿后，每過一個流水周期T，系統(tǒng)就有一個輸出，而各任務(wù)子圖負載越均衡，周期T越短，系統(tǒng)吞吐率越大.

圖2 任務(wù)子圖向處理器核心映射示意圖

圖3 處理器核心流水線執(zhí)行方式示意圖

1.2 眾核軟件映射問題的形式化描述

1.2.1 眾核軟件映射過程剖析

為便于映射算法的設(shè)計，本研究用一個問題實例來展示任務(wù)映射與綁定的流程，并分析相關(guān)的細節(jié)問題和影響吞吐率的因素.

(1)邏輯處理器抽象.圖4中，(A)是一個具有四核心的物理處理器.根據(jù)各核心的個數(shù)、互聯(lián)方式以及緩存的設(shè)置方式等，可以把物理處理器抽象為邏輯處理器，如圖4(G)所示.其中，物理核心Core3被抽象為邏輯核心P2，而物理核心Core2被抽象為邏輯核心P3.真實的眾核處理器上核心很多，有些核心甚至壞掉，在使用時，可以根據(jù)具體情況選擇一些核心來使用，并把它抽象成邏輯處理器[8].

圖4 眾核軟件映射過程示例圖

(2)數(shù)據(jù)流圖分析與轉(zhuǎn)換.圖4中，(B)是用同步數(shù)據(jù)流圖(SDF)表示的一個眾核軟件例子.該軟件由6個任務(wù)v、u、x、y、z和t組成，分別實現(xiàn)低通濾波、傅里葉變換、數(shù)據(jù)分發(fā)、數(shù)據(jù)快插和數(shù)據(jù)融合.其中，v運行1次要消耗1單元的數(shù)據(jù)并產(chǎn)生1單元數(shù)據(jù).u運行1次要消耗32單元的數(shù)據(jù)并產(chǎn)生32單元數(shù)據(jù).所以，為滿足軟件系統(tǒng)的正常運行，v需要連續(xù)運行32次，u才運行1次，而x需16次，y、z和t各需1次.此時，通信量為32.可把這種調(diào)度平衡后的負載與通信用有向無循環(huán)圖4(C)表示.目前已有很多算法解決SDF圖的平衡調(diào)度[9]，平衡調(diào)度好的SDF圖可以直接用有向無循環(huán)圖表示，供劃分映射.

(3)軟件向邏輯處理器映射.此階段由映射算法把圖4(C)的有向無循環(huán)圖向邏輯處理器映射，如圖4(D)所示.假定，v、u、x映射到P1，y、z映射到P2，t映射到P4，便構(gòu)成了一個3段流水線.最大化這個流水線吞吐率，是本研究要解決的問題.但問題的解決需要考慮任務(wù)綁定在核心上的具體情況.

(4)軟件任務(wù)向處理器核心綁定.如圖4(E)和(H)所示，劃分好的任務(wù)集需要綁定到映射的邏輯核心所對應(yīng)的物理核心.如y、z對應(yīng)的是邏輯核心P2，要綁定到物理核心Core3.此時，需要根據(jù)任務(wù)間的相對位置建立通信.若2個任務(wù)在一個核心上，那么定義數(shù)組變量，完成數(shù)據(jù)通信，如vu[32]便是v對u的通信.若兩者不在一個核心上，那么要定義數(shù)據(jù)發(fā)送/接收函數(shù)，如write(xy[1∶16],core3)便是x向y所在的Core3的緩存寫數(shù)據(jù)，而read(xy[1∶6],core3)便是y把x寫在本地緩存的數(shù)據(jù)讀出來.顯然,write函數(shù)是跨越處理器核心的，其通信時間是受具體通信鏈路決定的.為了讓任務(wù)利用以及產(chǎn)生通信數(shù)據(jù)，還要對任務(wù)加上封裝函數(shù)，如Hu(vu[1∶32],ux[1∶32]).

1.2.2 問題形式化描述

事實上，任務(wù)分配并綁定到核心后，雖然要對任務(wù)打包封裝并建立核心內(nèi)任務(wù)間通信變量，但是其額外的開銷與任務(wù)本身的負載相比可以忽略[4].真正影響系統(tǒng)吞吐率的因素是任務(wù)的負載和核心間任務(wù)的通信代價.所以，為了最大化吞吐率，首先映射到核心上的負載需均衡.即分配到不同核心的任務(wù)子圖的最大負載量和最小負載量之差應(yīng)盡可能地小，如式(2)所示,

(2)

式中，N為劃分的子圖數(shù)；wi為各子圖的負載量.

另外，核心間任務(wù)的通信代價與處理器的緩存的配置有關(guān).當(dāng)采用集中式緩存時，核心共享緩存，核心間通信的write和read函數(shù)都需要經(jīng)過片上網(wǎng)絡(luò)對該緩存進行操作；當(dāng)采用分布式緩存時，read不需要使用片上網(wǎng)絡(luò)，write則需要[10].

本研究針對分布式緩存建模，具體如圖5所示.對于圖1中邊ab，若任務(wù)a和b在不同的核心執(zhí)行，任務(wù)a需通過片上網(wǎng)絡(luò)向任務(wù)b所在核心的私有緩存寫入3單元的數(shù)據(jù)量，任務(wù)b再從自己的私有緩存讀取數(shù)據(jù).但這種通信方式對于任務(wù)a所在核心要產(chǎn)生額外的通信代價.因此，為最大化吞吐率，任務(wù)圖劃分時，需盡量減少通信代價，如式(3)所示，

圖5 不同處理器上的任務(wù)通信方式示意圖

mineεC{n(e)}

(3)

式中，C為所有切割邊集合；n表示通信代價.

基于以上分析，則基于流水執(zhí)行的眾核軟件映射問題可以形式化表達為下式，

minimizeQ

Q=F{‖wi‖,‖C‖}

s.t.V1∪V2∪…∪Vn=V

E1∪E2∪…∪EN∪C=E

(4)

式中，成本函數(shù)Q以系統(tǒng)的執(zhí)行周期進行建模，是系統(tǒng)吞吐率的倒數(shù).

2 基于吞吐率優(yōu)化的軟件映射算法設(shè)計

2.1 改進的動態(tài)規(guī)劃優(yōu)化算法思路

本研究以動態(tài)規(guī)劃算法作為基本優(yōu)化思路，并對其進行了2方面改進.

2.1.1 動態(tài)更新可選結(jié)點

區(qū)別于一般動態(tài)規(guī)劃算法，可選結(jié)點雖然也只有2個狀態(tài)：可選和不可選，但不可選是由2個原因造成:已經(jīng)被選擇了或存在依賴關(guān)系.所以，改進的動態(tài)規(guī)劃算法每選擇一個任務(wù)結(jié)點時，考慮依賴關(guān)系的變化，并實時更新可選結(jié)點(可選的值).

2.1.2 動態(tài)調(diào)整期望值exp

由于任務(wù)結(jié)點負載值具有顆粒性，利用動態(tài)規(guī)劃思路對任務(wù)圖進行劃分時，子圖結(jié)點的負載以及通信代價之和有時不會正好等于期望值.當(dāng)出現(xiàn)加上該結(jié)點的子圖的負載超過了期望值時，此時需要比較在沒有加上這個結(jié)點和加上了這個結(jié)點時的負載之和跟期望值之間的距離大小，并選擇距離較小的那種方案.因此，在對任務(wù)圖進行劃分時可以將問題簡化為：對于一些結(jié)點(此時的可選結(jié)點是動態(tài)變化的)，在限定總負載之和的情況下，如何劃分使得負載之和跟期望值距離最近，用公式表示為，

min1

(5)

式中，exp表示期望負載，絕對值表示實際負載和期望負載的差值，其目標(biāo)就是盡可能地讓差值最小.

如果按照上述方法，便會出現(xiàn)負載之和大于或者小于期望值的情況.為了減少子圖間負載之和的差距過大對系統(tǒng)吞吐率的影響，本研究使用動態(tài)調(diào)整子圖期望負載的機制.即除了第一個子圖，其余的子圖的結(jié)點的負載之和由其前面所有子圖的負載決定，每產(chǎn)生一個新的子圖，則需要動態(tài)改變允許負載的期望值.例如，在對任務(wù)圖進行劃分時，從第一個任務(wù)子圖到倒數(shù)第二個任務(wù)子圖的負載之和一直小于(大于)期望值，那么最后一個子圖的期望值便可能會很大(很小).如表1所示，在對一個任務(wù)圖進行劃分時，最初設(shè)定的期望負載值為40.

表1 采用動態(tài)調(diào)整大小機制所對應(yīng)的子圖負載

表1中，第一行數(shù)據(jù)為未采用動態(tài)調(diào)整子圖期望負載所對應(yīng)的最終劃分好的各個子圖的負載值，該劃分形成的流水線周期為59單位時間.而第二行數(shù)據(jù)為采用了該機制后所對應(yīng)的各個子圖的負載值，該劃分形成的流水線周期為42單位時間.顯然，采用動態(tài)調(diào)整子圖期望負載進行圖劃分后，各個子圖的負載更均衡，形成的流水線周期更小，流水線的吞吐率更大.在子圖劃分時，子圖動態(tài)期望負載由式(6)決定，

(6)

改進的動態(tài)規(guī)劃算法偽代碼如下：

算法1:改進的動態(tài)規(guī)劃算法/?options//可選結(jié)點w[]//任務(wù)結(jié)點的負載flag[]//結(jié)點的狀態(tài)C//子圖的期望負載m[]//狀態(tài)轉(zhuǎn)移方程對應(yīng)的值n//任務(wù)圖結(jié)點個數(shù)result[]//最優(yōu)解的值,以及選擇的結(jié)點 ?/optionsupdateNode(G)for var i0 to c for var j0 to jfor var k0 to j for var l0 to options,length if(flag[l]==1) if(m[i-1][k]+w[l]≤j) if(result[i-1])

2.2 軟件映射算法設(shè)計

基于動態(tài)規(guī)劃思路的軟件映射算法(dynamic programming mapping algorithm，DPMA)偽代碼如下：

算法2:基于改進動態(tài)規(guī)劃的軟件映射算法/?Dynamin()//改進的動態(tài)規(guī)劃算法getCost()//計算通信代價之和G//任務(wù)圖N//需要劃分的子圖個數(shù)options//可選結(jié)點Gi//被劃分成的子圖updateNode()//更新可選結(jié)點add()//將結(jié)點加入到子圖中updateCost()//更新子圖的期望值results//記錄最優(yōu)解所對應(yīng)的結(jié)果Best//記錄當(dāng)前最優(yōu)解?/optionsundateNode(G)best0for var x 0 to N for var i0 to options,NodeNum Giadd(Dynamin(options,exp)) resultsGiif(getCost(results)>best)){ bestgetCost(resluts)optionsupdateNode(Gi)expupdateCost(i1 getWordload(Gi))

DPMA算法的基本步驟如下：

(1)對任務(wù)圖進行拓撲排序，更新可選結(jié)點，計算第一個子圖的期望值.

(2)利用改進的動態(tài)規(guī)劃的思路在滿足子圖的負載以及通信代價之和小于期望值時，求出放入1個結(jié)點時到放入n個結(jié)點時所對應(yīng)的最優(yōu)解.其中，n是一個不確定的數(shù).當(dāng)子圖的負載以及通信代價之和接近期望值時，該子圖劃分完畢，開始構(gòu)建下一個子圖.

(3)更新該子圖中的結(jié)點，更新可選結(jié)點.

(4)重復(fù)步驟(2)、(3)，直到最優(yōu)解的值等于期望值或者一直是某個數(shù)值保持不變，此時一個子圖構(gòu)建完成.

(5)根據(jù)已構(gòu)建完的子圖，更新子圖負載的期望值.

(6)重復(fù)步驟(2)、(3)、(4)構(gòu)建下一個子圖，直到已有的子圖的個數(shù)等于既定的子圖個數(shù).

3 實驗與分析

為了進一步分析改進后的基于動態(tài)規(guī)劃思路的軟件映射算法的性能，本研究從文獻[11]中的網(wǎng)站下載了包含300個任務(wù)的任務(wù)圖模型，每個模型中包含任務(wù)的負載、任務(wù)之間的依賴關(guān)系等信息.然后從中隨機選取10個文件進行對比實驗.在設(shè)計算法時，首先需要對任務(wù)圖中的數(shù)據(jù)進行處理，篩選出有用的數(shù)據(jù)，接著再基于數(shù)據(jù)做進一步的實驗分析.本實驗采用java語言實現(xiàn)，程序的運行環(huán)境為Mac Os.

實驗中，利用文獻[4]的DPTAA算法、文獻[6]的SAATSA算法以及本研究的DPMA算法將任務(wù)圖劃分成20、50、100個子圖，分別映射到20、50、100核心的處理器上，結(jié)果如圖6～圖8所示.其中，橫向代表隨機抽取的10個任務(wù)圖，縱向表示各任務(wù)圖劃分后子任務(wù)圖負載以及通信代價之和的最大、最小值之差值與期望值之比.

圖6 劃分成20個任務(wù)子圖3種算法對比情況

圖7 劃分成50個任務(wù)子圖3種算法對比情況

圖8 劃分成100個任務(wù)子圖3種算法對比情況

測試結(jié)果表明，經(jīng)DPMA算法映射的系統(tǒng)在吞吐率方面優(yōu)于其他2種算法的結(jié)果.其原因是DPMA算法相當(dāng)于把一個映射問題劃分成多個子問題，通過尋找每個子問題的最優(yōu)解從而得到較好的最終解;而DPTAA算法屬于近似算法，不斷地切割圖，可能導(dǎo)致結(jié)果變差;SAATSA算法通過不斷進行鄰域搜索，很可能陷入局部最優(yōu)解.

利用本研究的DPMA算法將具有100、300、500個任務(wù)的任務(wù)圖劃分成20個、50個、100個子圖并映射到處理器，結(jié)果如圖9～圖11所示.其中，橫向代表選中的10個任務(wù)圖，縱向表示系統(tǒng)的吞吐率.由圖可見，將任務(wù)圖劃分為100個子圖映射時，系統(tǒng)的吞吐率最大.

圖9 100個結(jié)點任務(wù)圖劃分情況

圖10 300個結(jié)點任務(wù)圖劃分情況

圖11 500個結(jié)點任務(wù)圖劃分情況

吞吐率，按照定義來說，是單位時間內(nèi)處理信息的量.若流水線周期T小，則流水線的吞吐率大.在對任務(wù)圖劃分時，隨著子圖個數(shù)的增多，每個子圖的負載以及通信代價之和會降低，則所映射的處理器核心運行的時間就減小，導(dǎo)致流水線的周期T減小，系統(tǒng)的吞吐率變大.

4 結(jié) 論

本研究基于動態(tài)規(guī)劃算法思路，設(shè)計出了一種高效的眾核軟件任務(wù)映射算法.利用該算法把眾核軟件任務(wù)映射到處理器核心上構(gòu)成流水線執(zhí)行，充分挖掘了眾核平臺和眾核軟件任務(wù)的并行性，能有效提高系統(tǒng)的吞吐率.特別地，由于系統(tǒng)的流水線執(zhí)行狀態(tài)相對簡單，該映射算法較適合一些對系統(tǒng)狀態(tài)可預(yù)計性和可靠性要求較高的領(lǐng)域.