基于圖分割的流應(yīng)用多處理器映射算法

唐麒，吳尚峰，施峻武，魏急波

?

基于圖分割的流應(yīng)用多處理器映射算法

唐麒，吳尚峰，施峻武，魏急波

（國(guó)防科技大學(xué)電子科學(xué)與工程學(xué)院，湖南長(zhǎng)沙 410073）

為了充分利用多處理器平臺(tái)所提供的計(jì)算資源，需要將應(yīng)用以適當(dāng)?shù)姆绞接成涞讲煌幚砥?，從而最大程度地挖掘?yīng)用所提供的并發(fā)性以滿足應(yīng)用嚴(yán)格的實(shí)時(shí)性要求。提出了并發(fā)圖來(lái)量化、建模應(yīng)用任務(wù)間的并發(fā)性，提出了一種基于自同步調(diào)度的并發(fā)圖構(gòu)建算法，并將任務(wù)映射問(wèn)題轉(zhuǎn)換成圖分割問(wèn)題，然后將并發(fā)圖分割問(wèn)題建模為純0-1整數(shù)線性規(guī)劃模型并采用ILP求解器獲得最優(yōu)解。采用了大量隨機(jī)生成的同步數(shù)據(jù)流圖以及一組實(shí)際應(yīng)用對(duì)所提方法進(jìn)行性能評(píng)估，實(shí)驗(yàn)結(jié)果表明所提方法性能優(yōu)于已有算法。

同步數(shù)據(jù)流圖；映射；多處理器；圖分割

1 引言

同步數(shù)據(jù)流圖（SDFG，synchronous dataflow graph）廣泛用于建?，F(xiàn)代流應(yīng)用，包括視頻、音頻編解碼、軟件無(wú)線電等。為了滿足消費(fèi)者對(duì)應(yīng)用的質(zhì)量要求，這些應(yīng)用的計(jì)算復(fù)雜度日益增加，給硬件設(shè)計(jì)帶來(lái)了巨大挑戰(zhàn)。許多應(yīng)用有嚴(yán)格的實(shí)時(shí)性要求，例如，系統(tǒng)輸入與輸出間的延時(shí)或系統(tǒng)吞吐量要滿足特定指標(biāo)。為了滿足這些要求，一種直接的方法是增加處理器時(shí)鐘頻率，然而，隨著時(shí)鐘頻率的提升，系統(tǒng)能耗急劇增加，降低了這一方法的實(shí)用性。另外，時(shí)鐘頻率正逐漸接近物理極限，依靠這一方法增加計(jì)算能力難以為繼。多處理器平臺(tái)提供了另一種方案，可以在計(jì)算能力與功耗間達(dá)到更好的平衡，因此，在嵌入式系統(tǒng)設(shè)計(jì)中得到了大量應(yīng)用。盡管多處理器可以提供很高的計(jì)算能力，這并不意味著部署在其上的應(yīng)用可以完全挖掘這些處理能力。實(shí)際上，如果應(yīng)用只提供了極少量的并發(fā)性，那么采用多處理器幾乎不能提高系統(tǒng)性能。正如Amdahl定理所表明的那樣，使用多處理器帶來(lái)的性能增益嚴(yán)重受限于應(yīng)用并發(fā)性。盡管很多應(yīng)用，如由SDFG建模的流應(yīng)用，可以并行執(zhí)行，如何在多處理器上利用應(yīng)用的內(nèi)在并發(fā)性仍然是個(gè)有待解決的問(wèn)題，這就是所謂的并行調(diào)度問(wèn)題。

