安鑫 張影 康安 陳田 李建華

摘 要：異構(gòu)多核處理器（HMPs）平臺已成為現(xiàn)代嵌入式系統(tǒng)的主流解決方案，其中在線映射或調(diào)度對充分發(fā)揮其高性能和低功耗的優(yōu)勢起著至關(guān)重要的作用。針對HMPs的應(yīng)用任務(wù)動態(tài)映射問題，提出了一種基于機器學(xué)習預(yù)測模型的在線映射調(diào)度解決方案。一方面，構(gòu)建了一個可以快速高效地預(yù)測和評估不同映射方案性能的機器學(xué)習模型，為在線調(diào)度提供支持;另一方面，將該機器學(xué)習模型整合到遺傳算法中以高效地找到（接近）最優(yōu)的資源分配方案。最后，通過一個M-JPEG解碼器驗證了所提方法的有效性。實驗結(jié)果表明，該方法的平均執(zhí)行時間相較于常見的輪詢調(diào)度和抽樣調(diào)度方法分別降低了28%和19%左右。

關(guān)鍵詞：異構(gòu)多核處理器;機器學(xué)習;動態(tài)資源分配;性能預(yù)測;映射和調(diào)度

中圖分類號： TP302.7

文獻標志碼：A

Abstract： Heterogeneous Multi-core Processors （HMPs） platform has become the mainstream solution for modern embedded system design， and online mapping or scheduling plays a vital role in making full use of the advantages of high performance and low power consumption. Aiming at the dynamic mapping problem of application tasks in HMPs， a mapping and scheduling approach based on machine learning prediction model was proposed. On the one hand， a machine learning model was constructed to predict and evaluate the performance of different mapping strategies rapidly and efficiently， so as to provide support for online scheduling. On the other hand， the machine learning model was integrated with genetic algorithm to find out the optimal resource allocation strategy efficiently. Finally， an Motion-Join Photographic Experts Group （M-JPEG） decoder was used to verify the effectiveness of the proposed approach. The experimental results show that， compared with the Round Robin Scheduler （RRS） and sampling scheduling approaches， the proposed online mapping/scheduling approach has reduced the average execution time by about 19% and 28% respectively.

Key words： Heterogeneous Multi-core Processors （HMPs）; machine learning; dynamic resource allocation; performance prediction; mapping and scheduling

0 引言

為了滿足現(xiàn)代嵌入式系統(tǒng)對高性能、低功耗的需求，異構(gòu)多核處理器（Heterogeneous Multi-core Processors， HMPs）已經(jīng)得到了廣泛使用，如ARM big.Little移動設(shè)備[1]和新款iPhone XS配備的A12仿生異構(gòu)多核處理芯片[2]。該類處理器能夠?qū)⒏邥r鐘頻率、復(fù)雜指令集的大核和低時鐘頻率、簡單指令集的小核相結(jié)合，以此來滿足不同運行場景的需要[3]。另一方面，為了進一步提高現(xiàn)代嵌入式系統(tǒng)的能效，動態(tài)電壓和頻率調(diào)整（Dynamic Voltage and Frequency Scaling， DVFS）技術(shù)應(yīng)運而生，它通過根據(jù)需要調(diào)整核心頻率來實現(xiàn)節(jié)能需求，在現(xiàn)代處理器中也得到了普遍的應(yīng)用[4]。然而，要充分利用HMPs和DVFS技術(shù)來提高系統(tǒng)的性能并降低功耗，需要解決的一個很重要的問題就是任務(wù)的動態(tài)映射（或調(diào)度）問題。動態(tài)映射問題是指在系統(tǒng)運行過程中，當系統(tǒng)運行環(huán)境發(fā)生變化時如何為系統(tǒng)中的應(yīng)用任務(wù)進行相應(yīng)的資源分配和調(diào)度，從而使其達到優(yōu)化性能和功耗等方面的要求。

解決動態(tài)映射問題的關(guān)鍵是要能夠在環(huán)境發(fā)生變化后對可能的資源分配和調(diào)度方案進行性能等方面的評估，并從中選擇最優(yōu)或者接近最優(yōu)的映射調(diào)度方案。傳統(tǒng)的性能評估方法可以概括為兩類：一類是通過為系統(tǒng)建立抽象的數(shù)學(xué)評估模型（又稱為成本模型）來進行計算，另一類是通過對系統(tǒng)進行仿真模擬來獲得[5]。成本模型可以通過建立相關(guān)模型對系統(tǒng)不同調(diào)度方案的性能或者功耗進行高效評估，然而其準確性依賴于模型本身及其相關(guān)參數(shù)的準確性，而這些參數(shù)對于大部分系統(tǒng)來說一方面是動態(tài)可變的，另一方面往往難以準確獲得，從而導(dǎo)致該類方法精度不足;而基于仿真模擬的方法，為了提高評估準確性，需要盡可能地對系統(tǒng)的實現(xiàn)細節(jié)進行實現(xiàn)和模擬，從而導(dǎo)致該類方法比較耗時，不適于在線對大量的調(diào)度方案進行快速評估。因此，如何創(chuàng)建一種既能結(jié)合成本模型的快速高效、又能兼顧模擬仿真模型準確性的方法，在提高準確性的同時提高評估準確性，從而為系統(tǒng)動態(tài)進行分配資源和調(diào)度提供支持也就成為了業(yè)界一直以來的研究熱點。

