基于半監(jiān)督集成學(xué)習(xí)的多核設(shè)計(jì)空間探索

李丹丹， 姚淑珍,*， 王穎， 王森章， 譚火彬

(1. 北京航空航天大學(xué) 計(jì)算機(jī)學(xué)院， 北京 100083； 2. 中國(guó)科學(xué)院計(jì)算技術(shù)研究所 計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京100190； 3. 南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 南京 211106； 4. 北京航空航天大學(xué) 軟件學(xué)院, 北京 100083)

隨著集成電路工藝的進(jìn)步以及系統(tǒng)結(jié)構(gòu)設(shè)計(jì)的復(fù)雜度不斷提高，特別是隨著多核技術(shù)的發(fā)展，處理器設(shè)計(jì)相關(guān)的參數(shù)變得越來(lái)越多，從而使得處理器的設(shè)計(jì)空間呈指數(shù)式增長(zhǎng); 且處理器的工作負(fù)載通常由大量具有不同特性的應(yīng)用程序組成。為滿足處理器性能、功耗和設(shè)計(jì)成本等方面的要求和限制，系統(tǒng)結(jié)構(gòu)設(shè)計(jì)師面臨著更加嚴(yán)峻的挑戰(zhàn)：從龐大的設(shè)計(jì)空間中尋找滿足約束條件的最優(yōu)參數(shù)組合，即是設(shè)計(jì)空間探索。為解決該問(wèn)題，系統(tǒng)結(jié)構(gòu)設(shè)計(jì)師通常在制造芯片前，利用軟件模擬技術(shù)來(lái)模擬一部分具有代表性的工作負(fù)載來(lái)探索處理器的設(shè)計(jì)空間，進(jìn)而評(píng)估處理器各種參數(shù)組合的性能。然而，周期精準(zhǔn)的模擬器的低速問(wèn)題(比真實(shí)處理器運(yùn)算速度慢了3～5個(gè)數(shù)量級(jí))，使得對(duì)設(shè)計(jì)空間中每種可能的設(shè)計(jì)參數(shù)組合都進(jìn)行模擬是非常耗時(shí)且不可行的。導(dǎo)致的結(jié)果是，設(shè)計(jì)師被迫減少評(píng)估的參數(shù)配置數(shù)量：通常基于設(shè)計(jì)師對(duì)某些參數(shù)相對(duì)重要性的經(jīng)驗(yàn)以及功率預(yù)算等來(lái)確定需要模擬的參數(shù)組合。但此類(lèi)方法有以下缺點(diǎn)：

1) 針對(duì)不同的應(yīng)用程序，微體系結(jié)構(gòu)設(shè)計(jì)參數(shù)對(duì)性能或功耗的影響程度是不同的，因此，設(shè)計(jì)師的經(jīng)驗(yàn)可能是不準(zhǔn)確的。

2) 缺乏統(tǒng)計(jì)的嚴(yán)謹(jǐn)性，得到的結(jié)論可能不正確。

3) 缺乏對(duì)各個(gè)參數(shù)的重要性及意義、參數(shù)之間的相互作用等問(wèn)題的探討。

