S-Bridge:性能非對稱多核處理器下負載均衡代理機制?

趙 姍 , 郝春亮 , 翟 健 , 李明樹

1(中國科學院 軟件研究所 基礎(chǔ)軟件國家工程研究中心,北京 100190)

2(中國科學院大學,北京 100190)

性能非對稱性異構(gòu)多核處理器(asymmetric multicore processors,簡稱AMPs)在同一處理器中集成不同微架構(gòu)設(shè)計的CPU 核心(core),這些核心具有不同的特性,比如高性能、低功耗,可以協(xié)同工作提供良好的性能功耗比(能效)[1-3].目前,典型的代表是ARM 的big.LITTLE[4]架構(gòu)設(shè)計(例如高通驍龍855 和華為麒麟980),普遍應(yīng)用在移動終端場景下,可以根據(jù)手機上不同應(yīng)用的需求[5]選擇不同的CPU 核心處理,以便達到性能與功耗的平衡.

然而,異構(gòu)多核處理器設(shè)計在提供高能效的同時,也為操作系統(tǒng)的任務(wù)調(diào)度帶來諸多挑戰(zhàn)[1].任務(wù)調(diào)度作為提高多核系統(tǒng)性能和資源利用率的重要手段[6],其中一個重要的問題是CPU 調(diào)度的負載均衡[7,8].由于傳統(tǒng)負載均衡主要是針對同構(gòu)多核處理器設(shè)計,其基本思想是保證負載在各個核之間均勻分布,當分布不均時,需要將任務(wù)從高負載核心遷移到低負載核心[9,10].然而在異構(gòu)環(huán)境中,不同核之間的微架構(gòu)存在差異,相同任務(wù)在不同類型核上運行的相對負載不盡相同,無法再以任務(wù)的平均分布情況作為負載均衡的單一判別標準.同時,由于不同類型任務(wù)對于CPU 核的利用情況差異顯著[2,3],傳統(tǒng)的負載均衡會導致不合理的決策.

基于此問題,已有研究工作是面向異構(gòu)環(huán)境進行調(diào)度模塊本身的設(shè)計和優(yōu)化[7,11-15],為異構(gòu)環(huán)境提供了可用的調(diào)度和負載均衡方案.然而,由于缺乏平臺級的改進,無法對傳統(tǒng)環(huán)境下已有的調(diào)度器形成支持,因而降低了系統(tǒng)調(diào)度機制適配的可擴展特性.在上述背景下,本文提出一種新的負載均衡機制S-Bridge,在系統(tǒng)層實現(xiàn)對CPU 微架構(gòu)和任務(wù)異構(gòu)性的感知;繼而對所有調(diào)度器提供相應(yīng)開發(fā)接口,協(xié)助調(diào)度器進行異構(gòu)感知的負載均衡.

本文的主要貢獻如下:

(1) 提出一種新的負載均衡機制S-Bridge,在不修改調(diào)度算法的前提下,在系統(tǒng)層面實現(xiàn)接口和參數(shù),進行處理器核心和工作負載的異構(gòu)性的適配.S-Bridge 最顯著的貢獻是:在異構(gòu)環(huán)境下,可以協(xié)助沒有異構(gòu)支持的調(diào)度器進行快速適配和性能優(yōu)化;

(2) 提出一種新的負載度量模型,在傳統(tǒng)負載度量方法的基礎(chǔ)上進行擴展,基于對任務(wù)運行性能的經(jīng)驗分析,為負載均衡決策提供感知決策;

(3) 在不同的內(nèi)核版本上,針對不同的調(diào)度算法實現(xiàn)S-Bridge,驗證S-Bridge 的有效性和通用性.

本文第1 節(jié)介紹異構(gòu)調(diào)度的相關(guān)工作.第2 節(jié)描述異構(gòu)多核環(huán)境下的負載均衡問題.第3 節(jié)詳細介紹S-Bridge 的設(shè)計與實現(xiàn).第4 節(jié)介紹相關(guān)實驗及結(jié)果討論.第5 節(jié)是結(jié)論及展望.

1 相關(guān)工作

異構(gòu)多核處理器最主要的優(yōu)勢是,不同類型的核心可以滿足不同特定應(yīng)用的需求[1].因此,在任務(wù)調(diào)度時,需要感知異構(gòu)所帶來的計算能力的差異性和任務(wù)特性,為任務(wù)選擇更合適的核心.近年,異構(gòu)支持的調(diào)度優(yōu)化出現(xiàn)很多研究工作,主要從滿足性能[7,11-14,16-21]、能效[22-26]、公平性[15,27,28]等優(yōu)化目標提出調(diào)度算法.由于本文主要是性能為主要優(yōu)化目標,下面將重點介紹已有研究工作.

