基于強化學習的溫度感知多核任務調度?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 相關工作

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

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

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

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

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

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

2 基礎知識

2.1 強化學習概述

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

Fig.1 Reinforcement learning圖1 強化學習

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

2.2 Q-Learning算法

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

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

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

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

3 動機案例

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

3.1 LTB

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

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

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

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

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

Fig.3 Comparison of the same reward function under different environmental state models圖3 相同獎勵函數,不同環境狀態模型下的對比

Fig.4 Comparison of the same environment state model and different reward functions圖4 相同環境狀態模型,不同獎勵函數下的對比

3.2 DSM

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

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

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

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

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

4 ReLeTA 溫度感知調度方法

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

4.1 模型概述

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

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

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

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

(1) 環境狀態模型

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

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

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

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

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

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

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

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

最終,ReLeTA 中單個內核的狀態信息由下式表達:

而所有內核的當前狀態組合起來表示當前的系統狀態,系統狀態表示如下:

(2) 獎勵函數

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

(3) 動作空間

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

其中,ai表示為把當前任務分配到核i上運行,n是系統所擁有的內核數.

4.3 Q值近似

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

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

其中,θ={θ1,θ2,…,θn}表示神經網絡的參數,b表示偏置,Si是內核i的系統狀態,如式(8)所示.針對此神經網絡,我們使用梯度下降和以下損失函數來更新其參數θ:

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

4.4 Q-Learning參數設置

(1) 學習率

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

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

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

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

4.5 算法實現

5 實 驗

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

5.1 實驗配置

(1) 實驗環境

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

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

(2) 測試程序

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

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

5.2 實驗結果

(1) ReLeTA 與LTB

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

任務調度過程中,兩種調度方法均使用Linux 系統中的“ondemand”頻率調節方式.

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

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

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

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

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

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

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

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

為了進一步對比兩種方法的可擴展性,我們在20 核的實驗平臺上進行了對比實驗.實驗中使用由15 個任務構成的任務組合,按順序將這15 個任務各執行1 000 次.為了減少數據采集所導致的系統開銷,實驗每4s 采集一次系統的溫度信息.圖11 顯示了兩種方法在整個執行周期的峰值溫度變化,可以看出,ReLeTA 的峰值溫度絕大多數情況下優于LTB,峰值溫度平均降低了1.35°C.除了峰值溫度,我們還采集了系統的平均溫度和任務所運行內核的溫度,具體溫度變化情況如圖12 所示,具體溫度數據總結見表4.可以看出,ReLeTA 平均峰值溫度比LTB 降低了1.59°C,任務所調度內核的溫度相比于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 核系統中運行15 任務組合時系統的峰值溫度

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 核系統下運行15 任務組合時的系統平均溫度和任務運行所在內核的溫度

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

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

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

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

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

實驗結果展示在圖13 中,可以看出,整個實驗過程中,DSM 運行溫度較低.這是因為DSM 使用了主動調頻,使用較低的運行頻率來控制溫度,但同時導致單個程序運行時間更長.該方法下,運行完所有程序所需要的時間大約為3 000s;而其他方法以較高的頻率運行程序,運行完所有程序的時間為1 500s 左右.運行完所有程序后,系統進入空閑狀態從而降低系統溫度.我們以DSM 的執行時間為周期,計算了在這段時間間隔內4 種方法的平均系統溫度,結果匯總在表6 中.在整個任務執行周期,本文所提算法相對于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 默認調度方式的實驗結果

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

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

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

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

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

6 總結

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