為了解決以上問(wèn)題，近年來(lái)的相關(guān)的研究主要關(guān)注如下3個(gè)方向：分析模型、快速的模擬技術(shù)和基于機(jī)器學(xué)習(xí)技術(shù)構(gòu)建預(yù)測(cè)模型的方法。理論上，分析模型用來(lái)準(zhǔn)確表征處理器性能和各種微體系結(jié)構(gòu)參數(shù)之間的關(guān)系，能夠消除對(duì)耗時(shí)模擬的需要。然而，現(xiàn)有的處理器性能分析模型技術(shù)基于幾個(gè)簡(jiǎn)化的假設(shè)，僅對(duì)少量的微結(jié)構(gòu)參數(shù)建模[1-2]。并且，分析模型需要大量的專(zhuān)業(yè)領(lǐng)域知識(shí)，不具備通用性。因此，此類(lèi)模型缺乏在處理器設(shè)計(jì)周期使用的準(zhǔn)確性和靈活性。快速的模擬技術(shù)主要通過(guò)減少模擬指令來(lái)加速模擬，比較著名的有SimPoint[3]和SMARTS[4]，能夠極大地加快單個(gè)模擬的速度。這些方法在一定程度上減少了設(shè)計(jì)空間探索中的模擬成本，但設(shè)計(jì)空間中的配置數(shù)量太過(guò)于龐大，僅僅通過(guò)減少單個(gè)配置模擬的時(shí)間非常有限。隨著機(jī)器學(xué)習(xí)技術(shù)的日益發(fā)展以及其在數(shù)據(jù)挖掘、社交網(wǎng)絡(luò)分析等領(lǐng)域[5-6]的廣泛應(yīng)用，近年來(lái)，統(tǒng)計(jì)機(jī)器學(xué)習(xí)算法也被引入到系統(tǒng)結(jié)構(gòu)設(shè)計(jì)領(lǐng)域中[7-20]。首先通過(guò)對(duì)設(shè)計(jì)空間中的一小部分配置進(jìn)行模擬，然后根據(jù)模擬結(jié)果組成訓(xùn)練數(shù)據(jù)集，并構(gòu)建機(jī)器學(xué)習(xí)預(yù)測(cè)模型來(lái)預(yù)測(cè)設(shè)計(jì)空間中未模擬的配置性能或功耗響應(yīng)，從而極大地減少設(shè)計(jì)空間探索中的模擬成本。這種方法取得了較好的實(shí)驗(yàn)結(jié)果，往往和快速模擬技術(shù)SimPoint結(jié)合起來(lái)進(jìn)行設(shè)計(jì)空間探索。例如，Joseph等提出使用線性模型建模處理器性能與微系統(tǒng)結(jié)構(gòu)參數(shù)的關(guān)系[7]。然而，在實(shí)際應(yīng)用中，處理器的響應(yīng)結(jié)果與體系結(jié)構(gòu)設(shè)計(jì)參數(shù)的關(guān)系并非只有簡(jiǎn)單的線性關(guān)系。Joseph等又提出基于徑向基函數(shù)(RBF)的非線性回歸模型預(yù)測(cè)處理器性能[8]。Lee等在線性模型的基礎(chǔ)上，提出了采用樣條函數(shù)來(lái)刻畫(huà)兩者之間的非線性關(guān)系[9-10]。?pek等提出了基于人工神經(jīng)網(wǎng)絡(luò)(Artificial Neural Network, ANN)的預(yù)測(cè)模型[11]。郭崎等提出基于模型樹(shù)的預(yù)測(cè)模型[12]。龐九鳳等提出基于支持向量機(jī)(SVM)的預(yù)測(cè)模型[13]。Palermo等提出結(jié)合實(shí)驗(yàn)設(shè)計(jì)和響應(yīng)面模型技術(shù)來(lái)識(shí)別滿足系統(tǒng)級(jí)約束的Pareto解集合[14]。2015年，Palermo等又提出基于監(jiān)督的高水平分析的譜感知Pareto迭代細(xì)化方法，以尋找設(shè)計(jì)空間中滿足多約束的解集合[15]。針對(duì)單一預(yù)測(cè)模型的預(yù)測(cè)結(jié)果抖動(dòng)的問(wèn)題，郭崎等于2015年提出一種結(jié)合神經(jīng)網(wǎng)絡(luò)模型、SVM和模型樹(shù)3種預(yù)測(cè)模型的元模型，從而提高了預(yù)測(cè)模型的魯棒性[16]。2016年, 考慮到隨機(jī)采樣訓(xùn)練樣本的缺點(diǎn)，Li 等提出基于主動(dòng)學(xué)習(xí)采樣的設(shè)計(jì)空間探索方法[17]。針對(duì)通用處理器的設(shè)計(jì)而言，為了避免對(duì)每個(gè)不同的程序都構(gòu)建一個(gè)預(yù)測(cè)模型， Khan、Dubach和 Li等分別提出交叉應(yīng)用的預(yù)測(cè)模型[18-20]。由于模擬太過(guò)耗時(shí)且設(shè)計(jì)空間過(guò)于龐大，對(duì)于設(shè)計(jì)空間探索來(lái)講，關(guān)鍵是如何利用一個(gè)足夠小的樣本集來(lái)構(gòu)建預(yù)測(cè)模型，準(zhǔn)確學(xué)習(xí)參數(shù)和響應(yīng)之間的關(guān)系。傳統(tǒng)方法多數(shù)都是基于有監(jiān)督學(xué)習(xí)的預(yù)測(cè)模型，通常需要模擬大量的配置來(lái)提高預(yù)測(cè)模型的精度。為了減少模擬成本(次數(shù))，一個(gè)直觀的考慮是基于少量已標(biāo)記的樣本集，標(biāo)記設(shè)計(jì)空間中未模擬(即沒(méi)有標(biāo)記的)的配置(樣本)，從而達(dá)到擴(kuò)充訓(xùn)練數(shù)據(jù)集的目的，進(jìn)而提升預(yù)測(cè)模型的精度。此外，集成學(xué)習(xí)技術(shù)能夠通過(guò)結(jié)合多個(gè)基本預(yù)測(cè)模型，來(lái)提升模型的預(yù)測(cè)精度。因此，本文的目標(biāo)是利用半監(jiān)督學(xué)習(xí)和集成學(xué)習(xí)技術(shù)盡量減少模擬的次數(shù)并保證預(yù)測(cè)模型的精度。

本文首先提出采用集成學(xué)習(xí)算法AdaBoost提升人工神經(jīng)網(wǎng)絡(luò)算法的預(yù)測(cè)精度和魯棒性。然后結(jié)合AdaBoost算法的特點(diǎn)，提出一種基于半監(jiān)督學(xué)習(xí)的AdaBoost(Semi-Supervised Learning based AdaBoost，SSLBoost)模型，利用未標(biāo)記樣本來(lái)擴(kuò)展訓(xùn)練數(shù)據(jù)集，進(jìn)一步提升預(yù)測(cè)模型的精度。最后采用SSLBoost模型對(duì)未模擬配置的性能進(jìn)行預(yù)測(cè)，從而搜索到最佳設(shè)計(jì)參數(shù)組合。

1 基于半監(jiān)督集成學(xué)習(xí)的預(yù)測(cè)模型

本文結(jié)合半監(jiān)督學(xué)習(xí)和集成學(xué)習(xí)技術(shù)，以更少的模擬成本，來(lái)提升設(shè)計(jì)空間模型的精度。采用AdaBoost模型提升ANN的魯棒性和預(yù)測(cè)精度，并在此基礎(chǔ)上，提出一種半監(jiān)督集成學(xué)習(xí)算法。圖1給出了本文提出的設(shè)計(jì)空間探索框架，主要分為2個(gè)階段：訓(xùn)練數(shù)據(jù)集采樣階段和預(yù)測(cè)模型階段。在采樣階段，首先利用基于均勻隨機(jī)采樣方法從處理器設(shè)計(jì)空間中選取一部分設(shè)計(jì)配置(設(shè)計(jì)參數(shù)組合，如核的數(shù)目、Cache大小和發(fā)射寬度等的設(shè)計(jì)結(jié)構(gòu)組合)，利用模擬器進(jìn)行模擬得到相應(yīng)的性能響應(yīng)(執(zhí)行時(shí)間)；然后將這些性能響應(yīng)與設(shè)計(jì)參數(shù)共同組成初始訓(xùn)練數(shù)據(jù)集。在預(yù)測(cè)模型階段，利用第1個(gè)階段的訓(xùn)練數(shù)據(jù)集構(gòu)建基于半監(jiān)督學(xué)習(xí)的AdaBoost模型，迭代地對(duì)未標(biāo)記樣本進(jìn)行標(biāo)記，從而擴(kuò)大訓(xùn)練數(shù)據(jù)集的規(guī)模，更加精確地預(yù)測(cè)設(shè)計(jì)空間中未模擬的設(shè)計(jì)結(jié)構(gòu)的性能。

