趙 姍,楊秋松,李明樹

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

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

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

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

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

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

1 異構(gòu)多核處理器定義與分類

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

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

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

Fig.1 The structure of homogeneous and heterogeneous multicore processors圖1 同構(gòu)和異構(gòu)多核處理器結(jié)構(gòu)

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

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

Table 1 The category of asymmetric multicore processors表1 異構(gòu)多核處理器分類

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

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

Table 2 The micro-architecture configuration of Cortex A15&A7表2 Cortex A15&A7的微架構(gòu)參數(shù)

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

2 異構(gòu)調(diào)度的問題與挑戰(zhàn)

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

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

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

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

(3) 算法評(píng)估的方式直接影響異構(gòu)調(diào)度算法的驗(yàn)證效果,評(píng)估平臺(tái)或者模型的構(gòu)建需要異構(gòu)的特性,對(duì)算法做出正確的評(píng)估.

本文從優(yōu)化目標(biāo)、分析模型、調(diào)度決策和算法評(píng)估這4個(gè)方面對(duì)異構(gòu)感知的調(diào)度所面臨的問題與挑戰(zhàn)進(jìn)行了總結(jié)和討論.

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

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

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

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

2.2 分析模型問題

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

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

2.3 調(diào)度決策問題

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

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

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

2.4 算法評(píng)估問題

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

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

3 異構(gòu)調(diào)度技術(shù)

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

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

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

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

3.1 優(yōu)化目標(biāo)

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

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

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

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

文獻(xiàn)[8]分析了對(duì)于計(jì)算密集型程序(極端情況下,如果ASTPI為0),SF為MIPS的比值.對(duì)于內(nèi)存密集型程序(極端情況下,如果ASTPI無窮大),SF接近1.實(shí)驗(yàn)結(jié)果與IPC驅(qū)動(dòng)的調(diào)度算法性能對(duì)比有明顯提升,核類型越多,效果越明顯.

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

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

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

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

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

(1) 滿足能效

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

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

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

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

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

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

(2) 滿足實(shí)時(shí)任務(wù)時(shí)間約束

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

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

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

(3) 滿足用戶體驗(yàn)需求

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

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

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

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

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

3.1.3 滿足公平性

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

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

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

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

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

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

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

1) 程序同步

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

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

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

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

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

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

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

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

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

2) 資源競(jìng)爭(zhēng)

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

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

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

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

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

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

3.1.5 特定應(yīng)用領(lǐng)域優(yōu)化

文獻(xiàn)[66-69]提出異構(gòu)多核處理器環(huán)境下的虛擬機(jī)調(diào)度優(yōu)化技術(shù).

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

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

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

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

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

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

3.2 分析模型

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

由于以上的分析方法各有利弊,在近期的工作中也有考慮到借鑒架構(gòu)無關(guān)分析,提出基于架構(gòu)無關(guān)分析、架構(gòu)有關(guān)分析和經(jīng)驗(yàn)分析的混合模型.分析模型的正確性直接影響到調(diào)度決策的正確性,是值得重點(diǎn)研究的問題.

3.2.1 架構(gòu)無關(guān)分析模型

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

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

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

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

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

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

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

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

3.2.2 CPI棧模型

(1) 采樣

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

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

(2) 預(yù)測(cè)

文獻(xiàn)基于CPI(cycle per instructions)棧模型對(duì)線程的性能和功耗進(jìn)行估計(jì)與預(yù)測(cè).

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

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

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

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

3.2.3 經(jīng)驗(yàn)?zāi)Ｐ?/p>

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

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

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

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

3.2.4 混合模型

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

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

3.3 調(diào)度決策

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

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

3.3.1 訓(xùn)練決策

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

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

3.3.2 預(yù)測(cè)決策

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

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

3.4 算法評(píng)估

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

3.4.1 真實(shí)硬件

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

3.4.2 模擬器

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

3.4.3 評(píng)估模型

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

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

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

4 總結(jié)與展望

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

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

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

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

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

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

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

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