異構(gòu)信號(hào)處理平臺(tái)中層次性流水線(xiàn)調(diào)度算法

楊平平,岳春生,胡澤明

(信息工程大學(xué) 信息系統(tǒng)工程學(xué)院，鄭州 450001)

0 概述

隨著無(wú)線(xiàn)通信技術(shù)的快速發(fā)展,任務(wù)計(jì)算和數(shù)據(jù)信號(hào)的處理量出現(xiàn)爆炸式增長(zhǎng),對(duì)通信裝備平臺(tái)的快速研發(fā)、實(shí)時(shí)處理能力提出更高要求,使得軟件無(wú)線(xiàn)電[1]平臺(tái)成為了研究熱點(diǎn)。目前,通用軟件無(wú)線(xiàn)電平臺(tái)有加泰羅尼亞大學(xué)的ALOE[2]、愛(ài)爾蘭圣三一學(xué)院的IRIS[3]和中國(guó)微軟研究院的SORA[4]等,這些平臺(tái)在信號(hào)處理方面應(yīng)用較少，而且弗吉尼亞理工學(xué)院研究的OSSIE[5]和被譽(yù)為“黑客無(wú)線(xiàn)電”的GNU Radio[6]只能用來(lái)完成通信系統(tǒng)的建模和仿真學(xué)習(xí)[7]。異構(gòu)信號(hào)處理平臺(tái)通過(guò)軟件和硬件的解耦,解決了不同平臺(tái)間的可移植性和可擴(kuò)展性等問(wèn)題,充分利用了異構(gòu)可重構(gòu)特性。但是當(dāng)前大多數(shù)實(shí)時(shí)任務(wù)調(diào)度算法是針對(duì)同構(gòu)系統(tǒng)提出的,對(duì)于異構(gòu)系統(tǒng)的實(shí)時(shí)調(diào)度算法研究還不成熟,需要進(jìn)一步深入研究[8]。

異構(gòu)平臺(tái)相比于同構(gòu)平臺(tái),由于其處理節(jié)點(diǎn)的異構(gòu)性,提高了平臺(tái)處理復(fù)雜任務(wù)的靈活性和效率。異構(gòu)和同構(gòu)平臺(tái)算法的不同之處主要在于任務(wù)劃分階段,即建立任務(wù)模型有無(wú)考慮處理節(jié)點(diǎn)的異構(gòu)性帶來(lái)的影響。異構(gòu)平臺(tái)的實(shí)時(shí)調(diào)度本質(zhì)上就是資源映射和任務(wù)調(diào)度,在滿(mǎn)足任務(wù)約束關(guān)系的前提下,對(duì)任務(wù)進(jìn)行合理的劃分,實(shí)現(xiàn)資源的負(fù)載均衡,減少任務(wù)的調(diào)度長(zhǎng)度,同時(shí)構(gòu)造低延遲的流水線(xiàn)調(diào)度,提高任務(wù)調(diào)度的實(shí)時(shí)性。

層次性流水線(xiàn)調(diào)度包括多層次任務(wù)劃分和同步流水線(xiàn)調(diào)度。文獻(xiàn)[9-10]提出一種應(yīng)用于A(yíng)LOE框架的資源映射算法,利用框架的同步機(jī)制和流水線(xiàn)調(diào)度[11],能夠保證應(yīng)用的服務(wù)質(zhì)量,但該算法缺少對(duì)任務(wù)粒度劃分的研究。文獻(xiàn)[12-13]研究一種面向多核處理器實(shí)時(shí)數(shù)據(jù)流的低通信軟件流水調(diào)度方法,利用整數(shù)線(xiàn)性規(guī)劃理論對(duì)通信和計(jì)算資源進(jìn)行統(tǒng)一建模,但該方法沒(méi)有考慮分布式環(huán)境對(duì)調(diào)度的影響,缺少對(duì)網(wǎng)絡(luò)拓?fù)浜蛯哟涡匀蝿?wù)并行優(yōu)化的研究。文獻(xiàn)[14]提出一種面向多核集群的數(shù)據(jù)流層次流水線(xiàn)并行優(yōu)化方法,利用任務(wù)中的并行性構(gòu)造低延遲流水線(xiàn)調(diào)度,但該方法針對(duì)同構(gòu)集群采用的是均衡劃分策略,在任務(wù)劃分時(shí)沒(méi)有考慮節(jié)點(diǎn)計(jì)算能力和節(jié)點(diǎn)間的通信速率。文獻(xiàn)[15]針對(duì)異構(gòu)計(jì)算中的非均衡劃分問(wèn)題,提出一種基于圖的多級(jí)劃分算法,利用處理器計(jì)算性能的不同將圖與節(jié)點(diǎn)計(jì)算能力成比例劃分,然而,該算法沒(méi)有考慮任務(wù)間的依賴(lài)關(guān)系。

