一種負載感知的異構(gòu)MPSoC任務(wù)調(diào)度算法

謝 盈，吳盡昭，丁旭陽，張 暉

?

一種負載感知的異構(gòu)MPSoC任務(wù)調(diào)度算法

謝 盈1,3,5，吳盡昭2，丁旭陽4，張 暉1,3

(1. 中國科學院成都計算機應(yīng)用研究所 成都 610041；2. 廣西民族大學廣西混雜計算與集成電路設(shè)計分析重點實驗室 南寧 530006； 3. 中國科學院大學 北京 石景山區(qū) 100049；4. 電子科技大學計算機科學與工程學院 成都 611731； 5. 西南民族大學計算機科學與技術(shù)學院 成都 610041)

處理器核的異構(gòu)性、運行時負載和任務(wù)間依賴關(guān)系，是影響異構(gòu)MPSoC任務(wù)調(diào)度算法性能的關(guān)鍵因素。該文提出了一種負載感知的異構(gòu)MPSoC任務(wù)調(diào)度算法，在滿足任務(wù)間依賴關(guān)系的前提下，根據(jù)計算開銷和通信負載將待調(diào)度任務(wù)集劃分為任務(wù)子集。在考慮處理器核負載狀態(tài)的基礎(chǔ)上，通過賦權(quán)二部圖最大權(quán)匹配，將任務(wù)子集調(diào)度到適載的處理器核上運行，提高了待調(diào)度任務(wù)集總執(zhí)行效率。仿真實驗結(jié)果表明，該算法有效降低了任務(wù)集的調(diào)度長度，提高了處理器核的利用率。

異構(gòu)MPSoC; 負載感知; 任務(wù)調(diào)度; 任務(wù)劃分

片上多核處理器MPSoC(multi-processor system- on-chip)把多個處理核心集成到一個芯片中，通過這些處理核心的并行工作提高系統(tǒng)性能，以滿足日益增長的功能及性能需求[1]。其中，異構(gòu)MPSoC中的處理器核心具有不同結(jié)構(gòu)、地位、功耗及運算能力，大幅度增強了信息處理能力。在實際應(yīng)用中，任務(wù)調(diào)度算法的優(yōu)劣直接影響異構(gòu)MPSoC系統(tǒng)的利用率[2]，是被廣泛關(guān)注的研究熱點。

目前，針對復雜任務(wù)的調(diào)度技術(shù)主要有隨機搜索調(diào)度技術(shù)和啟發(fā)式調(diào)度技術(shù)[3-4]。隨機搜索調(diào)度技術(shù)如遺傳算法[5-6]、模擬退火算法[7]等，隨著任務(wù)數(shù)和核數(shù)量的增加，搜索開銷和計算復雜度呈非線性增長，收斂速度急劇下降。而啟發(fā)式調(diào)度技術(shù)因設(shè)計簡單且能夠獲得較好的次優(yōu)解，獲得更多研究者的青睞，涌現(xiàn)出大量研究成果，如：對任務(wù)進行分簇的邊消除算法[8]；為了減小通信依賴而對前驅(qū)任務(wù)進行復制的任務(wù)復制算法[9]；根據(jù)任務(wù)屬性構(gòu)造任務(wù)列表以依次調(diào)度任務(wù)的最早截止時間優(yōu)先算法[10]、關(guān)鍵路徑算法[11]、優(yōu)先級調(diào)度算法[12]等。但是在任務(wù)間依賴關(guān)系復雜、異構(gòu)處理器核性能差異較大的情況下，以上算法靈活性較差，且存在處理器負載不均的問題。為此，研究人員在考慮核異構(gòu)性的基礎(chǔ)上，應(yīng)用啟發(fā)式調(diào)度技術(shù)以獲得更好的調(diào)度性能。HEFT(heterogeneous earliest-finish-time)算法[13]將EDF算法應(yīng)用于異構(gòu)環(huán)境，是異構(gòu)環(huán)境下很多其他調(diào)度模型的基礎(chǔ)，但缺乏處理系統(tǒng)過載的能力。文獻[14]提出的PLTSF(probably lag time shortest first)算法，通過復制fork節(jié)點將具有復雜依賴關(guān)系的任務(wù)轉(zhuǎn)化為多個相互獨立的并行任務(wù)樹，再動態(tài)地計算任務(wù)樹優(yōu)先級，根據(jù)優(yōu)先級將任務(wù)分配到處理器核上，但該算法每次只選擇一個任務(wù)進行映射，效率較低。

