林新華 王 杰 王一超 左思成

(上海交通大學(xué)高性能計(jì)算中心 上海 200240)

處理器硬件性能計(jì)數(shù)器(processor hardware performance counters)是一組專用寄存器.在代碼執(zhí)行期間，這些計(jì)數(shù)器會(huì)記錄相關(guān)處理器硬件事件(processor hardware events)的發(fā)生次數(shù).在高性能計(jì)算(high performance computing, HPC)領(lǐng)域，硬件性能計(jì)數(shù)器被廣泛用于性能監(jiān)測(cè)與分析工具，譬如PAPI[1]，HPCTOOLKIT[2]，Intel VTune[3].使用者通過統(tǒng)計(jì)硬件事件發(fā)生次數(shù)，生成各種性能指標(biāo)，分析程序在處理器上遇到的性能瓶頸[4-6].

當(dāng)前主流處理器雖然能支持幾百種不同硬件事件，但受限于硬件性能計(jì)數(shù)器數(shù)量(通常6～12個(gè))，同一時(shí)刻能記錄的硬件事件極為有限.但在實(shí)踐中，程序開發(fā)者往往需要同時(shí)監(jiān)測(cè)盡可能多的硬件事件，才能更好地對(duì)程序性能進(jìn)行分析與建模[7-8].為緩解這一矛盾，硬件性能計(jì)數(shù)器復(fù)用技術(shù)(multiplexing, MPX)通過分時(shí)復(fù)用策略，估計(jì)未記錄的事件，從而實(shí)現(xiàn)利用少量硬件性能計(jì)數(shù)器記錄大量硬件事件.

MPX的核心是對(duì)未記錄事件進(jìn)行估計(jì)的算法.已有MPX估計(jì)算法[9-12]都是基于時(shí)間局部性假設(shè)：在2個(gè)相鄰被記錄下的數(shù)據(jù)之間，未被記錄的數(shù)據(jù)與前后數(shù)據(jù)存在緊耦合關(guān)系.此類算法利用不同插值函數(shù)，擬合未被記錄的事件次數(shù).然而，硬件事件的發(fā)生過程是一個(gè)與處理器微架構(gòu)以及應(yīng)用程序密切相關(guān)的復(fù)雜過程[10,13-14]，因此不存在某種特定插值方法可以適用所有場(chǎng)景.這導(dǎo)致基于時(shí)間局部性假設(shè)的估計(jì)算法存在不同程度的準(zhǔn)確率低下的問題.另外，硬件事件發(fā)生次數(shù)并不適用于某個(gè)特定的隨機(jī)過程.因此如何從硬件事件發(fā)生的隨機(jī)分布角度出發(fā)，設(shè)計(jì)出更加普適的估計(jì)算法是當(dāng)前MPX研究的最重要挑戰(zhàn)之一.

為應(yīng)對(duì)估計(jì)精度不高的挑戰(zhàn)，我們提出一種基于數(shù)據(jù)分布一致性的估計(jì)算法：輪廓線估計(jì)法(outline estimation, OLE).具體地，本文貢獻(xiàn)有3個(gè)方面：

1) 通過柯爾莫戈洛夫-斯米諾夫正態(tài)性檢驗(yàn)(Kolmogorov-Smirnov, KS)[15]，我們發(fā)現(xiàn)針對(duì)同一硬件事件，同一代碼在單計(jì)數(shù)器記錄單事件(one counter one event, OCOE)模式與MPX模式下，存在數(shù)據(jù)分布一致性規(guī)律；

2) 基于此規(guī)律，我們提出輪廓線估計(jì)法OLE，通過逆向累積分布實(shí)現(xiàn)估計(jì)插值；

3) 我們?cè)陂_源MPX庫(kù)NeoMPX[16]中實(shí)現(xiàn)OLE，并在主流X86和ARM處理器上進(jìn)行驗(yàn)證.實(shí)驗(yàn)結(jié)果表明，在對(duì)16個(gè)硬件事件同時(shí)進(jìn)行記錄時(shí)，OLE算法相比PAPI默認(rèn)的MPX估計(jì)算法[9]，結(jié)果準(zhǔn)確率平均提高了10.5%左右，最多可提升46.6%；相比DIRA/TAM算法[10-11]和DCAM/CAM算法[12]，結(jié)果準(zhǔn)確率分別提升了18.8%和17.7%.