HASS[18]是靜態(tài)調(diào)度算法,在調(diào)度之前,借助編譯器的反饋優(yōu)化技術(shù)提前對程序進行分析,并在二進制文件中保存架構(gòu)簽名,主要包括程序在不同配置核上的訪存信息,作為程序是否受益大核的依據(jù).文獻[7,11,19]根據(jù)應(yīng)用的運行時狀態(tài)(比如性能事件信息)進行調(diào)度策略的優(yōu)化,文獻[19]通過將線程分配到不同類型核上運行一段時間,周期性地進行IPC 的采樣,根據(jù)在大核和小核上運行的IPC 加速比進行線程的遷移.為了避免IPC 變化所帶來的頻繁遷移,調(diào)度決策依據(jù)歷史IPC 和當前IPC 的加權(quán)平均.文獻[7]建立CPI 棧模型,由核內(nèi)阻塞、核外阻塞和真正執(zhí)行占用的周期數(shù)組成,通過在不同核上采樣證明:當線程CPI 棧以執(zhí)行周期為主時,線程具有大核偏好(BIAS);反之則具有小核偏好.在系統(tǒng)不均衡的情況下,選擇最合適的任務(wù)遷移到目標核上.文獻[11]根據(jù)周期性地統(tǒng)計性能事件(包括LLC 缺失數(shù)、指令數(shù)、指令之間的依賴距離分布等)建立棧模型,結(jié)合硬件的架構(gòu)參數(shù)進行MLP 和ILP 的預測,并根據(jù)預測結(jié)果做出調(diào)度決策.文獻[20]提出一種異構(gòu)感知的負載均衡策略,保證核上運行的負載與核功耗成比例,并通過優(yōu)先使用大核的策略提升系統(tǒng)執(zhí)行性能,通過在線監(jiān)控線程的常駐工作集預測線程遷移的代價,并根據(jù)遷移代價進行線程遷移的優(yōu)化.文獻[21]采用跟文獻[20]相類似的大核優(yōu)先的調(diào)度策略和類似的效果,兩者的主要區(qū)別是,文獻[20]在提升性能的同時保證公平性.文獻[12]基于間隔分析(interval analysis)理論模型,通過動態(tài)獲取程序性能數(shù)據(jù)構(gòu)建CPI 棧來統(tǒng)計線程在不同核上的IPC,并形成以不同CPU 核配置和IPC 組成的性能矩陣作為線程分配和遷移的依據(jù).文獻[13,14]通過指令執(zhí)行由于訪存被阻塞的時間建立棧模型,通過大小核的加速比模型作為調(diào)度的依據(jù).

文獻[15,24]針對動態(tài)異構(gòu)多核處理器,根據(jù)應(yīng)用的運行時狀態(tài)進行處理器參數(shù)的動態(tài)調(diào)整.文獻[15]基于CFS 提出新的HFS(heterogeneity-aware fair scheduler)算法,增加集中式任務(wù)隊列支持邏輯核的快速分配和調(diào)整,同時,進行公平性決策時增加核計算性能的因素,實現(xiàn)在利用異構(gòu)多核性能優(yōu)勢的基礎(chǔ)上保證公平性.但是文獻[15]沒有考慮不同特征應(yīng)用計算資源的需求,而且異構(gòu)的適配需要在CFS 算法的基礎(chǔ)上進行修改.其余工作主要針對靜態(tài)性能非對稱異構(gòu)多核處理器,以下主要針對性能優(yōu)化目標的工作進行分析.文獻[16]提出基于穩(wěn)定匹配算法的調(diào)度技術(shù),維護動態(tài)的線程任務(wù)和核的優(yōu)先級表,作為調(diào)度的依據(jù).文獻[17]提出一種迭代啟發(fā)式調(diào)度算法,在滿足功耗線程的情況下提高吞吐量.

以上工作主要是針對調(diào)度算法本身,程序分析和調(diào)度決策本身具有較強的耦合度,缺乏通用性.而且HASS雖然對于有穩(wěn)定執(zhí)行狀態(tài)的負載,尤其是異構(gòu)度明顯的負載有較好的效果,但最主要的限制是無法感知程序變化的執(zhí)行階段,而且無法考慮運行狀態(tài)(比如共享內(nèi)存狀態(tài))的影響.文獻[7,19]都是IPC 驅(qū)動的動態(tài)調(diào)度算法,需要通過IPC 采樣獲取在不同核上的性能數(shù)據(jù),信息獲取依賴于不同微架構(gòu)的硬件支持,而且隨著核類型的增加,可擴展性也比較差.文獻[11]的性能預測模型從PMC 單元無法直接獲取,需要增加額外硬件支持.同時,文獻[7]雖然通過很少的代碼修改可以在多數(shù)Linux 調(diào)度器上實現(xiàn),但是僅對負載均衡時任務(wù)選擇的策略進行改進和增強.文獻[25]雖然是負載均衡算法的優(yōu)化,但是需要通過修改Linux 內(nèi)核的負載均衡算法加入處理器利用率信息,使動態(tài)調(diào)頻和負載均衡更好地協(xié)同工作.而不同于以上工作提出或者優(yōu)化具體調(diào)度算法的方法,本文從另外一個角度提供一種代理機制,為各種調(diào)度算法提供異構(gòu)的支持.這種機制跟以上工作最顯著的不同是不需要直接修改調(diào)度算法本身,而是基于運行時信息形成規(guī)則影響負載均衡決策,同時提供架構(gòu)無關(guān)的接口與調(diào)度器進行交互,適配不同的調(diào)度器,可以做到平臺無關(guān)性和通用性.

同時,HMP(heterogeneous multi processing)是Linaro 針對big.LITTLE 架構(gòu)開發(fā)的異構(gòu)感知的調(diào)度算法,在實現(xiàn)上與CFS 調(diào)度算法具有相同的入口,重新定義調(diào)度域為大小核兩個域,在此基礎(chǔ)上改進負載均衡策略,將負載重的任務(wù)遷移到大核域內(nèi)執(zhí)行,將負載輕的任務(wù)遷移到小核域內(nèi)執(zhí)行,采用任務(wù)處于可運行狀態(tài)所占用CPU時間比率作為負載輕重的依據(jù).由于HMP 這套機制在2014 年后的成功商業(yè)化,目前大部分big.LITTLE 設(shè)計的移動終端設(shè)備上(比如三星Exynos5430 和5433 等)都采用了HMP 機制.因此,本文實驗部分將優(yōu)化工作與此主流的異構(gòu)調(diào)度器進行比對.由于HMP 調(diào)度器在Linux 內(nèi)核原有負載計算方法上擴展,對于任務(wù)特性的感知在HMP 中沒有考慮,將通過本文的工作對HMP 進行擴展.

2 異構(gòu)多核處理器下的負載均衡問題

2.1 傳統(tǒng)負載均衡的設(shè)計