應(yīng)用調(diào)度包括任務(wù)映射、排序和定時(shí)[2]。任務(wù)映射是將任務(wù)分配到不同處理器上的過(guò)程。對(duì)于最優(yōu)調(diào)度，無(wú)論最優(yōu)性的評(píng)價(jià)標(biāo)準(zhǔn)是什么，總存在對(duì)應(yīng)的最優(yōu)映射，因此研究如何獲得最優(yōu)映射具有重要價(jià)值。對(duì)于映射問(wèn)題，研究者提出了很多針對(duì)不同應(yīng)用模型和平臺(tái)的算法。其中，圖分割法[3]和負(fù)載均衡法[4,5]得到了大量研究。然而，這2類(lèi)算法要么在最小化處理器間通信的前提下最大化負(fù)載均衡水平，要么單純地均衡不同處理器上的負(fù)載，而沒(méi)有綜合考慮應(yīng)用的內(nèi)在結(jié)構(gòu)，因此降低了性能。另一類(lèi)方法是鏈?zhǔn)秸{(diào)度算法[6,7]，這類(lèi)算法將任務(wù)調(diào)度分成優(yōu)先級(jí)分配和調(diào)度2個(gè)步驟，然而，這類(lèi)算法主要用于優(yōu)化系統(tǒng)延時(shí)，雖然可以通過(guò)修正應(yīng)用于吞吐量?jī)?yōu)化，但性能并不是很好。

本文研究SDFG在多處理器上的映射問(wèn)題，以獲得可以最大化應(yīng)用并發(fā)性的最優(yōu)任務(wù)映射，從而使應(yīng)用長(zhǎng)期吞吐量最大化。本文提出了并發(fā)圖（PG，parallelism graph）來(lái)量化和建模SDFG中不同任務(wù)間的并發(fā)性，提出了一種基于自同步調(diào)度的并發(fā)圖構(gòu)建算法，并將映射問(wèn)題轉(zhuǎn)換化成圖分割問(wèn)題，然后將圖分割問(wèn)題建模為純0-1整數(shù)線性規(guī)劃模型（ILP，integer linear programming），并使用ILP求解器獲取最優(yōu)解。

本文所提算法在SDF3[8]中實(shí)現(xiàn)，并采用隨機(jī)生成的SDFG和一組實(shí)際應(yīng)用進(jìn)行性能評(píng)估。算法的有效性通過(guò)與已有負(fù)載均衡算法[4,5]和HEFT算法[6]比較得以驗(yàn)證。

2 相關(guān)工作

圖分割[3]被證明可以用于并行計(jì)算。圖分割的主要目標(biāo)是將計(jì)算均勻地分配到多個(gè)處理器，同時(shí)最小化處理器間通信[9]。然而，算法中沒(méi)有考慮任務(wù)間的依賴(lài)關(guān)系。與此不同，本文提出并發(fā)圖的概念，利用任務(wù)間的依賴(lài)關(guān)系，建模任務(wù)間并行執(zhí)行關(guān)系，從而將問(wèn)題轉(zhuǎn)換成圖分割問(wèn)題。文獻(xiàn)[4,5]將負(fù)載均衡思想應(yīng)用于SDFG映射問(wèn)題，所提算法考慮了計(jì)算、通信帶寬及內(nèi)存消耗的均衡，任務(wù)綁定按照優(yōu)先級(jí)非遞增的順序進(jìn)行，任務(wù)優(yōu)先級(jí)采用估計(jì)最大均值（MCM，maximum cycle mean）[4]來(lái)計(jì)算。然而，算法沒(méi)有充分利用任務(wù)間的依賴(lài)關(guān)系，不能最大化應(yīng)用并發(fā)性，降低了算法性能。

文獻(xiàn)[6,7]研究了如何利用應(yīng)用結(jié)構(gòu)特征，包括任務(wù)間依賴(lài)關(guān)系、任務(wù)執(zhí)行時(shí)間及數(shù)據(jù)傳輸需求來(lái)提高調(diào)度性能。然而，這些方法針對(duì)由有向無(wú)環(huán)圖（DAG，directed acyclic graph）建模的應(yīng)用，不能直接應(yīng)用于SDFG。與DAG不同，SDFG可以支持任務(wù)間環(huán)狀依賴(lài)關(guān)系和多速率依賴(lài)，因此，任務(wù)間關(guān)系更為復(fù)雜。這種關(guān)系不能簡(jiǎn)單地由模型中的路徑特征，比如路徑長(zhǎng)度來(lái)描述。一種可行的方法是將SDFG轉(zhuǎn)換成同構(gòu)SDFG，并進(jìn)一步將同構(gòu)SDFG轉(zhuǎn)換為無(wú)環(huán)依賴(lài)圖[2]。由于無(wú)環(huán)依賴(lài)圖屬于DAG，因此上面提到的調(diào)度算法可以直接使用。然而，這種方法主要用于允許任務(wù)復(fù)制的系統(tǒng)，為了適應(yīng)無(wú)任務(wù)復(fù)制的系統(tǒng)，可以在調(diào)度時(shí)強(qiáng)制將同一任務(wù)的實(shí)例分配到同一處理器。