1 相關(guān)工作

目前已有的MPX估計(jì)算法主要有4種：

1) PAPI[1]默認(rèn)使用的MPX估計(jì)算法是由May[9]提出的固定值插值算法.該算法利用前一個(gè)記錄下的數(shù)據(jù)值作為固定值，插入到2次記錄的數(shù)據(jù)之間.該算法是第1個(gè)基于時(shí)間局部性假設(shè)的MPX估計(jì)算法.

2) Mathur等人[10-11]量化了由MPX引起的誤差，并提出了4種新的插值估計(jì)算法，其中梯形面積法(trapezoid-area method, TAM)和分隔矩形面積法(divided-interval rectangular area, DIRA)不需要預(yù)先計(jì)算，引入額外開銷最低，相比May[9]的算法，結(jié)果準(zhǔn)確度最高能提升32%左右.

3) Mytkowicz等人[13]率先提出動(dòng)態(tài)時(shí)間規(guī)整(dynamic time warping, DTW)算法，對(duì)MPX生成的硬件事件時(shí)間序列進(jìn)行分析.Lü等人[17]借鑒DTW算法，發(fā)現(xiàn)MPX事件序列中異常值是導(dǎo)致準(zhǔn)確度下降的主因，因此設(shè)計(jì)了一個(gè)針對(duì)結(jié)果后處理的數(shù)據(jù)清洗器，用來消除異常值，并填充缺失值.

4) Wang等人[12]進(jìn)一步闡明了Lü等人[17]未解釋清楚的異常值原因，并基于Mathur等人[10-11]的工作，提出了2種新的MPX估計(jì)算法：曲面面積法(curved-area method, CAM)和分隔曲面面積法(divided curved-area method, DCAM).

上述4種估計(jì)算法都基于時(shí)間局部性假設(shè).該假設(shè)認(rèn)為在時(shí)間相鄰的事件之間存在數(shù)據(jù)相關(guān)性，即臨近計(jì)數(shù)值存在某種函數(shù)關(guān)系.然而，通過觀察連續(xù)時(shí)間內(nèi)不同時(shí)間片的硬件事件數(shù)值，我們發(fā)現(xiàn)相鄰時(shí)間片間的記錄值并沒有遵循某種規(guī)律.反而，同一個(gè)程序運(yùn)行時(shí)的不同硬件事件在數(shù)據(jù)分布上存在一致性規(guī)律.因此我們提出了基于數(shù)據(jù)分布一致性規(guī)律的估計(jì)算法，該算法相比基于時(shí)間局部性假設(shè)的算法更能貼近硬件事件發(fā)生的真實(shí)情況.

2 研究背景與研究動(dòng)機(jī)

2.1 處理器硬件事件的記錄模式

處理器硬件事件是對(duì)應(yīng)用程序進(jìn)行性能分析與建模的重要指標(biāo)，譬如每周期執(zhí)行的指令數(shù)(instr-uction per cycle, IPC)、浮點(diǎn)運(yùn)算執(zhí)行的指令數(shù)、緩存訪問失效率等.這些重要指標(biāo)可以反映應(yīng)用程序運(yùn)行時(shí)，處理器微架構(gòu)層次上不同模塊的實(shí)際性能，例如IPC對(duì)應(yīng)處理器的指令吞吐量；緩存訪問失效率對(duì)應(yīng)程序的數(shù)據(jù)局部性.

本文選取PAPI[18]作為研究平臺(tái)，這是HPC領(lǐng)域最具影響力的開源性能分析工具之一.PAPI提供2種記錄硬件事件的模式：?jiǎn)蝹€(gè)計(jì)數(shù)器記錄單個(gè)事件的OCOE模式與多個(gè)計(jì)數(shù)器同時(shí)記錄多個(gè)事件的MPX模式.