現(xiàn)有流水線(xiàn)調(diào)度算法在任務(wù)劃分時(shí)未考慮硬件體系結(jié)構(gòu),即處理器節(jié)點(diǎn)的計(jì)算性能和通信帶寬資源帶來(lái)的影響。本文根據(jù)異構(gòu)信號(hào)處理平臺(tái)實(shí)時(shí)任務(wù)的特點(diǎn),提出層次性流水線(xiàn)調(diào)度方法。針對(duì)異構(gòu)信號(hào)處理平臺(tái)的任務(wù)劃分,提出負(fù)載均衡低通信同步開(kāi)銷(xiāo)的多層次劃分算法;在平臺(tái)對(duì)已有的事件觸發(fā)調(diào)度實(shí)時(shí)處理能力不強(qiáng)的情況下,采用低延遲的同步流水線(xiàn)調(diào)度。最后在A(yíng)TCA平臺(tái)下,以雷達(dá)等典型應(yīng)用為測(cè)試程序,驗(yàn)證該層次性流水線(xiàn)調(diào)度算法的有效性。

1 系統(tǒng)描述

1.1 異構(gòu)信號(hào)處理平臺(tái)

異構(gòu)信號(hào)處理平臺(tái)是將模塊化、標(biāo)準(zhǔn)化和通用化的硬件單元以總線(xiàn)或交換方式連接起來(lái)構(gòu)成通用平臺(tái),通過(guò)在平臺(tái)上加載可復(fù)用、可移植、可擴(kuò)展和易升級(jí)的標(biāo)準(zhǔn)化軟件模塊,實(shí)現(xiàn)各種信號(hào)處理功能[16]。異構(gòu)信號(hào)處理平臺(tái)在硬件體系架構(gòu)上采用通用的高性能硬件平臺(tái),如ATCA、CPCI、VPX等,平臺(tái)內(nèi)存在大量不同類(lèi)型的處理器,包括FPGA、DSP、GPU、GPP等。在軟件架構(gòu)上通過(guò)構(gòu)建標(biāo)準(zhǔn)化、規(guī)范化的層次式新型軟件體系架構(gòu),通過(guò)系統(tǒng)抽象屏蔽底層之間的差異,解決組件在異構(gòu)平臺(tái)中跨平臺(tái)操作和可移植性的難點(diǎn)。異構(gòu)信號(hào)處理平臺(tái)軟件體系架構(gòu)如圖1所示。

圖1 層次化新型信號(hào)處理平臺(tái)軟件體系架構(gòu)

圖1所示的異構(gòu)信號(hào)處理平臺(tái)軟件體系架構(gòu)主要分為硬件平臺(tái)層、操作系統(tǒng)層、驅(qū)動(dòng)抽象層、核心框架層、管理服務(wù)層和應(yīng)用層。其中,操作系統(tǒng)層與驅(qū)動(dòng)抽象層屬于運(yùn)行支撐服務(wù)層,能夠屏蔽底層處理單元的操作系統(tǒng)、通信、內(nèi)存及文件操作等硬件差異性,為上層提供統(tǒng)一規(guī)范的接口;核心框架層基于容器技術(shù)(包括FPGA容器、進(jìn)程容器、線(xiàn)程容器等)屏蔽處理器任務(wù)調(diào)度上的差異,實(shí)現(xiàn)應(yīng)用組件化調(diào)度服務(wù);管理服務(wù)層包括系統(tǒng)運(yùn)行管理環(huán)境和可視開(kāi)發(fā)管理兩大部分,提高應(yīng)用系統(tǒng)開(kāi)發(fā)的可視性以及便捷性;應(yīng)用層包括組件庫(kù)和應(yīng)用控制臺(tái),負(fù)責(zé)完成信號(hào)處理功能。目前,異構(gòu)信號(hào)處理平臺(tái)的開(kāi)發(fā)模式已經(jīng)成為一種發(fā)展趨勢(shì)。

