二進(jìn)制翻譯中代碼Ｃａｃｈｅ的分級(jí)雙粒度管理策略

摘 要：提出一種二進(jìn)制翻譯中代碼Cache管理的LRC（Level－Region－Chunk）策略。其兼具全清空策略、FIFO策略和多級(jí)Cache的優(yōu)點(diǎn)，并且考慮了程序的時(shí)間空間局部性、執(zhí)行特性和替換開(kāi)銷(xiāo)，具有較好的性能，實(shí)現(xiàn)了代碼Cache的高效管理。

關(guān)鍵詞：二進(jìn)制翻譯；代碼Cache；LRC策略

中圖分類(lèi)號(hào)：TP319文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2007)06-0302-04

二進(jìn)制翻譯技術(shù)是目前解決軟件移植問(wèn)題的一個(gè)研究熱點(diǎn)，能將現(xiàn)有的軟件移植到新開(kāi)發(fā)的處理器上執(zhí)行。基于軟件的二進(jìn)制翻譯系統(tǒng)主要分為解釋器、靜態(tài)翻譯器和動(dòng)態(tài)翻譯器三種。動(dòng)態(tài)二進(jìn)制翻譯系統(tǒng)的基本原理是這樣的：動(dòng)態(tài)翻譯執(zhí)行源體系結(jié)構(gòu)的二進(jìn)制代碼，收集Profile信息；通過(guò)反饋信息對(duì)執(zhí)行頻度較高的代碼采用簡(jiǎn)單高效的策略進(jìn)行深度優(yōu)化，得到效率更高的目標(biāo)機(jī)本地代碼。

動(dòng)態(tài)二進(jìn)制翻譯中一類(lèi)比較重要的問(wèn)題是如何管理翻譯出來(lái)的目標(biāo)機(jī)本地代碼，既要盡可能少地占用內(nèi)存空間，又要減少由于代碼Cache的替換操作造成的性能下降。本文通過(guò)對(duì)常用的代碼Cache管理策略進(jìn)行分析，提出一種新的代碼Cache管理策略L(fǎng)RC（Level－Region－Chunk）。LRC策略結(jié)合了全清空、FIFO和多級(jí)Cache等方法的優(yōu)點(diǎn)，具有分級(jí)雙粒度的特點(diǎn)，Cache不命中率小；并且考慮到程序的時(shí)間空間局部性和Cache替換開(kāi)銷(xiāo)，實(shí)現(xiàn)了對(duì)代碼Cache的高效管理。

1 常見(jiàn)的Cache管理策略

代碼Cache是指軟件模擬Cache的行為，在內(nèi)存中開(kāi)辟一塊空間來(lái)存儲(chǔ)翻譯出來(lái)的目標(biāo)機(jī)本地碼。在介紹LRC策略之前，先介紹動(dòng)態(tài)二進(jìn)制翻譯系統(tǒng)和動(dòng)態(tài)優(yōu)化系統(tǒng)中常用的幾種代碼Cache管理策略。

（1）不替換策略

不替換策略就是在代碼Cache中從低地址到高地址依次存放每個(gè)代碼塊。由于空間足夠大，不會(huì)出現(xiàn)本地碼的替換，只有本地碼第一次翻譯時(shí)發(fā)生Cache不命中。這種策略是用大量犧牲內(nèi)存的方式來(lái)?yè)Q取時(shí)間上的優(yōu)勢(shì)，但是會(huì)給硬件的內(nèi)存容量帶來(lái)壓力。尤其是那些嵌入式系統(tǒng)中，由于內(nèi)存容量有限，對(duì)內(nèi)存使用量的限制非常嚴(yán)格。這種策略并不可取，不作為L(zhǎng)RC策略的實(shí)驗(yàn)對(duì)比對(duì)象。

（2）全清空策略