圖1 基于半監(jiān)督集成學(xué)習(xí)的設(shè)計(jì)空間探索框架Fig.1 Design space exploration framework based on semi-supervised ensemble learning

1.1 AdaBoost.RT模型

考慮到預(yù)測(cè)模型的魯棒性和準(zhǔn)確性，本文采用集成算法AdaBoost中的一個(gè)變種AdaBoost.RT算法[21]構(gòu)建設(shè)計(jì)空間探索的預(yù)測(cè)模型。AdaBoost.RT是Shrestha和Solomatine在2006年提出一種基于回歸問(wèn)題的提升算法[21]，和其他提升算法一致，通過(guò)對(duì)多個(gè)弱學(xué)習(xí)器集成并提升為強(qiáng)的學(xué)習(xí)器。本文采用ANN作為弱學(xué)習(xí)器。

設(shè)L={(x1,y1),(x2,y2),…,(xm,ym)}為訓(xùn)練集，m為模擬配置的數(shù)量，xm為由設(shè)計(jì)空間所有設(shè)計(jì)參數(shù)的取值組成的向量，例如，設(shè)計(jì)參數(shù)有頻率、發(fā)射寬度、核數(shù)目等，x1=(2,6,2,…)就表示x1是一個(gè)頻率大小為2 GHz，發(fā)射寬度為6，核的數(shù)目為2的一個(gè)設(shè)計(jì)配置。yi為模擬相應(yīng)配置的處理器性能響應(yīng)，如常用性能指標(biāo)執(zhí)行時(shí)間。(xi,yi)即配置與模擬的性能組成的向量，在機(jī)器學(xué)習(xí)領(lǐng)域被稱(chēng)為一個(gè)已標(biāo)記樣本，組成的已標(biāo)記樣本集合被稱(chēng)為訓(xùn)練數(shù)據(jù)集。AdaBoost.RT模型迭代地訓(xùn)練多個(gè)弱預(yù)測(cè)器h1,h2,…,hT，這些弱預(yù)測(cè)器的線性組合作為最終的預(yù)測(cè)模型H。算法的初始，弱預(yù)測(cè)器都是由m個(gè)帶相同權(quán)重D1(i)=1/m的樣本訓(xùn)練得到的。ANN弱預(yù)測(cè)器的性能是使用訓(xùn)練數(shù)據(jù)的輸出估計(jì)值和真實(shí)值的相對(duì)誤差來(lái)評(píng)價(jià)的。即ANN的錯(cuò)誤率由一個(gè)預(yù)設(shè)的相對(duì)誤差閾值φ來(lái)計(jì)算的，φ用來(lái)區(qū)分預(yù)測(cè)是正確或錯(cuò)誤的。若一個(gè)配置的相對(duì)誤差(Absolute Relative Error,Et(i))大于閾值φ，那么就認(rèn)為該配置的預(yù)測(cè)響應(yīng)是錯(cuò)誤的，否則就是正確的。錯(cuò)誤預(yù)測(cè)的數(shù)量可以用來(lái)計(jì)算誤差率εt，計(jì)算公式如下：

(1)

(2)

式中：Zt為一個(gè)標(biāo)準(zhǔn)化因子。在T次迭代以后，如式(3)所示，得到最終的回歸模型H，為每個(gè)輸入配置x分配一個(gè)響應(yīng)值H(x)，即預(yù)測(cè)模型對(duì)未模擬配置的性能預(yù)測(cè)值。

(3)

1.2 基于半監(jiān)督學(xué)習(xí)的AdaBoost模型

基于有監(jiān)督學(xué)習(xí)的預(yù)測(cè)模型往往需要模擬大量的配置，才能構(gòu)建出比較精確的預(yù)測(cè)模型，模擬成本較高。為了減少模擬次數(shù)，一個(gè)直觀的考慮是利用已有的、大量未模擬的設(shè)計(jì)配置(也稱(chēng)為未標(biāo)記樣本)來(lái)提高預(yù)測(cè)模型的精度。即采用半監(jiān)督學(xué)習(xí)技術(shù)，根據(jù)少量已經(jīng)標(biāo)記的樣本為基礎(chǔ)，選取置信度較高的未標(biāo)記樣本進(jìn)行“偽”標(biāo)記，來(lái)增加訓(xùn)練數(shù)據(jù)集。

因此，本文提出了SSLBoost模型。其基本思想是結(jié)合半監(jiān)督學(xué)習(xí)和集成學(xué)習(xí)技術(shù)，一方面基于已標(biāo)記訓(xùn)練樣本，利用多個(gè)學(xué)習(xí)器集成地提升為更強(qiáng)的學(xué)習(xí)器，另一方面，通過(guò)自訓(xùn)練(self-training)的半監(jiān)督學(xué)習(xí)技術(shù)利用未標(biāo)記樣本增加訓(xùn)練數(shù)據(jù)集的規(guī)模，進(jìn)一步提升模型的預(yù)測(cè)精度。即將AdaBoost算法引入到半監(jiān)督學(xué)習(xí)的過(guò)程當(dāng)中，通過(guò)多次迭代訓(xùn)練來(lái)提高預(yù)測(cè)模型的精度。

