基于圖分割的流應用多處理器映射算法

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

?

基于圖分割的流應用多處理器映射算法

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

（國防科技大學電子科學與工程學院，湖南長沙 410073）

為了充分利用多處理器平臺所提供的計算資源，需要將應用以適當的方式映射到不同處理器，從而最大程度地挖掘應用所提供的并發性以滿足應用嚴格的實時性要求。提出了并發圖來量化、建模應用任務間的并發性，提出了一種基于自同步調度的并發圖構建算法，并將任務映射問題轉換成圖分割問題，然后將并發圖分割問題建模為純0-1整數線性規劃模型并采用ILP求解器獲得最優解。采用了大量隨機生成的同步數據流圖以及一組實際應用對所提方法進行性能評估，實驗結果表明所提方法性能優于已有算法。

同步數據流圖；映射；多處理器；圖分割

1 引言

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

應用調度包括任務映射、排序和定時[2]。任務映射是將任務分配到不同處理器上的過程。對于最優調度，無論最優性的評價標準是什么，總存在對應的最優映射，因此研究如何獲得最優映射具有重要價值。對于映射問題，研究者提出了很多針對不同應用模型和平臺的算法。其中，圖分割法[3]和負載均衡法[4,5]得到了大量研究。然而，這2類算法要么在最小化處理器間通信的前提下最大化負載均衡水平，要么單純地均衡不同處理器上的負載，而沒有綜合考慮應用的內在結構，因此降低了性能。另一類方法是鏈式調度算法[6,7]，這類算法將任務調度分成優先級分配和調度2個步驟，然而，這類算法主要用于優化系統延時，雖然可以通過修正應用于吞吐量優化，但性能并不是很好。

本文研究SDFG在多處理器上的映射問題，以獲得可以最大化應用并發性的最優任務映射，從而使應用長期吞吐量最大化。本文提出了并發圖（PG，parallelism graph）來量化和建模SDFG中不同任務間的并發性，提出了一種基于自同步調度的并發圖構建算法，并將映射問題轉換化成圖分割問題，然后將圖分割問題建模為純0-1整數線性規劃模型（ILP，integer linear programming），并使用ILP求解器獲取最優解。

本文所提算法在SDF3[8]中實現，并采用隨機生成的SDFG和一組實際應用進行性能評估。算法的有效性通過與已有負載均衡算法[4,5]和HEFT算法[6]比較得以驗證。

2 相關工作

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

文獻[6,7]研究了如何利用應用結構特征，包括任務間依賴關系、任務執行時間及數據傳輸需求來提高調度性能。然而，這些方法針對由有向無環圖（DAG，directed acyclic graph）建模的應用，不能直接應用于SDFG。與DAG不同，SDFG可以支持任務間環狀依賴關系和多速率依賴，因此，任務間關系更為復雜。這種關系不能簡單地由模型中的路徑特征，比如路徑長度來描述。一種可行的方法是將SDFG轉換成同構SDFG，并進一步將同構SDFG轉換為無環依賴圖[2]。由于無環依賴圖屬于DAG，因此上面提到的調度算法可以直接使用。然而，這種方法主要用于允許任務復制的系統，為了適應無任務復制的系統，可以在調度時強制將同一任務的實例分配到同一處理器。

3 應用模型

本文采用SDFG來建模流應用，如軟件無線電、通信協議、多媒體應用等。本文所采用SDFG模型的定義如下。

SDFG在執行過程中，任務將以不同頻率執行，因此在一次調度中會出現不同次數。SDFG迭代及重復向量可以用于來描述SDFG的這一特征。

定義2 （SDFG迭代）SDFG迭代是執行每個任務最小正整數次數同時使各邊符號數目恢復初始值的過程。

SDFG的重復向量可以通過解平衡方程而得[1]。當平衡方程有非零解[1]時，重復向量存在，且這樣的 SDFG 總可以轉換成等價的 HSDFG[2]。

本文只考慮強連通SDFG，其中每個任務都與其他任意任務直接或間接相連。對實際應用，這是一個合理的假定，因為實際系統內存消耗是受限的，因此SDFG中任意邊的最大符號數目是有限的。通過為SDFG中的每條邊增加額外的最大符號數目約束邊，可以將非強連通SDFG轉換成強連通圖。

