多核平臺(tái)下考慮能耗的實(shí)時(shí)任務(wù)分派與調(diào)度研究

黃陽陽

摘 要：Single-clock multiprocessor Frequency Assignment Algorithm（SFAA）算法是一個(gè)對(duì)周期性的實(shí)時(shí)任務(wù)進(jìn)行分派與調(diào)度的算法。本文打算對(duì)SFAA算法和三種常見的分派和調(diào)度算法分別在4核和8核平臺(tái)下在能耗和時(shí)間兩個(gè)方面進(jìn)行比較和分析，并且從任務(wù)集的任務(wù)數(shù)、任務(wù)集的利用率，即任務(wù)集中的每個(gè)任務(wù)的利用率之和，任務(wù)的利用率的最大值三個(gè)因素進(jìn)行分析。最后通過實(shí)驗(yàn)驗(yàn)證了SFAA算法在節(jié)能方面總是優(yōu)于其它三種算法；同時(shí)在時(shí)間方面總是SFAA耗時(shí)大于其它三種算法，揭示了任務(wù)集的任務(wù)數(shù)、任務(wù)集的利用率和任務(wù)的利用率的最大值對(duì)能耗和耗時(shí)的影響。

關(guān)鍵詞：實(shí)時(shí)系統(tǒng)；節(jié)能；時(shí)間分析 ；多核平臺(tái)

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

Energy Consumption for Real-Time Tasks Under the Multi-Cores Platform

HUANG Yangyang

（School of Computer Science and Technology， Donghua University， Shanghai 201620， China）

Abstract： Single-clock multiprocessor Frequency Assignment Algorithm （SFAA） algorithm is an algorithm for periodic real -time dispatching and scheduling tasks. This article intends to SFAA algorithm and three kinds of common assignment and scheduling algorithm based on 4-core and 8-core platform to compare and analyze such two aspects as energy consumption and time， and the paper mainly focused on the task and the task of utilization analysis from the number of jobs set for each task， the task set of use rate， maximum utilization of the three angles of each task. Finally， experiments verified the SFAA algorithm in energy efficiency is always better than the other three algorithms； and in terms of time always SFAA is larger than the other three algorithms. It reveals the impact of the number of tasks in a set， the total utilization of the tasks and the max utilization of tasks on energy consumption and time consuming under four algorithms.

Key words： Real-time Systems； Energy Efficiency； Time Analysis； Multicore Platform

0 引 言

在近些年，能量管理已經(jīng)成為現(xiàn)實(shí)發(fā)展異常活躍的研究領(lǐng)域。一個(gè)研發(fā)多核處理器的架構(gòu)（Chip Multi-Processors，簡稱CMPs）的重要因素是不可能持續(xù)增長的處理器頻率和傳統(tǒng)單核架構(gòu)的功率密度的趨勢。所以，在多個(gè)操作點(diǎn)的步驟規(guī)劃時(shí)，CMPs即配備了動(dòng)態(tài)電壓和頻率調(diào)節(jié)（Dynamic Voltage and Frequency Scaling）。

處理器的能量消耗主要包括兩部分，也就是動(dòng)態(tài)和靜態(tài)功耗。具體的來說，動(dòng)態(tài)功耗就是切換行為（switch activity）的消耗；靜態(tài)功耗則主要是泄露電流。一種常見的減少動(dòng)態(tài)功耗的方法就是使用動(dòng)態(tài)電壓和頻率調(diào)節(jié)，即DVFS[1]。而一種可以減少靜態(tài)功耗的方法即是當(dāng)處理器空閑的時(shí)候，關(guān)閉多核處理器[2-5]。這樣一種機(jī)制若要實(shí)現(xiàn)，即動(dòng)態(tài)關(guān)閉處理器，就需要硬件支持才可以完成。在實(shí)時(shí)環(huán)境下通過采用DVFS和動(dòng)態(tài)關(guān)閉處理器方式的節(jié)能調(diào)度問題就是要保證所有的實(shí)時(shí)任務(wù)均可到達(dá)截止期，且此過程中能量消耗則要最小。