機器學(xué)習和深度學(xué)習技術(shù)目前在自然語言處理、圖像識別、推薦系統(tǒng)與博弈等領(lǐng)域取得了很大的成功[6]。這也吸引了嵌入式系統(tǒng)設(shè)計領(lǐng)域?qū)＜液蛯W(xué)者的濃厚興趣，特別是面對設(shè)計復(fù)雜度日益增長的問題，機器學(xué)習技術(shù)可以從過去解決問題的經(jīng)驗中學(xué)習知識，以快速高效的方式找到高質(zhì)量的設(shè)計方案，這無疑大大減輕了設(shè)計人員的工作負擔。目前，已經(jīng)有基于機器學(xué)習技術(shù)來解決異構(gòu)多核系統(tǒng)調(diào)度問題的方法被提出并取得了良好的效果。這方面的工作主要有兩類：一類工作是針對調(diào)度方案的性能和/或功耗預(yù)測，如文獻[7-8];另外一類是針對任務(wù)的動態(tài)調(diào)度，如文獻[9-10]。然而，盡管過去幾年機器學(xué)習技術(shù)獲得越來越多的關(guān)注，但它在改善異構(gòu)多核系統(tǒng)性能方面仍處于早期階段[6]。大部分工作考慮系統(tǒng)運行時的細節(jié)信息（如中央處理器的利用率、內(nèi)存和通信互連的使用情況），但是這些細粒度信息通常不易得到而且獲取的代價較大，不能很好地解決在線映射調(diào)度兼顧高效和準確性的問題;另外目前大部分工作針對的是獨立任務(wù)的動態(tài)資源分配和調(diào)度問題，并沒有考慮任務(wù)之間依賴關(guān)系所帶來的問題復(fù)雜度。

針對具有DVFS功能的HMPs系統(tǒng)應(yīng)用任務(wù)動態(tài)映射問題，本文提出了一種基于機器學(xué)習模型對運行時映射選擇進行快速高效評估的動態(tài)映射調(diào)度解決方案。一方面該方案僅利用少許易獲取的運行時信息（比如映射位置），另一方面該方案可以處理采用有向無環(huán)圖（Directed Acyclic Graph， DAG）描述的應(yīng)用任務(wù)映射問題，從而能夠在動態(tài)調(diào)度中考慮任務(wù)依賴關(guān)系可能帶來的差異。具體而言，本文的工作主要包含以下兩個方面：

1）本文通過采用機器學(xué)習技術(shù)構(gòu)造系統(tǒng)性能預(yù)測模型來對不同映射方案和每個核的頻率值進行高效性能評估，并通過實驗驗證了其準確性。

2）提出了一種結(jié)合遺傳算法（Genetic Algorithm， GA）和機器學(xué)習預(yù)測模型的運行時動態(tài)映射方法，并通過實驗與當前常用的動態(tài)映射方法和最優(yōu)化的映射方法進行了比較和分析。

1 相關(guān)工作

隨著當前嵌入式系統(tǒng)設(shè)計復(fù)雜性的增加，處理器上核的數(shù)目不斷地增長，如何設(shè)計和實現(xiàn)應(yīng)用程序的映射和調(diào)度已經(jīng)成為研究的熱點之一。而并行程序的映射和調(diào)度是一個眾所周知的NP完全問題（Non-deterministic Polynomial complete problem）[11]，這意味著詳盡地探索所有的映射選擇從而找到最優(yōu)的映射方案是非常耗時的，也是不可行的。因此，目前關(guān)于映射問題的研究大多數(shù)是基于啟發(fā)式算法[12-14]來找到一個近似的最優(yōu)解。文獻[15]中對嵌入式系統(tǒng)設(shè)計空間的快速探索和評估的設(shè)計技術(shù)進行了詳細的介紹。本文主要關(guān)注結(jié)合機器學(xué)習技術(shù)來解決異構(gòu)多處理器的任務(wù)調(diào)度問題的技術(shù)和方法，故接下來主要討論基于機器學(xué)習模型來處理映射性能預(yù)測和動態(tài)調(diào)度的相關(guān)研究。

文獻[16]通過學(xué)習不同應(yīng)用程序行為在不同核上的功耗來構(gòu)建一個回歸預(yù)測模型，從而提出了一個可以優(yōu)化系統(tǒng)功耗的頻率電壓動態(tài)調(diào)節(jié)管理解決方案。文獻[17]提出了基于機器學(xué)習的方法來優(yōu)化用一種面向多核的StreamIt語言編寫的應(yīng)用程序，從而在動態(tài)的多核上執(zhí)行時找到最佳的映射方式。為了最大限度地提高系統(tǒng)的性能，該研究分別使用K-鄰近算法和線性回歸算法來構(gòu)建模型，用來預(yù)測應(yīng)用程序劃分的最佳線程數(shù)以及每個線程所需要的最佳內(nèi)核數(shù)。文獻[18]提出了一種多核平臺的執(zhí)行時間和能耗的預(yù)測方法，將不同映射方案通過編碼的方式采用人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Network， ANN）算法進行訓(xùn)練，從而幫助設(shè)計者找到最優(yōu)的資源分配。

文獻[19]通過選擇和提取開放運算語言（Open Computing Language， OpenCL）程序的靜態(tài)和動態(tài)特征，及其在核上的運行時性能來對支持向量機（Support Vector Machine， SVM）模型進行訓(xùn)練，訓(xùn)練后的模型用來預(yù)測未知應(yīng)用程序出現(xiàn)時所對應(yīng)映射的目標核的類型。然而，該模型沒有考慮多核的情況，只是將處理核的類型劃分為一個中央處理器和一個圖形處理器。在后續(xù)的研究工作文獻[20]中，考慮更多的處理核的類型，使用多個SVM模型進行訓(xùn)練，根據(jù)優(yōu)化目標來確定運行時處理核的配置。

