趙 姍,楊秋松,李明樹

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

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

現代的計算機處理系統(tǒng)呈現多樣化趨勢,從手持設備、筆記本電腦到集群系統(tǒng)、大規(guī)模數據中心,無不如此.同時,隨著人工智能、深度學習、大數據等技術的出現,應用程序日趨多樣和復雜,比如多媒體、視覺和語音識別、自然語言處理、數據并行處理等,應用程序呈現出不同的程序特性和資源需求.因此,針對單一的處理器結構,即使微架構設計經過充分的優(yōu)化也無法同時滿足多樣化的應用需求,比如實現更深的流水線,增加更多計算資源(比如執(zhí)行單元),采用優(yōu)化的緩存架構,采用同時多線程技術等等.由于設計在功耗、面積、成本等方面的限制,傳統(tǒng)摩爾定律的效果不再明顯,即使芯片同一面積可以容納越來越多的元器件,功耗也成為不可逾越的障礙.傳統(tǒng)的芯片改進技術(比如通過提高元器件密度增加處理核心數目,對各種功能單元的算法優(yōu)化)在不久的將來將不再具有優(yōu)化效果.因此,半導體制造產業(yè)需要探索更復雜的架構級優(yōu)化來滿足芯片高性能低功耗的發(fā)展需求,而異構技術可以有效補償半導體技術的這些限制,以滿足多樣的應用程序需求[1].

異構多核處理器將不同類型的處理核心(core)集成在處理器芯片中,以滿足高性能和低功耗的需求.比如:ARM采用big.LITTLE大小核切換技術將高性能的Cortex A15和低功耗的A7橋接在一起,根據不同應用的需求選擇不同的核心處理;Intel新一代處理器產品,SandyBridge和Xeon phi將通用的CPU和GPU集成在一起處理多樣化的應用需求,采用少數發(fā)射帶寬大的亂序(out-of-order)CPU核心提供高性能計算,結合大量發(fā)射帶寬小的順序(in-order)GPU提供高并發(fā)低功耗計算.文獻[2]設計了一種新的處理器架構,不同的處理核心具有不同的指令集架構(instruction set architecture,簡稱ISA),支持Thumb、X86-64和Alpha這3種,與單一指令集的多核處理器架構相比,分別具有21%左右的性能提升和23%的功耗下降.因此,異構多核處理器的多個核具有不同的微架構,支持不同的 ISA,每個處理核心具有不同的特性,比如支持較高的指令級并行(instruction level parallelism,簡稱ILP)、內存級并行(memory parallel parallelism,簡稱MLP)或者由于設計得簡單,支持線程高并發(fā)低功耗,這些處理核心協同工作來滿足不同應用的多樣化需求,從而能夠滿足處理系統(tǒng)的優(yōu)化目標,比如高性能、低功耗或者良好的性能功耗比.

因此,伴隨著異構多核處理器的處理核心類型的多樣化,設計和實現復雜度增加,傳統(tǒng)的運行于同構多核處理器上的軟件環(huán)境(如:操作系統(tǒng)、編譯器、運行環(huán)境)無法對其進行很好的管理,充分發(fā)揮異構多核處理器的特性和優(yōu)勢.作為應用和資源管理的重要組件,任務調度在異構多核環(huán)境下的實現變得更加復雜,需要充分考慮異構處理器系統(tǒng)的核間差異,針對應用的特性分析,根據應用需求進行線程的優(yōu)化分配.近些年來,在異構多核處理器領域中針對任務調度的優(yōu)化出現了不少的研究工作,本文主要針對異構感知的調度優(yōu)化技術進行系統(tǒng)的總結.

本文總結的研究工作主要基于性能非對稱性多核處理器,首先根據處理核心設計及功能的差異,對異構多核處理器進行分類,并重點總結性能非對稱性多核處理器的特性和功能.然后對異構多核處理器環(huán)境下調度面臨的主要問題與挑戰(zhàn)展開分析,最主要的問題是如何感知微架構和程序特性的差異,并根據優(yōu)化目標采用相對最優(yōu)的任務分配和遷移策略.因此,本文圍繞異構調度主要技術的 4個方面,包括優(yōu)化目標、分析模型、調度決策和算法評估已有工作加以詳述.最后,分析異構處理系統(tǒng)未來發(fā)展的多樣性和復雜性,這些復雜的異構系統(tǒng)為調度技術提出更為復雜的環(huán)境和需求.對異構感知的調度技術與微架構深度融合的工作進行簡要的總結與展望,為了更好地適配和管理異構硬件,不僅僅是調度算法,與之相關的操作系統(tǒng)及相關軟件都有很多工作值得去探索.

1 異構多核處理器定義與分類

異構多核處理器又被稱作非對稱多核處理器(asymmetric multicore processor,簡稱AMP),如圖1(b)所示,除了處理器的電源、中斷控制器、總線等其他片上結構暫且忽略,每個核的設計主要包括指令集架構(ISA)設計、流水線(pipeline)設計、緩存系統(tǒng)和用來訪問內存的集成控制器(MC).與同構多核處理器(如圖 1(a)所示)不同,異構多核處理器的每個核具有不同的微架構設計和實現,差異主要包括:

(1) 指令集架構差異:處理器每個核最核心的功能是對指令進行正確的譯碼和執(zhí)行,不同核實現的指令集不同,比如X86指令集、ARM指令集和GPU特有的指令集,支持執(zhí)行的程序也不同.文獻[2]通過對Arm Thumb、x86-64和Alpha這3種指令集架構混合設計的空間探索,證明相比于單一指令集異構處理器,支持不同指令集可以提供更高的性能或者能效.

(2) 流水線差異:流水線設計是提高指令級并行(ILP)、有效利用處理器資源的關鍵,從 Intel處理器架構的發(fā)展來看,i486處理器引入了5級流水線,奔騰處理器擴展到12級流水線,2013年的Haswell有16級流水線,而且除了流水級數的擴展外,Intel各代產品在流水線設計中增加了超標量(superscalar)、亂序(out-of-order)、超線程等技術,使得處理器性能不斷提升.而異構處理器中為了滿足不同需求,每個核采用不同的流水線設計,比如復雜串行的任務適合在支持超標量、亂序的深度流水線執(zhí)行,簡單并行的任務適合在順序執(zhí)行的簡單流水線執(zhí)行.同時,流水線的微架構設計也存在差異,比如:取指帶寬(fetch width)不同,分支預測單元(BPU)的大小和算法不同,執(zhí)行單元的數目和端口不同,亂序窗口大小不同,主要包括發(fā)射帶寬(issue width)、分配帶寬(dispatch width)、重排序隊列(ROB)、保留站(RS)等.

Fig.1 The structure of homogeneous and heterogeneous multicore processors圖1 同構和異構多核處理器結構

(3) 緩存系統(tǒng)差異:緩存系統(tǒng)的設計直接決定程序訪存的帶寬和效率,差異主要是緩存系統(tǒng)的架構層級,每級緩存的大小(size)、關聯方式(associativity)和數據包含關系(inclusive或者exclusive),所采用的預取策略、替換算法、回寫策略等,對于訪存密集型的應用,需要使用復雜的緩存系統(tǒng)以更好地支持內存級并行(MLP).

如表 1所示,根據以上特性所呈現的差異,本文將異構多核處理器劃分為性能非對稱多核處理器、功能非對稱多核處理器和動態(tài)多核處理器.動態(tài)(可配置)多核處理器是在保持現有核內部設計實現異構的新技術,文獻[3]提出一種可動態(tài)配置的異構多核架構(Bahurupi),可以動態(tài)地將兩個或者更多簡單的小核(比如亂序兩發(fā)射)達到大核執(zhí)行的效果(比如亂序四發(fā)射),通過提供更強的指令級并行來提高程序中串行代碼的執(zhí)行性能.由于設計和實現比較復雜,目前市場上還沒有產品出現.

Table 1 The category of asymmetric multicore processors表1 異構多核處理器分類

功能非對稱多核處理器在市場上以 CPU-GPU為主要代表,CPU-GPU結構利用專門化的硬件對特定的工作負載(比如簡單高并發(fā)處理的程序或者代碼片段)提供加速支持,見表1,不同類型核之間在架構設計上不共享地址空間,不允許在程序的任意執(zhí)行點隨意進行核之間的遷移,不同核之間的協同工作需要編程環(huán)境支持.

本文主要對性能非對稱多核處理器的調度優(yōu)化技術進行總結與探討,性能非對稱多核處理器一般將高性能、較高功耗的核和低功耗、性能較低的核集成在一塊處理器芯片中,為不同需求的應用程序提供服務.不同類型的核可以按照性能和復雜度進行排序和比較.目前典型的性能非對稱處理器結構是 ARM big.LITTLE結構,通過SoC設計將高性能處理器和低功耗處理器集成協同工作,比如三星Samsung Exynos 9系列處理器.如表2所示的一種big.LITTLE設計[4],將Cortex A15和A7集成在一起,A15和A7在流水線設計、發(fā)射和取指寬度、Cache大小等微架構參數存在設計上的差異,這種高性能聯合低功耗 CPU核的異構設計可以在明顯降低平均功耗的情況下提供高性能處理能力.ARM big.LITTLE架構在對性能要求不是特別高的應用場景下可以節(jié)省約75%的功耗,在高負載的應用場景下可以提升約40%的性能.

Table 2 The micro-architecture configuration of Cortex A15&A7表2 Cortex A15&A7的微架構參數

本文調度優(yōu)化工作中涉及的大核指的是微架構實現復雜、高性能的核,比如Cortex A15,小核則是微架構實現相對簡單但是功耗低的核,比如Cortex A7.本文統(tǒng)一采用線程來描述調度的粒度,因為無論是多線程程序、單線程程序還是多進程程序,最終在計算系統(tǒng)里都是以單個或者多個線程的形式存在.盡管不同的系統(tǒng)實現對于進程或者線程的定義有所差別,比如Linux系統(tǒng)通過輕量級進程(light-weight process,簡稱LWP)來定義線程,多個共享組ID的輕量級進程在同一進程空間,但是調度基本上都是以線程為粒度.

2 異構調度的問題與挑戰(zhàn)

異構多核處理器最主要的作用是不同類型的處理核可以滿足不同特定應用的需求.由于不同的核提供不同的資源和處理能力,為了滿足特定的優(yōu)化目標,在任務調度時,需要為任務選擇更合適的處理核心,而傳統(tǒng)的同構多核處理器環(huán)境下的調度技術并沒有考慮由于核之間的差異所造成的處理能力上的差異,主要根據程序的優(yōu)先級和核的負載情況進行任務的分配與遷移.因此,異構環(huán)境下調度技術的主要工作是有效感知異構所帶來的計算能力的差異性,感知工作負載特性,選擇更加合適的核而不是選擇最空閑的核進行任務分配,圍繞對于微架構和工作負載的感知,異構多核處理器環(huán)境對調度技術的研究提出了新的挑戰(zhàn).

異構多核處理器環(huán)境與同構多核處理器的核類型比較單一不同,它具有不同類型的處理核心,每種類型的核具有不同的微架構,如處理器中有些核是順序流水線設計,有些是亂序流水線設計;有些核是 MT(multithread)模式,有些核是 ST(single-thread)模式;有些核支持大的緩存結構,有些核緩存結構較小.在這樣的異構環(huán)境下,不同于同構處理器環(huán)境下的調度算法,在定義和滿足優(yōu)化目標時(如性能和功耗),需要感知核之間的差異.

(1) 由于程序的特性不同,如計算密集型、訪存密集型、分支密集型等,對于硬件資源的需求不同,在不同核上的行為也有所不同,故需要通過模型來感知不同程序在不同核上的特性核資源需求,作為調度的主要依據.

(2) 在異構多核處理器環(huán)境下,由于程序各執(zhí)行階段的行為特征不同以及核微架構的不同,對于程序不同的執(zhí)行階段所提供的計算能力也有所不同.因此,調度需要對負載進行感知,并綜合異構環(huán)境下不同核之間的遷移代價進行及時的調度決策響應.