圖1所示為一個由5個任務組成的SDFG示例。圖中各邊末端數字為邊的產出或消費速率，為簡單起見，只有當速率大于1時才予以標注。邊附近的文字為邊的標簽，標簽后面括號中的數字表示邊上的初始符號數，如果初始符號數為0，則予以忽略。圖中SDFG的重復向量為，表示在一次應用迭代中，任務、、、和分別需要執行2、2、3、1和次。

4 問題闡述

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

對于SDFG，盡管可以從圖模型結構推導阻止任務并發執行的優先約束關系，任務間并發性并未明顯地建模出來，例如，2個任務在多大程度上可以并行執行并未在應用圖中得到描述。除此之外，也不能直接將任務間優先關系與任務間并行度關聯起來，使在映射中挖掘任務并發性變得極為困難。盡管如此，如果可以量化任務間并發程度，則映射問題可以次優地轉換成最大化任務間并發性的問題。基于以上觀察，本文從提取、量化SDFG任務間并發性著手，并使用圖分割法解決應用映射問題。

5 周期靜態調度與吞吐量分析

由于最終目標是獲得吞吐量最優的映射，分析映射的吞吐量顯得極為重要。本文假定系統根據靜態周期調度循環執行，靜態周期調度強制任務按照指定順序依次執行。不同迭代可以在時間上重疊，采用流水線的方式執行。本文采用最早開始時間調度算法為每個處理器構建周期靜態順序調度。當同一時刻有多個任務可以同時執行時，任意一個任務被選擇優先執行。為每個處理器構建好周期靜態調度后，應用吞吐量可以通過已有方法來計算。

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

6 并發圖及其構建

本節介紹并發圖的概念及其構建方法。并發圖用于量化和建模SDFG任務間的并發性，其定義如下。

本文通過SDFG的ASAP（as-soon-as-possible）調度（自同步調度[2]）的周期擴展來計算任務間并發度。在ASAP調度中，當任務所依賴數據就序時，任務即開始執行。ASAP調度定義如下。

ASAP調度由瞬態和緊隨其后的周期態組成，其定義如下。

應用吞吐量由ASAP調度的周期態決定，因此使用它來計算任務間并發度。盡管周期態中一個周期可能包含多次應用迭代，如周期態定義中的所指明的那樣，無論最后計算出的任務間并發度是否除以這一數值，并不會影響最后結果。由于周期態具有周期特征，因此并不需要構建完整的ASAP調度，可以在獲得一個完整的執行周期后停止執行。本文從周期態中提取一個執行周期，對其進行周期擴展，并根據這個周期擴展中不同任務的并行執行時間來量化任務間并發度。

圖1所示SDFG的ASAP調度如圖2所示，ASAP調度由瞬態和周期態組成。周期態從時刻18開始；在時刻53，再次經歷時刻18經歷的狀態。因此時刻18和53之間的執行形成一個周期，其中包含一次應用迭代。

并發圖構建算法詳細描述了構建并發圖的步驟。對一個SDFG，首先為其增加自邊以約束任務自動并發，也即同一時間一個任務最多只能有一個實例處于運行狀態。然后，初始化并發圖，為其添加節點。并發圖中的每個節點對應SDFG中的一個任務。其次，反復調用方程(1)構建SDFG的ASAP調度。在此過程中，提取ASAP調度的一個執行周期，并對其進行周期擴展。根據得到的周期擴展，計算PG中任意2個節點間的邊權，邊權等于對應任務在周期擴展中的重疊時間。

并發圖構建算法

11) end for

15) end if

16) end for

STEM教育與STEM職業的聯系 教育的目的是為社會建設培養專業人才，對接社會的現代化發展。STEM教育理工科屬性很強，從事社會建設的科技產業建設者需要具有此類的設計性思維，對于社會的科技產業具有很強的帶動作用。

17) end for

如算法中第6)~17)行所示，并發圖中2個節點間邊的邊權通過累加對應任務實例的并行執行時間而得。如果計算得到的邊權非零，則在并發圖中為相應節點增加一條邊，邊權設置為上面計算得到的值。

