基于ANN的異構多核動態映射方法

李 陽，李建華，2，周義濤，趙玉來，胡海洋

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

0 引言

隨著應用程序對計算能力需求的逐漸增長，以及半導體技術的逐步演進，多核處理器的核心數量一直在增加。異構多核架構通過在同一平臺上集成多種類型的處理核，使得應用程序可以根據自身需求選擇不同的核心組合來更加高能效地完成任務。因此，異構多核平臺相比于同構多核平臺擁有更高的靈活性，并且可以更合理地利用片上資源。目前，異構多核平臺已經成為了當今嵌入式系統的主流解決方案。充分發揮異構多核系統的優勢需要高效的程序映射方法。

程序映射可以分為靜態映射和動態映射。其中，動態程序映射可根據程序的階段性特征以及不同類型處理核的特點進行映射的動態調整，能更充分地發揮平臺的性能優勢。靜態程序映射是在設計時進行的，因此可以使用計算密集型搜索方法或精確的系統級映射模擬來尋找最佳或近最佳的映射解決方案。但是，通常情況下卻無法處理（未知）動態工作負載。一個程序在其生命周期中可執行數百萬、數十億條、甚至更多的指令，并且其運行時的特征也在不斷地變化。一個高效的映射算法應該能夠根據這些變化的特征預測程序不同時刻在不同類型的核心上運行可獲得的性能，以便獲得更好的能效比。

近些年來，人工神經網絡（Artificial Neural Network，ANN），是人工智能領域的研究熱點之一。ANN是由多個具有層次和連接關系的神經元相互連接而成，一個完整的人工神經網絡是由輸入層、輸出層和隱藏層三部分組成。其中，輸入層負責接收和傳遞信息，不進行任何計算。隱藏層位于輸入層和輸出層之間，可以與輸入層和輸出層相連，不同的隱藏層間也可以互相連接，這些連接都被賦予了一個數值權重，該權重與相應的輸入參數相乘后，再與神經元其他傳入連接的結果相加。接下去，這些總和被傳遞到神經元的激活函數中，通常選用的是一個線性函數。如此處理后的神經元輸出將繼續輸入到下一層神經元或輸出神經元。總地來說，ANN可以通過合理的網絡結構擬合任意的非線性方程，因此ANN在數值預測和分類輸出方面都有著巨大的潛力。

ANN正在被廣泛地應用于各種領域，例如情感分析、預測估計、生物醫學等。雖然ANN的應用受到越來越多的關注，但是到目前為止，將其應用于多核異構平臺映射算法上的研究卻仍處于起步階段。為此，本文提出了一種基于ANN的異構多核動態映射方法AbDM。

AbDM的主要目標是最大化異構多核平臺性能，在給定多個應用程序和一個具有多種不同類型核心的異構平臺上，通過動態調整應用到核心的映射來實現目標。首先，使用基于ANN的性能預測器根據一段時間內的執行參數，預測每個應用下一階段在不同類型核心上的性能。隨后，重映射檢測算法判斷是否需要執行重映射。最后，若需要重映射，則由線程到核心類型匹配算法利用獲得的性能值，確定應用到核心的映射。

本文的主要貢獻如下：

（1）提出了一種線程到核心類型的匹配算法，在充分發揮平臺性能優勢的同時節省線程到核心類型綁定的時間。

（2）提出了一種重映射檢測算法，當線程執行階段發生變化時觸發重映射過程，從而避免過于頻繁的重映射，減少重新映射的時間和成本。

（3）提出了一種基于神經網絡的性能預測器，將運行參數作為模型輸入，預測性能。

實驗結果證實本文提出的AbDM和輪詢調度算法（RRS）相比平均每個時鐘周期執行的指令條數（）提高了63%左右。

本文其余部分組織如下：第一節介紹了相關研究工作；第二節闡述了本文提出的AbDM的具體實現；第三節對本文方法進行了實驗驗證和分析；第四節則總結了本文工作并展望了未來的研究方向。

1 相關工作