(3) 算法評估的方式直接影響異構調度算法的驗證效果,評估平臺或者模型的構建需要異構的特性,對算法做出正確的評估.

本文從優(yōu)化目標、分析模型、調度決策和算法評估這4個方面對異構感知的調度所面臨的問題與挑戰(zhàn)進行了總結和討論.

2.1 優(yōu)化目標問題

滿足性能目標主要是通過調度技術最大程度地利用處理器的并行處理能力,包括指令級并行和線程級并行,因此,針對不同的程序,在線程分配時,需要考慮程序在哪種核上更加受益,比如分配指令并行化程度高的線程在小核上執(zhí)行,串行的線程在大核上執(zhí)行.程序的訪存行為、程序之間的資源依賴和競爭關系都將影響到調度的決策以及系統(tǒng)性能.而且,異構環(huán)境下不同核之間的能耗存在差異,而目前異構多核處理器的主要應用場景為移動終端,功耗是影響用戶體驗的關鍵因素.因此,需要兼顧性能和功耗,在滿足性能和其他服務質量(QoS)指標的前提下通過調度來降低處理器功耗.

同時,由于異構多核處理器核之間設計的差異性,比如緩存設計不同,結合核內對于訪存指令執(zhí)行的流水線設計的不同,會導致緩存系統(tǒng)不同的吞吐量和延時,異構調度需要考慮更多的影響因素來解決并發(fā)程序的瓶頸問題.比如程序的同步以及資源競爭所導致的性能或者功耗問題.多線程程序的完成必須等待所有線程全部執(zhí)行結束,程序的性能受限于執(zhí)行時間最長的線程或者關鍵執(zhí)行代碼(比如鎖同步的代碼)執(zhí)行的速度,盡可能地將關鍵的線程或者代碼分配到大核上進行加速.當多個程序或者線程共享緩存資源時,要充分考慮線程的訪存特性以及與其共享緩存的線程的訪存蹤跡,盡量避免由于訪存競爭造成的性能損失和較大的功耗.

因此,異構調度需要考慮更多的微架構和程序特征影響的因素,要定義和滿足各種優(yōu)化目標,尤其要做到性能和公平性兼顧、性能和功耗兼顧以及其他QoS和功耗兼顧.

2.2 分析模型問題

程序分析是調度技術的重要工作,同構多核處理器環(huán)境下每個核提供的計算能力相同,調度主要對程序本身的特性進行分析,根據線程優(yōu)先級和負載情況,將線程分配到空閑的核上運行,對于程序適合運行的核微架構信息無需考慮.而在異構多核處理器環(huán)境下,由于核之間的微架構存在差異,線程在不同類型核上的行為存在很大差異,比如處理器中存在亂序執(zhí)行和順序執(zhí)行兩種核,對于浮點計算程序,如果任意調度到順序執(zhí)行核上運行,將嚴重影響程序執(zhí)行的性能.因此,調度需要獲取程序在不同類型核上的運行特性,針對不同的優(yōu)化目標,建立分析模型來評估程序更適合運行的核,作為調度決策的主要依據.因此,分析模型需要同時考慮程序本身的特性和核的微架構特性,是異構調度重點要解決的問題.

程序分析主要包括兩個方面的工作:(1) 獲取不同類型核上的特性;(2) 建立模型.要想獲取不同核上的運行特性,有些工作在調度時對線程的特性進行采樣,會造成比較大的開銷,隨著核類型的不斷增加,可擴展性也變得較差.有些工作不需要將線程在每個核上執(zhí)行,通過預測模型評估不同核上的特性,這種方法依賴于預測模型的可靠性,容易造成誤差.同時,之前的異構調度技術多采用簡單的分析模型,比如簡單地通過 IPC(instructions per cycle)的統(tǒng)計或者最后一級緩存缺失數(LLC misses)統(tǒng)計將線程劃分為計算密集型和訪存密集型進行調度,但是,近期的研究工作表明,簡單的分析模型會導致不理想的線程分配.因此,有研究工作通過機器學習等技術建立復雜的分析模型作為調度的依據,但是過于復雜的模型可能會影響調度系統(tǒng)的性能,而且模型需要的性能信息從現有硬件中獲取不到,可能需要實現額外的硬件支持.因此,從復雜度、系統(tǒng)開銷、模型正確性等方面考慮,采用高效又準確的分析技術建立分析模型能夠快速響應程序的變化且正確反映程序的資源需求,是值得需要不斷探索的問題.

2.3 調度決策問題

調度技術中重要的工作之一就是如何快速且正確地預測程序執(zhí)行階段的變化,并進行任務的遷移,將任務分配到能夠更加受益的核上執(zhí)行.影響調度決策的因素主要包括執(zhí)行階段變化的分析和預測以及任務遷移開銷.

目前,大部分調度根據設置的指令窗口大小將程序劃分為若干階段,根據基于運行時性能數據的分析模型進行調度決策和任務的遷移.采用這種方法指令窗口設置得是否合理,其產生的影響就比較大,劃分粒度如果太小,程序行為也許不會在這么短的時間間隔內發(fā)生變化,會造成很多不必要的系統(tǒng)開銷.劃分粒度如果太大,會錯失真正的程序行為變化而無法做出正確的調度決策.因此,如何正確地預測程序行為的變化(尤其是將要發(fā)生的執(zhí)行階段)并快速做出調度決策是值得研究的問題.

同時,在線程遷移過程中,遷移的代價除了表現在上下文環(huán)境的復制上,緩存系統(tǒng)數據的熱啟動(warmup)開銷也很大.最初階段的冷啟動會使得線程經歷大量的緩存缺失,從而導致大量的超長延時(一般數百個 Cycle)的內存訪問,影響線程執(zhí)行的性能和功耗.異構多核環(huán)境下,由于不同核之間的差異所帶來的遷移開銷更加明顯,文獻[5]指出異構多核環(huán)境下任務遷移代價是非常大的,甚至達到數百萬時鐘周期,實驗結果表明,在 ARM big. LITTLE系統(tǒng)中,任務從Cortex A15遷移到A7的延遲約為3.75ms,從A7到A15的延遲約為2.10ms.以最短的時間進行遷移后的熱啟動來降低遷移的代價,直接影響到能否實現細粒度的線程分配.對于遷移開銷的評價將直接影響調度的效果,是調度決策需要考慮的重要因素.

2.4 算法評估問題

評估平臺需要對異構多核處理器進行建模,同一芯片中集成不同微架構類型的處理核心,比如 ARM big.LITTLE的 SoC設計.但是,由于異構處理器的設計和實現相對于傳統(tǒng)的同構多核處理器要復雜很多,所以實際的非對稱異構處理器平臺還沒有被廣泛地生產和使用.以前的研究工作通過(dynamic voltage and frequency scaling,簡稱DVFS)技術調整核內的時鐘頻率和工作電壓來仿真異構多核平臺,文獻[6]采用4核AMD Opteron 2374-HE處理器作為實驗環(huán)境,其中,1個大核頻率設置為2GHz,3個小核頻率設置為800MHz,核之間的微架構完全一樣.在此實驗平臺上,該文將設計的調度算法與 Linux標準調度算法和 IPC作為調度主要參考依據(IPC-driven)的調度算法進行了對比,分別平均有12.3%和3.2%的性能提升.但是這樣的仿真方法過于簡單,無法真正模擬異構多核處理器的特性,優(yōu)化模型及實驗的結果可能也不適用于真正的微架構存在差異的處理器硬件.除了時鐘頻率的差異之外,異構更多體現在核的流水線設計、指令集結構、緩存結構等方面.因此,除了采用ARM big.LITTLE等已經存在的異構處理器產品,使用架構模擬器是比較常用的方法,但是由于軟件模擬的速度和精度等問題,對于復雜工作負載場景下的算法評估在模擬器的環(huán)境下很難實現.因此,設計與實現有效的評估模型對調度算法的效果進行驗證是值得探索的問題.

伴隨著異構多核處理器逐漸成為主流,如果想要在滿足高性能、低功耗等優(yōu)化目標的前提下,通過異構調度優(yōu)化技術對異構多核處理器進行有效管理,就要充分發(fā)揮異構多核處理器中不同微架構設計核心的優(yōu)勢,以上這些問題都值得去研究和探索.

3 異構調度技術

圍繞第2節(jié)提出的問題與挑戰(zhàn),本文從優(yōu)化目標、分析模型、調度決策、算法評估這4個方面對異構調度相關的已有研究工作進行了系統(tǒng)的總結(見表3).

Table 3 The technology summary of four aspects including optimization objectives,analysis model,scheduling decision and algorithm evaluation表3 優(yōu)化目標、分析模型、調度決策、算法評估這4個方面的總結

Table 3 The technology summary of four aspects including optimization objectives,analysis model,scheduling decision and algorithm evaluation (Continued)表3 優(yōu)化目標、分析模型、調度決策、算法評估這4個方面的總結(續(xù))

Table 3 The technology summary of four aspects including optimization objectives,analysis model,scheduling decision and algorithm evaluation (Continued)表3 優(yōu)化目標、分析模型、調度決策、算法評估這4個方面的總結(續(xù))

3.1 優(yōu)化目標

異構環(huán)境下的調度主要是協同計算核心更好的工作來滿足整個計算系統(tǒng)的優(yōu)化目標,除了滿足性能目標,因為異構環(huán)境的主要應用場景是移動終端(比如ARM的big.LITTLE架構設計),功耗也是重點關注的優(yōu)化目標,在滿足性能、實時性等 QoS指標的情況下應盡可能地降低功耗.除此之外,因為異構處理器在微架構方面的差異,在程序同步和競爭、公平性以及在特定應用領域,比如虛擬化方面,都存在很多研究工作,本節(jié)針對上述工作進行討論和總結.3.1.1 滿足性能

文獻[5]提出一種動態(tài)調度技術將線程遷移到更適合的核上運行,表明異構多核環(huán)境下動態(tài)調度策略比靜態(tài)調度策略能夠帶來更為明顯的性能提升.首先將線程分配到每種不同類型的核上運行很短的時間,進行線程IPC的統(tǒng)計,對于明顯受益于大核(線程分別在大核和小核上運行的IPC的比值,記為IPCratio)的線程將被遷移到大核執(zhí)行,如果沒有明顯受益將被遷移到小核執(zhí)行.為了避免 IPC變化所帶來的頻繁遷移,調度決策依據的 IPC相對值不是瞬時值,而是使用歷史的IPC和當前IPC的加權平均.

文獻[7]提出了一種基于穩(wěn)定匹配算法的動態(tài)調度技術,維護動態(tài)的線程任務和核的優(yōu)先級表,保存了每個任務適合運行核和每個核選擇任務的優(yōu)先級順序,調度算法將動態(tài)跟蹤優(yōu)先級表和可用的核,為每個核分配最適合的任務,通過最優(yōu)匹配縮短任務執(zhí)行時間.該文提到的優(yōu)先級表動態(tài)跟蹤和更新是調度的主要依據,更新的時機、頻率和正確性都直接影響了調度的效果,更新的效率也直接決定了調度算法的可擴展性.

文獻[8,9]提出了一種調度技術,通過大核和小核的加速比模型衡量線程是否有效利用大核,作為調度的依據.文獻[8]通過一條指令的平均阻塞時間(ASTPI)來衡量線程有效利用大核的能力,一條指令執(zhí)行的時間分為兩個部分:指令真正執(zhí)行的時間和由于等待內存訪問被阻塞的時間,程序執(zhí)行過程中被阻塞時間和 ASTPI的定義分別如下所示:

文獻[8]分析了對于計算密集型程序(極端情況下,如果ASTPI為0),SF為MIPS的比值.對于內存密集型程序(極端情況下,如果ASTPI無窮大),SF接近1.實驗結果與IPC驅動的調度算法性能對比有明顯提升,核類型越多,效果越明顯.

