基于機器學習的異構多核處理器系統在線映射方法

安鑫 張影 康安 陳田 李建華

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

關鍵詞：異構多核處理器;機器學習;動態資源分配;性能預測;映射和調度

中圖分類號： 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 引言

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

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

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

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

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

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

1 相關工作

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

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

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

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

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

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

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

2 基于機器學習的在線映射方法

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

2.1 整體框架

本文提出的基于機器學習的在線映射方法整體設計框架如圖1所示，分為：1）離線訓練（圖1（a）），即映射方案性能預測模型構建;2）在線調度（圖1（b）），即運行時動態映射方案搜索、評估和選擇。

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

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

2.2 離線訓練——性能預測模型構建

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

2.2.1 人工神經網絡

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

2.2.2 預測模型建模

采用人工神經網絡模型來對映射方案的性能指標進行預測，關鍵在于識別對性能結果產生影響的關鍵信息或特征。考慮到運行時信息獲取的難易程度以及動態映射對高效性的需求，本文采用任務在異構多核系統的映射位置以及所映射核的頻率值作為模型的輸入信息。下面介紹本文所采用的輸入信息編碼方式。

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

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

2.2.3 性能評估標準

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

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

2.3 在線調度

在系統運行過程中，當運行環境發生變化時，在線調度模塊需要能夠對相應的可選映射方案進行高效的搜索、評估，并選擇最優或者接近最優的解決方案。在2.2節構建的映射方案預測模型基礎上，還需要一個可以高效地引導、并選擇盡可能最優映射方案的搜索機制。鑒于該類問題搜索空間的龐大，本文采用文獻[27]中的一個遺傳算法（GA）來在線對系統的映射空間進行搜索，鑒于篇幅限制該算法細節不再詳述。

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

3 CLASSY模擬工具

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

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

定義1 給定一個任務集合T構成的應用程序，則其行為可用一對（∪bt（t∈T），）表示，其中∪bt（t∈T）表示所有任務t∈T中事件的集合，表示事件之間的偏序關系。

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

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

4 實驗與結果分析

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

4.1 實驗設置

本文采用的應用實例是文獻[27]中使用的M-JPEG（Motion-Join Photographic Experts Group）解碼器（如圖5所示），該應用程序由5個任務組成，包括Demux、VLD、IQZZ、IDCT和Libu;所使用的運行平臺是一個2×3的二維NoC異構多核平臺（如圖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、內存：32GB。

4.2 預測模型的準確性驗證

在這部分中，我們將分別介紹構建性能預測模型的數據集獲取、所采用ANN算法進行模型訓練的參數設置和對所獲取模型的驗證分析結果。

4.2.1 數據集獲取

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

4.2.2 ANN算法參數設置

本文使用人工神經網絡（ANN）算法來學習得到目標性能預測模型。為此，本文使用Pytorch軟件包對人工神經網絡模型進行訓練，使用高斯分布來隨機初始化權值矩陣，訓練過程中采用Adam優化方法迭代更新參數。根據多次實驗測試優化相關超參數，表1給出了最終相關超參數的詳細設置。

4.2.3 ANN性能預測模型的驗證

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

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

4.3 動態調度方案效果驗證

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

4.3.1 算法參數評估實驗

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

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

4.3.2 方案效果比較實驗

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

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

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

5 結語

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

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

參考文獻 （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].計算機科學，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異構系統任務分配模型[J].東北大學學報（自然科學版），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.