圖2給出了該算法流程圖，首先利用已標(biāo)記樣本集L訓(xùn)練AdaBoost模型；然后從未標(biāo)記樣本集U中隨機(jī)選擇一部分組成未標(biāo)記樣本池P，利用AdaBoost對(duì)未標(biāo)記樣本池P中的樣本進(jìn)行預(yù)測(cè)，根據(jù)AdaBoost中基本學(xué)習(xí)器(ANN)對(duì)樣本的預(yù)測(cè)結(jié)果，對(duì)樣本進(jìn)行置信度評(píng)估，選擇出置信度最高的樣本；利用預(yù)測(cè)結(jié)果對(duì)其標(biāo)記(本文稱(chēng)為“偽”標(biāo)記)，添加到訓(xùn)練數(shù)據(jù)集中，同時(shí)在未標(biāo)記樣本池中刪除該樣本。重復(fù)迭代該過(guò)程，利用未標(biāo)記樣本來(lái)增加訓(xùn)練樣本的數(shù)量，從而提升預(yù)測(cè)模型的精度。

圖2 基于半監(jiān)督學(xué)習(xí)的AdaBoost模型流程圖Fig.2 Flowchart of AdaBoost model based on semi-supervised learning

在半監(jiān)督學(xué)習(xí)技術(shù)中，一個(gè)關(guān)鍵的問(wèn)題就是樣本的置信度評(píng)估，其直接關(guān)系到算法是否選擇出有效的未標(biāo)記樣本，影響算法的預(yù)測(cè)精度[22]。相比半監(jiān)督分類(lèi)學(xué)習(xí)，半監(jiān)督回歸學(xué)習(xí)中的樣本置信度評(píng)估更難。分類(lèi)問(wèn)題中可以通過(guò)比較未標(biāo)記樣本屬于不同類(lèi)別的概率來(lái)評(píng)估，但回歸問(wèn)題的類(lèi)別標(biāo)簽是連續(xù)的實(shí)值，很難找到這樣的估計(jì)概率。而本文的設(shè)計(jì)空間探索模型對(duì)性能的預(yù)測(cè)為回歸問(wèn)題。

本文通過(guò)2個(gè)指標(biāo)對(duì)未標(biāo)記樣本進(jìn)行置信度評(píng)估。①一致性(consistency)指標(biāo)：AdaBoost模型中基本學(xué)習(xí)器預(yù)測(cè)未標(biāo)記樣本分歧越小(即一致性越高)的樣本置信度越高；②誤差下降指標(biāo)：將AdaBoost模型預(yù)測(cè)結(jié)果對(duì)未標(biāo)記樣本進(jìn)行“偽”標(biāo)記，添加到訓(xùn)練樣本集中，更新AdaBoost模型，對(duì)已標(biāo)記樣本集進(jìn)行預(yù)測(cè)，相比沒(méi)有添加該“偽”標(biāo)記樣本時(shí)，使對(duì)已標(biāo)記樣本集的預(yù)測(cè)誤差減小的樣本，置信度越高。也就是說(shuō)，如果多個(gè)基本學(xué)習(xí)器對(duì)一個(gè)未模擬的設(shè)計(jì)配置預(yù)測(cè)得出比較一致、分歧很小的性能結(jié)果，則可以認(rèn)為該配置的預(yù)測(cè)結(jié)果是相對(duì)穩(wěn)定且準(zhǔn)確的。若同時(shí)將該配置加入訓(xùn)練數(shù)據(jù)集中，使得預(yù)測(cè)模型對(duì)已模擬設(shè)計(jì)配置的性能預(yù)測(cè)精度更高，那么該配置就是置信度較高的樣本。

本文采用變異系數(shù)(coefficient of variation)對(duì)未標(biāo)記樣本的一致性進(jìn)行評(píng)估。變異系數(shù)為標(biāo)準(zhǔn)差與平均數(shù)的比值稱(chēng)，記為C，反應(yīng)了數(shù)據(jù)在單位均值上的離散程度。變異系數(shù)值越低，代表設(shè)計(jì)配置的預(yù)測(cè)結(jié)果分歧越小，一致性越高。

算法1給出了SSLBoost算法的偽代碼。該算法的目標(biāo)是迭代地依次擴(kuò)大已標(biāo)記的數(shù)據(jù)集，提升預(yù)測(cè)模型的精度。在訓(xùn)練過(guò)程的每一次迭代，每個(gè)學(xué)習(xí)器預(yù)測(cè)未標(biāo)記樣本池中的樣本，選擇出置信度高的樣本加入到訓(xùn)練數(shù)據(jù)集中。在算法開(kāi)始，由初始訓(xùn)練集初始化AdaBoost.RT模型H。設(shè)h1,h2,…,hT為模型H的T個(gè)ANN，因?yàn)锳daBoost中的每個(gè)ANN對(duì)未模擬的配置樣本預(yù)測(cè)的結(jié)果不同，變異系數(shù)越小代表這T個(gè)ANN對(duì)該樣本的預(yù)測(cè)一致性越高。第i個(gè)未標(biāo)記配置xi的C值由式(4)來(lái)計(jì)算：

(4)

基于AdaBoost中所有ANN對(duì)同一個(gè)未標(biāo)記樣本池中的樣本預(yù)測(cè)，對(duì)能夠達(dá)成比較一致的預(yù)測(cè)結(jié)果的、且能夠使得模型對(duì)已標(biāo)記樣本的預(yù)測(cè)誤差下降的樣本，基本上可以斷定該樣本的預(yù)測(cè)響應(yīng)值是非常接近真實(shí)模擬響應(yīng)值的，則可以省去不必要的模擬，將其添加到訓(xùn)練數(shù)據(jù)集，進(jìn)而提升AdaBoost模型的預(yù)測(cè)精度。

算法1SSLBoost算法

輸入：已標(biāo)記的配置集合L, 所有未模擬的配置集合U。

輸出：未模擬的配置x的預(yù)測(cè)性能值。

創(chuàng)建未標(biāo)記的樣本池P，隨機(jī)從U中選擇p個(gè)未標(biāo)記樣本到P。

利用L訓(xùn)練出AdaBoost.RT模型H。

迭代K次:

1H預(yù)測(cè)P中每一個(gè)未標(biāo)記的配置，對(duì)于每個(gè)未標(biāo)記樣本xi∈P，獲取預(yù)測(cè)結(jié)果hj(xi)。

