，，

(北京空間飛行器總體設(shè)計部，北京 100094)

0 引言

從國外衛(wèi)星系列的成功發(fā)射可以看出，衛(wèi)星從生產(chǎn)、組裝建造到發(fā)射的時間已從傳統(tǒng)模式的數(shù)月縮短至以小時為單位，并且隨著空間技術(shù)的提高和應(yīng)用需求的擴(kuò)展，星載嵌入式應(yīng)用軟件的功能越來越多，邏輯也越來越復(fù)雜[1]。這些繁多的、復(fù)雜的需求和功能都需要通過完備的軟件測試得以驗證。嵌入式軟件測試的一大特點就是絕大部分測試均需要通過外部激勵觸發(fā)執(zhí)行。對于智能衛(wèi)星這樣的復(fù)雜大系統(tǒng)而言，很多外部激勵需要具備一定的等待時長才能產(chǎn)生。因此，若采用硬件設(shè)備實施嵌入式軟件測試，其測試周期必然是各測試用例等待時間的總和。以衛(wèi)星數(shù)管軟件的熱控邏輯測試為例，遍歷一顆衛(wèi)星的所有熱控回路的測試常常需要24小時不間斷地持續(xù)幾天甚至1周時間，大大影響了衛(wèi)星的研制周期。

為了解決此問題，提出采用全數(shù)字虛擬機(jī)替代硬件目標(biāo)機(jī)實現(xiàn)星載軟件邏輯測試。此方法一方面能夠為星載軟件的前期預(yù)研提供調(diào)試環(huán)境，大大節(jié)約開發(fā)成本，另一方面，如果能夠讓虛擬目標(biāo)機(jī)實現(xiàn)超速運行，也能提高軟件測試的效率，縮短軟件研制周期，從而實現(xiàn)提升軟件質(zhì)量的目的[2]。

QEMU(quick emulator)是一款開源仿真平臺，支持多種處理器的功能仿真，包括x86、PowerPC、ARM 和Sparc系列處理器[3]，目前被業(yè)內(nèi)公認(rèn)為應(yīng)用最廣、效率最高的虛擬機(jī)實現(xiàn)軟件。其采用動態(tài)指令翻譯技術(shù)，在目標(biāo)碼運行時動態(tài)實現(xiàn)將目標(biāo)機(jī)代碼轉(zhuǎn)為宿主機(jī)代碼的過程全過程。但經(jīng)試驗測試，采用QEMU開源代碼搭建的虛擬處理器其指仿真效率僅能達(dá)到20～25 MIPS[4]，遠(yuǎn)不能達(dá)到超速模擬星載軟件運行的效果。

本文提出采用多級隊列緩存淘汰策略對QEMU的動態(tài)指令翻譯實現(xiàn)進(jìn)行改進(jìn)和優(yōu)化。該策略通過提高被翻譯指令塊的重用效率提高仿真處理器的整體處理速度。試驗證明，采用此仿真處理器實現(xiàn)的虛擬目標(biāo)機(jī)不但能夠在正常運行速度下滿足測試需要，還能夠成倍加速目標(biāo)二進(jìn)制代碼的執(zhí)行速度，從而達(dá)到縮短軟件測試周期的目的。相對直接采用QEMU開源代碼實現(xiàn)的仿真處理器，該方法實現(xiàn)的仿真處理器能更高效的完成星載軟件的仿真測試任務(wù)，為提高星載軟件的開發(fā)效率，縮短了軟件開發(fā)周期，提升軟件產(chǎn)品質(zhì)量提供有力保障。

1 影響指令集仿真速度因素分析

QEMU的動態(tài)指令編譯系統(tǒng)由4個模塊和一塊緩存組成，如圖1所示。

圖1 動態(tài)翻譯系統(tǒng)模塊組成