異構多核平臺上的應用映射在開發計算資源的多樣性方面發揮著關鍵作用，對此已經有數十年的研究積累。一般情況下對于異構多核映射問題大都采用一個線程映射到一個處理核心的模式。當前針對異構多核架構映射問題的研究可以分為3類：離線、在線和混合（離線分析后在線使用）方法。為了找到近似最優的映射解決方案，現有研究大多采用基于搜索的方法，結合一些分析來評估考慮的映射與設計需求之間的關系。

對于離線方法，在離線狀態下充分探索這些不同場景的資源分配，從而為每個場景指定一個最優或接近最優的資源分配方案。例如，文獻［7］提出了一種靜態調度方法，這是一種基于種群的新算法，可以在運行時動態切換探索性和開發性搜索模式。靜態調度器可以執行任務映射、調度和電壓縮放。在文獻［8］中，提出了一種算法來優化異構上應用程序的整體運行時間多核處理器。該算法將模擬退火和剪枝策略的組合，用于搜索應用程序和平臺之間的最佳映射。上述離線方法通常使用離線分析來確定映射方案，雖然簡單、但會產生額外的分析開銷，并且沒有充分考慮在線程序在執行過程中的動態變化。

與離線方法相比，在線資源管理缺少離線預處理階段。一般每個應用程序占用的資源都是在運行時動態調整的。這種方法的資源分配計劃是在運行時計算出來的，方法的目的則是為了在短時間內得到一個比較好的資源分配計劃。例如，文獻［9］中提出的方法首先根據性能要求和資源可用性選擇線程到核心的映射。然后，通過調整電壓頻率（）水平來應用在線自適應，以在不犧牲應用性能的情況下實現能量優化。研究可知，在文獻［10］中已有學者提出了一種基于機器學習的方法來增加異構多核平臺上的平均故障工作量，最終結果表明該方法的平均工作量增幅可以高達19.4%。在文獻［11］中，還提出了一種不需要任何自身信息就能夠在線對OpenCL應用進行功耗優化的一種自適應方法。

混合資源管理方法使用離線分析結果來做出運行時資源管理決策。第一步是在設計時進行全面的離線分析，并將分析結果集成到運行時控制器中，實現運行時的資源分配。例如文獻［12］提出的方法，首先使用緩存分區技術來限制共享緩存的不可預測性，其次探討核心頻率的影響和緩存分區（CPs）對任務執行周期的影響及其對執行時間和能耗的影響。此外，文獻［13］又提出了一種自適應映射方法。首先，使用性能監控計數器進行在線數據收集，然后使用離線訓練性能預測模型來應用不同類型的數據。預測應用程序的性能，最后評估和選擇資源組合（處理核心的數量和類型）。仍要提到的是，該方法還設置了一個資源管理器來監控應用程序性能、工作量，以及應用程序完成和新應用程序的到達情況，再以此來調整映射。

離線方法是設計時進行的，能夠找到最優或者接近最優的映射方案，但是通常卻無法處理動態工作負載問題。而在線方法能夠解決動態工作負載問題，但是由于運行時計算能力有限，可能最終獲得的映射方案不是最優方案或者接近最優的映射方案。混合資源管理方法結合了離線和在線的優點，可以在離線的時候對不同的應用場景進行充分的分析，也可以在運行時根據不同的執行場景動態地調整映射方案。所以目前混合資源管理方法獲得了十分廣泛的應用。

綜上，本文采用混合資源分配方案來實現資源分配，可以充分考慮不同類型線程的運行時特性和不同內核的處理能力，從而最大限度地發揮平臺的處理能力。

2 基于ANN的異構多核動態映射方法

本節主要介紹文中所提出的AbDM方案，圖1給出了其總體框架。給定一組線程和一個異構多核平臺，映射器首先為每個線程隨機分配一個空閑核心。同時，收集必要的運行時信息，用來進行性能預測。然后，重映射檢測器根據預測所得的性能判斷是否需要執行重映射。在需要執行重映射的情況下，由線程到核心類型匹配算法，將線程和核心進行匹配，從而實現IPC優化。

圖1 AbDM總體框架Fig.1 Overview of the proposed approach，AbDM

2.1 問題定義