3 應(yīng)用模型

本文采用SDFG來(lái)建模流應(yīng)用，如軟件無(wú)線電、通信協(xié)議、多媒體應(yīng)用等。本文所采用SDFG模型的定義如下。

SDFG在執(zhí)行過(guò)程中，任務(wù)將以不同頻率執(zhí)行，因此在一次調(diào)度中會(huì)出現(xiàn)不同次數(shù)。SDFG迭代及重復(fù)向量可以用于來(lái)描述SDFG的這一特征。

定義2 （SDFG迭代）SDFG迭代是執(zhí)行每個(gè)任務(wù)最小正整數(shù)次數(shù)同時(shí)使各邊符號(hào)數(shù)目恢復(fù)初始值的過(guò)程。

SDFG的重復(fù)向量可以通過(guò)解平衡方程而得[1]。當(dāng)平衡方程有非零解[1]時(shí)，重復(fù)向量存在，且這樣的 SDFG 總可以轉(zhuǎn)換成等價(jià)的 HSDFG[2]。

本文只考慮強(qiáng)連通SDFG，其中每個(gè)任務(wù)都與其他任意任務(wù)直接或間接相連。對(duì)實(shí)際應(yīng)用，這是一個(gè)合理的假定，因?yàn)閷?shí)際系統(tǒng)內(nèi)存消耗是受限的，因此SDFG中任意邊的最大符號(hào)數(shù)目是有限的。通過(guò)為SDFG中的每條邊增加額外的最大符號(hào)數(shù)目約束邊，可以將非強(qiáng)連通SDFG轉(zhuǎn)換成強(qiáng)連通圖。

圖1所示為一個(gè)由5個(gè)任務(wù)組成的SDFG示例。圖中各邊末端數(shù)字為邊的產(chǎn)出或消費(fèi)速率，為簡(jiǎn)單起見(jiàn)，只有當(dāng)速率大于1時(shí)才予以標(biāo)注。邊附近的文字為邊的標(biāo)簽，標(biāo)簽后面括號(hào)中的數(shù)字表示邊上的初始符號(hào)數(shù)，如果初始符號(hào)數(shù)為0，則予以忽略。圖中SDFG的重復(fù)向量為，表示在一次應(yīng)用迭代中，任務(wù)、、、和分別需要執(zhí)行2、2、3、1和次。

4 問(wèn)題闡述

吞吐量是流應(yīng)用最為重要的性能度量標(biāo)準(zhǔn)之一。本文研究如何將流應(yīng)用映射到多處理器從而最大化應(yīng)用的長(zhǎng)期吞吐量。根據(jù)是否允許任務(wù)復(fù)制，映射問(wèn)題可以分成基于復(fù)制的映射和無(wú)復(fù)制的映射。本文考慮不允許任務(wù)復(fù)制的應(yīng)用映射問(wèn)題，這意味著每個(gè)任務(wù)只能分配到一個(gè)處理器上執(zhí)行。在本文所考慮的問(wèn)題中，應(yīng)用采用SDFG建模。在SDFG中，應(yīng)用任務(wù)的并發(fā)執(zhí)行能力并未明顯建模。盡管應(yīng)用的最大吞吐量可以通過(guò)自同步調(diào)度[2]獲得，這一調(diào)度并未將資源約束，例如處理器數(shù)目納入考慮之中。實(shí)際多處理器平臺(tái)中處理器數(shù)目通常少于SDFG中最大可并發(fā)執(zhí)行的任務(wù)數(shù)目，因此，如何在映射中盡可能地挖掘SDFG任務(wù)間并發(fā)性以提高系統(tǒng)吞吐量是一個(gè)極為重要的問(wèn)題。

