黃陽陽

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

關鍵詞：實時系統(tǒng)；節(jié)能；時間分析 ；多核平臺

中圖分類號：TP311 文獻標識碼：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)實發(fā)展異?；钴S的研究領域。一個研發(fā)多核處理器的架構(gòu)（Chip Multi-Processors，簡稱CMPs）的重要因素是不可能持續(xù)增長的處理器頻率和傳統(tǒng)單核架構(gòu)的功率密度的趨勢。所以，在多個操作點的步驟規(guī)劃時，CMPs即配備了動態(tài)電壓和頻率調(diào)節(jié)（Dynamic Voltage and Frequency Scaling）。

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

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

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

1背景 介紹

1.1Sys-Clock算法

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

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

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

1.3 Liu and Layland Bound和Hyperbolic Bound算法

2 模擬實驗的系統(tǒng)模型

3 實驗

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

3.1實驗設計

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

3.2實驗結(jié)果與分析

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

圖1 n=8，m=20，α=0.3時的頻率圖

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

圖2 n = 4，m =20，α=0.2時的頻率圖

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

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

圖3 n=8，m=20，α=0.3時耗時圖

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

圖4 n=4，m=20，α=0.2時耗時圖

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

圖5給出了一個任務集利用率為2.4，最大利用率為0.1，處理器的個數(shù)為4的頻率圖。圖6是一個任務集利用率為3.2，最大利用率為0.1，處理器的個數(shù)為8的頻率圖?？梢詮膱D5和圖6看出，當任務集的任務數(shù)增多時，四個算法得到的處理器的整體頻率基本不變?？傮w看來，HB算法得到的處理器的整體頻率是要低于WFD算法的；Sys算法和SFAA算法進行比較，隨著任務數(shù)增多，二者得到的頻率之差卻未見有太大的變化。SFAA算法得到的整體頻率最低，其次是Sys算法，而后是HB算法，WFD算法得到的整體頻率最大。對應的能量消耗大小有：

EWFD>EHB>ESys>ESFAA 。

圖5 n=4，U=2.4，α=0.1時的頻率圖

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

圖6 n=8，U=3.2，α=0.1時的頻率圖

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

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

圖7 n=4，U=2.4，α=0.1時耗時圖

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

圖8 n=8，U=3.2，α=0.1時耗時圖

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

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

。FWFD>FHB>FSys>FSFAA

圖9 n=4，U=2.4，m=20時的頻率圖

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

圖10 n=4，U=2.4，m=20時的頻率圖

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

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

圖11 n=4，U=2.4，m=20時耗時圖

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

圖12 n=8，U=2.4，n=20時處理器時耗時圖

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

4結(jié)束語

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

參考文獻：

[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