2 計(jì)算未標(biāo)記樣本池P中每個(gè)未標(biāo)記樣本的變異系數(shù)C，基于C值對(duì)P中樣本升序排序

3 利用模型H預(yù)測(cè)L，記錄百分比誤差eL。

4 forn=1∶p

選擇C值排名為n的樣本xn，將H對(duì)xn的預(yù)測(cè)結(jié)果yn=H(xn)作為“偽”標(biāo)記賦予該樣本(xn,yn)，加入L形成新的集合L′←L∪{(xn,yn)}，更新模型為H′，預(yù)測(cè)L，記錄百分比誤差eL′。

IfeL′

樣本xn是置信度最高的樣本，記錄π←(xn,yn)

跳出循環(huán)；

5 ∥更新L和P

P←P-π;L←L∪π

6 利用新的集合L重新構(gòu)建Adaboost模型H。

7 從U中隨機(jī)挑選出來(lái)的樣本來(lái)補(bǔ)充未標(biāo)記樣本池P，使其大小為p。

8 輸出預(yù)測(cè)結(jié)果H(x)。

2 實(shí)驗(yàn)方法與環(huán)境

2.1 模擬器及基準(zhǔn)測(cè)試程序

本文采用科研領(lǐng)域廣泛使用的周期精準(zhǔn)的模擬器GEM5[23]模擬應(yīng)用程序在多核處理器多種配置之上的性能。由于多核處理器主要關(guān)注并行程序的執(zhí)行性能，因此本文選取了PARSEC(The Princeton Application Repository for Shared-memory Computers)基準(zhǔn)測(cè)試集[24]，一個(gè)多線程應(yīng)用程序組成的測(cè)試程序集。該程序集代表了未來(lái)運(yùn)行在片上多核系統(tǒng)中的共享內(nèi)存應(yīng)用程序的發(fā)展趨勢(shì)。本文從中選取了10個(gè)程序來(lái)對(duì)設(shè)計(jì)空間進(jìn)行評(píng)估，包括blackscholes、bodytrack、canneal、dedup、facesim、ferret、fluidanimate、freqmine、streamcluster和vips等。由于基準(zhǔn)程序中需要模擬的動(dòng)態(tài)指令過(guò)多，本文采用了快速模擬技術(shù)SimPoint來(lái)模擬1億條有代表性的指令，來(lái)節(jié)省每次模擬的模擬時(shí)間。本文采用執(zhí)行時(shí)間作為性能響應(yīng)。

2.2 處理器設(shè)計(jì)空間

表1給出了本文需要探索的多核處理器設(shè)計(jì)空間，涉及了10個(gè)主要與存儲(chǔ)系統(tǒng)密切相關(guān)的設(shè)計(jì)參數(shù)。這些設(shè)計(jì)參數(shù)的不同組合構(gòu)成的設(shè)計(jì)空間包含了超過(guò)419萬(wàn)個(gè)(4 194 304個(gè))不同的設(shè)計(jì)配置。

本文采用均勻隨機(jī)采樣的方法對(duì)設(shè)計(jì)空間分別采集了2 200個(gè)設(shè)計(jì)進(jìn)行模擬，從中隨機(jī)選擇200個(gè)樣本作為訓(xùn)練數(shù)據(jù)集，剩余2 000個(gè)樣本作為測(cè)試數(shù)據(jù)集。本文將構(gòu)建的預(yù)測(cè)模型對(duì)測(cè)試數(shù)據(jù)集進(jìn)行預(yù)測(cè)的誤差作為對(duì)模型準(zhǔn)確性的評(píng)估。

表1 多核設(shè)計(jì)空間

3 模型評(píng)估與比較

3.1 評(píng)估指標(biāo)

3.2 預(yù)測(cè)精度評(píng)估

為了評(píng)估本文所提的基于半監(jiān)督集成學(xué)習(xí)的設(shè)計(jì)空間探索方法對(duì)多核處理器建模的有效性，本文主要針對(duì)以下3個(gè)方面進(jìn)行實(shí)驗(yàn)評(píng)估：①對(duì)SSLBoost模型中的集成學(xué)習(xí)算法AdaBoost的有效性進(jìn)行評(píng)估，通過(guò)與ANN性能進(jìn)行比較，來(lái)驗(yàn)證AdaBoost能否有效提升ANN的性能。②對(duì)SSLBoost模型中半監(jiān)督學(xué)習(xí)算法的有效性進(jìn)行評(píng)估，通過(guò)對(duì)比SSLBoost模型和有監(jiān)督學(xué)習(xí)的AdaBoost模型的性能，來(lái)驗(yàn)證半監(jiān)督學(xué)習(xí)算法的有效性。本文所采用的對(duì)未標(biāo)記樣本進(jìn)行置信度評(píng)估的2個(gè)指標(biāo)，是半監(jiān)督集成學(xué)習(xí)算法的主流成熟技術(shù)，具有廣泛的應(yīng)用[22,25-26]。其中，一致性指標(biāo)能夠保證多個(gè)基本學(xué)習(xí)器ANN對(duì)樣本預(yù)測(cè)的確定性，確定性越高即分歧越小的樣本的預(yù)測(cè)準(zhǔn)確率越高，屬于預(yù)測(cè)器已經(jīng)學(xué)習(xí)到的知識(shí)[22-25]；誤差下降指標(biāo)也是半監(jiān)督學(xué)習(xí)中增加樣本的一個(gè)普遍采用的評(píng)價(jià)指標(biāo)[26]。③將SSLBoost的預(yù)測(cè)結(jié)果與當(dāng)前主流的設(shè)計(jì)空間探索方法進(jìn)行了比較，包括基于ANN[11]和基于SVM[13]的預(yù)測(cè)模型。對(duì)于ANN，本文實(shí)驗(yàn)中的參數(shù)設(shè)置與文獻(xiàn)[11]中的設(shè)置一致，即包含一個(gè)16個(gè)神經(jīng)元的隱含層，learning rate為0.001，而momentum為0.5。對(duì)于SVM，本文采用LIBSVM[27]中所提供的參數(shù)選擇工具來(lái)對(duì)每個(gè)程序分別自動(dòng)搜索最優(yōu)的訓(xùn)練參數(shù)，以得到精確的預(yù)測(cè)模型。本文的SSLBoost模型中的基本學(xué)習(xí)器ANN設(shè)置的是雙隱含層，每層8個(gè)神經(jīng)元，其他參數(shù)設(shè)置與文獻(xiàn)[11]中的一致。ANN基本學(xué)習(xí)器設(shè)為20個(gè)。半監(jiān)督迭代次數(shù)K設(shè)為100，也就是說(shuō)，本文訓(xùn)練樣本集經(jīng)過(guò)半監(jiān)督學(xué)習(xí)后，被擴(kuò)大到300的規(guī)模。鑒于訓(xùn)練樣本集是隨機(jī)采樣的，對(duì)所有方法運(yùn)行10次取預(yù)測(cè)誤差的平均值作為模型的預(yù)測(cè)誤差。

