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

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

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

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

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

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

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

本文的主要貢獻如下:

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

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

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

本文第1 節介紹異構調度的相關工作.第2 節描述異構多核環境下的負載均衡問題.第3 節詳細介紹S-Bridge 的設計與實現.第4 節介紹相關實驗及結果討論.第5 節是結論及展望.

1 相關工作

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

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

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

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

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

2 異構多核處理器下的負載均衡問題

2.1 傳統負載均衡的設計

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

2.2 負載均衡異構適配問題

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

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

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

· 二是圖中Sys2 所述系統狀態,即使用異構處理器專用調度器,其優點是對異構環境的適配較好,其缺點是缺乏通用性.

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

3 S-Bridge

本文從系統層面提出了一種負載均衡的增強代理機制S-Bridge,其主要思路是:基于針對任務在不同架構類型核上相關執行信息的學習,實現獨立于調度算法的異構感知層.S-Bridge 在系統層面提供接口和參數,通過負載擴展因子對線程的基礎負載進行動態適配,協助調度器的負載均衡進行決策的優化,將任務分配到更加合適的核上運行.

3.1 系統設計

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

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

(1) 從硬件性能監控計數器(PMU)獲取性能數據;

(2) 將這些性能數據,比如LLC 訪問缺失率、執行指令數和指令的周期數等,轉化為內部定義的數據結構進行保存;

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

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

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

3.2 可擴展負載度量模型

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

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

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

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

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

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

根據以上定義,CPIB通過1-CPIS計算.本文定義CPI_B表示CPU 計算資源的需求,由CPIB在CPI 棧所占的比例計算而來.為了對性能模型的合理性進行評估,本節針對CPU SPEC2006 的41 個測試程序進行了實驗.圖3 表示所有測試程序的CPI 棧信息與加速比的關系,可以發現:程序的CPI_B和加速比的曲線具有非常相似的趨勢,CPIB高的測試程序具有高的加速比,表明通過采用CPIB來表示程序對于大核的受益程度從而用來估計任務因子這種方法是可行且合理的.在圖3 中:兩條豎直虛線之前的區域與趨勢存在偏離,此區域中的程序集中為不同輸入集的gcc 程序,由于輸入集的不同造成了CPI 棧信息的差異.為了避免這種噪聲的影響,本文將所有程序的加速比范圍劃分為0.1 的區間,在進行任務因子估計的時候,在同一區間的程序具有相同的任務因子值.

3.2.2 負載模型

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

3.3 實 現

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

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

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

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

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

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

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

4 實 驗

4.1 實驗目標與設置

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

(1) 針對非異構感知的調度算法S-Bridge 的有效性

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

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

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

(3) S-Bridge 跟主流異構調度算法的對比

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

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

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

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

4.2 實驗結果與分析

4.2.1 ARM 平臺上S-Bridge 對于CFS 調度算法的效果

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

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

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

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

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

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

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

4.2.3 S-Bridge 跟主流異構調度器的對比

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

(1) S-Bridge 對HMP 的影響

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

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

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

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

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

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

第4.2 節的實驗結果總體表明:

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

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

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

4.3 討 論

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

4.3.1 CPU 因子設置對S-Bridge 效果的影響

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

4.3.2 微架構差異對于S-Bridge 效果的影響

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

4.3.3 S-Bridge 的系統開銷

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

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

5 結 論

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