基于機器學習的異構感知多核調度方法

安 鑫，康 安，夏近偉，李建華，陳 田，任福繼

（1.合肥工業大學計算機與信息學院，合肥 230601；2.情感計算與先進智能機器安徽省重點實驗室（合肥工業大學），合肥 230601）

（*通信作者電子郵箱xin.an@hfut.edu.cn）

0 引言

自計算機誕生以來，現代計算機處理系統的發展開始呈現多元化的趨勢，規模上實現了從小型的手持設備、筆記本電腦到集群服務器、數據中心的全覆蓋。另一方面其應用領域也日趨多樣化和復雜化，涵蓋了多媒體、信息的加解密、網絡服務和云同步、視覺和語音識別、自然語言處理等，這些不同類型的應用程序呈現出不同的程序特性和資源需求［1］。單核處理器受功耗、面積和成本等因素限制發展已經接近極限，為了應對當前應用的復雜性和對高性能、低功耗的需求，包含多個不同類型處理核的異構多核（heterogeneous multi-core）平臺［2］已經成為主流的解決方案。

異構多核平臺不同于傳統的同構多核中處理核比較單一的情況，它具有不同類型的處理核，每種類型的處理核又具有不同的微架構，如：有些處理核是順序流水線設計，有些是亂序流水線設計；有的處理核具有較大的緩存架構，有的處理核具有較小的緩存架構等。根據指令集架構和微架構的不同可以劃分為單指令集異構多核平臺和多指令集異構多核平臺，其中：單指令集異構多核平臺中的處理核具有相同的指令集架構，但具體的微架構實現不同；而多指令集異構多核平臺中的處理核具有不同的指令集架構。單指令集異構多核平臺主要將高性能高功耗的處理核和低性能低功耗的處理核進行集成，滿足多樣化的應用程序需求，由于處理核都為同一套指令集架構，因此無需額外的編程環境即可實現協同工作，程序執行點可以任意地進行遷移，如Arm 的Big.Little 架構將兩種不同微架構的CPU（Cortex-A7 和Cortex-A5）進行集成，滿足了移動領域下用戶對高性能和低功耗的需求［3］。多指令集異構多核平臺主要以CPU-GPU為代表，CPU-GPU架構利用專門化的圖形處理單元對可以高并發處理的程序片段提供加速支持，但該架構下不同類型的處理核之間的協同工作需要編程環境支持，不允許隨意地遷移程序的執行點到不同類型的處理核上。本文主要針對單指令集架構的異構多核平臺調度方法進行研究，因此下文中沒有額外說明的異構多核平臺皆為單指令集架構。

異構多核平臺通?？梢圆l執行多個應用程序，并且每個應用程序的行為和資源需求往往也會隨時間發生變化。為了適應這種動態執行場景并充分發揮出異構多核處理器的優勢，需要解決的很重要的一個問題是如何根據系統需求對應用程序進行動態的資源映射和調度。一個好的異構調度策略需要能夠感知異構處理器系統各個處理核之間的異構性和線程行為的不同特性，在對不同映射方案進行高效評估的基礎上，動態地進行線程到處理核的映射。這種決定某個線程應該映射到哪個處理核的問題類似于機器學習技術已成功得到應用的推薦系統要解決的推薦問題（比如一些視頻點播網站為用戶推薦他們可能會喜歡的視頻［4-5］）。

以神經網絡為代表的機器學習（Machine Learning，ML）和深度學習（Deep Learning，DL）技術目前已經在推薦系統、計算機視覺和自然語言處理等領域取得了巨大的成功。盡管機器學習類似于黑盒模型，所學到的輸入數據和輸出數據的關系通常難以被人們理解，但在輸入數據足夠多時，機器學習方法常常能提供出色的預測精度。目前已經不少工作嘗試將ML 引入到異構多核系統調度問題中并取得了不錯的效果［6］。這方面的工作主要有兩類：一類工作是僅針對如何對調度方案的性能或功耗等指標構建準確高效的預測模型［7-8］，這類工作需要結合其他在線搜索方法構成完整的動態映射和調度方案。另外一類是在第一類的基礎上如何設計完整的線程或任務的動態映射和調度方法［9-10］。這類方法除了要構建準確高效的性能預測模型之外，還需要解決運行時隨著線程行為等發生變化、何時對線程進行重新映射從而達到最優化運行的問題。目前大部分這類解決方案均基于固定的調度周期（如1 ms）進行映射選擇計算，而應用程序的運行行為大多呈現出階段變化的特征［11］，每個階段的運行行為相對穩定，而且往往持續較長時間，因而，過于頻繁的在線映射計算并不一定會改善當前的映射效果，反而會在一定程度上抵消整體映射和調度方案的效果。