圖3(a)、(b)分別給出了在多核處理器設(shè)計(jì)場(chǎng)景下，上述方法對(duì)于性能的預(yù)測(cè)誤差RMAE和MSE的對(duì)比結(jié)果,Avg為平均值。從圖3可以看出，SSLBoost模型的RMAE分別比SVM、ANN和AdaBoost模型平均降低了7.6%、5.2%和1.5%。尤其是較難預(yù)測(cè)的程序streamcluster，SSLBoost與SVM、ANN和AdaBoost模型相比，RMAE平均降低了14%、10%和4.2%。圖3(b)展示了以ANN的預(yù)測(cè)誤差作為標(biāo)準(zhǔn)，幾種方法經(jīng)過(guò)歸一化處理后的MSE對(duì)比。可以看出，SVM、ANN和AdaBoost模型的MSE平均是SSLBoost模型的4.9倍、3.1倍和1.5倍。

以上實(shí)驗(yàn)結(jié)果表明，在同樣的模擬次數(shù)(200)開(kāi)銷(xiāo)下，本文提出的設(shè)計(jì)空間探索方法可以顯著地提升預(yù)測(cè)模型精度。與ANN相比，有監(jiān)督的AdaBoost算法能夠明顯提升ANN的預(yù)測(cè)精度，并且魯棒性較好，表明了本文所采用的集成學(xué)習(xí)算法的有效性。而SSLBoost模型是結(jié)合了半監(jiān)督學(xué)習(xí)算法的AdaBoost模型，因此SSLBoost模型的預(yù)測(cè)精度高于原始的AdaBoost模型，則表明了本文提出的半監(jiān)督學(xué)習(xí)算法的有效性。SSLBoost不但利用了有標(biāo)記樣本對(duì)單個(gè)樣本精確描述的優(yōu)勢(shì)，而且發(fā)揮了無(wú)標(biāo)記樣本對(duì)訓(xùn)練數(shù)據(jù)集整體描述的重要作用，從而使訓(xùn)練出的模型具有更好的泛化性能，充分體現(xiàn)了半監(jiān)督學(xué)習(xí)的優(yōu)勢(shì)。

為了評(píng)估半監(jiān)督學(xué)習(xí)的迭代過(guò)程中預(yù)測(cè)模型的精度變化，本文以基準(zhǔn)程序vips為例，圖4(a)給出預(yù)測(cè)模型的RMAE隨著迭代過(guò)程的變化；圖4(b)給出將迭代初始的預(yù)測(cè)誤差MSE作為標(biāo)準(zhǔn)進(jìn)行歸一化后，MSE隨著迭代過(guò)程的變化。RMAE基本是隨著迭代次數(shù)的增長(zhǎng)均勻逐漸下降的，MSE在迭代次數(shù)大于10時(shí)，下降幅度較大，之后趨于平緩。由于初始訓(xùn)練樣本集的限制，從未模擬配置中學(xué)習(xí)到的知識(shí)是有限的，當(dāng)逐漸用盡能夠提升預(yù)測(cè)模型精度的優(yōu)秀未標(biāo)記樣本后，再選擇的置信度高的未標(biāo)記樣本，對(duì)于訓(xùn)練數(shù)據(jù)集來(lái)說(shuō)是冗余的。

圖3 在多核設(shè)計(jì)場(chǎng)景下不同方法的預(yù)測(cè)精度對(duì)比Fig.3 Prediction accuracy comparsion of different methods in multicore design scenarios

圖4 多核設(shè)計(jì)場(chǎng)景下SSLBoost模型關(guān)于不同數(shù)量的訓(xùn)練迭代次數(shù)的預(yù)測(cè)精度Fig.4 Prediction accuracy of SSLBoost model with respect to different numbers of training iterations in multicore design scenarios

3.3 模擬次數(shù)

由3.2節(jié)表明，本文提出的SSLBoost模型的預(yù)測(cè)精度在配置模擬次數(shù)相同的情況下優(yōu)于其他2種方法(ANN和SVM)。本節(jié)則評(píng)估ANN、SVM分別需要多少訓(xùn)練模擬樣本才能達(dá)到與SSLBoost模型相同的預(yù)測(cè)精度。

