宮曉利　于海洋　孫承君　李　濤,3　張　金　馬　捷

1(南開大學(xué)計(jì)算機(jī)與控制工程學(xué)院　天津　300071)2(南開大學(xué)軟件學(xué)院　天津　300071)3　　　(計(jì)算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院計(jì)算技術(shù)研究所)　北京　100190)

?

XOS：面向用戶體驗(yàn)質(zhì)量的高能效異構(gòu)多核調(diào)度算法

宮曉利1于海洋2孫承君1李濤1,3張金1馬捷2

1(南開大學(xué)計(jì)算機(jī)與控制工程學(xué)院天津300071)2(南開大學(xué)軟件學(xué)院天津300071)3(計(jì)算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院計(jì)算技術(shù)研究所)北京100190)

(gongxiaoli@nankai.edu.cn)

摘要智能移動(dòng)設(shè)備的重要作用日益凸顯，然而，對(duì)于性能的追求與有限電池容量的矛盾制約了產(chǎn)業(yè)的發(fā)展.異構(gòu)多核處理器架構(gòu)以其平衡性能與能耗的優(yōu)勢(shì)，成為一種新型的解決方案.用戶體驗(yàn)優(yōu)化是智能移動(dòng)設(shè)備的重要設(shè)計(jì)目標(biāo).借助一個(gè)分段式的用戶體驗(yàn)?zāi)Ｐ?，提出了面向異?gòu)多核設(shè)備的XOS(experience oriented scheduler)調(diào)度算法.XOS能夠跨層獲取任務(wù)信息，識(shí)別與用戶直接交互的任務(wù)組，保證這些任務(wù)的計(jì)算資源分配以保障用戶體驗(yàn),同時(shí)限制非交互性任務(wù)的計(jì)算資源以降低能耗.通過建立一套仿真系統(tǒng)驗(yàn)證了算法的有效性并進(jìn)行了調(diào)整優(yōu)化，然后在Odroid-XU3開發(fā)板Android系統(tǒng)中進(jìn)行了原型實(shí)現(xiàn)和驗(yàn)證.實(shí)驗(yàn)結(jié)果表明：XOS算法對(duì)于不同類型的任務(wù)僅產(chǎn)生了2.7%～7.3%的用戶體驗(yàn)下降，但節(jié)省了8%～48%的能量.

關(guān)鍵詞智能移動(dòng)設(shè)備；異構(gòu)多核處理器；體驗(yàn)質(zhì)量；能耗優(yōu)化；調(diào)度機(jī)制；跨層信息

智能移動(dòng)設(shè)備的產(chǎn)業(yè)生態(tài)正在迅速發(fā)展，智能手機(jī)、平板電腦等在日常生活中的地位日益增長(zhǎng).各類在線應(yīng)用商店中移動(dòng)應(yīng)用軟件數(shù)量巨大，吸引著用戶投入大量的時(shí)間與金錢，從而為設(shè)備制造商與軟件開發(fā)人員提供了廣闊的市場(chǎng)空間，進(jìn)而推動(dòng)了軟硬件產(chǎn)品的更新?lián)Q代，繁榮的市場(chǎng)吸引了更多的用戶.這種相互促進(jìn)的方式使得智能移動(dòng)設(shè)備相關(guān)技術(shù)飛速進(jìn)步.然而，電池容量與能量消耗問題已然成為制約其發(fā)展的瓶頸.為此，許多硬件解決方案與軟件管理策略不斷涌現(xiàn).

異構(gòu)多核處理器架構(gòu)以其平衡性能與能耗的優(yōu)勢(shì)，成為該領(lǐng)域的一個(gè)研究熱點(diǎn)[1-5].在智能移動(dòng)設(shè)備系統(tǒng)中，多種軟件任務(wù)并存，例如計(jì)算型任務(wù)(如游戲、圖片處理等)和IO型任務(wù)(如GPS導(dǎo)航等)等.不同類型的任務(wù)對(duì)性能和能耗的需求存在巨大的差異，傳統(tǒng)處理器架構(gòu)難以同時(shí)滿足.在異構(gòu)多核架構(gòu)中，多種不同類型的核心集成在一個(gè)芯片中以應(yīng)對(duì)多樣化的需求.在本文后續(xù)描述中，將高性能高能耗的核心稱之為大核，而低性能低能耗的核心則稱之為小核.

智能移動(dòng)設(shè)備領(lǐng)域使用的異構(gòu)多核架構(gòu)主要有2種:1)大核與小核在芯片的資源分配上存在較大差異，小核主要作為輔助控制器使用，從低速外設(shè)中收集信息并與大核進(jìn)行數(shù)據(jù)交換[6].這種方案雖然具有高能效的優(yōu)點(diǎn)，但對(duì)開發(fā)人員的編程技能要求較高.2)ARM上實(shí)現(xiàn)的big．LITTLE[7]架構(gòu)，big．LITTLE使用相似的頻率和相同的指令集以及同步的緩存機(jī)制，使得多核心編程開發(fā)更為簡(jiǎn)化，成為產(chǎn)業(yè)與科研的熱點(diǎn).IKS(in kernel switcher)與GTS(global task scheduling)是big．LITTLE架構(gòu)上典型的多核調(diào)度算法.IKS與GTS均以任務(wù)負(fù)載為調(diào)度基準(zhǔn)，使低負(fù)載任務(wù)運(yùn)行于小核上，高負(fù)載任務(wù)運(yùn)行于大核上.這種方法使得系統(tǒng)能夠充分發(fā)揮異構(gòu)多核架構(gòu)的優(yōu)勢(shì)，達(dá)到降低能耗的效果.

智能移動(dòng)設(shè)備作為一種用戶交互驅(qū)動(dòng)的設(shè)備，用戶體驗(yàn)質(zhì)量(quality of experience, QoE)是一個(gè)重要的設(shè)計(jì)指標(biāo)，因此需要在能耗約束和用戶體驗(yàn)之間尋求平衡.根據(jù)對(duì)于三星Exynos 5422 異構(gòu)多核處理器的測(cè)試，大核擁有大約相當(dāng)于小核3倍的處理速度，卻需產(chǎn)生接近后者十倍的能耗.小核的性能已經(jīng)能夠滿足部分任務(wù)的需求，而部分任務(wù)在大核上也無法產(chǎn)生相應(yīng)的用戶體驗(yàn)提升卻消耗了大量能量.因此，需要針對(duì)不同任務(wù)的特性設(shè)計(jì)調(diào)度機(jī)制以獲取最佳性能能耗比.

在傳統(tǒng)的異構(gòu)多核調(diào)度算法中，基于任務(wù)周期性的歷史運(yùn)行負(fù)載信息[8-9]對(duì)任務(wù)進(jìn)行大小核之間的遷移.然而在現(xiàn)代智能移動(dòng)設(shè)備中，大多數(shù)任務(wù)能夠在很短的時(shí)間內(nèi)完成，這使得難以進(jìn)行精確的任務(wù)負(fù)載追蹤.同時(shí)，線程池機(jī)制的大量使用使得同一線程執(zhí)行的多段代碼之間缺少必然的邏輯關(guān)系，這增加了負(fù)載追蹤的復(fù)雜度.

為了解決以上問題，本文提出了XOS(experience oriented scheduler)異構(gòu)多核調(diào)度算法，基于跨層信息，在保障用戶體驗(yàn)質(zhì)量的同時(shí)提高能效.該調(diào)度算法實(shí)現(xiàn)了3個(gè)目標(biāo)：