文獻[21]提出了一個基于ANN的應(yīng)用程序動態(tài)資源分配技術(shù)，每個ANN都輸入一些細粒度的資源信息和程序最近行為，包括二級緩存空間、片外帶寬、功率預(yù)算、在一級緩存中讀/寫命中，以及讀丟失/寫丟失的數(shù)量，根據(jù)這些輸入信息，ANN將預(yù)測出應(yīng)用程序的性能，從而得到最優(yōu)調(diào)度方案。相似的，文獻[6]提出了一種最大化吞吐量的調(diào)度模型，并采用ANN技術(shù)為不同應(yīng)用調(diào)度提供精確的性能預(yù)測，從而提高異構(gòu)多核系統(tǒng)的調(diào)度效率。

文獻[22]建立了基于反饋神經(jīng)網(wǎng)絡(luò)和徑向基神經(jīng)網(wǎng)絡(luò)的模型來預(yù)測多核處理器的性能和功耗，通過選取對性能影響比較大的參數(shù)，如發(fā)射寬度、二級緩存大小和二級緩存命中延遲等，來預(yù)測不同調(diào)度策略下的性能值，以此來提高設(shè)計空間的探索效率。文獻[23]提出了一個基于SVM的任務(wù)分配模型，通過分析處理器和任務(wù)的特征（如任務(wù)的類型、數(shù)據(jù)量大小、并行化程度）以及當前運行狀態(tài)，來預(yù)測任務(wù)的最優(yōu)分配方案。

文獻[9]研究了多線程應(yīng)用程序在異構(gòu)多核體系結(jié)構(gòu)上的調(diào)度問題，并建立了五種基于機器學(xué)習算法的預(yù)測模型，該算法可以預(yù)測最優(yōu)的線程數(shù)和相應(yīng)的電壓和頻率值，以此最大限度地提高能源效率。在運行時從應(yīng)用程序分析中提取的一組輸入特性，根據(jù)類別可分為內(nèi)存、指令和分支。在創(chuàng)建模型之后，實驗結(jié)果表明，與基于回歸模型和基于決策樹模型的分類器相比，多層感知器這種較復(fù)雜的預(yù)測器具有更高的精度，但是與此同時會有更高的時間開銷。

可以看到，當前大部分工作構(gòu)建機器學(xué)習模型均依賴于系統(tǒng)運行時的細節(jié)信息（如二級緩存狀態(tài)），而這些細粒度信息獲取的代價較大，從而導(dǎo)致在線映射調(diào)度方法開銷過大;另外這些工作要么只針對多核系統(tǒng)的映射問題，要么只針對DVFS動態(tài)調(diào)節(jié)，而本文則同時考慮兩者的動態(tài)管理。

2 基于機器學(xué)習的在線映射方法

本部分介紹本文提出的基于機器學(xué)習的在線映射方法，其中2.1部分介紹該方法的整體框架，2.2部分介紹對映射方案進行快速性能預(yù)測的模型構(gòu)建過程，2.3部分介紹本文所采用的在線映射方法搜索方案——遺傳算法。

2.1 整體框架

本文提出的基于機器學(xué)習的在線映射方法整體設(shè)計框架如圖1所示，分為：1）離線訓(xùn)練（圖1（a）），即映射方案性能預(yù)測模型構(gòu)建;2）在線調(diào)度（圖1（b）），即運行時動態(tài)映射方案搜索、評估和選擇。

在離線訓(xùn)練階段，考慮DAG描述的系統(tǒng)應(yīng)用和基于二維片上網(wǎng)絡(luò)（Network on Chip， NoC）的異構(gòu)多核處理器運行平臺，而且每個核在運行時是可以進行動態(tài)頻率調(diào)整的。在這個階段，希望采用機器學(xué)習方法來對系統(tǒng)的映射方案進行學(xué)習并最終獲得相應(yīng)的性能預(yù)測模型。為了產(chǎn)生相應(yīng)的訓(xùn)練數(shù)據(jù)集，首先使用CLASSY（CLock AnalysiS System）模擬器[24]來模擬和分析不同映射方案的執(zhí)行時間等性能指標從而得到初始數(shù)據(jù)，然后對初始訓(xùn)練集進行預(yù)處理。得到訓(xùn)練集后通過選擇合適的機器學(xué)習方法就可以對性能預(yù)測模型進行構(gòu)建。

在線調(diào)度階段，對于給定的應(yīng)用程序和執(zhí)行平臺，當運行時發(fā)生不可預(yù)知的動態(tài)事件（如某個運行核由于負載過高或故障等原因不可用、某兩個核之間的通信斷開）時，在線調(diào)度器需要對這種動態(tài)變化作出快速的響應(yīng)，也就是對資源進行重新分配和調(diào)度，從而滿足系統(tǒng)對性能、功耗等方面的需求，比如性能最優(yōu)化。為了做到這一點，在線調(diào)度器一方面需要通過啟發(fā)式算法對當前狀態(tài)下的資源分配方案進行快速高效的搜索，另一方面需要同時對不同方案進行性能評估（通過離線訓(xùn)練得到的預(yù)測模型進行），并最終從中選取最優(yōu)的映射決策。

