二進制翻譯中代碼Ｃａｃｈｅ的分級雙粒度管理策略

摘 要：提出一種二進制翻譯中代碼Cache管理的LRC（Level－Region－Chunk）策略。其兼具全清空策略、FIFO策略和多級Cache的優點，并且考慮了程序的時間空間局部性、執行特性和替換開銷，具有較好的性能，實現了代碼Cache的高效管理。

關鍵詞：二進制翻譯；代碼Cache；LRC策略

中圖分類號：TP319文獻標志碼：A

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

二進制翻譯技術是目前解決軟件移植問題的一個研究熱點，能將現有的軟件移植到新開發的處理器上執行。基于軟件的二進制翻譯系統主要分為解釋器、靜態翻譯器和動態翻譯器三種。動態二進制翻譯系統的基本原理是這樣的：動態翻譯執行源體系結構的二進制代碼，收集Profile信息；通過反饋信息對執行頻度較高的代碼采用簡單高效的策略進行深度優化，得到效率更高的目標機本地代碼。

動態二進制翻譯中一類比較重要的問題是如何管理翻譯出來的目標機本地代碼，既要盡可能少地占用內存空間，又要減少由于代碼Cache的替換操作造成的性能下降。本文通過對常用的代碼Cache管理策略進行分析，提出一種新的代碼Cache管理策略LRC（Level－Region－Chunk）。LRC策略結合了全清空、FIFO和多級Cache等方法的優點，具有分級雙粒度的特點，Cache不命中率小；并且考慮到程序的時間空間局部性和Cache替換開銷，實現了對代碼Cache的高效管理。

1 常見的Cache管理策略

代碼Cache是指軟件模擬Cache的行為，在內存中開辟一塊空間來存儲翻譯出來的目標機本地碼。在介紹LRC策略之前，先介紹動態二進制翻譯系統和動態優化系統中常用的幾種代碼Cache管理策略。

（1）不替換策略

不替換策略就是在代碼Cache中從低地址到高地址依次存放每個代碼塊。由于空間足夠大，不會出現本地碼的替換，只有本地碼第一次翻譯時發生Cache不命中。這種策略是用大量犧牲內存的方式來換取時間上的優勢，但是會給硬件的內存容量帶來壓力。尤其是那些嵌入式系統中，由于內存容量有限，對內存使用量的限制非常嚴格。這種策略并不可取，不作為LRC策略的實驗對比對象。

（2）全清空策略

全清空策略是在代碼Cache中從低地址到高地址依次存放每個代碼塊。當Cache空間不足或程序階段行為突變時，清空整個Cache。許多動態二進制翻譯系統和動態優化系統都采用這個策略，如Walkabout和Dynamo。其優點是算法簡單、容易實現、管理開銷較小；但是沒有考慮程序的時間和空間局部性，也沒有考慮程序的執行特性，會把很多比較熱的代碼塊替換出去，導致很多代碼塊的重復換入換出。這種抖動現象降低了程序的性能。

（3）FIFO策略

FIFO策略是在代碼Cache中從低地址到高地址依次存放每個代碼塊。當Cache空間不足時，按FIFO順序把最先進入Cache的代碼塊替換出去。如果空間仍然不足，就繼續把物理上相鄰的代碼塊替換出去，直至有足夠的空間來存放代碼塊。DynamoRIO系統就采用這種策略。FIFO策略在一定程度上考慮了程序執行的階段性特征。被替換出去的代碼塊是當前Cache中最先生成的代碼塊，因此有可能已經不再是執行的熱點。這種策略的執行效率較高；但是它沒有考慮程序的執行特性，也沒有考慮減少代碼塊換出的次數從而減少管理的開銷，而且先生成的代碼塊也未必應該先被替換出Cache。因為代碼的熱度不取決于進入Cache的順序。在性能上仍然存在一定的局限性。

（4）其他策略

除了上述三種最常用的管理策略外，還存在一些如最近最久未使用（LRU）策略、最大塊優先替換、最適合大小塊優先替換等策略。LRU策略雖然考慮了程序的執行特性和時間局部性，但實現復雜，算法本身的開銷非常大，而且還有碎片產生；后兩種策略只考慮空間的利用效率，而很少考慮程序的時間局部性和執行特性。這些策略很少被動態二進制翻譯系統和動態優化系統采用。

2 LRC策略

2.1 本地碼的鏈接和斷鏈