文獻[9]綜合考慮了程序的效率和線程級并行(TLP)兩個屬性,效率指的是程序有效利用大核的能力,TLP指的是高度并行化的代碼適合在小核上并發(fā)執(zhí)行.效率通過SF體現,通過LLC Misses來估計,這種估計方式對于高度計算密集型應用和高度內存密集型應用的區(qū)分比較準確,但是對于其他類型的應用準確度比較低.考慮到多線程程序的并行化特性,該文基于SF提出UF(utility factor)來進行估計,UF表示多線程程序利用所有大核執(zhí)行相對于所有小核執(zhí)行的加速比.UF的值受到平均SF和線程數的影響,因此,當程序的線程數發(fā)生變化或者線程的SF發(fā)生變化時,UF需要更新.

芯片級的線程級并行化(thread level parallelism,簡稱 TLP)是提高多核處理能力的關鍵技術,投機線程(thread level speculation,簡稱TLS)執(zhí)行是串行程序的加速技術,指的是抽取串行程序中有可以并行的程序片段(比如循環(huán)代碼),并將其分配到多個核上投機執(zhí)行,如果投機錯誤,由于需要重新執(zhí)行而帶來的流水線刷新將會帶來較大的系統(tǒng)懲罰,影響了程序執(zhí)行的性能.文獻[10]提出一種異構環(huán)境下針對投機線程的動態(tài)分配技術,該文提到的異構多核處理器的核之間的差異主要包括發(fā)射帶寬、L1緩存大小和是否支持同時多線程(simultaneous multi-threading,簡稱 SMT)等微架配置的不同.當線程之間頻繁發(fā)生核內資源競爭(比如指令級并行度很高)時,多線程適合在支持單線程的多個物理核(chip multi-processor,簡稱 CMP)上運行,當線程在執(zhí)行過程中由于資源的缺失(比如L2訪問缺失)頻繁發(fā)生流水線阻塞時,多線程適合在支持SMT的核上運行.基于上面的分析,該文提出一種動態(tài)分配機制,當程序片段首次出現時,將其所有的線程分配在默認配置的核上進行度量,并根據獲取的硬件性能事件對其最適合運行的核配置進行預測,保存在資源分配表中作為線程分配的依據.同時,該動態(tài)分配技術根據對重排序隊列的需求統(tǒng)計來決定線程是在發(fā)射帶寬大還是小的核上運行,當數據重用率(緩存內被重復使用的數據塊的比例)小的時候,將考慮關閉部分L1空間用來節(jié)能.為了平衡遷移開銷,對于執(zhí)行時間很短的指令段,或者當線程遷移或關閉L1的開銷大于收益的時候,將不進行線程的分配和遷移.

文獻[11]提出一種迭代啟發(fā)式調度算法.第1階段在不考慮功耗的情況下將線程分配到可以達到最大吞吐量的核上運行,第2階段通過迭代向下(與比當前核性能低的核進行比較)線程交換的方式,尋找最小性能損失情況下可以最大程度地節(jié)省功耗的線程進行實際的物理線程交換,直到滿足功耗的限制為止.文獻[11]中的實驗結果表明,系統(tǒng)的提升接近最優(yōu)算法,而且由于算法的開銷比較低,可擴展性比較好,可以適應于核數目比較多的異構系統(tǒng).

3.1.2 特定QoS下的功耗優(yōu)化

性能非對稱多核處理器具有高性能和低功耗結合的特點.它在為不同需求的應用程序提供服務的同時,功耗也是其重點關注的問題,這對操作系統(tǒng)調度和電源管理技術提出了挑戰(zhàn).由于移動終端特別是手機的普及和流行,應用需求多種多樣,對于任務來說,任務執(zhí)行時間、功耗以及其他QoS指標是相互制約的,比如視頻播放器,為了滿足性能和截止時間要求,需要降低畫面質量(QoS).因此,在滿足能效的情況下,同時考慮多種 QoS指標的功耗優(yōu)化也是研究的熱點.本節(jié)從滿足能效、實時任務時間約束和滿足用戶體驗需求這3個方面進行總結和分析.

(1) 滿足能效

以能效優(yōu)化為目標的調度技術,主要是在滿足程序執(zhí)行性能需求的前提下盡可能地達到最低的功耗.

文獻[20]提出了針對一組線程的全局線程分配方法,使線程在滿足計算和內存需求的情況下達到最小的功耗.該方法使用整數線性規(guī)劃優(yōu)化模型進行線程的動態(tài)分配,使得系統(tǒng)的能效達到最大,能效表示如下:

其中,y是經驗值設定(文中設置為2),為了平衡系統(tǒng)中性能和功耗的影響,2.0比1.0就意味著性能提升影響能效的作用更加明顯.優(yōu)化模型的目標函數主要滿足3個約束條件:(1) 分配線程的能效之和達到最大;(2) 分配線程的內存需求(每秒的內存請求數)之和不超過內存帶寬;(3) 每個線程分配在一個核上且分配的線程總和不超過可用的核數.本模型中線程的計算需求由IPS表示,內存需求由共享緩存的LLC Misses來表示.分配線程采用下一個適合的啟發(fā)算法,將線程的性能需求按照降序排列,然后按照順序將線程分配到能夠滿足需求的核上.

文獻[20,21]采用相同的能效度量公式,基于彩票調度算法提出一種線程按比例共享的調度算法,用來提高程序執(zhí)行的效能和性能.與文獻[29]不同的是,文獻[20,21]只考慮了局部線程效能的提升.在調度算法中,線程持有的票數代表在大核上運行的優(yōu)先級,票數的多少由線程在大核和小核上運行的效能比來決定.在調度周期內(200ms),獲取彩票的線程會被遷移到負載最輕的大核上執(zhí)行.

文獻[22]提出了基于價格理論的任務調度框架,在框架中,CPU核提供以計算單元(PU)為單位的計算資源(1PU為每秒1M個時鐘周期,每個核根據時鐘頻率進行換算).任務需要一定數量的計算單元,在任務不同的執(zhí)行階段以及不同的核上,需要的計算單元數量不同.框架中核的資源分配、DVFS、任務分配和遷移都是通過虛擬貨幣來進行計算單元的交易,最終滿足約束條件:系統(tǒng)在滿足性能需求的情況下其功耗低于散熱設計功耗(TDP)的限制.

文獻[23]提出了一種異構多核環(huán)境的新思路,即動態(tài)的異構多核環(huán)境,這種環(huán)境是指硬件的錯誤和程序異常等不確定因素造成的動態(tài)的無法預期的CPU核之間的差異.針對動態(tài)異構多核環(huán)境,該文提出的調度技術將程序分為探索階段(exploration phase)和穩(wěn)定階段(steady-phase).探索階段對線程在每個核上執(zhí)行的性能數據和功耗數據進行采樣統(tǒng)計,形成代價矩陣,每一項保存線程i在核j上的功耗數據.該文采用兩種方法進行最優(yōu)分配策略的決策,一種方法采用匈牙利算法[46],代價矩陣作為輸入,得出每個線程的最優(yōu)分配策略.另一種方法基于人工智能的迭代優(yōu)化算法,在探索階段的每個時間間隔,統(tǒng)計線程的ED2,找到最優(yōu)的線程分配策略,在穩(wěn)定階段使用.算法的驗證存在假設條件:線程之間沒有交互,在探索階段的程序執(zhí)行行為相對穩(wěn)定.

(2) 滿足實時任務時間約束

文獻[26]提出的技術通過定期檢查任務的執(zhí)行性能,分配任務到異構環(huán)境中合適的核上來滿足任務結束時間的嚴格約束(DeadLine).例如,如果任務在低功耗小核上運行無法滿足 DeadLine,將被分配到大核執(zhí)行,然后保證整體能耗在預先定義預算內的前提下將大小核的頻率調整到最高.由于計算密集型的多任務執(zhí)行導致能耗預算超支,大小核的頻率將被調整到最低.

文獻[27]提出一種異構環(huán)境下針對實時應用程序分配的方法,在保證程序截止時間要求的前提下最小化核的運行頻率.優(yōu)化目標可以定義為,將實時任務集分配到異構平臺上,如何進行任務的劃分使得每個核運行在最優(yōu)的運行頻率下,在保證時間要求的前提下總體功耗最小.文中通過分析發(fā)現,除非在核特性差異特別大或者特別接近的極端情況下,將負載盡可能地分布在最節(jié)能的核上或者均衡的負載分布不是最佳任務劃分,并將確定功耗最優(yōu)的負載分布抽象為可追蹤凸優(yōu)化問題的學習模型,通過對負載分布與核最優(yōu)頻率的關系來確定最優(yōu)的任務劃分.

文獻[28]的目標是集成近似計算、任務調度和DVFS電源管理機制在滿足性能和截止時間的前提下,盡可能地降低功耗.文中提出異構多核環(huán)境下針對軟實時任務的可擴展調度框架,結合線下分析和線上動態(tài)調度的方式,首先通過遺傳算法(GA)進行線下分析基于軟實時任務的最差執(zhí)行時間(WCET),得出相對較優(yōu)的任務調度和 CPU頻率調整策略,然后設計在線調度策略根據任務實際執(zhí)行時間進行調整,當任務執(zhí)行完畢,如果 CPU空閑,則將通過DVFS關閉來節(jié)省功耗.其中,根據最近已執(zhí)行任務的平均執(zhí)行時間預測待調度任務的執(zhí)行時間,并據此進行任務分配.實驗結果表明,在最小化對 QoS(平均約 1%的下降)影響的情況下,最高可以節(jié)省 84%的功耗.

(3) 滿足用戶體驗需求

目前,手機設備上的應用程序多種多樣,根據功能的不同,從用戶體驗的角度來看,對于程序的延時要求和容忍度也有所不同,比如媒體播放器是延時敏感程序,相反地,比如文件解析程序就是延時容忍程序.文獻[29]提出一種以用戶體驗為中心的調度算法,通過觀察用戶的交互行為(比如手機應用切換后的反饋延時)和對程序的關注度(比如程序在前臺還是后臺)提出程序敏感度概念,將程序分為高、中、低3個敏感狀態(tài),通過調度算法和電源管理策略的合作達到用戶體驗和功耗的均衡,根據敏感狀態(tài)分配不同比例的CPU資源,在原有基于時間均衡的基礎上增加敏感度的平衡,同時,為了降低功耗,盡量保持 CPU利用率的平衡.實驗結果表明,對于用戶體驗要求不高的后臺程序,具有非常明顯的降低功耗的效果,而對于用戶體驗要求高的前臺程序,性能提高得也比較明顯.

對于大規(guī)模分布式系統(tǒng)來說,尾延遲(tail latency)的影響尤其嚴重,比如大規(guī)模搜索引擎,單個請求發(fā)送到上萬臺服務器,系統(tǒng)不得不等待尾延遲請求返回才能響應用戶.據此,文獻[30]提出一種自適應的從慢到快(slow-to-fast)調度框架,通過調度策略和 DVFS技術將請求程序負載分配到不同運行速度的核上,在保證長請求服務的響應要求的同時盡可能地降低短請求服務的功耗,服務請求的長短由請求隊列的長度和計算時間決定.該框架提出一種在線的基于閾值的調度策略,每個請求服務開始被分配到慢核上運行,一旦超過遷移閾值(探測為長請求服務),將通過 DVFS動態(tài)提高頻率或者遷移到更快的核上運行.同時,為了減小系統(tǒng)開銷,根據請求服務的目標響應延時、在線測量的響應延時、系統(tǒng)負載等信息進行遷移負載的線下學習,并反饋給在線調度策略.實驗結果表明,該框架可以很好地適應負載的變化,在滿足響應要求的同時降低 18%～50%的功耗,提高 32%～82%的吞吐量.

