楊世貴 ,王媛媛,2,5 ,劉韋辰 ,姜 徐 ,趙明雄 ,方 卉 ,楊 宇,劉 迪,

1(云南大學 軟件學院,云南 昆明 650504)

2(中國科學院 信息工程研究所,北京 100093)

3(School of Computer Science and Engineering,Nanyang Technological University,Singapore)

4(東北大學 計算機科學與工程學院,遼寧 沈陽 110169)

5(中國科學院大學 網(wǎng)絡空間安全學院,北京 100049)

隨著計算機在日常生活中的普及,人們對其高性能和便攜性的需求日漸增強,由此推動著現(xiàn)代計算機不斷向多內(nèi)核、高集成度的方向發(fā)展.芯片中晶體管尺寸縮小(最新晶體管達到nm 級別),因此在同一尺寸內(nèi)可以放置更多的處理器.高集成度讓多核系統(tǒng)的處理器比以往具有更高的功率密度,可以帶來較高的性能,但也使系統(tǒng)的運行溫度大幅度提高且難以耗散,從而導致了芯片的老化不均勻,加速芯片磨損和故障,降低系統(tǒng)的可靠性以及性能.通常采用兩種方法來幫助多處理器系統(tǒng)有效的管理系統(tǒng)溫度.

1)物理方式:通過加散熱效果更好的散熱設備來降低系統(tǒng)溫度,然而散熱效果更好的散熱設備不可避免地提高系統(tǒng)的整體制造成本以及系統(tǒng)的能耗,從而使得芯片成本效益降低;

2)軟件方式:通過設計一個溫度感知的程序調(diào)度算法來優(yōu)化系統(tǒng)溫度,即:任務進入系統(tǒng)時,調(diào)度算法為程序選擇合適的處理器來運行程序,從而達到控制系統(tǒng)溫度的目的.

因靈活性高且不需要任何外部設備的輔助,基于軟件方式的溫度控制方法一直是多處理器研究領域的一個熱門研究課題.

早期的研究多采用基于線性規(guī)劃[1,2]、動態(tài)規(guī)劃[3]或者啟發(fā)式算法[4]設計溫度感知的調(diào)度算法,然而隨著計算機內(nèi)核數(shù)量的快速增長,以及各種復雜計算任務的出現(xiàn),傳統(tǒng)的溫度感知調(diào)度算法不能夠有效地適應不同的復雜計算環(huán)境[5].與此同時,隨著機器學習[6]的興起,機器學習技術在不同的領域展現(xiàn)出了很強的自我學習能力,因此有很多工作開始研究基于機器學習的溫度感知調(diào)度算法[7].使得溫度感知調(diào)度算法研究工作朝著智能化的方向發(fā)展.首先是基于監(jiān)督學習的方法:線性回歸[8,9]和分類算法[10],雖然這些方法在特定的情況下取得了很好的效果,但是模型的準確率依賴高質(zhì)量及多樣化的標簽數(shù)據(jù),且訓練模型泛化性能不佳,即,針對一個硬件訓練的方法很難直接使用到新的硬件平臺.另一方面,強化學習的出現(xiàn),在一定程度上克服了監(jiān)督學習存在的數(shù)據(jù)依賴問題以及模型泛化性弱的問題.強化學習不需要大量的訓練數(shù)據(jù),而通過和運行環(huán)境的動態(tài)交互來學習一個策略,在面對完全陌生的情況時,強化學習可以根據(jù)自己學習的策略來進行最優(yōu)的決策,比監(jiān)督學習的方法靈活性更強.出于以上原因,強化學習被廣泛應用于各種復雜的動態(tài)決策的場景,并且在各個領域取得很好的效果,例如,DeepMind 在2015 年提出的強化學習玩游戲完勝人類[11],DeepMind 提出的基于強化學習的AlphaZero擊敗了頂級的職業(yè)圍棋選手[12],圍棋在之前一直被認為是一個復雜度很高、機器很難擊敗人類的項目.計算機系統(tǒng)狀態(tài)有較強的動態(tài)性以及程序調(diào)度本身是一個復雜的決策問題,適合采用強化學習來解決.一些工作已經(jīng)研究了基于強化學習的溫度感知任務調(diào)度算法,但是目前存在的基于強化學習的系統(tǒng)溫度優(yōu)化方法中均存在一些問題,如環(huán)境建模不合理、獎勵設置不合理,因此未能夠使基于強化學習的溫度感知調(diào)度方法達到最好性能,此部分將在后文中詳細討論.

針對現(xiàn)有方法中存在的問題,針對多處理器系統(tǒng),我們提出了一種全新的基于強化學習的溫度感知任務調(diào)度算法來進行系統(tǒng)溫度的管理和控制,根據(jù)其英文名(reinforcement learning temperature-aware task allocation)將其命名為ReLeTA.本文具體的研究貢獻如下:

1)針對現(xiàn)有方法存在的缺點,本文提出了一種新的系統(tǒng)狀態(tài)建模方法,新狀態(tài)可以更準確地反映系統(tǒng)運行狀況與溫度之間的關系;同時,提出了一種新的獎勵函數(shù)用于協(xié)助優(yōu)化強化學習算法;對比了現(xiàn)有的兩種基于強化學習的研究方法.實驗證明,我們的建模方式更加有效.基于新的狀態(tài)模型和獎勵函數(shù),本文提出了一種新的基于強化學習的溫度感知多核任務分配算法——ReLeTA.

2)我們在不同的真實系統(tǒng)上對所設計的算法進行了評估,對比了現(xiàn)有的兩個基于強化學習的溫度感知任務調(diào)度算法和Linux 默認的調(diào)度算法,本文所提新方法能夠在基本不損失性能的基礎上降低系統(tǒng)溫度:最好情況下降低平均峰值溫度6°C,降低平均溫度3°C.

本文第1 節(jié)討論溫度感知調(diào)度方面的相關工作.第2 節(jié)介紹了強化學習相關的理論知識方便理解本文的貢獻.第3 節(jié)詳細討論現(xiàn)有方法的缺陷,以此說明新方法的必要性.第4 節(jié)詳細介紹本文算法的模型和參數(shù)設置.第5 節(jié)詳細展示了在真實平臺的實驗結果.第6 節(jié)對本文進行總結并討論了未來工作的方向.