目標(biāo)機(jī)二進(jìn)制可執(zhí)行代碼載入和初始化模塊是系統(tǒng)啟動后首先調(diào)用的模塊，通過建立客戶端棧和客戶端數(shù)據(jù)空間等建立客戶端運行環(huán)境。前端解碼器負(fù)責(zé)將二進(jìn)制指令碼生成中間代碼塊；后端編譯器負(fù)責(zé)將中間代碼塊翻譯為客戶機(jī)可識別的二進(jìn)制代碼。如如建立客戶端棧和客戶端數(shù)據(jù)空間等。然后前端翻譯模塊將目標(biāo)二進(jìn)制代碼分割為相對短小、簡單的指令集，稱為“微操作”。每個“微操作”均由一小段C函數(shù)實現(xiàn)，且每個C函數(shù)均被GCC編譯為一個對象文件(基本代碼塊)。“微操作”由大量實驗精選產(chǎn)生，其數(shù)量遠(yuǎn)小于目標(biāo)CPU的指令和操作數(shù)的所有組合，且由其組成的集合能夠完整表示不同指令集體系下的所有指令。為了增強“微操作”的可讀性和緊湊性，從目標(biāo)機(jī)可執(zhí)行代碼到“微操作”的轉(zhuǎn)換完全通過人工編寫代碼實現(xiàn)。由于此轉(zhuǎn)換過程是在目標(biāo)機(jī)代碼執(zhí)行前完成的，此部分的轉(zhuǎn)換效率并不直接影響仿真處理器的處理速度。

代碼運行時，若動態(tài)指令翻譯模塊發(fā)現(xiàn)有未被翻譯的“基本代碼塊”，則調(diào)用后端翻譯模塊將其翻譯為宿主機(jī)能夠識別和執(zhí)行的主機(jī)代碼，將翻譯結(jié)果存儲在緩存中，并執(zhí)行，否則直接跳轉(zhuǎn)到翻譯代碼地址處直接執(zhí)行。鑒于由于此操作是在目標(biāo)機(jī)代碼執(zhí)行過程中實時進(jìn)行的，此步驟的執(zhí)行效率將直接影響和決定仿真處理器的執(zhí)行速度。

2 QEMU緩存淘汰策略的問題

如圖1所示，動態(tài)指令編譯系統(tǒng)內(nèi)包含一個地址連續(xù)的存儲空間。系統(tǒng)用該空間緩存所有被翻譯過的指令塊TBs(Translated Blocks)，并采用鏈表的方式將所有TB關(guān)聯(lián)起來，如圖2所示。鏈表中每個“TB”都擁兩個指針，分別指向跳 轉(zhuǎn)到當(dāng)前“TB”的上一個“TB”的地址和當(dāng)前“TB”跳轉(zhuǎn)至的下一個“TB”的地址。隨著目標(biāo)機(jī)代碼的不斷執(zhí)行，鏈表上各“TB”之間的關(guān)聯(lián)關(guān)系不斷得到完善，指令集仿真的執(zhí)行效率也會隨之提高。但隨著執(zhí)行時間持續(xù)增加，也會引發(fā)另一個問題，就是翻譯代碼緩存空間會被占滿。為了實現(xiàn)簡便，一旦緩存空間被占滿，QEMU會將該空間全部清空[5]。

圖2 指令集轉(zhuǎn)換原理

可見，當(dāng)控制流從一個基本代碼塊跳轉(zhuǎn)到另一個基本代碼塊時，若可以根據(jù)TB指針直接跳轉(zhuǎn)執(zhí)行，則可以節(jié)省很多上下文切換的開銷，保持仿真系統(tǒng)的高效執(zhí)行。但如果因為緩存空間不夠?qū)е麓鎯υ谄渲械腡Bs被全部清空或某個TB的被新的TB所替換，則直接跳轉(zhuǎn)的鏈路將被打斷。此時對于一個需要執(zhí)行的基本塊，仿真系統(tǒng)或者按照全系統(tǒng)查找的方法在緩存區(qū)中找到其對應(yīng)的TB執(zhí)行，或者在根本找不到對應(yīng)的TB時，重新將該基本快翻譯為TB，存入緩存，并利用鏈表重新建立各TB間的關(guān)聯(lián)關(guān)系，然后才能執(zhí)行該基本塊的代碼。顯然，此時仿真速度將大大降低。

為了改善上述問題，提出采用多級隊列的緩存淘汰策略替代原有的緩存清空策略，實現(xiàn)提高指令集仿真速度的目的。

3 多級隊列緩存淘汰算法實現(xiàn)

3.1 多級隊列緩存淘汰算法分析