OCOE模式是指每個(gè)硬件計(jì)數(shù)器在程序運(yùn)行期間只針對(duì)一個(gè)硬件事件進(jìn)行計(jì)數(shù).OCOE模式的優(yōu)勢(shì)是計(jì)數(shù)結(jié)果準(zhǔn)確，因此本文將OCOE 模式的計(jì)數(shù)結(jié)果作為評(píng)估結(jié)果準(zhǔn)確率的基準(zhǔn)；OCOE模式的局限是每次能記錄的事件數(shù)量受限于硬件計(jì)數(shù)器的數(shù)量，例如Intel Cascade Lake處理器可用計(jì)數(shù)器僅為8個(gè).在OCOE模式下，要記錄48個(gè)硬件事件需重復(fù)運(yùn)行6次程序，每次運(yùn)行記錄8個(gè)不同事件.

2.2 MPX模式的原理

MPX模式采用分時(shí)復(fù)用[9]的方法，將各個(gè)硬件計(jì)數(shù)器的可用時(shí)間切分成不同的時(shí)間片，然后在不同的時(shí)間片上輪流記錄不同的硬件事件.在MPX模式下，硬件性能計(jì)數(shù)器在多事件調(diào)度過程中，存在部分事件發(fā)生次數(shù)未被計(jì)數(shù)器記錄的情況.此時(shí)估計(jì)算法將估算該時(shí)間段內(nèi)硬件事件的發(fā)生次數(shù)，補(bǔ)全未被記錄的數(shù)據(jù).

因此，MPX主要有2個(gè)步驟組成：

1) 時(shí)間片調(diào)度.由于MPX模式基于分時(shí)復(fù)用，不同的硬件事件會(huì)輪流在硬件計(jì)數(shù)器上記錄，其調(diào)度需要通過操作系統(tǒng)的內(nèi)部計(jì)時(shí)器和信號(hào)處理功能實(shí)現(xiàn).

2) 算法估計(jì).由于時(shí)間片調(diào)度過程中部分硬件事件未被記錄，因此需要使用估計(jì)算法通過已記錄的事件數(shù)據(jù)，估算出未被記錄的事件數(shù)據(jù).目前已有算法都是使用插值法對(duì)該事件未被記錄的時(shí)間片進(jìn)行估算填充.以PAPI默認(rèn)的MPX估計(jì)算法[9]為例，該算法使用最近一次記錄的事件數(shù)值進(jìn)行插值填充，以補(bǔ)全未記錄事件數(shù)的時(shí)間片.如圖1所示，在事件A未被調(diào)度的時(shí)間片內(nèi)，若事件A的實(shí)際發(fā)生率小于默認(rèn)算法的估計(jì)值，則事件A的估計(jì)值會(huì)明顯高于實(shí)際值；反之，若事件A的實(shí)際發(fā)生率大于默認(rèn)算法的估計(jì)值，則事件A的估計(jì)值會(huì)明顯低于實(shí)際值.對(duì)于上述2種情況，PAPI默認(rèn)的MPX估計(jì)算法無法進(jìn)行調(diào)整，因此會(huì)引入誤差較大的異常值.這正是MPX異常值的主要來源之一[12,17].

Fig. 1 Default MPX estimation algorithm in PAPI[9]圖1 PAPI默認(rèn)的MPX估計(jì)算法[9]

2.3 基于時(shí)間局部性假設(shè)的MPX估計(jì)算法

已有MPX估計(jì)算法都是基于時(shí)間局部性假設(shè).這種假設(shè)是基于代碼執(zhí)行的局部性原理，認(rèn)為在局部的時(shí)間片上處理器運(yùn)行相同代碼片段時(shí)，在時(shí)間上相近的硬件事件記錄值會(huì)相近或是遵循統(tǒng)一的變化趨勢(shì)，從而導(dǎo)致硬件事件的相鄰記錄點(diǎn)之間存在某種數(shù)據(jù)相關(guān)性.

