片上網絡異構多核系統任務調度與映射

楊鵬飛,王泉

(西安電子科技大學計算機學院,710071,西安)

?

片上網絡異構多核系統任務調度與映射

楊鵬飛,王泉

(西安電子科技大學計算機學院,710071,西安)

針對傳統任務模型包含有效信息少,任務調度算法效率低、效果差的問題,設計了新的任務模型,提出了一種改進的粒子群算法(optimized particle swarm optimization, oPSO)。新模型增加了對任務類型及任務間遷移成本、計算單元類型及其運行成本等特性的描述。通過分析任務調度問題的需求,制定了oPSO算法的編解碼方案,設定了算法各個關鍵部分參數及計算方法,并解決了粒子群算法(PSO)在任務調度前期收斂速度過快、后期易陷入局部最優的問題。在不同任務規模下分別對遺傳算法(GA)、PSO以及oPSO算法進行調度仿真對比,當IP核數目為100左右時,oPSO算法較GA算法和PSO算法運行時間至少縮短10%,系統功耗至少降低15%,實驗結果表明:oPSO算法調度效果明顯優于其他算法,且各節點上功耗更為均衡,適用于解決任務調度問題。

多核系統;片上網絡;任務劃分;IP映射

利用片上網絡連接的系統級芯片(system-on-chip, SOC)成為新一代復雜計算體系結構的必然選擇[1],但是也給系統設計帶來很多新的問題與挑戰,任務的調度映射問題成為研究重點,決定了任務在體系結構上的實現方式、處理性能和效率。調度問題的通用解決思路是將任務抽象成某種形式的模型來設計調度算法,根據子任務之間的信息,以整個系統運行時間最短為目標對任務進行分配與調度[2-4],這其中涉及任務模型的設計以及調度算法的選擇應用兩個關鍵部分。

任務模型方面,最為普遍的是有向無環圖(directed acyclic graph, DAG)模型。DAG模型將任務間的關系簡單抽象為前后調用關系、數據通信量以及其在不同計算單元上的運算時間,而任務間的相互依賴關系復雜,其他影響因素例如任務類型、其對應的計算單元的種類、子任務在不同計算單元上的運行成本等,DAG模型并沒有全面包含,且模型較少地考慮任務在不同計算單元間的遷移成本。

調度算法方面,從進行調度決策的時機來看,可以分為靜態調度和動態調度。靜態任務調度是由編譯器在編譯時進行調度決策。例如基于列表的算法(list-based)[3-4]、聚類算法[5-7]和基于副本的算法(duplication based algorithms)[6-7]。靜態調度模型有一些缺點,如模型只是基于對處理器間通信和執行時間的近似估計,會產生不好的調度結果。動態任務調度是根據系統中實際任務運行時的情況實時將其調度到相應的計算單元上執行,并滿足系統所要求的各項約束指標,例如基于遺傳算法[8]和蟻群[9-10]的啟發式任務調度、基于任務池庫的動態調度算法[11]、粒子群優化算法(particle swarm optimization,PSO)[12]以及基于實時性約束的動態調度算法[13]等。在實際應用中,這些算法本身的問題容易導致運行過程中產生種種弊端。例如遺傳算法參數較多、編程實現比較復雜,且易陷入局部最優;蟻群算法前期不能很好地覆蓋全部集合;粒子群優化算法較遺傳算法更加方便高效,但是其初期收斂速度過快,易陷入局部最優,后期的局部搜索能力較差,收斂速度緩慢。以上種種問題導致應用傳統算法進行調度計算都會導致結果與最優值間存在差距。

此外,目前的調度算法多數較少或者沒有綜合考慮功耗均衡、資源占用等其他因素,沒有考慮片上網絡拓撲的異構性,且大多忽略任務間的通信延時,算法的實用性較差。在項目組之前的研究中,針對片上網絡規模大,片上可調用資源相對任務規模有較大盈余的情況,將調度方案分為任務劃分與調度和IP映射兩個部分完成[14],但是IP映射算法在片上網絡規模不大,任務運行需調用全部片上資源的情況下成為多余運算,浪費了系統資源。

本文重新設計了任務模型,使其能真實反映子任務間調度與制約關系。適應性的設計改進粒子群優化算法,使其適用于異構多核任務調度映射問題,并克服了算法本身容易陷入局部最優、后期局部搜索能力差的缺陷。利用其將一個大的任務按照通信量及調用關系分割成數個具有高并行性、粒度大小合適的子任務,結合任務性質分配到相應的計算單元上,在任務執行時間短、占用系統資源少、功耗均衡的前提下,進一步降低整個系統的通信延時。

1 相關模型

算法設計了兩個模型,任務調度模型和通信核圖。任務調度模型將任務抽象為一個五元組

