指令集仿真器自動生成技術(shù)及其優(yōu)化

孔黎，劉靜

（西北工業(yè)大學(xué) 陜西 西安 710072）

ISS（指令集仿真器）可以讓開發(fā)人員在硬件完成之前就能對系統(tǒng)的正確性進(jìn)行驗證，同時也能使應(yīng)用開發(fā)人員對應(yīng)用設(shè)計的正確性以及效果做出評估。

雖然ISS在芯片以及應(yīng)用開發(fā)中有著不可代替的作用，但傳統(tǒng)的手動編寫的方法不僅需要花費大量的物力人力，效率低下，而且其正確性無法得到很好的保證。嵌入式芯片的更新?lián)Q代越來越快，為了以更快地速度、更低的代價開發(fā)出可靠的ISS，自動生成技術(shù)就成為了必然選擇[1]。

1 ISS自動生成技術(shù)概述

現(xiàn)行的自動生成技術(shù)有2種，即構(gòu)件組裝法和模板構(gòu)造法。這2種方法都有自身的優(yōu)勢與不足，但相對于原先的手動開發(fā)無論從效率還是正確率上都有了很大的提升。

構(gòu)件組裝法是指將ISS的不同部件手工編寫完成后，放入構(gòu)件庫，利用面向?qū)ο蠹夹g(shù)，在開發(fā)新產(chǎn)品的時候，將庫中的構(gòu)件組合連接起來，這樣的方法其實并不是真正意義上的自動生成技術(shù)，而是一種半自動技術(shù)。在對于一些變化不大的部分，使用這種方法是很有效的，但是不同公司的不同版本的芯片之間的體系結(jié)構(gòu)以及指令集都有很大的差距，因此并不是所有的部分都能復(fù)用。

模板構(gòu)造法是通過一些接口語言，對指令集的特征進(jìn)行描述，從而自動生成所需要的ISS。這類接口語言有LISA，nML等。這種方法是通過屏蔽平臺差異的接口語言描述所需仿真平臺的指令集體系結(jié)構(gòu)（ISA），再經(jīng)過自動生成工具產(chǎn)生仿真器部件。這種方法的效率很高，但靈活性不好。

在實際的研制過程中，都采用構(gòu)件與模板構(gòu)造相結(jié)合的方法。對于變動不大的部分，采用構(gòu)件組合的方式，而對于變化非常大的部分則采用自動生成技術(shù)來實現(xiàn)部件的設(shè)計。

一般的解釋型ISS[2]是由幾個固定的模塊組成的，取指，譯碼，路由，執(zhí)行，其運行流程如圖1所示。取指模塊的作用是讀取PC值，到相應(yīng)的位置獲取指令字，并將指令字傳給譯碼模塊；譯碼模塊的作用是將指令字翻譯成指令序號以及并獲取操作數(shù)；路由模塊的作用是根據(jù)譯碼的結(jié)構(gòu)將操作數(shù)傳給正確的執(zhí)行函數(shù)；執(zhí)行則是最后的完成指令功能的C函數(shù)。其中的譯碼模塊以及執(zhí)行模塊是最為繁瑣，最易出錯的部分，ISS開發(fā)的大部分工作量都集中在這兩個模塊上。所以自動生成主要就是這兩部分。

圖1 仿真器執(zhí)行流程Fig.1 Flow of the simulator

2 譯碼模塊的自動生成策略

譯碼的過程實質(zhì)上是識別指令字的過程。這一部件是相對獨立的，它的輸入是指令字，而輸出則是指令標(biāo)志（序號）以及操作數(shù)。任意一條指令都是由操作數(shù)以及操作碼組成的，操作碼的作用是唯一的確定某一條指令；而操作數(shù)則是包含在指令字中，表示指令操作對象的值，操作數(shù)一般包含源操作數(shù)和目標(biāo)操作數(shù)。

DSP芯片一般采用的都是RISC指令集，其指令字的長度是固定的，這就為譯碼的工作帶來了很大的便利。我們把指令字在屏蔽掉操作數(shù)之后的結(jié)果稱為特征碼，指令字與掩碼進(jìn)行按位與運算可以得到特征碼。

譯碼的過程實際上是一個搜索匹配過程，在把指令字與掩碼進(jìn)行按位與運算后得到的數(shù)與指令特征碼進(jìn)行匹配確定指令字所代表的指令。一般的DSP芯片的指令集系統(tǒng)設(shè)計時會將所有的指令分為幾大類，而每一類的指令操作碼的位置是相同的，這樣這一類指令在譯碼是所需要的掩碼也就是一樣的。以Tricore為例，Tricore的指令集中將790條指令分為25大類，而一共使用的掩碼個數(shù)為18個。

在設(shè)計譯碼模塊的時候，將特征碼、掩碼信息以及操作數(shù)位置的信息脫離出來，用配置文件表示，這樣譯碼器就可以針對不同平臺進(jìn)行復(fù)用。在實現(xiàn)的過程中，抽象出一個opcoder類，其中包含了對配置文件進(jìn)行分析的函數(shù)以及執(zhí)行譯碼操作的函數(shù)，opcoder類的定義如下：