這種數(shù)據(jù)相關(guān)性的具體體現(xiàn)是相鄰記錄點(diǎn)之間存在某種函數(shù)關(guān)系.譬如PAPI默認(rèn)的MPX估計(jì)算法[9]假設(shè)相鄰記錄點(diǎn)之間的計(jì)數(shù)值相同，因此就直接采用臨近記錄點(diǎn)的計(jì)數(shù)值作為預(yù)測(cè)結(jié)果來填補(bǔ)未記錄時(shí)段的計(jì)數(shù)值.但這種等值預(yù)測(cè)的估計(jì)方式誤差較大，因此Mathur等人[10-11]提出了基于線性增長(zhǎng)方式的算法，而Wang等人[12]則進(jìn)一步提出了基于指數(shù)增長(zhǎng)方式的CAM和DCAM算法.如圖2所示，DCAM算法對(duì)于2個(gè)記錄點(diǎn)之間的硬件事件發(fā)生次數(shù)，以曲線函數(shù)中常用的指數(shù)函數(shù)進(jìn)行遞增插值.與線性增長(zhǎng)插值算法[10-11]相比，DCAM更符合硬件事件發(fā)生時(shí)的非線性規(guī)律，但仍遵循單一變化率趨勢(shì)進(jìn)行插值，具有一定的局限性[12].

Fig. 2 DCAM estimation algorithm[12]圖2 DCAM估計(jì)算法[12]

3 MPX估計(jì)算法設(shè)計(jì)

我們首先對(duì)MPX模式下硬件事件的數(shù)據(jù)分布進(jìn)行分析，然后受KS檢驗(yàn)[15]啟發(fā)提出基于數(shù)據(jù)分布一致性的MPX估計(jì)算法.

算法相關(guān)變量的定義：

Δcountraw=MPX和OCOE采集數(shù)據(jù)之間的差值；

Tend=程序運(yùn)行總時(shí)間序列數(shù)據(jù)；

Trun=記錄總時(shí)間序列數(shù)據(jù)；

Inci=2次記錄數(shù)值之間的變化梯度.

3.1 MPX數(shù)據(jù)分布呈現(xiàn)一致性規(guī)律

通過觀察連續(xù)時(shí)間內(nèi)不同時(shí)間片的硬件事件記錄值，我們發(fā)現(xiàn)相鄰時(shí)間片的記錄值并不遵循時(shí)間局部性假設(shè)(見2.3節(jié)).經(jīng)分析，原因?yàn)椋嚎紤]硬件事件計(jì)數(shù)器的記錄時(shí)延、線程調(diào)度等多種因素影響，并結(jié)合我們的測(cè)試數(shù)據(jù)，推測(cè)PAPI的計(jì)時(shí)誤差應(yīng)該在1 ms左右，因此將PAPI的記錄時(shí)間片設(shè)置為10 ms以上才能獲得較為準(zhǔn)確的記錄數(shù)據(jù).而結(jié)合現(xiàn)代處理器的頻率和指令集設(shè)計(jì)可知，單個(gè)時(shí)間片內(nèi)可運(yùn)行的指令數(shù)在百萬數(shù)量級(jí)，即使換算成高級(jí)語言也很難確保局部時(shí)間片上處理器運(yùn)行了相似代碼片段.因此實(shí)踐中，時(shí)間局部性假設(shè)不成立.

我們對(duì)MPX模式下采集到的數(shù)據(jù)與OCOE模式下采集到的數(shù)據(jù)進(jìn)行KS檢驗(yàn)，分2步：1)對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，將采集到的Δcountraw進(jìn)行排序，得到由小到大的Δcountraw序列數(shù)據(jù)；2)通過對(duì)比2組數(shù)據(jù)之間的累計(jì)分布函數(shù)，檢驗(yàn)數(shù)據(jù)分布一致性.我們從Rodinia基準(zhǔn)測(cè)試集[19]的6個(gè)測(cè)試程序中，針對(duì)16個(gè)硬件事件進(jìn)行KS檢驗(yàn)，結(jié)果顯示平均的D值為0.10，最小值為0.06，平均的P值為0.90，最大值為0.95.該結(jié)果表明針對(duì)同一硬件事件，相同代碼在OCOE和MPX這2種模式下數(shù)據(jù)分布呈一致性.以HeartWall測(cè)試程序?yàn)槔瑘D3為硬件事件dtlm:m在這2種模式下的累積分布圖，2種模式下的數(shù)據(jù)在不同時(shí)刻的總體分布呈現(xiàn)高度相似.