全清空策略是在代碼Cache中從低地址到高地址依次存放每個(gè)代碼塊。當(dāng)Cache空間不足或程序階段行為突變時(shí)，清空整個(gè)Cache。許多動(dòng)態(tài)二進(jìn)制翻譯系統(tǒng)和動(dòng)態(tài)優(yōu)化系統(tǒng)都采用這個(gè)策略，如Walkabout和Dynamo。其優(yōu)點(diǎn)是算法簡(jiǎn)單、容易實(shí)現(xiàn)、管理開(kāi)銷(xiāo)較小；但是沒(méi)有考慮程序的時(shí)間和空間局部性，也沒(méi)有考慮程序的執(zhí)行特性，會(huì)把很多比較熱的代碼塊替換出去，導(dǎo)致很多代碼塊的重復(fù)換入換出。這種抖動(dòng)現(xiàn)象降低了程序的性能。

（3）FIFO策略

FIFO策略是在代碼Cache中從低地址到高地址依次存放每個(gè)代碼塊。當(dāng)Cache空間不足時(shí)，按FIFO順序把最先進(jìn)入Cache的代碼塊替換出去。如果空間仍然不足，就繼續(xù)把物理上相鄰的代碼塊替換出去，直至有足夠的空間來(lái)存放代碼塊。DynamoRIO系統(tǒng)就采用這種策略。FIFO策略在一定程度上考慮了程序執(zhí)行的階段性特征。被替換出去的代碼塊是當(dāng)前Cache中最先生成的代碼塊，因此有可能已經(jīng)不再是執(zhí)行的熱點(diǎn)。這種策略的執(zhí)行效率較高；但是它沒(méi)有考慮程序的執(zhí)行特性，也沒(méi)有考慮減少代碼塊換出的次數(shù)從而減少管理的開(kāi)銷(xiāo)，而且先生成的代碼塊也未必應(yīng)該先被替換出Cache。因?yàn)榇a的熱度不取決于進(jìn)入Cache的順序。在性能上仍然存在一定的局限性。

（4）其他策略

除了上述三種最常用的管理策略外，還存在一些如最近最久未使用（LRU）策略、最大塊優(yōu)先替換、最適合大小塊優(yōu)先替換等策略。LRU策略雖然考慮了程序的執(zhí)行特性和時(shí)間局部性，但實(shí)現(xiàn)復(fù)雜，算法本身的開(kāi)銷(xiāo)非常大，而且還有碎片產(chǎn)生；后兩種策略只考慮空間的利用效率，而很少考慮程序的時(shí)間局部性和執(zhí)行特性。這些策略很少被動(dòng)態(tài)二進(jìn)制翻譯系統(tǒng)和動(dòng)態(tài)優(yōu)化系統(tǒng)采用。

2 LRC策略

2.1 本地碼的鏈接和斷鏈

在翻譯執(zhí)行目標(biāo)機(jī)本地碼的過(guò)程中，存在翻譯控制器與本地碼之間的上下文切換。這個(gè)切換要做很多事情。例如保存或恢復(fù)機(jī)器運(yùn)行狀態(tài)、再優(yōu)化/再翻譯源程序接下來(lái)的指令序列、存儲(chǔ)翻譯優(yōu)化的本地碼到Cache中等操作，會(huì)帶來(lái)很大開(kāi)銷(xiāo)。一種解決辦法就是記錄x86二進(jìn)制代碼的前驅(qū)后繼關(guān)系，把本地碼按照邏輯上的執(zhí)行順序鏈接起來(lái)，減少切換次數(shù)，直到所需的本地碼不在代碼Cache中，才發(fā)生切換來(lái)翻譯執(zhí)行后續(xù)的x86代碼。

Cache管理策略要對(duì)Cache中的某些本地碼進(jìn)行替換，會(huì)出現(xiàn)懸空的鏈接，使被刪除代碼塊的前驅(qū)找不到后繼。因此要進(jìn)行一些斷鏈處理，把被刪除代碼塊的前驅(qū)修改成返回翻譯控制器，同時(shí)修改刪除代碼塊的記錄信息。斷鏈也會(huì)使以前命中的本地碼變成不命中；可能導(dǎo)致這些本地碼的重新翻譯，引入一定的額外開(kāi)銷(xiāo)。

