一種基于頻度統(tǒng)計(jì)的動(dòng)態(tài)二進(jìn)制翻譯優(yōu)化方法*

李 男，龐建民，單 征

(解放軍信息工程大學(xué),河南 鄭州 450002)

1 引言

以龍芯[1]、申威[2]、飛騰等為代表的國產(chǎn)處理器的問世不僅顯示出我國在自主核心芯片研發(fā)上的實(shí)力，也大大增強(qiáng)了國家的信息安全防護(hù)能力；同時(shí)，以神威、天河、曙光等為代表的國產(chǎn)超級(jí)計(jì)算機(jī)的計(jì)算能力在世界上也處于領(lǐng)先水平，2016年以來，在全球超級(jí)計(jì)算機(jī)500強(qiáng)榜單上，神威·太湖之光與天河二號(hào)三次攜手奪得前兩名。與國產(chǎn)硬件水平不斷提升相比，其上支持的軟件棧的數(shù)量和規(guī)模仍有待提高，面向國產(chǎn)平臺(tái)借助二進(jìn)制翻譯手段進(jìn)行軟件移植的意義重大。

二進(jìn)制翻譯技術(shù)[3,4]是作為程序等價(jià)變換工具產(chǎn)生并發(fā)展起來的，被定義為一種機(jī)器上的指令序列到另一種機(jī)器上指令序列的等價(jià)轉(zhuǎn)換過程。按照翻譯方式可以分為三種[5]：解釋執(zhí)行，靜態(tài)翻譯和動(dòng)態(tài)翻譯[6]。動(dòng)態(tài)二進(jìn)制翻譯采用了“查找→翻譯→執(zhí)行”的工作模型，如圖 1所示，先在翻譯緩存T-Cache(Translated Code Cache)中進(jìn)行查找，如果命中，則進(jìn)入執(zhí)行階段，否則進(jìn)入翻譯階段。翻譯階段以基本塊為單位進(jìn)行，將翻譯后的代碼以翻譯塊TB(Translated Block)為單位存入到T-Cache中，執(zhí)行階段以TB為單位進(jìn)行，一個(gè)TB執(zhí)行完畢后檢查是否存在塊鏈，如果存在則繼續(xù)執(zhí)行代碼，否則轉(zhuǎn)入到查找階段。T-Cache作為連接查找、翻譯和執(zhí)行三個(gè)過程的紐帶，是構(gòu)成動(dòng)態(tài)二進(jìn)制翻譯的重要內(nèi)容，也是優(yōu)化工作的一個(gè)關(guān)注點(diǎn)。

Figure 1 Model of dynamic binary translator圖1 動(dòng)態(tài)二進(jìn)制翻譯器的工作模型

2 問題的提出

為了緩存翻譯代碼并提高其復(fù)用性，動(dòng)態(tài)二進(jìn)制翻譯建立了一套T-Cache管理機(jī)制，將動(dòng)態(tài)翻譯產(chǎn)生的本地碼以TB的形式存入緩存區(qū)T-Cache中，當(dāng)程序運(yùn)行過程中需要重復(fù)調(diào)用某TB時(shí)，翻譯平臺(tái)會(huì)在T-Cache中進(jìn)行查找。T-Cache機(jī)制由于需要暫存TB，需要在內(nèi)存中開辟一段存儲(chǔ)空間，理想的狀態(tài)是T-Cache無限大，能夠容納所有的TB，但是有限的物理資源決定了T-Cache只能是有限空間。為了在有限的T-Cache空間下盡可能地提高翻譯效率，必須對(duì)T-Cache進(jìn)行有效的分配和管理。

程序局部性原理表明，程序中20%的指令占用了80%的執(zhí)行時(shí)間，如果能夠使執(zhí)行頻度高的代碼較長(zhǎng)時(shí)間駐留在T-Cache中，無疑會(huì)提高執(zhí)行效率。