圖3為示例SDFG的并發圖及其鄰接矩陣。如圖2所示，不同執行周期在時間上不重疊，例如，第1個周期開始于時刻18而結束于時刻53，第2個周期開始于時刻53而結束于時刻87。因此，構建并發圖時，并不需要進行周期擴展。在圖2所示ASAP調度的第一個周期中，任務實例（上標表示實例索引）與重疊，重疊時間為5，因此，在并發圖中，任務和間有一條邊，邊權為5。類似地，可以為并發圖添加其他邊。

在并發圖中，由于邊權均為正整數，因此每一條邊均表示該邊所連接任務在一定程度上可以并發執行，邊權記錄了對應任務可并發執行的程度。如果在調度中有盡可能多的任務可以并發執行，則應用的一次迭代可以在更少的時間內完成，因而提高應用吞吐量。因此，以最大化吞吐量為目標的映射問題，在一定程度上可以等價于最大化映射的并發度。通過使用并發圖，任務間并發性得以量化，映射問題可以等價于分割并發圖并使割最大化。割定義為所連接任務被分配到不同處理器的邊的邊權之和。采用上述方法，可以將映射問題轉化成圖分割問題。

7 純0-1整數線性規劃模型

(4)

(5)

(7)

(8)

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

(10)

(11)

8 實驗與結果

本節通過實驗來評估所提算法的性能，并將本文所提算法與負載均衡算法[4]及HEFT算法[6]進行了比較。

8.1 度量參數

吞吐量是流應用系統的關鍵優化目標，如同文獻[4,5]一樣，本文采用吞吐量對算法性能進行評估。吞吐量采用第5節所介紹的方法計算。同時，在實驗中分析了不同映射算法所獲得映射方案的割值及算法時間開銷。割值大小反映了映射所挖掘的并發度，定義為跨越不同子集的邊的邊權之和。

8.2 測試基準

本文使用一組隨機生成的SDFG及一組實際應用進行性能測試，并使用開源工具SDF3[8]來產生隨機SDFG，其中任務數為5到15。對每個圖尺寸，均生成個100個隨機SDFG。SDFG參數包括任務執行時間和邊上的符號大小，均隨機生成。任務累積執行時間在400和1 000間均勻產生。

8.3 實驗結果

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

表1 隨機應用性能對比

表2所示為實際應用在多處理器上的測試結果。表中數據表明本文所提算法對實際應用仍然有效，吞吐量要優于負載均衡算法和HEFT。對調制解調器，使用所提算法與負載均衡算法和HEFT相比可以提高9.6%和18.6%的吞吐量。對其他應用，也可取得一定的性能增益。與隨機應用一樣，使用本文算法可以提高映射割值，再次驗證了映射割值與吞吐量之間的正相關關系，表明采用割值來優化映射問題要優于其他方法。在時間復雜度方面，除MP3解碼器1外，所提算法與負載均衡算法相當，略高于HEFT，表明所提算法可較好地應用于實際應用。

表2 實際應用性能對比

9 結束語

本文研究了SDFG在多處理器上的映射問題，以最大化應用吞吐量為目標。提出了并發圖來量化、建模應用并發性，提出了一種基于自同步調度的并發圖構建算法，并將映射問題轉換為圖分割問題，最后將圖分割問題建模為純0-1整數線性規劃問題。本文采用了一組實際應用和隨機產生的SDFG進行了算法性能評估。實驗結果表明本文所提算法的吞吐量性能要優于負載均衡算法和HEFT算法，證明采用并發圖及圖分割的方法求解映射問題優于已有方法。

[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

國家自然科學基金資助項目（No.61471376）

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

唐麒（1986-），男，湖南益陽人，國防科技大學博士生，主要研究方向為軟件無線電技術和嵌入式并行計算。

吳尚峰（1986-），男，重慶人，國防科技大學博士生，主要研究方向為軟件無線電技術。

施峻武（1977-），男，云南曲靖人，國防科技大學講師，主要研究方向為軟件無線電技術。

魏急波（1967-），男，湖南漢川人，國防科技大學教授、博士生導師，主要研究方向為通信信號處理與通信網絡。