多媒體程序由于使用硬件解碼不會占用太多的 CPU資源,基于此分析,文獻[31]提出基于調度的能耗管理技術,采用類型分類方法根據程序是否包含特定的視頻音頻播放線程區(qū)分多媒體程序和非多媒體程序,并將多媒體程序分配到小核上運行.該技術在保證媒體播放質量的情況下,通過分配較少的CPU資源達到降低能耗的目的.

文獻[32]利用手機設備上的大小端特點,提出一種感知網頁特性的調度技術,根據不同網頁的特性分配合適的異構資源.該文根據頁面架構設計中對于資源需求的不同建立網頁加載時間和能耗的回歸預測模型,指導調度器確定分配核和運行頻率的最優(yōu)配置,在滿足延時的需求下,降低能耗.針對不同網頁的實驗結果表明,該技術平均節(jié)省83%的能耗,其中約4.1%的網頁沒有滿足延時要求.

文獻[33]提出一種異構環(huán)境下瀏覽器線程的調度技術,分為線下(offline)和線上(online)兩個階段.線下對線程特性分類,包括影響網頁加載速度的關鍵線程和不影響加載速度的非關鍵線程,線上調度時盡量不分配非關鍵線程到大核執(zhí)行.同時,通過關閉空閑的大核節(jié)省能耗.

3.1.3 滿足公平性

針對多線程(multi-thread)和多程序(multi-program)的工作負載,有些調度算法會造成有些線程很長時間沒有被調度,導致一直無法執(zhí)行完成,從系統(tǒng)執(zhí)行的全局角度來看,公平性對于整體性能的提升非常重要.

文獻[45]提出了感知公平性的全局調度算法,使系統(tǒng)中的線程保持相同的執(zhí)行進度(equal-progress scheduling).公平性的度量值如下所示:

文獻[45]采用所有線程減速的變異系數表示不公平性,因此,fairness值越大,表示越公平,當fairness值為 1時,表示所有線程具有相同的執(zhí)行進度.調度算法的目的就是使得fairness的值接近于1.調度算法最大的挑戰(zhàn)是計算每個線程的 slowdown,需要獲取線程在大核和小核上運行的總時間以及單獨在大核上運行的時間,在大核和小核上運行的總時間可以通過線程實際運行時間計算而來,單獨在大核上的時間需要在運行時進行估計.實驗結果表明,程序具有平均14%最高25%的性能提升.

文獻[46]針對緩存資源共享和競爭對共同運行多線程的影響所造成的系統(tǒng)性能問題,比如不公平的 CPU時間片分享和優(yōu)先級翻轉等,提出基于緩存系統(tǒng)公平性的調度算法,根據緩存的影響重新調整分配的CPU時間片.CPU的執(zhí)行延遲通過(cycle per instruction,簡稱CPI)來衡量,對于等待訪問緩存(cache-starved)的線程,CPI會比較高.該調度算法通過調整CPU的時間片,使得等待緩存訪問的線程多運行一些時間,達到預期的CPI.該算法分為兩個階段:勘察階段,根據線程運行的性能信息估計線程公平訪問緩存的 CPI,從而估計線程應該執(zhí)行的指令數;校準階段,根據應該執(zhí)行指令數與實際執(zhí)行的指令數的比較差,對線程運行的 CPU時間片進行校準.線程運行的CPI可以通過動態(tài)測量,線程公平訪問緩存的CPI如何估計是算法需要解決的主要問題.文獻[46]假設共同運行的線程如果具有類似的緩存缺失率,則這些線程在公平訪問緩存系統(tǒng),共同運行線程的緩存缺失率具有線性關系.在此假設關系下,通過隨機測試線程與其他線程共同運行的缺失率估計該線程的公平訪問的缺失率(FairMissRate),基于公平訪問缺失率估計公平訪問的CPI.

文獻[47]提出在操作系統(tǒng)的層面通過對性能監(jiān)控單元(PMU)記錄的性能數據的統(tǒng)計與分析,觀察線程的動態(tài)執(zhí)行行為.每個線程設置相應的訪存權重,權重由線程每個時鐘周期的LLC Misses來決定,LLC Misses高的線程,訪存權重大.訪存權重大的占用了 CPU時間片,卻無法有效利用核內計算資源.為了解決公平性問題:當權重小的線程與權重大的線程一起運行時,影響了權重小的程序,操作系統(tǒng)根據觀察,將分配給它更多的時間片.

文獻[48]提出了異構環(huán)境下的公平調度算法,在盡可能不影響吞吐量的前提下保證同程序的公平性,使同優(yōu)先級的程序具有相同減速(slowdown,程序通過調度執(zhí)行的時間與全部在大核上執(zhí)行時間的相對比值).算法通過線程的虛擬運行時間(Amp_Vruntime)來跟蹤相比于運行在大核上進展的相對進度,比如兩個減速相同為2的程序A和B,在某一調度周期內,如果A運行在大核上,B運行在小核上,A的虛擬運行時間是B的2倍,意味著A的進度是B的2倍,為了公平性,調度器下個周期會將B分配在大核上運行.由于公平性會影響系統(tǒng)的吞吐量,該文對虛擬運行時間進行了優(yōu)化,增加影響系數來提高系統(tǒng)的吞吐量,當影響系數為 1時,盡可能地保證最優(yōu)的公平性,當系數大于1時,將犧牲部分公平性來提高系統(tǒng)的吞吐量.為了避免頻繁遷移所帶來的系統(tǒng)開銷,設定閾值,當兩個線程的虛擬運行時間差超過閾值時才進行任務的遷移.實驗結果表明,該算法在不影響吞吐量的前提下具有11%的公平性提升.

3.1.4 并發(fā)程序瓶頸優(yōu)化

1) 程序同步

異構多核處理器環(huán)境下,線程同步影響性能主要包括兩個因素:(1) 對于具有同步關系的并行程序(一個程序視為一個線程)或者沒有交互關系的多線程程序,多個線程需要在某個執(zhí)行點或者在結束的時候進行同步,執(zhí)行時間最長的線程影響整個程序的運行時間,影響的線程為落后線程(lagging thread);(2) 多線程互斥訪問,關鍵代碼的執(zhí)行速度直接影響程序的性能.已有的調度研究工作主要針對上面這兩種同步情況進行優(yōu)化.

在異構多核處理器環(huán)境下,由于核間性能不同,在并行程序調度的時候,如果沒有考慮這種差異,將會導致工作負載的不均衡,如圖 2(b)所示,影響到系統(tǒng)的執(zhí)行效率.文獻[52-54]主要針對并行程序調度(比如 workstealing)的不均衡問題提出優(yōu)化方法,目標是通過調度使得程序中線程的最大完成時間(makespan)達到最小.

Fig.2 Two possible thread allocation method圖2 線程的兩種分配方法

文獻[54]提出了一種感知工作負載(執(zhí)行時間)的任務調度算法(WATS).解決的問題模型為:將m個任務分配到c個不同類型的核上(c的值默認為 2),使得每個任務全部執(zhí)行完成的時間達到最小.這個問題是 NP-Hard問題,文獻[54]提出了近似最優(yōu)的啟發(fā)算法,將工作負載重的任務分配到大核上執(zhí)行,算法將并行程序的任務按照在大核上的執(zhí)行時間進行排序,執(zhí)行時間長就表示工作負載重.算法實現最重要的是感知任務的工作負載,也就是對任務在不同類型核上的執(zhí)行時間進行統(tǒng)計分析與預測.為了更好地進行任務執(zhí)行歷史信息的統(tǒng)計及預測,WATS算法假設執(zhí)行相同函數的任務具有相同的工作負載,將具有相同函數的任務歸為統(tǒng)一任務類,任務類將根據任務的歷史執(zhí)行信息預測同一類的任務的執(zhí)行時間,當任務執(zhí)行完成后,更新并維護m個任務類的執(zhí)行時間表,進行任務的分配和負載均衡.任務的執(zhí)行時間由于受到操作系統(tǒng)中斷事件的影響會明顯增加,該文采用IPC來更新任務的執(zhí)行時間歷史信息.實驗結果表明,該方法可以提供比較好的性能提升,但是實現相對復雜,而且沒有考慮動態(tài)的異構(比如通過DVFS的頻率變化).而文獻[53]同時考慮了核微架構的靜態(tài)異構和動態(tài)異構,提出一種異構感知的 Work-Stealing優(yōu)化方法(AAWS),并提出 3種軟硬件結合的技術:Work-Pacing、Work-Sprinting和 Work-Mugging,根據程序的高并行度(HP)和低并行度(LP)行為動態(tài)調整大小核的頻率以提供合適的計算能力,實驗結果表明,該方法能夠提供較好的能效.

文獻[55]通過識別落后線程,并對落后線程進行加速以提高程序整體執(zhí)行的性能.文獻[55]提出了基于線程相對執(zhí)行長度(reletive thread length)的調度算法,相對執(zhí)行長度長的任務將優(yōu)先被調度.假設程序的多線程基本上具有同樣的程序行為,遵循簡單的fork-join模型,一個程序內的所有線程如果在同一時間創(chuàng)建,則距離下次里程碑(milestone)有相同的距離.算法將多線程的同步點定義為多個里程碑,通過動態(tài)統(tǒng)計線程執(zhí)行的指令數預測每個線程的距離里程碑的相對長度,采用距離長的線程優(yōu)先調度到大核處理的策略推動落后線程的進度.

多線程程序的性能受執(zhí)行瓶頸的影響,比如關鍵代碼、柵欄(barrier)等,文獻[56-58]通過加速多線程程序的關鍵代碼執(zhí)行速度來提高性能.文獻[57]提出了一種利用大核來加速關鍵代碼的運行的方法,執(zhí)行并行代碼在小核上提高多線程的執(zhí)行性能.當小核遇到關鍵代碼的執(zhí)行時,將把關鍵路徑的代碼遷移到大核上執(zhí)行.大核上通過實現關鍵代碼請求緩存(CSRB)來保存來自小核的請求,并增加兩條新指令的設計:用 CSCALL(critical section cxecution call)和CSRET(critical section return)來處理關鍵代碼執(zhí)行的交互及上下文切換.

文獻[57]提出一種調度技術,首先分配最長的任務和執(zhí)行關鍵路徑的任務到大核上執(zhí)行.關鍵路徑指的是,線程獲取鎖權限進入的代碼區(qū)域或者等到所有線程執(zhí)行完畢(barrier).該文通過編譯器靜態(tài)分析每個任務的循環(huán)數目來決定任務的大小,當該任務對應的線程創(chuàng)建的時候,由程序通過系統(tǒng)調用告訴內核該任務的大小.測試程序使用的是PARSEC、ITK,不同于單線程的多個程序,多線程的測試程序是有交互的且存在關鍵路徑,對于調度算法的驗證非常有效.

文獻[58]提出軟硬件結合的關鍵執(zhí)行路徑識別機制,在軟件層面,通過程序、編譯器、庫等對潛在瓶頸進行標識,并通過硬件指令(BottleCall和BottleReturn)對潛在瓶頸進行封裝,對于等待瓶頸執(zhí)行其他線程的代碼使用硬件指令(bottleneck)替換,已達到運行時進行跟蹤的目的.同時,設計自動加速機制統(tǒng)計線程等待瓶頸執(zhí)行的執(zhí)行周期保存在瓶頸信息表中,并選擇被等待時間最長的瓶頸進行加速,分配到大核上執(zhí)行.

文獻[59]提出一種同時適用于加速關鍵路徑和落后線程的調度優(yōu)化技術,采用通過使用加速度量指標(acceleration metric)來決定適合在大核上執(zhí)行的代碼片段,以實現多線程程序的加速.

2) 資源競爭

文獻[60-64]提出的調度算法主要是降低多線程程序或者多程序工作負載共同運行導致的緩存訪問共享、競爭以及訪存延時等問題對于性能的影響,從而提高系統(tǒng)的整體性能.