2.2 LRC策略的代碼Cache模型

LRC策略把代碼Cache按照所存儲(chǔ)的本地碼的執(zhí)行熱度分成上下兩級(jí)，大小的比例是1:4。上級(jí)Cache存儲(chǔ)熱度較高的本地碼；本地碼首先存入下級(jí)Cache，達(dá)到一定熱度后會(huì)被提升到上級(jí)。與硬件多級(jí)Cache不同的是：一塊本地碼在整個(gè)Cache中只有一個(gè)副本，因?yàn)榇aCache是用內(nèi)存模擬的，無(wú)論是在哪一級(jí)中發(fā)生Cache命中，對(duì)于性能來(lái)說(shuō)都是一樣的。下級(jí)本地碼被替換時(shí)會(huì)從Cache中替換出去，而上級(jí)本地碼被替換時(shí)被換到下級(jí)Cache中。這樣做是為了讓熱度較高的代碼能更長(zhǎng)時(shí)間地存留在Cache中。兩級(jí)Cache的內(nèi)部結(jié)構(gòu)相同，都采用兩種不同的粒度劃分。粗粒度的基本單位是Region，大小相同，組織成雙向循環(huán)鏈表的形式。細(xì)粒度的基本單位是Chunk，是對(duì)Region的進(jìn)一步劃分。每個(gè)Chunk存儲(chǔ)一個(gè)x86代碼塊對(duì)應(yīng)的本地碼，因此Chunk大小不確定。如果一塊本地碼超過(guò)Region大小，可以把這塊本地碼拆開(kāi)存儲(chǔ)在多個(gè)Region中，第2.5節(jié)會(huì)具體分析這種情況的性能。Region是替換和提升的最小單位；而Chunk是分配的最小單位。

2.3 LRC策略核心算法

LRC策略的核心算法主要是兩級(jí)Cache如何進(jìn)行分配、替換管理以及下級(jí)Cache中的Region向上級(jí)提升的條件判斷和操作。為了維持兩級(jí)Cache在空間上的比例，當(dāng)下級(jí)Region提升時(shí)，要與上級(jí)Cache交換一個(gè)Region。下級(jí)Cache采用類(lèi)似于FIFO的管理策略，同時(shí)在適當(dāng)?shù)臅r(shí)機(jī)循環(huán)遍歷整個(gè)下級(jí)Cache，把符合條件的Region向上級(jí)提升。上級(jí)Cache的管理策略與提升的條件密切相關(guān)。在LRC策略中，把一個(gè)Region中所有Chunk的執(zhí)行次數(shù)之和作為這個(gè)Region的執(zhí)行次數(shù)進(jìn)行提升判斷。主要提出三種備選的提升條件，并會(huì)在后面通過(guò)實(shí)驗(yàn)數(shù)據(jù)加以對(duì)比。

（1）把下級(jí)Cache中執(zhí)行次數(shù)最大的Region與上級(jí)Cache的遍歷指針指向的Region相比。若下級(jí)Region的次數(shù)大于上級(jí)Region的次數(shù)則交換這兩個(gè)Region。上級(jí)Cache采用FIFO策略。

（2）把下級(jí)Cache中執(zhí)行次數(shù)最大的Region與上級(jí)Cache中執(zhí)行次數(shù)最小的Region相比。若下級(jí)Region的次數(shù)大于上級(jí)Region的次數(shù)則交換這兩個(gè)Region。上級(jí)Cache按照Region的熱度進(jìn)行管理，淘汰執(zhí)行次數(shù)最小的Region。

（3）把下級(jí)Cache中執(zhí)行次數(shù)最大的Region與所有Region執(zhí)行次數(shù)和的某個(gè)百分比進(jìn)行比較。若大于則提升。上級(jí)Cache采用FIFO策略。由于比較的時(shí)候只是程序執(zhí)行到某個(gè)階段的累積，并不代表執(zhí)行的整個(gè)過(guò)程。這個(gè)百分比不宜過(guò)大，應(yīng)設(shè)為20%。