1.2 異構(gòu)信號(hào)處理平臺(tái)任務(wù)模型

本文利用有向無(wú)環(huán)圖(Directed Acyclic Graph,DAG)描述異構(gòu)信號(hào)處理平臺(tái)應(yīng)用的處理流程,數(shù)據(jù)流程圖中節(jié)點(diǎn)和有向邊分別代表應(yīng)用的組件和通信鏈路。軟件無(wú)線(xiàn)電應(yīng)用可分解為一系列具有相互依賴(lài)關(guān)系、周期性執(zhí)行、可部署的軟件模塊或組件[17]。各軟件模塊之間存在數(shù)據(jù)流水依賴(lài)性,其中，某個(gè)組件的輸出可以是相應(yīng)下一步組件的輸入,因此，系統(tǒng)模型可用一個(gè)四元數(shù)組表示,記為G={V,E,C,L}。其中,G代表平臺(tái)的一個(gè)應(yīng)用，V={v1,v2,…,vn}是應(yīng)用所包含組件的集合,節(jié)點(diǎn)vi∈V表示應(yīng)用中的一個(gè)組件，E={e12,e23,…,eij}表示依賴(lài)關(guān)系的有向邊的集合,E?V×V,eij=(vi,vj)∈E表示組件vi和組件vj有直接通信鏈接,組件vi是組件vj的前驅(qū)節(jié)點(diǎn)，C={c1,c2,…,cn}表示組件的計(jì)算量集合,C(vi)表示組件vi的計(jì)算數(shù)據(jù)量，L(vi,vj)表示組件間的通信量集合。如圖2所示,每一個(gè)應(yīng)用都可以用DAG來(lái)表示。

圖2 應(yīng)用的DAG示意圖

表1 異構(gòu)信號(hào)處理平臺(tái)任務(wù)執(zhí)行時(shí)間

2 異構(gòu)信號(hào)處理平臺(tái)實(shí)時(shí)任務(wù)調(diào)度策略

2.1 基于DAG的多層次任務(wù)劃分方法

任務(wù)劃分是實(shí)時(shí)調(diào)度的首要步驟,快速有效的劃分方法是調(diào)度成功的關(guān)鍵。本文提出的基于DAG多層次劃分算法借鑒了多層圖劃分的思想,主要由3個(gè)階段組成:對(duì)DAG進(jìn)行分層拓?fù)渑判?順序融合分組進(jìn)行初始劃分以及局部非均衡聚簇。任務(wù)劃分的目的是為了保證節(jié)點(diǎn)間的負(fù)載均衡性,減少節(jié)點(diǎn)間的同步開(kāi)銷(xiāo),構(gòu)造低延遲高吞吐率的流水線(xiàn)調(diào)度。

2.1.1 DAG的分層拓?fù)渑判?/p>

分層拓?fù)渑判蚴菍?duì)DAG進(jìn)行預(yù)處理。由圖論可知,有向無(wú)環(huán)圖節(jié)點(diǎn)存在入度值,入度值指的是鄰接到某頂點(diǎn)弧的數(shù)目。預(yù)處理是根據(jù)節(jié)點(diǎn)的入度值,將有向無(wú)環(huán)圖分成多層,每層的組件沒(méi)有數(shù)據(jù)依賴(lài)關(guān)系的節(jié)點(diǎn),可以進(jìn)行并行處理。

DAG分層算法描述如下:

算法1任務(wù)分層算法

輸入原始DAGG(V,E)

輸出經(jīng)過(guò)分層后的DAGG:(V,E)