多級隊列緩存淘汰算法的原理是根據(jù)訪問頻率將“TB”塊劃分至多個隊列，不同的隊列具有不同的訪問優(yōu)先級，優(yōu)先緩存在目標(biāo)代碼執(zhí)行過程中調(diào)用次數(shù)多的TB。如圖3所示，該算法的具體實現(xiàn)方法如下：

圖3 多級緩存淘汰算法示意

1)仿真系統(tǒng)調(diào)用某個“TB”后，將其插入隊列Q0。

2)針對翻譯緩存中的每一個隊列，根據(jù)其中掛接的“TB”塊的歷史訪問記錄實施淘汰策略，其原則是：如果某個“TB”塊剛被調(diào)用過，則其被再次訪問的概率也最高。實現(xiàn)方法如下：

(1)最新被調(diào)用的“TB”塊插入鏈表頭部；

(2)當(dāng)隊列中的某個“TB”塊被再次調(diào)用后，該“TB”塊被移至鏈表頭部；

(3)當(dāng)鏈表存滿時，丟棄鏈表尾部的“TB”塊。

3)當(dāng)“TB”塊被調(diào)用的次數(shù)到達(dá)升級門限時，將該“TB”塊從當(dāng)前隊列刪除，加入到高一級隊列的頭部；

4)為了防止高優(yōu)先級“TB”塊永遠(yuǎn)霸占最高優(yōu)先級隊列空間，當(dāng)“TB”塊在閾值門限時間段內(nèi)沒有被再次調(diào)用時，對其做降級處理，將其從當(dāng)前隊列刪除，加入到低一級的隊列頭部；

5)當(dāng)翻譯緩存存滿需要淘汰“TB”時，從最低一級隊列QN開始按照步驟2)中給出的策略淘汰“TB”；每個隊列淘汰“TB”時，將其從隊列中刪除，并將其索引加入歷史隊列頭部；

6)如果某個“TB”在歷史隊列中被重新調(diào)用，就可以重新計算該“TB”塊的優(yōu)先級，將其移到優(yōu)先級最低的隊列頭部；

7)歷史隊列按照同樣按照步驟2)中的策略淘汰“TB”塊的索引。

多級隊列緩存淘汰算法解決了翻譯指令緩存占滿后清空造成的指令仿真速度降低的問題，同時能夠避免采用單隊列的LRU算法造成的“緩存污染”問題，數(shù)據(jù)重用命中率大大高于LRU算法。但是鑒于多級隊列緩存緩存淘汰算法需要維護(hù)多個隊列，且需要維護(hù)每個數(shù)據(jù)訪問時間，復(fù)雜度稍高，因此在具體工程實踐中需要根據(jù)業(yè)務(wù)需要和對數(shù)據(jù)的訪問情況適當(dāng)選擇隊列數(shù)量。

3.2 算法實現(xiàn)

本文根據(jù)被仿真處理器的應(yīng)用場景，即其應(yīng)用在航天領(lǐng)域，其上運行的代碼為星載應(yīng)用軟件的實際情況，選擇采用二級隊列實現(xiàn)多級隊列淘汰緩存算法。

首先將整個翻譯指令塊緩存空間分割為兩個隊列，分割比例為2：1。第一個隊列長度占總緩存空間的三分之二，用于記錄翻譯指令塊的訪問歷史。具體而言，當(dāng)某個翻譯指令塊第一次被調(diào)用后，將其加入此列表。當(dāng)此列表空間被占滿而需要通過淘汰已有翻譯指令塊騰出隊列空間時，則按照先進(jìn)先出的原則丟棄此列表中被調(diào)用次數(shù)小于35的翻譯指令塊。反之，若此隊列中某個翻譯指令塊的訪問次數(shù)超過35次，則將該翻譯指令塊索引從當(dāng)前隊列刪除，同時將其插入第二個緩存隊列頭部。

第二個緩存隊列占總翻譯指令塊緩存空間的三分之一，用于根據(jù)歷史訪問記錄存儲翻譯指令塊。其排序原則是，總是保持最新被調(diào)用的翻譯指令塊排在最靠近鏈表頭部的為止。如此，當(dāng)此隊列排滿必須淘汰某個翻譯指令塊時，只需要淘汰排在隊列最末尾的翻譯指令塊即可。

3.3 加速仿真實現(xiàn)