這些年已經(jīng)有很多論文已經(jīng)針對(duì)基于DVFS的實(shí)時(shí)嵌入式系統(tǒng)的方案可以運(yùn)用在每個(gè)處理器中不同的芯片（chip）的傳統(tǒng)的多處理器平臺(tái)上展開多方研究論證[6]。研究后成果確認(rèn)該問題主要?dú)w結(jié)為兩個(gè)難點(diǎn)：一是任務(wù)的分派，二是運(yùn)行時(shí)在不同處理器上電壓的調(diào)節(jié)[6]。但是新興的CMP平臺(tái)卻因其自身獨(dú)具的一些特性，而使得這一問題和傳統(tǒng)的多處理器平臺(tái)呈現(xiàn)了不同的問題論述。事實(shí)上，多核處理器在商業(yè)的CMPs中是共享同一個(gè)電壓電平的。

眾所周知，在強(qiáng)條件下的多處理器的實(shí)時(shí)調(diào)度分派是一個(gè)NP-hard問題[6]，但是在實(shí)踐中則會(huì)發(fā)現(xiàn)一些簡單且高效的分派啟發(fā)法在多數(shù)情形下卻有著上佳表現(xiàn)[6]。無獨(dú)有偶的是能量消耗最小的任務(wù)的分派問題同樣也是一個(gè)NP-hard[6]問題。最近研究則已表明處理器負(fù)載均衡就能有效降低能量消耗[6]。Worst-Fit-Decrease（WFD）啟發(fā)式算法即可使處理器達(dá)到負(fù)載均衡，從而降低能量消耗。但是負(fù)載平衡卻并非總能降低能量消耗，由此Single-clock multiprocessor Frequency Assignment Algorithm（SFAA）算法隨即形成并已獲提出[6]。

1背景 介紹

1.1Sys-Clock算法

Sys-Clock算法是在一個(gè)應(yīng)用給定的優(yōu)先級(jí)設(shè)計(jì)的調(diào)度策略的系統(tǒng)中，用來計(jì)算在單個(gè)處理器下使得任務(wù)集的每個(gè)任務(wù)都不會(huì)錯(cuò)過截止期的前提下，處理器能夠達(dá)到最小頻率的一個(gè)流程描述。該算法主要利用了一個(gè)處理器的基本性質(zhì)：如果處理器運(yùn)行其工作負(fù)載是在一個(gè)最小的可能的恒定速度下，那么此時(shí)耗費(fèi)的能量最小。但是在一個(gè)系統(tǒng)中使用給定的優(yōu)先級(jí)設(shè)計(jì)的調(diào)度策略時(shí)，工作負(fù)載需要完成的任務(wù)的請(qǐng)求，即包括該任務(wù)本身運(yùn)行時(shí)間和中斷該任務(wù)的高優(yōu)先級(jí)的多個(gè)任務(wù)的運(yùn)行時(shí)間。而且當(dāng)系統(tǒng)中有多個(gè)周期任務(wù)運(yùn)行時(shí)，處理器的空閑區(qū)也不 是均勻分布在任務(wù)的最壞情況下的運(yùn)行區(qū)域（critical zone）。

1.2 Single-clock multiprocessor Frequency Assignment Algorithm（SFAA）算法

能耗值不僅與任務(wù)分派有關(guān)，還和任務(wù)集的調(diào)度策略有關(guān)。由于在RMS調(diào)度下，負(fù)載均衡（load-balancing）不一定總能做到能量最小。針對(duì)這一情況，SFAA提出了一定改進(jìn)，相應(yīng)策略是使用sys-clock算法來完成分派和調(diào)度。WFD啟發(fā)式分派算法在分派時(shí)只考慮了任務(wù)的利用率，而SFAA分派算法除了考慮了任務(wù)的利用率，同時(shí)還一并考慮了任務(wù)的周期的影響。

1.3 Liu and Layland Bound和Hyperbolic Bound算法

2 模擬實(shí)驗(yàn)的系統(tǒng)模型

3 實(shí)驗(yàn)

本文實(shí)現(xiàn)四種算法，分別是：WFD算法，HB算法，Sys算法和SFAA算法。其中，WFD算法，HB算法和Sys算法都是使用WFD啟發(fā)式分派算法來實(shí)現(xiàn)任務(wù)分派，算法中保證任務(wù)集的可調(diào)度性策略分別是LL-Bound，H-Bound，Sys-clock算法。

3.1實(shí)驗(yàn)設(shè)計(jì)

本文的實(shí)驗(yàn)設(shè)計(jì)以文獻(xiàn)[6]為基礎(chǔ)，并在參數(shù)設(shè)置上進(jìn)行了擴(kuò)充。本文為每組實(shí)驗(yàn)隨機(jī)生成1 000個(gè)任務(wù)集，文中每個(gè)任務(wù)的利用率服從均勻分布，在 的區(qū)間上隨機(jī)產(chǎn)生實(shí)時(shí)任務(wù)的利用率。