對(duì)于SDFG，盡管可以從圖模型結(jié)構(gòu)推導(dǎo)阻止任務(wù)并發(fā)執(zhí)行的優(yōu)先約束關(guān)系，任務(wù)間并發(fā)性并未明顯地建模出來(lái)，例如，2個(gè)任務(wù)在多大程度上可以并行執(zhí)行并未在應(yīng)用圖中得到描述。除此之外，也不能直接將任務(wù)間優(yōu)先關(guān)系與任務(wù)間并行度關(guān)聯(lián)起來(lái)，使在映射中挖掘任務(wù)并發(fā)性變得極為困難。盡管如此，如果可以量化任務(wù)間并發(fā)程度，則映射問(wèn)題可以次優(yōu)地轉(zhuǎn)換成最大化任務(wù)間并發(fā)性的問(wèn)題。基于以上觀察，本文從提取、量化SDFG任務(wù)間并發(fā)性著手，并使用圖分割法解決應(yīng)用映射問(wèn)題。

5 周期靜態(tài)調(diào)度與吞吐量分析

由于最終目標(biāo)是獲得吞吐量最優(yōu)的映射，分析映射的吞吐量顯得極為重要。本文假定系統(tǒng)根據(jù)靜態(tài)周期調(diào)度循環(huán)執(zhí)行，靜態(tài)周期調(diào)度強(qiáng)制任務(wù)按照指定順序依次執(zhí)行。不同迭代可以在時(shí)間上重疊，采用流水線的方式執(zhí)行。本文采用最早開(kāi)始時(shí)間調(diào)度算法為每個(gè)處理器構(gòu)建周期靜態(tài)順序調(diào)度。當(dāng)同一時(shí)刻有多個(gè)任務(wù)可以同時(shí)執(zhí)行時(shí)，任意一個(gè)任務(wù)被選擇優(yōu)先執(zhí)行。為每個(gè)處理器構(gòu)建好周期靜態(tài)調(diào)度后，應(yīng)用吞吐量可以通過(guò)已有方法來(lái)計(jì)算。

文獻(xiàn)[12]提出了一種無(wú)資源約束下的基于狀態(tài)空間搜索的SDFG吞吐量分析方法。這一方法采用SDFG邊上符號(hào)分布及任務(wù)執(zhí)行狀態(tài)來(lái)表征應(yīng)用狀態(tài)。由于所考慮SDFG是強(qiáng)連通的，并且狀態(tài)中各元素值的范圍是有限的，因此，狀態(tài)空間也是有限的。經(jīng)過(guò)有限次數(shù)的狀態(tài)轉(zhuǎn)移后，將重新遇到已經(jīng)經(jīng)歷過(guò)的狀態(tài)，從而形成狀態(tài)環(huán)。獲得狀態(tài)空間中的狀態(tài)環(huán)后，吞吐量可以直接計(jì)算出來(lái)。另一種計(jì)算吞吐量的方法是用max-plus代數(shù)[10]建模應(yīng)用的自同步執(zhí)行，max-plus矩陣的特征值的倒數(shù)即等于應(yīng)用吞吐量。上述吞吐量計(jì)算方法沒(méi)有考慮映射和調(diào)度，只適應(yīng)于無(wú)資源約束的場(chǎng)景。文獻(xiàn)[11,13]提出了將周期靜態(tài)順序調(diào)度建模到HSDFG/SDFG中的方法，通過(guò)對(duì)SDFG進(jìn)行調(diào)度擴(kuò)展，可以用文獻(xiàn)[10,12]中的吞吐量分析方法進(jìn)行精確的吞吐量分析。本文使用文獻(xiàn)[11,12]中的方法進(jìn)行調(diào)度性能分析。

6 并發(fā)圖及其構(gòu)建