采用上節(jié)中介紹的多級隊列緩存淘汰算法，在原有QEMU處理器仿真模型的框架下實現(xiàn)仿真處理器。為了實現(xiàn)加速仿真并準(zhǔn)確計算仿真處理器與目標(biāo)處理器之間的頻率比例，對QEMU系統(tǒng)時鐘進(jìn)行分析。

QEMU系統(tǒng)中有3個時鐘，分別為REALTIME、VIRTUA時鐘和HOST時鐘。REALTIME時鐘是通過直接獲取宿主機(jī)CPU時鐘信息來計時； VIRTUAL時鐘通過仿真處理器執(zhí)行的指令數(shù)來計時；HOST時鐘則是直接從宿主操作系統(tǒng)中獲取時間信息。

通過實際測量的方法估計仿真處理器與目標(biāo)處理器之間的運行速度比。采用VIRTUAL時鐘記時測算仿真處理器的運行速率可以屏蔽宿主機(jī)本身其性能對測算結(jié)果的影響，因此采用該時鐘進(jìn)行運行速度比估算。設(shè)計一段由CPU計算密集型指令組成的測試代碼(不考慮I/O指令對運行速度的影響)。在仿真處理器上運行該測試代碼，同時在目標(biāo)處理器上運行同一段測試代碼，記錄兩次運行時間并計算二者之間的比值，將該值稱為“最大加速率”。當(dāng)用戶在采用仿真處理器運行目標(biāo)代碼時，可以根據(jù)測試項目需要，在1到“最大加速率”之間任選一值。當(dāng)選1時，表示仿真處理器的運行速度與目標(biāo)處理器一致；當(dāng)選“最大加速率”時，表示仿真處理器的運行速度為目標(biāo)處理器的“最大加速率”倍；當(dāng)選二者之間的任意其他值時，仿真處理器該值大小等比例放緩仿真處理器執(zhí)行速度，實現(xiàn)按需模擬的目的。

4 實驗結(jié)果

4.1 實驗環(huán)境

仿真處理器宿主機(jī)CPU為2.2 G的Intel(R)Core(TM)i7處理器，目標(biāo)系統(tǒng)為Linux-13.04版。仿真處理器基于QEMU- 2.6.1版本，并在該版本基礎(chǔ)上，采用多級隊里緩存淘汰算法對TB緩存淘汰策略進(jìn)行優(yōu)化實現(xiàn)。

被仿真處理器為我國自主研制BM3803處理器，該處理器設(shè)計面向空間應(yīng)用，是我目前國星載計算機(jī)的常用芯片，其主頻可達(dá)20 MHz，具有32位精簡指令系統(tǒng)(RISC)[6]。芯片內(nèi)部包含整數(shù)處理單元(IU)、浮點數(shù)處理單元(FPU)、獨立的指令和數(shù)據(jù)緩存(Cache)、硬件乘法器、除法器等，指令分為加載/存儲，算術(shù)/邏輯/移位，控制轉(zhuǎn)移，讀/寫控制寄存器，浮點操作等指令。

選取采用國產(chǎn)BM3803處理器的某衛(wèi)星中心計算機(jī)為實驗對象，針對加載在其內(nèi)部的嵌入式應(yīng)用軟件進(jìn)行測試。測試環(huán)境構(gòu)成如圖4所示，由外圍輔助測試系統(tǒng)和被測系統(tǒng)組成。外圍輔助測試系統(tǒng)由測試激勵模塊和遙測處理模塊組成；被測系統(tǒng)由仿真處理器及其外圍總線、FPGA模塊等組成。測試時，采用測試腳本通過測試激勵模塊向被測系統(tǒng)注入指令或仿真數(shù)據(jù)，引導(dǎo)被測軟件執(zhí)行各項任務(wù)。

圖4 測試系統(tǒng)結(jié)構(gòu)示意圖

4.2 目標(biāo)應(yīng)用程序

選用某型號星載中心計算機(jī)應(yīng)用程序作為目標(biāo)應(yīng)用程序。首先在硬件目標(biāo)機(jī)上采用硬件處理器對目標(biāo)代碼的遙測、遙控、總線、內(nèi)務(wù)、熱控、能源等功能進(jìn)行測試，然后在仿真處理器上加載相同目標(biāo)代碼，測試相同的功能模塊。二次測試的測試激勵完全一致，通過比較兩次測試得到的測試結(jié)果能夠證明仿真處理器實現(xiàn)的正確性和仿真加速效果的有效性[7]。