2.2 離線訓(xùn)練——性能預(yù)測模型構(gòu)建

對應(yīng)用程序在異構(gòu)多核系統(tǒng)上的不同映射方案進行性能預(yù)測可以看作一個線性回歸問題，鑒于該問題的復(fù)雜性，本文選用已得到廣泛使用的ANN進行預(yù)測模型的學(xué)習和構(gòu)建。

2.2.1 人工神經(jīng)網(wǎng)絡(luò)

人工神經(jīng)網(wǎng)絡(luò)（ANN），又稱為多層前饋神經(jīng)網(wǎng)絡(luò)，它是由“M-P神經(jīng)元模型”為基礎(chǔ)發(fā)展而來[25]。 ANN的結(jié)構(gòu)如圖2所示，它由輸入層、隱藏層和輸出層組成，各層神經(jīng)元與相鄰層神經(jīng)元之間相互全相聯(lián)。輸入層神經(jīng)元用來接收外界的輸入?yún)?shù)，通過各層連接的權(quán)值與對應(yīng)的輸入?yún)?shù)相乘，再與該層其他神經(jīng)元傳入連接的結(jié)果相加，它們的和會被傳遞到神經(jīng)元的激活函數(shù)中（如修正線性函數(shù)），最后將這些神經(jīng)元的輸出作為輸入傳遞到下一層隱藏神經(jīng)元或輸出神經(jīng)元中。在訓(xùn)練期間，ANN可以通過Adam（Adaptive moment estimation）優(yōu)化算法[26]來調(diào)整權(quán)值，以此找到一個最優(yōu)的極小值使得實際輸出與網(wǎng)絡(luò)計算輸出之間的預(yù)測誤差最小化。

2.2.2 預(yù)測模型建模

采用人工神經(jīng)網(wǎng)絡(luò)模型來對映射方案的性能指標進行預(yù)測，關(guān)鍵在于識別對性能結(jié)果產(chǎn)生影響的關(guān)鍵信息或特征?？紤]到運行時信息獲取的難易程度以及動態(tài)映射對高效性的需求，本文采用任務(wù)在異構(gòu)多核系統(tǒng)的映射位置以及所映射核的頻率值作為模型的輸入信息。下面介紹本文所采用的輸入信息編碼方式。

圖3給出了一個由m個任務(wù)（t1，t2，…，tm）構(gòu)成的應(yīng)用在由9個核構(gòu)成的二維片上網(wǎng)絡(luò)（Network on Chip， NoC）（3×3）異構(gòu)多核系統(tǒng)上的映射編碼方式。異構(gòu)多核系統(tǒng)中的核根據(jù)位置用二維笛卡兒坐標進行表示，并且每個核有F={fk|k=1，2，…，|F|}種頻率可供選擇，圖中箭頭表示當前任務(wù)映射到哪個核上。每一種映射方案可以表示為一個映射編碼向量，該向量由t1， t2，…，tm所映射的目標核的位置坐標以及所選擇的頻率組合而成。

此外，在將含有映射位置和頻率的編碼輸入信息給預(yù)測模型訓(xùn)練之前，為了提高梯度收斂的速度，需要對頻率進行特征縮放處理。本文所采用的方法是對每個核的頻率值都除以固定的數(shù)，從而保證頻率的范圍處在0到20之間。以圖3中所示的映射方案為例，當任務(wù)t1映射到坐標為（0，0）、頻率為40MHz的核上，任務(wù)t2映射到坐標為（0，2）、頻率為120MHz的核上，任務(wù)tm映射到坐標為（2，0）、頻率為60MHz的核上時，通過把它們的頻率都除以10，可以得到映射編碼（0，0，4，0，2，12，… ，2，0，6）。

2.2.3 性能評估標準

度量不同學(xué)習模型的泛化能力，不僅要有高效的實驗預(yù)測方法，還要有衡量模擬器泛化能力的評估標準?；貧w問題常用的預(yù)測度量標準是計算真實值與實際值之間的均方誤差（Mean Squared Error， MSE），MSE值越低，預(yù)測模型準確度越高。然而，本文的目標是能夠在運行時從多個映射方案中選擇一個相對最好的映射方案， 因而得到一個可以對映射方案的性能值進行正確排序的模型就足夠了。當預(yù)測模型的MSE值很低的時候這種相對大小是可以保證的，而MSE值很高的時候并不能說明這種相對大小就一定不能夠得到保證。因而，為了得到一個可以對若干個映射方案性能值相對大小進行預(yù)測的模型，需要一種可以對預(yù)測數(shù)值的相對大?。ɑ蛘呲厔荩┻M行評估的方法。本文采用常用的趨勢預(yù)測指標皮爾遜相關(guān)系數(shù)（Person Correlation Coefficient， PCC）來進行評估，表示如下：

其中：N表示測試樣本的個數(shù);Pi表示預(yù)測模型預(yù)測的性能值;Ei表示模擬器運行得到的真實值;P和E分別表示預(yù)測樣本和真實樣本的平均值;σP和σE分別表示預(yù)測樣本和真實樣本的標準差。r的值介于-1和1之間，當r的絕對值越接近1，表示預(yù)測值越接近真實值，性能預(yù)測模型越好。

2.3 在線調(diào)度