本文提出了一種基于機器學習、能快速準確評估程序性能和程序行為階段變化的檢測技術來有效確定重映射時機，從而最大化系統性能的映射和調度解決方案。該方法通過合理選擇處理核和線程運行時的靜態和動態特征來有效感知異構處理所帶來的處理核計算能力和工作負載運行行為的差異，從而構建更加準確的預測模型；通過引入階段檢測技術來盡可能減少在線映射計算的次數，從而提供更加高效的調度方案；通過與Linux 系統使用的經典完全公平調度（Completely Fair Scheduler，CFS）方法進行對比，實驗結果表明使用本文調度方法的計算性能能提高52%左右。

1 相關工作

為了充分利用異構多核系統的異構特性和優勢來滿足應用程序的多樣化需求，如何設計和實現應用程序的合理映射和調度方案已經成為研究熱點之一。由于調度問題是一個眾所周知的NP-Hard 問題，通過手動設計算法或者尋找滿足所有給定約束條件的最優解非常困難并且十分耗時，因此，目前研究者們大多基于啟發式算法［12-14］，在可接受的時間內尋找滿足條件的一個近似最優解。文獻［1］中作者從優化目標、分析模型、調度決策和算法評估四個方面對異構多核調度所面臨的問題與挑戰進行了總結和討論，并對各種調度技術進行了概括。由于本文的關注點在于應用機器學習技術來解決異構多核系統中的任務映射及調度問題的工作，因此接下來主要討論在進行應用程序映射核調度過程中，使用機器學習模型來優化解決方案的相關研究。

文獻［12］中作者針對片上網絡（Network-on-Chip，NoC）異構多核平臺下的任務映射問題提出了一種基于人工神經網絡（Artificial Neural Network，ANN）的解決方案。該方案首先探索任務節點映射到不同位置的處理核的所有可能，之后將對應的映射方式進行編碼并交給ANN 來預測，通過統計不同映射方案所能達到的最少執行時間來幫助設計者找到最優的任務映射方式。文獻［13］則針對動態多核平臺下的映射問題提出了一個基于機器學習方法的解決框架，分別使用K近鄰和線性回歸算法構建了一個線程數預測模型和一個處理核數量預測模型。在開始映射前，框架首先通過K近鄰算法來預測應用程序需要劃分成多少個線程，之后再利用線性回歸算法來預測每個線程所需要的最佳處理內核數，從而找到最佳的映射方式。

在文獻［14］中作者針對由CPU 和GPU 兩類處理核組成的異構多核平臺，首先對OpenCL程序的靜態和動態特征進行了特征分析，之后選擇了16 種特征訓練了一個可以預測應用程序在映射時需要映射的最佳處理核類型的支持向量機（Support Vector Machine，SVM）模型。在他們后續的工作中，對預測模型進行了進一步的優化，將更多類型的處理核因素納入了模型的訓練過程中，使用了多個SVM 來訓練預測模型，其中每種SVM 對應一種類型的處理核，并結合優化目標來確定程序在運行時所需要映射的處理核類型［15］。

