陳耀

摘要：面向移動(dòng)終端的處理器性能評估需要具有代表性的測試程序，本文通過分析安卓應(yīng)用階段性的微架構(gòu)無關(guān)特征，選取能夠代表整個(gè)應(yīng)用的程序片段，為最終生成代表性測試程序提供可靠依據(jù)。本文所提出的微架構(gòu)無關(guān)特征包括指令混合比、關(guān)鍵路徑長度、寄存器傳輸、指令/數(shù)據(jù)的空間局部性/時(shí)間局部性、分支行為、串行指令分布7大類，總計(jì)227個(gè)微架構(gòu)無關(guān)特征維度。同時(shí)在Gem5中加入了特征參數(shù)的統(tǒng)計(jì)代碼，通過基于固定Cycle數(shù)的切割方法，對安卓應(yīng)用進(jìn)行切片，并提取了所有特征片段中的微架構(gòu)無關(guān)參數(shù)以及相應(yīng)的微架構(gòu)相關(guān)參數(shù)。隨后通過降維、聚類的方法從眾多的特征片段中挑選出典型特征片段來代表整個(gè)安卓應(yīng)用執(zhí)行時(shí)的負(fù)載特征。

關(guān)鍵詞：安卓應(yīng)用；微架構(gòu)無關(guān)特征；降維；聚類；典型特征片段

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）14-0214-03

當(dāng)前，對移動(dòng)智能設(shè)備硬件性能的評估已成為業(yè)界以及用戶所關(guān)注的重點(diǎn)。為了得到有意義、可量化比較的性能評估結(jié)果，首先必須確定量化的標(biāo)準(zhǔn)，即需要選擇合適的測試程序?qū)τ布阅苓M(jìn)行評估。當(dāng)前學(xué)界對傳統(tǒng)桌面應(yīng)用程序的研究已經(jīng)較為完善，但針對移動(dòng)智能終端交互式應(yīng)用的研究較為不足。傳統(tǒng)的面向通用處理性能的測試集，如針對計(jì)算機(jī)系統(tǒng)的SPEC測試集以及針對嵌入式系統(tǒng)的MiBench[1]、MediaBench[2]測試集等，在程序的功能以及規(guī)模等方面都與移動(dòng)智能設(shè)備應(yīng)用存在著較大的不同[3]。面向安卓應(yīng)用還沒有像SPEC一樣權(quán)威的測試集。因此，所在課題組提出了如圖1所示的構(gòu)造測試集的過程：

即首先通過對安卓應(yīng)用進(jìn)行負(fù)載特征分析，提取典型特征片段，然后進(jìn)行合成，最終構(gòu)造面向安卓應(yīng)用的測試集。本文的主要工作在于負(fù)載特征分析以及典型特征片段提取。

安卓應(yīng)用的執(zhí)行行為主要由2方面的特征可以描述，其一是與具體運(yùn)行的處理器微架構(gòu)相關(guān)的特征，比如cache缺失率、分支預(yù)測錯(cuò)誤率、TLB缺失率等；其二是與處理器微架構(gòu)無關(guān)的特征，比如指令混合比、寄存器傳輸、指令/數(shù)據(jù)局部性、分支行為以及程序內(nèi)在的指令級并行度等。使用微架構(gòu)相關(guān)負(fù)載特性來比較程序極有可能產(chǎn)生誤導(dǎo)，因?yàn)樵谔囟ㄎ⒓軜?gòu)上得到的負(fù)載特性并不一定等同于在其他微架構(gòu)上得到的負(fù)載特性。微架構(gòu)無關(guān)特征是程序的內(nèi)在特征，與具體的處理器實(shí)現(xiàn)之間沒有必然聯(lián)系。因此，本文基于微架構(gòu)無關(guān)負(fù)載特征對安卓應(yīng)用進(jìn)行典型特征片段的提取。

1 微架構(gòu)無關(guān)負(fù)載特征

