孔黎，劉靜

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

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

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

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

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

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

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

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

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

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

2 譯碼模塊的自動(dòng)生成策略

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

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

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

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

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

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

11110022223333334444555500000000

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

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

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

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

仿真函數(shù)庫(kù)的作用是用高級(jí)語(yǔ)言（C/C++）描述指令集中的沒一條指令。一般來(lái)說(shuō)一個(gè)C函數(shù)代表一個(gè)DSP指令。

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

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

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

1）OR－rules列出了一個(gè)指令部分的所有可選項(xiàng)。

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

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

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

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

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

4 ISS的優(yōu)化

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

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

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

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

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

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

在class opcoder中加入項(xiàng)：

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

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

unsigned int hash_entry_num//哈希表入口的數(shù)量，通過(guò)op1的長(zhǎng)度來(lái)確定

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

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

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

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

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

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

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

5 結(jié) 論

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

[1]王小紅．指令集仿真器快速生成環(huán)境的研究與實(shí)現(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è)與實(shí)現(xiàn)[J].計(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]劉競(jìng)楠．基于nML的指令集仿真器自動(dòng)生成技術(shù)初步研究[D].北京：華北電力大學(xué)，2008.