3.2實(shí)驗(yàn)結(jié)果與分析

處理器個(gè)數(shù)為8，任務(wù)數(shù)為20，任務(wù)的最大利用率為0.3的頻率圖如圖1所示。可以從圖1中看出，增大任務(wù)集的利用率，則8核處理器的整體頻率增大；并將WFD算法和HB算法得到的整體頻率進(jìn)行對(duì)比后，發(fā)現(xiàn)隨著任務(wù)集的利用率的增加，HB算法得到的整體頻率的優(yōu)勢越小；而SFAA算法得到的整體頻率的優(yōu)勢卻越來越大。任務(wù)數(shù)為20，任務(wù)的最大利用率為0.2，處理器為4時(shí)的頻率圖則如圖2所示，與處理器為8時(shí)的情況相同。4種算法得到的整體頻率總是有：

圖1 n=8，m=20，α=0.3時(shí)的頻率圖

Fig.1 Frequency at n=8，m=20，α=0.3

圖2 n = 4，m =20，α=0.2時(shí)的頻率圖

Fig.2 Frequency at n=4，m=20，α=0.2

處理器個(gè)數(shù)為8，任務(wù)數(shù)為20，任務(wù)的最大利用率為0.3的時(shí)間消耗圖如圖3所示。可以從圖3中看出，隨著任務(wù)集的利用率增加，SFAA算法所消耗的時(shí)間最大，然后是Sys算法消耗的次多，HB所消耗時(shí)間則要小于WFD所消耗的時(shí)間，整體看來四種算法所消耗的時(shí)間均呈略降態(tài)勢。任務(wù)數(shù)為20，任務(wù)的最大利用率為0.2，處理器為4的耗時(shí)如圖4所示，不難看出與處理器為8時(shí)的結(jié)論相同。

圖3 n=8，m=20，α=0.3時(shí)耗時(shí)圖

Fig.3 Time consuming at n=8，m=20，α=0.3

圖4 n=4，m=20，α=0.2時(shí)耗時(shí)圖

Fig.4 Time consuming at n=4，m=20，α=0.2

圖5給出了一個(gè)任務(wù)集利用率為2.4，最大利用率為0.1，處理器的個(gè)數(shù)為4的頻率圖。圖6是一個(gè)任務(wù)集利用率為3.2，最大利用率為0.1，處理器的個(gè)數(shù)為8的頻率圖。可以從圖5和圖6看出，當(dāng)任務(wù)集的任務(wù)數(shù)增多時(shí)，四個(gè)算法得到的處理器的整體頻率基本不變。總體看來，HB算法得到的處理器的整體頻率是要低于WFD算法的；Sys算法和SFAA算法進(jìn)行比較，隨著任務(wù)數(shù)增多，二者得到的頻率之差卻未見有太大的變化。SFAA算法得到的整體頻率最低，其次是Sys算法，而后是HB算法，WFD算法得到的整體頻率最大。對(duì)應(yīng)的能量消耗大小有：

EWFD>EHB>ESys>ESFAA 。

圖5 n=4，U=2.4，α=0.1時(shí)的頻率圖

Fig.5 Frequency at n=4，U=2.4，α=0.1

圖6 n=8，U=3.2，α=0.1時(shí)的頻率圖

Fig.6 Frequency at n=8，U=3.2，α=0.1

圖7為對(duì)應(yīng)的時(shí)間圖。可以從圖7中看出隨著任務(wù)集中的任務(wù)數(shù)的增加，WFD算法和HB算法所消耗的時(shí)間基本一樣，其中SFAA算法所消耗的時(shí)間最大，然后是Sys算法消耗的時(shí)間較多，再后即是HB算法和WFD算法。整體看來，4種算法所消耗的時(shí)間均處于增長中。處理器為8的情況如圖8所示，不難看出與處理器為4時(shí)的情況也是一樣。

圖7 n=4，U=2.4，α=0.1時(shí)耗時(shí)圖

Fig.7 Time consuming at n=4，U=2.4，α=0.1

圖8 n=8，U=3.2，α=0.1時(shí)耗時(shí)圖

Fig.8 Time consuming at n=8，U=3.2，α=0.1