1 相關工作

目前,溫度管理技術在學術界和工業(yè)界都受到了極大的關注,已有很多研究致力于控制芯片的溫度[7].早期的研究多采用基于線性規(guī)劃[1,2]、動態(tài)規(guī)劃[3]或者啟發(fā)式算法[4]設計溫度感知的任務調(diào)度算法,然而隨著計算機內(nèi)核數(shù)量的快速增長,以及各種復雜計算任務的出現(xiàn),傳統(tǒng)的溫度感知調(diào)度算法不能夠有效地適應不同的復雜計算環(huán)境.

隨著機器學習的發(fā)展,各類機器學習算法被廣泛地應用在各個領域內(nèi),解決著大量過去難以處理的問題,展現(xiàn)著巨大的應用潛力.因此,更多的研究將ML(machine learning[6])利用到多核系統(tǒng)溫度管理領域,提出了多種系統(tǒng)溫度優(yōu)化算法.本文總結了目前主流的溫度優(yōu)化方法,分別從靜態(tài)和動態(tài)兩方面介紹.

?靜態(tài)方法通常利用監(jiān)督學習,通過訓練大量的數(shù)據(jù)得到溫度、性能預測模型,在設計系統(tǒng)的過程中訓練好一個固定的算法模型,并將其應用于任務調(diào)度中[13].文獻[14]基于自適應學習樹算法來預測空閑期開始時間并選擇性地將其調(diào)至低功耗睡眠狀態(tài),從而達到降低系統(tǒng)功耗、降低系統(tǒng)溫度的目的.另外,還有一種使用貝葉斯分類技術的電源管理框架[15],利用監(jiān)督學習來預測處理器的性能狀態(tài),查找并執(zhí)行最優(yōu)的電源管理操作,從而達到降低系統(tǒng)溫度的目的.文獻[9]提出一種基于線性回歸模型的方法,通過采集任務運行時性能計數(shù)器的值和傳感器的值來訓練預測模型進行任務映射.以上使用監(jiān)督學習的方法需要大量的訓練數(shù)據(jù),然而高質(zhì)量且多樣化的訓練數(shù)據(jù)集往往難以獲取,導致了這些方法對于數(shù)據(jù)集外其他任務的分配效果未必能夠達到預期目標;同時,基于一個硬件訓練的模型很難移植到其他不同的硬件上.

?動態(tài)方法區(qū)別于靜態(tài)方法,其能夠在運行過程中持續(xù)地學習改進自身算法.在溫度感知調(diào)度中,動態(tài)方法能夠在運行過程中優(yōu)化溫度,不會受到訓練數(shù)據(jù)和系統(tǒng)硬件的局限.目前已有的動態(tài)算法,如借用松弛技術動態(tài)管理峰值溫度[16]、基于神經(jīng)網(wǎng)絡的自適應技術來降低溫度[17]、基于強化學習的自適應技術通過迭代溫度變化來控制任務映射以優(yōu)化核心溫度等.其中,強化學習能夠更靈活地處理動態(tài)決策問題,在性能和復雜性方面達到一個均衡.因此,利用強化學習進行芯片溫度管理的研究工作逐漸增多.

一種啟發(fā)式的基于強化學習的溫度管理方法在文獻[18]中被提出,該方法通過設置溫度閾值和功耗閾值來限制狀態(tài)空間和動作空間.該方法每個內(nèi)核有一個屬于自己的Q 表,能有效提高算法的收斂速度,但是隨著內(nèi)核的增多,存儲Q 表會帶來巨大的空間開銷.此外,如何有效保證每個內(nèi)核的Q 表都能收斂是最大的問題.文獻[19]提出一種根據(jù)當前芯片溫度狀態(tài)來預測并執(zhí)行能最大限度降低未來最高溫度的任務分配策略算法,但是該方法算法模型的設置不合理,對于獎勵和狀態(tài)模型的設置過于簡單,沒有全面考慮到影響芯片溫度變化的多個因素,造成了算法的效果和性能不能達到最佳,且該方法只是在仿真平臺運行和測試.文獻[20]設計了一個基于強化學習的溫度感知調(diào)度算法,同時加入了系統(tǒng)動態(tài)調(diào)頻方法,該方法基于溫度循環(huán),并將系統(tǒng)的延遲作為獎勵的一個部分.雖然該方法同時考慮了溫度和性能,但因其獎勵函數(shù)設置不合理導致其很難實現(xiàn)溫度和性能的最佳權衡.后面我們在真實的系統(tǒng)上對比了這兩種方法.

溫度感知的調(diào)度方法有些時候也可以和系統(tǒng)能耗控制方法結合在一起,首先是動態(tài)電源管理(dynamic power management,簡稱DPM)[21]技術根據(jù)工作設備的負載情況動態(tài)的選擇各個內(nèi)核的電源狀態(tài),切換各個處理器的工作模式(活動模式或低功耗模式等).另一種是動態(tài)電壓頻率調(diào)整(DVFS)[22]技術,利用了芯片的特性,可以根據(jù)內(nèi)核的實際功耗來調(diào)節(jié)其工作電壓或頻率.這兩項技術的本質(zhì)都是降低系統(tǒng)功耗,達到有效控制芯片整體溫度的目的.在后面的工作中,我們會考慮將DPM 和DVFS 技術與ReLeTA 相結合,探索更優(yōu)的任務分配算法.

2 基礎知識

2.1 強化學習概述

強化學習屬于機器學習范疇內(nèi)的一個重要分支,其本質(zhì)是通過與環(huán)境連續(xù)的交互來尋找一個最優(yōu)的決策.強化學習中包含有智能體(agent)、環(huán)境(environment)、狀態(tài)(state)、動作(action)和獎勵(reward).強化學習模仿了生物通過與外界交互來在環(huán)境中進行決策的行為(如圖1 所示):智能體通過執(zhí)行動作來影響環(huán)境,環(huán)境接收到新動作之后會產(chǎn)生新的狀態(tài),并對剛才的動作進行一個獎勵反饋,根據(jù)所返回的新的狀態(tài)來決定其需要進行的動作.強化學習的訓練過程就是智能體不斷地根據(jù)當前環(huán)境狀態(tài)進行動作決策,同時根據(jù)環(huán)境反饋的獎勵值及時改進其決策的過程,最終的目標是找尋一個最優(yōu)策略,即智能體能夠從環(huán)境狀態(tài)改變的過程中累積盡可能多的獎勵值.

