謝 盈，吳盡昭，丁旭陽(yáng)，張 暉

?

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

謝 盈1,3,5，吳盡昭2，丁旭陽(yáng)4，張 暉1,3

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

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

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

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

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

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

1 系統(tǒng)模型

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

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

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

2.1 任務(wù)子集劃分

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

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

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

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

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

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

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

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

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

且由

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

2.3 算法復(fù)雜度分析

3 仿真實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

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

圖6 處理器核利用率

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

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

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

[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ù)實(shí)時(shí)調(diào)度方法[J]. 計(jì)算機(jī)學(xué)報(bào), 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

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

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