1) 確保用戶體驗(yàn)質(zhì)量;

2) 改進(jìn)能量利用效率;

3) 避免給程序開發(fā)人員帶來巨大的編程負(fù)擔(dān).

1相關(guān)技術(shù)介紹

1.1智能移動(dòng)設(shè)備中的任務(wù)

智能移動(dòng)設(shè)備多采用現(xiàn)代化的多任務(wù)操作系統(tǒng)，可以支持多進(jìn)程、多線程的運(yùn)行環(huán)境.設(shè)備中并發(fā)運(yùn)行著多種不同類型的任務(wù).依據(jù)與用戶直接交互形式的差異，本文中將任務(wù)分為3類：

1) 后臺(tái)任務(wù).后臺(tái)任務(wù)是指處于等待外部設(shè)備數(shù)據(jù)狀態(tài)的服務(wù)任務(wù)，包括檢測(cè)信號(hào)強(qiáng)度、電量、統(tǒng)計(jì)存儲(chǔ)用量等，或是由用戶人工置于后臺(tái)的任務(wù).用戶通常不等待這些任務(wù)運(yùn)行的直接結(jié)果，因而用戶體驗(yàn)很少受到此類任務(wù)的影響.

2) 強(qiáng)交互任務(wù).強(qiáng)交互任務(wù)與用戶的主觀體驗(yàn)直接相關(guān)，如3D游戲、網(wǎng)頁渲染等.用戶通常直接等待此類任務(wù)產(chǎn)生的反饋結(jié)果，任務(wù)的響應(yīng)時(shí)間會(huì)對(duì)用戶體驗(yàn)質(zhì)量產(chǎn)生明顯影響.因此，需向此類任務(wù)分配更多的計(jì)算資源以加速其執(zhí)行.

3) 輕交互任務(wù).此類任務(wù)交互頻率較低、間隔長(zhǎng)，因而有足夠的時(shí)間完成計(jì)算任務(wù)；或者是任務(wù)本身資源占用比較少，能夠在很短時(shí)間內(nèi)完成，例如文本輸入、圖標(biāo)選擇等.對(duì)于輕交互任務(wù)，存在某個(gè)特定的任務(wù)執(zhí)行時(shí)間閾值，只要任務(wù)能夠在這個(gè)時(shí)間內(nèi)完成，用戶體驗(yàn)將不會(huì)受到執(zhí)行時(shí)間的影響.例如，如果文字輸入軟件的處理速度與用戶的反應(yīng)速度相當(dāng)，軟件響應(yīng)快于用戶輸入速度并不會(huì)帶來更好的用戶體驗(yàn).

顯而易見，為了降低能耗，后臺(tái)任務(wù)應(yīng)該被分配到小核執(zhí)行；同時(shí)，強(qiáng)交互性任務(wù)應(yīng)該分配到大核執(zhí)行以提高用戶體驗(yàn)質(zhì)量.本文聚焦于輕交互任務(wù)的調(diào)度，這些任務(wù)如果調(diào)度合理，就能夠在不影響用戶體驗(yàn)質(zhì)量的前提下降低能耗.輕交互任務(wù)又可以細(xì)分為長(zhǎng)任務(wù)和短任務(wù).短任務(wù)是指能夠在幾百毫秒內(nèi)完成的任務(wù)，例如文字輸入、按鈕點(diǎn)擊等；長(zhǎng)任務(wù)則是需要幾秒甚至更長(zhǎng)的時(shí)間才能完成的任務(wù).在后文中會(huì)分別對(duì)這2類任務(wù)進(jìn)行處理.

1.2IKS與GTS調(diào)度算法

IKS是big．LITTLE上的第1代調(diào)度算法，其本質(zhì)為利用內(nèi)核中DVFS(動(dòng)態(tài)電壓頻率調(diào)整)來實(shí)現(xiàn)計(jì)算資源的管理.在該算法中，一個(gè)大核與一個(gè)小核被分為一組.同一組中，只能有一個(gè)核心處于開啟狀態(tài)，調(diào)度器依據(jù)DVFS中對(duì)頻率的設(shè)定控制核心的工作狀態(tài)和工作頻率.IKS可以保持對(duì)Linux內(nèi)核中原有同構(gòu)多核調(diào)度算法的兼容，但是由于同一組中2個(gè)核心不能同時(shí)開啟，所以IKS并不能充分利用異構(gòu)多核架構(gòu)的計(jì)算資源.

GTS是針對(duì)big．LITTLE架構(gòu)而專門設(shè)計(jì)的多核調(diào)度算法[10].GTS算法根據(jù)任務(wù)負(fù)載進(jìn)行任務(wù)調(diào)度.如圖1所示，CPU中所有的大核為一簇，所有的小核為一簇.任務(wù)首先被分配至大核簇，如果此后任務(wù)的負(fù)載低于大核簇的遷移臨界值，則任務(wù)會(huì)被遷移至小核簇；同理，如果任務(wù)運(yùn)行于小核簇，而其負(fù)載高于小核簇的遷移臨界值，則任務(wù)會(huì)遷移至大核簇.如果大核簇上沒有任務(wù)運(yùn)行，那么大核簇將完全關(guān)閉以降低能耗.但是由于小核簇至少包含一個(gè)CPU用于運(yùn)行操作系統(tǒng)，所以小核簇會(huì)一直處于開啟狀態(tài).

Fig. 1　The GTS model.圖1　GTS模型

相比于IKS，GTS能夠同時(shí)開啟所有的核心，充分利用異構(gòu)多核CPU的計(jì)算資源.然而，GTS僅以任務(wù)負(fù)載作為任務(wù)遷移的依據(jù)，并沒有針對(duì)移動(dòng)任務(wù)的特征和用戶體驗(yàn)的需求進(jìn)行優(yōu)化.

1.3QoE用戶體驗(yàn)質(zhì)量

用戶體驗(yàn)質(zhì)量QoE是指用戶對(duì)于服務(wù)體驗(yàn)的主觀感受，用于描述業(yè)務(wù)應(yīng)用的舒適程度.QoE是一個(gè)復(fù)雜的主觀指標(biāo)，對(duì)其進(jìn)行量化描述十分困難.有的研究者試圖利用一些客觀因素來量化QoE，例如執(zhí)行時(shí)間、資源消耗等.但是這些因素并不能直接刻畫用戶體驗(yàn)質(zhì)量.另一種常用的量化方法是基于用戶主觀感知的打分法，例如國際電信聯(lián)盟(Inter-national Telecommunication Union, ITU)提出的一種在廣播、游戲與電視換臺(tái)過程中用戶體驗(yàn)質(zhì)量與響應(yīng)時(shí)間的關(guān)系模型[11].該模型使用平均主觀意見分(mean opinion score,MOS)進(jìn)行度量.MOS通常用五分制來表示，數(shù)值從1(最差)到5(最好)表示不同的用戶體驗(yàn).其研究結(jié)果表明，用戶體驗(yàn)質(zhì)量的MOS是一個(gè)復(fù)雜的函數(shù)，電視換臺(tái)體驗(yàn)的MOS與響應(yīng)時(shí)間的關(guān)系[11]：

MOS=max(min(-1.02 ln(Time),5),1).

(1)