在本文中，通過個線程（，，，t）在的多核平臺上執行，表示為｛，…，C，…，C｝，其中C表示核心位于2網格的第行和第列。每個核C屬于種核類型的一種、表示為｛，，…，c｝，并且可以獨立地執行DVFS（Dynamic Voltage and Frequency Scaling）。本文所提出的AbDM方案使用每個時鐘周期所執行的指令數、即指令數／周期（Instructions Per Cycle，）作為性能指標。

由于程序運行在其生命周期中經常會發生一些階段性的變化，并且不同的階段有著不同的運行時的特征。所以，需要周期性地收集程序運行過程中相關特征數據。

2.2 運行時參數收集

AbDM需要周期性地收集必要的運行時參數數據，以進行動態的重映射決策。AbDM收集的參數如下：

（1）用于監視在特定內核上運行線程的性能的值。

（2）緩存缺失，包括：一級數據緩存命中缺失率、二級緩存命中缺失率、三級緩存命中缺失率，以及讀內存指令、寫內存指令、浮點加法指令、浮點減法指令、浮點乘法指令和浮點除法指令。

2.3 性能預測器

為了將線程分配給異構多核系統中的特定核以最大化性能，必須了解每個線程在各種類型的核上的執行情況。實現這一目標的一種方法是在所有類型的內核上在線執行線程，并相應地采取最佳分配。這顯然并不適用于在線映射方法，因為需要用到復雜的運行時遷移和性能度量。另一種方法是通過只在一種核心類型上運行（參見文獻［7］）來獲得不同類型核心的線程性能。這種方法需要在設計時或運行時構建性能預測模型。由于運行時的學習模型可能會使動態映射方法不可擴展，并且還將引入太多的開銷。類似于文獻［5，13］中的做法，本文選擇在設計時使用機器學習技術為所有類型的核構建預測模型。

2.3.1 參數的選取

應用在某類核心上執行的不僅取決于當前執行的類型，還和硬件資源相關。因此，需要將一些應用統計信息及執行參數作為預測器的輸入參數。根據文獻［16-17］中的方案所選擇的參數和屬性，本文選取了9個與相關的參數來構建ANN學習模型。參數分別是緩存丟失率（一級數據緩存命中缺失率、二級緩存命中缺失率、三級緩存命中缺失率），以及讀內存指令、寫內存指令、浮點加法指令、浮點減法指令、浮點乘法指令和浮點除法指令。

2.3.2 參數的預處理

由于模擬直接收集的輸入參數的統計量可能具有不同的尺度（例如，緩存失效率低于1，而指令數可達數千萬），因此需要對輸入參數做預處理，以確保輸入參數具有相同的尺度。另一方面，為了使用統計信息作為不同核心類型的性能預測的輸入，統計信息應該盡可能通用。將統計數據規范化為比率可以確保神經網絡輸入的一致性，當使用從小核心收集的數據進行訓練的時候，但卻可能是使用從大核心收集的輸入統計數據進行預測的。因此，本文將不同類型的指令數轉換為指令比。

2.3.3 模型結構

在本文的ANN網絡的輸入層是由9個神經元組成，用來接收輸入參數。一般來說，隨著神經網絡的隱藏層和隱藏層的節點數的增加可以降低網絡誤差、提高精度，但也會使網絡復雜化，從而增加了網絡的訓練時間和出現“過擬合”的傾向。通過仿真實驗，最終確定了性能預測器所使用的神經網絡模型隱藏層數為27，并且使用作為激活函數。在損失函數和學習率方面，本文選用了最常用的均方誤差（Mean Squared Error，）損失函數來對性能預測器進行訓練，同時通過觀察損失函數和學習率的關系，最終將學習率確定為0.001。

2.4 重映射檢測器

一個程序在其生命周期中可執行數百萬甚至數十億條指令，運行中的行為通常經歷階段變化。在不同的階段，可以觀察到不同的執行特征。因此，不能在每個信息收集階段進行重新映射，而是只會在檢測到某些階段變化時進行重新映射，用以降低重新映射的成本。

在論文中定義一個變化率，當變化超過一定范圍時就會觸發重映射，從而調用后面的線程到核心類型匹配算法，反之本階段將不進行重映射。Δ定義公式如下，

