楊平平,岳春生,胡澤明

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

0 概述

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

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

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

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

1 系統(tǒng)描述

1.1 異構信號處理平臺

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

圖1 層次化新型信號處理平臺軟件體系架構

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

1.2 異構信號處理平臺任務模型

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

圖2 應用的DAG示意圖

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

2 異構信號處理平臺實時任務調度策略

2.1 基于DAG的多層次任務劃分方法

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

2.1.1 DAG的分層拓撲排序

分層拓撲排序是對DAG進行預處理。由圖論可知,有向無環(huán)圖節(jié)點存在入度值,入度值指的是鄰接到某頂點弧的數目。預處理是根據節(jié)點的入度值,將有向無環(huán)圖分成多層,每層的組件沒有數據依賴關系的節(jié)點,可以進行并行處理。

DAG分層算法描述如下:

算法1任務分層算法

輸入原始DAGG(V,E)

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

Void TopologicalSort (int Num); {//節(jié)點數目

Int gInDegree[MAX_NODE];

FindInDegree();//對各頂點求入度值

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

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

if (! gInDegree[i] )

push (S,i);

//入度為0者進棧,k層

While(! StackEmpty(S)){

pop(S,i);

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

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

int v = gEdges[e].to;

gInDegree[v]--;

//對i頂點的每個鄰節(jié)點的入度值減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; //存在回路

}//輸出分層結果

圖3所示為DAG分層拓撲排序處理的示例,其中,圖3(a)為一個異構信號處理平臺應用的DAG映射到處理器的示例，Vi表示組件,權值為組件在處理器上的執(zhí)行時間,圖3(b)描述了經過任務分層后的DAG。首先計算圖3(a)中各個頂點的入度值,將所有入度值為0的節(jié)點放在第k層,然后將上一層頂點的所有邊消除,再計算新圖入度值為0的頂點,放入第k+1層,直到DAG中不存在入度值為0的節(jié)點。分層拓撲排序可以檢測DAG中是否出現(xiàn)環(huán)路,防止執(zhí)行時出現(xiàn)死鎖。

圖3 DAG分層拓撲排序示例

2.1.2 順序融合聚簇算法

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

(1)

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

順序融合算法描述如下:

算法2順序融合算法

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

輸出經過順序融合后的DAGG:(V,E)

Graph G =ConstructGraph(DAG);

VertexNum = Count(G);//當前節(jié)點數

averageWorkload = Weight(DAG)/ClusterNum;

// 理論上平均最佳負載

priorityQueue = ConstructpriorityQueue(G);

//收益為權值的優(yōu)先隊列

While(VertexNum > ClusterNum){

MaxGain = GetMaxGain(priorityQueue);

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

If(maxGain<=0)break;

PairmaxGainCluster=

GetMaxGainCluster(priorityQueue,G);

ClusterWeight =Weight(cluster);

//計算當前cluster的負載

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

PriorityQueue.delete(maxGainCluster);

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

newVertexr = Fused(Vi,Vj);

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

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

PriorityQueue.update(maxGainCluster,

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

-- VertexNum;

}//END WHILE

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

圖4 DAG多層次劃分示例

2.1.3 局部非均衡劃分算法

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

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

(2)

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

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

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

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

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

PriorityQueue_CP = ConstructpriorityQueue(CP);

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

PriorityQueue_Workload=ConstructpriorityQueue(G);

//構造以任務負載為權值的優(yōu)先隊列

Match(PriorityQueue_CP,PriorityQueue_Workload);

//將處理器的計算能力與任務的負載進行匹配

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

TopologicalSort[]=ConstructClusterTopoLogicSort(G);

//構造聚簇拓撲排序,進行劃分

Int curPartitionNo = 0;//當前的劃分編號

While(SearchClusterTopoLogicSort(G)){

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

CurPartitionWorkload=Weight(Vertex)+

Weight(curPatitionNo);

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

//根據任務負載量匹配相應的處理器

initPartitionMap.insert(curPartitionNo,Vertex);

//當前負載不足,添加節(jié)點

}//END IF

else

++curPartitionNo;

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

}//END WHLIE

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

2.2 同步流水線調度

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

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

圖5 應用分配到2個處理器時的流水線調度

2.3 調度策略分析

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

3 實驗與性能分析

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

表2 異構信號平臺處理器參數配置

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

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

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

4 結束語

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