具體的算法描述如下：初始化時(shí)把待分配的空閑Region指針指向下級(jí)Cache的第一個(gè)Region。需要分配Chunk時(shí)，在下級(jí)Cache中待分配的空閑Region中按地址從低到高進(jìn)行分配。如果待分配的空閑Region的剩余空間不夠，把這個(gè)Region標(biāo)記為已滿(mǎn)；將待分配的空閑Region指針指向下一個(gè)Region。如果這個(gè)新的Region是空的，就直接在這個(gè)Region中分配；若這個(gè)新的Region已滿(mǎn)，說(shuō)明整個(gè)下級(jí)Cache都被分配了。這就要在下級(jí)Cache中進(jìn)行提升條件的判斷，試圖尋找一個(gè)可以提升的Region。若沒(méi)有可提升的Region，直接對(duì)待分配的空閑指針指向的Region進(jìn)行替換操作，并在這個(gè)Region中分配Chunk。若存在可提升的Region，把可提升的Region按照提升條件中的規(guī)則與上級(jí)Cache中的某個(gè)Region交換。從上級(jí)Cache中交換下來(lái)的Region如果是空的，直接在這個(gè)空Region上分配；如果已滿(mǎn)，則仍要對(duì)待分配的空閑指針指向的Region進(jìn)行替換操作，然后再分配本地碼空間。以后每次遇到下級(jí)Cache已滿(mǎn)的情況都要進(jìn)行提升的判斷。

2.4 對(duì)算法有影響的參數(shù)

LRC策略中主要開(kāi)銷(xiāo)有三方面：Cache維護(hù)開(kāi)銷(xiāo)、提升開(kāi)銷(xiāo)和替換開(kāi)銷(xiāo)。Cache維護(hù)時(shí)的操作基本是固定操作，可以假設(shè)單位空間上的維護(hù)開(kāi)銷(xiāo)是定值。提升開(kāi)銷(xiāo)主要包括提升條件判斷開(kāi)銷(xiāo)和上下級(jí)Region交換的開(kāi)銷(xiāo)。交換Region是固定開(kāi)銷(xiāo)；而條件判斷開(kāi)銷(xiāo)要對(duì)整個(gè)Cache進(jìn)行遍歷，與Cache和Region的大小相關(guān)。替換開(kāi)銷(xiāo)主要是替換后的斷鏈和不命中造成的開(kāi)銷(xiāo)，執(zhí)行速度會(huì)下降很多。在LRC策略中，Cache大小、Region大小和提升條件是三個(gè)關(guān)鍵的參數(shù)；它們的取值直接影響著這三種開(kāi)銷(xiāo)。

代碼Cache大小對(duì)于三種開(kāi)銷(xiāo)都有一定的影響。因?yàn)閱挝豢臻g上的維護(hù)開(kāi)銷(xiāo)是定值，所以Cache維護(hù)開(kāi)銷(xiāo)是Cache大小的遞增函數(shù)。為了減小維護(hù)開(kāi)銷(xiāo)，就要求Cache變小。由于進(jìn)行提升條件判斷時(shí)要對(duì)整個(gè)Cache進(jìn)行遍歷，總的來(lái)說(shuō)提升開(kāi)銷(xiāo)是關(guān)于Cache大小的遞增函數(shù)，為了降低提升開(kāi)銷(xiāo)，Cache應(yīng)該減小。但是Cache越大，容納的本地碼就越多，不命中的可能性和斷鏈帶來(lái)的性能降低也就越小。因此替換開(kāi)銷(xiāo)是Cache大小的遞減函數(shù)。綜合這三種開(kāi)銷(xiāo)，應(yīng)該選擇一個(gè)極值點(diǎn)作為Cache的大小。