其中，（）是階段的，（1）是1階段的預測。

2.5 線程到核心類型匹配算法

本文的目的是獲得線程到核心的最佳映射，從而充分發揮異構多核平臺的性能優勢。本文所提出的線程到核心類型的匹配算法，以性能預測器所預測的下一階段的各個線程到各種類型核心的值為基礎，來確定線程擬將映射的具體核心類型。從而獲得線程到核心的最優匹配，使得異構多核平臺性能得以充分發揮，總的值達到了最大化。

本文中定義線程在核心類型上的值為（），并且類型核心的數量為。線程與核心類型的綁定表示為。是一個一維向量，其中第個位置的數表示線程映射到類型為的核心上。

線程到核心類型的匹配算法可分為4步：

初始化中的所有線程到核心類型的綁定，使得初始綁定為空（這里設為）。

對于所有類型的核心，根據性能預測器預測所得的值，將對應的線程進行排序。例如對于核心類型，預測所有線程下一階段在此類核心上的值。然后根據預測映射所得的值，為對應的線程進行排序（值越大的線程越靠前），得到序列（_（…，t，…），_，…，_c，…）。

根據每種核心類型的處理能力，對核心類型進行排序，得到_（…c…）。

為了最大限度地提高系統性能，需要優先選擇使用更強大的核心。因此，本算法的核心思想是根據線程處理能力的順序（由_表示）將線程分配給內核。首先依據序列_中核心的順序，依次查看該核心對應的序列中的前｜c｜個線程的分配情況。若當前線程未被分配，將線程分配到當前核心。反之，若已經分配，則將線程映射到所得較大的核心上。映射后獲得的值較小的核心對應的序列上空出的核心位置，由對應的序列第｜c｜開始的第一個未被分配的線程補上。研發得到偽代碼詳見如下。

3 實驗評估

為了評估AbDM的性能，本文基于Sniper模擬器搭建了一個異構多核平臺，用來模擬不同應用在實際運行中的行為。并且，將AbDM與常見的輪詢調度算法（Round Robin Scheduler，RRS）進行對比，用來分析AbDM方法的優勢。

輪詢調度主要是通過交換在大核上執行的線程和在小內核上執行的線程進而實現對性能的優化。之所以選擇輪詢調度進行對比，是因為輪詢調度算法可以在Linux調度程序和公平感知調度程序上為單線程和多線程工作負載提供性能改進。

3.1 實驗設置

實驗使用模擬器Sniper搭建了一個4行4列的異構多核平臺。該平臺由2種處理能力不同的核心組成，這2種核心稱為大核和小核，大核與小核各占兩行，具體如圖2所示。并且本文中的大核和小核的指令集架構均基于Intel Nehalem x86架構，且處理核的主頻均為2.66 GHz，發射寬度均為4，2種類型的處理核具有相同的緩存架構。其中，Cache為256 KB，Cache為512 KB，共享的Cache大小設置為8 MB。大核擁有128的指令窗口大小和長度為48的讀取隊列，而小核的指令窗口大小為16，讀取隊列長度為6。頻率調節的步長為0.2 GHz，對于每個頻率，電壓的設置參照文獻［22］。

圖2 Sniper模擬器布置的16個核心的系統平面圖Fig.2 Floorplan of a 16-core system simulated in Sniper

從基準測試SPLASH-2中選擇了10種不同的應用，并且將這些應用組成不同的分組，將分組內的所有程序在搭建的模擬平臺上并發執行，用來模擬現實世界的程序執行情況。具體的程序組合見表1。

表1 應用程序組合Tab.1 Combination of programs

3.2 實驗結果與分析

為了更好地評估本文提出的方法，實驗分別對性能預測器、應用到核心的匹配算法以及AbDM整體進行評估。從局部和整體兩個方面對本文提出的算法進行仿真測試。

3.2.1 性能預測器的評估

