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

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

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

0 引言

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

圖1 整體框架Fig.1 Overall framework

2.1 階段檢測(cè)

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

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

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

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

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

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

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

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

2.2.1 模型參數(shù)選擇

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

2.2.2 ANN預(yù)測(cè)模型

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

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

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

在激活函數(shù)的使用上本文選擇了ReLU（Rectified Linear Unit）函數(shù)，該函數(shù)不含任何復(fù)雜的運(yùn)算（如指數(shù)級(jí)運(yùn)算），只擁有很小的計(jì)算量，可以最大限度地降低異構(gòu)多核調(diào)度中產(chǎn)生的在線預(yù)測(cè)時(shí)間開(kāi)銷。同時(shí)，ReLU函數(shù)在訓(xùn)練過(guò)程中也可以有效避免梯度飽和問(wè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ù)測(cè)器屬于機(jī)器學(xué)習(xí)中的回歸模型，因此本文使用回歸模型常用的均方誤差（Mean Squared Error，MSE）損失函數(shù)來(lái)對(duì)ANN 性能預(yù)測(cè)器進(jìn)行訓(xùn)練。使用MSE 函數(shù)訓(xùn)練ANN性能預(yù)測(cè)器時(shí)，整個(gè)ANN的梯度會(huì)隨MSE值的增大而增大，而MSE值趨于0時(shí)網(wǎng)絡(luò)的梯度則會(huì)減小，因此采用固定的學(xué)習(xí)率即可保證整個(gè)網(wǎng)絡(luò)可以有效地收斂，并在訓(xùn)練結(jié)束時(shí)取得良好的預(yù)測(cè)效果，所以本文將學(xué)習(xí)率設(shè)置為固定的0.001。

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

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

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

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

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

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

2.2.4 預(yù)測(cè)器評(píng)估

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

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

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

2.2.5 映射方案計(jì)算部件

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

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

3 實(shí)驗(yàn)評(píng)估

3.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

表3 實(shí)驗(yàn)用的程序組合Tab.3 Combination of programs in experiments

圖5 給出了使用本文的異構(gòu)調(diào)度方法在Sniper 搭建的四核異構(gòu)平臺(tái)中分別運(yùn)行表3 中各組應(yīng)用程序的實(shí)驗(yàn)結(jié)果，其中橫坐標(biāo)表示不同的程序組合編號(hào)，縱坐標(biāo)是本文提出的異構(gòu)調(diào)度方法與Linux 默認(rèn)的CFS 相比所實(shí)現(xiàn)的IPC 加速比。從圖5可以看出，本文所構(gòu)建的調(diào)度器相比CFS在組合2上加速比最低，在組合6 上加速比最高，分別是1.12 和2.49，在7種組合下平均實(shí)現(xiàn)了1.52 的加速比。根據(jù)圖4 中ANN 性能預(yù)測(cè)器在SPLASH-2 基準(zhǔn)測(cè)試程序上的表現(xiàn)可知，由于組合2含有MSE值最高的volrend和fft，因此整體的ANN性能預(yù)測(cè)器預(yù)測(cè)效果較其他組合相比最差，所以達(dá)到的IPC 加速比最低。同理，組合6中各程序的MSE值整體比較接近，ANN性能預(yù)測(cè)器的整體預(yù)測(cè)效果較好，因而達(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)平臺(tái)中分別運(yùn)行表3 中各組應(yīng)用程序的CPU 資源利用率（CPU 處于運(yùn)行狀態(tài)的時(shí)鐘周期數(shù)與總的時(shí)鐘周期數(shù)的比值）的情況，其中本文方法的平均CPU 核資源利用率為93%，高于CFS 的平均CPU 核資源利用率（85%）。結(jié)果表明本文提出的異構(gòu)調(diào)度器能夠更加充分地利用CPU的資源。

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

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

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

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

4 結(jié)語(yǔ)

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

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