ODAG=(V,E,S,U,C)

(1)

式中:V表示任務節點集,即頂點v∈V表示一個子任務;E表示邊集,邊eij∈E表示任務vi到vj存在數據通信,方向表示數據傳遞方向;S表示任務類型,其與計算單元的類型對應,即任務只能被分配到與之類型匹配的計算單元上執行,可以通過矩陣D={da,b}表示,元素da,b=∞表示任務va不適宜在計算單元pb上執行,da,b=t表示va可以在pb上執行,執行時間為t。元素Ur∈U表示第r種計算單元的單位時間運行成本。元素Cij∈C表示子任務vi通過邊eij到vj的遷移成本,當vi到vj分配到同一個計算單元上時,Cij為0。

子任務映射到計算單元上,會形成具有通信關系的通信核圖,可以抽象為一個三元組

CDAG=(P,R,T)

(2)

式中:P表示通信核圖中的計算單元集合,其中頂點pη(r)∈P,η是計算單元的唯一識別編碼,r為類型編碼;R表示邊集,邊rxy∈R表示計算單元px與py之間存在數據交換;T為計算單元間的通信開銷,Txy表示計算單元px與py之間的通信總量。

2 調度算法

粒子群算法不能直接用于解決任務調度映射問題,必須進行適應性的優化設計。

2.1 編解碼

子任務和計算單元的數目經常是不同的,設一個任務中包含N個子任務,系統中有M個可利用的計算單元,這些計算單元可分為m種,按子任務數與計算單元數的大小關系,編碼分為以下3種情況。

(1)計算單元數等于子任務數。粒子編碼長度等于子任務數,假設N=M=10,粒子(2,3,5,1,10,8,6,9,7,4)即是一個可行的調度方案,見表1。

表1 M等于N時編碼示例

(2)計算單元數大于子任務數。粒子編碼長度等于計算單元的數目,編碼時首先添加M-N個虛擬子任務,這些子任務在任意計算單元上的執行時間均為0,它們與其他N個子任務間的通信量為0。假設M=10、N=6,粒子編碼示例見表2。

表2 M大于N時編碼示例

(3)計算單元數小于子任務數。首先采用線性聚簇的思想,將通信量大且能在同一個計算單元上執行的子任務合并,直到合并后的子任務數等于計算單元數。對于ODAG,首先將所有子任務中相鄰的有通信關系且其對應計算單元類型有交集的子任務按照通信量的大小排序,然后按照通信量,從大到小進行合并,直到子任務數等于計算單元數。假設M=6、N=10,粒子編碼示例見表3。

表3 M小于N時編碼示例

通過以上處理,計算單元數等于子任務數,編碼方式等同于第一種描述情況。

解碼方面,算法結束后,會得到一個最優的計算單元序列,每個計算單元所在的位置序列即代表其需要執行的子任務編號。對于計算單元數目大于子任務數的情況,由于虛擬子任務是不占用運算資源和通信資源的,所以運行虛擬子任務的計算單元實際是不被調用的;對于計算單元數小于子任務數的情況,計算單元的位置序列對應的是合并后的子任務編號,只需將合并后的子任務編號與合并前的編號對應起來,即可實現解碼操作。

由前面的問題模型可知,每個子任務在不同計算單元上的執行時間是已知的,每個計算單元上任務運行的時間為

(3)

式中:Ti,x表示子任務vi在第x個計算單元上的運行時間;q表示分配到第x個計算單元上的子任務的數目。用k表示此次調度算法中可調用的計算單元的總數目,則任務總完成時間為

(4)

完成任務的總運行成本為

(5)

假設分配到第x個計算單元上的任務集合為Vx,分配到第y個計算單元上的任務集合為Vy,則計算單元px與py之間的任務遷移成本為

(6)

整個任務的遷移成本為

(7)

拓撲上,計算單元px與py的通信成本為

(8)

式中:Txy是px與py之間的通信總量;D(L(px),L(py))是px與py在拓撲上的映射位置之間的曼哈頓距離。

2.2 初始化及適應度函數

設種群規模為S、子任務數為N、計算單元的總數為M、計算單元種類數為m,則種群的初始化描述為:隨機產生S個粒子,第s個粒子的位置由向量xs=(xs1,xs2,…,xsn)表示,其中1≤s≤S,1≤n≤N,xsn(1≤xsn≤M)表示在第s個粒子中任務s被分配到第xsn個計算單元上運行;粒子速度由向量vs=(vs1,vs2,…,vsn)表示,其中1≤s≤S,1≤n≤N,-M≤vsn≤M。時間的適應度函數為

(9)

(10)

(11)

(12)