本文提出了一種具備負載感知能力的異構(gòu)MPSoC任務(wù)調(diào)度算法LATS(load-aware task scheduling)，依據(jù)任務(wù)計算開銷和任務(wù)間通信負載，將具有依賴關(guān)系的任務(wù)集劃分為并行任務(wù)子集，在考慮處理器核負載狀態(tài)的前提下，根據(jù)賦權(quán)二部圖的最大權(quán)匹配將多個任務(wù)子集優(yōu)化調(diào)度到適載處理器核上，提高了待調(diào)度任務(wù)集的總執(zhí)行效率。仿真實驗及結(jié)果表明，本文提出的算法在負載感知的基礎(chǔ)上，有效降低了任務(wù)集的調(diào)度長度，提高了處理器核利用率。

1 系統(tǒng)模型

如圖1所示，該DAG圖表示了個任務(wù)的計算開銷，任務(wù)間依賴關(guān)系和通信負載。后續(xù)任務(wù)需要使用其所有直接前驅(qū)任務(wù)的輸出結(jié)果或占用的系統(tǒng)資源，因此，后續(xù)任務(wù)要等其所有直接前驅(qū)任務(wù)都執(zhí)行結(jié)束后，才能開始被調(diào)度執(zhí)行。

圖1 任務(wù)集DAG圖示

2 負載感知異構(gòu)MPSoC任務(wù)調(diào)度算法

2.1 任務(wù)子集劃分

為了充分利用MPSoC豐富的計算資源，LATS算法在任務(wù)子集劃分階段以盡量降低任務(wù)間通信負載為目標，將含有個任務(wù)的任務(wù)集劃分為個并行任務(wù)子集。

LATS任務(wù)子集劃分算法如圖2所示。

1) 按任務(wù)節(jié)點索引值遞增的順序遍歷所有節(jié)點。任務(wù)節(jié)點索引值定義為：

圖2 任務(wù)子集劃分流程圖

2.2 負載感知調(diào)度

在異構(gòu)MPSoC環(huán)境下，每個處理器核的計算速率和當前負載都是不相同且在隨時變化的，負載感知調(diào)度綜合考慮當前處理器核的負載、處理器核運算速率、任務(wù)間通信負載和任務(wù)計算開銷等多個方面的因素，將劃分好的任務(wù)子集在運行時環(huán)境下動態(tài)地映射到合適的處理器核。

MPSoC相較于多處理器系統(tǒng)和分布式系統(tǒng)，其核間通信速率大大提升，處理器核采用計算與傳輸重疊模式工作，即處理器核能夠在運行任務(wù)的同時發(fā)送/接收數(shù)據(jù)，因此，在MPSoC環(huán)境下核間通信已不是影響處理器核執(zhí)行效率的主要因素。

基于賦權(quán)二部圖最大權(quán)匹配的負載感知調(diào)度如圖3所示。

圖3 負載感知調(diào)度流程圖

且由

6) 若未分配完所有任務(wù)子集，轉(zhuǎn)步驟1)，否則算法結(jié)束。

2.3 算法復雜度分析

3 仿真實驗及結(jié)果分析

圖4、圖5分別在CCR為0.5和2時，LATS、HEFT和PLTSF的平均調(diào)度長度的比較圖。

圖4 不同任務(wù)數(shù)的平均調(diào)度長度(CCR=0.5)