Region大小主要對(duì)提升開(kāi)銷(xiāo)和替換開(kāi)銷(xiāo)的影響很大。Region如果過(guò)大，對(duì)于提升開(kāi)銷(xiāo)來(lái)說(shuō)，因?yàn)镽egion過(guò)大，在Cache大小一定的情況下，Region的個(gè)數(shù)就少，那么判斷提升條件時(shí)循環(huán)的次數(shù)就少，提升開(kāi)銷(xiāo)也會(huì)小；但是對(duì)于替換開(kāi)銷(xiāo)，因?yàn)樘鎿Q的Region過(guò)大，不命中的可能性和斷鏈的次數(shù)都會(huì)增大，替換開(kāi)銷(xiāo)也會(huì)增大。Region過(guò)小的情況正好與此相反。因此，應(yīng)該選擇一個(gè)合適的Region大小。

提升的條件對(duì)于程序的性能也有很大的影響。提升開(kāi)銷(xiāo)和替換開(kāi)銷(xiāo)雖然是Cache大小和Region大小的遞增或遞減函數(shù)，但是好的提升條件，會(huì)使開(kāi)銷(xiāo)增長(zhǎng)的速度減慢。因?yàn)樗鼤?huì)把熱度較高的本地碼都留在上級(jí)代碼Cache中，進(jìn)一步減小不命中的機(jī)會(huì)，降低斷鏈帶來(lái)的性能影響。

2.5 算法性能分析

翻譯優(yōu)化器按程序的執(zhí)行流來(lái)翻譯源程序，形成目標(biāo)機(jī)本地代碼塊。采用LRC策略的代碼Cache按地址從低到高來(lái)組織Region。Region內(nèi)也按地址從低到高來(lái)劃分Chunk。這樣與程序流在邏輯上保持了空間上的一致性。

LRC策略是全清空、FIFO和多級(jí)Cache思想的綜合，兼具了它們的優(yōu)點(diǎn)，回避了其缺點(diǎn)。替換操作對(duì)于Region內(nèi)部來(lái)說(shuō)相當(dāng)于全清空，避免了為分配一個(gè)代碼塊而發(fā)生多次替換。但這種全清空的范圍不是整個(gè)Cache，LRC相比全清空策略有更高的命中率和更少的斷鏈次數(shù)。Region間的管理是類(lèi)似于FIFO的操作，因此具有FIFO策略的優(yōu)點(diǎn)，很好地考慮了程序的時(shí)間局部性。但分級(jí)思想使得熱度較高的Region進(jìn)入上級(jí)Cache，能夠長(zhǎng)時(shí)間地保留；而單純的FIFO策略，由于沒(méi)有考慮程序的執(zhí)行特性，很可能把熱度較高的代碼塊替換出去，導(dǎo)致了過(guò)多的換入換出的抖動(dòng)現(xiàn)象。對(duì)于那種不分級(jí)而只分雙粒度的策略（Region－Chunk，RC）來(lái)說(shuō)，其相當(dāng)于一種粗糙的FIFO，沒(méi)有考慮Region的熱度，因此在性能上也不如LRC策略。

LRC策略很好地考慮了時(shí)間空間局部性和程序執(zhí)行特性，具有較好的性能。由2.4節(jié)的分析可知，Region過(guò)大或者過(guò)小都會(huì)對(duì)提升開(kāi)銷(xiāo)和替換開(kāi)銷(xiāo)有影響。為了得到較小的開(kāi)銷(xiāo)，就應(yīng)該綜合考慮Region的大小。因此可以得出一個(gè)結(jié)論，即中等粒度LRC策略的性能較好。這里粗粒度的極限就是全清空，細(xì)粒度的極限就是FIFO。