當(dāng)前所提出的微架構(gòu)無關(guān)負(fù)載特征幾乎覆蓋了安卓應(yīng)用的所有程序行為特征，主要包括指令混合比、關(guān)鍵路徑長度、寄存器傳輸、指令的空間局部性/時(shí)間局部性、數(shù)據(jù)的空間局部性/時(shí)間局部性、分支行為、串行指令分布7大類，總計(jì)227個(gè)微架構(gòu)無關(guān)特征維度。各特征維度的具體含義如下：

1.1指令混合比

指令混合比表示特定類型的動(dòng)態(tài)執(zhí)行指令占全部動(dòng)態(tài)執(zhí)行指令的比例，基于ARM指令集架構(gòu)特點(diǎn)，本文考慮了六類指令包括寄存器載入指令、寄存器存儲指令、分支指令、整數(shù)指令、浮點(diǎn)指令以及串行指令。

1.2關(guān)鍵路徑長度

關(guān)鍵路徑是指指令窗口中最長的依賴關(guān)系鏈，也就是指令窗口中動(dòng)態(tài)指令流的源寄存器和目的寄存器之間的依賴關(guān)系。

1.3寄存器傳輸

本文使用三類參數(shù)反映寄存器傳輸相關(guān)特性，包括平均寄存器讀取數(shù)、平均寄存器賦值數(shù)、寄存器依賴距離分布，其中依賴距離定義為寄存器賦值操作與讀取該寄存器操作之間的指令數(shù)。

1.4指令的空間局部性及時(shí)間局部性

指令的空間局部性定義為上一條指令地址與當(dāng)前指令地址的差值，指令的時(shí)間局部性定義為兩次獲取相同指令地址之間的指令數(shù)。

1.5數(shù)據(jù)的空間局部性及時(shí)間局部性

數(shù)據(jù)的空間局部性分為全局?jǐn)?shù)據(jù)跨度和局部數(shù)據(jù)跨度。全局?jǐn)?shù)據(jù)跨度是指相鄰的兩次訪存操作中，訪存地址的距離；局部數(shù)據(jù)跨度是指由同一條指令發(fā)起的兩次訪存操作中訪存地址的距離。由于ARM指令中的訪存指令分為Load、Store兩大類，因此空間局部性又分為Load指令、Store指令這兩類來進(jìn)行統(tǒng)計(jì)。

數(shù)據(jù)的時(shí)間局部性定義為兩次訪問相同存儲地址之間的訪存指令數(shù)。類似與數(shù)據(jù)的空間局部性，數(shù)據(jù)的時(shí)間局部性同樣分為全局?jǐn)?shù)據(jù)跨度和局部數(shù)據(jù)跨度。同時(shí)，存儲器操作分為存儲器讀操作和存儲器寫操作，因此同樣需要分為Load指令和Store指令來統(tǒng)計(jì)數(shù)據(jù)的時(shí)間局部性。

1.6 分支行為

本文使用基本塊大小、分支跳轉(zhuǎn)方向、分支跳轉(zhuǎn)比例、分支跳轉(zhuǎn)地址跨度、以及分支跳轉(zhuǎn)變化率來描述分支行為的負(fù)載特征?；緣K大小指的是動(dòng)態(tài)指令流中連續(xù)兩次條件分支指令之間的指令數(shù)。分支跳轉(zhuǎn)方向有兩種，分為前向分支跳轉(zhuǎn)和后向分支跳轉(zhuǎn)。分支跳轉(zhuǎn)比例指的是程序動(dòng)態(tài)指令流中分支發(fā)生跳轉(zhuǎn)的概率。分支跳轉(zhuǎn)地址跨度是指相鄰兩次分支指令之間的跳轉(zhuǎn)地址的差值。分支跳轉(zhuǎn)變化率是指指令從跳轉(zhuǎn)變?yōu)椴惶D(zhuǎn)，或從不跳轉(zhuǎn)變?yōu)樘D(zhuǎn)的頻率。

1.7 串行指令分布

串行指令分布是指動(dòng)態(tài)指令流中連續(xù)兩條串行指令之間的指令數(shù)。

2 特征獲取

2.1 仿真工具