為了簡(jiǎn)單起見，本文將用戶體驗(yàn)質(zhì)量分為3段：高用戶體驗(yàn)部分(good QoE)、低用戶體驗(yàn)部分(bad QoE)以及介于兩者之間的連續(xù)變化部分，如圖2所示.根據(jù)ITU研究結(jié)果，如果響應(yīng)時(shí)間過短或過長(zhǎng)，那么響應(yīng)時(shí)間的變化對(duì)用戶體驗(yàn)質(zhì)量不會(huì)產(chǎn)生顯著影響.換言之，處于高用戶體驗(yàn)區(qū)或低用戶體驗(yàn)區(qū)的部分任務(wù)，可以在不影響其用戶體驗(yàn)質(zhì)量的前提下降低其性能，以達(dá)到降低系統(tǒng)能耗的效果.這是XOS調(diào)度算法建立的基礎(chǔ).

Fig. 2　MOS for response time.圖2　響應(yīng)時(shí)間與MOS折線圖

2XOS算法設(shè)計(jì)

2.1調(diào)度原則

XOS調(diào)度算法將兼顧能耗與用戶體驗(yàn)質(zhì)量.為此，算法的設(shè)計(jì)滿足6個(gè)原則：

① 出于降低能耗的考慮，任務(wù)初始化于小核；

② 算法能夠識(shí)別輕交互任務(wù)，當(dāng)任務(wù)在小核上執(zhí)行時(shí)間過長(zhǎng)時(shí)，為避免QoE 出現(xiàn)損失，提前將任務(wù)遷移至大核；

③ 如果任務(wù)運(yùn)行于大核而用戶體驗(yàn)質(zhì)量仍未能得到改進(jìn)，那么此時(shí)應(yīng)該以降低能耗為首要目標(biāo)，將其遷至小核；

④ 交互事件完成之后，任務(wù)應(yīng)該立即回到小核上以減少能耗；

⑤ 傳統(tǒng)的同構(gòu)多核調(diào)度算法中對(duì)于同類核心的管理代碼應(yīng)該加以利用；

⑥ 不應(yīng)該給應(yīng)用開發(fā)人員帶來額外的編程負(fù)擔(dān)，避免開發(fā)復(fù)雜化.

2.2調(diào)度模型

根據(jù)調(diào)度算法的設(shè)計(jì)原則，本文提出了面向QoE的XOS調(diào)度算法模型.XOS通過獲取交互事件開始及結(jié)束的信息識(shí)別交互性任務(wù)及其運(yùn)行狀態(tài)的變化，并根據(jù)大小核的差異決定任務(wù)是否需要在大小核之間遷移.在本文中，一次交互指的是一次用戶的操作，能夠觸發(fā)一次有意義的應(yīng)用功能，例如從圖庫中選擇一張圖片或發(fā)送一個(gè)信息等.

圖3展示了一個(gè)交互任務(wù)的調(diào)度模型：

Fig. 3　The XOS scheduling model.圖3　XOS算法模型

一個(gè)任務(wù)接受了用戶的交互操作，或與交互任務(wù)建立依賴關(guān)系后開始進(jìn)入交互狀態(tài).根據(jù)調(diào)度模型，一個(gè)交互任務(wù)的完整調(diào)度流程分為4個(gè)步驟：

Step1. 任務(wù)在小核上創(chuàng)建并初始化.考慮到小核性能已經(jīng)足夠滿足許多任務(wù)的需求，因而出于降低能耗的目的，每個(gè)任務(wù)均在小核上完成初始化工作.

Step2. 任務(wù)運(yùn)行于小核.如果交互任務(wù)能夠在短時(shí)間內(nèi)完成(t

Step3. 任務(wù)遷移至大核運(yùn)行.Tswitchup被設(shè)置為任務(wù)從小核遷移至大核的時(shí)間臨界點(diǎn).即如果任務(wù)不能夠在Tswitchup時(shí)間內(nèi)完成，這表明若任務(wù)繼續(xù)停留在小核，則QoE將開始顯著下降，那么此時(shí)任務(wù)需要被遷移至大核以保證用戶體驗(yàn)質(zhì)量.

Step4. 任務(wù)從大核遷移回小核運(yùn)行.Tswitchdown被設(shè)置為任務(wù)從大核遷回至小核的時(shí)間臨界點(diǎn).如果任務(wù)在Tswitchdown的時(shí)間內(nèi)沒有完成，這表示此任務(wù)給用戶帶來的體驗(yàn)已經(jīng)很低，此時(shí)即使加速此任務(wù)，用戶體驗(yàn)質(zhì)量也無法改進(jìn).因此，該任務(wù)將會(huì)被遷回至小核執(zhí)行，以降低能耗.

另外，如果交互任務(wù)執(zhí)行結(jié)束或者被轉(zhuǎn)移至后臺(tái)使得其不再處于交互狀態(tài)，則無論任務(wù)此時(shí)運(yùn)行于何種核心，都會(huì)遷移到小核上運(yùn)行以節(jié)省能耗.

以上是任務(wù)在大小核之間遷移的基本流程.在大核簇與小核簇的內(nèi)部，仍舊按照傳統(tǒng)同構(gòu)多核調(diào)度算法的規(guī)則進(jìn)行內(nèi)部調(diào)度，充分發(fā)揮處理器性能.

2.3交互事件信息

應(yīng)用程序內(nèi)部的上下文語義信息在到達(dá)操作系統(tǒng)內(nèi)核前就已丟失，因而交互行為很難被操作系統(tǒng)自動(dòng)檢測(cè).因此，本文將引入一種跨層通信機(jī)制收集應(yīng)用層信息并將其直接傳遞給調(diào)度器.

交互的開始與結(jié)束是基于程序的功能設(shè)計(jì)的，是具有上下文語義的，不能簡(jiǎn)單地以其是否占據(jù)前臺(tái)或者是否有內(nèi)容變化為條件進(jìn)行判斷.交互的形式可以是一個(gè)簡(jiǎn)單的信息提示，也可以是多種處理與復(fù)雜功能回調(diào)的綜合反饋.因此，本文提出了一個(gè)UI檢測(cè)輔助框架，應(yīng)用開發(fā)人員可以很容易地使用此框架在代碼中標(biāo)注交互事件的開始與結(jié)束.框架中為每個(gè)交互事件賦予獨(dú)立的ID，并在運(yùn)行時(shí)將事件的開始和結(jié)束標(biāo)志傳遞到調(diào)度器中，同時(shí)，程序前后臺(tái)切換與屏幕關(guān)閉等信息也會(huì)被傳遞到調(diào)度器.

當(dāng)一個(gè)處于交互事件中的任務(wù)被調(diào)度時(shí)，所有被此任務(wù)調(diào)用而產(chǎn)生依賴關(guān)系的任務(wù)都應(yīng)被當(dāng)作交互任務(wù)對(duì)待.因此，XOS算法中包含一個(gè)任務(wù)依賴關(guān)系檢測(cè)機(jī)制.當(dāng)應(yīng)用程序中任務(wù)之間發(fā)生依賴關(guān)系時(shí)，依賴關(guān)系信息將被發(fā)送至調(diào)度器.XOS會(huì)根據(jù)應(yīng)用層的運(yùn)行信息，建立一個(gè)任務(wù)依賴關(guān)系樹.在任務(wù)遷移的過程中，依賴關(guān)系樹中所有的任務(wù)會(huì)綁定為一個(gè)整體，依據(jù)根結(jié)點(diǎn)的屬性進(jìn)行遷移判斷.

由于跨層獲取信息需要程序開發(fā)人員在程序源代碼中添加支持代碼，為了減少開發(fā)人員的工作量，本文將跨層通信機(jī)制所需的代碼編寫為庫文件供應(yīng)用開發(fā)人員直接調(diào)用.

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

3.1仿真程序設(shè)計(jì)

為了驗(yàn)證XOS調(diào)度算法的有效性，并確定2.2節(jié)提到的2個(gè)時(shí)間臨界點(diǎn)Tswitchup與Tswitchdown，首先采用程序模擬調(diào)度的方式進(jìn)行仿真實(shí)驗(yàn).在仿真實(shí)驗(yàn)中，同時(shí)實(shí)現(xiàn)了GTS算法和XOS算法的調(diào)度邏輯，并通過模擬對(duì)2種算法的性能進(jìn)行比較.

仿真實(shí)驗(yàn)程序用JAVA語言編程，圖4為其程序類圖.程序中使用一個(gè)線程(SimulationThread)的一次循環(huán)執(zhí)行代表內(nèi)核時(shí)間片的一次運(yùn)轉(zhuǎn).使用任務(wù)實(shí)體類(TaskEntity)來代表任務(wù)，并細(xì)分為短任務(wù)類(ShortTask)與長(zhǎng)任務(wù)類(LongTask)，所有的任務(wù)會(huì)存放于任務(wù)對(duì)象池(TaskObjectPool)數(shù)據(jù)結(jié)構(gòu)中.任務(wù)以及任務(wù)對(duì)象池在仿真初始化時(shí)產(chǎn)生.仿真線程由任務(wù)實(shí)體類對(duì)象與調(diào)度算法類對(duì)象(GTS，XOS)組成，并在一次循環(huán)過程中分別按照GTS與XOS算法對(duì)這些任務(wù)對(duì)象進(jìn)行模擬調(diào)度，并分別記錄2種算法對(duì)于任務(wù)的執(zhí)行結(jié)果.

Fig. 4　The class diagram of the simulation problem.圖4　仿真實(shí)驗(yàn)程序類圖

每個(gè)任務(wù)都有啟動(dòng)時(shí)間、持續(xù)時(shí)間、任務(wù)負(fù)載等屬性，這些屬性都是在仿真實(shí)驗(yàn)開始時(shí)隨機(jī)生成，并且，短任務(wù)與長(zhǎng)任務(wù)的持續(xù)時(shí)間有明顯的差異.

3.2仿真參數(shù)設(shè)置

在仿真實(shí)驗(yàn)中需要配置一些實(shí)驗(yàn)參數(shù)，例如真實(shí)環(huán)境中的硬件性能參數(shù)、能耗參數(shù)等.這些參數(shù)對(duì)于仿真實(shí)驗(yàn)的有效性至關(guān)重要.

1) 能耗參數(shù)設(shè)置