Void TopologicalSort (int Num); {//節(jié)點(diǎn)數(shù)目

Int gInDegree[MAX_NODE];

FindInDegree();//對(duì)各頂點(diǎn)求入度值

IniStack(S);//建立入度值頂點(diǎn)棧

for( int i = 0; i < Num; i++ )

if (! gInDegree[i] )

push (S,i);

//入度為0者進(jìn)棧,k層

While(! StackEmpty(S)){

pop(S,i);

gVisited [i] = true;//輸出i節(jié)點(diǎn)

for( int e = gHead[i]; e!= -1; e = gEdges[e].next){

int v = gEdges[e].to;

gInDegree[v]--;

//對(duì)i頂點(diǎn)的每個(gè)鄰節(jié)點(diǎn)的入度值減1

if ( ! gInDegree[v] ){

push (S,v);

//如果入度值減為0,則入棧,k+1層

}// END IF

}//END FOR

}//END WHILE

for (int i =0; i < Num; i++)

if(!gVisited [i]) return ERROR; //存在回路

}//輸出分層結(jié)果

圖3所示為DAG分層拓?fù)渑判蛱幚淼氖纠?其中,圖3(a)為一個(gè)異構(gòu)信號(hào)處理平臺(tái)應(yīng)用的DAG映射到處理器的示例，Vi表示組件,權(quán)值為組件在處理器上的執(zhí)行時(shí)間,圖3(b)描述了經(jīng)過(guò)任務(wù)分層后的DAG。首先計(jì)算圖3(a)中各個(gè)頂點(diǎn)的入度值,將所有入度值為0的節(jié)點(diǎn)放在第k層,然后將上一層頂點(diǎn)的所有邊消除,再計(jì)算新圖入度值為0的頂點(diǎn),放入第k+1層,直到DAG中不存在入度值為0的節(jié)點(diǎn)。分層拓?fù)渑判蚩梢詸z測(cè)DAG中是否出現(xiàn)環(huán)路,防止執(zhí)行時(shí)出現(xiàn)死鎖。

圖3 DAG分層拓?fù)渑判蚴纠?/p>

2.1.2 順序融合聚簇算法

順序融合聚簇是對(duì)分層處理后的DAG進(jìn)行初始劃分,將相鄰的節(jié)點(diǎn)進(jìn)行融合。任務(wù)劃分粒度越小,子任務(wù)數(shù)越多,并行程度越高,但通信開(kāi)銷(xiāo)就越大;相反,任務(wù)劃分粒度越大,通信開(kāi)銷(xiāo)越少,但并行度就越小。順序融合聚簇方法是消除通信延遲劃分算法中的一種,其將相鄰節(jié)點(diǎn)融合可以降低通信開(kāi)銷(xiāo)的收益,但有可能會(huì)喪失后驅(qū)節(jié)點(diǎn)的并行性。因此,順序融合聚簇時(shí)要盡量使任務(wù)之間的通信開(kāi)銷(xiāo)減小,又同時(shí)保持任務(wù)自身并行性以及預(yù)防出現(xiàn)環(huán)路情況。本文采用文獻(xiàn)[14]的DAG粗粒度融合方法,將相鄰節(jié)點(diǎn)融合產(chǎn)生的收益定義為:

(1)

其中,任務(wù)模型中的元素L(vi,vj)、C(vi)、C(vj)分別表示組件間的通信量、組件vi的計(jì)算量(即負(fù)載)和組件vj的計(jì)算量。

順序融合算法描述如下:

算法2順序融合算法

輸入經(jīng)過(guò)分層后的DAGG:(V,E)

輸出經(jīng)過(guò)順序融合后的DAGG:(V,E)

Graph G =ConstructGraph(DAG);

VertexNum = Count(G);//當(dāng)前節(jié)點(diǎn)數(shù)

averageWorkload = Weight(DAG)/ClusterNum;

// 理論上平均最佳負(fù)載

priorityQueue = ConstructpriorityQueue(G);

//收益為權(quán)值的優(yōu)先隊(duì)列