為實(shí)現(xiàn)這個(gè)目的，需要解決好兩個(gè)問題：一是熱代碼的有效識(shí)別問題。本文將待翻譯程序中頻繁執(zhí)行的二進(jìn)制代碼片段稱為熱代碼，識(shí)別熱代碼的工作必須在動(dòng)態(tài)二進(jìn)制翻譯中完成，這就需要在翻譯器的合適位置進(jìn)行程序插樁，動(dòng)態(tài)監(jiān)控基本塊的執(zhí)行情況，另外，還需要確定熱代碼的起始位置和終止條件。二是保證熱代碼能夠被整體地執(zhí)行。熱代碼往往包含多個(gè)基本塊，而執(zhí)行階段T-Cache中的代碼以TB為單位執(zhí)行，這就會(huì)造成熱代碼執(zhí)行時(shí)程序控制流會(huì)在執(zhí)行線索與翻譯線索間頻繁切換，造成額外的時(shí)間開銷。

為此，文本提出了“熱代碼識(shí)別→超塊緩存STB(Super Translated Block)構(gòu)造→T-Cache管理策略改進(jìn)”的解決思路，針對(duì)第一個(gè)問題，本文提出了一種基于頻度統(tǒng)計(jì)的熱代碼識(shí)別算法，通過在翻譯器的適當(dāng)位置進(jìn)行程序插樁，動(dòng)態(tài)更新每個(gè)基本塊的執(zhí)行次數(shù)——即“熱度”，把熱度超過預(yù)定閾值的基本塊及其后續(xù)若干基本塊認(rèn)定為熱代碼。針對(duì)第二個(gè)問題，本文提出了構(gòu)造超塊緩存的思想，將熱代碼中的基本塊翻譯后鏈接為緩存容量更大的超塊提供給T-Cache系統(tǒng)?；跓岽a和超塊，本文最后提出了改進(jìn)的T-Cache管理策略。

本文的主要貢獻(xiàn)在于：

(1) 提出了一種基于頻度統(tǒng)計(jì)的熱代碼識(shí)別算法，通過程序插樁和動(dòng)態(tài)監(jiān)控對(duì)每個(gè)基本塊的執(zhí)行情況進(jìn)行profiling統(tǒng)計(jì)，在動(dòng)態(tài)翻譯過程中實(shí)現(xiàn)了有效識(shí)別執(zhí)行頻度高的代碼片段。

(2) 提出了構(gòu)建超塊緩存的思想，將熱代碼中包含的基本塊翻譯后鏈接成緩存容量更大的超塊，能夠有效減少上下文切換次數(shù)，降低時(shí)間開銷，也為T-Cache系統(tǒng)提供了新的緩存資源。

(3) 改進(jìn)了T-Cache系統(tǒng)的查找方法，提出了雙層查找策略，針對(duì)新引進(jìn)的超塊緩存進(jìn)行快速查找，針對(duì)常規(guī)緩存進(jìn)行慢速查找；同時(shí)，改進(jìn)了T-Cache系統(tǒng)原有的替換策略，對(duì)超塊緩存和常規(guī)緩存使用了不同的內(nèi)容替換策略，提高了T-Cache的命中率。

3 基于頻度統(tǒng)計(jì)的熱代碼識(shí)別算法

動(dòng)態(tài)二進(jìn)制翻譯主要有三種熱代碼識(shí)別方法[7]：一是基于塊的識(shí)別。該策略記錄每個(gè)基本塊的使用次數(shù)，一旦達(dá)到熱度即認(rèn)定為熱塊，并開始建立熱路徑。這種方法造成的系統(tǒng)開銷較大，預(yù)測(cè)精度不高。二是基于跳轉(zhuǎn)邊的識(shí)別。該策略通過統(tǒng)計(jì)基本塊之間的跳轉(zhuǎn)次數(shù)取代收集基本塊的使用信息完成熱路徑識(shí)別，文獻(xiàn)[8]對(duì)該策略進(jìn)行了詳細(xì)闡述。該策略實(shí)現(xiàn)簡(jiǎn)單，準(zhǔn)確性較高。但是，由于跳轉(zhuǎn)邊僅僅反映局部跳轉(zhuǎn)關(guān)系，無法應(yīng)對(duì)基本塊重疊的情況。三是基于路徑的識(shí)別。該策略不需要像前兩種方法那樣，在每次基本塊發(fā)生跳轉(zhuǎn)時(shí)都進(jìn)行計(jì)數(shù)統(tǒng)計(jì)，僅需要對(duì)整條路徑進(jìn)行計(jì)數(shù)即可，可以有效減少統(tǒng)計(jì)開銷。文獻(xiàn)[9]表明，有效利用該方法的前提是找到一種適合當(dāng)前動(dòng)態(tài)翻譯平臺(tái)的高效算法。該策略需要有效解決預(yù)測(cè)路徑中包含的基本塊的表示問題，文獻(xiàn)[10]中提出了一種使用二進(jìn)制編碼序列來標(biāo)識(shí)路徑中包含基本塊的方法，該方法使用0、1編碼來分別標(biāo)識(shí)條件跳轉(zhuǎn)發(fā)生后的不同目標(biāo)基本塊，這樣，每一條路徑對(duì)應(yīng)一個(gè)二進(jìn)制編碼序列，所有路徑可以構(gòu)成一個(gè)哈夫曼樹的結(jié)構(gòu)。