在主流的Linux 操作系統(tǒng)中,調(diào)度器中的負載平衡針對同構(gòu)多核系統(tǒng)(SMP)設(shè)計,目標是通過在各個核之間均勻分配負載,使各個核之間處于平衡的狀態(tài).傳統(tǒng)負載均衡的實現(xiàn)采用pull 和push 兩種方式進行負載均衡,以pull 方式為例:當前CPU 運行隊列為空的時候,觸發(fā)負載均衡,調(diào)度器將找到負載最重的CPU,并移動該CPU運行隊列中的任務(wù)到空閑核上.其中,所有CPU 都被對稱對待,默認具有相同的處理能力(sched_capacity_scale).每個CPU 工作負載是指運行隊列(runqueue)中所有的線程負載的總和.每個線程負載的度量方法隨著調(diào)度算法的發(fā)展而不斷演化,最初定義為線程的負載權(quán)重(根據(jù)線程的優(yōu)先級定義權(quán)重值),后來發(fā)展為負載跟蹤度量標準(load track metric)[28],根據(jù)歷史負載的衰減來跟蹤負載,但是基礎(chǔ)的負載依然是線程的負載權(quán)重.該度量方法主要基于線程的優(yōu)先級和平均CPU 利用率統(tǒng)計線程的負載.傳統(tǒng)的負載均衡主要基于CPU 對稱性和任務(wù)對稱性的假設(shè),在CFS 調(diào)度算法中,假定相同優(yōu)先級的任務(wù)具有相同的基礎(chǔ)負載權(quán)重,而不會考慮任務(wù)屬性.對于相同優(yōu)先級而且一直占用CPU 的任務(wù),將具有相同的負載、但是優(yōu)先級相同的任務(wù)由于對CPU 資源需求的不同(比如計算密集型和內(nèi)存密集型),在負載均衡的過程中,如果被選擇遷移,不能一視同仁地分配在所有不同類型的目標核上.因此在異構(gòu)多核環(huán)境下,CPU 的處理能力和任務(wù)特性不同對CPU 造成的負載不同且變化.

2.2 負載均衡異構(gòu)適配問題

在異構(gòu)多核處理器環(huán)境中,使用傳統(tǒng)同構(gòu)環(huán)境的負載均衡算法會導致執(zhí)行效率問題.其原因是:異構(gòu)多核處理器是一個相對復雜的架構(gòu)設(shè)計,每種類型的核之間的微架構(gòu)存在差異[8],包括流水線設(shè)計、緩存設(shè)計等差異.以ARM big.LITTLE 設(shè)計(包括ARM Cortex A15 和A7)為例,這兩種類型核在微架構(gòu)方面存在顯著差異.A7(小核)主要用于低功耗處理,采用8～10 級順序(in-order)流水線設(shè)計;A15(大核)主要用于性能處理,采用15～24 級亂序(out-of-order)流水線設(shè)計.微架構(gòu)設(shè)計的不同,導致A15 和A7 的處理能力大不相同,在運行處理器運算能力基準程序Dhrystone 的情況下,A15 可以達到A7 的1.9 倍[4].此外,不同的任務(wù)類型適合運行的核類型也不同.例如:計算密集型任務(wù)更適合在亂序窗口、取指寬度大的亂序核上運行,因此在A15 上受益明顯,更適合遷移到大核上運行;訪存密集型任務(wù)由于訪存延時無法充分利用流水線的并發(fā)設(shè)計,更適合在小核上運行.因此,基于CPU和任務(wù)對稱性假設(shè)下的傳統(tǒng)負載均衡,在異構(gòu)多核處理器上會產(chǎn)生不準確的負載均衡決策.

在目前主流的Linux 操作系統(tǒng)中,針對異構(gòu)處理器環(huán)境下負載均衡問題,有如圖1 所示兩種(Sys1,Sys2)常見的系統(tǒng)狀態(tài).

· 一是圖中Sys1 所描述思路,即繼續(xù)使用為同構(gòu)環(huán)境設(shè)計的經(jīng)典調(diào)度器;這些調(diào)度器可以在異構(gòu)處理器環(huán)境下正常運行,但由于未針對異構(gòu)環(huán)境進行適配,可能出現(xiàn)前文所述的低效情況.因此,操作系統(tǒng)中常用的調(diào)度算法,比如先進先出(FCFS)、時間片輪轉(zhuǎn)(RR)、最高優(yōu)先級(HPF)、完全公平(CFS)等,在異構(gòu)處理器環(huán)境都同樣面臨著異構(gòu)適配的問題;

· 二是圖中Sys2 所述系統(tǒng)狀態(tài),即使用異構(gòu)處理器專用調(diào)度器,其優(yōu)點是對異構(gòu)環(huán)境的適配較好,其缺點是缺乏通用性.

在以上背景下,本研究認為:為異構(gòu)處理器環(huán)境的負載均衡提供系統(tǒng)級的支持,是一種可行的、更為通用的方案.其思路如圖1 中Sys3 所示,使用專用定制的系統(tǒng)級接口以及參數(shù),傳統(tǒng)調(diào)度器也可以有效地與異構(gòu)硬件環(huán)境進行適配,且可以保留原有操作系統(tǒng)調(diào)度機制的通用性.

3 S-Bridge

本文從系統(tǒng)層面提出了一種負載均衡的增強代理機制S-Bridge,其主要思路是:基于針對任務(wù)在不同架構(gòu)類型核上相關(guān)執(zhí)行信息的學習,實現(xiàn)獨立于調(diào)度算法的異構(gòu)感知層.S-Bridge 在系統(tǒng)層面提供接口和參數(shù),通過負載擴展因子對線程的基礎(chǔ)負載進行動態(tài)適配,協(xié)助調(diào)度器的負載均衡進行決策的優(yōu)化,將任務(wù)分配到更加合適的核上運行.

3.1 系統(tǒng)設(shè)計