Fig. 3 Cumulative distribution of the dtlm:m event with OCOE and MPX modes in HeartWall圖3 HeartWall中事件dtlm:m在OCOE和MPX 2種模式下的累積分布圖

3.2 基于數(shù)據(jù)分布一致性的MPX估計(jì)算法

根據(jù)MPX數(shù)據(jù)分布呈現(xiàn)一致性規(guī)律，我們提出一種全新的MPX估計(jì)算法：輪廓線估計(jì)法(OLE).該算法包括數(shù)據(jù)預(yù)處理和基于輪廓線插值2個(gè)步驟.

1) 數(shù)據(jù)預(yù)處理.為保證在增加估計(jì)插入值后的序列數(shù)據(jù)與插入前的序列數(shù)據(jù)相比仍能保持分布一致性，我們對(duì)排序后的Δcountraw數(shù)據(jù)序列中的每個(gè)數(shù)據(jù)做編號(hào)處理.這些編號(hào)不是連續(xù)的，而是在2個(gè)連續(xù)序列數(shù)據(jù)的編號(hào)中空缺一定比例的編號(hào)，并且空缺的比例在整個(gè)編號(hào)序列中是均勻的.空缺的比例可由Tend和Trun計(jì)算得到.

具體來說，為每個(gè)Δcountraw序列數(shù)據(jù)設(shè)置編號(hào)的策略為：為保持增加估計(jì)計(jì)數(shù)值后的序列數(shù)據(jù)與原始序列數(shù)據(jù)分布一致，我們按照Inci=Tend/Trun對(duì)編號(hào)做了等比例的縮放.我們分別對(duì)Inci的整數(shù)部分和小數(shù)部分做累計(jì)，整數(shù)部分或小數(shù)部分每加1，則空出1個(gè)序列號(hào)以備后續(xù)作為估計(jì)計(jì)數(shù)值的編號(hào)，并將開頭的編號(hào)作為當(dāng)前原始序列計(jì)數(shù)值的編號(hào).在實(shí)現(xiàn)中，為防止估計(jì)值整體偏大，我們對(duì)小數(shù)部分累計(jì)值采取滿0.5加1、滿1置0的策略.預(yù)處理步驟的完整描述如算法1所示：

算法1.數(shù)據(jù)預(yù)處理的算法.

輸入：硬件事件A的程序運(yùn)行總時(shí)間序列數(shù)據(jù)Tend與記錄總時(shí)間序列數(shù)據(jù)Trun的比值P；

輸出：原始序列計(jì)數(shù)值編號(hào)S1、估計(jì)序列計(jì)數(shù)值編號(hào)S2.

過程：SeqNum(P)

①c←0,F←0;

② forpinPdo

③c←c+1;

④S1.append(c);

⑤i←int(p);

⑥F←F+p-i;

⑦ ifF>0.5

⑧c←c+1,S2.append(c);

⑨ end if

⑩ end for

2) 基于輪廓線插值.在獲得原始計(jì)數(shù)值序列及其編號(hào)序列對(duì)后，我們利用2層神經(jīng)網(wǎng)絡(luò)對(duì)序列對(duì)做擬合操作，使神經(jīng)網(wǎng)絡(luò)擬合出一個(gè)平滑的排序外輪廓線.選擇2層神經(jīng)網(wǎng)絡(luò)擬合是因?yàn)楦鶕?jù)萬能近似定理，2層神經(jīng)網(wǎng)絡(luò)可以擬合任意函數(shù).這個(gè)輪廓線上所有數(shù)據(jù)組成的數(shù)據(jù)序列的數(shù)據(jù)分布與原始序列數(shù)據(jù)的數(shù)據(jù)分布是一致的.最后將獲得的估計(jì)計(jì)數(shù)值編號(hào)代入輪廓線函數(shù)中，從而獲得估計(jì)計(jì)數(shù)值序列數(shù)據(jù).基于輪廓線插值步驟的完整描述如算法2所示：