While(VertexNum > ClusterNum){

MaxGain = GetMaxGain(priorityQueue);

//優(yōu)先隊(duì)列中選擇收益最大的融合

If(maxGain<=0)break;

PairmaxGainCluster=

GetMaxGainCluster(priorityQueue,G);

ClusterWeight =Weight(cluster);

//計(jì)算當(dāng)前cluster的負(fù)載

If(ClusterWeight < averageWoekload && ErrorDAG) //當(dāng)前相鄰節(jié)點(diǎn)融合負(fù)載小于劃分后理論平均負(fù)載值且新//DAG沒(méi)有環(huán)路

PriorityQueue.delete(maxGainCluster);

//優(yōu)先隊(duì)列刪除最大收益值

newVertexr = Fused(Vi,Vj);

//融合后的新節(jié)點(diǎn)

G.update(Vi,Vj,newVertex);//更新DAG

PriorityQueue.update(maxGainCluster,

newVertexr);//更新收益優(yōu)先隊(duì)列

-- VertexNum;

}//END WHILE

ClusterNum是對(duì)節(jié)點(diǎn)數(shù)量設(shè)置的下限閾值,防止過(guò)度融合。順序融合算法首先計(jì)算理論上的平均最佳負(fù)載,采用貪心算法計(jì)算相鄰節(jié)點(diǎn)融合的收益,并構(gòu)造以收益為權(quán)值的優(yōu)先隊(duì)列。然后,從隊(duì)列中選擇收益最大的相鄰節(jié)點(diǎn)進(jìn)行融合,計(jì)算融合后節(jié)點(diǎn)的負(fù)載,如果當(dāng)前融合后的負(fù)載小于劃分后理論平均負(fù)載且新DAG沒(méi)有環(huán)路,那么就將參與融合的相鄰節(jié)點(diǎn)刪除,插入融合后的新節(jié)點(diǎn)并更新DAG,最后更新收益優(yōu)先隊(duì)列。算法經(jīng)過(guò)多次迭代,當(dāng)收益為負(fù)或者DAG中的節(jié)點(diǎn)數(shù)小于下限閾值時(shí),DAG中節(jié)點(diǎn)停止融合。圖4所示為DAG多層次劃分處理的示例,其中,圖4(a)中的節(jié)點(diǎn)vi表示組件,權(quán)值為組件的負(fù)載,圖4(b)描述了經(jīng)過(guò)融合后的DAG。

圖4 DAG多層次劃分示例

2.1.3 局部非均衡劃分算法

局部非均衡劃分算法考慮到異構(gòu)信號(hào)處理平臺(tái)中處理器的計(jì)算能力不同,為保證任務(wù)實(shí)時(shí)調(diào)度適應(yīng)更廣泛意義上的異構(gòu)負(fù)載均衡,任務(wù)粒度劃分要隨計(jì)算能力成正比例改變。局部非均衡算法要盡量保證任務(wù)間通信開(kāi)銷(xiāo)減小,注意預(yù)防執(zhí)行死鎖。

由表1可知,異構(gòu)處理器的計(jì)算能力影響任務(wù)的執(zhí)行時(shí)間,本文采用文獻(xiàn)[15]的計(jì)算方法來(lái)表示處理器的計(jì)算能力。在異構(gòu)信號(hào)處理平臺(tái)中,單個(gè)處理器的計(jì)算能力(Computing Power,CP)是一個(gè)綜合量,主要包括I/O、內(nèi)存讀寫(xiě)、處理器、網(wǎng)絡(luò)通信開(kāi)銷(xiāo)。因此,單個(gè)處理器的計(jì)算能力可以定義為:

(2)

局部非均衡聚簇算法描述如下:

算法3局部非均衡聚簇算法

輸入經(jīng)過(guò)順序融合后的DAGG:(V,E),initPartition Map(G)

輸出經(jīng)過(guò)非均衡聚簇后的DAGG:(V,E)

ProcessNum = Count(P);//實(shí)際處理器個(gè)數(shù)

PriorityQueue_CP = ConstructpriorityQueue(CP);

//構(gòu)造以處理器計(jì)算能力為權(quán)值的優(yōu)先隊(duì)列

PriorityQueue_Workload=ConstructpriorityQueue(G);

//構(gòu)造以任務(wù)負(fù)載為權(quán)值的優(yōu)先隊(duì)列

Match(PriorityQueue_CP,PriorityQueue_Workload);

//將處理器的計(jì)算能力與任務(wù)的負(fù)載進(jìn)行匹配