在系統(tǒng)運行過程中，當運行環(huán)境發(fā)生變化時，在線調(diào)度模塊需要能夠?qū)ο鄳?yīng)的可選映射方案進行高效的搜索、評估，并選擇最優(yōu)或者接近最優(yōu)的解決方案。在2.2節(jié)構(gòu)建的映射方案預(yù)測模型基礎(chǔ)上，還需要一個可以高效地引導(dǎo)、并選擇盡可能最優(yōu)映射方案的搜索機制。鑒于該類問題搜索空間的龐大，本文采用文獻[27]中的一個遺傳算法（GA）來在線對系統(tǒng)的映射空間進行搜索，鑒于篇幅限制該算法細節(jié)不再詳述。

如圖1（b）中所示，在線調(diào)度模塊的基本工作流程包括：1）當應(yīng)用程序啟動后，算法GA迭代搜索映射方案空間，并根據(jù)搜索目標和預(yù)測模型對各個映射方案的性能預(yù)測結(jié)果來確定初始映射方案，然后對初始方案在運行平臺上進行相應(yīng)部署;2）每當系統(tǒng)運行狀態(tài)發(fā)生變化時，如某個運行核由于負載過高或故障等原因不可用時，在線搜索、評估當前系統(tǒng)狀態(tài)下可行的映射方案，并從中選擇最優(yōu)的映射方案重新進行部署。

3 CLASSY模擬工具

本文使用文獻[24，28]的CLASSY模擬器來分析異構(gòu)多核處理器上不同映射方案的性能指標，該模擬器是基于Lee等[29]針對嵌入式系統(tǒng)建模（Model of Computation）所提出的Tagged Model構(gòu)建的。

為了采用Tagged Model對應(yīng)用程序運行行為進行描述，CLASSY定義了兩個集合：一個邏輯時刻的離散集合T（包含最小元素τmin且與一個偏序相關(guān)聯(lián)）和一個值域集合V（表示事件的運行時間或功耗）。二元組（τ，υ），其中τ∈T，υ∈V，表示一個事件e。事件e可以是任務(wù)運行過程中的某次運算或者某次信息傳輸?shù)?，一個連續(xù)的事件集合就構(gòu)成一個任務(wù)t的行為bt，可以用bt={ e0，e1，…} 表示。基于事件e和任務(wù)行為bt的定義，可以對應(yīng)用程序行為進行以下定義。

定義1 給定一個任務(wù)集合T構(gòu)成的應(yīng)用程序，則其行為可用一對（∪bt（t∈T），）表示，其中∪bt（t∈T）表示所有任務(wù)t∈T中事件的集合，表示事件之間的偏序關(guān)系。

圖4給出了一個由三個任務(wù)T={t0，t1，t2}組成的應(yīng)用程序的行為bT，其中bt0={e00，e10}，bt1={e01，e11}，bt2={e02，e12}。圖4中的箭頭表示事件間的優(yōu)先關(guān)系（比如某個人物的運算需要等待其他任務(wù)的計算結(jié)果），如箭頭從事件e00指向事件e02則表示為e00e02，而兩個事件之間沒有箭頭連接意味著它們之間沒有優(yōu)先關(guān)系約束，如事件e10和事件e01。

針對異構(gòu)多核處理器平臺，該模擬器采用了基于同步時鐘的模型來進行模擬，并可以對各個處理核在不同運行頻率下的行為進行區(qū)別。給定相應(yīng)的應(yīng)用和平臺描述后，該模擬器就可以對不同的映射調(diào)度方案進行性能分析和評估。此外，它還提供了一種動態(tài)映射調(diào)度模擬機制，允許用戶通過整合自己的動態(tài)映射算法來對運行時的不同調(diào)度選擇進行時間等方面的性能評估。鑒于篇幅限制，這方面的具體細節(jié)不再詳述。

4 實驗與結(jié)果分析

為了驗證本文提出的基于機器學(xué)習的在線映射調(diào)度方法的效果和效率（即響應(yīng)時間），分別進行兩方面的實驗：1）4.2節(jié)的實驗驗證所構(gòu)建機器學(xué)習預(yù)測模型的準確度和效率;2）4.3節(jié)的實驗驗證整合遺傳算法和預(yù)測模型的在線映射調(diào)度算法的效果和效率。

4.1 實驗設(shè)置

本文采用的應(yīng)用實例是文獻[27]中使用的M-JPEG（Motion-Join Photographic Experts Group）解碼器（如圖5所示），該應(yīng)用程序由5個任務(wù)組成，包括Demux、VLD、IQZZ、IDCT和Libu;所使用的運行平臺是一個2×3的二維NoC異構(gòu)多核平臺（如圖6所示），該平臺由五個核{p1，p2，… ，p5}組成，其中核p1、p2、p3分配到第一行，分別用二維笛卡兒坐標（0，0）、（0，1）和（0，2）表示，該行核有兩種頻率可供選擇{40MHz，80MHz}，核p4、p5分配到第二行，分別用坐標（1，0）和（1，1）表示，該行核可供選擇的頻率是{60MHz，120MHz}。本文所運行實驗的機器配置為CPU： Intel Core i5-6600 3.4GHz、內(nèi)存：32GB。

4.2 預(yù)測模型的準確性驗證

在這部分中，我們將分別介紹構(gòu)建性能預(yù)測模型的數(shù)據(jù)集獲取、所采用ANN算法進行模型訓(xùn)練的參數(shù)設(shè)置和對所獲取模型的驗證分析結(jié)果。

4.2.1 數(shù)據(jù)集獲取