S-Bridge 的主要思想是:在系統(tǒng)中設(shè)計實現(xiàn)一種增強代理層,在不修改現(xiàn)有負載均衡算法的前提下,設(shè)計一系列異構(gòu)感知的接口和參數(shù),供調(diào)度器使用,協(xié)助負載均衡進行異構(gòu)感知和適配.為了保證S-Bridge 架構(gòu)無關(guān)性,設(shè)計獨立的模塊與硬件交互獲取任務(wù)性能事件(performance monitoring counter,簡稱PMC[29])信息.S-Bridge 總體設(shè)計如圖2 所示,主要核心功能由3 部分組成:架構(gòu)性能收集器、CPU 異構(gòu)配置收集器和規(guī)則生成器.規(guī)則生成器基于一定的模型進行適配規(guī)則的產(chǎn)生,模型是獨立可替換的,本文采用自己提出的可擴展負載模型.

架構(gòu)性能收集器的主要目的是在線程進行上下文切換(比如調(diào)度和遷移)時,對線程的性能數(shù)據(jù)進行收集、分析和預測.它提供一系列回調(diào)函數(shù)用于實現(xiàn)如下功能.

(1) 從硬件性能監(jiān)控計數(shù)器(PMU)獲取性能數(shù)據(jù);

(2) 將這些性能數(shù)據(jù),比如LLC 訪問缺失率、執(zhí)行指令數(shù)和指令的周期數(shù)等,轉(zhuǎn)化為內(nèi)部定義的數(shù)據(jù)結(jié)構(gòu)進行保存;

(3) 基于上面收集的信息進行線程性能數(shù)據(jù)的分析與預測.在線程調(diào)度和遷移的時間點,調(diào)用相應(yīng)的回調(diào)函數(shù).

CPU 異構(gòu)配置收集器提供API 來檢測不同類型CPU 核的參數(shù),如CPU 核ID、緩存大小等,根據(jù)收集的信息設(shè)置CPU 核處理能力的初始值.

規(guī)則生成器主要是接收架構(gòu)性能和CPU 異構(gòu)配置收集器的數(shù)據(jù),基于可擴展負載模型進行規(guī)則的產(chǎn)生.本文主要基于可擴展負載的度量模型計算線程的擴展因子,并更新擴展因子矩陣.擴展因子矩陣用來保存每個線程在不同核上的負載擴展因子,并通過接口傳給調(diào)度器使用,在負載均衡的時候,通過影響線程負載的計算,反映每個線程適應(yīng)異構(gòu)多核處理器環(huán)境的真實負載.同時,出于性能方面的考慮,擴展因子矩陣主要是用來避免對相同任務(wù)性能的重復度量,對于運行的任務(wù),如果在矩陣中已經(jīng)存在相應(yīng)的項,則不再進行度量.

3.2 可擴展負載度量模型

如上所述,S-Bridge 結(jié)構(gòu)的實現(xiàn)基礎(chǔ)是可擴展負載度量模型.如第2.1 節(jié)討論:在同構(gòu)多核環(huán)境下,由于核設(shè)計對稱,傳統(tǒng)基于優(yōu)先級和平均CPU 利用率的負載度量方法不需考慮核處理能力和任務(wù)特性的區(qū)別;然而在異構(gòu)多核環(huán)境下,由于核微架構(gòu)設(shè)計不同,任務(wù)資源需求不同,在不同類型核上的性能表現(xiàn)有很大差異,任務(wù)在各類型核上形成的負載也有差異.以上兩種因素直接影響負載均衡決策,因此,本研究提出一種新的負載度量模型,基于對任務(wù)運行性能的經(jīng)驗分析,在原有負載度量方法的基礎(chǔ)上進行擴展,考慮不同類型核之間處理能力差異(CPU 因子)以及任務(wù)在不同核上的性能差異(任務(wù)因子),從而實現(xiàn)異構(gòu)感知.該模型包括兩個部分.

(1) 任務(wù)的性能模型.基于CPI(cycle per instruction)[30]棧模型對于任務(wù)的計算需求進行度量,即任務(wù)執(zhí)行所有指令的時鐘周期中,真正執(zhí)行(而不是由于訪存或者其他CPU 資源不足所阻塞)所占用的時鐘周期比例被用來表示程序在大核上運行的受益程度;

(2) 負載模型.此模型基于程序性能模型和CPU 核之間處理能力差異進行負載擴展因子的評估.

3.2.1 程序性能模型該性能模型基于CPI 棧分析程序在大核上運行的受益程度.CPI 棧是經(jīng)典的被廣泛采用的微架構(gòu)性能評估模型,CPI 棧主要由基礎(chǔ)執(zhí)行的CPI 和由各種阻塞事件(比如訪存缺失)占用的CPI 組成,因此,通過基礎(chǔ)執(zhí)行的時鐘周期和由于外部阻塞所占用的時鐘周期來計算CPI 棧.如公式(1)所示:

總的CPI由CPIB和CPIS組成:CPIB表示真正用來執(zhí)行指令的周期數(shù),表示用來處理阻塞事件的周期數(shù);CPIS是無法有效利用CPU 的時間.本文通過硬件性能事件程序執(zhí)行的周期數(shù)(cycles)以及指令數(shù)(instructions)比值計算CPI,CPIS通過公式(2)計算:

其中,Mref表示每條指令的評價平均訪存次數(shù);Cmiss表示最后一級緩存(LLC)訪問缺失率;Cpenalty表示緩存訪問缺失所帶來的時間懲罰,Cpenalty等于訪問內(nèi)存延時.

根據(jù)以上定義,CPIB通過1-CPIS計算.本文定義CPI_B表示CPU 計算資源的需求,由CPIB在CPI 棧所占的比例計算而來.為了對性能模型的合理性進行評估,本節(jié)針對CPU SPEC2006 的41 個測試程序進行了實驗.圖3 表示所有測試程序的CPI 棧信息與加速比的關(guān)系,可以發(fā)現(xiàn):程序的CPI_B和加速比的曲線具有非常相似的趨勢,CPIB高的測試程序具有高的加速比,表明通過采用CPIB來表示程序?qū)τ诖蠛说氖芤娉潭葟亩脕砉烙嬋蝿?wù)因子這種方法是可行且合理的.在圖3 中:兩條豎直虛線之前的區(qū)域與趨勢存在偏離,此區(qū)域中的程序集中為不同輸入集的gcc 程序,由于輸入集的不同造成了CPI 棧信息的差異.為了避免這種噪聲的影響,本文將所有程序的加速比范圍劃分為0.1 的區(qū)間,在進行任務(wù)因子估計的時候,在同一區(qū)間的程序具有相同的任務(wù)因子值.