本文實(shí)驗(yàn)中使用了Odroid-XU3開發(fā)板，其CPU為三星Exynos 5422，包含4個(gè)Cortex-A15核心與4個(gè)Cortex-A7核心，組成big．LITTLE架構(gòu).開發(fā)板上附帶了4個(gè)能耗傳感器，能夠?qū)崟r(shí)監(jiān)測(cè)大核簇、小核簇、GPU和內(nèi)存的能耗信息.本文使用簡(jiǎn)單的循環(huán)計(jì)算程序?qū)PU進(jìn)行能耗測(cè)試，同時(shí)，使用一個(gè)循環(huán)線程來讀取能耗傳感器的值.通過測(cè)量，小核單個(gè)核心在滿負(fù)載狀態(tài)下的能耗為180 mW，大核為1 555 mW.另外，當(dāng)小核簇或者大核簇在開啟時(shí)會(huì)產(chǎn)生基礎(chǔ)能耗，小核簇的基礎(chǔ)能耗為282 mW，大核簇的基礎(chǔ)能耗為1 013 mW.最后，通過測(cè)試不同核心對(duì)SysBench[12]指標(biāo)程序執(zhí)行時(shí)間長(zhǎng)短的不同，得到大核與小核的計(jì)算性能比為2.5∶1.以上信息將作為基本參數(shù)用于模擬實(shí)驗(yàn).

2) 遷移臨界設(shè)置

根據(jù)ITU的研究報(bào)告[11]，任務(wù)的MOS值超過3.5即可計(jì)為用戶體驗(yàn)優(yōu)良狀態(tài)，按式(1)即為任務(wù)的響應(yīng)時(shí)間控制在430 ms之內(nèi).所以在仿真實(shí)驗(yàn)中選擇430 ms作為任務(wù)從小核遷移到大核的臨界點(diǎn).

根據(jù)Agawi[13]的測(cè)試結(jié)果，智能移動(dòng)設(shè)備的屏幕響應(yīng)時(shí)間大約在100～130 ms之間.程序可用的運(yùn)行時(shí)間應(yīng)減去設(shè)備的響應(yīng)時(shí)間，因此設(shè)置Tswitchup=300 ms.同時(shí)，根據(jù)式(1)，設(shè)置Tswitchdown=5 s.

3) 任務(wù)集合設(shè)置

仿真實(shí)驗(yàn)設(shè)計(jì)了長(zhǎng)任務(wù)集合與短任務(wù)集合.每個(gè)集合內(nèi)各自包含500個(gè)隨機(jī)任務(wù).短任務(wù)的持續(xù)時(shí)間在300 ms之內(nèi)隨機(jī)選擇，長(zhǎng)任務(wù)的持續(xù)時(shí)間隨機(jī)分布在5～40 s之間.任務(wù)的CPU負(fù)載設(shè)置為1%～100%之間的隨機(jī)值.這里的時(shí)間值、負(fù)載值都是任務(wù)在小核上運(yùn)行時(shí)的數(shù)值，如果任務(wù)切換到大核上，那么這些值將按照大小核的計(jì)算性能比例，依據(jù)Amdahl定律進(jìn)行轉(zhuǎn)換.通過隨機(jī)設(shè)置啟動(dòng)時(shí)間，確保同一時(shí)間只有1～3個(gè)任務(wù)在進(jìn)行仿真調(diào)度.

3.3仿真結(jié)果

1) XOS調(diào)度模型改進(jìn)

通過對(duì)仿真實(shí)驗(yàn)數(shù)據(jù)的分析發(fā)現(xiàn)，在簡(jiǎn)單短任務(wù)調(diào)度的能效方面XOS比GTS具有明顯優(yōu)勢(shì)，但隨著任務(wù)在大核上執(zhí)行時(shí)間的增長(zhǎng)，XOS算法能耗快速增加.由于交互任務(wù)一直運(yùn)行于大核，超過特定時(shí)間點(diǎn)后，XOS算法的能效開始低于GTS.此后，使用GTS算法能夠獲得更好的能量利用率.

基于該方面的考慮，本文選擇一定的時(shí)間之后使用GTS算法的調(diào)度邏輯來調(diào)度任務(wù)，以獲取更優(yōu)的能效.即在原有的2個(gè)時(shí)間點(diǎn)Tswitchup與Tswitchdown之間，加入一個(gè)時(shí)間點(diǎn)TswitchtoGTS.圖5展示的是加入TswitchtoGTS時(shí)間點(diǎn)之后的調(diào)度模型.如果一個(gè)任務(wù)在遷移到大核并且執(zhí)行時(shí)間達(dá)到TswitchtoGTS之后，仍舊沒有完成，那么它將會(huì)遵循GTS的調(diào)度原則進(jìn)行調(diào)度.如果它在達(dá)到Tswitchdown時(shí)間點(diǎn)之后仍然沒有完成，那么它將會(huì)按照XOS算法的調(diào)度原則強(qiáng)制遷移至小核.