對于4.1節(jié)給出的M-JEPG應(yīng)用程序和執(zhí)行平臺，采用ClASSY模擬器來產(chǎn)生所需要的數(shù)據(jù)集。首先，隨機生成30000種映射方案作為數(shù)據(jù)集，然后將以上數(shù)據(jù)集劃分為訓(xùn)練集和測試集。按照機器學(xué)習模型訓(xùn)練和驗證常用的劃分方法，將總數(shù)據(jù)集的65%（即19500種）用來訓(xùn)練模型，剩下的35%（即10500種）作為測試集用來評估該模型在未知數(shù)據(jù)上的預(yù)測能力。

4.2.2 ANN算法參數(shù)設(shè)置

本文使用人工神經(jīng)網(wǎng)絡(luò)（ANN）算法來學(xué)習得到目標性能預(yù)測模型。為此，本文使用Pytorch軟件包對人工神經(jīng)網(wǎng)絡(luò)模型進行訓(xùn)練，使用高斯分布來隨機初始化權(quán)值矩陣，訓(xùn)練過程中采用Adam優(yōu)化方法迭代更新參數(shù)。根據(jù)多次實驗測試優(yōu)化相關(guān)超參數(shù)，表1給出了最終相關(guān)超參數(shù)的詳細設(shè)置。

4.2.3 ANN性能預(yù)測模型的驗證

圖7給出了經(jīng)過學(xué)習后得到的人工神經(jīng)網(wǎng)絡(luò)預(yù)測模型在所有測試集數(shù)據(jù)上的預(yù)測情況，其中，橫軸（X軸）表示由CLASSY模擬器得到的實際值，縱軸（Y軸）表示由預(yù)測模型給出的預(yù)測值。圖7中每一個點表示測試集中的一種映射方案，每一個點的位置表示實際值和預(yù)測值的相對偏差。當相關(guān)系數(shù)為1時，則所有的數(shù)據(jù)點都將收斂到X=Y的函數(shù)曲線上，表示預(yù)測值與實際值相等。從圖7可以看出，本文所獲得的ANN預(yù)測模型的預(yù)測效果很接近X=Y函數(shù)曲線，預(yù)測效果非常好。另外，通過計算得到該預(yù)測模型的預(yù)測值和實際值之間的皮爾遜相關(guān)系數(shù)值：0.97，非常接近1，因而這兩組數(shù)據(jù)是非常相關(guān)的，從而可以驗證本文得到的人工神經(jīng)網(wǎng)絡(luò)預(yù)測模型可以對映射方案性能值的相對大小進行準確的預(yù)測。

此外，在本實驗中對ANN模型離線訓(xùn)練所需時間是4min，生成預(yù)測模型的大小是4KB，而采用該模型進行預(yù)測的響應(yīng)時間為2.4ms。

4.3 動態(tài)調(diào)度方案效果驗證

為了驗證本文動態(tài)調(diào)度方案的效果，通過隨機生成一個固定長度系統(tǒng)運行時的事件序列，例如某個運行核由于負載過高或故障等原因不可用、某兩個核之間的通信斷開等，來進行實驗?？紤]到采用遺傳算法不同參數(shù)對算法的影響，首先通過實驗評估不同參數(shù)的效果和開銷，然后將本文方法分別與常見的輪詢調(diào)度（Round Robin Scheduler， RRS）[30] 、抽樣調(diào)度和通過遍歷所有方案獲得的最優(yōu)化方法進行對比實驗。

4.3.1 算法參數(shù)評估實驗

對于遺傳算法，需要考慮如下參數(shù)：1）種群規(guī)模（population），每一代種群染色體總數(shù);2）迭代（iteration），種群交叉變異迭代的次數(shù);3）基因（gene），用于表示個體的特征;4）交叉概率（P_cross），在循環(huán)中進行交叉操作所用到的概率;5）變異概率（P_mutation），從個體群中產(chǎn)生變異的概率。表2給出了M-JPEG解碼器在保持執(zhí)行平臺不變的情況下，種群規(guī)模（#popu.）和迭代次數(shù)（，#inter.）的選取對算法開銷和執(zhí)行時間的影響（交叉概率和變異概率根據(jù)若干實驗驗證分別選取效果最好的0.8和0.003）。

從表2中可以看出，隨著迭代次數(shù)和種群規(guī)模不斷變大，其方案效果越來越好（執(zhí)行時間越來越短），然而相應(yīng)的實踐開銷也越來越大。綜合考慮執(zhí)行時間和算法開銷，在后面的實驗中均采用種群規(guī)模為1000，迭代次數(shù)為10。

4.3.2 方案效果比較實驗

圖8給出了四種調(diào)度方法在100個隨機事件序列場景下得到的平均執(zhí)行時間，其中每個隨機事件序列包括10個事件（如某個運行核由于負載過高或故障等原因不可用、某兩個核之間的通信斷開等），并且事件發(fā)生的時間是隨機的。