文獻[60]提出了針對Dram和Nvram異構內存的多程序調度算法,通過調度,使得多個程序盡量互補地訪問不同類型的內存,減少訪存沖突,提高程序性能.由于Dram和Nvram的特性不同,被頻繁訪問或者短期存活的數據保存在Dram中,其他的數據保存在Nvram中,Nvram的寫訪問比Dram的讀訪問的延遲還要長.由于Dram的訪問延時與請求類型無關,在以 Dram 為主的內存中,內存帶寬通過單位時間內的內存訪問事務(transaction)數目來計算,但是Nvram不同的請求類型,訪問延時有很大的差異,請求類型的不同嚴重影響了單位時間內的訪存數目.因此,該文提出了有效內存帶寬來計算混合內存的帶寬,將訪存類型分為Dram access、Nvram讀和Nvram寫,有效內存帶寬可以反映不同類型的訪存帶寬,將Nvram的訪問帶寬轉化為單位時間內的Dram請求數.調度算法根據有效內存帶寬將任務分為延遲敏感和帶寬敏感,為了不擠占內存帶寬,優(yōu)先調度延遲敏感性任務.

文獻[61]提出了一種優(yōu)化緩存和內存等共享資源競爭問題的調度技術,避免線程之間的資源競爭,在實在無法避免競爭的情況下,提出動態(tài)調整頻率的啟發(fā)算法來降低功耗.該文提出了基于向量的負載均衡策略,采用任務活動向量來保存競爭資源,如內存、LLC的資源利用率.為了避免共享資源的競爭,盡量將任務活動向量差異度大(即活動向量中每項之間的方差比較大)的線程分配到不同的核上執(zhí)行.調度算法按照內存資源的利用率將每個核上的線程進行排序,單數的核降序排列,雙數的核升續(xù)排列,按照此順序進行線程的遷移.任務活動向量保存在線程的運行上下文中,在任務上下文切換時進行更新.同時,對于正在運行的線程根據資源利用情況通過行動態(tài)頻率的調整來降低功耗.當核的頻率發(fā)生變化時,任務活動向量也會發(fā)生變化,該文為不同頻率定義了翻譯向量表,預測當頻率發(fā)生變化時,任務活動向量應該調整的因子.

文獻[62]提出一種新的調度思想,主要目標不是合理地利用核資源,而是通過線程的調度與分配合理地利用片上內存資源,減少訪問內存的延時.調度對象不是線程而是線程涉及的數據(比如指令和數據),算法將線程所使用的數據對象合理地分配到不同核的緩存上,當線程需要不同核上的數據時,將線程遷移到距離訪問數據近的核上.該方法需要對程序進行分析,獲取程序的數據對象及大小、程序所做的操作及操作的時間,而且控制數據到緩存的分配.

文獻[63]對已有分析的線程間資源競爭影響分類學習機制進行對比分析,發(fā)現緩存競爭不是影響性能的主導因素,除此之外,還有內存控制器、內存總線和預取硬件等共享資源對性能的影響,并且分析發(fā)現這 3種對于性能的影響比緩存競爭更加明顯,并且預測,為了減少這些因素的影響,調度算法應該使緩存的缺失數達到最小.該文提出了基于緩存缺失率的啟發(fā)算法,線程的分布使得緩存之間的缺失率盡可能地均衡.而且這種競爭感知的調度算法主要是可以提升程序的服務質量,比如請求相應或性能隔離性.

文獻[64]提出不同程序的特性,任務的分配及處理器的運行頻率直接影響資源競爭情況、性能和能耗,該文提出了任務活動向量的概念,用來保存任務對于共享資源(內存總線、L2緩存等)和核內非共享資源(L1、執(zhí)行單元等)的利用情況,活動向量通過性能計數器(PMC)獲得.任務獲得向量根據不同的運行階段進行在線更新.基于任務活動向量,資源感知的調度算法將有不同資源需求的任務同時進行分配,降低資源的競爭,以提高性能和降低能耗,當實在無法避免競爭的時候,將通過調整頻率來達到節(jié)能的目的.

3.1.5 特定應用領域優(yōu)化

文獻[66-69]提出異構多核處理器環(huán)境下的虛擬機調度優(yōu)化技術.

文獻[66]提出一種可以感知(non-uniform memory access,簡稱 NUMA)架構的虛擬機調度算法,以降低NUMA系統(tǒng)的內存局部性問題所帶來的影響.NUMA系統(tǒng)中,不同的處理器直接與本地內存(local memory)相連,同時可以訪問其他處理器的內存(remote memory).因此,虛擬機的調度需要考慮的訪存因素包括:遠程內存訪問的懲罰、共享資源競爭、多處理器芯片之間的數據共享.為了避免出現這些問題,在線程調度時,考慮訪存密集型的線程分配在不同的處理器節(jié)點運行,有數據共享的線程盡量分配在同一節(jié)點,在任務遷移的時候,要考慮內存局部性的問題.

文獻[66]采用基于硬件微架構(Intel Nehalem)來估計線程訪問內存延時的方法,通過動態(tài)監(jiān)測 SQ(super queue)的占有率來計算內存延時.根據律特法則:

w表示平均Uncore訪問延時,q表示平均的并發(fā)Uncore請求數目,L表示在γ周期內SQ中Uncore請求的數目,t′表示SQ中至少有一個Uncore請求存在的周期數.該文通過PMU獲取模型相關的數據,并通過實驗驗證此模型比基于LLC Miss Rate的估計模型更加準確.調度算法根據估計模型在線監(jiān)控每個虛擬CPU運行核上的PMU數據,估計內存訪問延時,進行虛擬 CPU 的遷移使整個系統(tǒng)的內存訪問延時最低.為了降低頻繁遷移的開銷,每個虛擬CPU都具有標示是否遷移的屬性值(0和100之間),只有當虛擬CPU要遷移的核會發(fā)生較少的Uncore訪問阻塞時才會進行遷移.

文獻[67]分析了導致虛擬機系統(tǒng)整體性能下降的原因,主要包括:(1) 網絡通信的延遲:虛擬機之間的網絡通信都要通過domain0進行;(2) 調度帶來的延遲:在Xen授權(credit)調度器中,當被I/O訪問阻塞的虛擬CPU被喚醒后,會搶占計算密集型的虛擬 CPU,導致后者性能下降.同時,調度是異步調度,這樣會使得需要同步的虛擬CPU之間的性能下降.為了解決這些問題,提出了一種感知虛擬機特性和處理器異構性的調度算法,分析了虛擬機對于CPU頻率敏感度的分析,將虛擬CPU分為計算密集型和I/O密集型,通過對線程執(zhí)行時間的測試來統(tǒng)計對不同的頻率設置的敏感度以區(qū)分計算密集型和I/O密集型.兩種不同類型的虛擬機在不同的隊列中分別調度,給予不同的優(yōu)先級和時間片,前者優(yōu)先在大核上執(zhí)行,分配30ms的時間片;后者在小核上執(zhí)行分配10ms的時間片.每個虛擬機根據虛擬CPU的數量設定一定比例的權重,虛擬CPU數量為1的計算密集型虛擬機將被視為一個虛擬CPU直接進入隊列調度執(zhí)行.通過將兩種類型的虛擬CPU隔離以降低調度帶來的延遲;通過縮短小核調度時間片,降低虛擬CPU之間的同步延遲.該文修改了Xen的調度算法并進行了驗證.

文獻[68]提出在虛擬化環(huán)境中,調度主要包括在虛擬化層面為虛擬 CPU(VCPU)分配相應的物理 CPU(PCPU),在客戶機中進行線程的分配,兩者的調度相互配合.即使客戶機操作系統(tǒng)中的調度器可以感知異構,如果虛擬化層的調度無法感知異構,客戶機異構調度的效果將會受到很大的限制,比如線程需要在大核運行,虛擬化層面將虛擬CPU與小核映射,客戶機的調度將無法發(fā)揮作用.為了解決這一問題,該文提出一種感知異構的虛擬機調度算法,支持異構調度的客戶機工作,同時實現對于具有相同資源需求虛擬CPU的公平調度,對于重要虛擬CPU,可通過優(yōu)先級進行優(yōu)先調度.該文對Xen采用的授權調度器進行修改和擴展,實現了異構感知的調度算法,同時為了避免遷移帶來的開銷,遷移最短周期為 30milliseconds.實驗結果表明,增加了異構支持的調度算法其性能提升達36%.

文獻[69]提出一種異構環(huán)境下針對虛擬機的調度技術,以盡可能地提高系統(tǒng)能效.文中提出以單位功耗下指令的吞吐量(BIPS/W)為度量標準建立能效評估模型,根據對虛擬CPU(VCPU)而不是VCPU中所有應用的執(zhí)行行為統(tǒng)計分析,建立線性模型估計和預測VPU的能效因子,文中通過修改Xen的Credit調度器,在進行VCPU負載均衡時,根據預測的不同頻率下核的能效因子閾值和待遷移VCPU的能效因子進行VCPU的選擇和分配,實驗結果表明,針對大部分測試程序平均有13.5%的能效提升.

3.2 分析模型

根據調度技術中模型建立方法的不同,可以將分析模型分為架構無關分析模型和架構相關分析模型兩大類,其中,架構相關分析模型主要包括 CPI(cycle per instruction)棧模型和經驗模型.(1) 架構無關分析模型的建立主要對不依賴于微架構的程序內在特性(比如指令類型的分布,指令之間的依賴關系等)進行分析,可以借助編譯器等技術采用線下的方法提前對程序進行分析,提前對程序階段的變化進行標記.因此,分析的開銷比較小,適用于生命周期比較短的線程,但是模型的正確性依賴于程序輸入集的類型和覆蓋率,如果輸入集的選擇不夠全面和具有代表性,則將直接影響模型的正確性,而且,在架構無關模型的建立過程中考慮程序在系統(tǒng)中真實執(zhí)行的情況比,如資源競爭,也是比較困難的.(2) 目前的很多異構調度算法都采用 CPI棧模型進行程序性能的評估,針對各種性能事件對于執(zhí)行時間的影響進行量化.CPI棧由真正占用流水線執(zhí)行的時間和由于流水線堵塞事件、分支預測錯誤等造成的懲罰時間組成,CPI棧信息主要通過線程在執(zhí)行過程中的性能信息進行統(tǒng)計,性能信息多與架構相關,比如線程運行的時鐘周期數、指令數、分支預測錯誤數、LLC Misses等,這些信息可以通過CPU性能監(jiān)控單元(PMU)輔助獲得.構建CPI棧的方法主要有采樣和預測.采樣主要根據程序運行信息的統(tǒng)計和分析建立模型,需要獲取不同架構核上的性能數據.相對于架構無關分析,考慮比如線程同步、資源競爭的實際情況,可以適應程序真實執(zhí)行狀態(tài)的變化.但是,程序的性能信息依賴于不同微架構的硬件支持,開銷比較大,因此,采樣不適宜特別的頻繁,這樣會影響對于短生命周期線程的分析,采樣的周期也決定了模型能否很好地適應程序階段的變化.同時,隨著核數的增加,可擴展性也比較差.而預測主要是根據某個核上的性能信息對其他核上的性能信息進行估計,相比于采樣,開銷和可擴展性都有所改進,但在實現過程中,根據模型的復雜程度需要獲取更多的性能信息(比如依賴指令的分布信息),就需要額外的硬件支持.(3) 經驗模型主要根據選取的測試程序獲取相關性能數據,并采用機器學習的方法建立相關性能數據和目標的關系,經驗模型的正確性主要取決于所選取的測試程序是否具有代表性,以體現明顯的微架構特征,是否可以盡可能全面地覆蓋各種程序特性等.

由于以上的分析方法各有利弊,在近期的工作中也有考慮到借鑒架構無關分析,提出基于架構無關分析、架構有關分析和經驗分析的混合模型.分析模型的正確性直接影響到調度決策的正確性,是值得重點研究的問題.

3.2.1 架構無關分析模型