3.2.2 負載模型

負載模型基于程序性能模型和CPU 核之間處理能力的差異進行負載擴展因子的計算.CPU 因子表示異構(gòu)多核處理器中,不同核之間處理能力的比值;任務(wù)因子表示不同類型任務(wù)之間CPI_B的比值.假設(shè)將APPm在Corek上的擴展負載因子作為參考,APPi在Corej上的擴展因子計算如公式(3)所示:

3.3 實 現(xiàn)

本研究在ARM big.LITTLE 平臺(Cubieboard4 CC-A80)運行的Linux 內(nèi)核3.4 版本上對S-Bridge 進行了實現(xiàn).同時,為證明S-Bridge 的通用性和可移植性,在X86 平臺(Intel Core? i7-2600K)運行的Linux 內(nèi)核3.13 版本也進行了實現(xiàn).

S-Bridge 提供一系列接口與調(diào)度器交互,在創(chuàng)建、調(diào)度或遷移線程的時候,通過S-Bridge 架構(gòu)性能收集器的接口進行線程性能數(shù)據(jù)的收集,基于可擴展負載均衡模型進行經(jīng)驗分析,并通過規(guī)則生成器生成的參數(shù)對線程的負載進行動態(tài)擴展,將線程分配到更加適合的核上運行.CPU 異構(gòu)配置收集器提供接口獲取或設(shè)置CPU 核處理能力的值,由于平臺大小核具有確定的微架構(gòu)參數(shù),本文對表示大小核之間處理能力差異的CPU 因子提前測試并進行初始化.其中,較為核心的架構(gòu)性能收集器部分主要功能通過以下回調(diào)函數(shù)進行實現(xiàn).

(1)do_fork和do_exec:當線程被直接創(chuàng)建或者調(diào)用exec(?)新建的時候,該函數(shù)為每個新建立的線程分配并初始化相應(yīng)的數(shù)據(jù)結(jié)構(gòu),比如用來保存架構(gòu)性能數(shù)據(jù)的結(jié)構(gòu),在擴展因子矩陣中分配相應(yīng)的項,并將該線程的擴展因子的初始值設(shè)置為1,這個值表示在做負載均衡的時候不會對線程的負載有任何影響,還是保持原有的基礎(chǔ)負載;

(2)do_migration:在負載均衡的時候,當線程被遷移時,線程的性能數(shù)據(jù)被實時地更新.該函數(shù)中,讀取性能數(shù)據(jù)的接口通過內(nèi)核監(jiān)控模塊的加載進行初始化;

(3)do_statistic:基于歷史的性能數(shù)據(jù)進行分析和預測.為了簡化,這個函數(shù)在將來的工作中被定義和擴展;

(4)factor_gen:根據(jù)擴展負載的度量模型生成線程的擴展因子,并更新擴展因子矩陣相應(yīng)線程的項.擴展因子矩陣里主要包括產(chǎn)生縮放因子的基礎(chǔ)上可擴展的負載度量模型和更新的縮放因子矩陣相應(yīng)的條目.每個條目的信息包括CPU 核類型、任務(wù)名稱、不同階段的負載因子等信息.

S-Bridge 為了做到獨立和架構(gòu)無關(guān)性,硬件性能數(shù)據(jù)的獲取通過專門的內(nèi)核監(jiān)控模塊來實現(xiàn),用來訪問和讀取底層硬件性能事件計數(shù)器,在架構(gòu)性能收集器的回調(diào)函數(shù)只是對全局讀取函數(shù)的指針進行初始化,當內(nèi)核模塊加載的時候,會對函數(shù)指針進行賦值.在實現(xiàn)過程中,由于ARM 平臺的PMU 性能事件支持尚未完備,需要在3.4 內(nèi)核中增加對于特定硬件事件的支持,具體包括訪存缺失數(shù)、分支預測錯誤數(shù)等.

4 實 驗

4.1 實驗?zāi)繕伺c設(shè)置

在本節(jié)中,由于S-Bridge 最突出貢獻是在不修改調(diào)度算法本身的前提下,協(xié)助異構(gòu)多核處理器環(huán)境下沒有異構(gòu)支持的調(diào)度器進行快速適配和性能優(yōu)化;同時,S-Bridge 是獨立的架構(gòu)無關(guān)的負載均衡代理層,具有方便的移植性,適用于不同的調(diào)度器,因此,實驗擬分別在ARM 和X86 平臺上對S-Bridge 的有效性和通用性進行評估,實驗對象是主流的調(diào)度器CFS(沒有異構(gòu)感知)和HMP(異構(gòu)感知)算法.

(1) 針對非異構(gòu)感知的調(diào)度算法S-Bridge 的有效性

本文在big.LITTLE 設(shè)計的ARM 平臺上,以目前Linux 中主流的CFS 調(diào)度算法為實例進行S-Bridge 支持前后的對比實驗.實驗基于UltraOcta A80 處理器的ARM 平臺,包括Cortex-A15(指定為大核,縮寫為B)和Cortex-A7(指定為小核,縮寫為S)兩種類型的核,如第2.2 節(jié)描述,兩種核具有不同的微架構(gòu)設(shè)計,分別適用于高性能和低功耗的場景,大小核的頻率分別為1.608G 和0.72G.該平臺運行的內(nèi)核版本為Linux kernel 3.4.

(2) S-Bridge 方法的通用性