算法2.基于輪廓線插值的算法.

輸入：硬件事件A的程序運(yùn)行總時(shí)間序列數(shù)據(jù)、記錄總時(shí)間序列數(shù)據(jù)、記錄計(jì)數(shù)值C；

輸出：硬件事件A在程序運(yùn)行期間發(fā)生的次數(shù)Cfinal.

過程：OLE(Tend,Trun,C)

①Cfinal←0;

② ΔTend[i]←Tend[i+1]-Tend[i];

③ ΔTrun[i]←Trun[i+1]-Trun[i];

④ ΔC[i]←C[i+1]-C[i];

⑤ ΔTend_s,ΔTrun_s,ΔCs←ArgSortOnC(ΔTend,

ΔTrun,ΔC);

⑥S1,S2←SeqNum(ΔTend_s/ΔTrun_s);

⑦Cfinal←Cfinal+sum(ΔCs);

⑧N←regression(Si,ΔCs);

⑨ foriinS2do

⑩Cfinal←Cfinal+N.predict(i);

4 算法實(shí)現(xiàn)及調(diào)用方式

為檢驗(yàn)OLE算法提升MPX準(zhǔn)確率的效果，我們?cè)陂_源MPX庫(kù)NeoMPX[16]中實(shí)現(xiàn)OLE算法.NeoMPX庫(kù)兼容PAPI，已集成多種MPX算法，包括TAM，DIRA，CAM，DCAM等.NeoMPX庫(kù)具有良好的可擴(kuò)展性，可新增其他MPX估計(jì)算法.

NeoMPX的軟件架構(gòu)如圖4所示，整體流程分為3個(gè)主要步驟：調(diào)度、采樣和估計(jì).其中調(diào)度部分沿用PAPI的標(biāo)準(zhǔn)設(shè)計(jì)，使用Linux系統(tǒng)工具perf提供的接口，直接獲取調(diào)度結(jié)果.為了保證時(shí)序采樣的精準(zhǔn)性，子進(jìn)程專門對(duì)父進(jìn)程運(yùn)行的應(yīng)用程序的事件進(jìn)行定時(shí)采樣，并在程序運(yùn)行完后，基于采樣序列進(jìn)行估計(jì).圖4中的估計(jì)模塊中(子進(jìn)程)，我們加入了新實(shí)現(xiàn)的OLE算法.

Fig. 4 The software architecture of NeoMPX圖4 NeoMPX軟件架構(gòu)圖

NeoMPX算法框架采用2層可擴(kuò)展設(shè)計(jì)：上層組合不同通用算子實(shí)現(xiàn)不同的估計(jì)算法；下層集成不同估計(jì)算法中用到的通用算子.基于這個(gè)可擴(kuò)展框架，NeoMPX不僅可以通過調(diào)用不同API來使用不同估計(jì)算法，而且在新增OLE算法時(shí)，僅需針對(duì)估計(jì)算法模塊添加入新算法的實(shí)現(xiàn)，并用API封裝即可.

NeoMPX庫(kù)兼容標(biāo)準(zhǔn)的PAPI API，因此使用方式與PAPI完全一致.MPX估計(jì)算法可以通過API顯式地進(jìn)行選擇.如圖5所示，在NeoMPX庫(kù)中顯式調(diào)用OLE算法(行13).

Fig. 5 The sample code of invoking OLE in NeoMPX圖5 在NeoMPX庫(kù)中調(diào)用OLE的示例代碼

5 實(shí)驗(yàn)設(shè)置