//計(jì)算理論上平均最佳執(zhí)行時(shí)間(即最佳同步周期)

TopologicalSort[]=ConstructClusterTopoLogicSort(G);

//構(gòu)造聚簇拓?fù)渑判?進(jìn)行劃分

Int curPartitionNo = 0;//當(dāng)前的劃分編號(hào)

While(SearchClusterTopoLogicSort(G)){

//依次遍歷DAG中分簇節(jié)點(diǎn)

CurPartitionWorkload=Weight(Vertex)+

Weight(curPatitionNo);

If(Weight(curPartitionWorkload)< averageRunTime×matched(CP)){

//根據(jù)任務(wù)負(fù)載量匹配相應(yīng)的處理器

initPartitionMap.insert(curPartitionNo,Vertex);

//當(dāng)前負(fù)載不足,添加節(jié)點(diǎn)

}//END IF

else

++curPartitionNo;

G.update(newVertex);//更新DAG

}//END WHLIE

局部非均衡劃分算法首先計(jì)算所有節(jié)點(diǎn)的負(fù)載以及系統(tǒng)中各個(gè)處理器的計(jì)算能力,構(gòu)造相對(duì)應(yīng)的優(yōu)先隊(duì)列。然后,將隊(duì)列中任務(wù)的負(fù)載與處理器計(jì)算能力進(jìn)行匹配,計(jì)算理論上平均最佳執(zhí)行時(shí)間(即最佳同步周期),對(duì)DAG進(jìn)行拓?fù)渑判?依次遍歷DAG中的節(jié)點(diǎn),確定各個(gè)簇的劃分編號(hào)。最后,根據(jù)子任務(wù)負(fù)載情況匹配相應(yīng)的處理器,對(duì)后驅(qū)節(jié)點(diǎn)依次進(jìn)行融合,如果融合后形成新節(jié)點(diǎn)的負(fù)載小于最佳時(shí)間乘以處理器計(jì)算能力的值,那么添加節(jié)點(diǎn),反復(fù)迭代上述過(guò)程直到確定劃分的編號(hào)。經(jīng)過(guò)非均衡劃分后的DAG見(jiàn)圖4(c)。

2.2 同步流水線(xiàn)調(diào)度

異構(gòu)信號(hào)處理平臺(tái)采用同步流水線(xiàn)調(diào)度作為調(diào)度模型。同步流水線(xiàn)調(diào)度根據(jù)應(yīng)用組件的依賴(lài)關(guān)系,將一個(gè)應(yīng)用分割成若干個(gè)流水線(xiàn)階段,同一階段內(nèi)的組件是相互獨(dú)立的,同時(shí)采用全局同步時(shí)鐘保證流水線(xiàn)各個(gè)執(zhí)行階段具有相同的時(shí)間片。在任一時(shí)間片內(nèi),組件最多只能執(zhí)行一次處理任務(wù),同時(shí)將數(shù)據(jù)傳輸?shù)胶篁?qū)組件,后驅(qū)組件要等待下一個(gè)時(shí)間片,才能處理前驅(qū)組件的輸出數(shù)據(jù)。因此,同步流水線(xiàn)調(diào)度利用時(shí)間片消除了組件間前后依賴(lài)關(guān)系,實(shí)現(xiàn)了組件的并行執(zhí)行。

同步流水線(xiàn)調(diào)度的性能取決于執(zhí)行時(shí)間最長(zhǎng)的組件,因此，任務(wù)劃分的負(fù)載均衡至關(guān)重要。圖5所示為軟件無(wú)線(xiàn)電應(yīng)用分配到2個(gè)處理器的同步流水線(xiàn)調(diào)度,其中,應(yīng)用包含4個(gè)組件V={V1,V2,V3,V4},V1和V2分配到處理器P1,V3和V4分配到處理器P2。圖5的調(diào)度流程存在透明的組件,表示組件尚未激活,其中，組件V2和V3是組件V1的后驅(qū)節(jié)點(diǎn),是組件V4的前驅(qū)節(jié)點(diǎn),因此整個(gè)應(yīng)用被分割成3個(gè)不同的流水階段。當(dāng)應(yīng)用經(jīng)過(guò)3個(gè)時(shí)間片時(shí),流水線(xiàn)進(jìn)入滿(mǎn)狀態(tài),此時(shí)同步流水線(xiàn)能夠產(chǎn)生高吞吐量。