算法選擇總適應度高的粒子,為進化出下一代優秀的粒子提供優良基礎。α、β和δ為權重系數,表示在粒子選擇時更側重于哪方面的性能。

2.3 位置及速度更新

(13)

(14)

式中:w用來控制粒子歷史速度對當前速度的影響程度,對于平衡算法全局與局部搜索能力有很大作用。w較大時算法具有較強的全局搜索能力,w較小時算法有利于局部搜索,采用如下線性遞減慣性權重

w(g)=ws(ws-we)(G-g)/G

(15)

式中:ws、we分別為初始慣性權重和迭代至最大次數G時的慣性權重。w隨著迭代次數變化,使得算法在開始時搜索較大區域,較快地確定最優解的大致位置,之后粒子速度減慢,開始細致的局部搜索,避免算法陷入局部最優出現早熟現象,并在迭代后期仍然能夠保持較強的搜索能力,提高了算法性能。

2.4 算法流程

步驟1 按照上文描述,對粒子群位置和速度進行隨機初始化;

步驟2 計算每個粒子的適應度F,設置粒子的Bp和Ba;

步驟3 如果Bp和Ba在多次迭代中始終保持不變,或者算法達到最大迭代次數,輸出最優解,算法結束,否則轉至步驟4;

步驟4 對每個粒子根據式(13)、(14)更新粒子的速度和位置;

步驟5 轉至步驟3。

3 對比實驗及分析

本文從兩方面對所設計的調度映射方案進行對比和評價,一是算法本身的執行速度,通過對相同規模的任務分別按照遺傳算法(genetic algorithm,GA)、PSO算法及本文改進的粒子群算法(optimized particle swarm optimization,oPSO)進行運算。這部分在Matlab2012b上完成,軟件環境是惠普的Z800工作站,CPU為Xeon E5530,主頻為2.4 GHz,內存為8 GB,操作系統為64位Windows XP系統,實驗中所需不同規模的任務由任務產生工具(task graph for free, TGFF)[15]產生,粒子數S設置為100,迭代次數均為200次,群體最優值的停滯代數設為5,α、β和δ均設置為1,加速因子c1=c2=2,不同任務規模下算法運行時間t對比如圖1所示。

圖1 算法執行時間對比

當任務規模較小時,oPSO相比PSO算法優勢不大,運行時間甚至會略大于PSO算法,這是因為oPSO在進行粒子更新操作時多了對權值w的更新計算,增加了運算步驟和運行時間,算法優勢隨任務規模的擴大逐漸明顯。我們統計了200次迭代中得到最優解的次數,GA算法是43次,PSO算法是69次,而oPSO算法能達到131次,運算結果明顯優于其他兩種算法。

對比不同映射結果在運行過程中產生的包平均延時L和系統功耗W。實驗運行平臺參數同上,片上網絡拓撲采用常用的Mesh結構,路由算法使用XY路由算法,對比結果如圖2所示,當任務規模較小時,3種算法調度效果性能差異不大,隨著任務規模不斷擴大(子任務數為100時),無論是包平均延時還是系統功耗,oPSO算法的調度效果都要明顯優于其他兩種算法。

同時,實驗記錄了片上網絡上每個交換節點處的功率情況,圖3是節點規模為100的情況下,分別執行3種算法時各個節點上的功率分布,可以看到,oPSO算法能將任務較為均衡地映射在整個系統上,不會出現過度繁忙或空閑的節點或區域,功耗較為均衡。

4 結 論

本文分析了片上網絡系統任務調度映射中的關鍵問題,設計了新任務模型,使其能夠更加真實地反映子任務間的制約關系;以單位時間運行成本作為衡量標準,算法調度結果更加高效、 實用;

調度目標

A:時鐘周期(a)包平均延時對比

(b)系統功耗對比圖2 算法執行效果對比

(a)GA算法節點功率分布

(b)PSO算法節點功率分布

(c)oPSO算法節點功率分布圖3 交換節點上的功率分布比較

不僅考慮任務總的完成時間,同時也考慮時間成本和資源成本,從而達到系統性能的綜合優化;改進了PSO算法,使其適于解決大規模任務調度問題,克服了算法前期搜素過快,容易出現早熟現象,后期搜索能力下降,易陷入局部最優的缺點。

[1]ADDO-QUAYE C.Thermal-aware mapping and placement for 3-D NoC designs [C]∥Proceedings of the 2005 IEEE International SOC Conference.Piscataway, NJ, USA: IEEE, 2005: 25-28.

[2]SINGH A K, WU Jigang, PRAKASH A, et al.Mapping algorithms for NoC-based heterogeneous MPSoC platforms [C]∥Proceedings of the 12th Euromicro Conference on Digital System Design, Architectures, Methods and Tools.Piscataway, NJ, USA: IEEE, 2009: 133-140.

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