Fig.1 Reinforcement learning圖1 強化學習

強化學習與機器學習中其他需要大量訓練數(shù)據(jù)的學習算法不同,它不需要使用大量的數(shù)據(jù)樣本,而是通過不斷的試錯進行自我學習,這種自動進行學習和決策的方法能夠解決監(jiān)督學習方法所面臨的由于系統(tǒng)動態(tài)性所導致的訓練數(shù)據(jù)不全面的問題,更適用于多核溫度感知調(diào)度算法.

2.2 Q-Learning算法

隨著強化學習的發(fā)展,在Q-Learning 的基礎上出現(xiàn)了很多效果更穩(wěn)定的強化學習算法,如A3C[23]、DDPG[24]等.但是這些算法相比于Q-Learning 會帶來更大的開銷:更新策略過程中的算力開銷和推理最佳動作的時間開銷,這對于系統(tǒng)級的算法來說是不可接受的.為了權衡調(diào)度算法的開銷和調(diào)度算法的最終效果,ReLeTA 最終選擇Q-Learning 作為框架中的學習算法.Q-Learning算法是一個基于價值的離軌策略算法,Q值指的是智能體在特定狀態(tài)下執(zhí)行特定動作所能夠獲得獎勵的期望值[25],算法通過建立一個以狀態(tài)(state)為行、動作(action)為列的Q 表來存儲和更新Q值,Q值的更新如式(1)所示:

其中,α,γ分別表示學習率和折扣系數(shù).α用于控制每次Q值更新的幅度,決定了算法收斂的速度以及最終算法的收斂效果,學習率較大則收斂較快但可能導致最終的性能不穩(wěn)定.為了節(jié)省時間和保證最終收斂的效果,一般將學習率初始化為較大的值,然后逐漸縮小.γ是數(shù)值在0～1 之間的折扣因子,強化學習的目標是為了能獲得更多的長期收益,智能體會對未來動作的收益進行考慮.但是未來動作的選擇具有不確定性,且離當前時間點越遠對當前動作的影響越小,所以在Q值的計算中,將未來可能執(zhí)行動作的Q值進行折扣.γ值為0,則只考慮當前的獎勵.γ值越大,則表示對未來考慮的越多.Q-Learning 中智能體的決策使用了ε-greedy 策略:智能體的決策包括兩個部分,其中一個是應用(exploit),另一個是探索(explore).智能體以1?ε(0<ε<1)的概率選擇目前Q值最大的動作,這就是對當前學習到的策略的應用.而探索是指智能體以ε的概率隨機選擇動作來探索可能存在的更優(yōu)的策略,這樣做能防止智能體學到次優(yōu)策略.

Q-Learning算法通過圖2 所示的步驟實現(xiàn):首先構建一個m×n的Q 表(其中,m為狀態(tài)數(shù),n為動作數(shù)),并將表格內(nèi)的值初始化為0.智能體根據(jù)當前的狀態(tài)來計算所有動作的Q值,結合Q值和ε-greedy 策略來選擇動作,決策后會獲得新的狀態(tài)和一個回報值,然后使用式(1)來更新Q 表,在反復的迭代更新Q 表后,智能體會學習到較好的策略.

Fig.2 Flow of the Q-Learning algorithm圖2 Q-Learning算法的流程

3 動機案例

本節(jié)將討論當前流行的兩種基于強化學習的溫度管理算法,并通過在真實系統(tǒng)上運行來評估這兩種方法存在的問題,以此作為ReLeTA 方法的動機.

3.1 LTB

文獻[19]與ReLeTA 的調(diào)度方式相似,本節(jié)首先對該文獻進行討論.為了方便后文進行討論,將文獻[19]中的算法命名為LTB.算法LTB 通過溫度傳感器讀取所有處理器的溫度,而將這些溫度用作強化學習中的環(huán)境狀態(tài)模型,智能體將程序分配到不同的處理器上運行.假定有CPU 有n個處理器核心,則動作空間與處理器核心數(shù)一致都為n.在LTB 中,獎勵函數(shù)r定義如下:

其中,Tem為內(nèi)核的最高閾值溫度,Tmax為當前所有內(nèi)核的最高溫度值.式(2)中,獎勵函數(shù)存在獎勵和智能體動作之間關聯(lián)度較低的缺陷.當系統(tǒng)中運行多個任務時,當前分配任務的內(nèi)核不一定就是溫度最高的核.這樣導致獎勵函數(shù)與動作之間相關性不夠高,根據(jù)獎勵函數(shù)優(yōu)化的溫度感知調(diào)度算法就很難達到一個最優(yōu)的效果.

為了展示LTB 方法存在的缺陷,我們在真實的系統(tǒng)上評估了其性能.實驗平臺設置如下:處理器為Inter Core i7-4790 8 處理器,其最大頻率為3.6GHz;實驗操作系統(tǒng)為Ubuntu 18.04 LTS 的4 核計算機上使用Parsec benchmark[26]中的facesim 應用程序來進行實驗驗證(本文將該任務設為單任務組合,在第5 節(jié)實驗配置部分說明).重復執(zhí)行該程序1 000 次,并記錄系統(tǒng)溫度變化數(shù)據(jù).為了避免溫度波動影響圖像的展示,將每5 個單位數(shù)據(jù)取平均值繪制成圖,因此,1 000 次程序執(zhí)行總共采樣溫度200 次.圖中step指采樣的次數(shù),y軸是系統(tǒng)的峰值溫度.作為參考方法,本組實驗選用了本文所提出的狀態(tài)模型和獎勵函數(shù)作為對比.當使用相同的獎勵函數(shù)和不同的環(huán)境狀態(tài)模型(即本文所提出的環(huán)境狀態(tài)模型)時,如圖3 所示,使用LTB 環(huán)境狀態(tài)模型的多核系統(tǒng)溫度管理方式與本文提出的方式相比,處理器中內(nèi)核的最高溫度提高了平均1.3°C.這是由于LTB 所設計的環(huán)境狀態(tài)模型僅僅考慮了所有內(nèi)核的當前溫度,該方式太過簡單,無法準確地展現(xiàn)處理器內(nèi)核的負載變化以及溫度的變化趨勢,因此對溫度的控制效果略有不足.