Fig. 5　The improved XOS schedule model.圖5　改進(jìn)的XOS模型

Fig. 6　The result of the experiment without Tswitchdown.圖6　去掉Tswitchdown之后的實(shí)驗(yàn)仿真結(jié)果

本文設(shè)計(jì)了一個(gè)實(shí)驗(yàn)以尋找GTS與XOS兩種算法的時(shí)間臨界點(diǎn)TswitchtoGTS.實(shí)驗(yàn)設(shè)置如下：首先取消Tswitchdown，即如果任務(wù)從小核遷移至大核，那么它將一直運(yùn)行于大核直到完成.按照任務(wù)持續(xù)時(shí)間的不同設(shè)置了9類任務(wù)集合，任務(wù)的持續(xù)時(shí)間從1 100 ms到1 500 ms遞增,每類任務(wù)的持續(xù)時(shí)間增加50 ms，第1類任務(wù)的任務(wù)持續(xù)時(shí)間為1 100 ms，第9類任務(wù)集合的任務(wù)持續(xù)時(shí)間為1 500 ms.分別使用2種算法的調(diào)度邏輯調(diào)度這些任務(wù)，得到的實(shí)驗(yàn)結(jié)果如圖6所示.由圖6可知，如果任務(wù)的響應(yīng)時(shí)間超過1 400 ms，那么XOS算法的能耗將會(huì)趕超GTS算法.因此，在后續(xù)仿真實(shí)驗(yàn)中將TswitchtoGTS設(shè)定為1 400 ms.

2) 仿真結(jié)果分析

Fig. 7　The result of short tasks simulation.圖7　仿真實(shí)驗(yàn)短任務(wù)能耗結(jié)果

圖7與圖8分別為短任務(wù)集合與長(zhǎng)任務(wù)集合的仿真實(shí)驗(yàn)結(jié)果.表1為任務(wù)集合的QoE統(tǒng)計(jì)結(jié)果, 包含用戶體驗(yàn)優(yōu)良(MOS≥3.5)的任務(wù)數(shù)量，以及所有任務(wù)根據(jù)式(1)計(jì)算出的用戶體驗(yàn)MOS值的總和.如圖7所示，XOS算法應(yīng)用于短任務(wù)集合的能耗低于GTS算法，而且2種算法得到的用戶體驗(yàn)優(yōu)良的任務(wù)數(shù)量均為500.因此，XOS使得短任務(wù)的能耗降低了42.9%，雖然總用戶體驗(yàn)MOS值略微降低，但是每個(gè)任務(wù)的用戶體驗(yàn)仍處于優(yōu)良.圖8表明長(zhǎng)任務(wù)的總體能耗降低了14.7%.而從表1可得，由于長(zhǎng)任務(wù)的用戶體驗(yàn)MOS值不高，XOS沒有產(chǎn)生明顯的用戶體驗(yàn)質(zhì)量損失.總體而言，XOS算法能夠在整體用戶體驗(yàn)質(zhì)量變化不大的情況下獲得系統(tǒng)能耗的明顯降低.

Fig. 8　The result of long tasks simulation.圖8　仿真實(shí)驗(yàn)長(zhǎng)任務(wù)能耗結(jié)果

AlgorithmMOS≥3.5MOSSumShortTasksLongTasksShortTasksLongTasksGTS50002467315XOS50002272313

4XOS算法實(shí)現(xiàn)

本文在hardkernel發(fā)布的Linux-odroidxu3-3.10.y-android的基礎(chǔ)上實(shí)現(xiàn)了XOS調(diào)度算法，并將其部署運(yùn)行在相應(yīng)的Odroid-XU3開發(fā)板上進(jìn)行驗(yàn)證.按照模擬仿真實(shí)驗(yàn)的結(jié)果，XOS中還保持了GTS算法的調(diào)度邏輯并在特定的條件下被激活，因此，該調(diào)度算法在GTS的數(shù)據(jù)結(jié)構(gòu)和代碼邏輯基礎(chǔ)上擴(kuò)展實(shí)現(xiàn).

1) 算法的內(nèi)核實(shí)現(xiàn)

在數(shù)據(jù)存儲(chǔ)上，擴(kuò)展task_struct中的數(shù)據(jù)結(jié)構(gòu)sched_avg，加入對(duì)進(jìn)程的交互狀態(tài)(qoe_in_interaction_process)、交互開始時(shí)間(qoe_interaction_start_time_jiffies)、大小核切換時(shí)間(qoe_switch_to_highprocess_for_performance，qoe_switch_to_lowprocess_for_saving) 等信息的存儲(chǔ)，并在相應(yīng)的時(shí)機(jī)進(jìn)行更新.

在執(zhí)行邏輯上，借助GTS對(duì)遷移條件檢查的時(shí)間點(diǎn)對(duì)QoE和交互狀態(tài)進(jìn)行檢查，并完成任務(wù)的核心遷移.在GTS算法中一共有5個(gè)遷移點(diǎn)，在內(nèi)核源代碼中分別實(shí)現(xiàn)為select_task_rq_fair，run_rebalance_domains，hmp_force_up_migration，hmp_idle_pull，hmp_offload_down.每個(gè)任務(wù)的負(fù)載在__update_task_entity_contrib中定期更新,并檢查是否需要觸發(fā)任務(wù)遷移事件.在遷移時(shí)，任務(wù)會(huì)被hmp_up_migration與hmp_down_migration加以評(píng)估，以決定一個(gè)任務(wù)是否繼續(xù)在原有的核上運(yùn)行.

借用GTS的接口，在每次任務(wù)負(fù)載更新函數(shù)__update_task_entity_contrib被調(diào)用時(shí)，XOS檢查任務(wù)的交互狀態(tài)和在當(dāng)前核心上的運(yùn)行時(shí)間，以決定是否需要觸發(fā)遷移以及遷移的方向.類似地，在其他4個(gè)遷移點(diǎn)，XOS也需要判斷遷移條件和方向.此部分邏輯在每次確定遷移方向前都被調(diào)用，因此在內(nèi)核中被實(shí)現(xiàn)為一個(gè)內(nèi)聯(lián)函數(shù)should_stay_low_cpu.同時(shí)，在遷移條件的檢查點(diǎn)也需要確認(rèn)任務(wù)在大核上的運(yùn)行時(shí)間和交互狀態(tài)，以確定是否應(yīng)該使用GTS調(diào)度算法，該內(nèi)聯(lián)函數(shù)實(shí)現(xiàn)為should_follow_gts.為了保證GTS算法在接管調(diào)度器時(shí)能夠正確地計(jì)量任務(wù)的負(fù)載，所有GTS算法相關(guān)的數(shù)據(jù)結(jié)構(gòu)和屬性更新均保持原有執(zhí)行邏輯，不受XOS算法的影響.

任務(wù)的交互狀態(tài)信息由應(yīng)用程序借助sysfs接口傳遞給內(nèi)核.調(diào)度器通過在sysfs中注冊(cè)一些屬性文件實(shí)現(xiàn)與用戶空間的交互，其中move_foreground與move_background用于向內(nèi)核傳遞任務(wù)的狀態(tài)變化，由交互任務(wù)向文件中寫入對(duì)應(yīng)的任務(wù)號(hào)即可通知內(nèi)核改變其交互狀態(tài).對(duì)于任務(wù)依賴關(guān)系，則通過attached_to_foreground，detached_from_foreground兩個(gè)接口獲得.被前臺(tái)任務(wù)調(diào)用的任務(wù)，將其調(diào)用者的任務(wù)號(hào)寫入相應(yīng)接口即可通知調(diào)度器.