除了情形(1)中的ARM 平臺上,本文同時在運行不同Linux 內(nèi)核版本的X86 平臺上進行對比實驗.實驗基于Intel 4 核心處理器(Core? i7-2600K),雙線程的X86 處理平臺.跟ARM 不同的是,由于4 個核的微架構(gòu)設(shè)計相同,本實驗主要通過設(shè)置不同的時鐘頻率來體現(xiàn)核的異構(gòu)性,頻率主要包括3.2G(指定為大核,縮寫為B)和1.6G(指定為小核,縮寫為S).該平臺運行的內(nèi)核版本為Linux kernel 3.13.

(3) S-Bridge 跟主流異構(gòu)調(diào)度算法的對比

本文選擇big.LITTLE 平臺上主流的HMP 負載均衡算法作為實例進行S-Bridge 支持前后的對比實驗,分析在已經(jīng)異構(gòu)適配的調(diào)度算法上的效果和影響,同時與HMP 對比進行S-Bridge 潛在限制的分析.實驗采用與情形(1)相同的平臺.

本文主要選擇1B-1S,1B-3S 和3B-1S 這3 種平臺進行實驗.如表1 所示:在實驗中采用的工作負載主要由不同特性的單線程(比如相對訪存多和相對計算多)程序隨機混合組成,在實驗平臺上同時并發(fā)地執(zhí)行.這些程序分別選自SPEC CPU2006[31]和MiBench[32]測試套件,SPEC CPU2006 主要針對X86 平臺,而Mibench 主要針對ARM 平臺.

Table 1 ARM 和X86 平臺工作負載的混合測試程序表1 ARM 和X86 平臺的多程序隨機混合負載

S-Bridge 的效果,通過工作負載中的所有測試程序在原始調(diào)度算法和帶有S-Bridge 的調(diào)度算法兩種情況下的執(zhí)行時間加速比進行衡量.測試時,為了減少系統(tǒng)線程的影響,一方面盡可能地關(guān)閉運行的系統(tǒng)線程;另一方面,通過重復執(zhí)行數(shù)百次工作負載,計算負載中每個程序的平均執(zhí)行時間加速比.測試程序的性能數(shù)據(jù)主要通過PMC 記錄硬件性能事件,包括程序運行的指令數(shù)、周期數(shù)和LLC 缺失數(shù)等.如第4.3.1 節(jié)討論,由于時鐘頻率差異也是影響CPU 處理能力差異的因素,實驗平臺中每個核的頻率通過CPUFreq[33]技術(shù)被設(shè)置為固定的頻率.

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

4.2.1 ARM 平臺上S-Bridge 對于CFS 調(diào)度算法的效果

如圖4(實驗平臺為ARM 1B-1S,大小核的頻率分別為1.608G 和0.72G,內(nèi)核版本為3.4)和圖5 所示(實驗平臺為ARM 3B-1S,大小核的頻率分別為1.608G 和0.72G,內(nèi)核版本為3.4):當S-Bridge 使能時,所有程序的平均性能提升超過約68.4%;對于個別執(zhí)行時間特別短的程序(比如search_large)達到100%.

在程序運行過程中,更加適合在大核上運行的程序由于獲得較多在大核上運行的機會而有相對明顯的性能提升,比如patricia_l 總體性能提升約71.4%;而對于更加適合在小核上運行的程序rijndael_s 性能提升約50.5%,而且它本身執(zhí)行時間也比較短.對于適合在大核上運行的執(zhí)行時間短的程序比執(zhí)行時間長的程序效果明顯,由于伴隨部分程序執(zhí)行結(jié)束,系統(tǒng)的整體負載下降,會影響到S-Bridge 效果,S-Bridge 在系統(tǒng)負載重的情況下效果會更加明顯.1B-1S 和3B-1S 有相似的效果趨勢,平均性能提升均超過70.3%.基于相同的CFS 調(diào)度算法,相比于在X86 平臺(如圖6 和圖7 所示),S-Bridge 在ARM 平臺上效果更加明顯,因為ARM 平臺上不同類型的CPU 核微架構(gòu)差異更大,而X86 平臺上僅是頻率的差異.因此,實驗結(jié)果總結(jié)如下.

· 基于CFS,S-Bridge 集成后在很大程度上減少了異構(gòu)環(huán)境下調(diào)度的隨機性,所有程序的平均執(zhí)行性能均有明顯的提升.S-Bridge 對于沒有考慮異構(gòu)的調(diào)度算法效果明顯;

· S-Bridge 在系統(tǒng)負載重的情況下效果會更加明顯;

· S-Bridge 對于微架構(gòu)差異大的異構(gòu)處理器效果會更加明顯.

4.2.2 S-Bridge 的通用性(X86 平臺)評估

圖6(實驗平臺為X86 1B-1S,大小核的頻率分別為3.2G 和1.6G,內(nèi)核版本為3.13)和圖7(實驗平臺為X86 1B-3S,大小核的頻率分別為3.2G 和1.6G,內(nèi)核版本為3.13)表示表1 中的X86 工作負載在Intel 處理器上的平均執(zhí)行時間及執(zhí)行時間的加速比:當S-Bridge 使能的時候,所有程序的平均性能超過15%.最好的情況下,性能提升超過35%.比如:以計算為主更加受益于在大核上運行的程序hmmer 和bzip2;但是以訪存為主無法明顯從大核受益的程序,比如mcf 的性能提升約有11%,不是特別的明顯.1B-3S 的情況下,有些測試程序沒有被調(diào)度到大核上運行導致了性能的下降,比如gcc,性能下降約28%,milc 性能下降約3%.由于X86 的測試程序運行時間都比較長,本文對程序特性階段的變化沒有進行細粒度學習和預測,對于gcc 這種執(zhí)行計算和訪存交替變換的程序,本應(yīng)在大核執(zhí)行的階段沒有及時被調(diào)度,性能的提升會受到影響.

4.2.3 S-Bridge 跟主流異構(gòu)調(diào)度器的對比

本文以big.LITTLE 處理器架構(gòu)下的主流調(diào)度器HMP 為基準進行S-Bridge 效果的實驗與對比,主要包括:

(1) S-Bridge 對HMP 的影響

圖8(實驗平臺為ARM 1B-1S,大小核的頻率分別為1.608G 和0.72G,內(nèi)核版本為3.4)表示測試程序的平均執(zhí)行時間和執(zhí)行時間的加速比:當S-Bridge 使能時,所有程序的平均性能提升約2.3%.最好情況下,basicmath_s性能提升約6%.其中有3 個測試程序(lout_l,toast_l,rawcaudio_l)的性能略有下降,分別約為0.37%,2.75%,2.51%.

當S-Bridge 使能的時候,針對HMP 調(diào)度算法雖然有效果,但整體不是特別的明顯.在實驗中,HMP 算法通過S-Bridge 模型進行不同任務(wù)類型的適配.但是由于S-Bridge 中對于任務(wù)的階段類型沒有進行細粒度學習和預測,所以會影響到任務(wù)因子的適應(yīng)性.在結(jié)果上,對于明顯受益大核(比如basicmath_s 和qsort_large),效果會相對明顯;但是對于比如toast_l 和rawcaudio_l 這樣的程序,整個程序沒有特別明顯地以計算密集或者訪存密集為主,而是階段交替性出現(xiàn)不同的程序特征,由于階段類型預測的自適應(yīng)性沒有支持,所以會影響到任務(wù)因子的評估而影響到調(diào)度決策.在某個執(zhí)行階段,本該調(diào)度到大核執(zhí)行,反被分配到小核,從而導致程序性能不升反降.在后面的工作中,會繼續(xù)對任務(wù)階段特性進行學習和預測.

(2) 在同構(gòu)工作負載下S-Bridge 與HMP 的對比

圖9 表示在完全同構(gòu)的負載場景下,沒有異構(gòu)支持的原始CFS、使能S-Brige 的CFS 以及HMP 工作情況下,工作負載執(zhí)行完成的時間對比(同構(gòu)負載的程序主要來自 Mibench 中以訪存為主的測試程序,比如rijndael_s,rawcaudio_s 等.相比專門的異構(gòu)調(diào)度器HMP,S-Bridge 沒有明顯效果.實驗平臺為ARM 1B-1S,大小核的頻率分別為固定頻率(1.608G～0.72G)和動態(tài)調(diào)頻,內(nèi)核版本為3.4).

負載的程序從Mibench 中選擇以訪存為主的同類程序(比如crc_l,rijndael_s,rawcaudio_s 等).在固定頻率情況下,相比于原始CFS 約有5%的性能提升.而在DVFS 情況下,由于大核和小核的頻率在運行過程中伴隨負載而變化,會導致CPU 因子設(shè)置的不合理,從而影響調(diào)度效果(具體會在第4.3.1 節(jié)討論),相比于原始CFS 反倒略下降(加之考慮到本身的系統(tǒng)開銷).在此種情況下,沒有HMP 的效果明顯,HMP 主要有針對性地將占用CPU 時間長(超過預先設(shè)定的閾值)的任務(wù)遷移到大核上執(zhí)行.

在S-Bridge 中,對于任務(wù)的階段類型沒有進行細粒度學習和預測,所以會影響到任務(wù)因子的適應(yīng)性和靈敏度,而且工作負載如果完全是同類型訪存為主的任務(wù),S-Bridge 會考慮盡量將任務(wù)留在小核執(zhí)行,從而無法充分利用大核資源.因此,S-Bridge 在后面需要考慮CPU 因子根據(jù)頻率變化自適應(yīng)學習以及任務(wù)階段類型的細粒度學習和預測.

第4.2 節(jié)的實驗結(jié)果總體表明:

(1) S-Bridge 對于沒有考慮異構(gòu)支持的調(diào)度算法效果明顯,很大程度上減少了異構(gòu)環(huán)境下調(diào)度的隨機性;而且S-Bridge 對于微架構(gòu)差異大的異構(gòu)處理器效果會更加明顯;

(2) S-Bridge 可以方便地在不同平臺和內(nèi)核版本上進行移植和實現(xiàn),對不同版本的調(diào)度器起到異構(gòu)適配的效果;

(3) S-Bridge 能夠與目前主流的異構(gòu)調(diào)度算法(比如HMP)協(xié)同工作,對HMP 的任務(wù)類型適配性進行優(yōu)化有一定的效果.但是在完全異構(gòu)的工作負載場景下,影響S-Bridged 的異構(gòu)適配效果.

4.3 討 論

本節(jié)圍繞以下3 個方面進行討論:一是CPU 因子設(shè)置(實驗中采用了經(jīng)驗值)對S-Bridge 效果的影響;二是微架構(gòu)差異(實驗中采用頻率設(shè)置差異)對于S-Bridge 效果的影響;三是S-Bridge 的系統(tǒng)開銷.

4.3.1 CPU 因子設(shè)置對S-Bridge 效果的影響

在固定頻率的情況下,CPU 因子的設(shè)置是否能反映不同核之間的處理能力差異,對于S-Bridge 的效果影響至關(guān)重要.圖10 表示:在大核和小核頻率為1.608G～0.72G 的時候,S-Bridge 在CPU 因子設(shè)置為1.5 的情況下性能最優(yōu)(本實驗中,當CPU 因子為1.5 性能提升最明顯,說明1.5 合理反映了大小核處理能力的差異);而CPU 因子為2 和2.5 的時候,由于對于CPU 處理能力差異性評估的不合理,會導致大核負載過重而影響性能,而且會造成任務(wù)在大核和小核之間的遷移顛簸.因此,不合理的CPU 因子會嚴重影響S-Bridge 的效果,甚至起到負效果.

4.3.2 微架構(gòu)差異對于S-Bridge 效果的影響

