XOS：面向用戶體驗質量的高能效異構多核調度算法

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

1(南開大學計算機與控制工程學院　天津　300071)2(南開大學軟件學院　天津　300071)3　　　(計算機體系結構國家重點實驗室(中國科學院計算技術研究所)　北京　100190)

?

XOS：面向用戶體驗質量的高能效異構多核調度算法

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

1(南開大學計算機與控制工程學院天津300071)2(南開大學軟件學院天津300071)3(計算機體系結構國家重點實驗室(中國科學院計算技術研究所)北京100190)

(gongxiaoli@nankai.edu.cn)

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

關鍵詞智能移動設備；異構多核處理器；體驗質量；能耗優化；調度機制；跨層信息

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

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

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

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

在傳統的異構多核調度算法中，基于任務周期性的歷史運行負載信息[8-9]對任務進行大小核之間的遷移.然而在現代智能移動設備中，大多數任務能夠在很短的時間內完成，這使得難以進行精確的任務負載追蹤.同時，線程池機制的大量使用使得同一線程執行的多段代碼之間缺少必然的邏輯關系，這增加了負載追蹤的復雜度.

為了解決以上問題，本文提出了XOS(experience oriented scheduler)異構多核調度算法，基于跨層信息，在保障用戶體驗質量的同時提高能效.該調度算法實現了3個目標：

1) 確保用戶體驗質量;

2) 改進能量利用效率;

3) 避免給程序開發人員帶來巨大的編程負擔.

1相關技術介紹

1.1智能移動設備中的任務

智能移動設備多采用現代化的多任務操作系統，可以支持多進程、多線程的運行環境.設備中并發運行著多種不同類型的任務.依據與用戶直接交互形式的差異，本文中將任務分為3類：

1) 后臺任務.后臺任務是指處于等待外部設備數據狀態的服務任務，包括檢測信號強度、電量、統計存儲用量等，或是由用戶人工置于后臺的任務.用戶通常不等待這些任務運行的直接結果，因而用戶體驗很少受到此類任務的影響.

2) 強交互任務.強交互任務與用戶的主觀體驗直接相關，如3D游戲、網頁渲染等.用戶通常直接等待此類任務產生的反饋結果，任務的響應時間會對用戶體驗質量產生明顯影響.因此，需向此類任務分配更多的計算資源以加速其執行.

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

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

1.2IKS與GTS調度算法

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

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

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

相比于IKS，GTS能夠同時開啟所有的核心，充分利用異構多核CPU的計算資源.然而，GTS僅以任務負載作為任務遷移的依據，并沒有針對移動任務的特征和用戶體驗的需求進行優化.

1.3QoE用戶體驗質量

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

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

(1)

為了簡單起見，本文將用戶體驗質量分為3段：高用戶體驗部分(good QoE)、低用戶體驗部分(bad QoE)以及介于兩者之間的連續變化部分，如圖2所示.根據ITU研究結果，如果響應時間過短或過長，那么響應時間的變化對用戶體驗質量不會產生顯著影響.換言之，處于高用戶體驗區或低用戶體驗區的部分任務，可以在不影響其用戶體驗質量的前提下降低其性能，以達到降低系統能耗的效果.這是XOS調度算法建立的基礎.

Fig. 2　MOS for response time.圖2　響應時間與MOS折線圖

2XOS算法設計

2.1調度原則

XOS調度算法將兼顧能耗與用戶體驗質量.為此，算法的設計滿足6個原則：

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

② 算法能夠識別輕交互任務，當任務在小核上執行時間過長時，為避免QoE 出現損失，提前將任務遷移至大核；

③ 如果任務運行于大核而用戶體驗質量仍未能得到改進，那么此時應該以降低能耗為首要目標，將其遷至小核；

④ 交互事件完成之后，任務應該立即回到小核上以減少能耗；

⑤ 傳統的同構多核調度算法中對于同類核心的管理代碼應該加以利用；

⑥ 不應該給應用開發人員帶來額外的編程負擔，避免開發復雜化.

2.2調度模型

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

圖3展示了一個交互任務的調度模型：

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

一個任務接受了用戶的交互操作，或與交互任務建立依賴關系后開始進入交互狀態.根據調度模型，一個交互任務的完整調度流程分為4個步驟：

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