對(duì)于每個(gè)基準(zhǔn)程序，和3.2節(jié)相同，采用200個(gè)均勻隨機(jī)采樣的訓(xùn)練樣本來(lái)構(gòu)建SSLBoost模型、ANN和SVM。從2.2節(jié)提到的2 000個(gè)測(cè)試樣本集中均勻隨機(jī)采樣選出300個(gè)樣本，作為ANN和SVM的備用訓(xùn)練集。為公平起見(jiàn)，剩余的1 700個(gè)樣本作為3種方法的共同測(cè)試樣本集。然后從備用訓(xùn)練數(shù)據(jù)集中隨機(jī)選擇10個(gè)樣本加入到訓(xùn)練數(shù)據(jù)集中，重新構(gòu)建ANN和SVM，檢驗(yàn)ANN和SVM的預(yù)測(cè)精度是否達(dá)到SSLBoost的預(yù)測(cè)精度。重復(fù)這個(gè)過(guò)程，利用10個(gè)樣本作為增長(zhǎng)步長(zhǎng)，直到ANN和SVM達(dá)到與SSLBoost相同的預(yù)測(cè)精度，或者用盡備用訓(xùn)練數(shù)據(jù)集里的樣本。

從表2可以看出，ANN和SVM分別需要191%、228+%的模擬樣本，才能達(dá)到和SSLBoost模型相當(dāng)?shù)念A(yù)測(cè)精度。“+”表示對(duì)于一些基準(zhǔn)程序，ANN或SVM用盡了所有備用訓(xùn)練樣本(300)，還是不能達(dá)到SSLBoost模型的預(yù)測(cè)精度。總之，SSLBoost模型能夠節(jié)省大量的訓(xùn)練模擬。

表2 為達(dá)到SSLBoost模型相同的預(yù)測(cè)精度，ANN和SVM所需要的模擬配置(訓(xùn)練樣本)數(shù)量Table 2 Numbers of simulated configurations (trainingexamples) required by ANN and SVM to achieve thesame level of prediction accuracy as SSLBoost model

3.4 設(shè)計(jì)空間探索時(shí)間

通常來(lái)說(shuō)，模擬108條指令需要10 min以上的模擬的時(shí)間。基于本文的訓(xùn)練數(shù)據(jù)集，SSLBoost的訓(xùn)練時(shí)間從0.5～1 h不等(隨基準(zhǔn)程序變化)。雖然比ANN和SVM的訓(xùn)練開(kāi)銷(xiāo)時(shí)間(秒級(jí))要長(zhǎng)，但是節(jié)省了更多的模擬次數(shù)，即減少了大量的模擬時(shí)間開(kāi)銷(xiāo)。實(shí)際在工業(yè)實(shí)踐中，每個(gè)程序的全部動(dòng)態(tài)指令數(shù)目通常都有數(shù)109、甚至1010條。在這種情況下，SSLBoost模型的訓(xùn)練開(kāi)銷(xiāo)與模擬開(kāi)銷(xiāo)相比基本上可以忽略不計(jì)。因此，3.3節(jié)的模擬次數(shù)比較，也表明了SSLBoost模型能夠極大地減少設(shè)計(jì)空間探索時(shí)間。

3.5 探索更優(yōu)配置

通常來(lái)說(shuō)，除非將整個(gè)設(shè)計(jì)空間中的配置都模擬了，才能找到最優(yōu)的配置，但這是不可行的。一個(gè)折中方案是對(duì)比由SSLBoost模型預(yù)測(cè)出的最優(yōu)配置和由現(xiàn)有設(shè)計(jì)空間探索方法ANN和SVM預(yù)測(cè)的最優(yōu)配置相對(duì)比。具體來(lái)講，從整個(gè)設(shè)計(jì)空間中隨機(jī)采樣3 000個(gè)配置，然后利用這3種方法來(lái)預(yù)測(cè)這3 000個(gè)配置的性能響應(yīng)，從而尋找到其中的最優(yōu)配置。最后模擬3種方法找到的最優(yōu)配置，并直接比較其真實(shí)的模擬性能響應(yīng)。以基準(zhǔn)程序vips為例，表3展示了SSLBoost模型和其他2種模型預(yù)測(cè)的最優(yōu)配置以及預(yù)測(cè)精度(RMAE)。這里ANN、SVM的訓(xùn)練樣本集和SSLBoost模型的初始訓(xùn)練集大小都為200，測(cè)試樣本集合大小為2 000。從表3可以看出，與其他2種方法相比，SSLBoost模型尋找的最優(yōu)配置的性能最好，并且，SSLBoost模型對(duì)該配置預(yù)測(cè)的性能響應(yīng)非常接近這個(gè)配置的真實(shí)模擬性能，僅僅3.5%的預(yù)測(cè)誤差。而其他2個(gè)方法得到的最優(yōu)配置性能都較低，且預(yù)測(cè)精度也較低(誤差為12.9%、23.8%)。因此，在探索更優(yōu)配置方面，SSLBoost模型無(wú)論在準(zhǔn)確性和還是有效性上都優(yōu)于ANN和SVM。

表3 各種模型預(yù)測(cè)的最優(yōu)配置對(duì)比(vips)

4 結(jié) 論

本文提出了一種有效且高效的結(jié)合集成學(xué)習(xí)和半監(jiān)督學(xué)習(xí)算法的多核設(shè)計(jì)空間探索框架。實(shí)驗(yàn)結(jié)果表明：

1) 采用集成學(xué)習(xí)算法AdaBoost模型來(lái)集成ANN的預(yù)測(cè)模型能夠有效地提升ANN的預(yù)測(cè)精度。

2) 半監(jiān)督集成學(xué)習(xí)模型SSLBoost模型利用未標(biāo)記配置來(lái)擴(kuò)充訓(xùn)練樣本集，在相同的模擬代價(jià)下，相比現(xiàn)有的基于ANN和SVM的探索方法，能夠極大地降低模型的預(yù)測(cè)誤差。

3) 相比基于ANN和SVM的方法，SSLBoost模型能夠使用更少的模擬樣本來(lái)達(dá)到相當(dāng)?shù)念A(yù)測(cè)精度。

因此，本文所提出的多核設(shè)計(jì)空間探索方法SSLBoost模型比現(xiàn)有的探索方法更加高效、準(zhǔn)確。

參考文獻(xiàn) (References)