安卓應(yīng)用的微架構(gòu)無關(guān)負(fù)載特征即安卓應(yīng)用程序的動(dòng)態(tài)指令流信息。因此，首先需要以翻譯的方式執(zhí)行安卓應(yīng)用程序，獲取安卓應(yīng)用程序的動(dòng)態(tài)指令流，繼而進(jìn)行相應(yīng)的微架構(gòu)無關(guān)負(fù)載特征分析。對于ARM指令集，當(dāng)前主要有Gem5以及SimpleScalar兩種指令集模擬器能夠以翻譯的方式執(zhí)行安卓應(yīng)用程序的二進(jìn)制代碼。當(dāng)前，Gem5的支持更為完善并且得到了廣泛的應(yīng)用。因此，本論文將基于Gem5，在原有特征參數(shù)統(tǒng)計(jì)的基礎(chǔ)上，增加相應(yīng)的微架構(gòu)無關(guān)負(fù)載特征的統(tǒng)計(jì)模塊，獲取本文所需的安卓應(yīng)用微架構(gòu)無關(guān)負(fù)載特征。

2.2 典型特征片段提取步驟

典型特征片段是指那些能夠代表眾多特征片段的片段。其選取的流程如圖2所示，具體的選取步驟如下：

1）在加入了微架構(gòu)無關(guān)負(fù)載特征統(tǒng)計(jì)代碼的Gem5上以固定Cycle數(shù)運(yùn)行Moby測試集（該測試集是中科院提出的一個(gè)用于硬件體系架構(gòu)研究的移動(dòng)智能終端基準(zhǔn)測試程序集），從應(yīng)用執(zhí)行過程中的動(dòng)態(tài)指令流中獲取應(yīng)用每個(gè)片段的微架構(gòu)無關(guān)負(fù)載特征。

2）由于不同的微架構(gòu)無關(guān)特征參數(shù)具有不同的量綱，因此需要對每個(gè)片段的數(shù)據(jù)做標(biāo)準(zhǔn)化，以免影響到后續(xù)數(shù)據(jù)分析的結(jié)果。

3）提取到的原始特征片段是個(gè)高維數(shù)據(jù)，很多傳統(tǒng)的聚類算法在對高維數(shù)據(jù)做聚類處理時(shí)，往往會(huì)出現(xiàn)維度災(zāi)難[4]。同時(shí)，原始數(shù)據(jù)中不同的微架構(gòu)無關(guān)特征參數(shù)之間存在著一定的相關(guān)性，因此需要對原始特征參數(shù)進(jìn)行降維處理。

4）基于微架構(gòu)無關(guān)特征參數(shù)，通過聚類算法將所有的特征片段分成若干類，每一類中選取離聚類中心最近的特征片段作為典型特征片段。

3 數(shù)據(jù)的獲取與分析

3.1 特征獲取與預(yù)處理

本文以固定Cycle數(shù)（1 千萬個(gè) cycle）作為切割的粒度，將所選取的安卓應(yīng)用程序切分成不同的片段，該操作可以利用Gem5 自帶的命令行選項(xiàng)就可以實(shí)現(xiàn)。然后在Gem5的o3_config.ini配置文件中添加本文所需的特征參數(shù)名稱，并通過修改Gem5原生提供的m5stats2streamline.py數(shù)據(jù)提取工具，對 Gem5 仿真獲得的 stats.txt 文件做第一步數(shù)據(jù)提取工作，獲取本文所需的微架構(gòu)無關(guān)特征參數(shù)以及微架構(gòu)相關(guān)特征參數(shù)。

不同的微架構(gòu)無關(guān)特征參數(shù)具有不同的量綱，比如關(guān)鍵路徑長度和空間局部性這兩類微架構(gòu)無關(guān)特征所對應(yīng)的量綱是不一樣的。為了消除微架構(gòu)無關(guān)特征參數(shù)間的量綱影響，需要對數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理。原始數(shù)據(jù)經(jīng)過標(biāo)準(zhǔn)化處理后，使得各數(shù)據(jù)指標(biāo)處在同一數(shù)量級，適合后續(xù)一系列的降維以及聚類處理。標(biāo)準(zhǔn)化的方法如式（1）所示，其中[X]為原始數(shù)據(jù)中某一個(gè)微架構(gòu)無關(guān)特征參數(shù)，[μ]表示[X]的平均值，[σ]表示[X]的標(biāo)準(zhǔn)差，[X*]是標(biāo)準(zhǔn)化之后的數(shù)據(jù)。