圖4 展示了使用相同的環(huán)境狀態(tài)模型和不同的獎勵函數(shù)(即本文所提出的獎勵函數(shù))時,處理器內(nèi)核最高溫度的變化情況.使用LTB 獎勵函數(shù)下的內(nèi)核的最高溫度增加了平均2.0°C,這是由于該獎勵函數(shù)考慮的是某一狀態(tài)下所有內(nèi)核的最高溫度值Tmax與閾值溫度的差值,而在真實的系統(tǒng)中,不同的動作(任務分配)可能會產(chǎn)生相同的Tmax,導致模型不能很好地區(qū)分不同動作的效果,使得該獎勵函數(shù)不能準確地幫助模型進行策略選擇.

這里可以看出,LTB 的狀態(tài)模型沒能有效地反映系統(tǒng)溫度變化,其獎勵函數(shù)與任務分配關聯(lián)度較低,導致了其效果不佳.而本文所提出的環(huán)境狀態(tài)模型同時兼顧了系統(tǒng)負載信息和溫度以及溫度變化趨勢(詳細信息見第4 節(jié)),能較為全面地反映當前的系統(tǒng)狀態(tài).同時,新提出的獎勵函數(shù)相比于LTB 中的獎勵函數(shù)不僅考慮到了整體的溫度,也提高了動作與獎勵的相關性,從而產(chǎn)生更優(yōu)異的溫度控制效果.

Fig.3 Comparison of the same reward function under different environmental state models圖3 相同獎勵函數(shù),不同環(huán)境狀態(tài)模型下的對比

Fig.4 Comparison of the same environment state model and different reward functions圖4 相同環(huán)境狀態(tài)模型,不同獎勵函數(shù)下的對比

3.2 DSM

本文還研究了當前另一種基于強化學習的溫度管理算法[20],后文中簡稱該方法為DSM.在DSM 中,作者使用兩個指標:熱應力(由于溫度變化使得芯片在各種約束下所有的應力反應)和老化程度作為最小化溫度的環(huán)境狀態(tài),并將這兩個指標加入到獎勵函數(shù)的計算結果中.該方法采用了一個較為復雜的動作空間,同時對任務進行調(diào)度并相應地主動調(diào)節(jié)系統(tǒng)頻率.在獎勵函數(shù)中,DSM 將延遲考慮進去,通過加入延遲約束來同時優(yōu)化溫度和保證延遲.然而通過實驗發(fā)現(xiàn),此方法并不能在這溫度和性能兩者之間達到一個很好的平衡.使用之前相同的計算平臺,采用DSM 方法調(diào)度程序facesim 進行實驗,選擇test為程序的輸入集,因DSM 需要加入一個約束延遲,通過實驗測試facesim 在本次實驗環(huán)境下的最低運行時間為4.0s,最高運行時間為19.0s.我們選擇將DSM 的延遲設置為5s,反復調(diào)用1 200 次.

圖5 展示了第850 次～第885 次的運行實驗結果,包含了程序運行時間和系統(tǒng)溫度.

Fig.5 Peak temperature of the system and the running time of facesim under the DSM method圖5 DSM 方法下系統(tǒng)的峰值溫度和facesim 的運行時間

根據(jù)圖5 所示的結果,在該程序執(zhí)行850 次后,DSM 方法在訓練很多次之后仍然不能夠達到一個較為穩(wěn)定的結果,出現(xiàn)了很多延遲低但溫度很高和延遲高卻溫度很低的情況.這是因為該方法的獎勵函數(shù)中雖然同時考慮了溫度和性能,但是并未對二者進行有效的權衡,造成了系統(tǒng)的溫度波動以及程序的程序執(zhí)行時間變化,并不能夠滿足制定的延遲約束條件.

從本節(jié)對現(xiàn)有方法的討論可以看出,現(xiàn)有的基于強化學習的溫度感知調(diào)度算法仍然存在一些問題.為了改善現(xiàn)有方法的缺陷,本文提出了全新的溫度感知調(diào)度算法ReLeTA,通過全新的建模方式來實現(xiàn)高效的溫度感知多核處理器調(diào)度.

4 ReLeTA 溫度感知調(diào)度方法

本節(jié)將對提出的算法進行全面的討論,包括對算法的總體設計以及建模方法都進行了詳細描述.

4.1 模型概述

圖6 展示了ReLeTA 的整體框架,目前,ReLeTA 的調(diào)度算法是在用戶空間(user space)實現(xiàn),在未來考慮將其實現(xiàn)于操作系統(tǒng)內(nèi)核中.作為一個多核系統(tǒng)的任務調(diào)度器,當一個新的應用程序到達后,ReLeTA 從底層硬件獲取狀態(tài)信息,隨后與操作系統(tǒng)進行交互,通過CPU_affinity 將程序分配到對應的處理核心上.系統(tǒng)完成程序分配之后返回獎勵值,并根據(jù)獎勵值來更新策略.其中,底層硬件是處理器的內(nèi)核,現(xiàn)代CPU 在每個計算內(nèi)核上都設有傳感器,可以直接讀取處理器當前的運行溫度.在工作過程中,操作系統(tǒng)將所獲取的處理器頻率、利用率以及溫度信息傳遞給ReLeTA 來優(yōu)化調(diào)度策略.整個ReLeTA算法的系統(tǒng)開銷較小,通常在1ms 之內(nèi),詳細的系統(tǒng)開銷實驗結果可見第5 節(jié)表8.在下面的章節(jié)中,將詳細介紹ReLeTA 如何使用從底層獲取的系統(tǒng)信息.

Fig.6 ReLeTA framework model圖6 ReLeTA 框架模型

4.2 溫度感知的強化學習建模