[1] NOONBURG D B,SHEN J P.Theoretical modeling of superscalar processor performance[C]∥Proceeding of International Symposium on Microarchitecture.New York:ACM,1994:52-62.

[2] KARKHANIS T S,SMITH J E.Automated design of application specific superscalar processors:An analytical approach[C]∥Proceedings of the 34th International Symposium on Computer Architecture.New York:ACM,2007:402-411.

[3] HAMERLY G,PERELMAN E,CALDER B.How to use SimPoint to pick simulation points[J].ACM Sigmetrics Performance Evaluation Review,2004,31(4):25-30.

[4] WUNDERLICH R E,WENISCH T F,FALSAFI B,et al.SMARTS:Accelerating microarchitecture simulation via rigorous statistical sampling[C]∥Proceedings of the 30th Annual International Symposium on Computer Architecture.New York:ACM,2003:84-97.

[5] WANG S,HU X,YU P S,et al.MMRate:Inferring multi-aspect diffusion networks with multi-pattern cascades[C]∥ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM,2014:1246-1255.

[6] WANG S,LI Z,CHAO W,et al.Applying adaptive over-sampling technique based on data density and cost-sensitive SVM to imbalanced learning[C]∥ International Symposium on Neural Networks.Piscataway,NJ:IEEE Press,2012:1-8.

[7] JOSEPH P J,VASWANI K,THAZHUTHAVEETIL M J.Construction and use of linear regression models for processor performance analysis[C]∥Proceedings of the 12th International Symposium on High-Performance Computer Architecture.Piscataway,NJ:IEEE Press,2006:99-108.

[8] JOSEPH P J,VASWANI K,THAZHUTHAVEETIL M J.A predictive performance model for superscalar processors[C]∥Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture.Piscataway,NJ:IEEE Press,2006:161-170.

[9] LEE B C,BROOKS D M.Accurate and efficient regression modeling for microarchitectural performance and power prediction[C]∥ Proceedings of 12th International Conference on Architectural Support for Programming Language and Operating Systems.New York:ACM,2006:185-194.

[10] LEE B C,COLLINS J,WANG H,et al.CPR:Composable performance regression for scalable multiprocessor models[C]∥ Proceedings of the 41 st Annual IEEE/ACM International Symposium on Microarchitecture.Piscataway,NJ:IEEE Press,2008:270-281.

[11] ?PEK E,MCKEE S A,CARUANA R,et al.Efficiently exploring architectural design spaces via predictive modeling[C]∥Proceedings of 12th International Conference on Architectural Support for Programming Language and Operating Systems.New York:ACM,2006:195-206.

[12] 郭崎,陳天石,陳云霽.基于模型樹(shù)的多核設(shè)計(jì)空間探索技術(shù)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2012,24(6):710-720.

GUO Q,CHEN T S,CHEN Y J.Model tree based multi-core design space exploration[J].Journal of Computer-Aided Design & Computer Graphics,2012,24(6):710-720(in Chinese).

[13] PANG J F,LI X F,XIE J S,et al.Microarchitectural design space exploration via support vector machine[J].Acta Scientiarum Naturalium Universitatis Pekinensis,2010,46(1):55-63.

[14] PALERMO G,SILVANO C,ZACCARIA V.ReSPIR:A response surface-based Pareto iterative refinement for application-specific design space exploration[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2009,28(12):1816-1829.

[15] XYDIS S,PALERMO G,ZACCARIA V,et al.SPIRIT:Spectral-aware Pareto iterative refinement optimization for supervised high-level synthesis[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2015,34(1):155-159.

[16] GUO Q,CHEN T,ZHOU Z H,et al.Robust design space modeling[J].ACM Transactions on Design Automation of Electronic Systems,2015:20(2):18.

[17] LI D,YAO S,LIU Y H,et al.Efficient design space exploration via statistical sampling and AdaBoost learning[C]∥Design Automation Conference.New York:ACM,2016:1-6.

[18] KHAN S,XEKALAKIS P,CAVAZOS J,et al.Using predictivemodeling for cross-program design space exploration in multicore systems[C]∥Proceedings of the 22nd International Conference on Parallel Architectures and Compilation Techniques.Piscataway,NJ:IEEE Press,2007:327-338.

[19] DUBACH C,JONES T,OBOYLE M.Microarchitectural design space exploration using an architecture-centric approach[C]∥Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture.Piscataway,NJ:IEEE Press,2007:262-271.

[20] LI D,WANG S,YAO S,et al.Efficient design space exploration by knowledge transfer[C]∥Eleventh IEEE/ACM/IFIP International Conference on Hardware/software Codesign and System Synthesis.New York:ACM,2016:1-10.

[21] SHRESTHA D L,SOLOMATINE D P.Experiments with AdaBoost.RT,an improved boosting scheme for regression[J].Neural Computation,2006,18(7):1678-1710.

[22] ZHOU Z H,LI M.Semi-supervised learning by disagreement[J].Knowledge and Information Systems,2010,24(3):415-439.

[23] BINKERT N,BECKMANN B,BLACK G,et al.The gem5 simulator[J].ACM SIGARCH Computer Architecture News,2011,39(2):1-7.

[24] BIENIA C,KUMAR S,SINGH J P,et al.The PARSEC benchmark suite:Characterization and architectural implications[C]∥Proceedings of the 17th International Conference on Parallel Architecture and Compilation Techniques.New York:ACM,2008:72-81.

[25] HAMED V,RONG J,ANIL K.Semi-supervised boosting for multi-class classification[C]∥European Conference on Principles of Data Mining and Knowledge Discovery,2008:522-537.

[26] ZHOU Z H,LI M.Semi-supervised regression with co-training[C]∥Proceedings of the 19th International Joint Conference on Artificial Intelligence.New York:ACM,2005:908-913.

[27] CHANG C C,LIN C J.LIBSVM:A library for support vector machines[J].ACM Transactions on Intelligent Systems and Technology,2011,2(3):27-1-27-27.