本節(jié)介紹并發(fā)圖的概念及其構(gòu)建方法。并發(fā)圖用于量化和建模SDFG任務(wù)間的并發(fā)性，其定義如下。

本文通過(guò)SDFG的ASAP（as-soon-as-possible）調(diào)度（自同步調(diào)度[2]）的周期擴(kuò)展來(lái)計(jì)算任務(wù)間并發(fā)度。在ASAP調(diào)度中，當(dāng)任務(wù)所依賴(lài)數(shù)據(jù)就序時(shí)，任務(wù)即開(kāi)始執(zhí)行。ASAP調(diào)度定義如下。

ASAP調(diào)度由瞬態(tài)和緊隨其后的周期態(tài)組成，其定義如下。

應(yīng)用吞吐量由ASAP調(diào)度的周期態(tài)決定，因此使用它來(lái)計(jì)算任務(wù)間并發(fā)度。盡管周期態(tài)中一個(gè)周期可能包含多次應(yīng)用迭代，如周期態(tài)定義中的所指明的那樣，無(wú)論最后計(jì)算出的任務(wù)間并發(fā)度是否除以這一數(shù)值，并不會(huì)影響最后結(jié)果。由于周期態(tài)具有周期特征，因此并不需要構(gòu)建完整的ASAP調(diào)度，可以在獲得一個(gè)完整的執(zhí)行周期后停止執(zhí)行。本文從周期態(tài)中提取一個(gè)執(zhí)行周期，對(duì)其進(jìn)行周期擴(kuò)展，并根據(jù)這個(gè)周期擴(kuò)展中不同任務(wù)的并行執(zhí)行時(shí)間來(lái)量化任務(wù)間并發(fā)度。

圖1所示SDFG的ASAP調(diào)度如圖2所示，ASAP調(diào)度由瞬態(tài)和周期態(tài)組成。周期態(tài)從時(shí)刻18開(kāi)始；在時(shí)刻53，再次經(jīng)歷時(shí)刻18經(jīng)歷的狀態(tài)。因此時(shí)刻18和53之間的執(zhí)行形成一個(gè)周期，其中包含一次應(yīng)用迭代。

并發(fā)圖構(gòu)建算法詳細(xì)描述了構(gòu)建并發(fā)圖的步驟。對(duì)一個(gè)SDFG，首先為其增加自邊以約束任務(wù)自動(dòng)并發(fā)，也即同一時(shí)間一個(gè)任務(wù)最多只能有一個(gè)實(shí)例處于運(yùn)行狀態(tài)。然后，初始化并發(fā)圖，為其添加節(jié)點(diǎn)。并發(fā)圖中的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)SDFG中的一個(gè)任務(wù)。其次，反復(fù)調(diào)用方程(1)構(gòu)建SDFG的ASAP調(diào)度。在此過(guò)程中，提取ASAP調(diào)度的一個(gè)執(zhí)行周期，并對(duì)其進(jìn)行周期擴(kuò)展。根據(jù)得到的周期擴(kuò)展，計(jì)算PG中任意2個(gè)節(jié)點(diǎn)間的邊權(quán)，邊權(quán)等于對(duì)應(yīng)任務(wù)在周期擴(kuò)展中的重疊時(shí)間。

并發(fā)圖構(gòu)建算法

11) end for

15) end if

16) end for

STEM教育與STEM職業(yè)的聯(lián)系 教育的目的是為社會(huì)建設(shè)培養(yǎng)專(zhuān)業(yè)人才，對(duì)接社會(huì)的現(xiàn)代化發(fā)展。STEM教育理工科屬性很強(qiáng)，從事社會(huì)建設(shè)的科技產(chǎn)業(yè)建設(shè)者需要具有此類(lèi)的設(shè)計(jì)性思維，對(duì)于社會(huì)的科技產(chǎn)業(yè)具有很強(qiáng)的帶動(dòng)作用。

17) end for