本節(jié)通過設(shè)置大小核不同的時鐘頻率進行實驗,討論微架構(gòu)差異對于S-Bridge 的影響.圖11 表示ARM 平臺上大核和小核之間不同的時鐘頻率設(shè)置下所有測試程序加速比的分布,大核設(shè)置固定頻率為1.608G,小核的頻率設(shè)置范圍為0.48G～1.104G.結(jié)果表示:S-Bridge 在大核和小核頻率為1.608G～0.72G 的時候性能最優(yōu),所有程序的平均性能約65%,有50%的程序性能提升超過70%;而在大核和小核頻率為1.608G～0.48G 效果相對較差,平均約有10%的性能提升.由于兩個核的處理能力相差最大,在負載均衡的時候,更多的任務(wù)被遷移到大核上執(zhí)行,會出現(xiàn)大核在忙、而小核出現(xiàn)空閑的情況,這也是S-Bridge 后續(xù)要繼續(xù)考慮改進的情況.

4.3.3 S-Bridge 的系統(tǒng)開銷

如第3.3 節(jié)所述,S-Bridge 在原有Linux 系統(tǒng)上的增強實現(xiàn)主要包括與調(diào)度器交互接口和與硬件性能事件寄存器(PMC)交互的部分.調(diào)度器在進行上下文切換(調(diào)度周期到達、新建任務(wù)、喚醒任務(wù)、任務(wù)遷移)時,進行任務(wù)性能信息的統(tǒng)計與分析,生成擴展的負載均衡規(guī)則.伴隨著所調(diào)度任務(wù)數(shù)量的增加及任務(wù)大小的增加,任務(wù)上下文切換次數(shù)增加,因此,S-Bridge 實現(xiàn)的時間復雜度與調(diào)度算法時間復雜度相同.以CFS 調(diào)度算法為例,復雜度為O(n),本身與調(diào)度器交互并不會帶來太大的開銷.另外,與硬件交互的部分主要是訪問PMCs 和特定的內(nèi)核數(shù)據(jù)結(jié)構(gòu),用來保存每個新線程的性能信息.文獻[34]的實驗表明,與硬件交互的開銷一般少于1 000 個時鐘周期(對于程序執(zhí)行來說,時間的影響微乎其微),這對于內(nèi)核對調(diào)度處理的開銷來說是非常小的影響.

本文根據(jù)上面的分析進行實驗,主要針對原始的CFS 算法和S-Bridge 使能情況下的CFS 算法的性能進行對比,跟第4.2 節(jié)實驗不同的是:S-Bridge 的各個組件都在工作,但是無效S-Bridge 生成的規(guī)則,使其不對調(diào)度決策產(chǎn)生任何影響,因此原始CFS 算法與S-Bridge 生效的CFS 算法由于調(diào)度對程序執(zhí)行的影響應(yīng)該沒有差異.選取的測試工作負載是并發(fā)執(zhí)行10 000 次的空函數(shù),在頻率固定的核上運行,在原始CFS 算法的場景下,工作負載完成的時間690.07s,在S-Bridge 使能的情況下為692.35s.由于單次執(zhí)行空函數(shù)的時間少于0.008s,由于系統(tǒng)進程的影響,在工作負載執(zhí)行階段所發(fā)生的上下文切換將大于幾十萬次,由此驗證S-Bridge 對于每次切換所造成的開銷影響是比較小的.

5 結(jié) 論

本文針對異構(gòu)多核處理器環(huán)境中傳統(tǒng)負載均衡問題,提出了一種新的負載均衡代理機制S-Bridge.該方法的核心思想是:在系統(tǒng)層面提出異構(gòu)感知的接口和參數(shù),在不修改具體調(diào)度算法的前提下,協(xié)助已有調(diào)度器進行異構(gòu)環(huán)境的適配,提高所有可替換調(diào)度器在異構(gòu)處理器環(huán)境的決策正確性;同時,為調(diào)度器開發(fā)提供異構(gòu)接口支持.本文對S-Bridge 在不同內(nèi)核版本的ARM 和X86 平臺上進行實現(xiàn)和驗證,實驗表明:在適配未針對異構(gòu)處理器優(yōu)化的調(diào)度算法時,S-Bridge 具有明顯效果,平均性能提升超過15%,部分情況下可超65%;而且,S-Bridge 與HMP 適配時仍繼承了HMP 本身的優(yōu)化效果,并且在此基礎(chǔ)上進行不同任務(wù)類型的適配.但是與HMP 這種專用調(diào)度器相比,在完全同構(gòu)負載的情況下,S-Bridge 效果并不明顯.所以,如何同時發(fā)揮S-Bridge 平臺特性以及HMP等異構(gòu)環(huán)境專用調(diào)度器的優(yōu)勢,獲得進一步調(diào)度優(yōu)化,以及結(jié)合動態(tài)電源管理技術(shù)(比如DVFS)向能效的擴展,是本研究未來的工作方向.而且,伴隨著人工智能,邊緣、近似計算等技術(shù)的興起,數(shù)據(jù)融合的時代已經(jīng)到來,即使在移動終端也要進行媒體信息識別和處理,對于系統(tǒng)的能效要求越來越高.除了單一指令集(single ISA)異構(gòu)系統(tǒng),也出現(xiàn)通用處理器(CPU)和加速協(xié)處理器(GPU、DSP、媒體處理器等)協(xié)同的異構(gòu)指令集(Heterogeneous ISA)系統(tǒng)[35],協(xié)處理器主要滿足特定需求和目標;同時,由于應(yīng)用執(zhí)行階段特性的不同,對于指令級的親和度也不同,有另外一種將通用CPU 指令集混成發(fā)揮各自優(yōu)勢的研究思路,比如ARM 和X86[36]、ARM 和精簡的專用ARM指令集[37]等,以滿足不同需求.總之,異構(gòu)系統(tǒng)在向著多樣化和“術(shù)業(yè)有專攻”的方向發(fā)展,這也為操作系統(tǒng)、編譯器、運行環(huán)境等基礎(chǔ)軟件提出了更多挑戰(zhàn),也是本文異構(gòu)調(diào)度優(yōu)化擴展延伸的方向.