從圖8中可以看出：輪詢調(diào)度的執(zhí)行時間最長，主要原因在于輪詢調(diào)度將任務(wù)的請求輪流分配給每個核，但是這種調(diào)度方式通常忽略了任務(wù)和每個核各自的特點和需求，無法充分發(fā)揮異構(gòu)多核處理器的優(yōu)勢，因而效果最差。抽樣調(diào)度是從1000個候選的映射方案中抽選最優(yōu)的調(diào)度方案并執(zhí)行調(diào)度，這種調(diào)度方式的表現(xiàn)往往會優(yōu)于輪詢調(diào)度，但是其調(diào)度結(jié)果受到隨機抽樣的約束。最優(yōu)調(diào)度是探索每一種系統(tǒng)動態(tài)場景中所有的映射方案，從而選出最優(yōu)的調(diào)度方法，該調(diào)度模型無疑是最優(yōu)的，但是遍歷所有可能性并進行性能評估的時間開銷過大（本實驗中平均需要2.83min），不適合解決動態(tài)映射調(diào)度問題。而本文的調(diào)度模型是通過遺傳算法和機器學(xué)習相結(jié)合的方式，相較于輪詢和抽樣調(diào)度，遺傳算法通過不斷迭代的方式能夠高效地引導(dǎo)搜索的方向，相較于最優(yōu)調(diào)度，基于機器學(xué)習的性能預(yù)測模型能夠在縮短在線搜索評估開銷的同時給出接近最優(yōu)調(diào)度的效果，本實驗中每次調(diào)度調(diào)整平均需要時間為0.93s。

在本實驗中，本文提出的基于機器學(xué)習預(yù)測模型的在線映射調(diào)度方法在平均執(zhí)行時間方面相較于常用的輪詢調(diào)度和抽樣調(diào)度方法能夠分別降低了28%和19%，并達到接近最優(yōu)的解決方案。

5 結(jié)語

本文提出了一種基于機器學(xué)習預(yù)測模型的在線映射方法：一方面通過采用機器學(xué)習技術(shù)來構(gòu)造系統(tǒng)性能預(yù)測模型來，從而對不同映射方案和每個核的頻率值進行高效的性能評估;另一方面，將其與遺傳算法進行整合構(gòu)造了一個在線的映射調(diào)度方法。實驗結(jié)果表明，所提方法在平均執(zhí)行時間方面相較于常用的輪詢調(diào)度和抽樣調(diào)度方法能夠分別降低了28%和19%，并接近最優(yōu)的解決方案。

下一步的研究分兩方面進行：一方面希望采用更廣泛多樣的案例來驗證該在線映射方法的效果;另一方面由于目前采用的模擬工具對于異構(gòu)多核系統(tǒng)中每個核之間的通信開銷以及任務(wù)遷移的開銷精確度不足，我們希望在進一步研究基礎(chǔ)上，使用更加精確的模擬工具或者是基于實際的異構(gòu)多核平臺（比如ARM big.Little）來進行實驗。此外，在接下來的工作中，我們還將考慮通過改進在線調(diào)度算法來進一步提高映射效果。

參考文獻 （References）

[1] GREENHALGH A P. Big. LITTLE processing with ARM cortexTM-A15 & cortex-A7 [EB/OL]. [2018-09-19]. https：//www.arm.com/files/downloads/b-igLITTLE Final Final.pdf.

[2] Apple Inc. A12-bionic [EB/OL]. [2018-09-12]. https：//www.apple.com/cn/iphone-xs/a12-bionic/.

[3] LI C V， PETRUCCI V， MOSSE D. Predicting thread profiles across core types via machine learning on heterogeneous multiprocessors [C]// Proceedings of the 2016 VI Brazilian Symposium on Computing Systems Engineering. Piscataway， NJ： IEEE， 2016： 56-62.

[4] LE SUEUR E， HEISER G. Dynamic voltage and frequency scaling： The laws of diminishing returns [C]// HotPower 2010： Proceedings of the 2010 International Conference on Power Aware Computing and Systems. Berkeley， CA： USENIX Association， 2010： Article No. 1-8.

[5] GOLI M， MCCALL J， BROWN C， et al. Mapping parallel programs to heterogeneous CPU/GPU architectures using a Monte Carlo tree search [C]// CEC 2013： Proceedings of the 2013 IEEE Congress on Evolutionary Computation. Piscataway， NJ： IEEE， 2013： 2932-2939.

[6] NEMIROVSKY D， ARKOSE T， MARKOVIC N， et al. A machine learning approach for performance prediction and scheduling on heterogeneous CPUs [C]// Proceedings of the 2017 IEEE 29th International Symposium on Computer Architecture and High Performance Computing. Piscataway， NJ： IEEE， 2017： 121-128.

[7] ZHANG Y Q， LAURENZANO M A， MARS J， et al. SMiTe： precise QoS prediction on real-system SMT processors to improve utilization in warehouse scale computers [C]// Proceedings of the 2014 47th Annual IEEE/ACM International Symposium on Microarchitecture. Washington， DC： IEEE Computer Society， 2014： 406-418.

[8] MICHALSKA M， CASALE-BRUNET S， BEZATI E， et al. High-precision performance estimation for the design space exploration of dynamic dataflow programs [J]. IEEE Transactions on Multi-Scale Computing Systems， 2018， 4（2）： 127-140.

[9] SAYADI H， PATEL N， SASAN A， et al. Machine learning-based approaches for energy-efficiency prediction and scheduling in composite cores architectures [C]// Proceedings of the 2017 35th IEEE International Conference on Computer Design. Piscataway， NJ： IEEE， 2017： 129-136.

[10] WANG L， LIU S L， LU C， et al. Stable matching scheduler for single-ISA heterogeneous multi-core processors [C]// APPT 2015： Proceedings of the 2015 International Workshop on Advanced Parallel Processing Technologies， LNCS 9231. Cham： Springer， 2015： 45-59.

[11] ULLMAN J D. NP-complete scheduling problems [J]. Journal of Computer and System Sciences， 1975， 10（3）： 384-393.