如算法中第6)~17)行所示，并發(fā)圖中2個(gè)節(jié)點(diǎn)間邊的邊權(quán)通過(guò)累加對(duì)應(yīng)任務(wù)實(shí)例的并行執(zhí)行時(shí)間而得。如果計(jì)算得到的邊權(quán)非零，則在并發(fā)圖中為相應(yīng)節(jié)點(diǎn)增加一條邊，邊權(quán)設(shè)置為上面計(jì)算得到的值。

圖3為示例SDFG的并發(fā)圖及其鄰接矩陣。如圖2所示，不同執(zhí)行周期在時(shí)間上不重疊，例如，第1個(gè)周期開(kāi)始于時(shí)刻18而結(jié)束于時(shí)刻53，第2個(gè)周期開(kāi)始于時(shí)刻53而結(jié)束于時(shí)刻87。因此，構(gòu)建并發(fā)圖時(shí)，并不需要進(jìn)行周期擴(kuò)展。在圖2所示ASAP調(diào)度的第一個(gè)周期中，任務(wù)實(shí)例（上標(biāo)表示實(shí)例索引）與重疊，重疊時(shí)間為5，因此，在并發(fā)圖中，任務(wù)和間有一條邊，邊權(quán)為5。類(lèi)似地，可以為并發(fā)圖添加其他邊。

在并發(fā)圖中，由于邊權(quán)均為正整數(shù)，因此每一條邊均表示該邊所連接任務(wù)在一定程度上可以并發(fā)執(zhí)行，邊權(quán)記錄了對(duì)應(yīng)任務(wù)可并發(fā)執(zhí)行的程度。如果在調(diào)度中有盡可能多的任務(wù)可以并發(fā)執(zhí)行，則應(yīng)用的一次迭代可以在更少的時(shí)間內(nèi)完成，因而提高應(yīng)用吞吐量。因此，以最大化吞吐量為目標(biāo)的映射問(wèn)題，在一定程度上可以等價(jià)于最大化映射的并發(fā)度。通過(guò)使用并發(fā)圖，任務(wù)間并發(fā)性得以量化，映射問(wèn)題可以等價(jià)于分割并發(fā)圖并使割最大化。割定義為所連接任務(wù)被分配到不同處理器的邊的邊權(quán)之和。采用上述方法，可以將映射問(wèn)題轉(zhuǎn)化成圖分割問(wèn)題。

7 純0-1整數(shù)線性規(guī)劃模型

(4)

(5)

(7)

(8)

由于每個(gè)任務(wù)只能映射到一個(gè)處理器，因此必須滿足如式(4)所示的任務(wù)映射約束。由于引入了輔助變量使如式(3)所示目標(biāo)函數(shù)線性化，需要引入約束式(4)~式(8)。這些約束方程的推導(dǎo)如下。

(10)

(11)

8 實(shí)驗(yàn)與結(jié)果

本節(jié)通過(guò)實(shí)驗(yàn)來(lái)評(píng)估所提算法的性能，并將本文所提算法與負(fù)載均衡算法[4]及HEFT算法[6]進(jìn)行了比較。

8.1 度量參數(shù)

吞吐量是流應(yīng)用系統(tǒng)的關(guān)鍵優(yōu)化目標(biāo)，如同文獻(xiàn)[4,5]一樣，本文采用吞吐量對(duì)算法性能進(jìn)行評(píng)估。吞吐量采用第5節(jié)所介紹的方法計(jì)算。同時(shí)，在實(shí)驗(yàn)中分析了不同映射算法所獲得映射方案的割值及算法時(shí)間開(kāi)銷(xiāo)。割值大小反映了映射所挖掘的并發(fā)度，定義為跨越不同子集的邊的邊權(quán)之和。

8.2 測(cè)試基準(zhǔn)

本文使用一組隨機(jī)生成的SDFG及一組實(shí)際應(yīng)用進(jìn)行性能測(cè)試，并使用開(kāi)源工具SDF3[8]來(lái)產(chǎn)生隨機(jī)SDFG，其中任務(wù)數(shù)為5到15。對(duì)每個(gè)圖尺寸，均生成個(gè)100個(gè)隨機(jī)SDFG。SDFG參數(shù)包括任務(wù)執(zhí)行時(shí)間和邊上的符號(hào)大小，均隨機(jī)生成。任務(wù)累積執(zhí)行時(shí)間在400和1 000間均勻產(chǎn)生。