圖5 應(yīng)用分配到2個(gè)處理器時(shí)的流水線(xiàn)調(diào)度

2.3 調(diào)度策略分析

異構(gòu)信號(hào)處理平臺(tái)的實(shí)時(shí)任務(wù)調(diào)度策略主要包括多層次任務(wù)劃分和同步流水線(xiàn)調(diào)度。本文提出的基于DAG的多層次任務(wù)劃分算法借鑒多層圖劃分的思想并對(duì)其進(jìn)行改進(jìn),同時(shí)考慮任務(wù)之間的數(shù)據(jù)依賴(lài)關(guān)系、節(jié)點(diǎn)的異構(gòu)性以及處理器間的通信速率。預(yù)處理階段的目的是對(duì)DAG進(jìn)行分層排序,使同層上的任務(wù)可以進(jìn)行并行處理。初始劃分階段的順序融合聚簇算法,采用貪心算法計(jì)算融合收益,減小通信開(kāi)銷(xiāo)。非均衡劃分階段考慮到節(jié)點(diǎn)的計(jì)算能力不同,采用廣度優(yōu)先搜索算法進(jìn)行任務(wù)匹配,保證粒度劃分與節(jié)點(diǎn)計(jì)算能力成正比例改變,確定劃分后的簇與處理器之間的映射,實(shí)現(xiàn)了任務(wù)的負(fù)載均衡和低通信同步開(kāi)銷(xiāo)。最后采用同步流水線(xiàn)調(diào)度方法,實(shí)現(xiàn)節(jié)點(diǎn)的并行執(zhí)行,達(dá)到了數(shù)據(jù)低延遲實(shí)時(shí)處理的目的。

3 實(shí)驗(yàn)與性能分析

本文采用異構(gòu)信號(hào)處理平臺(tái)來(lái)測(cè)試多層次劃分算法以及同步流水線(xiàn)調(diào)度的性能。異構(gòu)信號(hào)平臺(tái)由通用PC平臺(tái)和高性能ATCA平臺(tái)組成,2個(gè)平臺(tái)通過(guò)網(wǎng)線(xiàn)互連形成局域網(wǎng),其中,PC是域管理器客戶(hù)端,用于組件的開(kāi)發(fā)和應(yīng)用的搭建;ATCA是運(yùn)行平臺(tái),主要實(shí)現(xiàn)應(yīng)用的軟件功能,對(duì)應(yīng)用進(jìn)行實(shí)際處理。在恒為公司ATCA平臺(tái)內(nèi),插有計(jì)算刀片、承載板以及AMC-FPGA 3種板卡,計(jì)算刀片內(nèi)存在GPP處理器,運(yùn)行Windows Server 2008操作系統(tǒng),AMC-FPGA板卡內(nèi)存在DSP處理器,移植μC/OS II操作系統(tǒng),以及一塊Kintex-7 FPGA處理器。平臺(tái)內(nèi)計(jì)算刀片板卡和承載板內(nèi)通信協(xié)議為萬(wàn)兆網(wǎng),板卡間通信協(xié)議也為萬(wàn)兆網(wǎng),AMC-FPGA板卡內(nèi)處理器FPGA與DSP之間通過(guò)RAPID I/O總線(xiàn)相連,其性能參數(shù)配置如表2所示。

表2 異構(gòu)信號(hào)平臺(tái)處理器參數(shù)配置

本文選取FFT、短波FSK、QPSK和MIMO雷達(dá)信號(hào)處理4個(gè)典型應(yīng)用作為測(cè)試程序,4個(gè)測(cè)試程序的DAG的節(jié)點(diǎn)數(shù)和拓?fù)浣Y(jié)構(gòu)復(fù)雜度依次增加。其中,FFT應(yīng)用的DAG包含3個(gè)節(jié)點(diǎn),FSK包含5個(gè)節(jié)點(diǎn),QPSK包含8個(gè)節(jié)點(diǎn),MIMO包含10個(gè)節(jié)點(diǎn)。針對(duì)平臺(tái)目前采用的事件觸發(fā)數(shù)據(jù)流調(diào)度算法與多層同步流水線(xiàn)調(diào)度算法進(jìn)行對(duì)比實(shí)驗(yàn),其中,事件觸發(fā)調(diào)度算法按照應(yīng)用原始DAG進(jìn)行調(diào)度,不再進(jìn)行任務(wù)劃分。多層次流水線(xiàn)調(diào)度與事件觸發(fā)調(diào)度算法的性能對(duì)比如圖6所示。