LRC策略的一個(gè)不足之處是有碎片產(chǎn)生。如果待分配的空閑Region的剩余空間不夠分配，就會(huì)轉(zhuǎn)向它的下一個(gè)Region，這樣就出現(xiàn)了碎片。如果導(dǎo)致待分配空閑Region的剩余空間不足的本地碼過(guò)大，那碎片就會(huì)很大；而且當(dāng)本地碼大到超過(guò)Region大小時(shí)，會(huì)把這塊本地碼存儲(chǔ)在多個(gè)Region中，帶來(lái)額外的維護(hù)開(kāi)銷(xiāo)。不過(guò)，從表2中可知，本地碼的平均大小約為170 Bytes。因此出現(xiàn)比較大的本地碼的幾率非常小，對(duì)時(shí)間和空間的影響也就可以忽略不計(jì)。而且由于Region的替換，當(dāng)前Region中的碎片會(huì)因?yàn)橐院蟮幕厥斩辉俅卫谩＊?/p>

3 算法實(shí)現(xiàn)及實(shí)驗(yàn)結(jié)果

LRC策略已經(jīng)在動(dòng)態(tài)二進(jìn)制翻譯系統(tǒng)Digital Bridge上得到實(shí)現(xiàn)，通過(guò)了大量測(cè)試用例的驗(yàn)證，并且與其他策略在Digi－tal Bridge系統(tǒng)上進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果表明LRC策略能夠?qū)崿F(xiàn)對(duì)代碼Cache的高效管理。

3.1 Digital Bridge系統(tǒng)簡(jiǎn)介

Digital Bridge系統(tǒng)是從x86/Linux平臺(tái)到MIPS/Linux平臺(tái)的動(dòng)態(tài)二進(jìn)制翻譯系統(tǒng)。總框架如圖1所示。該系統(tǒng)主要由BT控制器、文件加載器、解釋器、庫(kù)函數(shù)調(diào)用處理、動(dòng)態(tài)信息管理器、本地碼執(zhí)行器、翻譯優(yōu)化器、代碼Cache管理器和后臺(tái)翻譯優(yōu)化器組成。LRC策略主要是實(shí)現(xiàn)在代碼Cache管理器這一模塊上。

3.2 關(guān)鍵參數(shù)的確定

3.2.1 提升條件的確定

比較第2.3節(jié)中的三種提升條件，通過(guò)對(duì)這三種條件下程序運(yùn)行時(shí)間和Cache不命中次數(shù)的比較得出最好的提升條件。為了更好地突出提升條件對(duì)于替換的影響，把Cache的大小設(shè)定為200 KB，Region的大小設(shè)定為10 KB。測(cè)試用例選擇SPEC CPU2000 INT中bzip2和gzip的Test測(cè)試集。因?yàn)檫@兩個(gè)Benchmark的時(shí)間局部性較明顯、熱度較高的代碼塊較為集中。具體測(cè)試數(shù)據(jù)如表1所示。

從表1的數(shù)據(jù)可以看出，不論是運(yùn)行時(shí)間還是Cache不命中次數(shù)，條件(2)的數(shù)據(jù)都要好于其他兩種條件。在表中最后一列的統(tǒng)計(jì)中，條件(2)的數(shù)據(jù)大于其他兩種條件，說(shuō)明它發(fā)生了更多的提升。提升次數(shù)增多雖然增大了開(kāi)銷(xiāo)，但是由于程序按階段執(zhí)行的特性，程序的熱點(diǎn)會(huì)隨著時(shí)間而改變，淘汰那些當(dāng)前不再執(zhí)行但是熱度仍很高的本地碼，有利于把正在執(zhí)行的熱度高的本地碼提升到上級(jí)Cache中，進(jìn)一步提高性能。不命中次數(shù)這項(xiàng)統(tǒng)計(jì)也恰恰說(shuō)明了這點(diǎn)。因此在以后的實(shí)驗(yàn)中，都會(huì)選擇條件（2）作為提升的判斷依據(jù)。

3.2.2 Cache大小的確定

表2是SPEC CPU2000 INT中九個(gè)Benchmark Test測(cè)試集的一些統(tǒng)計(jì)信息。通過(guò)這些信息可以知道本地碼的大小、x86代碼塊的執(zhí)行總次數(shù)、x86代碼塊的個(gè)數(shù)、平均每個(gè)代碼塊的執(zhí)行次數(shù)和平均每個(gè)Block的本地碼大小。這九個(gè)Benchmark本地碼的平均大小是850 KB左右。為了能夠體現(xiàn)LRC策略的性能，把Cache的大小定為512 KB。根據(jù)實(shí)驗(yàn)擬合，Cache大小為512 KB時(shí)的性能也較好。