8.3 實(shí)驗(yàn)結(jié)果

表1所示為隨機(jī)應(yīng)用在具有不同處理器數(shù)目的多處理器上的測(cè)試結(jié)果。表中第1列和第2列分別表示隨機(jī)SDFG的任務(wù)數(shù)目和平臺(tái)處理器數(shù)目。“吞吐量”、“割值”、“時(shí)間復(fù)雜度”列中所有數(shù)值均進(jìn)行了歸一化。從表中可以看出，對(duì)不同多處理器和有不同任務(wù)數(shù)的SDFG，本文所提算法從吞吐量的角度看要優(yōu)于其他2種算法，吞吐量平均增加17.40%和18.23%。這一性能增益表明最大化并發(fā)度的思想有助于提升映射的吞吐量。由于采用并發(fā)圖來(lái)表示應(yīng)用并發(fā)性，并采用圖分割方法最大化映射的割值，采用本文所提算法所獲得的映射在并發(fā)度的數(shù)值上要大于負(fù)載均衡算法和HEFT。如“割值”列中數(shù)據(jù)所示，在所有測(cè)試中，所提出的算法所生成的映射的割值比負(fù)載均衡算法大10%，比HEFT高21.95%。采用本文所提算法的時(shí)間復(fù)雜度高于其他2種算法。當(dāng)任務(wù)數(shù)目較小的，時(shí)間復(fù)雜度是負(fù)載均衡算法的數(shù)倍；而當(dāng)任務(wù)數(shù)較大時(shí)，復(fù)雜度急劇增加，這表明所提算法可較好地應(yīng)用于小規(guī)模問(wèn)題。

表1 隨機(jī)應(yīng)用性能對(duì)比

表2所示為實(shí)際應(yīng)用在多處理器上的測(cè)試結(jié)果。表中數(shù)據(jù)表明本文所提算法對(duì)實(shí)際應(yīng)用仍然有效，吞吐量要優(yōu)于負(fù)載均衡算法和HEFT。對(duì)調(diào)制解調(diào)器，使用所提算法與負(fù)載均衡算法和HEFT相比可以提高9.6%和18.6%的吞吐量。對(duì)其他應(yīng)用，也可取得一定的性能增益。與隨機(jī)應(yīng)用一樣，使用本文算法可以提高映射割值，再次驗(yàn)證了映射割值與吞吐量之間的正相關(guān)關(guān)系，表明采用割值來(lái)優(yōu)化映射問(wèn)題要優(yōu)于其他方法。在時(shí)間復(fù)雜度方面，除MP3解碼器1外，所提算法與負(fù)載均衡算法相當(dāng)，略高于HEFT，表明所提算法可較好地應(yīng)用于實(shí)際應(yīng)用。

表2 實(shí)際應(yīng)用性能對(duì)比

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

本文研究了SDFG在多處理器上的映射問(wèn)題，以最大化應(yīng)用吞吐量為目標(biāo)。提出了并發(fā)圖來(lái)量化、建模應(yīng)用并發(fā)性，提出了一種基于自同步調(diào)度的并發(fā)圖構(gòu)建算法，并將映射問(wèn)題轉(zhuǎn)換為圖分割問(wèn)題，最后將圖分割問(wèn)題建模為純0-1整數(shù)線性規(guī)劃問(wèn)題。本文采用了一組實(shí)際應(yīng)用和隨機(jī)產(chǎn)生的SDFG進(jìn)行了算法性能評(píng)估。實(shí)驗(yàn)結(jié)果表明本文所提算法的吞吐量性能要優(yōu)于負(fù)載均衡算法和HEFT算法，證明采用并發(fā)圖及圖分割的方法求解映射問(wèn)題優(yōu)于已有方法。

[1] LEE E A, MESSERSCHMITT D G. Static scheduling of synchronous data flow programs for digital signal processing[J]. IEEE Transactions on Computers, 1987, 100(1): 24-35.