1) 硬件平臺(tái).我們選取當(dāng)前主流的X86和ARM的處理器作為實(shí)驗(yàn)平臺(tái)，分別是Intel Xeon Gold 6248和Huawei Kunpeng 920.這2款處理器都是2019年發(fā)布的全新架構(gòu)，與硬件事件相關(guān)的參數(shù)如表1所列.從表1中可以看出，處理器能支持的硬件事件數(shù)量遠(yuǎn)大于硬件計(jì)數(shù)器數(shù)量.操作系統(tǒng)使用CentOS，以保證Linux perf對(duì)多事件調(diào)度的實(shí)現(xiàn)一致.

Table 1 The Specification of Two Mainstream Processors About Hardware Counters表1 2款處理器與硬件事件相關(guān)的參數(shù)

2) 基準(zhǔn)測(cè)試程序.Rodinia[19]是HPC領(lǐng)域國(guó)際上流行的一款測(cè)試程序集.為檢驗(yàn)OLE算法的使用效果，我們選取Rodinia的6個(gè)典型測(cè)試程序，如表2所示.這6個(gè)測(cè)試程序涵蓋HPC領(lǐng)域的4種不同數(shù)值計(jì)算模式以及5個(gè)不同應(yīng)用領(lǐng)域.

Table 2 Six Evaluated Benchmarks from Rodinia表2 6個(gè)Rodinia測(cè)試程序

測(cè)試中，這些測(cè)試程序的運(yùn)行參數(shù)都使用默認(rèn)值，且我們?cè)谶@些程序源代碼中插入PAPI和NeoMPX庫(kù)的API調(diào)用,如圖5所示.

3) 處理器硬件事件.主流處理器能支持的硬件事件很多(可達(dá)上百個(gè))，但性能分析與建模中最常用的事件并不需要那么多，因此我們?cè)?款測(cè)試處理器上分別選取了16個(gè)最常用的硬件事件.如表3所示，在Intel X86處理器上選取的16個(gè)硬件事件涵蓋了分支預(yù)測(cè)和TLB訪問等5類關(guān)鍵事件類型.

Table 3 Sixteen Evaluated Hardware Events on Intel CPU表3 Intel處理器上的16個(gè)常用的硬件事件

4) MPX估計(jì)算法.我們選取5個(gè)最典型的MPX估計(jì)算法與OLE算法進(jìn)行對(duì)比，分別是：PAPI默認(rèn)的MPX估計(jì)算法、Mathur等人[10-11]提出的TAM和DIRA算法、Wang等人[12]提出的CAM和DCAM算法.

① OCOE模式的每個(gè)硬件計(jì)數(shù)器在程序運(yùn)行期間內(nèi)只對(duì)一個(gè)硬件事件進(jìn)行計(jì)數(shù)，不存在任何估計(jì)導(dǎo)致的誤差，因此將其作為基準(zhǔn)結(jié)果.則MPX估計(jì)算法(相對(duì)OCOE模式)的錯(cuò)誤率Rerr為

(1)

(2)

② 對(duì)不同硬件事件，在所有測(cè)試程序中的準(zhǔn)確率提升為

(3)

6 結(jié)果分析

為全面分析實(shí)驗(yàn)結(jié)果，我們從測(cè)試程序、硬件事件以及跨處理器這3個(gè)不同角度進(jìn)行分析.

Fig. 6 The relative error ratio (to PAPI default) of the five MPX estimation algorithms圖6 5種MPX估計(jì)算法相對(duì)PAPI默認(rèn)MPX估計(jì)算法的錯(cuò)誤率

進(jìn)一步分析，我們發(fā)現(xiàn)OLE在HeartWall(結(jié)構(gòu)化網(wǎng)格)、KNN和StreamCluster(密集線性代數(shù))90%的硬件事件中都能有效低相對(duì)錯(cuò)誤，這表明OLE針對(duì)結(jié)構(gòu)化網(wǎng)格和密集線性代數(shù)算法有很好的效果.

2) 從硬件事件的角度.表4對(duì)比了5種MPX估計(jì)算法的準(zhǔn)確率提升.我們將基于時(shí)間局部性假設(shè)的4種不同算法(DIRA，TAM，DCAM，CAM)根據(jù)算法類型分為2類，每一類都選取最優(yōu)結(jié)果來比較.