但是，文獻(xiàn)[10]在表示路徑構(gòu)成時(shí)僅對(duì)條件跳轉(zhuǎn)后的基本塊進(jìn)行了編碼標(biāo)識(shí)，沒有對(duì)直接跳轉(zhuǎn)后的基本塊進(jìn)行編碼，即忽略了直接跳轉(zhuǎn)的情況。雖然這樣可以有效壓縮路徑長(zhǎng)度、節(jié)省查找開銷，但同時(shí)也可能導(dǎo)致路徑表示不完整，影響熱路徑判定的命中率。

綜合考慮多種因素，本文提出了一種基于頻度統(tǒng)計(jì)的熱代碼識(shí)別算法，該算法結(jié)合了塊識(shí)別和路徑識(shí)別兩種策略的特點(diǎn)，借助程序插樁和profiling技術(shù)[11]實(shí)現(xiàn)了在動(dòng)態(tài)執(zhí)行過程中對(duì)基本塊的頻度統(tǒng)計(jì)。算法在循環(huán)終止條件中增加了對(duì)于回路的判斷，這對(duì)于識(shí)別程序中最容易成為熱代碼的循環(huán)結(jié)構(gòu)特別有效。

雖然算法會(huì)造成部分統(tǒng)計(jì)開銷，但本文更多的是考慮熱路徑的有效識(shí)別問題，后續(xù)內(nèi)容提到的構(gòu)造超塊緩存方法和T-Cache管理策略的改進(jìn)才是本文帶來效率提升的關(guān)鍵。

3.1 HCFS算法原理

基于頻度統(tǒng)計(jì)的熱代碼識(shí)別HCFS(Hot Code Based on Frequency Statistic)算法將“一個(gè)執(zhí)行頻度高的基本塊與其后若干連續(xù)執(zhí)行的基本塊組成的路徑”作為熱代碼預(yù)測(cè)條件，遵循“先熱先選擇”的設(shè)計(jì)原則，從頻度值高的基本塊開始，把其后連續(xù)執(zhí)行的若干基本塊也納入熱代碼范圍。理論上熱代碼路徑越長(zhǎng)意味著基本塊的復(fù)用率越高，更多的基本塊能夠被連續(xù)執(zhí)行，有利于縮減基本塊的翻譯次數(shù)，降低翻譯開銷。但是，由于受到緩存區(qū)大小的物理限制，熱代碼不能過長(zhǎng)，因此確定熱代碼識(shí)別的終止條件是一個(gè)關(guān)鍵問題。本文對(duì)熱代碼的終止條件做出了限制：對(duì)于非循環(huán)結(jié)構(gòu)，算法規(guī)定當(dāng)熱代碼長(zhǎng)度達(dá)到預(yù)定上限時(shí)，終止熱代碼識(shí)別；對(duì)于循環(huán)結(jié)構(gòu)，由于其成為熱代碼的概率高，算法將形成回路作為算法終止的另一個(gè)條件，即當(dāng)基本塊跳轉(zhuǎn)到熱代碼的頭部形成回路時(shí)，算法終止。

3.2 HCFS算法實(shí)現(xiàn)