對Q-Learning 來說,最重要的部分就是設置有效的環(huán)境狀態(tài)模型、動作空間及獎勵函數(shù),使智能體也就是溫度感知調(diào)度器可以快速地學習到一個策略來有效降低系統(tǒng)的溫度.本節(jié)將詳細介紹ReLeTA 如何對這幾個方面進行建模.

(1) 環(huán)境狀態(tài)模型

強化學習需要一個精確的環(huán)境模型,可以準確地反映出系統(tǒng)變化和獎勵以及智能體動作之間的關系,從而幫助智能體快速學習到一個最優(yōu)的策略.因此,環(huán)境狀態(tài)模型是否能精確地體現(xiàn)當前系統(tǒng)的狀態(tài),是任務調(diào)度器至關重要的一部分.一個準確、全面的環(huán)境狀態(tài)模型更有助于找到最優(yōu)的任務分配策略,也能夠促進任務調(diào)度器快速地收斂到最優(yōu)的策略.

溫度感知任務調(diào)度器的最終目的是要實現(xiàn)系統(tǒng)溫度的優(yōu)化,因此在建模系統(tǒng)狀態(tài)時,首先對系統(tǒng)溫度相關的因素進行分析.目前,大部分基于Linux 的操作系統(tǒng)都使用“ondemand”調(diào)頻模式,在此模式下,系統(tǒng)根據(jù)CPU 當前的利用率來動態(tài)地調(diào)節(jié)運行頻率[27]:系統(tǒng)負載較高,則提高頻率來加速任務的運行;負載降低后,系統(tǒng)降低運行頻率達到節(jié)能的目的.為了觀察影響系統(tǒng)溫度的不同要素,我們采用了與第4 節(jié)相同的實驗環(huán)境,在系統(tǒng)中反復調(diào)用parsec 測試集中的facesim 程序,同時采集任務所在內(nèi)核的運行頻率、利用率和溫度,采集的系統(tǒng)數(shù)據(jù)繪制在圖7 中.通過觀察可以看到:系統(tǒng)的利用率和運行頻率均與溫度有很高的相關性,當利用率和運行頻率大幅度上升時,溫度也會大幅度上升;反之,溫度也隨之下降.因此,我們將每個處理器的運行頻率和利用率作為強化學習中狀態(tài)的一部分.然而,將所有處理器核心的運行頻率和利用率加入到系統(tǒng)狀態(tài)中會導致狀態(tài)的維度很大,當系統(tǒng)處理核心增加之后,不利于算法的可擴展性,也會導致強化學習的系統(tǒng)開銷增加.因此,我們將同一個內(nèi)核的利用率和運行頻率以相加的形式合并到一個變量中.然而在不同的調(diào)頻模式下,頻率和利用率對溫度的影響不一致,因此我們對它們進行加權求和,公式如下:

其中,wf,wu分別為頻率和利用率對應的權重值,且兩個參數(shù)滿足wf+wu=1.通過實驗結果發(fā)現(xiàn),在“ondemand”調(diào)頻模式下的最佳權重為:為t時刻核i的利用率,計算機中內(nèi)核利用率是介于0 和1 之間的值,頻率則一般處于200MHz 至4GHz 之間,兩個指標之間數(shù)值相差較大.當指標間的水平相差很大時,直接使用原始指標值作為狀態(tài),就會突出數(shù)值較高的指標對系統(tǒng)狀態(tài)的影響,同時削弱數(shù)值較低指標的作用.因此,為了確保頻率和利用率處于同一數(shù)值范圍內(nèi),對頻率進行歸一化處理[28],式(3)中表示為t時刻核i的歸一化運行頻率.運行頻率的歸一化處理方式如下:

其中,Fcurrently_i為核i的當前頻率,Fmax為核的最大運行頻率.

Fig.7 Relationship between operating frequency and core utilization with core temperature圖7 運行頻率和內(nèi)核利用率與內(nèi)核溫度之間的關系

我們在真實系統(tǒng)中對比了合并利用率和頻率作為系統(tǒng)狀態(tài)和單獨使用利用率和頻率作為狀態(tài)下的實驗效果,發(fā)現(xiàn)合并狀態(tài)后的效果并未差于將兩個狀態(tài)分開表示.

為了全面反映當前系統(tǒng)的狀態(tài),除了系統(tǒng)利用率和頻率信息,還需要考慮系統(tǒng)的溫度信息.現(xiàn)有方法如LTB,直接使用所有內(nèi)核的當前溫度作為系統(tǒng)狀態(tài).然而系統(tǒng)溫度變化很快,僅用內(nèi)核的當前溫度并不能較好地反映系統(tǒng)的溫度變化趨勢.在溫度管理的文獻中,通常同時使用當前溫度和溫度梯度來表示當前系統(tǒng)的溫度變化趨勢[18],然而,直接用一個2n維的數(shù)據(jù)來表示系統(tǒng)的溫度狀態(tài)會帶來巨大的空間和時間開銷.從當前溫度和溫度變化以及降維的角度出發(fā),我們采用了文獻[29]中所提出的方法來表示當前內(nèi)核的溫度狀態(tài):

其中,Ti(t)為核i在t時刻的溫度,Ti(t?Δt)為核i在t?Δt時刻的溫度,b是由處理器決定的常數(shù),Δt表示間隔時間.這些參數(shù)在文獻[29]中進行了詳細的介紹,在此處不做描述.式(5)涵蓋了系統(tǒng)的當前溫度和溫度變化趨勢,相比于LTB 能更好地反映系統(tǒng)溫度信息,而相比于文獻[18],則實現(xiàn)了有效降維.為了使溫度狀態(tài)與合并的系統(tǒng)狀態(tài)處于相同的數(shù)值范圍,我們使用系統(tǒng)的最大閾值溫度Tthreshold對當前溫度狀態(tài)進行歸一化:

最終,ReLeTA 中單個內(nèi)核的狀態(tài)信息由下式表達:

而所有內(nèi)核的當前狀態(tài)組合起來表示當前的系統(tǒng)狀態(tài),系統(tǒng)狀態(tài)表示如下:

(2) 獎勵函數(shù)

