陳耀

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

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

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

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

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

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

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

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

1.1指令混合比

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

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

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

1.3寄存器傳輸

本文使用三類(lèi)參數(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指令中的訪存指令分為L(zhǎng)oad、Store兩大類(lèi)，因此空間局部性又分為L(zhǎng)oad指令、Store指令這兩類(lèi)來(lái)進(jìn)行統(tǒng)計(jì)。

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

1.6 分支行為

本文使用基本塊大小、分支跳轉(zhuǎn)方向、分支跳轉(zhuǎn)比例、分支跳轉(zhuǎn)地址跨度、以及分支跳轉(zhuǎn)變化率來(lái)描述分支行為的負(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)無(wú)關(guān)負(fù)載特征即安卓應(yīng)用程序的動(dòng)態(tài)指令流信息。因此，首先需要以翻譯的方式執(zhí)行安卓應(yīng)用程序，獲取安卓應(yīng)用程序的動(dòng)態(tài)指令流，繼而進(jìn)行相應(yīng)的微架構(gòu)無(wú)關(guān)負(fù)載特征分析。對(duì)于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)無(wú)關(guān)負(fù)載特征的統(tǒng)計(jì)模塊，獲取本文所需的安卓應(yīng)用微架構(gòu)無(wú)關(guān)負(fù)載特征。

2.2 典型特征片段提取步驟

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

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

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

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

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

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

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

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

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

3.2 特征降維

由于本文總共選取了227個(gè)微架構(gòu)無(wú)關(guān)特征維度，屬于高維數(shù)據(jù)，而這些高維數(shù)據(jù)通常包含許多冗余[5]， 其本質(zhì)維度往往比原始的數(shù)據(jù)維度要小得多。針對(duì)高維數(shù)據(jù)，通?？梢圆捎孟嚓P(guān)的降維方法來(lái)減少若干并不相關(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ì)損失太多信息。主成分分析的主要思想是對(duì)變量進(jìn)行計(jì)算，得到互不相關(guān)的主成分（每個(gè)主成分是原始變量的線性組合），即將p個(gè)變量轉(zhuǎn)化為p個(gè)主成分，保留p個(gè)主成分中的前q個(gè)，在q[<<]p的情況下可以大大降低數(shù)據(jù)集的維度。一般來(lái)說(shuō)，主成分分析所得到的主成分與原始數(shù)據(jù)間有如下關(guān)系：

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

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

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

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

3.3 特征聚類(lèi)

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

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

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

其中[IPCseli]為聚類(lèi)后第i類(lèi)所選典型特征片段的[IPC]值，[ai]為聚類(lèi)后第i類(lèi)中的片段數(shù)，即對(duì)應(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類(lèi)后，所選典型特征片段與多個(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é)語(yǔ)

本文基于微架構(gòu)無(wú)關(guān)負(fù)載特征參數(shù)提取了安卓應(yīng)用的典型特征片段，且最終所選取的典型特征片段能較好地代表整個(gè)安卓應(yīng)用執(zhí)行時(shí)的負(fù)載特征，但仍有很多地方值得完善。第一，在微架構(gòu)無(wú)關(guān)負(fù)載特征的參數(shù)選擇上，還可以根據(jù)新的應(yīng)用場(chǎng)景添加新的參數(shù)，使得微架構(gòu)無(wú)關(guān)負(fù)載特征更加完善，更能準(zhǔn)確地量化軟件負(fù)載特征。第二，本文僅針對(duì)Moby測(cè)試集中的安卓應(yīng)用進(jìn)行了分析與研究，而沒(méi)有涉及到其他交互式應(yīng)用，后續(xù)對(duì)安卓應(yīng)用場(chǎng)景的選擇需要進(jìn)一步完善。第三，在研究應(yīng)用的階段行為時(shí)，對(duì)不同的切割方法需要進(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ù)挖掘中聚類(lèi)集成與半監(jiān)督聚類(lèi)研究 [D].西南交通大學(xué)， 2010.

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

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