HCFS算法是基于頻度統(tǒng)計(jì)實(shí)現(xiàn)的，頻度統(tǒng)計(jì)代碼插樁在基本塊開始執(zhí)行前，在獲取當(dāng)前基本塊的PC(地址)后，開始對(duì)profiling進(jìn)行遞增處理，更新基本塊的使用次數(shù)，完成基本塊執(zhí)行頻度統(tǒng)計(jì)。頻度統(tǒng)計(jì)函數(shù)tb_update_profiling( )的實(shí)現(xiàn)如下所示：

//功能:基本塊熱度統(tǒng)計(jì)

static inline TranslationBlock *tb_update_profiling(void){

TranslationBlock *tb;

int flags;

cpu_get_tb_cpu_state(env,&pc,&cs_base,&flags);/*獲取當(dāng)前執(zhí)行到的PC*/

if(tb→pc)

{

++tb→profiling;//更新profiling

}

returntb;

}

其中，tb為指向當(dāng)前基本塊的指針；pc代表基本塊的本地地址，負(fù)責(zé)對(duì)基本塊進(jìn)行唯一標(biāo)識(shí)；profiling代表基本塊的頻度，負(fù)責(zé)統(tǒng)計(jì)基本塊的執(zhí)行次數(shù)。

基于頻度統(tǒng)計(jì)，HCFS算法的偽代碼如算法 1所示，算法的工作過程如下所示：

步驟1依次讀取可執(zhí)行文件中的每個(gè)基本塊信息。

步驟2獲取當(dāng)前基本塊的地址pc。

步驟3檢查是否為最后一個(gè)基本塊，如果是，跳轉(zhuǎn)到步驟7；否則，跳轉(zhuǎn)到步驟4。

步驟4判斷當(dāng)前基本塊是否處于熱代碼中，如果是，跳轉(zhuǎn)回步驟2進(jìn)行下一個(gè)基本塊判斷；否則，進(jìn)入步驟5，提取新的熱代碼。

步驟5判斷當(dāng)前基本塊的頻度值是否超過閾值，如果是，進(jìn)入步驟6；否則，跳轉(zhuǎn)回步驟2。

步驟6將當(dāng)前基本塊預(yù)設(shè)為新熱代碼的頭部，啟動(dòng)熱代碼預(yù)測(cè)。每次讀入一個(gè)基本塊，判斷是否滿足兩個(gè)條件：一是當(dāng)前基本塊是否指向熱代碼頭部，如果是，說明出現(xiàn)回路，跳轉(zhuǎn)到步驟7；二是熱代碼長(zhǎng)度是否達(dá)到上限，如果達(dá)到，退出本次預(yù)測(cè),跳轉(zhuǎn)到步驟2；如果兩個(gè)條件都不滿足，將當(dāng)前基本塊納入熱路徑，并繼續(xù)讀入下一個(gè)基本塊。

步驟7算法結(jié)束，輸出熱代碼。

算法1HCFS算法描述

//功能：熱路徑局部預(yù)測(cè)

//輸入：可執(zhí)行文件句柄elf-file

//輸出：熱路徑頭指針headpc

Foreachtbinelf-file

pc=env→pc;//從全局變量env中獲取當(dāng)前基本塊pc

if當(dāng)前基本塊不處于當(dāng)前熱路徑中

if基本塊profiling大于熱度閾值

headpc=pc;//當(dāng)前基本塊為熱路徑頭部

foreachtb→nextinelf-file∥啟動(dòng)熱路徑預(yù)測(cè)循環(huán)

將基本塊納入熱路徑序列；

if(基本塊pc等于headpc) or (熱路徑長(zhǎng)度大于設(shè)定長(zhǎng)度上限) 輸出當(dāng)前熱路徑頭指針headpc;//結(jié)束熱路徑識(shí)別

break;

Endif

Endfor

else

tb=tb→next;//指向下一個(gè)基本塊

Endif

else

tb=tb→next;//指向下一個(gè)基本塊

Endif

iftb→next=NULL

break;//終止動(dòng)態(tài)翻譯循環(huán)

Endif

Endfor

4 超塊緩存構(gòu)造