Step2. 任務運行于小核.如果交互任務能夠在短時間內完成(t

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

Step4. 任務從大核遷移回小核運行.Tswitchdown被設置為任務從大核遷回至小核的時間臨界點.如果任務在Tswitchdown的時間內沒有完成，這表示此任務給用戶帶來的體驗已經很低，此時即使加速此任務，用戶體驗質量也無法改進.因此，該任務將會被遷回至小核執行，以降低能耗.

另外，如果交互任務執行結束或者被轉移至后臺使得其不再處于交互狀態，則無論任務此時運行于何種核心，都會遷移到小核上運行以節省能耗.

以上是任務在大小核之間遷移的基本流程.在大核簇與小核簇的內部，仍舊按照傳統同構多核調度算法的規則進行內部調度，充分發揮處理器性能.

2.3交互事件信息

應用程序內部的上下文語義信息在到達操作系統內核前就已丟失，因而交互行為很難被操作系統自動檢測.因此，本文將引入一種跨層通信機制收集應用層信息并將其直接傳遞給調度器.

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

當一個處于交互事件中的任務被調度時，所有被此任務調用而產生依賴關系的任務都應被當作交互任務對待.因此，XOS算法中包含一個任務依賴關系檢測機制.當應用程序中任務之間發生依賴關系時，依賴關系信息將被發送至調度器.XOS會根據應用層的運行信息，建立一個任務依賴關系樹.在任務遷移的過程中，依賴關系樹中所有的任務會綁定為一個整體，依據根結點的屬性進行遷移判斷.

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

3仿真實驗

3.1仿真程序設計

為了驗證XOS調度算法的有效性，并確定2.2節提到的2個時間臨界點Tswitchup與Tswitchdown，首先采用程序模擬調度的方式進行仿真實驗.在仿真實驗中，同時實現了GTS算法和XOS算法的調度邏輯，并通過模擬對2種算法的性能進行比較.

仿真實驗程序用JAVA語言編程，圖4為其程序類圖.程序中使用一個線程(SimulationThread)的一次循環執行代表內核時間片的一次運轉.使用任務實體類(TaskEntity)來代表任務，并細分為短任務類(ShortTask)與長任務類(LongTask)，所有的任務會存放于任務對象池(TaskObjectPool)數據結構中.任務以及任務對象池在仿真初始化時產生.仿真線程由任務實體類對象與調度算法類對象(GTS，XOS)組成，并在一次循環過程中分別按照GTS與XOS算法對這些任務對象進行模擬調度，并分別記錄2種算法對于任務的執行結果.

Fig. 4　The class diagram of the simulation problem.圖4　仿真實驗程序類圖

每個任務都有啟動時間、持續時間、任務負載等屬性，這些屬性都是在仿真實驗開始時隨機生成，并且，短任務與長任務的持續時間有明顯的差異.

3.2仿真參數設置

在仿真實驗中需要配置一些實驗參數，例如真實環境中的硬件性能參數、能耗參數等.這些參數對于仿真實驗的有效性至關重要.

1) 能耗參數設置

本文實驗中使用了Odroid-XU3開發板，其CPU為三星Exynos 5422，包含4個Cortex-A15核心與4個Cortex-A7核心，組成big．LITTLE架構.開發板上附帶了4個能耗傳感器，能夠實時監測大核簇、小核簇、GPU和內存的能耗信息.本文使用簡單的循環計算程序對CPU進行能耗測試，同時，使用一個循環線程來讀取能耗傳感器的值.通過測量，小核單個核心在滿負載狀態下的能耗為180 mW，大核為1 555 mW.另外，當小核簇或者大核簇在開啟時會產生基礎能耗，小核簇的基礎能耗為282 mW，大核簇的基礎能耗為1 013 mW.最后，通過測試不同核心對SysBench[12]指標程序執行時間長短的不同，得到大核與小核的計算性能比為2.5∶1.以上信息將作為基本參數用于模擬實驗.

2) 遷移臨界設置

根據ITU的研究報告[11]，任務的MOS值超過3.5即可計為用戶體驗優良狀態，按式(1)即為任務的響應時間控制在430 ms之內.所以在仿真實驗中選擇430 ms作為任務從小核遷移到大核的臨界點.

根據Agawi[13]的測試結果，智能移動設備的屏幕響應時間大約在100～130 ms之間.程序可用的運行時間應減去設備的響應時間，因此設置Tswitchup=300 ms.同時，根據式(1)，設置Tswitchdown=5 s.

3) 任務集合設置

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

