楊平平,岳春生,胡澤明

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

0 概述

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

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

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

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

1 系統(tǒng)描述

1.1 異構(gòu)信號處理平臺

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

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

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

1.2 異構(gòu)信號處理平臺任務(wù)模型

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

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

表1 異構(gòu)信號處理平臺任務(wù)執(zhí)行時間

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

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

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

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

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

DAG分層算法描述如下:

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

輸入原始DAGG(V,E)

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

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

Int gInDegree[MAX_NODE];

FindInDegree();//對各頂點(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]--;

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

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

2.1.2 順序融合聚簇算法

順序融合聚簇是對分層處理后的DAG進(jìn)行初始劃分,將相鄰的節(jié)點(diǎn)進(jìn)行融合。任務(wù)劃分粒度越小,子任務(wù)數(shù)越多,并行程度越高,但通信開銷就越大;相反,任務(wù)劃分粒度越大,通信開銷越少,但并行度就越小。順序融合聚簇方法是消除通信延遲劃分算法中的一種,其將相鄰節(jié)點(diǎn)融合可以降低通信開銷的收益,但有可能會喪失后驅(qū)節(jié)點(diǎn)的并行性。因此,順序融合聚簇時要盡量使任務(wù)之間的通信開銷減小,又同時保持任務(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的計算量(即負(fù)載)和組件vj的計算量。

順序融合算法描述如下:

算法2順序融合算法

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

輸出經(jīng)過順序融合后的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)先隊列

While(VertexNum > ClusterNum){

MaxGain = GetMaxGain(priorityQueue);

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

If(maxGain<=0)break;

PairmaxGainCluster=

GetMaxGainCluster(priorityQueue,G);

ClusterWeight =Weight(cluster);

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

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

PriorityQueue.delete(maxGainCluster);

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

newVertexr = Fused(Vi,Vj);

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

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

PriorityQueue.update(maxGainCluster,

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

-- VertexNum;

}//END WHILE

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

圖4 DAG多層次劃分示例

2.1.3 局部非均衡劃分算法

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

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

(2)

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

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

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

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

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

PriorityQueue_CP = ConstructpriorityQueue(CP);

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

PriorityQueue_Workload=ConstructpriorityQueue(G);

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

Match(PriorityQueue_CP,PriorityQueue_Workload);

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

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

TopologicalSort[]=ConstructClusterTopoLogicSort(G);

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

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

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

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

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

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

同步流水線調(diào)度的性能取決于執(zhí)行時間最長的組件,因此，任務(wù)劃分的負(fù)載均衡至關(guān)重要。圖5所示為軟件無線電應(yīng)用分配到2個處理器的同步流水線調(diào)度,其中,應(yīng)用包含4個組件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),因此整個應(yīng)用被分割成3個不同的流水階段。當(dāng)應(yīng)用經(jīng)過3個時間片時,流水線進(jìn)入滿狀態(tài),此時同步流水線能夠產(chǎn)生高吞吐量。

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

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

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

3 實驗與性能分析

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

表2 異構(gòu)信號平臺處理器參數(shù)配置

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

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

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

4 結(jié)束語

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