為了實現(xiàn)對指令字中操作數(shù)位置的描述，定義了一個操作數(shù)掩碼：

而在配置文件中，指令的操作數(shù)掩碼如下：

11110022223333334444555500000000

32位數(shù)字表示Tricore的指令字長為32位，其中為1的位表示第一個操作數(shù)，4個1表示第一個操作數(shù)占據(jù)了31～28位，2表示第二個操作數(shù)占據(jù)的位數(shù)。在配置文件讀取的過程中，操作數(shù)掩碼是以string形式讀入，通過opcoder:init（）函數(shù)填入operand_maskcode_struct結(jié)構(gòu)體中。

opcoder類定義了針對指令掩碼的vector存儲掩碼列表，對指令進(jìn)行編號，將指令編號與指令特征碼作為一個對存儲在map中。在初始化的過程中，譯碼器從配置文件中獲取相關(guān)信息并將這些信息分類存放在容器中，而在譯碼的時候則從掩碼表中逐個進(jìn)行按位與運算，進(jìn)行匹配，直到找到為止。

這樣的設(shè)計使譯碼模塊具有很好的靈活性，可以進(jìn)行復(fù)用。但由于強(qiáng)調(diào)了通用性，造成其譯碼效率較低。在實際的應(yīng)用中，對于指令集仿真器，最受到關(guān)注的就是它的效率問題。實際上，效率低下是指令集仿真器一直以來的通病，這是顯而易見的，對于一條機(jī)器指令需要用一個C函數(shù)進(jìn)行仿真，C語言沒一條語句都對應(yīng)幾條甚至幾十條x86匯編語句。一般來說，指令集中一條語句對應(yīng)1 000條左右的x86指令。

3 仿真函數(shù)庫的自動生成策略

仿真函數(shù)庫的作用是用高級語言（C/C++）描述指令集中的沒一條指令。一般來說一個C函數(shù)代表一個DSP指令。

仿真函數(shù)的編寫是整個仿真器中工作量最大的一部分，而且其中的重復(fù)工作很多，而且極易出錯，后期的測試也會花費大量的時間來驗證這一部分的正確性。因此，對這一部分的自動化生成有強(qiáng)烈的需求。由于指令集結(jié)構(gòu)（ISA）差異巨大，因此無法使用構(gòu)件組合法。在一般的開發(fā)中，每一款DSP都要重新為其手動編寫仿真函數(shù)庫。在本仿真器的設(shè)計中，使用了模板法自動生成函數(shù)庫，選取nML語言作為描述指令的接口語言[3]。

nML的語法是一個上下文無關(guān)的語法，通常一個上下文無關(guān)的語法可以用一個四元組來表示，G=（N，T，P，S），其中N表示非終止符，T表示終止符，P表示生成規(guī)則，S表示起始符[4]。

nML語言對ISA的描述是由各種規(guī)則組成的，而在nML中有2種生成準(zhǔn)則：

1）OR－rules列出了一個指令部分的所有可選項。

2）AND－rules描述了指令各部分的組成。

使用nML語言自動生成需要對DSP的數(shù)據(jù)類型、主存、寄存器、指令進(jìn)行描述[5]。

指令集仿真器自動生成器主要由兩部分組成，即前端和后端。前端是以nML描述語言描述的模板作為輸入，因此，其任務(wù)就是識別nML語言的規(guī)則，將用戶描述的各種指令以及定義的寄存器等信息收集起來，并存儲到相應(yīng)的數(shù)據(jù)結(jié)構(gòu)之中。這一部分由兩個過程組成，即詞法分析和語法分析。詞法分析的主要任務(wù)是識別nML文件中的各個單詞，并將這些單詞轉(zhuǎn)換成內(nèi)部記號（tokens）表示；語法分析的主要任務(wù)是識別nML語言的語法結(jié)構(gòu)，如“與”規(guī)則，“或”規(guī)則，以及寄存器定義等等，并將這些信息全部記錄到預(yù)先設(shè)計好的各種表格中，這是一個信息收集的過程。信息收集完畢后，我們將這些信息保存到文件中，以便后端使用。

后端的主要工作首先是從中間文件中讀取數(shù)據(jù)，將前端收集到的各種信息還原，然后就是對這些信息進(jìn)行處理，主要包括：①“或”規(guī)則的去除；②將“與”規(guī)則根據(jù)其action屬性轉(zhuǎn)換成相應(yīng)的指令解釋程序，并生成唯一的指令名；③根據(jù)每條指令的image屬性來構(gòu)造譯碼表；④初始化代碼的生成。最后，將處理好的信息按照C語言的格式輸出到外部文件中。

這里之所以使用前端和后端兩部分來構(gòu)成自動生成器，就是為了達(dá)到松散偶合的目的，即前后端的工作都相對獨立，這樣自動生成器的可移植性就會更好[6]。

4 ISS的優(yōu)化

自動生成ISS的有點十分明顯，減少工作量，提高了正確性，但是缺點也是十分突出的，那就是無法根據(jù)不同DSP的ISA特性來對仿真器進(jìn)行優(yōu)化。