3.3仿真結果

1) XOS調度模型改進

通過對仿真實驗數據的分析發現，在簡單短任務調度的能效方面XOS比GTS具有明顯優勢，但隨著任務在大核上執行時間的增長，XOS算法能耗快速增加.由于交互任務一直運行于大核，超過特定時間點后，XOS算法的能效開始低于GTS.此后，使用GTS算法能夠獲得更好的能量利用率.

基于該方面的考慮，本文選擇一定的時間之后使用GTS算法的調度邏輯來調度任務，以獲取更優的能效.即在原有的2個時間點Tswitchup與Tswitchdown之間，加入一個時間點TswitchtoGTS.圖5展示的是加入TswitchtoGTS時間點之后的調度模型.如果一個任務在遷移到大核并且執行時間達到TswitchtoGTS之后，仍舊沒有完成，那么它將會遵循GTS的調度原則進行調度.如果它在達到Tswitchdown時間點之后仍然沒有完成，那么它將會按照XOS算法的調度原則強制遷移至小核.

Fig. 5　The improved XOS schedule model.圖5　改進的XOS模型

Fig. 6　The result of the experiment without Tswitchdown.圖6　去掉Tswitchdown之后的實驗仿真結果

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

2) 仿真結果分析

Fig. 7　The result of short tasks simulation.圖7　仿真實驗短任務能耗結果

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

Fig. 8　The result of long tasks simulation.圖8　仿真實驗長任務能耗結果

AlgorithmMOS≥3.5MOSSumShortTasksLongTasksShortTasksLongTasksGTS50002467315XOS50002272313

4XOS算法實現

本文在hardkernel發布的Linux-odroidxu3-3.10.y-android的基礎上實現了XOS調度算法，并將其部署運行在相應的Odroid-XU3開發板上進行驗證.按照模擬仿真實驗的結果，XOS中還保持了GTS算法的調度邏輯并在特定的條件下被激活，因此，該調度算法在GTS的數據結構和代碼邏輯基礎上擴展實現.

1) 算法的內核實現

在數據存儲上，擴展task_struct中的數據結構sched_avg，加入對進程的交互狀態(qoe_in_interaction_process)、交互開始時間(qoe_interaction_start_time_jiffies)、大小核切換時間(qoe_switch_to_highprocess_for_performance，qoe_switch_to_lowprocess_for_saving) 等信息的存儲，并在相應的時機進行更新.

在執行邏輯上，借助GTS對遷移條件檢查的時間點對QoE和交互狀態進行檢查，并完成任務的核心遷移.在GTS算法中一共有5個遷移點，在內核源代碼中分別實現為select_task_rq_fair，run_rebalance_domains，hmp_force_up_migration，hmp_idle_pull，hmp_offload_down.每個任務的負載在__update_task_entity_contrib中定期更新,并檢查是否需要觸發任務遷移事件.在遷移時，任務會被hmp_up_migration與hmp_down_migration加以評估，以決定一個任務是否繼續在原有的核上運行.

借用GTS的接口，在每次任務負載更新函數__update_task_entity_contrib被調用時，XOS檢查任務的交互狀態和在當前核心上的運行時間，以決定是否需要觸發遷移以及遷移的方向.類似地，在其他4個遷移點，XOS也需要判斷遷移條件和方向.此部分邏輯在每次確定遷移方向前都被調用，因此在內核中被實現為一個內聯函數should_stay_low_cpu.同時，在遷移條件的檢查點也需要確認任務在大核上的運行時間和交互狀態，以確定是否應該使用GTS調度算法，該內聯函數實現為should_follow_gts.為了保證GTS算法在接管調度器時能夠正確地計量任務的負載，所有GTS算法相關的數據結構和屬性更新均保持原有執行邏輯，不受XOS算法的影響.

任務的交互狀態信息由應用程序借助sysfs接口傳遞給內核.調度器通過在sysfs中注冊一些屬性文件實現與用戶空間的交互，其中move_foreground與move_background用于向內核傳遞任務的狀態變化，由交互任務向文件中寫入對應的任務號即可通知內核改變其交互狀態.對于任務依賴關系，則通過attached_to_foreground，detached_from_foreground兩個接口獲得.被前臺任務調用的任務，將其調用者的任務號寫入相應接口即可通知調度器.