3.2 特征降維

由于本文總共選取了227個(gè)微架構(gòu)無關(guān)特征維度，屬于高維數(shù)據(jù)，而這些高維數(shù)據(jù)通常包含許多冗余[5]， 其本質(zhì)維度往往比原始的數(shù)據(jù)維度要小得多。針對高維數(shù)據(jù)，通常可以采用相關(guān)的降維方法來減少若干并不相關(guān)的數(shù)據(jù)，從而降低高維數(shù)據(jù)的維度。本文所采用的降維方法為主成分分析，該方法是一種經(jīng)典的數(shù)據(jù)統(tǒng)計(jì)分析方法，有兩個(gè)主要功能：①將維度相關(guān)的數(shù)據(jù)集轉(zhuǎn)換為維度互不相關(guān)的數(shù)據(jù)集；②降低數(shù)據(jù)集的維度，而不會(huì)損失太多信息。主成分分析的主要思想是對變量進(jìn)行計(jì)算，得到互不相關(guān)的主成分（每個(gè)主成分是原始變量的線性組合），即將p個(gè)變量轉(zhuǎn)化為p個(gè)主成分，保留p個(gè)主成分中的前q個(gè)，在q[<<]p的情況下可以大大降低數(shù)據(jù)集的維度。一般來說，主成分分析所得到的主成分與原始數(shù)據(jù)間有如下關(guān)系：

1） 每個(gè)主成分都是個(gè)原始特征維度的線性組合。

2） 主成分的數(shù)目遠(yuǎn)遠(yuǎn)小于原始特征維度的數(shù)目。

3） 主成分保留了原始特征維度中絕大多數(shù)的信息量。

4） 各主成分間互不線性相關(guān)。

3.3 特征聚類

對微架構(gòu)無關(guān)負(fù)載特征數(shù)據(jù)集進(jìn)行降維處理以后，本文采用K-means聚類算法對微架構(gòu)無關(guān)參數(shù)進(jìn)行聚類分析，并將聚類后每一類中離聚類中心最近的片段作為最終所選取的典型特征片段。K-means[6]是同類文獻(xiàn)中使用最頻繁的聚類算法，由于K-means算法的執(zhí)行效率較高，因此在對規(guī)模較大的數(shù)據(jù)集進(jìn)行聚類時(shí)被廣泛使用。K-means聚類算法以 k 為參數(shù)，把所有數(shù)據(jù)對象分成 k 個(gè)類，使得類內(nèi)數(shù)據(jù)的相似度較高，而類間數(shù)據(jù)的相似度較低。該算法是一個(gè)迭代過程，其處理過程如下：首先，隨機(jī)的選取 k個(gè)數(shù)據(jù)對象，每個(gè)數(shù)據(jù)對象初始的代表了一個(gè)類的平均值，對于剩下的每個(gè)數(shù)據(jù)對象，計(jì)算該對象與各類中心的距離，并將其賦給與之最近的類，然后重新計(jì)算每個(gè)類的平均值，該過程不斷重復(fù)，直到收斂，即每一個(gè)類中的數(shù)據(jù)對象不再改變或者達(dá)到最大迭代次數(shù)[7]。可以看出，K-means聚類算法產(chǎn)生的是球形聚類，數(shù)據(jù)點(diǎn)分布在聚類中心的周圍。聚類分析得到的聚類有著相似的負(fù)載行為特征。對于特定聚類來說，最接近聚類中心的數(shù)據(jù)點(diǎn)可以代表該聚類，作為相似特征片段的代表性樣例。

4 典型特征片段代表性驗(yàn)證