任務(wù)間的依賴關(guān)系在內(nèi)核中以樹的形式記錄.每個(gè)任務(wù)的task_struct數(shù)據(jù)結(jié)構(gòu)中加入變量qoe_attached_to_process.如果任務(wù)沒有依賴關(guān)系，那么這個(gè)任務(wù)的依賴樹就是一棵只有根節(jié)點(diǎn)的樹，該變量中保存的是該任務(wù)自已的任務(wù)號(hào).當(dāng)任務(wù)產(chǎn)生依賴時(shí)，被調(diào)用者記錄了調(diào)用者的任務(wù)號(hào)，形成一個(gè)以父節(jié)點(diǎn)形式存儲(chǔ)的樹狀結(jié)構(gòu).在進(jìn)行遷移條件檢查時(shí)，如果發(fā)現(xiàn)任務(wù)存在對(duì)其他任務(wù)的依賴，則沿著該組任務(wù)的qoe_attached_to_process尋找到這個(gè)依賴樹的樹根，并以根任務(wù)的屬性進(jìn)行遷移條件判斷.

2) 跨層類庫實(shí)現(xiàn)

為了減少應(yīng)用開發(fā)人員在跨層通信時(shí)的編程負(fù)擔(dān)，本文將Android層的信息傳遞代碼編寫為Java類庫.開發(fā)人員可以通過直接調(diào)用類的靜態(tài)方法進(jìn)行交互信息傳遞.靜態(tài)方法有2個(gè)：標(biāo)識(shí)交互事件開始的方法foreground(intpid)和標(biāo)識(shí)交互任務(wù)結(jié)束的方法background(intpid).對(duì)于任務(wù)依賴關(guān)系，可以通過另外2個(gè)靜態(tài)方法attachForeground(int pid)與attachBackground(intpid)進(jìn)行傳遞.第5節(jié)中均使用這個(gè)類庫來進(jìn)行跨層信息的傳遞.

上述方法中的參數(shù)為交互線程的任務(wù)ID編號(hào).由于Android層的線程編號(hào)與對(duì)應(yīng)的Linux內(nèi)核中的線程編號(hào)不同，因此在Android層需要使用android.os.Process.myTid()方法來獲取對(duì)應(yīng)于Linux內(nèi)核層的線程的任務(wù)ID.

5實(shí)驗(yàn)與評(píng)估

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

為了驗(yàn)證XOS算法的實(shí)際運(yùn)行效率，本文設(shè)計(jì)一系列實(shí)驗(yàn)，將任務(wù)分別使用GTS與XOS執(zhí)行，并分別統(tǒng)計(jì)響應(yīng)時(shí)間與能耗信息，以比較2種算法的性能.如表2所示，本文抽取了在智能移動(dòng)設(shè)備上用戶的幾類典型交互行為，包括圖片上傳、網(wǎng)頁瀏覽、音樂播放、視頻播放以及電子書閱讀，并為每種行為都分別設(shè)計(jì)了一組實(shí)驗(yàn).由于圖片上傳、網(wǎng)頁瀏覽交互行為的響應(yīng)時(shí)間都比較短，為減少實(shí)驗(yàn)誤差，在實(shí)驗(yàn)中將每種操作重復(fù)10次，每10次作為一次循環(huán)，一共循環(huán)4次.實(shí)驗(yàn)的硬件環(huán)境仍為Odroid-XU3開發(fā)板.

Table 2　The Tests Table

由于缺少商用Android應(yīng)用程序的源代碼，跨層通信機(jī)制難以實(shí)現(xiàn)，因而本文設(shè)計(jì)了新的程序?qū)崿F(xiàn)對(duì)這幾種交互行為的模擬測(cè)試.為了減少其他任務(wù)的影響，實(shí)驗(yàn)程序包含6個(gè)Activity界面，其中一個(gè)為主界面，從主界面可以跳轉(zhuǎn)到實(shí)現(xiàn)這些交互行為的測(cè)試界面上.使用第4節(jié)描述的Java類庫來進(jìn)行跨層通信，僅需要在這些實(shí)驗(yàn)程序模塊中各自添加兩行代碼標(biāo)識(shí)交互事件開始、交互事件結(jié)束即可實(shí)現(xiàn)，大大減少了跨層通信的代碼工作量，有效降低了開發(fā)人員在使用此調(diào)度算法時(shí)的負(fù)擔(dān).

對(duì)于圖片上傳測(cè)試，本文搭建了一個(gè)基于J2EE的服務(wù)器用以接受客戶端發(fā)來的圖片.每次上傳大小均為2 097 152 B的一張圖片.測(cè)試程序與服務(wù)器處于局域網(wǎng)中來減少網(wǎng)絡(luò)波動(dòng)對(duì)實(shí)驗(yàn)的影響.對(duì)于網(wǎng)頁瀏覽測(cè)試，選擇淘寶網(wǎng)站主頁(www.taobao.com)作為加載頁面.對(duì)于音樂播放測(cè)試，本文選取了播放長(zhǎng)度為27 s的MP3音樂文件作為測(cè)試對(duì)象.對(duì)于視頻播放測(cè)試，測(cè)試對(duì)象為播放長(zhǎng)度為55 s的MP4視頻文件.由于MP3,MP4文件格式能夠被Android系統(tǒng)在無第三方應(yīng)用的情況下支持，所以使用這2種文件作為測(cè)試對(duì)象，能夠在最大程度上減少其他因素的影響.對(duì)于電子書閱讀測(cè)試，測(cè)試程序讀取大小為5 MB的TXT文件，并在屏幕上顯示20行文字.每隔2 s時(shí)間，屏幕會(huì)自動(dòng)翻頁并顯示接下來的20行文字，一次測(cè)試一共執(zhí)行20次自動(dòng)翻頁.

在每個(gè)測(cè)試執(zhí)行過程中，啟用一個(gè)采樣線程來獲取測(cè)試實(shí)驗(yàn)的能耗數(shù)據(jù)以及響應(yīng)時(shí)間.由于采樣線程無論以何種采樣頻率進(jìn)行采樣，都會(huì)有一定的能耗，所以本文在測(cè)試實(shí)驗(yàn)結(jié)束之后將采樣線程本身的能耗從結(jié)果中減去，以減少采樣線程所帶來的實(shí)驗(yàn)誤差.

5.2實(shí)驗(yàn)分析

實(shí)驗(yàn)結(jié)束后，本文通過采樣線程分別收集了2種算法的實(shí)驗(yàn)?zāi)芎臄?shù)據(jù)與響應(yīng)時(shí)間數(shù)據(jù).

圖9為實(shí)驗(yàn)?zāi)芎慕y(tǒng)計(jì)結(jié)果，5種實(shí)驗(yàn)測(cè)試在XOS算法下的能耗相對(duì)于GTS算法分別降低了48.5%,12.1%,9.8%,28.2%與8.0%.