識(shí)別出熱代碼后，其包含的基本塊被翻譯并存儲(chǔ)到T-Cache中，但T-Cache以TB為單位的傳統(tǒng)執(zhí)行方式，使得熱代碼不能被一次性執(zhí)行完畢，無法充分發(fā)揮熱代碼的功效。為此，本文提出了構(gòu)造超塊緩存的思路，將HCFS算法識(shí)別出的熱代碼中包含的基本塊有序地組織起來，翻譯后形成緩存容量更大的翻譯塊—“超塊”STB提供給T-Cache使用，不僅使得執(zhí)行頻率較高的代碼保存在T-Cache中，也能擴(kuò)大一次執(zhí)行的代碼量，有效減少線索切換產(chǎn)生的上下文開銷。需要說明的是，本文提出的超塊概念特指的是在翻譯緩存中新開辟的一段特殊區(qū)域。

STB的構(gòu)造過程從熱代碼的頭指針開始，依次判斷當(dāng)前基本塊結(jié)尾是否為直接跳轉(zhuǎn)，如果是，直接插入后繼基本塊代碼；否則，保留跳轉(zhuǎn)出口信息。圖2展示了STB使用前后的對(duì)比情況，假設(shè)TB1和TB2屬于同一個(gè)熱代碼區(qū)域，且存在直接跳轉(zhuǎn)關(guān)系。圖2a展示了未使用STB的情況，TB1執(zhí)行后和TB2執(zhí)行前，必須進(jìn)行相關(guān)環(huán)境變量的保存工作和恢復(fù)工作，環(huán)境變量主要包含一些本地寄存器的相關(guān)信息；圖2b展示了使用STB的情況，將TB1和TB2之間的直接跳轉(zhuǎn)語句刪除，合并兩個(gè)基本塊后形成超塊STB。

Figure 2 Construction of super translated block圖2 STB的構(gòu)造

作為TB的有益補(bǔ)充，STB豐富了T-Cache的管理范圍，但同時(shí)也對(duì)T-Cache原有的管理方法提出了新的要求。下面從查找方法和清空策略兩個(gè)方面討論在增加超塊緩存后，對(duì)于T-Cache管理的優(yōu)化。

5 T-Cache系統(tǒng)管理策略的改進(jìn)

5.1 查找方法的改進(jìn)

T-Cache系統(tǒng)原有的查找方法只涉及TB，未涉及STB。引進(jìn)STB后，需要改進(jìn)原有的T-Cache查找算法，增加對(duì)STB的處理。為了不引起混淆，下文將由常規(guī)TB構(gòu)成的翻譯緩存區(qū)域稱為OldCache，由STB構(gòu)成的翻譯緩存區(qū)域稱為NewCache。

為充分發(fā)揮STB的作用，本文提出了分層查找的思想，將查找過程分成兩個(gè)階段，先在NewCache中進(jìn)行快速查找，再在常規(guī)OldCache中進(jìn)行慢速查找，算法描述如算法 2所示。工作流程如下所示：

步驟1從環(huán)境變量env中提取當(dāng)前基本塊PC等參數(shù)。

步驟2在NewCache中進(jìn)行快查，取出由PC標(biāo)識(shí)的STB。

步驟3判斷STB是否為空，如果是，轉(zhuǎn)入步驟4進(jìn)行慢查；否則，說明查找命中，轉(zhuǎn)入步驟7。

步驟4在OldCache中進(jìn)行慢查，取出由PC標(biāo)識(shí)的常規(guī)TB。

步驟5判斷TB是否為空，如果是，跳轉(zhuǎn)至步驟6，進(jìn)入翻譯過程；否則，說明查找命中，輸出TB，算法結(jié)束。

步驟6翻譯基本塊，將翻譯后的本地代碼存入OldCache中。

步驟7輸出STB，算法結(jié)束。

在上述步驟中，步驟2中的快查針對(duì)NewCache，步驟4中的慢查針對(duì)OldCache。快查和慢查都使用了Hash查找方法，將PC作為鍵值。查找過程的順序是先進(jìn)行快查再進(jìn)行慢查，如果慢查也未命中，則進(jìn)行翻譯工作。

算法2改進(jìn)的T-Cache查找算法

//功能：查找T-Cache

//輸入：環(huán)境變量env

//輸出：翻譯緩存tb

cpu_get_tb_cpu_state(env,&pc,&cs_base,&flags);//獲取env中的相關(guān)成員值