針對2種類型核的16核平臺，實驗中搭建了2種人工神經網絡模型。一種是根據小核的線程執行信息來預測大核的，另一種是根據大核的線程執行信息來預測小核的。根據小核的線程執行信息來預測大核的的模型稱為，根據大核的線程執行信息來預測小核的的模型稱為。2種神經網絡模型都是使用上述的不同應用組合所收集的數據集訓練得到的，數據集的收集周期為30 ms，即每隔30 ms收集一次用以訓練性能預測器的參數的數值。

為了更好地評估AbDM的性能，實驗用10個splash-2基準應用作為和模型評估的測試集。圖3給出了和預測不同應用的誤差。從圖3中可以看出，2個預測模型在應用barnes上均取得最小誤差，同時在應用volread上的效果也最不理想，但是即使在最差情況也僅為031，并且和的平均僅為0.15和0.17。由實驗數據還可以看出，總體上，大核性能預測器和小核性能預測器均具有較好的預測效果。

圖3 預測器誤差Fig.3 MSE of ANN predictor

3.2.2 線程到核心類型匹配算法的評估

本部分通過將線程到核心類型匹配算法與窮舉算法進行比較，來評估算法的性能。具體的比較有2方面。一方面是線程到核心類型匹配所需的時間，另一方面是匹配后所獲得的值。

通過設置不同的線程數、核心類型數以及每種核心的數量，來對比本文提出的線程到核心類型匹配算法與窮舉法的性能。例如表2中，組合1表示的是4個線程運行于擁有2種不同類型核心的異構平臺上，并且2種類型的核心數量都是4個。對于窮舉算法來說，算法考慮了所有線程到核心類型匹配的可能性，故毋庸置疑可知，窮舉算法獲得的值是最大值。接下去，由表3的實驗結果可知，隨著測試配置越來越復雜，窮舉法所耗費的時間增長速度遠遠高于本文提出的方法，并且在配置6的時候，窮舉法沒有時間結果，是由于運行時間超過了0.5 h，為此停止了實驗。在總的值方面，本文提出的方法可以接近于最優值。能夠非常有效地獲得接近最優的解。

表2 異構多核配置Tab.2 Heterogeneous multi-core configuration

表3 本文提出的方法與遍歷法的運行時間Tab.3 Running time of the method proposed in this article vs.the traversal method ms

圖4 AbDM與遍歷法所獲得的IPC對比Fig.4 Comparison of IPC obtained by AbDM vs.IPC obtained by the traversal method

3.2.3 對基于神經網絡的異構多核動態映射方法的評估

為了評估AbDM與現有技術相比的優劣，實驗中使用RR作為基準方法，并對8個應用程序組合進行實驗，以觀察本文提出的方法與RRS比較所實現的加速比。

AbDM和輪詢調度的加速比如圖5所示。圖5中，橫坐標表示不同的程序組合所對應的編號，縱坐標表示本文提出的方法與RR比較所獲得的加速比。從圖5中可以看到，AbDM在所有的8種實驗配置下效果均優于輪詢調度算法，并且平均吞吐量提高了63%。這是因為AbDM考慮到了程序生命周期中的階段性變化，為不同階段的程序選擇適合當前階段的核心類型，從而最大限度地發揮異構多核平臺的性能優勢。另一方面，AbDM執行更少的重映射計算，每隔一個特定的周期進行一次重映射檢測，當且僅當滿足重映射條件是觸發重映射。

圖5 AbDM和輪詢調度的加速比Fig.5 Acceleration ratio of the proposed method and RRS

4 結束語

本文提出了一種基于神經網絡的異構多核動態映射算法。該方法首先根據執行階段不同線程的特點，通過人工神經網絡預測不同類型核上各線程下一階段的值。然后，重映射算法確定是否需要重映射，并在必要時執行重映射算法。反之，若無需重映射，則保持當前映射不變。仿真實驗結果表明本文提出的方法相對于傳統的輪詢算法優勢明顯，平均吞吐量提高了63%。

此外隨著處理核數量的增加，處理器中晶體管密度同步提高，現代多核處理器具有更高的功率密度，進而導致芯片溫度也有同步升高，最終會對系統性能造成一定的負面影響。所以在未來的工作中，會考慮引入一個新的參考因素熱安全。在保證熱安全的前提下，最大化異構多核平臺的性能。