[2] SRIRAM S, BHATTACHARYYA S S. Embedded multiprocessors: scheduling and synchronization[M]. CRC Press, 2012.

[3] AUBANEL E. Resource-aware load balancing of parallel applications[M]// Handbook of research on grid technologies and utility computing: concepts for managing large-scale applications. 2009: 12-21.

[4] STUIJK S, BASTEN T, GEILEN M, et al. Multiprocessor resource allocation for throughput-constrained synchronous dataflow graphs[C]// The 44th Annual Design Automation Conference. c2007: 777-782.

[5] AMBROSE J A, NAWINNE I, PARAMESWARAN S. Latency- constrained binding of dataflow graphs to energy conscious GALS- based MPSoCs[C]//IEEE International Symposium on Circuits and System. c2013: 1212-1215.

[6] TOPCUOGLU H, HARIRI S, WU M. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13 (3): 260-274.

[7] SINNEN O. Task scheduling for parallel systems[M]. John Wiley & Sons, 2007.

[8] STUIJK S, GEILEN M, BASTEN T. SDF3: SDF for free[C]// Conference on Application of Concurrency to System Design. c2006: 276-278.

[9] HENDRICKSON B, KOLDA T G. Graph partitioning models for parallel computing[J]. Parallel Computing, 2000, 26 (12): 1519-1534.

[10] GEILEN M. Synchronous dataflow scenarios[J]. ACM Transactions on Embedded Computing Systems, 2010, 10 (2): 16.

[11] DAMAVANDPEYMA M, STUIJK S, BASTEN T, et al. Schedule-extended synchronous dataflow graphs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2013, 32 (10): 1495-1508.

[12] GHAMARIAN A H, GEILEN M, STUIJK S, et al. Throughput analysis of synchronous data flow graphs[C]//Sixth International Conference on Application of Concurrency to System Design. c2006: 25-36.

[13] BAMBHA N, KIANZAD V, KHANDELIA M, et al. Intermediate representations for design automation of multiprocessor DSP systems[J]. Design Automation for Embedded Systems, 2002, 7 (4): 307-323.

[14] WINSTON W L, GOLDBERG J B. Operations research: applications and algorithms[M]. Duxbury Press, 2004.

Graph partition based mapping algorithm on multiprocessors for streaming applications

TANG Qi, WU Shang-feng, SHI Jun-wu, WEI Ji-bo

(College of Electronic Science and Engineering, National University of Defense Technology, Changsha 410073, China）

To take advantage of multiprocessor platform, it is a necessity to map tasks of the application properly onto different processors to exploit the concurrency in the application and thus meet the stringent timing requirements. Parallelism graph was proposed to quantify and model the concurrency among tasks of the application. An algorithm was also proposed to construct the parallelism graph based on the self-timed schedule and transform the mapping problem to a graph partitioning problem. The graph partitioning problem as a pure 0-1 integer linear programming model was further formulated and the ILP solver to find the optimal result. A lot of randomly generated synchronous dataflow graphs and a set of practical applications were used to evaluate the performance of the proposed method. The experimental results demonstrate that the proposed method outperforms available algorithms.

synchronous dataflow graph, mapping, multiprocessor, graph partition

TP399

A

10.11959/j.issn.1000-436x.2016123

2015-10-14；

2016-05-11

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61471376）

The National Natural Science Foundation of China (No.61471376)

唐麒（1986-），男，湖南益陽(yáng)人，國(guó)防科技大學(xué)博士生，主要研究方向?yàn)檐浖o(wú)線電技術(shù)和嵌入式并行計(jì)算。

吳尚峰（1986-），男，重慶人，國(guó)防科技大學(xué)博士生，主要研究方向?yàn)檐浖o(wú)線電技術(shù)。

施峻武（1977-），男，云南曲靖人，國(guó)防科技大學(xué)講師，主要研究方向?yàn)檐浖o(wú)線電技術(shù)。

魏急波（1967-），男，湖南漢川人，國(guó)防科技大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)橥ㄐ判盘?hào)處理與通信網(wǎng)絡(luò)。