tb=env→th_jmp_NewCache[tb_jump_NewCache_hash_func(pc)];/*在NewCache中進(jìn)行查找*/

if(!tb)//如果沒有找到所需超塊

{

{tb=env→tb_jmp_OldCache[tb_jmp_OldCache_hash_func(pc)];/*進(jìn)入OldCache中查找*/

if(!tb)

{

tb=tb_gen_code(env,pc,cs_base,flags,0);/*進(jìn)入翻譯模塊*/

env→tb_jmp_OldCache[tb_jmp_OldCache_hash_func(pc)]=tb;/*將tb寫入OldCache中*/

}

}

輸出tb;

改進(jìn)的T-Cache查找算法，加入了針對(duì)STB的處理，一旦命中，立即執(zhí)行熱代碼對(duì)應(yīng)的翻譯緩存，并且一次執(zhí)行的代碼量大，使得程序經(jīng)常執(zhí)行的代碼部分可以駐留在T-Cache中，能夠有效延長(zhǎng)執(zhí)行線索在T-Cache的駐留時(shí)間，提升了系統(tǒng)效率。

5.2 替換策略的改進(jìn)

T-Cache的替換策略在T-Cache管理優(yōu)化中發(fā)揮著重要作用，由于STB的引入，需要改進(jìn)原有的替換策略。

T-Cache已有的替換策略包括：全清空策略(Full Cache Flush)采用的方法是一旦T-Cache空間不足，則清空全部T-Cache內(nèi)容。該算法實(shí)現(xiàn)簡(jiǎn)單，但性能不高，未考慮基本塊的熱度；最近最少使用策略(Least-Recently-Used)考慮了熱度的影響因素，一旦T-Cache空間不足，淘汰最近使用最少的基本塊，但該策略由于替入塊與替出塊的大小不同，容易形成存儲(chǔ)空間的碎片；先進(jìn)先出策略(First-In-First-Out)采用隊(duì)列作為數(shù)據(jù)結(jié)構(gòu)，一旦T-Cache空間不足，淘汰排在隊(duì)頭的基本塊。該策略可以有效減少空間碎片，但未考慮熱度影響。分時(shí)清空策略(Preemptive Flush)根據(jù)程序的運(yùn)行情況，在特定時(shí)域內(nèi)采用全清空處理。該策略被Dynamo[12]平臺(tái)采用，可以有效降低熱塊的損失。

由于新構(gòu)建的NewCache豐富了T-Cache系統(tǒng)的翻譯緩存類型，結(jié)合工程實(shí)際，本文針對(duì)不同緩存類型采用不同的替換策略。針對(duì)OldCache，仍然使用簡(jiǎn)單的全清空策略；針對(duì)NewCache，為了提高管理效率，采用先入先出的替換策略，將超塊按照先后順序從地址低位向高位依次存放，當(dāng)NewCache滿時(shí)，將先進(jìn)入的超級(jí)塊淘汰。該策略實(shí)現(xiàn)簡(jiǎn)單，和全清空策略相比，可以較好地提升查找效率，延長(zhǎng)STB的存活時(shí)間。

6 實(shí)驗(yàn)

6.1 實(shí)驗(yàn)環(huán)境

本文將提出的優(yōu)化方法在開源二進(jìn)制翻譯器QEMU1.7.2[13]中進(jìn)行了實(shí)現(xiàn)。使用了如表 1所示的實(shí)驗(yàn)環(huán)境，源平臺(tái)采用的是X86-64架構(gòu)處理器；本地平臺(tái)采用的是國產(chǎn)SW410處理器。測(cè)試用例選取了SPEC 2006(Standard Performance Evaluation Corporation)測(cè)試集，它是由標(biāo)準(zhǔn)性能評(píng)估公司組織建立的一套用于計(jì)算機(jī)系統(tǒng)評(píng)估的業(yè)界標(biāo)準(zhǔn)測(cè)試集。

Table 1 Test environment表1 實(shí)驗(yàn)環(huán)境

6.2 熱代碼識(shí)別測(cè)試

使用SPEC 2006中的部分用例對(duì)HCFS算法的識(shí)別效果進(jìn)行了測(cè)試，因?yàn)榇隧?xiàng)測(cè)試只涉及熱代碼的識(shí)別，不涉及超塊的構(gòu)造及T-Cache管理策略的改進(jìn)，為此，測(cè)試時(shí)注釋掉了T-Cache優(yōu)化部分的代碼，圖3和表2分別展示了熱代碼識(shí)別情況和對(duì)應(yīng)的頻度統(tǒng)計(jì)造成的開銷情況。