3.2.3 Region大小的確定

前面第2.5節(jié)對(duì)于LRC策略的性能分析，得出中等粒度的LRC策略性能最優(yōu)，而粗粒度和細(xì)粒度在向中等粒度過(guò)渡的過(guò)程中，性能逐漸變好。這一節(jié)將通過(guò)九個(gè)Benchmark的Test測(cè)試集運(yùn)行時(shí)間的對(duì)比來(lái)驗(yàn)證這個(gè)結(jié)論。其中，Cache的大小設(shè)為512 KB；Region的大小是變化的。

圖2是九個(gè)Benchmark在六種Region大小時(shí)運(yùn)行時(shí)間的測(cè)試數(shù)據(jù)。通過(guò)對(duì)比發(fā)現(xiàn)，bzip2、gzip、mcf在時(shí)間對(duì)比上不明顯。尤其是bzip2還有與結(jié)論相反的表現(xiàn)。這主要是因?yàn)檫@三個(gè)Benchmark的本地碼小于512 KB，所以基本不發(fā)生替換。但對(duì)于本地碼較大的Benchmark，如crafty、parser、vpr和perlbmk，可以發(fā)現(xiàn)Region大小為24 KB時(shí)性能最好。gap除了Region大小為4 KB時(shí)性能最好以外，其余的Region大小仍符合這個(gè)結(jié)論；也是Region大小為24 KB時(shí)性能最好。綜合來(lái)看，第2.5節(jié)中的結(jié)論得到了實(shí)驗(yàn)數(shù)據(jù)的支持。

3.3 與其他策略的數(shù)據(jù)對(duì)比

最后將LRC策略和全清空、FIFO、RC三種策略的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行對(duì)比來(lái)說(shuō)明LRC策略?xún)?yōu)于這些策略。主要是對(duì)比九個(gè)Benchmark分別應(yīng)用這四種策略的運(yùn)行時(shí)間，如圖3所示。這四種策略的Cache大小選擇512 KB。其中LRC策略和RC策略的Region大小選擇24 KB。

從圖3中可以發(fā)現(xiàn)，bzip2、gzip、mcf這三個(gè)Benchmark仍然在數(shù)據(jù)對(duì)比上不明顯。原因與3.2節(jié)相同。但是對(duì)于其他Benchmark，LRC策略在性能上都要優(yōu)于其他策略。RC策略的性能僅次于LRC策略。總的來(lái)說(shuō)，LRC策略相對(duì)于全清空策略性能提高了7.43%；相對(duì)于FIFO策略性能提高了5.16%；相對(duì)于RC策略性能提高了2.73%。

4 結(jié)束語(yǔ)

本文提出了一種代碼Cache的分級(jí)雙粒度管理策略——LRC策略。它綜合了全清空策略、FIFO策略、分級(jí)Cache的思想，兼具它們的優(yōu)點(diǎn)，同時(shí)也在一定程度上回避了它們各自的缺點(diǎn)。這個(gè)策略綜合考慮了程序的時(shí)空局部性、提升開(kāi)銷(xiāo)和替換開(kāi)銷(xiāo)，實(shí)現(xiàn)了代碼Cache的高效管理。LRC策略在性能上比全清空策略、FIFO策略和只分粒度不分級(jí)的RC策略都要有一定程度的提高。尤其是本地碼較大、需要大量替換操作時(shí)，性能提高更為突出。

LRC策略在提高性能的同時(shí)也帶來(lái)碎片問(wèn)題，存在一定的空間浪費(fèi)，這一點(diǎn)有待進(jìn)一步的提高。同時(shí)下級(jí)Cache中Region向上級(jí)提升的條件模型有待進(jìn)一步挖掘。

本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。