文獻［16］中詳細評估分析了異構多核系統上的動態電壓頻率縮放行為，并利用凸優化方法來尋找性能與功率之間的關系，最終提出了一種可以預估線程在處理核上運行所產生功耗的預測模型，并基于該模型提出了一種可以優化系統運行時功耗的解決方案。文獻［17］中將機器學習技術引入了單應用程序系統的能源優化探索領域。作者使用了5 種機器學習模型來探索不同的配置選項，包括套接字分配、超線程使用和處理器DVFS（Dynamic Voltage and Frequency Scaling）級別等。該文獻將調度計算的時間間隔設為5 s，并對調度間隔的大小設置進行了實驗探索，實驗結果表明越小的調度間隔越有利于把握程序行為變化，但會導致更多的調度計算開銷。文獻［18］中將異構平臺的資源分配問題定義成機器學習問題，提出了一個基于ANN 的動態資源管理器。該資源管理器在運行時監視每個應用程序的執行情況，利用細粒度的資源動態信息（如L2 緩存空間、片外帶寬、功率預算、在L1 緩存中讀/寫命中以及讀丟失/寫丟失的數量等）預測每個應用程序在不同資源分配方案下的性能表現，從而動態調整資源分配策略，實現對緩存、內存和電壓頻率等資源的管理。文獻［19］中同樣利用ANN 技術構建了一個調度模型來幫助優化系統最大的吞吐量。作者提出利用程序的行為特性和處理核微架構信息來為程序尋找最合適的處理核的思想，針對大核和小核兩種類型的核心分別構建了兩個ANN 模型，利用程序的指令特征（如浮點運算指令、邏輯跳轉指令等）和核心微架構參數（如各級緩存的命中丟失率）來訓練ANN 模型。作者設定兩種ANN 模型每隔1 ms運行一次，預測所有線程在大核（小核）的性能結果，并根據預測結果找出使整個異構平臺可以達到最高IPC（Instructions Per Cycle）的調度方案?？梢钥闯鲞@些方法往往將調度間隔設成了固定的大小，沒有充分考慮程序運行行為的階段性變化，過于頻繁的調度計算無疑會影響整體系統運行效率。

相對于其他方法，本文在權衡機器學習模型預測準確性、復雜度和在線預測模型開銷的基礎上，選擇了具有一個隱藏層的ANN 作為異構多核系統的性能預測模型。此外為了盡可能降低在線計算的次數，本文引入了階段檢測［18］的思想，通過感知程序線程行為是否發生足夠明顯的變化來決定是否進行重調度計算，從而盡可能地降低在線調度計算的額外開銷，進一步提升系統的性能。

2 基于機器學習的異構多核系統調度方法

本章介紹本文針對異構多核系統所提出的動態映射和調度方法，對于給定的若干個獨立線程，調度目標是通過對線程-處理核的動態映射實現異構多核系統的性能最大化。在本文中，計算性能通過每個時鐘周期所運行的指令數即IPC 值來衡量，并假設每個核上同一時刻只能運行一個線程［19］。圖1 給出了該方法的整體框架，由圖可以看出整個異構多核調度方法的輸入是一組處于就緒狀態的待調度多線程隊列，輸出是線程到處理核的映射方案，主要由檢測應用程序行為階段變化的階段檢測器、基于ANN 的系統性能預測器和映射方案計算部件三部分構成。具體工作分三個階段：

1）在每個系統調度周期或者時間片收集異構多核平臺上所運行的各個處理核和線程的運行信息（包括IPC 值等相關信息），并將IPC值傳遞給階段檢測器。

2）階段檢測器通過對比每個處理核在當前時間片和上一時間片的IPC 值來確定其所運行的線程是否發生了行為變化。如果行為變化足夠明顯，那么調度方法就進入重映射計算階段來進行新的映射計算，來找到可以使系統性能最大化的新映射方案。

3）在重映射階段，首先性能預測器基于采集到的線程當前運行信息來對其在不同類型核上的運行性能（IPC 值）進行預測，然后映射計算部件根據這些預測值來決定當前時刻最優的映射方案即線程與處理核的最優映射關系。

此外，圖1 中的映射器用于具體部署映射計算部件得到的映射方案。

圖1 整體框架Fig.1 Overall framework

2.1 階段檢測

一個程序在其生命周期中可以執行百億條指令，在執行過程中其行為往往會發生階段性的變化并且許多行為會重復出現［11］。程序在不同階段一般具有不同的行為特征，表現為在不同階段執行指令的類型和數量不同，cache 缺失率、指令級并行度和系統資源利用率不同等［20］。

圖2展示了運行SPEC2006 基準程序測試集的gcc 程序時其IPC 值隨時間片變化的情況。圖2 中的橫坐標表示時間片的編號，每個時間片對應的縱坐標表示gcc 程序在該時間片的IPC 平均值。IPC 值相對穩定的時間片區間可以看作一個程序穩定運行的階段，從圖2可以看出程序在運行時其IPC值會隨著時間發生階段性的變化，這種階段性變化會在相鄰兩個時間片的IPC 發生明顯變化時出現。此外，還可以看到每個階段橫跨的時間有長有短，有的階段維持的時間跨度甚至多達成百上千個時間片。由于在每個階段程序行為相對穩定，因此就可以只在階段發生切換時對現有的系統映射進行調整計算并尋找下一個階段的最優映射方案，從而大大減少映射計算的次數，有效地降低在線計算的時間開銷。