Chen和John[71]提出了一種基于微架構匹配度的異構調度技術,通過分析不依賴于微架構的程序特性反映的資源需求,建立與核微架構配置參數的映射關系,他們首先從依賴指令之間的距離分布、連續(xù)訪問相同地址的內存間隔次數的分布和分支跳轉變化頻率分布3個方面分析,建立與核發(fā)射帶寬(issue width)、L1D緩存和分支預測器的適應度,通過依賴指令之間的距離分布來分析程序指令級并行程度(ILP),反映程序對于CPU發(fā)射帶寬的需求,對于依賴指令的長距離所占比重大的程序需要更大的發(fā)射帶寬.通過程序連續(xù)訪問同一物理地址的內存間隔次數的分布來分析程序的數據局部性,反映對于L1D的需求,對于內存間隔次數大的訪問所占比重大的程序需要更大的緩存.通過條件分支指令跳轉方向的變化頻率分布來反映程序的分支可預測性,意味著對于分支預測器的需求.程序中如果變化率非常高或非常低的分支指令所占比重較高的話,分支預測器的功能不需要太強大,但若變化率在 50%上下的分支所占比重較高的話,意味著分支的跳轉方向不斷變化,對于分支預測器的需求就比較高.基于以上分析,最后通過模糊推理方法將程序的資源需求從低到高進行分配,根據核的配置參數,提供程序資源需求與核的匹配度.

由于模糊推理的方法采用“IF-THEN”的規(guī)則進行核配置的匹配,實現的可擴展性比較差.Chen和John[72]提出的調度技術將程序的資源需求和核的微架構配置映射到同一多維空間,通過計算加權歐氏距離(WED)將程序分配到距離程序資源需求點最近的可用核上執(zhí)行.由于核整體的處理能力與核上所有配置參數有關,而且配置參數之間相互影響,比如在其他參數不變的情況下,不斷增加發(fā)射帶寬的配置,核處理能力增加到一定的程度也會遇到瓶頸.因此,在進行核配置參數映射函數設計時,需要考慮硬件的邊際遞減效應,也就是說,隨著硬件資源的增加,處理能力的增長空間會越來越小.他們給出的實驗結果表明,加權歐式距離越小,程序在核上執(zhí)行的效率越高.

文獻[8,73-77]借助編譯器技術基于對程序進行靜態(tài)分析,獲取調度需要的程序特性.

Shelepov[74]在2009年提出了簽名支持異構感知的調度算法(HASS),借助編譯器的反饋優(yōu)化技術在二進制文件中保存架構簽名,簽名信息主要將程序保存在不同配置核上的 LLC Misses,文獻[73]在調度之前提前對程序進行分析,通過統(tǒng)計程序連續(xù)訪問相同地址的內存間隔次數的分布來估計 LLC Misses.在進行調度時,通過LLC Misses和訪存的延時來估計程序執(zhí)行過程中由于訪存被阻塞的時間,作為能否從大核受益的評估指標,如果阻塞時間長,表示無法很好地利用大核高頻率的特性,因此在調度時分配到小核上執(zhí)行,反之,則分配到大核上執(zhí)行.該文測試了所有可能的靜態(tài)分配策略,表明 HASS調度策略對于性能的提升與最佳的靜態(tài)分配策略非常接近.該文采用的方法相比于在每個核上執(zhí)行來采樣性能數據的方法,在犧牲了部分正確性的前提下降低了開銷,而且可擴展性也較好,但是在程序執(zhí)行階段變化明顯和多線程運行競爭共享資源的場景下,調度將無法做出正確的響應.之后,文獻[74]對 HASS算法進行了改進,提出了 HASS-D,在程序執(zhí)行過程中動態(tài)統(tǒng)計緩存的缺失率.動態(tài)調度可以適應線程階段和不同輸入集的變化.

文獻[75]提出基于靜態(tài)單賦值(SSA)形式的控制流圖(CFG)動態(tài)調度技術,借助編譯技術將程序劃分為多個并行指令執(zhí)行片段,通過調度最大化地利用指令并行化處理能力.SSA形式是程序已經消除假依賴(讀后寫和寫后寫)的中間表示形式,文獻[75]通過分析將SSA形式的控制流圖中的基本塊(basic block)劃分為多個可以并行執(zhí)行的子塊,也就是說,子塊之間沒有真正的數據依賴關系,根執(zhí)行時間將子塊分配到各個核上,保證程序執(zhí)行完成需要的時間最短.該文基于背包算法進行子塊到核的分配,根據每個子塊的指令大小和執(zhí)行時間進行分配.首次分配的話根據指令大小的順序進行分配.

文獻[76]提出了在異構多核處理器上基于任務階段行為的自動分配策略,使得線程的資源需求與所執(zhí)行核的可用資源盡量匹配.該文首先通過編譯技術對程序進行分析,構造帶屬性的控制流圖(CFG),其中,每個節(jié)點由基本塊組成,對基本塊進行分類,將具有相似行為的基本塊歸為一類.同時,根據基本塊執(zhí)行的指令數確定每個塊的權重,由此構造出帶屬性的控制流圖.該文對帶屬性的控制流圖進行深度遍歷,找到以圖的某個節(jié)點為單一入口點的子圖作為程序的執(zhí)行間隔子圖,并根據子圖中每個節(jié)點的類型屬性及權重值,計算得到執(zhí)行間隔主導的類型屬性,形成帶屬性的間隔圖,每個節(jié)點帶有執(zhí)行間隔和類型的信息.根據帶屬性的間隔圖,在二進制程序中插入執(zhí)行階段標記來標記執(zhí)行間隔.該文的調度算法通過采樣的方式將程序在不同類型的核上執(zhí)行,查看在不同核上的執(zhí)行平均 IPC的比值是否超過設定的閾值,如果超過閾值,表示此執(zhí)行階段可以更多地從大核受益,此執(zhí)行階段將被分配到大核上執(zhí)行.

文獻[77]提出基于基本塊聚類分析的動態(tài)調度技術,針對有相似行為的執(zhí)行部分采用相同的調度策略.該文通過編譯器技術統(tǒng)計基本塊的指令類型(計算、訪存和分支等)分布,并對其進行聚類分析,將基本塊分為不同的類,在程序運行過程中對每類的IPC進行統(tǒng)計,為聚類后的基本塊集群設置IPC閾值,在某個核上運行的IPC超過閾值,證明性能良好,如果沒有超過閾值設置,則進行調度策略的調整.如果長時間無法超過閾值,則動態(tài)調整閾值.該文為了降低頻繁核遷移的開銷,避免基本塊的粒度過細,將參與聚類基本塊的大小閾值設置為 20條指令.

文獻[57]針對多線程程序的性能優(yōu)化,提出了最長和最關鍵的任務優(yōu)先分配到大核執(zhí)行的調度策略.該文首先提出程序中比較長的串行執(zhí)行代碼和同步部分的代碼的執(zhí)行時間會直接影響多線程程序執(zhí)行的時間.通過編譯器靜態(tài)分析多線程程序串行執(zhí)行代碼的長度和同步需要執(zhí)行的關鍵路徑(比如:鎖操作)代碼的長度,并保存在二進制程序中,當該程序對應的線程創(chuàng)建時,由程序通過系統(tǒng)調用告訴內核該任務的大小,將串行任務或者關鍵路徑長的線程分配到大核上執(zhí)行,用來降低程序執(zhí)行時間.

3.2.2 CPI棧模型

(1) 采樣

文獻[78]提出核偏好(bias)的概念,表示線程對于大核和小核的偏好,根據線程在大核和小核上的加速比來定義大核偏好和小核偏好,調度時根據核偏好進行線程的分配,偏好大核的線程被分配到大核執(zhí)行,偏好小核的線程被分配到小核執(zhí)行.該文建立了CPI棧模型,由核內阻塞(internal stall)、核外阻塞(external stall)和真正執(zhí)行(execution)占用的周期數組成.核內阻塞由核內資源的缺乏或者競爭導致,比如沒有空閑的執(zhí)行單元、重排序隊列(ROB)已滿、指令緩存缺失、TLB缺失和分支預測錯誤等;核外阻塞由核外資源的訪問和競爭導致,比如LLC Misses,訪問內存或者I/O等.通過在不同核上采樣可以證明,當線程CPI棧以執(zhí)行周期為主時,線程具有大核偏好,反之,線程具有小核偏好.該文采用簡單的CPI模型對線程進行計算密集型和訪存型的劃分,以此作為線程分配策略的依據,該文表明,這種簡單的劃分方式會導致不理想的調度策略.

文獻[79]基于間隔分析(interval analysis)理論模型提出調度算法,間隔分析模型是基于對微架構設計潛在分析而形成的一種機械模型(mechanistic model),表示程序執(zhí)行的CPI可以表示為被長延時的缺失事件分隔的持續(xù)穩(wěn)定的執(zhí)行狀態(tài),總共分為真正執(zhí)行、訪存延時和其他延時3個部分.CPIexe表示指令真正用于執(zhí)行的周期數,CPImem表示由于LLC Misses導致的內存訪問的懲罰,CPIother表示由其他缺失事件比如指令緩存缺失、分支預測錯誤等導致的懲罰.該文通過動態(tài)獲取程序性能數據構建CPI棧來統(tǒng)計線程在不同核上的性能IPC,并形成以不同CPU核配置和IPC組成的性能矩陣,作為線程分配和遷移的依據.為了避免頻繁的遷移帶來的過大的系統(tǒng)開銷,設定遷移閾值,當IPC的加速比超過閾值時,進行線程的重新分配.

(2) 預測

文獻基于CPI(cycle per instructions)棧模型對線程的性能和功耗進行估計與預測.

文獻[80]提出,雖然在大核和小核的內存級并行化比率(MLPratio)與訪存密集型程序強相關,指令級并行化比率與計算密集型程序強相關,但是只有當MLPratio和ILPratio結合可以很好地表示在不同核上的性能差異,程序在目標核的性能就可以通過MLP和ILP進行預測,因此,文獻[80]根據MLP、ILP信息和CPI棧建立性能預測模型.該模型根據周期性的統(tǒng)計架構相關的信息(包括 LLC Misses、指令數、指令之間的依賴距離分布等),結合硬件的架構參數(比如重排序隊列大小、發(fā)射帶寬)進行MLP和ILP的預測,并根據預測結果做出調度決策.該文對遷移開銷進行了評估,在2.5ms的遷移頻率的情況下,遷移造成的性能開銷少于0.6%.但是文中的評估對異構系統(tǒng)的微架構做出了簡化,假設異構系統(tǒng)中只有大核和小核,并且兩種類型的核都具有相同的緩存結構.而且,動態(tài)調度過程中周期收集的架構信息,比如指令之間的依賴距離,現有 CPU性能監(jiān)控單元無法直接獲取,需要增加額外的硬件支持.

文獻[46,80]采用相同的預測模型,假設系統(tǒng)中只有大核和小核,并且兩種類型的核都具有相同的內存結構.根據大核和小核微架構特性的不同,通過大核預測小核和通過小核預測大核采用不同的方法來估計CPIbase和CPImem.CPIbase的估計主要是對平均IPC的估計.大核的CPIbase通過大核的發(fā)射帶寬的倒數估計.小核的CPIbase通過估計小核的IPC得到,通過概率論計算在發(fā)射帶寬范圍內的IPC取值的概率之和.CPImem的估計主要是對MLP的估計,大核的 MLP主要通過小核的每條指令的 LLC Misses與重排序隊列大小的乘積而得到,小核的MLP主要通過大核的每條指令的LLC Misses與訪存缺失的Load指令之前的依賴距離的乘積而得到.該文對預測模型進行了實驗驗證,通過小核預測大核的平均錯誤率為9%,反之,平均錯誤率約為13%.

文獻[81]提出了基于CPI棧的性能分析模型,假設不同核的ICache、ITLB、BPU等資源相同,所以Icache 缺失和BPU預測錯誤事件造成的懲罰(即CPIother)是相同的.