圖5 不同任務(wù)數(shù)的平均調(diào)度長度(CCR=2)

從兩幅圖均可看出，隨著任務(wù)節(jié)點數(shù)的增加，系統(tǒng)負載相應(yīng)增大時，LATS的平均調(diào)度長度明顯優(yōu)于HEFT和PLTSF。這是因為LATS考慮了當前系統(tǒng)所有核的負載，將一批任務(wù)同時分配到適載處理器核，而HEFT和LATS每次只把一個任務(wù)分配到能使其最早執(zhí)行的處理器核上，只能實現(xiàn)局部最優(yōu)。

值得注意的是，從圖4和圖5的對比可以看出，當CCR較大時，LATS算法相同任務(wù)數(shù)的平均調(diào)度長度得到進一步提高。這是因為在LATS算法任務(wù)子集劃分階段將具有最大前驅(qū)開銷的任務(wù)劃分在了一個任務(wù)子集，并在調(diào)度階段將任務(wù)子集中的所有任務(wù)都調(diào)度到處理器核，降低了任務(wù)間的通信開銷。

圖6統(tǒng)計了1 000幅含有150個任務(wù)節(jié)點的隨機DAG圖在運行LATS算法、HEFT算法和PLTSF算法的處理器核的利用率。異構(gòu)MPSoC處理器核利用率是每個異構(gòu)核利用率的算術(shù)平均值。

圖6 處理器核利用率

從圖6可知，LATS算法的處理器核利用率較之HEFT算法和PLTSF算法有所提升，且由于LATS算法每次分配一批任務(wù)到適載處理器核，而不是一個一個地分配，其處理器核利用率在任務(wù)集運行之初增長較快。

4 結(jié)束語

任務(wù)調(diào)度算法使得異構(gòu)MPSoC的性能得以充分發(fā)揮，而處理器核的異構(gòu)性、運行時負載和任務(wù)間依賴關(guān)系，是影響異構(gòu)MPSoC上任務(wù)調(diào)度算法性能的關(guān)鍵因素。本文提出了一種負載感知的異構(gòu)MPSoC任務(wù)調(diào)度算法LATS，在滿足任務(wù)間依賴關(guān)系的前提下，根據(jù)計算開銷和通信負載將待調(diào)度任務(wù)集劃分為任務(wù)子集；在考慮處理器核負載狀態(tài)的基礎(chǔ)上，通過賦權(quán)二部圖最大權(quán)匹配，將任務(wù)子集調(diào)度到適載處理器核上運行，提高了待調(diào)度任務(wù)集總執(zhí)行效率。仿真實驗結(jié)果表明，LAST算法有效降低了具有依賴關(guān)系的DAG任務(wù)圖的調(diào)度長度，提高了處理器核利用率。

[1] AGERWALA T, CHATTERIJEE S. Computer architecture: Challenge and opportunities for the next decade[J]. IEEE Micro, 2005, 25(3): 58-69.

[2] POORANI A, ANURADHA B, VIVEKANADHAN C. An effectual elucidation of task scheduling and memory partitioning for MPSoC[C]//2014 IEEE 8th International Conference on Intelligent Systems and Control(ISCO). Coimbatore. India: IEEE, 2014: 295-299.

[3] YAO Xuan-xia, GENG Peng, DU Xiao-jiang. A task scheduling algorithm for multi-core processors[C]//2013 International Conference on Parallel and Distributed Computing, Applications and Technologies(PDCAT). Washington DC, USA: IEEE Computer Society, 2013: 259-264.

[4] LZAKIAN H, ABRAHAM A, SNASEL V. Comparison of heuristics for scheduling independent tasks on heterogeneous distributed environments[C]//Proceedings of the 2009 International Joint Conference on Computational Sciences and Optimization. NJ: IEEE Computer Society, 2009: 8-12.

[5] MITEHELL M. An Introduction to genetic algorithms[M]. Cambrige, MA: The MIT Press, 1996.