圖2 gcc程序的IPC變化情況Fig.2 IPC change of gcc program

由于階段切換時相鄰兩個時間的IPC 變化較為明顯，因而通過檢測IPC 變化幅度就可以檢測階段是否發生切換。為此本文通過在每個處理核上設置一個階段檢測器來完成階段檢測，工作原理是比較在相鄰兩個時間片所采集到的處理核上所運行線程的IPC 值的變化幅度與所設閾值的大小，如果變化幅度高于所設閾值則認為階段發生切換。IPC 波動幅度δipc的計算公式為：，

其中：IPCj為當前時間片IPC 值的大??；IPCj-1是上一時間片IPC值的大小。

可以看出，能否找到發生階段切換的最佳閾值，對于精確捕捉程序運行行為發生變化的時機至關重要。閾值的最優值往往需要根據具體的異構多核平臺配置以及對運行的應用程序的實際執行情況進行探索來獲得，文獻［21］對不同閾值設置方法的檢測效果進行了詳細的探索和討論，并給出了參考閾值，故本文參考該文獻的設置方法，為檢測器設置了大小為50%的全局閾值δmax。類似地，在時間片大小的設置上本文也參考了其他相關方法［22］，將時間片設置為1 ms。

2.2 構建ANN預測模型

為了更加直觀地闡述本文方法，假定異構處理器平臺由兩類處理核（即大核和小核）構成，由更多類型的處理核構成的異構平臺可以相似地進行處理。本文選擇采用ANN 來為兩類處理核分別構建性能預測器，預測器的輸入是一組包含了線程運行信息和微架構參數信息的特征值集合，輸出是當前線程在兩類處理核上運行時能達到的IPC值。

2.2.1 模型參數選擇

一個預測特定處理核上線程IPC 值的機器學習模型的準確性很大程度上取決于輸入參數是否能夠準確捕捉到程序的行為特性（如浮點計算數量、訪存行為、分支行為等）以及程序運行時所使用的處理核上各種資源的多少（如CPU 資源、Cache 資源等）。本文對各個輸入參數利用皮爾遜相關系數（Pearson Correlation Coefficient，PCC）進行相關性分析［23］，利用相關系數來尋找參數與性能指標IPC 是否有相關性，從而建立性能預測模型。在經過相關性分析后，本文從18 種參數中選取了和IPC 值關系較密切的10 個指標來構建ANN 性能預測器。這10 個指標包括4 種與處理核心微架構相關的參數，即L1-D、L1-I、L2和L3 Cache 命中缺失率，以及6 種與程序行為變化相關的參數，即浮點加法、減法、乘法、除法、跳轉指令和讀寫內存指令。

2.2.2 ANN預測模型

除了輸入參數本身以外，模型復雜度的高低和運行模型所產生的硬件開銷等也是評估模型好壞的重要指標。由于ANN 屬于計算密集型算法，隨著網絡層數的增多，網絡結構會越復雜，進而帶來更多的硬件和在線預測開銷等問題。因此，在綜合權衡模型時間開銷和精確度以后，本文最終使用了三層的神經網絡來構建ANN性能預測器。表1給出了本文最終確定使用的網絡模型的各項參數，接下來分別介紹這些參數的選擇依據和考慮。

表1 人工神經網絡參數設置Tab.1 Parameter setting of artificial neural network

ANN 的輸入層由10 個神經元節點組成，輸入層的10 個節點分別負責接收10 個輸入參數，在計算完畢后，輸入節點會將計算結果通過激活函數傳遞到隱藏層。理論上隱藏層節點的個數越多，ANN 性能預測器在訓練數據集上的預測效果就越好，但隱藏層節點個數超過一定數量會導致過擬合現象的出現。本文參考文獻［24］中所提出的經驗公式來確立隱藏層節點的個數，即采用經驗公式2n+m，其中n為輸入節點的數量，m為0～10 的正整數。在對m的數值進一步進行實驗分析后，選擇使ANN 性能預測器在訓練集上獲得最好效果的m值（即5），因此最終本文選擇的隱藏層節點個數為25。隱藏層的每個神經元節點會接收所有的輸入節點結果，在對其完成計算后通過激活函數傳遞到輸出層。輸出層利用所有隱藏神經元節點的計算結果得到最后的輸出值（IPC）。