在翻譯執行目標機本地碼的過程中，存在翻譯控制器與本地碼之間的上下文切換。這個切換要做很多事情。例如保存或恢復機器運行狀態、再優化/再翻譯源程序接下來的指令序列、存儲翻譯優化的本地碼到Cache中等操作，會帶來很大開銷。一種解決辦法就是記錄x86二進制代碼的前驅后繼關系，把本地碼按照邏輯上的執行順序鏈接起來，減少切換次數，直到所需的本地碼不在代碼Cache中，才發生切換來翻譯執行后續的x86代碼。

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

2.2 LRC策略的代碼Cache模型

LRC策略把代碼Cache按照所存儲的本地碼的執行熱度分成上下兩級，大小的比例是1:4。上級Cache存儲熱度較高的本地碼；本地碼首先存入下級Cache，達到一定熱度后會被提升到上級。與硬件多級Cache不同的是：一塊本地碼在整個Cache中只有一個副本，因為代碼Cache是用內存模擬的，無論是在哪一級中發生Cache命中，對于性能來說都是一樣的。下級本地碼被替換時會從Cache中替換出去，而上級本地碼被替換時被換到下級Cache中。這樣做是為了讓熱度較高的代碼能更長時間地存留在Cache中。兩級Cache的內部結構相同，都采用兩種不同的粒度劃分。粗粒度的基本單位是Region，大小相同，組織成雙向循環鏈表的形式。細粒度的基本單位是Chunk，是對Region的進一步劃分。每個Chunk存儲一個x86代碼塊對應的本地碼，因此Chunk大小不確定。如果一塊本地碼超過Region大小，可以把這塊本地碼拆開存儲在多個Region中，第2.5節會具體分析這種情況的性能。Region是替換和提升的最小單位；而Chunk是分配的最小單位。

2.3 LRC策略核心算法

LRC策略的核心算法主要是兩級Cache如何進行分配、替換管理以及下級Cache中的Region向上級提升的條件判斷和操作。為了維持兩級Cache在空間上的比例，當下級Region提升時，要與上級Cache交換一個Region。下級Cache采用類似于FIFO的管理策略，同時在適當的時機循環遍歷整個下級Cache，把符合條件的Region向上級提升。上級Cache的管理策略與提升的條件密切相關。在LRC策略中，把一個Region中所有Chunk的執行次數之和作為這個Region的執行次數進行提升判斷。主要提出三種備選的提升條件，并會在后面通過實驗數據加以對比。

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

（2）把下級Cache中執行次數最大的Region與上級Cache中執行次數最小的Region相比。若下級Region的次數大于上級Region的次數則交換這兩個Region。上級Cache按照Region的熱度進行管理，淘汰執行次數最小的Region。

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

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

2.4 對算法有影響的參數

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

代碼Cache大小對于三種開銷都有一定的影響。因為單位空間上的維護開銷是定值，所以Cache維護開銷是Cache大小的遞增函數。為了減小維護開銷，就要求Cache變小。由于進行提升條件判斷時要對整個Cache進行遍歷，總的來說提升開銷是關于Cache大小的遞增函數，為了降低提升開銷，Cache應該減小。但是Cache越大，容納的本地碼就越多，不命中的可能性和斷鏈帶來的性能降低也就越小。因此替換開銷是Cache大小的遞減函數。綜合這三種開銷，應該選擇一個極值點作為Cache的大小。

Region大小主要對提升開銷和替換開銷的影響很大。Region如果過大，對于提升開銷來說，因為Region過大，在Cache大小一定的情況下，Region的個數就少，那么判斷提升條件時循環的次數就少，提升開銷也會小；但是對于替換開銷，因為替換的Region過大，不命中的可能性和斷鏈的次數都會增大，替換開銷也會增大。Region過小的情況正好與此相反。因此，應該選擇一個合適的Region大小。

提升的條件對于程序的性能也有很大的影響。提升開銷和替換開銷雖然是Cache大小和Region大小的遞增或遞減函數，但是好的提升條件，會使開銷增長的速度減慢。因為它會把熱度較高的本地碼都留在上級代碼Cache中，進一步減小不命中的機會，降低斷鏈帶來的性能影響。

2.5 算法性能分析

翻譯優化器按程序的執行流來翻譯源程序，形成目標機本地代碼塊。采用LRC策略的代碼Cache按地址從低到高來組織Region。Region內也按地址從低到高來劃分Chunk。這樣與程序流在邏輯上保持了空間上的一致性。

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