強化學習是通過智能體不斷地執(zhí)行操作和評估環(huán)境所反饋的獎勵值來改善其學習策略,因此,獎勵函數(shù)的設置決定了任務調(diào)度器學習到最優(yōu)策略的時間和學習策略的最終效果.現(xiàn)有文獻的獎勵函數(shù)存在一定缺陷:LTB 的獎勵函數(shù)與動作之間相關性不夠高,DSM 的獎勵函數(shù)復雜度高且很難實現(xiàn)溫度和性能的均衡.這兩種情況均不利于智能體學習到最優(yōu)的任務調(diào)度策略.因此,我們提出了一種新的獎勵函數(shù)來高效地指導調(diào)度器學習到最優(yōu)的溫度感知調(diào)度策略.新的獎勵函數(shù)公式如下:

(3) 動作空間

強化學習中的動作空間指智能體可以執(zhí)行的所有動作的集合,ReLeTA 是一個溫度感知的調(diào)度器,其目標就是將程序調(diào)度到不同的處理器上,從而達到降低系統(tǒng)溫度的目的.因此,我們將ReLeTA 的動作空間定義如下:

其中,ai表示為把當前任務分配到核i上運行,n是系統(tǒng)所擁有的內(nèi)核數(shù).

4.3 Q值近似

ReLeTA 使用Q-Learning算法來訓練調(diào)度策略,傳統(tǒng)的Q-Learning算法使用Q值表格來存儲不同狀態(tài)、動作下所獲得的Q值,然而隨著狀態(tài)空間和動作空間的增加,會導致存儲Q值所需的內(nèi)存空間呈指數(shù)形增長.為了緩解這一問題,通常采用神經(jīng)網(wǎng)絡來近似估計不同狀態(tài)動作組合下的Q值,將Q 表的更新問題變成一個函數(shù)擬合問題.在ReLeTA 中,使用同樣的方法來處理存儲Q 表帶來的內(nèi)存開銷問題.

為了設計一個簡單且準確的神經(jīng)網(wǎng)絡來擬合Q值,我們對網(wǎng)絡的層數(shù)和神經(jīng)元的個數(shù)對模型的影響進行了評估.使用大量不同的神經(jīng)網(wǎng)絡進行了多組測試后,發(fā)現(xiàn)“輸入層-隱藏層-輸出層”這種3 層結構的神經(jīng)網(wǎng)絡,隱藏層的神經(jīng)元個數(shù)設置為2×n,能使算法達到較好的效果且開銷較低,而增加網(wǎng)絡層數(shù)或隱藏層神經(jīng)元個數(shù)都不能使得效果有明顯提升.因此綜合考慮效果和系統(tǒng)開銷,我們選擇3 層神經(jīng)網(wǎng)絡來擬合Q值:

其中,θ={θ1,θ2,…,θn}表示神經(jīng)網(wǎng)絡的參數(shù),b表示偏置,Si是內(nèi)核i的系統(tǒng)狀態(tài),如式(8)所示.針對此神經(jīng)網(wǎng)絡,我們使用梯度下降和以下?lián)p失函數(shù)來更新其參數(shù)θ:

其中,r為狀態(tài)s下執(zhí)行動作a的獎勵,r+γmaxQ(s′,a′,θ)為目標Q值,而Q(s,a,θ)是真實的Q值.Q-Learning 通過目標值和真實值之間的誤差期望值建立損失函數(shù).

4.4 Q-Learning參數(shù)設置

(1) 學習率

Q-Learning 中,學習率表示了Q值更新的幅度,決定了算法的收斂速度和最終的收斂效果.學習率較大時,算法收斂較快,但一定程度上會影響性能[30].所以通常初始化一個較大的學習率,隨著算法運行次數(shù)的增加,逐步縮小學習率,從而使算法收斂速度較快且最終性能較好.在ReLeTA 中,我們通過實驗來經(jīng)驗性地確定最佳學習率.實驗平臺與第4 節(jié)中的一致.通過反復調(diào)度同一個任務,來觀察不同的學習率下算法的收斂效率和對溫度的控制效果,實驗結果如圖8 所示.需注意,采用不同的程序不會影響圖8 所獲得的實驗結果.可以看出,學習率初始化為0.8 的情況下,算法收斂速度最快且溫度控制較好;其他方法最終也能達到類似的溫度降低效果,但所需的時間更長.因此我們采用0.8 作為算法的初始學習率來更新神經(jīng)網(wǎng)絡權重.

Fig.8 Convergence of temperature under different learning rates圖8 不同學習率下溫度的收斂情況

(2) 貪婪策略(ε-greedy)

Q-Learning 在決策學習過程中,如果每次都選擇當前狀態(tài)下Q值最大的動作,容易導致所學策略收斂到局部最優(yōu)的結果.因此,強化學習算法通常使用貪婪策略(ε-greedy)來進行一定比例的隨機探索,從而避免策略收斂到局部最優(yōu).具體來說,貪婪策略就是在每次動作選擇時,以概率ε來隨機選擇一個動作,而不采用當前最大Q值的動作.在ReLeTA 中同樣使用了貪婪策略:為了學習到最優(yōu)的任務調(diào)度策略,在任務調(diào)度初期將探索的概率ε設置為0.4;隨著任務調(diào)度次數(shù)的增加,逐步縮小ε,最終保持在0.03.這樣,算法初期可以嘗試更多的策略,而后期減少探索偏向于使用優(yōu)化過的策略.

4.5 算法實現(xiàn)

5 實 驗

為了驗證ReLeTA 的性能,我們通過大量基于真實硬件平臺的實驗對所提出方法進行了全方位的評估,并與現(xiàn)有的幾種方法進行了對比.相比于之前的很多方法采用系統(tǒng)模擬和數(shù)值模擬的實驗方式,在真實系統(tǒng)上的評估更能反映出各個方法的實際效果.

5.1 實驗配置

(1) 實驗環(huán)境

為了驗證所提出方法的有效性和可擴展性,本次實驗采用了3 種不同的計算機硬件平臺進行實驗,表1 列出了3 種實驗平臺的配置.本次實驗中使用的操作系統(tǒng)均為Ubuntu 18.04,內(nèi)核版本為4.15.0.