其中,CPIexe表示一條指令真正用于穩(wěn)定執(zhí)行的周期數,受限于線程執(zhí)行過程中平均的 ILP和發(fā)射帶寬,取兩者的最小值.CPImem由 LLC Misses(文中 LLC指的是 L2)和訪存延遲來決定,由于 CPU MLP的設計,有些 LLC Misses的延遲會被覆蓋掉,因此CPImem由不會被覆蓋掉的明顯的LLC Misses及其延時決定.ILP通過分析程序的關鍵依賴路徑來估計,發(fā)射帶寬通過等待發(fā)射執(zhí)行的不同類型指令的數目大小估計,不同 L2大小情況下的L2 load缺失數采用Mattson’s stack distance model[76]進行估計.線程在一個核上的CPItotal通過PMU獲取,CPIexe和CPImem通過對程序特性分析模型進行估計和預測,計算得到程序在一個核上的CPIother信息,基于假設條件帶入CPI棧的分析模型估計其他類型核上的CPI信息.文獻[76]對此分析預測模型進行驗證,CPI的平均誤差不高于8.71%.

3.2.3 經驗模型

文獻[82]在文獻[83]的工作基礎上進行了改進,考慮 CPU微架構參數的不同,SF的估計通過機器學習(WEKA 的 additive regression模型)建立 SF與 IPC、LLC Miss Rate、L2 Miss Rate、Execution Stalls、Retirement Stalls的關系模型,并且將大核和小核的模型分開建立.為了模型的準確性,文中的訓練集選取SPECOMP 2001、NAS Parallel、PARSEC,從計算密集型、訪存、并發(fā)等角度盡可能地覆蓋線程的不同特性.

文獻[21,22]通對提前運行測試程序,對性能數據(比如IPS、LLCmisses、MIPS)進行統(tǒng)計分析得出性能預測的線性回歸模型.這種預測方法需要輸入測試的程序具有代表性,最好可以體現明顯的硬件特征,比如訪存行為頻繁,分支比較多,浮點計算密集等.

文獻[29]通過建立線性回歸模型,根據線程在一個核上執(zhí)行的IPS和LLC Misses來預測在其他不同類型核上的IPS和LLC Misses.該文主要從CPU SPEC 2006中選取有代表性的工作集和輸入集,采用機器學習軟件(Weka)中的多元線性回歸的標準實現進行建模,經過10折交叉驗證表面算法的誤差約為3%.

文獻[84]提出了一種經驗模型,在滿足性能、功耗的優(yōu)化目標下,在線程階段發(fā)生變化時對線程的分配策略進行預測.通過收集程序的運行時信息:IPC、cycle和指令類型分布向量(instructions type vector)用來表示程序的階段特征和資源需求,將程序劃分為不同的階段.當階段發(fā)生變化時,收集程序在大核上的信息,然后通過線性回歸模型預測在大核和小核上的能耗信息.所有線程根據能耗的計算值從高到低排序,采取 LIFO或者 FIFO的順序進行遷移.

3.2.4 混合模型

文獻[85]采用線性回歸模型進行 EDP的預測,經過對樣本數據的統(tǒng)計分析,EDP主要與執(zhí)行周期數、指令數、L1 Dcache訪問數、L2cache訪問數存在線性關系.靜態(tài)的功耗與執(zhí)行時間成比例,動態(tài)功耗與指令數和cache的訪問數成比例.該文提出靜態(tài)輔助分析的方法,通過對程序的靜態(tài) SSA中間表示形式(IR)的分析,識別函數調用和循環(huán)代碼以及循環(huán)的邊界,構造調用圖.為了避免由于程序行為階段的粒度過小導致頻繁的線程遷移造成的開銷,文中設定函數調用或循環(huán)的指令數閾值、調用或循環(huán)次數的閾值,超過這兩個閾值的函數調用和循環(huán)將被識別為現成的階段,若階段發(fā)生變化,則需進行線程的重新分配.

文獻[86]提出了一種針對異構多核處理器的性能和功耗分析模型.由于異構系統(tǒng)中的大核和小核的微架構存在很大差異,除了流水線組織,緩存系統(tǒng)和分支預測器等的設計都可能存在差異;而且不同核上可以獲取的硬件性能事件也可能不同,這些都增加了在不同核上進行性能和功耗分析的難度.為了解決這些問題,文獻[86]綜合編譯器輔助的架構無關分析模型、基于線性回歸的經驗模型和機械模型(mechanistic modeling)[87]形成最終的混合分析模型.該文的性能分析模型主要通過對架構相關時間對于指令執(zhí)行時間影響的量化來構建 CPI棧,其中性能事件,比如緩存缺失數、分支預測錯誤率可以直接通過硬件的性能監(jiān)控單元(PMU)獲得,不能直接通過PMU獲得的事件,比如指令之間的數據依賴關系,通過編譯器靜態(tài)分析獲得.如果要獲取某種類型核上的性能事件,則通過線性回歸模型預測在另外核上的性能時間,以達到不同核上的性能評估.在性能模型的基礎上考慮額外的因素,比如程序內存行為和指令類型的分布,來進行不同核功耗的評估.文獻[86]在真實的 ARM big.LITTLE系統(tǒng)上進行實驗結果表明了分析模型的健壯性,平均誤差在15%以內.

3.3 調度決策

調度決策主要是能夠快速、準確地捕獲程序執(zhí)行階段的變化,并根據階段的行為做出是否需要重新調度的決定.本文將調度決策分為訓練決策和預測決策.訓練決策指的是將程序的行為階段按照固定的指令窗口進行劃分,并將指令窗口的執(zhí)行劃分為訓練階段和決策階段,在訓練階段對程序進行隨機調度,并根據程序執(zhí)行行為以及優(yōu)化目標提供最優(yōu)調度策略,在決策階段,根據訓練得到的調度策略進行線程的重新調度.預測決策雖然也是按照指令窗口進行程序階段的劃分,但是每個執(zhí)行階段的調度決策不是通過訓練得來.通過模型對程序的執(zhí)行階段進行預測,如果執(zhí)行階段已經出現過,則將按照之前的調度策略進行調度.

訓練決策在對每個執(zhí)行階段進行訓練的時候,需要考慮各種調度策略的可能性,并進行調度的優(yōu)劣評估,可能會帶來比較大的系統(tǒng)開銷.同時,只有在程序執(zhí)行階段行為比較穩(wěn)定的時候,訓練決策才可以做到準確;而預測決策不需要對每個執(zhí)行階段進行訓練,效率比訓練決策會高,但是階段預測模型的正確性會直接影響調度的效果.同時,指令窗口的選擇也尤為重要,窗口選擇過大的話無法快速適應執(zhí)行階段的變化,窗口選擇太小的話可能會導致頻繁的任務遷移.因此,指令窗口的選擇需要全面的實驗和仔細的評估.

3.3.1 訓練決策

文獻[88]首先提出了一種針對異構緩存系統(tǒng)(主要是LLC大小不同)的調度算法,使線程在不同LLC大小核上運行的每條指令的緩存訪問缺失(MPI)總數最低.算法考慮了 LLC是私有和共享兩種情況,私有情況下,LLC被線程獨享,只需要選擇 MPI最小的線程進行調度.共享情況下,需要考慮線程共同被調度對緩存的影響,一個線程訪問緩存會影響到其他線程的緩存數據,該文通過估算線程訪問缺失數目所占的比例來對 MPI的值進行修正,作為調度依據.為了實現調度算法,文獻[88]在硬件中設計緩存訪問預測(ACCESS prediction engine)模塊來預測LLC的缺失數.該文選取程序執(zhí)行階段的1%作為訓練階段,進行線程的隨意調度,并根據LLC缺失的統(tǒng)計可以滿足MPI總數最低的線程分配策略,在線程執(zhí)行的穩(wěn)定階段,根據訓練階段的結果進行線程的重新分配.為了調度的準確性,訓練階段需要考慮各種調度的可能性以進行性能數據的統(tǒng)計,而且訓練結果確定之后可能會帶來線程的遷移,為了降低這些計算開銷,該文在考慮現有系統(tǒng)狀態(tài)的情況下來選擇最優(yōu)的調度策略,同時對遷移算法進行了優(yōu)化.

文獻[89]根據線程運行的歷史信息分析進行線程分配策略的優(yōu)化,適應線程執(zhí)行階段的變化.資源需求大的執(zhí)行階段將被分配到大核上執(zhí)行,若資源需求小或者線程對于正在占用核的利用變少的話,將被分配到小核上執(zhí)行.調度主要分為兩個階段:行為階段探測(phase detection)和重新分配(reassignment unit).在行為階段探測過程中,通過分析線程的吞吐量(throughput)和對CPU核的利用率(core utilization)進行資源需求的度量,吞吐量通過100K個時鐘周期內提交(retire)的指令數表示,利用率主要是分析CPU核計算資源的使用情況,通過指令窗口中不同類型的指令占有率來表示(至少包括整數指令和浮點指令).行為階段劃分的指令窗口大小選擇 100K條指令.在重新分配階段,為了避免頻繁遷移,對吞吐量和利用率的高低閾值進行設置,根據高低閾值,將線程的執(zhí)行階段類型分為 3類:UG(upgrading)、DG(downgrading)和 NC(no-change),UG的線程被重新分配到大核執(zhí)行,DG的線程被重新分配到小核執(zhí)行,NC的線程不進行重新分配.考慮到遷移的代價,并不是執(zhí)行階段發(fā)生變化就會進行線程的重新分配.每個核都有一個5位的線程階段類型變化歷史表(demand history counter),當線程類型為UG時加1,當類型為DG時減1,到了一定閾值(文中設置為6),才進行核的重分配.

3.3.2 預測決策

文獻[90]提出的調度技術在程序運行過程中對程序行為進行階段探測,同時標識和記錄程序行為階段的性能數據(主要是IPC)作為調度的依據,將線程調度到IPC高的核上執(zhí)行.該文通過工作集簽名(WSS)表示線程某個執(zhí)行階段,WSS表示線程在一定指令窗口內提交指令的集合表示.線程不同執(zhí)行階段的區(qū)分通過兩個WSS的距離(即 WSS中不同位的個數)計算得到,為了去噪,定義執(zhí)行階段變化閾值,如果兩個 WSS之間不同位數除以WSS的總位數高于50%的話,將兩個階段標識為不同,階段發(fā)生變化并且是新出現的階段,將對線程在各個核上的IPC進行統(tǒng)計,并根據IPC進行調度.該文設計實現工作簽名歷史表保存每個階段的WSS及此階段的IPC數據.每個執(zhí)行階段的WSS計算是通過指令執(zhí)行地址計數器(PC)的哈希計算映射到512個字節(jié)的向量表中,向量表中的1位表示指令緩存的64個字節(jié)的大小.當映射到向量表里對應的位的指令已提交,那么相應的位置1,沒有執(zhí)行的位置 0,向量表各位值的序列就是WSS的值.文獻[90]提出,計算 WSS的指令窗口如果選擇過小,將會導致線程執(zhí)行階段的劃分比較多,從而會導致過大的遷移開銷,因此,通過實驗選取50K作為執(zhí)行階段識別的指令窗口.

文獻[91]提出了以降低功耗為目標的感知程序執(zhí)行階段的調度算法,證明當程序行為和特性發(fā)生變化的時候進行線程的動態(tài)分配可以有效降低功耗.采用與文獻[83]相同的程序執(zhí)行階段探測算法,采用的度量標準是系統(tǒng)的EDP(energy-delay product),調度算法將分配線程到運行此線程EDP比較小的核上執(zhí)行.文獻[91]假設程序相同執(zhí)行階段具有相似的 EDP,當執(zhí)行階段發(fā)生變化的時候,進行重新調度.線程新的階段出現的時候,將在每種類型的核上對 EDP進行采樣,根據采樣結果進行調度.下次出現相同執(zhí)行階段時,根據之前的結果進行調度.

3.4 算法評估