[12] ROY P， ALAM M M U， DAS N. Heuristic based task scheduling in multiprocessor systems with genetic algorithm by choosing the eligible processor [J]. International Journal of Distributed and Parallel Systems， 2012， 3（4）： 111-121.

[13] CHATTERJEE N， PAUL S， MUKHERJEE P， et al. Deadline and energy aware dynamic task mapping and scheduling for network-on-chip based multi-core platform [J]. Journal of Systems Architecture， 2017， 74： 61-77.

[14] GHARSELLAOUI H， KTATA I， KHARROUBI N， et al. Real-time reconfigurable scheduling of multiprocessor embedded systems using hybrid genetic based approach [C]// Proceedings of the 2015 IEEE/ACIS 14th International Conference on Computer and Information Science. Piscataway， NJ： IEEE， 2015： 605-609.

[15] SINGH A K， SHAFIQUE M， KUMAR A， et al. Mapping on multi/many-core systems： survey of current and emerging trends [C]// DAC 2013： Proceedings of the 2013 50th ACM/EDAC/IEEE Design automation conference. Piscataway， NJ： IEEE， 2013： 1-10.

[16] CAI E， JUAN D C， GARG S， et al. Learning-based power/performance optimization for many-core systems with extended-range voltage/frequency scaling [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2016， 35（8）： 1318-1331.

[17] MICOLET P J， SMITH A， DUBACH C. A machine learning approach to mapping streaming workloads to dynamic multicore processors [C]// LCTES 2016： Proceedings of the 2016 17th ACM SIGPLAN/SIGBED Conference on Languages， Compilers， Tools， and Theory for Embedded Systems. New York： ACM， 2016： 113-122.

[18] GAMATIE A， URSU R， SELVA M， et al. Performance prediction of application mapping in manycore systems with artificial neural networks [C]// Proceedings of the 2016 IEEE 10th International Symposium on Embedded Multicore/Many-core Systems-on-Chip. Piscataway， NJ： IEEE， 2016： 185-192.

[19] WEN Y， WANG Z， OBOYLE M F P. Smart multi-task scheduling for OpenCL programs on CPU/GPU heterogeneous platforms [C]// HiPC 2014： Proceedings of the 2014 21st International Conference on High Performance Computing. Piscataway， NJ： IEEE， 2014： 1-10.

[20] TAYLOR B， MARCO V S， WANG Z. Adaptive optimization for OpenCL programs on embedded heterogeneous systems [C]// LCTES 2017： Proceedings of the 18th ACM SIGPLAN/SIGBED Conference on Languages， Compilers， and Tools for Embedded Systems. New York： ACM， 2017： 11-20.

[21] BITIRGEN R， IPEK E， MARTINEZ J F. Coordinated management of multiple interacting resources in chip multiprocessors： a machine learning approach [C]// MICRO 41： Proceedings of the 41st annual IEEE/ACM International Symposium on Microarchitecture. Washington， DC： IEEE Computer Society， 2008： 318-329.

[22] 袁景凌，繆旭陽，楊敏龍，等.基于神經(jīng)網(wǎng)絡(luò)的多核功耗預(yù)測策略[J].計算機科學(xué)，2014，41（6A）：47-51.（JIAO J L， MIAO X Y， YANG M L， et al. Neural network based power prediction strategy for multi-core architecture [J]. Computer Science， 2014， 41（6A）： 47-51.）

[23] 王彥華，喬建忠，林樹寬，等.基于SVM的CPU-GPU異構(gòu)系統(tǒng)任務(wù)分配模型[J].東北大學(xué)學(xué)報（自然科學(xué)版），2016，37（8）：1089-1094.（WANG Y H， QIAO J Z， LIN S K， et al. A Task allocation model for CPU-GPU heterogeneous system based on SVMs [J]. Journal of Northeastern University （Natural Science）， 2016， 37（8）： 1089-1094.）

[24] AN X， BOUMEDIEN S， GAMATIE A， et al. CLASSY： a clock analysis system for rapid prototyping of embedded applications on MPSoCs [C]// SCOPES 2012： Proceedings of the 2012 15th International Workshop on Software and Compilers for Embedded Systems. New York： ACM， 2012： 3-12.

[25] HAYKIN S S. Neural Networks： a Comprehensive Foundation [M]. Upper Saddle River， NJ： Prentice Hall， 1994： 133-147.

[26] KINGMA D P， BA J L. Adam： a method for stochastic optimization [EB/OL]. [2018-09-19]. https：//www.docin.com/p-1725989690.html. Proceedings of the 2014 International Conference on Learning Representations.arXiv preprint arXiv.1412.6980， 2014.

[27] HOLLAND J H. Adaptation in Natural and Artificial Systems： an Introductory Analysis with Applications to Biology， Control， and Artificial Intelligence [M]. Cambridge， MA： MIT press， 1992： 32-58.

[28] AN X， GAMATIE A， RUTTEN E. High-level design space exploration for adaptive applications on multiprocessor systems-on-chip [J]. Journal of Systems Architecture， 2015， 61（3/4）： 172-184.

[29] LEE E A， SANGIOVANNI-VINCENTELLI A. A framework for comparing models of computation [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 1998， 17（12）： 1217-1229.

[30] MARKOVIC N， NEMIROVSKY D， MILUTINOVIC V， et al. Hardware round-robin scheduler for single-ISA asymmetric multi-core [C]// Euro-Par 2015： Proceedings of the 2015 European Conference on Parallel Processing， LNCS 9233. Berlin： Springer， 2015： 122-134.