在激活函數的使用上本文選擇了ReLU（Rectified Linear Unit）函數，該函數不含任何復雜的運算（如指數級運算），只擁有很小的計算量，可以最大限度地降低異構多核調度中產生的在線預測時間開銷。同時，ReLU函數在訓練過程中也可以有效避免梯度飽和問題，防止訓練失敗的情況出現。詳細的ANN連接結構如圖3所示。

圖3 人工神經網絡模型Fig.3 Artificial neural network model

ANN 性能預測器屬于機器學習中的回歸模型，因此本文使用回歸模型常用的均方誤差（Mean Squared Error，MSE）損失函數來對ANN 性能預測器進行訓練。使用MSE 函數訓練ANN性能預測器時，整個ANN的梯度會隨MSE值的增大而增大，而MSE值趨于0時網絡的梯度則會減小，因此采用固定的學習率即可保證整個網絡可以有效地收斂，并在訓練結束時取得良好的預測效果，所以本文將學習率設置為固定的0.001。

2.2.3 數據集獲取和預處理

本文使用Sniper工具來獲取用于訓練大核和小核ANN性能預測器的兩個數據集。為此，本文分別建立了兩個獨立的處理核平臺，其中訓練大核性能預測器的處理核平臺只擁有一個大核，另一個用于訓練小核性能預測器的處理核平臺只擁有一個小核。通過在兩個平臺上完整執行基準測試集SPLASH-2中所有應用，并收集每個時間片的相關輸入參數和輸出標簽等數據來獲得原始數據集。

由于收集到的原始數據中各輸入特征的單位或數量級不一致且相差較大（如每個時間片程序執行指令條數多達成百上千條，而cache 命中缺失率常常遠低于1），因此直接用原始數據對程序的IPC 值進行預測的話，數量級較大的各種指令特征會嚴重影響預測效果。此外，程序每個時間片在大核上執行的各類型指令的條數與小核上執行的指令條數有時也會有1～2 個數量級的差別，所以在大（?。┖松鲜占妮斎雲惦y以直接用來預測線程在?。ù螅┖松系腎PC 值。因此本文對收集到的原始數據作了以下標準化處理：

1）針對6 種表示程序行為的指令特征，本文用不同類型的指令條數占總指令條數的比率來替代原來的指令數量。

2）針對全部10種參數，本文對其進行了Z-Score歸一化處理以使數據集更加符合正態分布。具體計算公式如下：

其中：μβ和分別是訓練集的均值和方差；ε是一個用來避免為0的常量，本次實驗中將ε值設置為0.001。

2.2.4 預測器評估

在利用Sniper 和基準測試集SPLASH-2 得到所需要的原始數據集后，本文利用該數據集來對ANN 性能預測器進行訓練和評估。首先，將經過預處理后的原始數據集按照機器學習模型訓練和評估常用的劃分方法將數據集以7∶3 的比例進行劃分，其中的70%用來訓練模型，剩下的30%作為測試集來評估ANN性能預測器在未知數據上的預測效果。

圖4 顯示了本文訓練的兩個ANN 性能預測器在SPLASH-2 基準程序測試集上的表現情況，MSE 值越低表示ANN 性能預測器的效果越好。從圖4 可以看出：小核性能預測器和大核性能預測器在barnes 上表現最好，MSE 值分別為0.010 8 和0.013 7；而在volrend 上兩者表現最差，分別為0.750 6和0.936 4?？傮w上，在8個基準測試程序上兩者分別達到了0.155 4 和0.228 4 的平均MSE 值，均具有較好的預測效果。

圖4 ANN預測器的均方誤差Fig.4 MSE of ANN predictor

2.2.5 映射方案計算部件

由于ANN 性能預測器的輸出結果是IPC 值，并不是一個完整的映射方案，因此本文設計了一個映射方案計算部件來找出最優的映射方案。該部件的主要功能是利用ANN 性能預測器給出各個線程在大（?。┨幚砗松系腎PCbig（IPCsmall）來對所有可行的映射方案進行評估，找出使所有線程總IPCsum的最大的映射方案。