圖9為任務(wù)集的利用率為2.4，任務(wù)數(shù)20，處理器的個(gè)數(shù)為4的頻率圖。隨著α的增大，4種算法得到的頻率有所減小。這是因?yàn)殡S著α的增大，任務(wù)集中的任務(wù)的利用率分布更稀疏。而圖10即為任務(wù)集的利用率為2.4，任務(wù)數(shù)20，處理器的個(gè)數(shù)為8的頻率圖，可以看出隨著α的增大，4種算法得到的頻率都是先降后增。頻率先降低是因?yàn)槿蝿?wù)集中任務(wù)的利用率分布越來越稀疏，分到每個(gè)處理器上將更趨平均；后面升高卻是因?yàn)橛袀€(gè)別任務(wù)的利用率太大，導(dǎo)致其它的任務(wù)的利用率分布稠密。4核和8核處理器都可以得出：

。FWFD>FHB>FSys>FSFAA

圖9 n=4，U=2.4，m=20時(shí)的頻率圖

Fig.9 Frequency at n=4，U=2.4，m=20

圖10 n=4，U=2.4，m=20時(shí)的頻率圖

Fig.10 Frequency at n=4，U=2.4，m=20

在耗時(shí)方面，圖11和圖12分別為對(duì)應(yīng)的處理器為4和8的耗時(shí)圖，均可得知SFAA算法所消耗的時(shí)間最大，然后是Sys算法消耗的時(shí)間較多，最后是HB算法和WFD算法。由此結(jié)果可以看出隨著α的增大，Sys算法和SFAA算法都有增加，而WFD算法和HB算法卻基本不發(fā)生變化。

圖11 n=4，U=2.4，m=20時(shí)耗時(shí)圖

Fig.11 Time consuming at n=4，U=2.4，m=20

圖12 n=8，U=2.4，n=20時(shí)處理器時(shí)耗時(shí)圖

Fig.12 Time consuming at n=8，U=2.4，n=20

4結(jié)束語

本文針對(duì)SFAA算法及其它三種算法在多核平臺(tái)下進(jìn)行了能耗和時(shí)間的研究分析。通過研究發(fā)現(xiàn)，四種算法在節(jié)能方面均表現(xiàn)為SFAA算法優(yōu)于Sys算法，Sys算法優(yōu)于HB算法，HB算法優(yōu)于WFD算法，在時(shí)間消耗方面則與上相反。在實(shí)時(shí)系統(tǒng)中，任務(wù)集的利用率越大，能耗就越大；任務(wù)集中的任務(wù)數(shù)對(duì)于能耗并無影響；任務(wù)集中的任務(wù)的利用率的分布，對(duì)于能耗卻是有其具體影響的。相對(duì)于時(shí)間方面，任務(wù)集中的任務(wù)數(shù)越多，四種算法都是耗時(shí)越多；而隨著任務(wù)集的利用率的增大，SFAA算法和Sys算法耗時(shí)減少，WFD算法和HB算法耗時(shí)不變；隨著任務(wù)集中最大利用率的增長，SFAA算法和Sys算法耗時(shí)增加，而WFD算法和HB算法的耗時(shí)只是有所波動(dòng)，但基本保持不變。

參考文獻(xiàn)：

[1] YAO F， DEMERS A， SHENKER S. A schedling model for reduced cpu energy[C]// FOFS 95： Proceedings of the 36th Annual Symposium on Foundations of Computer Science， USA， Washington， DC：IEEE Computer Socitety， 1995：374 .

[2] IRANI S， SHUKLA S， GUPTA R. Algorithms for power saving s. ACM Trans[J]. Alorithms， 2007， 3（4）：41.

[3] LEE Y， REDDY K P， KRISHNA C M. Scheduling techniques for reduing leakage power in hard real-time systems[C]// Euromicro Conference on Real-Time Systems ， Portugal ， Porto：IEEE ， 2003 ：105.

[4] JEJURIKA R， GUPTA R. Procrastination scheduling in fixed priority real-time systems[J]. SIGPLAN Not， 2004，39（7）：57-66.

[5] ROWE A， LAKSHMANAN K， ZHU H， et al. Rate-harmonized scheduling for saving energy[C]// In RTSS08：Proceedings of the 2008 Real-Time Systems Symposium， USA， DC， Washton：IEEE Computer Socitety， 2008：113-122.

[6] KANDHALU A， KIM J. Engery-Aware partition fixed-priority scheduling for chip multi-processors[C]// 2011 IEEE 17th International Conference on Embedded and Real-Time Computing System and Applications， Japan T-oyama：IEEE， 2011，1：93-102