基于機器學(xué)習(xí)的異構(gòu)感知多核調(diào)度方法

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

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

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

0 引言

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

相對于其他方法，本文在權(quán)衡機器學(xué)習(xí)模型預(yù)測準(zhǔn)確性、復(fù)雜度和在線預(yù)測模型開銷的基礎(chǔ)上，選擇了具有一個隱藏層的ANN 作為異構(gòu)多核系統(tǒng)的性能預(yù)測模型。此外為了盡可能降低在線計算的次數(shù)，本文引入了階段檢測［18］的思想，通過感知程序線程行為是否發(fā)生足夠明顯的變化來決定是否進(jìn)行重調(diào)度計算，從而盡可能地降低在線調(diào)度計算的額外開銷，進(jìn)一步提升系統(tǒng)的性能。

2 基于機器學(xué)習(xí)的異構(gòu)多核系統(tǒng)調(diào)度方法

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

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

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

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

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

圖1 整體框架Fig.1 Overall framework

2.1 階段檢測

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

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

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

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

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

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

2.2 構(gòu)建ANN預(yù)測模型

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

2.2.1 模型參數(shù)選擇

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

2.2.2 ANN預(yù)測模型

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

表1 人工神經(jīng)網(wǎng)絡(luò)參數(shù)設(shè)置Tab.1 Parameter setting of artificial neural network

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

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

圖3 人工神經(jīng)網(wǎng)絡(luò)模型Fig.3 Artificial neural network model

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

2.2.3 數(shù)據(jù)集獲取和預(yù)處理

本文使用Sniper工具來獲取用于訓(xùn)練大核和小核ANN性能預(yù)測器的兩個數(shù)據(jù)集。為此，本文分別建立了兩個獨立的處理核平臺，其中訓(xùn)練大核性能預(yù)測器的處理核平臺只擁有一個大核，另一個用于訓(xùn)練小核性能預(yù)測器的處理核平臺只擁有一個小核。通過在兩個平臺上完整執(zhí)行基準(zhǔn)測試集SPLASH-2中所有應(yīng)用，并收集每個時間片的相關(guān)輸入?yún)?shù)和輸出標(biāo)簽等數(shù)據(jù)來獲得原始數(shù)據(jù)集。

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

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

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

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

2.2.4 預(yù)測器評估

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

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

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

2.2.5 映射方案計算部件

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

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

3 實驗評估

3.1 實驗設(shè)置

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

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

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

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

3.2 實驗結(jié)果

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

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

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

圖5 本文異構(gòu)調(diào)度方法的加速比Fig.5 Speedup ratio of proposed heterogenous scheduling method

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

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

圖6 本文異構(gòu)調(diào)度方法和CFS的核資源利用率Fig.6 Core resource utilization rate of proposed heterogenous scheduling method and CFS

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

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

4 結(jié)語

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

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