通過實驗可以發(fā)現(xiàn)，ISS工作時，主要的時間開銷是在譯碼上，實驗結(jié)構(gòu)表明譯碼的時間大約是執(zhí)行時間的3.7倍，因此優(yōu)化主要是在譯碼模塊進(jìn)行的。

4.1 搜索算法的優(yōu)化

首先，在譯碼的過程中，顯然時間主要花在搜索匹配上。最簡單的設(shè)計就是用順序搜索的算法，逐一與掩碼進(jìn)行按位與運算，為了提高效率，使用hash表的方法。DSP芯片的指令中都包含操作碼（op），這些操作碼代表了這條指令的意義，同一類型的指令往往其op1是相同的，所以，我們選取op1作為哈希函數(shù)的Key值，哈希函數(shù)即為H（Key）=Key。Tricore中一共有790條指令，op1的長度為8位，因此哈希表的入口有256個，理論上平均搜索長度為3左右。在實際中，指令的op1并不是在0-255上均勻分布的，所以平均搜索長度會高于3，經(jīng)過統(tǒng)計之后發(fā)現(xiàn)，平均搜索長度約為5左右。

在自動生成過程中，添加一個配置項，該配置項為指令的op1（或者op）的起始位和結(jié)束位，在Tricore中這兩個數(shù)字為0和7。在獲得op1的位置后，譯碼模塊會根據(jù)其位置以及長度建立相應(yīng)的hash表。

根據(jù)這種方法，聲明哈希表中項的結(jié)構(gòu)：

在class opcoder中加入項：

int init_hash（）；//初始化哈希表的函數(shù)

unsigned int op_mask；//獲取指令op1所需要的掩碼

unsigned int hash_entry_num//哈希表入口的數(shù)量，通過op1的長度來確定

vector>hash_table；//建立的哈希表

通過測試，可以發(fā)現(xiàn)哈希表的搜索速度相對于順序執(zhí)行提高了3倍左右，兩者的測試比較如圖2所示。其中橫軸是指令的數(shù)量，縱軸是運行這些指令所需的時間，單位是秒。

圖2 搜索效率比較Fig.2 Compare of the searching

4.2 動態(tài)預(yù)譯碼策略

所謂預(yù)譯碼[6]，就是在指令執(zhí)行之前對整個可執(zhí)行文件中的指令進(jìn)行預(yù)譯碼，并把譯碼結(jié)果代替原來內(nèi)存位置中裝載的指令。在程序的執(zhí)行過程中，大部分時間都是花在循環(huán)上，而在循環(huán)中，所執(zhí)行的指令是相同的，因此如果反復(fù)地對相同的指令進(jìn)行譯碼就會造成大量資源的浪費。經(jīng)過預(yù)譯碼的處理之后，ISS執(zhí)行的時間大大縮短。但有的大型程序有很多分支路徑，而在實際的運行中，執(zhí)行路徑很短，這樣預(yù)譯碼也會造成大量的浪費。為了解決這個問題，可以采取動態(tài)的指令緩存的方法。即在執(zhí)行的過程中查找緩存中是否有結(jié)果，如果沒有則進(jìn)行譯碼，有就直接執(zhí)行。使用動態(tài)預(yù)譯碼效率與原始效率對比如圖3所示，橫軸表示循環(huán)次數(shù)，縱軸是時間，單位是秒。

圖3 預(yù)譯碼效率比較Fig.3 Predecoding efficiency comparison

在自動生成譯碼模塊的過程中，在class opcoder中添加指令緩存項，改寫譯碼函數(shù)。用一個與可執(zhí)行文件中指令段的大小相同的數(shù)組來表示指令緩存，譯碼結(jié)果存儲在結(jié)構(gòu)體中，而緩存中只記錄這些結(jié)構(gòu)體的地址。

5 結(jié) 論

通過結(jié)合構(gòu)件法與模板構(gòu)造法，能夠快速而高效地生成一款DSP芯片的指令集仿真器，通過對其譯碼模塊的優(yōu)化，能夠大大提高ISS的性能，從而達(dá)到實際的使用要求。

[1]王小紅．指令集仿真器快速生成環(huán)境的研究與實現(xiàn)[D]．北京：北京航空航天大學(xué)，2001.

[2]俞甲子，石凡，潘愛民，等.程序員的自我修養(yǎng)[M].北京：電子工業(yè)出版社，2009.

[3]Nohl A.A universal technique for fast and flexible instructionset architecture simulation[M].DAC，2002.

[4]陶峰峰，付宇卓.DSP指令集仿真器的設(shè)與實現(xiàn)[J].計算機(jī)仿真，2005，22（9）：225-228.TAO Feng-feng，F(xiàn)U Yu-zhuo.Design and implementation of DSP instruction simulator[J].Computer Simulation，2005，22（9）:225-228.

[5]Freericks M．The nML machine description formalism[M]．Berlin Tech．Rep．TU Berlin， Fachbereich Informatik，1991.

[6]劉競楠．基于nML的指令集仿真器自動生成技術(shù)初步研究[D].北京：華北電力大學(xué)，2008.