圖3中，定義熱代碼識(shí)別率HCR(Hot Code Ratio)來描述識(shí)別效果，HCR=Nhotcode/Nallcode×100%。公式中，Nhotcode代表用例的熱代碼包含的基本塊數(shù)量;Nallcode代表用例的基本塊的總數(shù);HCR代表熱代碼中的基本塊占用例基本塊總數(shù)的比率，HCR數(shù)值越大，說明用例的熱代碼識(shí)別效果越好。從測(cè)試結(jié)果可以看出，用例h264ref和sjeng的識(shí)別效果較好，識(shí)別率分別達(dá)到29.73%和23.45%，gobmk和libquantum的識(shí)別效果較差，識(shí)別率只有0.14%和0.98%。

表2展示了每個(gè)用例的profiling開銷情況，第二列Time1表示未進(jìn)行頻度統(tǒng)計(jì)時(shí)的用例執(zhí)行時(shí)間;第三列Time2表示進(jìn)行頻度統(tǒng)計(jì)時(shí)的用例執(zhí)行時(shí)間;第四列表示頻度統(tǒng)計(jì)造成的開銷情況，Profiling開銷比=(Time2-Time1)/Time1×100%。

Table 2 Cost of profiling for hot code表2 熱代碼profiling開銷

測(cè)試數(shù)據(jù)說明，識(shí)別熱代碼時(shí)造成的profiling開銷與熱代碼的識(shí)別情況直接相關(guān)，識(shí)別效果越好的用例,profiling時(shí)間開銷越大，反之，開銷越小。例如，用例sjeng和h264ref的開銷分別達(dá)到5.02%和5.86%，而用例gobmk的開銷只有0.14%。另外，測(cè)試結(jié)果也說明在未使用T-Cache優(yōu)化方法前，熱代碼識(shí)別只能帶來負(fù)收益。

Figure 3 Performance test of HCFS algorithm圖3 HCFS算法性能測(cè)試

6.3 T-Cache管理的改進(jìn)測(cè)試

為測(cè)試改進(jìn)的T-Cache查找算法和替換策略效果，實(shí)驗(yàn)記錄了對(duì)OldCache和NewCache使用分層查找方法并配合使用改進(jìn)的替換策略時(shí)的運(yùn)行時(shí)間，此項(xiàng)測(cè)試包含了全部?jī)?yōu)化代碼。表3和圖4以不同形式展現(xiàn)了使用改進(jìn)的T-Cache管理策略時(shí)的優(yōu)化效果。表3以表格的形式展現(xiàn)了測(cè)試用例使用優(yōu)化方法前后的時(shí)間以及優(yōu)化加速情況，Tori表示優(yōu)化前的運(yùn)行時(shí)間，Topt表示優(yōu)化后的運(yùn)行時(shí)間，定義加速比Ratio=1-Topt/Tori×100%描述加速效果，Ratio值越小，表明優(yōu)化效果越好。圖4以柱狀圖的形式展現(xiàn)了各個(gè)用例的加速情況。

Table 3 Test of optimization method of T-Cache表3 T-Cache優(yōu)化方法測(cè)試

Figure 4 Test of optimization method of T-Cache圖4 T-Cache優(yōu)化方法測(cè)試

顯然，使用改進(jìn)方法后，翻譯系統(tǒng)的執(zhí)行效率得到了明顯提升，測(cè)試用例sjeng和h264ref的加速效果最明顯，分別達(dá)到了19.52%和15.73%。所有用例的平均加速比達(dá)到9.34%。

7 結(jié)束語