圖6 多層次流水線(xiàn)調(diào)度與事件觸發(fā)調(diào)度算法對(duì)比

圖6(a)為測(cè)試程序的DAG經(jīng)過(guò)多層次劃分結(jié)果的示意圖,可以看出,測(cè)試程序FSK、QPSK和MIMO經(jīng)過(guò)多層次劃分DAG節(jié)點(diǎn)數(shù)明顯減少,但對(duì)于FFT應(yīng)用,劃分結(jié)果并不理想,原因是FFT應(yīng)用的組件較少,DAG拓?fù)浣Y(jié)構(gòu)過(guò)于簡(jiǎn)單。實(shí)驗(yàn)測(cè)試選擇的性能指標(biāo)為應(yīng)用完成執(zhí)行的時(shí)間,圖6(b)為測(cè)試程序在2種調(diào)度算法下執(zhí)行性能的比較,可以看出,測(cè)試程序隨著DAG節(jié)點(diǎn)數(shù)以及拓?fù)浣Y(jié)構(gòu)復(fù)雜度的增加,多層次流水線(xiàn)調(diào)度算法執(zhí)行時(shí)間呈遞減趨勢(shì),執(zhí)行時(shí)間越小,說(shuō)明改進(jìn)效果越好。但FFT應(yīng)用在2種算法下執(zhí)行時(shí)間基本相同,多層次同步流水線(xiàn)調(diào)度并沒(méi)有取得很好的性能收益,原因是FFT應(yīng)用的節(jié)點(diǎn)數(shù)太少且拓?fù)浣Y(jié)構(gòu)過(guò)于簡(jiǎn)單,但隨著任務(wù)DAG節(jié)點(diǎn)數(shù)的增多,拓?fù)浣Y(jié)構(gòu)復(fù)雜度增加,多層次流水線(xiàn)調(diào)度的優(yōu)勢(shì)也越明顯。因?yàn)槭录|發(fā)調(diào)度算法在依賴(lài)節(jié)點(diǎn)數(shù)過(guò)多且約束關(guān)系復(fù)雜的情況下,其節(jié)點(diǎn)在運(yùn)行時(shí)會(huì)頻繁喚醒,所以帶來(lái)的開(kāi)銷(xiāo)過(guò)大。MIMO雷達(dá)信號(hào)處理應(yīng)用節(jié)點(diǎn)數(shù)最多、拓?fù)浣Y(jié)構(gòu)最復(fù)雜,相對(duì)于事件觸發(fā)調(diào)度算法,多層次同步流水線(xiàn)調(diào)度算法的運(yùn)行時(shí)間能夠縮短25%左右。

4 結(jié)束語(yǔ)

本文基于異構(gòu)信號(hào)處理平臺(tái)提出利用DAG的任務(wù)模型,設(shè)計(jì)實(shí)現(xiàn)多層次任務(wù)劃分算法,保證任務(wù)節(jié)點(diǎn)間的異構(gòu)負(fù)載均衡,減少同步開(kāi)銷(xiāo)。同時(shí),在多層次任務(wù)劃分的基礎(chǔ)上設(shè)計(jì)同步流水線(xiàn)調(diào)度策略,實(shí)現(xiàn)節(jié)點(diǎn)的并行執(zhí)行。實(shí)驗(yàn)結(jié)果表明,該算法適合異構(gòu)信號(hào)處理平臺(tái)中實(shí)時(shí)任務(wù)的調(diào)度。但是本文多層次任務(wù)劃分算法還存在不足,在保證任務(wù)劃分均衡的情況下降低節(jié)點(diǎn)通信開(kāi)銷(xiāo),是下一步研究的方向。