假設異構多核平臺需要映射的線程數量為M，其中N個需要映射到大核上，另外M-N個線程映射到小核上，則存在的映射方案數量一共為。映射方案計算部件每次選擇N個線程的IPCbig和另外M-N個線程的IPCsmall相加得到本次映射的IPCsum，在得到個IPCsum后，完成對所有可行映射方案的探索，并將IPCsum值最大的那種映射方案輸出給映射器。映射器在得到映射計算部件給出的映射方案后完成線程到處理核的部署。

3 實驗評估

3.1 實驗設置

本文選擇采用業界常用的Sniper［24］作為數據采集和實驗評估的工具，Sniper 是一個用于處理器架構設計驗證的模擬器，既可以用來模擬同構多核架構系統，也可以模擬異構多核架構系統的運行。該模擬器主要支持x86 指令集的處理核，目前最新版本也加入了對RISC-V 指令集的支持。為了實現良好的仿真效果和更快的仿真速度，Sniper 選擇了基于時間間隔模擬的方式來獲得處理核運行時產生的各項指標并對設計方案進行評估。

由于本文主要針對單指令集架構下的異構多核平臺，即同一平臺下的多個處理核具有相同的指令集架構但各自有不同的微架構（如處理器主頻、流水線深度、緩存系統差異等）的處理核，因此在本次實驗中，本文基于Sniper搭建了一個由大核和小核兩種類型的處理核組成的異構多核平臺，其中大核指微架構的實現更加復雜，性能更高的處理核，而小核指的是微架構的實現相對簡單，功耗較低的處理核。該平臺是一個典型的四核異構非對稱多核處理器，由1個大核和3個小核組成，詳細配置如表2 所示。1 大3 小的四核架構是移動平臺領域常見的處理器配置方式：1 個主打高性能的大核能在可接受面積和功耗的前提下提供最高的單核性能，而3 個小核則可以在做到在更小的面積和功耗下提供一定的多核性能，從而在多個常見場景下擁有性能和功耗的優勢。此外，由于cache大小、時鐘頻率等參數既影響程序的性能執行結果又影響了資源爭用和線程同步等情況，為了精確驗證程序在不同核心上執行的性能差異原因，本文采用了相同的時鐘頻率和三級cache 緩存架構，其中L1 Cache 為256 KB，L2 Cache 為512 KB，共享的L3 Cache 大小設置為8 MB。大核和小核的指令集架構均基于Intel Nehalem x86架構，且處理核的主頻均為2.66 GHz。在核心的微架構配置上，本文為大核和小核均設置了大小為4的發射寬度，但是大核擁有128的指令窗口大小和長度為48 的讀取隊列，與之對應的小核的指令窗口大小和隊列長度分別為16和6。

表2 異構多核處理平臺配置Tab.2 Heterogenous multi-core processor configurations

本文使用SPLASH-2 基準測試集作為實驗用的程序集合。SPLASH-2基準測試集由一系列多線程程序組成，多應用于高性能計算和圖形多媒體程序的測試。同時，Sniper 集成了SPLASH-2 基準測試集的已編譯版本，可以對其下所有應用程序在實際硬件平臺上的運行情況進行準確模擬，因此利用Sniper 和SPLASH-2 基準測試集可以全面綜合地對異構調度方法進行評估，并測試調度效果。在對比實驗中，本文選擇了Linux默認的CFS調度器，該調度器已被廣泛應用在各種多核處理系統中。

3.2 實驗結果

在實際的調度場景中，調度器需要面臨各種已知或未知類型的程序并對其進行調度。由于基準測試集中包含的程序涵蓋了大多數的程序類型，因此為了對調度器進行全面的評估本文將SPLASH-2 基準測試集進行了如表3 所示的分組。分組原則為使每組程序中既包含MSE 值較低的程序，也包含MSE 值較高的程序，并通過進行多組實驗來盡可能充分地模擬調度器在真實環境下的復雜調度場景。為了保證實驗評估結果的準確性，本文在Sniper 下分別實現了異構調度器和CFS 調度器，其中CFS 調度器的實現方式參考了Linux Kernel 2.6.33 所實現的版本［25］。在執行方式上，每組的4 個多線程程序會在4 個處理核上循環執行直到該組的所有程序的所有線程都至少執行完一遍為止，從而盡可能真實地模擬現實場景下的程序執行行為。

表3 實驗用的程序組合Tab.3 Combination of programs in experiments