LRC策略很好地考慮了時間空間局部性和程序執行特性，具有較好的性能。由2.4節的分析可知，Region過大或者過小都會對提升開銷和替換開銷有影響。為了得到較小的開銷，就應該綜合考慮Region的大小。因此可以得出一個結論，即中等粒度LRC策略的性能較好。這里粗粒度的極限就是全清空，細粒度的極限就是FIFO。

LRC策略的一個不足之處是有碎片產生。如果待分配的空閑Region的剩余空間不夠分配，就會轉向它的下一個Region，這樣就出現了碎片。如果導致待分配空閑Region的剩余空間不足的本地碼過大，那碎片就會很大；而且當本地碼大到超過Region大小時，會把這塊本地碼存儲在多個Region中，帶來額外的維護開銷。不過，從表2中可知，本地碼的平均大小約為170 Bytes。因此出現比較大的本地碼的幾率非常小，對時間和空間的影響也就可以忽略不計。而且由于Region的替換，當前Region中的碎片會因為以后的回收而被再次利用。

3 算法實現及實驗結果

LRC策略已經在動態二進制翻譯系統Digital Bridge上得到實現，通過了大量測試用例的驗證，并且與其他策略在Digi－tal Bridge系統上進行了對比。實驗結果表明LRC策略能夠實現對代碼Cache的高效管理。

3.1 Digital Bridge系統簡介

Digital Bridge系統是從x86/Linux平臺到MIPS/Linux平臺的動態二進制翻譯系統。總框架如圖1所示。該系統主要由BT控制器、文件加載器、解釋器、庫函數調用處理、動態信息管理器、本地碼執行器、翻譯優化器、代碼Cache管理器和后臺翻譯優化器組成。LRC策略主要是實現在代碼Cache管理器這一模塊上。

3.2 關鍵參數的確定

3.2.1 提升條件的確定

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

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

3.2.2 Cache大小的確定

表2是SPEC CPU2000 INT中九個Benchmark Test測試集的一些統計信息。通過這些信息可以知道本地碼的大小、x86代碼塊的執行總次數、x86代碼塊的個數、平均每個代碼塊的執行次數和平均每個Block的本地碼大小。這九個Benchmark本地碼的平均大小是850 KB左右。為了能夠體現LRC策略的性能，把Cache的大小定為512 KB。根據實驗擬合，Cache大小為512 KB時的性能也較好。

3.2.3 Region大小的確定

前面第2.5節對于LRC策略的性能分析，得出中等粒度的LRC策略性能最優，而粗粒度和細粒度在向中等粒度過渡的過程中，性能逐漸變好。這一節將通過九個Benchmark的Test測試集運行時間的對比來驗證這個結論。其中，Cache的大小設為512 KB；Region的大小是變化的。

圖2是九個Benchmark在六種Region大小時運行時間的測試數據。通過對比發現，bzip2、gzip、mcf在時間對比上不明顯。尤其是bzip2還有與結論相反的表現。這主要是因為這三個Benchmark的本地碼小于512 KB，所以基本不發生替換。但對于本地碼較大的Benchmark，如crafty、parser、vpr和perlbmk，可以發現Region大小為24 KB時性能最好。gap除了Region大小為4 KB時性能最好以外，其余的Region大小仍符合這個結論；也是Region大小為24 KB時性能最好。綜合來看，第2.5節中的結論得到了實驗數據的支持。

3.3 與其他策略的數據對比

最后將LRC策略和全清空、FIFO、RC三種策略的實驗數據進行對比來說明LRC策略優于這些策略。主要是對比九個Benchmark分別應用這四種策略的運行時間，如圖3所示。這四種策略的Cache大小選擇512 KB。其中LRC策略和RC策略的Region大小選擇24 KB。

從圖3中可以發現，bzip2、gzip、mcf這三個Benchmark仍然在數據對比上不明顯。原因與3.2節相同。但是對于其他Benchmark，LRC策略在性能上都要優于其他策略。RC策略的性能僅次于LRC策略。總的來說，LRC策略相對于全清空策略性能提高了7.43%；相對于FIFO策略性能提高了5.16%；相對于RC策略性能提高了2.73%。

4 結束語

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

LRC策略在提高性能的同時也帶來碎片問題，存在一定的空間浪費，這一點有待進一步的提高。同時下級Cache中Region向上級提升的條件模型有待進一步挖掘。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。