對異構調度算法有效地進行評估需要實驗平臺更加真實地對異構多核處理器環(huán)境進行建模.由于通過DVFS調整核的電壓和時鐘頻率無法真實地仿真異構多核處理器,所以,越來越多的研究工作采用真實的異構硬件、模擬器或者通過評估模型來進行算法的效果評估.

3.4.1 真實硬件

文獻[66,92]采用(non-uniform memory access,簡稱 NUMA)服務器作為實驗平臺,文獻[66]提出可以感知NUMA架構的虛擬機調度算法,以降低NUMA系統(tǒng)的內存局部性問題所帶來的影響.文獻[92]提出感知NUMA架構的線程遷移策略,通過在線監(jiān)控線程的常駐工作集(WSS)預測線程遷移的代價,如果線程從核A遷移核B,并且A和B在NUMA不同的節(jié)點,線程在核A的WSS最大并且超過了核B的LLC大小,則預測線程遷移的代價非常大,由于導致很高的LLC Misses而不進行遷移,根據此策略進行線程遷移的優(yōu)化從而提高系統(tǒng)性能.文獻[93]采用ARM big.LITTLE架構的開發(fā)板作為實驗平臺,主要包括2個Cortex A15和3個Cortex A7,該文主要提出了基于價格理論的調度優(yōu)化技術,目的是在滿足系統(tǒng)性能的前提下降低功耗,而 ARM big.LITTLE架構可以表現良好功耗性能的異構特性.

3.4.2 模擬器

現在進入市場的異構產品,比如NUMA和ARM big.LITTLE,針對特定架構和特性,配置相對固定,無法通過靈活的參數配置和定制進行算法的測試.與之相比,采用架構模擬器支持更靈活的配置,可以全面地對算法進行評估.文獻[46]使用sniper進行異構的配置,大核配置為4發(fā)射亂序處理核心,小核配置為4發(fā)射順序處理核心.文獻[71]采用 Simscalar模擬異構多核處理器,每個核都采用亂序超標量技術,通過在發(fā)射帶寬、L1D緩存的大小、分支預測器的大小采用不同的配置來進行異構的模擬.文獻[85]采用 Intel Quick IA作為評估的異構平臺,Quick IA是Intel的FPGA的SoC原型驗證平臺,該文在平臺上對低功耗的Atom Core和高性能的Xeon Core的異構處理器構建進行仿真.通過模擬器進行不同核的微架構配置相對方便,而且核之間的差異度也更加貼近真實的異構系統(tǒng),但是模擬器模擬的正確性與真實硬件畢竟存在偏差,因此,為了調度算法評估結果適用于真實的硬件平臺,首先需要對模擬器的正確性進行驗證和校準.

3.4.3 評估模型

然而,由于模擬器本身速度受限,無法支持大量混合工作負載(比如:數百個并行程序)在合理時間內執(zhí)行完成.有些工作建立了分析模型以進行異構處理環(huán)境下的程序性能(或功耗)的評估,分析模型不需要像模擬器那樣對異構多核處理器的微架構進行詳細模擬,通過模型和算法對復雜工作負載場景下的程序性能進行評估,相比于模擬器來說,速度更快,可擴展性更好,但是分析模型的正確性在算法評估時變得尤為重要.

文獻[94]提出分析模型MPPM(multi-program performance model)來評估并發(fā)多程序的性能.由于多個程序并發(fā)執(zhí)行時,多核之間的資源競爭會影響程序的進度,反過來,每個程序執(zhí)行的進度也會影響資源競爭的程度.MPPM的輸入是每個程序獨立地在每個核運行的性能數據,包括總的CPI、訪存CPI和訪問Cache地址的記錄,因此需要提前對這些性能數據進行測試和統(tǒng)計.模型算法的初始狀態(tài)是假設所有的程序都以單核執(zhí)行的狀態(tài)開始,通過對 Cache訪問競爭和訪存 CPI的監(jiān)控分析,評估多核間資源競爭對于程序 CPI的影響,也就是說,由于資源競爭導致的CPI下降,算法將調整CPI為考慮資源競爭影響的CPI(文獻[94]中稱其為多核CPI),然后算法不斷迭代直到退出.通過MPPM可以對并發(fā)多程序工作負載下每個程序的CPI進行評估,從而根據CPU計算系統(tǒng)的吞吐量(STP)和每個程序的平均執(zhí)行時間(ANTT).通過與時鐘精確的架構模擬器的結果進行對比,在2核、4核和8核的情況下,MPPM模型估計的STP平均誤差是1.4%、1.6%和1.7%,ANTT的平均誤差為1.5%、1.9%和2.1%.

MPPM 同時支持同構和異構多核處理器的性能,在異構多核處理器環(huán)境下,算法將首先對所有程序在所有核上獨立執(zhí)行的性能數據進行收集分析,然后隨機選擇測試的benchmark程序分配到N個Core上,通過MPPM進行異構多核處理器環(huán)境下的程序 CPI的估計.由于性能評估的結果與測試程序調度的算法密切相關,模型也可被用作調度算法效果的評估.

4 總結與展望

伴隨計算機系統(tǒng)的日趨復雜和應用需求的多樣化,異構多核處理系統(tǒng)逐漸成為主流.調度技術作為充分管理和利用異構多核處理器的主要手段變得尤為重要[95],然而傳統(tǒng)操作系統(tǒng)中的調度技術主要針對同構多核處理器結構設計,沒有充分考慮程序的行為特性、資源需求和CPU微架構的差異性,無法對硬件架構和工作負載的差異性進行有效感知,影響了調度決策的準確性.本文針對性能非對稱性異構多核處理環(huán)境下的調度優(yōu)化技術的挑戰(zhàn)及已有研究工作進行了系統(tǒng)的總結.

異構調度的目標是根據負載特性和核之間微架構的差異,將程序分配到最適合的核上運行.最主要的問題是如何感知微架構和程序特性的差異,并根據優(yōu)化目標采用相對最優(yōu)的任務分配和遷移策略.因此,本文從優(yōu)化目標、分析模型、調度決策和算法評估這4個方面對異構調度技術已有工作進行了詳述.由于異構環(huán)境中比如大核和小核的流水線設計差異、緩存架構差異等為各種優(yōu)化目標的定義和實現提供了更加復雜的場景,優(yōu)化目標需要在定義和滿足優(yōu)化目標的度量標準時,感知程序在不同微架構運行的差異.本文分別從滿足性能、能效、公平性、并發(fā)程序瓶頸優(yōu)化及特定應用領域優(yōu)化等目標來描述異構調度的工作,比如滿足性能主要通過加速比、IPC比率、關鍵代碼大核執(zhí)行等的衡量標準將程序分配到更加受益的核上.分析模型主要在程序資源需求分析的時候建立程序特性與不同微架構之間的關聯,作為調度的主要依據.本文主要總結了架構無關分析、CPI模型、經驗模型方法,由于分析方法各有利弊,在近期的工作中綜合這幾種分析方法提出了混合分析模型.由于程序資源需求伴隨執(zhí)行階段而發(fā)生變化,為了實現細粒度的異構調度,調度決策主要通過對程序階段變化的感知來進行任務遷移的決策,主要的方法包括訓練和預測模型,預測決策不需要對每個執(zhí)行階段進行訓練,效率比訓練決策會高,但是預測模型的正確性會直接影響調度的效果.最后,總結了對調度算法進行評估的方法,在使用真實的異構硬件和模擬器的基礎上,描述了評估模型相關的工作,在異構硬件環(huán)境有限的前提下,分析模型不需要像模擬器那樣對異構多核處理器的微架構進行詳細模擬,通過模型和算法對復雜工作負載場景下的程序性能進行評估,相比于模擬器來說,速度更快,可擴展性更好,但是評估模型的準確性就變得尤為重要.

然而,當前異構計算機處理系統(tǒng)變得越來越復雜,核的數量和種類不斷增加,同時,更多關注微架構設計的持續(xù)優(yōu)化與新軟件技術的深度融合,出現了 AI芯片和深度學習處理器并開始應用.以內存為例,在關于摩爾定律未來的討論中,有專家表明,傳統(tǒng)的DRAM訪問延時如果從200ns降低為150ns,整體的數據中心的功耗將下降15%.片上內存的架構設計成為一個有潛力的改進方向,文獻[96]證明,片上內存有大于10倍的延時縮短和功耗降低.2016年,Google公司公布了張量處理器——TPU(tensor processing unit),將深度學習等新型軟件技術應用在芯片設計中,將處理復雜應用的難度從軟件系統(tǒng)降低到硬件架構的層面來實現,在未來還可能會將頻繁使用的軟件處理算法,比如大數據的排序、查找等直接固化在片上內存中.同時,3D集成電路[97,98](3DIC)等新技術在芯片設計中的應用,將額外或者共享的資源(比如重排序隊列、緩存系統(tǒng)等)拓展到第三維度,達到資源的細粒度共享和相對較低的延遲.這些復雜的異構環(huán)境為調度優(yōu)化目標的建立和滿足提出了更為復雜的環(huán)境和需求,需要考慮更多的因素.異構感知的調度技術與硬件及微架構的深度融合還有很多工作可以探索.

(1) 伴隨異構處理器的應用尤其是在移動終端市場的普及,在滿足性能和其他服務質量(QoS)指標的前提下,通過調度來降低功耗是被關注的工作,處理器從硬件層面提供DVFS(dynamic voltage and frequency)、DPM(dynamic power management)等電源管理技術,軟件層面的調度技術如何根據用戶QoS需求與硬件提供的電源管理技術深度融合以降低功耗是值得研究的方向.同時,目前的硬件暫沒有提供度量程序功耗的接口,軟件一般也沒有提供程序行為變化的接口,因此,在滿足異構調度優(yōu)化目標尤其是功耗目標的工作中,軟硬件深度融合的協同工作將是未來主要的方向.

(2) 分析模型是異構感知調度重要的工作,伴隨著異構環(huán)境的日趨復雜,指令和硬件類型的種類越來越多,差異度也越來越大,比如存在多種指令集(ARM、X86),存在普通內存(DRAM)和非易失性內存(non-volatile memory,簡稱NVM)等多種內存,而且由于程序執(zhí)行過程中競爭或者執(zhí)行異常和錯誤會造成動態(tài)的異構變化,這就給分析模型在不同微架構配置核上的性能評估帶來了困難.如果處理器硬件能夠提供合理的輔助程序分析模塊,就可以在系統(tǒng)層面提供相應的接口供調度做出更為準確的決策.比如文獻[99]設計硬件模塊監(jiān)控線程的行為,并進行其他核上的性能預測.硬件輔助分析的方式雖然提高了調度決策的準確性,速度也會更快,但是增加了硬件設計和實現的開銷,需要軟硬件設計更好的協同,最好可以在操作系統(tǒng)層面提供接口,為調度提供直接的支持.

(3) 在調度決策方面,現在主要還是在當前指令窗口中采用邊訓練邊決策的方式進行調度,在復雜的異構環(huán)境下,如何能夠快速、準確地預測程序執(zhí)行階段的變化,并快速進行決策值得繼續(xù)探索.同時,任務遷移也需要程序設計、編譯器和系統(tǒng)架構給出優(yōu)化的思路,如果兩個核之間具有不同的指令集架構就又增加了實現的難度,目前在這方面還需要做更多的研究.

(4) 近年出現軟件技術如近似計算(approximate computing)、近閾值計算(near-threshold computing)、內存系統(tǒng)的數據壓縮技術也將推進更多樣化的多核異構系統(tǒng)進入市場,這些計算對于能效提出了更高的要求,例如:百萬兆的計算目標在 20MW的功耗下1s完成 1018次計算[100],通過異構調度來滿足優(yōu)化目標還有很多工作需要探索.

總之,隨著硬件芯片技術和軟硬件融合技術的發(fā)展,為了更好地適配和管理異構硬件,不僅僅是調度算法,與之相關的操作系統(tǒng)及相關軟件都有很多工作要做.