Table 4 Comparison of Accuracy Improved Ratio for Estimation Algorithms on Events表4 估計(jì)算法對(duì)事件準(zhǔn)確率提升的對(duì)比 %

如表4所示，OLE相比PAPI默認(rèn)MPX評(píng)估算法，準(zhǔn)確率平均提升了10.5%左右，最多可提升46.6%；相比DIRA/TAM和DCAM/CAM這2類算法，準(zhǔn)確率平均分別提升了18.8%和17.7%.

進(jìn)一步分析，我們發(fā)現(xiàn)：

① 在最壞情況下，OLE比其他2類基于時(shí)間局部性假設(shè)的算法，都有更好的結(jié)果(參見表4，-15.3%比-59.2%和-95.2%)；

② 在性能建模領(lǐng)域中，最常用的訪存相關(guān)的硬件事件，其中有3個(gè)事件OLE都取得了約20%的準(zhǔn)確率提升；

③ 對(duì)TLB相關(guān)的硬件事件dtlm:m和dtlm:s，OLE對(duì)結(jié)果準(zhǔn)確率提升更具優(yōu)勢(shì)(34%～46%).

這些結(jié)果顯示，OLE有助于MPX在性能建領(lǐng)域的進(jìn)一步應(yīng)用.

3) 從跨處理器的角度.為評(píng)估OLE算法在不同處理器之間的普適性，我們?cè)?款主流X86和ARM 處理器上進(jìn)行實(shí)驗(yàn)對(duì)比.表5展示了3類算法(包含DIRA，TAM，DCAM，CAM，OLE，結(jié)果均取最優(yōu)值)在不同處理器上的平均準(zhǔn)確率以及最大、最小準(zhǔn)確率的提升.

實(shí)驗(yàn)結(jié)果顯示，OLE在Intel處理器上獲得了平均10.5%的準(zhǔn)確率提升，在ARM處理器上獲得了平均3.5%的準(zhǔn)確率提升，均高于其他4種基于時(shí)間局部性假設(shè)的估計(jì)算法.這說明OLE在跨處理器上，能獲得更穩(wěn)定、更精確的計(jì)數(shù)結(jié)果.

Table 5 Comparison of Accuracy Improved Ratio for Five Different Estimation Algorithms表5 5種估計(jì)算法準(zhǔn)確率提升對(duì)比 %

7 結(jié) 論

MPX允許處理器使用數(shù)量有限的硬件性能計(jì)數(shù)器來記錄更多的硬件事件，但現(xiàn)有基于時(shí)間局部性假設(shè)的MPX估計(jì)算法準(zhǔn)確率過低，導(dǎo)致MPX在實(shí)際場(chǎng)景中一直未被廣泛使用.為此，本文提出了一種基于數(shù)據(jù)分布一致性的輪廓線估計(jì)法OLE，通過對(duì)硬件事件分布進(jìn)行排序，逆向累積分布實(shí)現(xiàn)估計(jì)插值，從而有效提升MPX估計(jì)結(jié)果的準(zhǔn)確率.

下一步，我們將結(jié)合基于時(shí)間局部性假設(shè)的工作[12]以及本文基于數(shù)據(jù)分布一致性規(guī)律的工作，設(shè)計(jì)一套自適應(yīng)MPX框架，針對(duì)不同應(yīng)用與處理器，根據(jù)實(shí)時(shí)采集的硬件事件的數(shù)據(jù)特征，動(dòng)態(tài)選擇最優(yōu)的MPX估計(jì)算法.

作者貢獻(xiàn)聲明：林新華負(fù)責(zé)全文框架設(shè)計(jì)、論文撰寫、全文修訂、最終審核；王杰負(fù)責(zé)內(nèi)容設(shè)計(jì)，提出算法和實(shí)驗(yàn)設(shè)計(jì)；王一超負(fù)責(zé)論文整體研究思路、部分論文撰寫、最終版本修訂；左思成負(fù)責(zé)文獻(xiàn)調(diào)研和撰寫、論文插圖設(shè)計(jì)和修訂.