測(cè)試程序的執(zhí)行時(shí)間如圖10所示，圖片上傳的執(zhí)行時(shí)間增加了15.9%，而網(wǎng)頁瀏覽的執(zhí)行時(shí)間增加了7.0%.由于音樂播放、視頻播放與電子書閱讀行為屬于長(zhǎng)任務(wù)，其QoE值已經(jīng)很低，所以對(duì)于這3種操作，本文僅統(tǒng)計(jì)其能耗結(jié)果.根據(jù)式(1)，將響應(yīng)時(shí)間轉(zhuǎn)換為用戶體驗(yàn)MOS值的統(tǒng)計(jì)結(jié)果如表3所示，XOS算法對(duì)于圖片上傳操作的用戶體驗(yàn)降低了7.3%左右，而對(duì)于網(wǎng)頁瀏覽操作降低了2.7%.

Fig. 9　Energy consumption with GTS and XOS.圖9　實(shí)驗(yàn)?zāi)芎慕Y(jié)果

Fig. 10　Response time of tasks with GTS and XOS.圖10　實(shí)驗(yàn)響應(yīng)時(shí)間結(jié)果

AlgorithmImageUploadingWebpageLoadingGTS2.482.98XOS2.302.90

總體而言，XOS算法使得任務(wù)的執(zhí)行時(shí)間略有延長(zhǎng)，用戶體驗(yàn)輕微下降，但是實(shí)現(xiàn)了能耗的顯著降低.特別是對(duì)于執(zhí)行時(shí)間不受硬件影響的任務(wù)(如音樂播放等)，XOS能夠明顯降低其能耗.

6相關(guān)工作

在先前的研究中，許多研究者聚焦于異構(gòu)多核架構(gòu)的任務(wù)調(diào)度.現(xiàn)有調(diào)度算法可大致分為2類：1)粗粒度算法，其調(diào)度對(duì)象為線程或進(jìn)程；2)細(xì)粒度算法，其調(diào)度對(duì)象為代碼段[14].

粗粒度調(diào)度算法中有公平算法與不公平算法2種.Van Craeynest等人提出了一種公平調(diào)度算法，試圖保證每個(gè)線程在每種類型的核心上運(yùn)行相等的時(shí)間，從而達(dá)到公平的目的[15].但是這個(gè)調(diào)度算法僅試圖將所有的核心利用起來，并未對(duì)性能與能耗進(jìn)行優(yōu)化.該團(tuán)隊(duì)同時(shí)還提出了另一種非公平調(diào)度算法PIE(performance impact estimation)，通過收集任務(wù)運(yùn)行時(shí)CPI棧、MLP、ILP的信息決定任務(wù)適合在何種類型的核心上運(yùn)行[9].此外，Li等人也提出了一種大核優(yōu)先算法，盡可能讓新的任務(wù)運(yùn)行在大核上以充分利用大核的計(jì)算資源[8].以上這2種算法僅考慮了性能優(yōu)化而忽視了系統(tǒng)的能耗約束.Koufaty等人提出了一種偏好算法，能夠識(shí)別一個(gè)線程的運(yùn)行是偏向于大核還是小核，繼而選擇最合適的核心來運(yùn)行[16].該算法能夠在一定程度上兼顧性能與能耗，但是仍舊沒有考慮用戶體驗(yàn).

細(xì)粒度的調(diào)度算法側(cè)重于代碼段的執(zhí)行，這種類型的調(diào)度算法能夠?qū)θ蝿?wù)進(jìn)行更精細(xì)的分割.Suleman等人提出了ACS(accelerated critical sections)算法，能夠加速線程中臨界區(qū)代碼段的執(zhí)行速度[17]，但是對(duì)于交互敏感的非互斥任務(wù)作用不大.Sondag等人提出了一種基于代碼分段的算法，將代碼分段，根據(jù)預(yù)先建立的信息庫匹配代碼段的特性，用于指導(dǎo)該段代碼的核心分配[18].研究顯示，高并行化的代碼在大量低性能核心上運(yùn)行的效率是在少量高性能核心上的2倍左右[19].鑒于此，Saez等人提出了一種輕量算法，能夠快速識(shí)別出線程并發(fā)度高的代碼和處理器密集型代碼，從而針對(duì)性地分配核心以發(fā)揮優(yōu)勢(shì)[20].蔣建春等人設(shè)計(jì)了靜態(tài)任務(wù)調(diào)度算法，能夠使得任務(wù)在最短時(shí)間內(nèi)完成并實(shí)現(xiàn)大小核心的負(fù)載均衡[21].這些算法能夠加速任務(wù)執(zhí)行、縮短響應(yīng)時(shí)間，但是這些算法側(cè)重于性能的提升，沒有考慮智能移動(dòng)設(shè)備的能耗約束和應(yīng)用軟件的復(fù)雜性，所以不能很好地應(yīng)用于商業(yè)產(chǎn)品中.彭蔓蔓等人在使用改進(jìn)的啟發(fā)式方法進(jìn)行任務(wù)分組的同時(shí)，又使用遺傳算法進(jìn)行任務(wù)的調(diào)度，能夠?qū)崿F(xiàn)在實(shí)時(shí)性要求較低的情況下以較小的時(shí)間代價(jià)來節(jié)省較多的能耗[22].然而對(duì)于交互性任務(wù)，其實(shí)時(shí)性要求較高，所以這種調(diào)度算法并不能滿足用戶的交互體驗(yàn).

7總結(jié)

本文設(shè)計(jì)了一種面向用戶體驗(yàn)的高能效異構(gòu)多核調(diào)度算法XOS，試圖兼顧智能移動(dòng)設(shè)備的能效與用戶體驗(yàn).首先本文使用一個(gè)仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性，并對(duì)算法模型進(jìn)行了改進(jìn)，同時(shí)確定了調(diào)度時(shí)間臨界點(diǎn).隨后，在Android平臺(tái)和在Linux系統(tǒng)內(nèi)核中實(shí)現(xiàn)了該算法，并通過應(yīng)用程序?qū)崪y(cè)檢測(cè)算法的性能.實(shí)驗(yàn)測(cè)試結(jié)果顯示，XOS能夠在保障用戶體驗(yàn)的前提下使系統(tǒng)能耗得到明顯的降低.

參考文獻(xiàn)

[1]Kumar R, Farkas K I, Jouppi N P, et al. Single-ISA heterogeneous multi-core architectures: The potential for processor power reduction[C]Proc of the 36th Annual IEEEACM Int Symp on Microarchitecture. Los Alamitos, CA: IEEE Computer Society, 2003: 81-92

[2]Kumar R, Tullsen D M, Ranganathan P, et al. Single-ISA heterogeneous multi-core architectures for multithreaded workload performance[J]. ACM SIGARCH Computer Architecture News, 2004, 32(2): 64-64

[3]Duran A, Ayguadé E, Badia R M, et al. Ompss: A proposal for programming heterogeneous multi-core architectures[J]. Parallel Processing Letters, 2011, 21(2): 173-193

[4]Wang P H, Collins J D, Chinya G N, et al. EXOCHI: Architecture and programming environment for a heterogeneous multi-core multithreaded system[C]Proc of the 28th ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2007: 156-166

[5]Chen Fangyuan, Zhang Dongsong, Wang Zhiying. Research of the heterogeneous multi-core processor architecture design[J]. Computer Engineering & Science, 2011, 33(12): 27-36 (in Chinese)(陳芳園, 張冬松, 王志英. 異構(gòu)多核處理器體系結(jié)構(gòu)設(shè)計(jì)研究[J]. 計(jì)算機(jī)工程與科學(xué), 2011, 33(12): 27-36)