任務間的依賴關系在內核中以樹的形式記錄.每個任務的task_struct數據結構中加入變量qoe_attached_to_process.如果任務沒有依賴關系，那么這個任務的依賴樹就是一棵只有根節點的樹，該變量中保存的是該任務自已的任務號.當任務產生依賴時，被調用者記錄了調用者的任務號，形成一個以父節點形式存儲的樹狀結構.在進行遷移條件檢查時，如果發現任務存在對其他任務的依賴，則沿著該組任務的qoe_attached_to_process尋找到這個依賴樹的樹根，并以根任務的屬性進行遷移條件判斷.

2) 跨層類庫實現

為了減少應用開發人員在跨層通信時的編程負擔，本文將Android層的信息傳遞代碼編寫為Java類庫.開發人員可以通過直接調用類的靜態方法進行交互信息傳遞.靜態方法有2個：標識交互事件開始的方法foreground(intpid)和標識交互任務結束的方法background(intpid).對于任務依賴關系，可以通過另外2個靜態方法attachForeground(int pid)與attachBackground(intpid)進行傳遞.第5節中均使用這個類庫來進行跨層信息的傳遞.

上述方法中的參數為交互線程的任務ID編號.由于Android層的線程編號與對應的Linux內核中的線程編號不同，因此在Android層需要使用android.os.Process.myTid()方法來獲取對應于Linux內核層的線程的任務ID.

5實驗與評估

5.1實驗設計

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

Table 2　The Tests Table

由于缺少商用Android應用程序的源代碼，跨層通信機制難以實現，因而本文設計了新的程序實現對這幾種交互行為的模擬測試.為了減少其他任務的影響，實驗程序包含6個Activity界面，其中一個為主界面，從主界面可以跳轉到實現這些交互行為的測試界面上.使用第4節描述的Java類庫來進行跨層通信，僅需要在這些實驗程序模塊中各自添加兩行代碼標識交互事件開始、交互事件結束即可實現，大大減少了跨層通信的代碼工作量，有效降低了開發人員在使用此調度算法時的負擔.

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

在每個測試執行過程中，啟用一個采樣線程來獲取測試實驗的能耗數據以及響應時間.由于采樣線程無論以何種采樣頻率進行采樣，都會有一定的能耗，所以本文在測試實驗結束之后將采樣線程本身的能耗從結果中減去，以減少采樣線程所帶來的實驗誤差.

5.2實驗分析

實驗結束后，本文通過采樣線程分別收集了2種算法的實驗能耗數據與響應時間數據.

圖9為實驗能耗統計結果，5種實驗測試在XOS算法下的能耗相對于GTS算法分別降低了48.5%,12.1%,9.8%,28.2%與8.0%.

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

Fig. 9　Energy consumption with GTS and XOS.圖9　實驗能耗結果

Fig. 10　Response time of tasks with GTS and XOS.圖10　實驗響應時間結果

AlgorithmImageUploadingWebpageLoadingGTS2.482.98XOS2.302.90

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

6相關工作

在先前的研究中，許多研究者聚焦于異構多核架構的任務調度.現有調度算法可大致分為2類：1)粗粒度算法，其調度對象為線程或進程；2)細粒度算法，其調度對象為代碼段[14].

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

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

7總結

本文設計了一種面向用戶體驗的高能效異構多核調度算法XOS，試圖兼顧智能移動設備的能效與用戶體驗.首先本文使用一個仿真實驗驗證了算法的有效性，并對算法模型進行了改進，同時確定了調度時間臨界點.隨后，在Android平臺和在Linux系統內核中實現了該算法，并通過應用程序實測檢測算法的性能.實驗測試結果顯示，XOS能夠在保障用戶體驗的前提下使系統能耗得到明顯的降低.

參考文獻

[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)(陳芳園, 張冬松, 王志英. 異構多核處理器體系結構設計研究[J]. 計算機工程與科學, 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)(蔣建春, 汪同慶. 異構多核處理器的任務調度算法[J]. 計算機工程與應用, 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)(彭蔓蔓, 徐立超, 王穎. 異構多核處理器的任務分配及能耗的研究[J]. 計算機應用研究, 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

基金項目：教育部高等學校博士學科點專項科研基金項目(20130031120028)；天津市應用基礎與前沿技術研究計劃青年項目(14JCQNJC00700)；天津市自然科學基金項目(16JCYBJC15200)；計算機體系結構國家重點實驗室開放課題(CARCH201504)

中圖法分類號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).