[4]DAOUD M I, KHARMA N.Efficient compile-time task scheduling for heterogeneous distributed computing systems [C]∥Proceedings of the 12th International Conference on Parallel and Distributed Systems.Piscataway, NJ, USA: IEEE Computer Society, 2006: 1-9.

[5]WU Minyou, GAJSKI D D.Hypertool: a programming aid for message-passing systems [J].IEEE Transactions on Parallel and Distributed Systems, 1990, 1(3): 330-343.

[6]CHUNG Y C, RANKA S.Applications and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessors [C]∥Proceedings of the Supercomputing ’92.Piscataway, NJ, USA: IEEE, 1992: 512-521.

[7]ANMAD I, KWORK Y K.A new approach to scheduling parallel programs using task duplication [C]∥Proceedings of the International Conference on Parallel Processing.Piscataway, NJ, USA: IEEE, 1994: 47-51.

[8]SAYUTI M N S M, INDRUSIAK L S.Real-time low-power task mapping in networks-on-chip [C]∥Proceedings of the 2013 IEEE Computer Society Annual Symposium on VLSI.Piscataway, NJ, USA: IEEE, 2013: 14-19.

[9]FERRANDI F, LANZI P L, PILATO C, et al.Ant colony heuristic for mapping and scheduling tasks and communications on heterogeneous embedded systems [J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2010, 29(6): 911-924.

[10]SILVA L, NEDJAH N, MOURELLE L.ACO approach in static routing for network-on-chips with 3D mesh topology [C]∥Proceedings of the 2013 IEEE 4th Latin American Symposium on Circuits and Systems.Piscataway, NJ, USA: IEEE, 2013: 1-4.

[11]HOFFMANN R, RAUBE T.Dynamic task scheduling and load balancing on cell processors [C]∥Proceedings of the 2010 18th Euromicro International Conference on Parallel, Distributed and Network-Based Processing.Piscataway, NJ, USA: IEEE Computer Society, 2010: 205-212.

[12]SIDHU M S, THULASIRAMAN P.A load-rebalance PSO heuristic for task matching in heterogeneous computing systems [C]∥Proceedings of the 2013 IEEE Symposium on Swarm Intelligence.Piscataway, NJ, USA: IEEE, 2013: 180-187.

[13]AMOLD O, FETTWEIS G.Power aware heterogeneous MPSoC with dynamic task scheduling and increased data locality for multiple applications [C]∥Proceedings of the 2010 International Conference on Embedded Computer Systems.Piscataway, NJ, USA: IEEE, 2010: 110-117.

[14]YANG Pengfei, WANG Quan.Effective task scheduling and IP mapping algorithm for heterogeneous NoC-based MPSoC [J].Mathematical Problems in Engineering, 2014, 2014: 202748.

[15]DICK R P, RHODES D L, WOLF W.TGFF: task graphs for free [C]∥Proceedings of the 6th International Workshop on Hardware/Software Codesign.Piscataway, NJ, USA: IEEE Computer Society, 1998: 97-101.

(編輯 武紅江)

An Effective Scheduling and Mapping Algorithm of Tasks for Heterogeneous NoC-Based MPSoC

YANG Pengfei, WANG Quan

(School of Computer, Xidian University, Xi’an 710071, China)

A new task model is designed and an optimized particle swarm optimization (oPSO) algorithm is proposed to solve the problem that the traditional task DAG model contains less information and the existing task scheduling algorithms based on the model are of inefficiency.The new model adds the description of task type and some real inter-task relations such as transfer cost of the task, the type of processing element (PE) and its running cost.After the requirements of task scheduling and mapping are analyzed, a new scheme of coding and decoding is formulated, key parameters of the algorithm and their calculation are proposed, and the shortcomings of the particle swarm optimization algorithm such as poor local search capacity in the early period and being easily trapped into local optima in the late period of the algorithm are overcome.Simulations and comparisons with the GA and PSO algorithms under different IP scales show that when the number of IPs is about 100, the execution time and the power consumption of the oPSO algorithm reduce at least 10% and 15%, respectively, the scheduling effect of oPSO is much better than those of other algorithms, and the energy consumption on each IPs is balanced.Thus it can be concluded that the proposed algorithm is applicable for the solution of task scheduling.

multiprocessor system-on-chip; network on chip; task scheduling; IP mapping

2014-10-21。 作者簡介:楊鵬飛(1985—),男,博士生;王泉(通信作者),男,教授,博士生導師。 基金項目:國家自然科學基金資助項目(61474087)。

時間:2015-04-29

http:∥www.cnki.net/kcms/detail/61.1069.T.20150429.1437.002.html

10.7652/xjtuxb201506012

TN409

A

0253-987X(2015)06-0072-05