[6]Lin F X, Wang Z, Zhong L. K2: A mobile operating system for heterogeneous coherence domains[J]. ACM Trans on Computer Systems, 2015, 33(2): 4:1-4:27

[7]Greenhalgh P. big.LITTLE processing with ARM Cortex-A15 & Cortex-A7[EBOL]. [2016-03-01]. http:www.eetimes.comdocument.asp?doc_id=1279167

[8]Li T, Baumberger D, Koufaty D A, et al. Efficient operating system scheduling for performance-asymmetric multi-core architectures[C]Proc of the 2007 ACMIEEE Conf on Supercomputing. New York: ACM, 2007: 53-53

[9]Van Craeynest K, Jaleel A, Eeckhout L, et al. Scheduling heterogeneous multi-cores through performance impact estimation (PIE)[C]Proc of the 39th Annual Int Symp on Computer Architecture. Los Alamitos, CA: IEEE Computer Society, 2012: 213-224

[10]ARM. big.LITTLE Technology: The Future of Mobile[EBOL]. [2016-03-01]. http:www.arm.comfilespdfbig_LITTLE_Technology_the_Futue_of_Mobile.pdf

[11]Kuipers F, Kooij R, De Vleeschauwer D, et al. Techniques for measuring quality of experience[C]Proc of the 8th Int Conf on WiredWireless Internet Communications. Berlin: Springer, 2010: 216-227

[12]Kopytov A. SysBench: A system performance benchmark[EBOL]. [2016-03-01]. http:sysbench.sourceforge.net

[13]Agawi App Glimpse. TouchMarks I: Smartphone Touchscreen Latencies[EBOL]. [2016-03-01]. http:appglimpse.comblogtouchmarks-i-smart-phone-touch-screen-latencies

[14]Bambagini M, Marinoni M, Aydin H, et al. Energy-aware scheduling for real-time systems: A survey[J]. ACM Trans on Embedded Computing Systems (TECS), 2016, 15(1): 7:1-7:34

[15]Van Craeynest K, Akram S, Heirman W, et al. Fairness-aware scheduling on single-ISA heterogeneous multi-cores[C]Proc of the 22nd Int Conf on Parallel Architectures and Compilation Techniques. Piscataway, NJ: IEEE, 2013: 177-188

[16]Koufaty D, Reddy D, Hahn S. Bias scheduling in heterogeneous multi-core architectures[C]Proc of the 5th European Conf on Computer Systems. New York: ACM, 2010: 125-138

[17]Suleman M A, Mutlu O, Qureshi M K, et al. Accelerating critical section execution with asymmetric multi-core architectures[C]Proc of the 14th Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2009: 253-264

[18]Sondag T, Rajan H. Phase-guided thread-to-core assignment for improved utilization of performance-asymmetric multi-core processors[C]Proc of the 2009 ICSE Workshop on Multicore Software Engineering. Los Alamitos, CA: IEEE Computer Society, 2009: 73-80

[19]Hill M D, Marty M R. Amdahl’s law in the multicore era[J]. Computer, 2008, 41(7): 33-38

[20]Saez J C, Prieto M, Fedorova A, et al. A comprehensive scheduler for asymmetric multicore systems[C]Proc of the 5th European Conf on Computer Systems. New York: ACM, 2010: 139-152

[21]Jiang Jianchun, Wang Tongqing. Task scheduling algorithm for heterogeneous multi-core processor[J]. Computer Engineering and Applications, 2009, 45(33): 52-56 (in Chinese)(蔣建春, 汪同慶. 異構(gòu)多核處理器的任務(wù)調(diào)度算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2009, 45(33): 52-56)

[22]Peng Manman, Xu Lichao, Wang Ying. Task allocation and energy on heterogeneous multi-core processors[J]. Application Research of Computers, 2010, 27(5): 1729-1736 (in Chinese)(彭蔓蔓, 徐立超, 王穎. 異構(gòu)多核處理器的任務(wù)分配及能耗的研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2010, 27(5): 1729-1736)

Gong Xiaoli, born in 1983. PhD and assistant professor in Nankai University. Member of China Computer Federation. His main research interests include embedded system design and optimization.

Yu Haiyang, born in 1991. Bachelor in Nankai University. His main research interests include energy-efficient computing and human-computer interaction (oceanisher@mail.nankai.edu.cn).

Sun Chengjun, born in 1992. Bachelor in Nankai University. Her main research interests include energy-efficient computing and human-computer interaction (suncheng jun2015@mail.nankai.edu.cn).

Li Tao, born in 1977. PhD and associate professor in Nankai University. Member of China Computer Federation. His main research interests include high performance computing and parallelized computing (litao@nankai.edu.cn).

Zhang Jin, born in 1979. PhD and associate professor in Nankai University. Member of China Computer Federation. His main research interests include mobile cloud computing (nkzhangjin@nankai.edu.cn).

Ma Jie, born in 1957. Bachelor and professor in Nankai University. Member of China Computer Federation. His main research interests include new media technology (majie1765@nankai.edu.cn).

收稿日期：2016-03-03；修回日期：2016-05-07

基金項(xiàng)目：教育部高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金項(xiàng)目(20130031120028)；天津市應(yīng)用基礎(chǔ)與前沿技術(shù)研究計(jì)劃青年項(xiàng)目(14JCQNJC00700)；天津市自然科學(xué)基金項(xiàng)目(16JCYBJC15200)；計(jì)算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室開放課題(CARCH201504)

中圖法分類號(hào)TP316

XOS: A QoE Oriented Energy Efficient Heterogeneous Multi-Processor Schedule Mechanism

Gong Xiaoli1, Yu Haiyang2, Sun Chengjun1, Li Tao1,3, Zhang Jin1, and Ma Jie2

1(CollegeofComputerandControlEngineering,NankaiUniversity,Tianjin300071)2(CollegeofSoftware,NankaiUniversity,Tianjin300071)3(StateKeyLaboratoryofComputerArchitecture(InstituteofComputingTechnology,ChineseAcademyofSciences),Beijing100190)

AbstractSmart mobile devices are playing a more and more important part in people’s daily life. However, the pursuit of increasing performance of mobile devices directly conflicts with the limited battery capacity. The inevitable contradiction between them begins to block the development of smart mobile devices. To overcome this limitation, the heterogeneous multi-processor architecture can balance the user experience and the energy consumption on smart mobile devices, which makes it become a new solution. Based on a compartmental QoE model, a schedule mechanism called XOS oriented heterogeneous multi-processor devices is presented to provide a high energy efficient solution. In XOS, the user interaction tasks are recognized by the operating system based on the cross-layer information, and more computing resources are allocated to these tasks to guarantee the quality of experience, while resources would be limited for other tasks to reduce energy consumption. A simulation system is built to verify the effectiveness of the XOS model and then make a reasonable optimization. Then the implementation and the experiment of the XOS are conducted on Odroid-XU3 board with Android operation system. The result shows that the tasks scheduled by XOS decelerate lessens 2.7%～7.3% QoE lost, whereas they reduce 8%～48% energy consumption at the same time.

Key wordssmart mobile devices; heterogeneous multi-processor (HMP); quality of experience (QoE); energy consumption optimization; schedule mechanism; cross-layer information

This work was supported by the Specialized Research Fund for the Doctoral Program of Higher Education of China (20130031120028), the Research Plan in Application Foundation and Advanced Technologies in Tianjiin (14JCQNJC00700), the Natural Science Foundation of Tianjin (16JCYBJC15200), and the Open Project of the State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences (CARCH201504).