4.3 仿真結(jié)果

仿真系統(tǒng)初始化完成后，將某星載計算機(jī)嵌入式應(yīng)用軟件以二進(jìn)制碼流的方式讀取至仿真系統(tǒng)，保存該文件的代碼段、數(shù)據(jù)段和堆棧段地址等基本信息，并根據(jù)上述信息設(shè)置仿真處理器段寄存器，將堆棧指針移至虛擬RAM的起始位置，設(shè)置各虛擬寄存器工作模式，模擬真實硬件處理器的啟動流程，引導(dǎo)虛擬處理啟動并開始運行[8]。

通過動態(tài)指令翻譯模塊接口統(tǒng)計了各目標(biāo)功能模塊的動態(tài)指令數(shù)和仿真時間，得到了采用多級隊列緩存淘汰算法優(yōu)化前后的仿真速度比較結(jié)果，如圖5所示。從圖中可以看出，采用優(yōu)化算法后的仿真速度比優(yōu)化前平均提高了9.3倍。

圖5 優(yōu)化算法前后仿真速比對比

5 結(jié)束語

本文在開源軟件QEMU的動態(tài)指令翻譯基礎(chǔ)上，提出了基于多級隊列緩存淘汰算法的處理器全數(shù)字仿真優(yōu)化實現(xiàn)方法，實現(xiàn)了國產(chǎn)BM3803處理器的全數(shù)字系統(tǒng)仿真。實驗證明，仿真處理器加載星載嵌入式軟件測試能夠正確實現(xiàn)軟件功能、性能需求，且優(yōu)化后的指令集仿真算法比原方法的平均處理速度提高了9倍，為軟件測試提供加速運行途徑。以熱控測試為例，采用本文方法實現(xiàn)的仿真處理器能夠?qū)峥販y試周期從7天縮短為1.5天。大大提高了星載嵌入式軟件確認(rèn)測試的效率，也為縮短軟件研制周期，提升軟件研制質(zhì)量奠定了基礎(chǔ)。

參考文獻(xiàn)：

[1] Shoemaker J，Wright M． 0rbital express space operations architec-

ture program E[A]. International Society for 0ptical Engineering． 0rlando： The International Commission for 0Dtics[C].2003，5088：1-9.

[2] Austin T，Larson E，Enrst D．SimpleSealar：An infrastructure for computer system modeling． IEEE Computer，2002，35(2)：59-67.

[3] Qeemu B F. A fast and portable dynamic translator[A]. Proc. USENIX Annual Tech. Conf.[C].FREENIX Track, 2005:41-46.

[4] Choi J W, Nam B G. Development of high performance space processor emulator based on QEMU-open source dynamic Translator[A]. Conference on Control, Automation and Systems, 2012 12th International Conference[C].2012.

[5] Cmelik B，Keppel D．Shade：A fast instruction—set simulator for execution profiling[A]. Proc of SIGMETRICS Conf on Measurement and Modeling of Computer Systems[C]．New York：ACM，1994：128-137.

[6] Witchel E，Rosenblum M．Embra：Fast and flexible machine simulation[A]. Proc of the ACM SIGMETRICS Int. Conf. on Measurement and Modeling of Computer Systems[C]．New York：ACM，1996，24(1)：68-79.

[7] 北京微電子技術(shù)研究所.BM3803MG 32微空間處理器用戶手冊[Z].北京：北京微電子技術(shù)研究所，2010.

[8] Marques P, Feiteirinha J, Pureza L,et al. cLeonVM: using dynamic translation for developing high-speed space processor emulators[A]. Proc. of the 9th International Workshop on Simulation for European Space Programmes (SESP'2006)[C]. Noordwijk, The Netherlands, 2006.

[9] 張震波,楊鶴標(biāo),馬振華.基于LRU算法的Web系統(tǒng)緩存機(jī)制[J].計算機(jī)工程,2006，32(19):68-70.

[10] 黃 晨 ,汪文明 , 張義超 ,等. 基于國產(chǎn)CPU的并行冗余計算機(jī)系統(tǒng)研究[J]. 計算機(jī)測量與控制, 2017, 25(7):257-259.