本文以“熱代碼識(shí)別→超塊緩存構(gòu)造→T-Cache管理策略改進(jìn)”為優(yōu)化線索，提出了一個(gè)提升動(dòng)態(tài)二進(jìn)制翻譯效率的方法。通過熱代碼的識(shí)別和超塊的構(gòu)造，為改進(jìn)T-Cache的原有管理策略打下了基礎(chǔ)。引入了熱代碼的概念，通過在動(dòng)態(tài)翻譯過程中對(duì)基本塊的執(zhí)行情況進(jìn)行即時(shí)監(jiān)控和統(tǒng)計(jì)，實(shí)現(xiàn)了對(duì)執(zhí)行頻度高的熱代碼的識(shí)別。為了使熱代碼能夠常駐翻譯緩存，通過構(gòu)造“超塊”的方法，將熱代碼中的基本塊重新鏈接，形成了容量更大的翻譯緩存。引進(jìn)超塊后，通過引入雙層查找策略，以及采用新的替換策略，提高了超塊的使用率，同時(shí)也增加了T-Cache的命中率。該優(yōu)化方法的正確性和帶來的收益在國產(chǎn)申威處理器平臺(tái)上進(jìn)行了實(shí)驗(yàn)驗(yàn)證。下一步，需要進(jìn)一步考慮翻譯緩存中OldCache和NewCache的不同占比情況對(duì)優(yōu)化效果的影響。

參考文獻(xiàn):

[1] Cai Song-song,Liu Qi,Wang Jian,et al.Optimization of binary translator based on GODSON CPU[J].Computer Engineering,2009,35(7):280-282.(in Chinese)

[2] SW410[EB/OL].[2014-03-26].http://www.shenweimicro.com/.

[3] Altman E,Kaeli D,Sheffer Y.Welcome to the opportunities of binary translation[J].IEEE Computer,2000,33(3):40-45.

[4] Gschwind M, Altman E R,Sathaye S,et al.Dynamic and transparent binary translation[J].IEEE Computer,2000,33(3):54-59.

[5] Cifuentes C,Malhotra V.Binary translation:Static,dynamic,retargetable?[C]∥Proc of International Conference on Software Maintenance,1996:340-349.

[6] Li Jian-hui, Ma Xiang-ning,Zhu Chuan-qi.Dynamic binary translation and optimization[J].Journal of Computer Research and Development,2007,44(1):161-168.(in Chinese)

[7] Shi H,Wang Y,Guan H,et al.An intermediate language level optimization framework for dynamic binary translation[J].ACM SIGPLAN Notices,2007,42(5):3-9.

[8] Ball T,Mataga P,Sagiv M.Edge profiling versus path profiling:The showdown[C]∥Proc of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages,1998:734-148.

[9] Dhodapkar A S,Smith J E.Comparing program phase detection techniques[C]∥Proc of the 36th Annual IEEE/ACM International Symposium on Microarchitecture,2003:217.

[10] Shi Hui-hui,Guan Hai-bing,Liang A-lei.Hot path optimization in software dynamic binary translation[J].Journal of Computer Engineering,2007,33(23):78-80.(in Chinese)

[11] Spink T,Wagstaff H,Franke B,et al.Efficient code generation in a region-based dynamic binary translator[C]∥Proc of the 2014 SIGPLAN/SIGBED Conference on Languages,Compilers and Tools for Embedded Systems,2014:3-12.

[12] Bala V,Duesterwald E,Banerjia S.Dynamo:A transparent dynamic optimization system[J].Proceeding of ACM SIGPLAN Notices,2000,35(5):1-12.

[13] Bellard F.QEMU,a fast and portable dynamic translator [C]∥Proc of the Annual Conference on USENIX Annual Technical Conference,2005:41-46.

附中文參考文獻(xiàn)：

[1] 蔡嵩松,劉淇,王劍,等.基于龍芯處理器的二進(jìn)制翻譯器優(yōu)化[J].計(jì)算機(jī)工程,2009,35(7):280-282.

[6] 李劍慧,馬湘寧,朱傳琪.動(dòng)態(tài)二進(jìn)制翻譯與優(yōu)化技術(shù)研究[J].計(jì)算機(jī)研究與發(fā)展,2007,44(1):161-168.

[10] 史輝輝,管海兵,梁阿磊.動(dòng)態(tài)二進(jìn)制翻譯中熱路徑優(yōu)化的軟件實(shí)現(xiàn)[J].計(jì)算機(jī)工程,2007,33(23):78-80.