[6] QIU Mei-kang, MING Zhong, LI Jia-yin, et al. Phase-change memory optimization for green cloud with genetic algorithm[J]. IEEE Transactions on Computers, 2015, 16(12): 3528-3540.

[7] JIANG Hua, BAO Yun, ZHENG Li-ping, et al. A hybrid algorithm of harmony search and simulated annealing for multiprocessor task scheduling[C]//2012 International Conference on Systems and Informatics(ICSAI). Yantai, China: IEEE, 2012: 718-720.

[8] MISHRA A, TRIPATHI A K. An extention of edge zeroing heuristic for scheduling precedence constrained task graphs on parallel systems using cluster dependent priority scheme[C]//2010 International Conference on Computer and Communication Technology(ICCCT). Allahabad(UP), India: IEEE Communication Society and IEEE UP Section, 2010: 647-651.

[9] DARBHA S, AGRAWAL D P. Optimal scheduling algorithm for distributed memory machines[J]. IEEE Transactions on Parallel and Distributed Systems, 1998, 9(1): 87-91.

[10] ZAID A B, ZENG Hai-bo, MARCO D N, et al. Multitask implementation of synchronous reactive models with earliest deadline first scheduling[C]//2013 8th IEEE International Symposium on Industrial Embedded Systems(SIES). Porto, Portugal: IEEE, 2013: 168-177.

[11] ARABNEJAD H, BARBOSA J G. List scheduling algorithm for heterogeneous systems by an optimistic cost table[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(3): 682-694.

[12] LIU Xin, LIVIU I, RUI Kang, et al. Real-time household load priority scheduling algorithm based on prediction of renewable source availability[J]. IEEE Transactions on Consumer Electronics, 2012, 58(2): 318-326.

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

[14] 黃殊娟, 朱怡安, 李兵哲, 等. 具有依賴關(guān)系的周期任務(wù)實時調(diào)度方法[J]. 計算機學報, 2015, 38(5): 999-1006.

HUANG Shu-juan, ZHU Yi-an, LI Bing-zhe, et al. Real-time scheduling method for dependency period task[J]. Chinese Journal of Computers, 2015, 38(5): 999-1006.

編 輯 蔣 曉

A Load-Aware Task Scheduling Algorithm on Heterogeneous MPSoC

XIE Ying1,3,5, WU Jin-zhao2, DING Xu-yang4, and ZHANG Hui1,3

(1. Chengdu Institute of Computer Application, Chinese Academy of Sciences Chengdu 610041; 2. Guangxi Key Laboratory of Hybrid Computational and IC Design Analysis, Guangxi University for Nationalities Nanning 530006; 3. University of Chinese Academy of Sciences Shijingshan Beijing 100049; 4. School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu 611731; 5. School of Computer Science and Technology, Southwest University for Nationalities Chengdu 610041)

The performance of task scheduling algorithm on heterogeneous MPSoC is affected by heterogeneous cores, run-time load and tasks dependencies. A novel load-aware task scheduling algorithm is proposed on heterogeneous MPSoC, which divides task-set into task-subsets based on tasks dependencies, computation overhead and communication overhead. In considering the core’s load state, task-subsets are dispatched to appropriate cores by maximum weight matching of weighted bipartite graph, which improves the overall efficiency of task-set. Simulation results show that the proposed algorithm can reduce the length of task-set scheduling and improve the utilization of cores.

heterogeneous MPSoC; load-aware; tasks dispatch; tasks divide

TP301

A

10.3969/j.issn.1001-0548.2017.06.017

2016-04-21；

2016-07-15

國家自然科學基金(11371003，11461006)；廣西自然科學基金(2012GXNSFGA060003)；中央高?；究蒲袠I(yè)務(wù)費(2015NZYQN28).

謝盈(1984-)，女，博士生，主要從事嵌入式系統(tǒng)、形式化方法方面的研究.