基于PCA處理后的微架構(gòu)無關(guān)負(fù)載特征，利用K-means算法將Moby中的每一個(gè)應(yīng)用的片段聚成了100類，并選取每一類中離聚類中心最近的片段作為該類的典型特征片段。為了驗(yàn)證所選典型特征片段的代表性，本文計(jì)算了特征片段與應(yīng)用整體的IPC 誤差、L1 I-Cache miss 誤差、L1 D-Cache miss 誤差以及Branch miss 誤差。以IPC誤差為例，其誤差計(jì)算公式如（2）所示。

其中[IPCseli]為聚類后第i類所選典型特征片段的[IPC]值，[ai]為聚類后第i類中的片段數(shù)，即對應(yīng)所選典型特征片段的權(quán)重值，A為應(yīng)用切割后的總片段數(shù)，[IPCtotal]為應(yīng)用整體的[IPC]值。每個(gè)應(yīng)用所選典型特征片段與應(yīng)用整體的各相關(guān)特征的誤差如表1所示。

由表1可知，將每個(gè)應(yīng)用的片段均聚成100類后，所選典型特征片段與多個(gè)安卓應(yīng)用整體的IPC平均誤差為1.29%，L1 I-Cache miss 平均誤差為3.84%，L1 D-Cache miss 平均誤差為3.73%，Branch miss 平均誤差為7.85%，所選典型特征片段與應(yīng)用整體的多個(gè)相關(guān)特征的平均誤差均在10%以內(nèi)。因此，最終所選取的典型特征片段能較好地代表整個(gè)安卓應(yīng)用執(zhí)行時(shí)的負(fù)載特征。

5 結(jié)語

本文基于微架構(gòu)無關(guān)負(fù)載特征參數(shù)提取了安卓應(yīng)用的典型特征片段，且最終所選取的典型特征片段能較好地代表整個(gè)安卓應(yīng)用執(zhí)行時(shí)的負(fù)載特征，但仍有很多地方值得完善。第一，在微架構(gòu)無關(guān)負(fù)載特征的參數(shù)選擇上，還可以根據(jù)新的應(yīng)用場景添加新的參數(shù)，使得微架構(gòu)無關(guān)負(fù)載特征更加完善，更能準(zhǔn)確地量化軟件負(fù)載特征。第二，本文僅針對Moby測試集中的安卓應(yīng)用進(jìn)行了分析與研究，而沒有涉及到其他交互式應(yīng)用，后續(xù)對安卓應(yīng)用場景的選擇需要進(jìn)一步完善。第三，在研究應(yīng)用的階段行為時(shí)，對不同的切割方法需要進(jìn)一步研究，使得切割所得的特征片段更能反映程序階段性的軟件負(fù)載特征。

參考文獻(xiàn)：

[1] Guthaus M R， Ringenberg J S， Ernst D， et al. MiBench： A free， commercially representative embedded benchmark suite [C].Proceedings of the Workload Characterization， 2001 WWC-4 2001 IEEE International Workshop on， IEEE， 2001： 3-14.

[2] Lee C， Potkonjak M， Mangione-Smith W H. MediaBench： a tool for evaluating and synthesizing multimedia and communicatons systems [C].Proceedings of the Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture， IEEE Computer Society， 1997： 330-5.

[3] Gutierrez A， Dreslinski R G， Wenisch T F， et al. Full-system analysis and characterization of interactive smartphone applications [C].Proceedings of the Workload Characterization （IISWC）， 2011 IEEE International Symposium on， IEEE， 2011： 81-90.

[4] 李郁林. 高維數(shù)據(jù)分析中的降維研究[J]. 計(jì)算機(jī)軟件與應(yīng)用，2012，17（3）： 2-5.

[5] 譚維. 數(shù)據(jù)挖掘中聚類集成與半監(jiān)督聚類研究 [D].西南交通大學(xué)， 2010.

[6] 馮超. K-means聚類算法的研究 [D].大連理工大學(xué)， 2007.

[7] 付峰.聚類分析（三）K 中心點(diǎn)算法（k-mediods）[D].西南交通大學(xué)， 2009.