圖5 給出了使用本文的異構調度方法在Sniper 搭建的四核異構平臺中分別運行表3 中各組應用程序的實驗結果，其中橫坐標表示不同的程序組合編號，縱坐標是本文提出的異構調度方法與Linux 默認的CFS 相比所實現的IPC 加速比。從圖5可以看出，本文所構建的調度器相比CFS在組合2上加速比最低，在組合6 上加速比最高，分別是1.12 和2.49，在7種組合下平均實現了1.52 的加速比。根據圖4 中ANN 性能預測器在SPLASH-2 基準測試程序上的表現可知，由于組合2含有MSE值最高的volrend和fft，因此整體的ANN性能預測器預測效果較其他組合相比最差，所以達到的IPC 加速比最低。同理，組合6中各程序的MSE值整體比較接近，ANN性能預測器的整體預測效果較好，因而達到了最高的IPC加速比。

圖5 本文異構調度方法的加速比Fig.5 Speedup ratio of proposed heterogenous scheduling method

圖6 給出了本文所提出的異構調度方法與CFS 調度器在Sniper 所搭建的四核異構平臺中分別運行表3 中各組應用程序的CPU 資源利用率（CPU 處于運行狀態的時鐘周期數與總的時鐘周期數的比值）的情況，其中本文方法的平均CPU 核資源利用率為93%，高于CFS 的平均CPU 核資源利用率（85%）。結果表明本文提出的異構調度器能夠更加充分地利用CPU的資源。

通過實驗數據可知，相對于利用虛擬運行時間大小來分配處理核資源的CFS 調度算法，本文所提出的異構調度方法通過感知線程行為的變化和不同時刻下線程對處理核資源的需求，將線程及時分配到最適合其運行的處理核上，從而能夠更好地發揮異構多核所帶來的優勢，獲得更好的調度性能。

圖6 本文異構調度方法和CFS的核資源利用率Fig.6 Core resource utilization rate of proposed heterogenous scheduling method and CFS

使用ANN 性能預測器所帶來的額外開銷主要由預測器指令的執行時間開銷和為了存儲模型參數所帶來的額外存儲開銷組成。在不考慮各級緩存命中缺失率、數據是否對齊等因素的影響下，一個ANN 性能預測器每次執行所需要的浮點乘法指令條數約為250條、浮點加法指令為26條、訪存相關的指令約為70 條，而存儲模型參數所需要的內存約為1 104 B。通過查詢Intel 指令手冊［26］可知，理想情況下運行上述指令所需的總指令周期數最小為1 160，因此在4 個處理核上分別運行4個ANN性能預測器所帶來的總消耗為4 640個時鐘周期，內存開銷為552 KB。假設CPU 時鐘頻率為1 GHz，當時間片為1 ms時，每個時間片有1×106時鐘周期，運行ANN 性能預測器的時間開銷約為0.5%。而本文提出的方法整合了階段檢測器，此時ANN 性能預測器往往需要經過往往成百上千個時間片才會被調用，因此引入ANN 性能預測器所帶來的實際額外時間開銷會更低，甚至可以忽略。

綜上，相對于經典的CFS調度器，本文所提出的調度程序引入了階段檢測機制和ANN 性能預測器來幫助感知線程行為變化并為其選擇更合適的處理核，最終在基本沒有帶來明顯額外在線計算開銷的前提下，獲得了更好的性能收益。

4 結語

本文提出了一種基于階段檢測和機器學習預測模型的異構多核映射和調度方法：一方面通過階段檢測來感知線程的行為變化，按需進行重新映射和調度；另一方面通過采用機器學習技術來構建系統性能預測模型從而對程序在不同類型的處理核的IPC 進行預測，并根據預測結果制定映射調度方案。實驗結果表明，與Linux 系統使用的CFS 調度器相比，本文方法提升了52%的計算性能。

接下來的工作中，一方面希望將方法應用于具有更多處理核的異構多核處理平臺上，為此需要研究能夠高效地尋找最優或接近最優的搜索算法以提高該方法的可擴展性；另一方面由于目前的工作只考慮了性能優化，忽略了系統的能耗情況，因此也希望在當前的基礎上引入對能耗指標的優化，從而實現異構多核平臺的能效最大化。此外，采用更復雜的ANN 模型來提高預測精度，以及更加全面地考慮資源競爭和線程同步等方面對調度方法設計的影響也是之后計劃研究的方向。