Table 1 Computer configuration information表1 計算機配置信息

(2) 測試程序

本次實驗采用了Parsec 程序集[26],Parsec 程序集中的程序種類多樣,能充分代表計算機中常見的各種不同類型的程序,因此被廣泛地用于計算機系統(tǒng)性能測試.為了驗證算法在不同程序集下的效果,我們使用表2 中的不同程序以及不同的程序輸入來組成更加多樣化的測試集,隨機生成3 任務組合、5 任務組合、8 任務組合、15 任務組合這4 種.為了保證實驗的公平性,對每個任務組我們通過隨機生成一個時間間隔(時間間隔介于0.1s～1.6s 之間)來生成一個程序調(diào)度序列,然后對不同的方法使用相同的序列.對于不同的對比實驗,我們針對實驗需求采用了不同的溫度采集方法,在后面的實驗會進行具體說明.實驗中所用到的測試任務信息和輸入信息展示在表2,與Parsec 程序集相關的輸入信息不在此處進行詳細地描述.

Table 2 Test tasks and inputs表2 測試任務和輸入

5.2 實驗結果

(1) ReLeTA 與LTB

現(xiàn)有的基于溫度感知的調(diào)度算法中,DSM 同時考慮了性能和溫度,每個任務都有特定的性能約束,在進行任務分配的同時,還進行系統(tǒng)內(nèi)核頻率調(diào)節(jié).而ReLeTA 和LTB 都僅通過任務調(diào)度來優(yōu)化系統(tǒng)溫度,不主動進行頻率調(diào)節(jié).兩種方法的動作空間及優(yōu)化目標一致,所以本節(jié)首先對兩種方法進行全面的實驗對比,通過在不同的平臺下調(diào)度不同的任務集,來對比兩種方法對系統(tǒng)溫度的管理效果.

任務調(diào)度過程中,兩種調(diào)度方法均使用Linux 系統(tǒng)中的“ondemand”頻率調(diào)節(jié)方式.

第1 組實驗選取程序fluidanimate(輸入為simdev)在2 核的平臺上運行,在系統(tǒng)中反復調(diào)用1 400 次,每次任務運行結束采集一次系統(tǒng)峰值溫度,結果如圖9 所示.

Fig.9 Peak system temperature when LTB and ReLeTA run a single task in the 2-core platform圖9 LTB 和ReLeTA 在2 核平臺中運行單任務時系統(tǒng)峰值溫度

從圖中可以看出,在任務反復調(diào)度200 次后,我們方法的峰值溫度明顯低于LTB,在整個任務執(zhí)行周期的峰值平均溫度比LTB 降低1.8°C.值得注意的是,兩種方法下任務運行的平均時間均為0.68s.

為了進一步增加硬件的內(nèi)核數(shù)和程序的多樣性,我們在4 核平臺上的展開實驗,結果如圖10 所示.

Fig.10 Peak temperature of the system under different task combinations of LTB and ReLeTA圖10 LTB 與ReLeTA 在不同任務組合下系統(tǒng)的峰值溫度

實驗分別使用3 任務組合、5 任務組合、8 任務組合和15 任務組這4 個任務集對兩種方法進行了對比實驗.每個實驗中,將任務集中的程序隨機調(diào)度2 000 次,并記錄每次程序運行結束時的系統(tǒng)峰值溫度.X軸表示程序執(zhí)行的次數(shù),Y軸表示為峰值溫度.

從實驗結果來看,ReLeTA 相比于LTB 能進一步降低系統(tǒng)溫度.表3 總結了實驗的溫度差異數(shù)據(jù),從該數(shù)據(jù)可以看出,在最好的情況下,ReLeTA 在8 任務組合下平均溫度降低了4°C,在5 任務組合下兩種方法的最高溫度差達到了13°C.從圖10 和表3 中可以看出,當執(zhí)行3 任務組合和5 任務組合時,運行初期LTB 的性能要略微優(yōu)于本文方法.這是因為LTB 的狀態(tài)簡單,當測試程序數(shù)量較少時,LTB 可以更快地學習到有效的任務調(diào)度策略;但是隨著程序運行次數(shù)的增加,ReLeTA 的溫度管理效果逐漸優(yōu)于LTB.同時可以看到:隨著測試程序種類的增加,ReLeTA 展現(xiàn)出更優(yōu)越的溫度管理效果,說明ReLeTA 面對多樣的程序時具有更強的適應性.

Table 3 Temperature difference of the system under different task groups of LTB and ReLeTA表3 LTB 和ReLeTA 不同任務組下系統(tǒng)的溫度差

為了進一步對比兩種方法的可擴展性,我們在20 核的實驗平臺上進行了對比實驗.實驗中使用由15 個任務構成的任務組合,按順序?qū)⑦@15 個任務各執(zhí)行1 000 次.為了減少數(shù)據(jù)采集所導致的系統(tǒng)開銷,實驗每4s 采集一次系統(tǒng)的溫度信息.圖11 顯示了兩種方法在整個執(zhí)行周期的峰值溫度變化,可以看出,ReLeTA 的峰值溫度絕大多數(shù)情況下優(yōu)于LTB,峰值溫度平均降低了1.35°C.除了峰值溫度,我們還采集了系統(tǒng)的平均溫度和任務所運行內(nèi)核的溫度,具體溫度變化情況如圖12 所示,具體溫度數(shù)據(jù)總結見表4.可以看出,ReLeTA 平均峰值溫度比LTB 降低了1.59°C,任務所調(diào)度內(nèi)核的溫度相比于LTB 則大大降低,平均降低了5.26°C.

Fig.11 Peak temperature of the system when LTB and ReLeTA run 15 tasks in the 20-core system圖11 LTB 和ReLeTA 在20 核系統(tǒng)中運行15 任務組合時系統(tǒng)的峰值溫度

Fig.12 Average temperature of the system and the temperature of the core where the task is running when LTB and ReLeTA run 15 tasks in the 20-core system圖12 LTB 和ReLeTA 在20 核系統(tǒng)下運行15 任務組合時的系統(tǒng)平均溫度和任務運行所在內(nèi)核的溫度

Table 4 System temperature of LTB and ReLeTA running 15 tasks in the 20-core system表4 LTB 和ReLeTA 在20 核系統(tǒng)中運行15 任務組的系統(tǒng)溫度情況

我們在20 核的平臺使用Hyper-Threading 技術將邏輯內(nèi)核數(shù)擴展到40 核開展進一步的測試.因篇幅有限,我們在此處不展示詳細的溫度變化圖,統(tǒng)計的實驗結果總結在表5 中.可以看出,在兩種方法下,峰值平均溫度相差0.9°C,平均溫度相差了1.4°C,運行任務所在內(nèi)核的平均溫差較大達到了3.5°C.在40 核的情況下,峰值平均溫度差相比于20 核有所下降.這是因為在40 核下,我們使用了與20 核實驗中相同的任務集,相比于20 核的運行環(huán)境出現(xiàn)了更多的空閑時間,導致系統(tǒng)峰值溫度和平均溫度降低.

Table 5 System temperature of LTB and ReLeTA running 15 tasks in the 40-core system表5 LTB 和ReLeTA 在40 核系統(tǒng)中運行15 任務組的系統(tǒng)溫度情況

(2) ReLeTA 與DSM、LTB 和Linux 之間的比較

在第2 個實驗中,加入了DSM 和Linux 的CFS 調(diào)度方式[31]來進行對比.本次實驗采用了4 核實驗平臺,選用了3 個運行時間存在一定差異的程序:canneal、dedup、facesim 來進行實驗.因為DSM 需要指定任務的延遲約束,通過在系統(tǒng)上進行測試,將3 個程序的約束依次設置為:2ms,43ms,5s.每個任務各執(zhí)行400 次,執(zhí)行過程中,我們采集了所有程序的運行時間以及每次程序運行結束時的系統(tǒng)溫度.針對ReLeTA、LTB 和Linux,直接使用Linux 默認的“ondemand”調(diào)頻模式來控制系統(tǒng)頻率.

實驗結果展示在圖13 中,可以看出,整個實驗過程中,DSM 運行溫度較低.這是因為DSM 使用了主動調(diào)頻,使用較低的運行頻率來控制溫度,但同時導致單個程序運行時間更長.該方法下,運行完所有程序所需要的時間大約為3 000s;而其他方法以較高的頻率運行程序,運行完所有程序的時間為1 500s 左右.運行完所有程序后,系統(tǒng)進入空閑狀態(tài)從而降低系統(tǒng)溫度.我們以DSM 的執(zhí)行時間為周期,計算了在這段時間間隔內(nèi)4 種方法的平均系統(tǒng)溫度,結果匯總在表6 中.在整個任務執(zhí)行周期,本文所提算法相對于DSM 僅高出0.6°C;而相對于其他兩種方法,我們的方法降低的平均峰值溫度分別為5.8°C 和2.5°C.

Fig.13 Experimental results of ReLeTA,LTB,DSM,and Linux default scheduling methods圖13 針對ReLeTA、LTB、DSM、Linux 默認調(diào)度方式的實驗結果

Table 6 Comparison of various methods with DSM表6 多種方法與DSM 對比

DSM 的目標是在滿足性能約束的前提下進行系統(tǒng)溫度優(yōu)化,然而正如我們在圖5 所展示,DSM 復雜的獎勵函數(shù)很難實現(xiàn)溫度和性能的平衡.表7 對所有方法中不滿足性能約束的情況進行了總結,DSM 方法下,任務canneal、dedup、facesim 分別有41%,5%和4%的情況下不滿足延遲約束,而本文所提方法只有極少量的情況下出現(xiàn)約束不滿足的情況.綜合溫度和性能的考慮,相比于其他兩種方法,ReLeTA 能在保證性能的情況下,將系統(tǒng)溫度保持在較低的狀態(tài).

Table 7 Proportion of running three tasks under four methods that do not meet the time constraint (%)表7 4 種方法下運行3 種任務不滿足時間約束的占比(%)

除溫度和性能,本文對3 種方法下的時間開銷進行了統(tǒng)計評估,總結見表8.此處的時間開銷是指各個方法從系統(tǒng)讀取狀態(tài)到最終完成任務調(diào)度的時間間隔,3 種方法的平均開銷都在保證在1ms 以內(nèi),但是DSM 運行任務過程中的最大開銷是其他兩種方法的3 倍左右.因為DSM 讀取了溫度循環(huán)再進行了一系列的計算得到真正的狀態(tài),再計算各個動作下的Q值,中間的計算量較大,所以時間開銷最大(并且DSM 動作包括了任務映射和調(diào)頻).本文方法的開銷高于LTB,主要由于本文狀態(tài)模型更為復雜.

Table 8 Time overhead under the three methods表8 3 種方法下的時間開銷

6 總結

多核系統(tǒng)的溫度管理已經(jīng)成為多核系統(tǒng)領域一個重要的研究課題,由于機器學習方法在各個方面的應用均取得巨大突破,受到了關注.其中,強化學習作為靈活性最高的機器學習算法,被廣泛運用于各種復雜動態(tài)決策問題.目前已經(jīng)有很多基于強化學習的系統(tǒng)溫度管理研究工作,然而當前存在的基于強化學習的系統(tǒng)溫度管理方法在狀態(tài)和獎勵函數(shù)建模中均存在一些問題,使得算法很難實現(xiàn)性能、溫度和復雜度得較好平衡.通過對當前相關工作的總結,本文提出了全新的狀態(tài)建模和獎勵函數(shù)建模方法,并且在不同真實的硬件平臺上使用不同的任務集進行了全面的實驗評估.相比于現(xiàn)有的兩種方法,本文所提的ReLeTA 方法可以實現(xiàn)更好的溫度管理,降低系統(tǒng)的峰值溫度和平均溫度.ReLeTA 在本文中僅僅考慮了任務的調(diào)度,為了能夠?qū)崿F(xiàn)一個全方位的溫度管理系統(tǒng),需要進一步考慮主動控制系統(tǒng)的頻率.在未來的工作中,我們將進一步將如何有效主動控制系統(tǒng)頻率考慮到ReLeTA 中.