寬函數(shù)的布爾匹配及其在FPGA重綜合中的應(yīng)用*

張峰 王作建 吳洋 于芳 劉忠立

(1.中國科學(xué)院 微電子研究所，北京 100029;2.北京飄石科技有限公司，北京 100029)

近年來，現(xiàn)場(chǎng)可編程門陣列(FPGA)在速度、容量及功能性方面有顯著提升，因此在諸多應(yīng)用領(lǐng)域逐漸取代專用集成電路(ASIC).FPGA 的應(yīng)用和廣泛普及為數(shù)字系統(tǒng)的設(shè)計(jì)帶來極大的靈活性.當(dāng)前大多數(shù)FPGA 的可編程邏輯塊(CLB)基于查找表(LUT).一個(gè)k 輸入LUT(k-LUT)包含有2k個(gè)靜態(tài)存儲(chǔ)器(SRAM)單元，可實(shí)現(xiàn)任意輸入數(shù)不大于k的邏輯.為進(jìn)一步提高CLB 的配置靈活性，目前商用FPGA 的CLB 結(jié)構(gòu)增加了很多輔助單元用來更高效地實(shí)現(xiàn)各種功能.比如使用多路復(fù)用器(MUX)和異或門(XOR)來輔助實(shí)現(xiàn)快速進(jìn)位鏈，使用MUX來組合寬輸入的LUT 等.為了有效地利用現(xiàn)代FPGA芯片的這些異構(gòu)特性，需要在已有基于LUT映射方法的基礎(chǔ)上進(jìn)行擴(kuò)充或改進(jìn).

1 目標(biāo)FPGA 結(jié)構(gòu)

以Xilinx 公司的CLB 結(jié)構(gòu)為例，1 個(gè)CLB 包含兩個(gè)邏輯片(SLICE)，每個(gè)SLICE 包含兩個(gè)基本邏輯單元(LC)，每個(gè)LC 由一個(gè)k-LUT 和一個(gè)時(shí)序元件D 型觸發(fā)器(DFF)組成，如圖1 所示.

對(duì)于一個(gè)LUT 基CLB 結(jié)構(gòu)，假如CLB/SLICE能實(shí)現(xiàn)任意k 輸入函數(shù)，那么定義k 的最大值為CLB 的特征數(shù)值.對(duì)于變量數(shù)大于特征數(shù)值k 的函數(shù)，定義該函數(shù)為相對(duì)于CLB/SLICE 的寬函數(shù).

以k-LUT 的k 值等于4 為例(如圖1 所示［1］)，每個(gè)SLICE 中含有兩個(gè)LUT(F 和G)，1 個(gè)2 選1 MUX H，用于將SLICE 中的兩個(gè)4-LUT 組合成5-LUT，則該SLICE 的特征數(shù)值k 為5，每個(gè)SLICE可實(shí)現(xiàn)輸入數(shù)不大于5 的任意邏輯，或者1 個(gè)4 選1 MUX，或者輸入數(shù)在6 到9 之間的部分邏輯(寬函數(shù)).類似地，2 選1 MUX I 將兩個(gè)H 的輸出組合，則CLB 的特征數(shù)值k 為6，使得1 個(gè)CLB 可以實(shí)現(xiàn)輸入數(shù)不大于6 的任意邏輯，或者1 個(gè)8 選1 MUX，或者輸入數(shù)介于7 到19 之間的部分寬函數(shù).

圖1 包含兩個(gè)SLICE 的CLB 視圖［1］Fig.1 Detailed view of two-SLICE CLB［1］

由幾個(gè)k-LUT 組成的網(wǎng)表通常被稱作LUTs 結(jié)構(gòu)，如圖2 所示.從廣義上講，SLICE 和CLB 也屬于LUTs 結(jié)構(gòu).對(duì)于寬函數(shù)與LUTs 結(jié)構(gòu)之間的布爾匹配問題，通常有以下幾種應(yīng)用:FPGA 結(jié)構(gòu)的評(píng)估、對(duì)LUTs 結(jié)構(gòu)的工藝映射、對(duì)映射后的網(wǎng)表進(jìn)行的重綜合.

圖2 LUTs 結(jié)構(gòu)示例Fig.2 Examples of LUT structures

2 布爾匹配問題的研究現(xiàn)狀

國內(nèi)對(duì)布爾匹配問題的研究報(bào)道較少，國外的研究主要基于以下幾種方法.

(1)結(jié)構(gòu)化匹配.結(jié)構(gòu)化的工藝映射工具(如文獻(xiàn)［2］和［3］)一般采用這種方法.該方法主要基于輸入數(shù)的匹配，因此對(duì)寬函數(shù)的匹配問題成功率較低.

(2)基于可滿足性(SAT)的匹配方法［4-5］.該方法可有效地對(duì)寬函數(shù)與LUTs 結(jié)構(gòu)進(jìn)行匹配，可保證存在的匹配能被找到，但是這種方法非常耗時(shí).文獻(xiàn)［4］報(bào)道，在60s 的限制時(shí)間內(nèi)，該方法對(duì)10 輸入變量的函數(shù)只有50%的匹配成功率.因此，受運(yùn)行時(shí)間限制，基于SAT 的匹配方法一般用于輸入數(shù)≤10的函數(shù).

(3)基于NPN 等價(jià)類的方法［6-7］.該方法主要基于NPN 等價(jià)類編碼方法.即對(duì)給定的LUTs 結(jié)構(gòu)，將所有能實(shí)現(xiàn)的函數(shù)的NPN 等價(jià)類預(yù)先計(jì)算好，存入庫中，在需要匹配時(shí)將庫文件導(dǎo)入內(nèi)存中，將待匹配的寬函數(shù)進(jìn)行NPN 編碼后在庫中查找匹配.這種方法效率很高，運(yùn)行時(shí)間少，缺點(diǎn)是對(duì)庫的依賴大，數(shù)量龐大的NPN 等價(jià)類會(huì)占用大量?jī)?nèi)存.如文獻(xiàn)［6］中對(duì)9 輸入的函數(shù)如果要達(dá)到95%的匹配率，需要占用155.7 MB 內(nèi)存，而且輸入數(shù)每增加1，內(nèi)存占用會(huì)增加近10 倍.因此這種方法一般適用于特定的結(jié)構(gòu)，并且輸入數(shù)≤10 的情況.

(4)基于布爾函數(shù)分解的方法［8-9］.該方法適應(yīng)性廣，主要通過分解算法將布爾函數(shù)分解，使得每一個(gè)分解后的子函數(shù)能被k-LUT 實(shí)現(xiàn).這種方法的匹配率和效率取決于被匹配的布爾函數(shù)和采用的分解算法，通常在分解的過程中采用啟發(fā)式的方式來提高算法的效率.

3 布爾匹配方法及其應(yīng)用

文中所采用的布爾匹配方法屬于基于布爾函數(shù)分解的方法，采用MUX 分解技術(shù)和不相交支持集分解(DSD)算法相結(jié)合的技術(shù).

文獻(xiàn)［6］中提及，給定邏輯函數(shù)與LUTs 結(jié)構(gòu)之間的匹配問題，可以歸為兩類:①提供確定的LUTs結(jié)構(gòu)(如CLB、SLICE)，判斷給定的邏輯函數(shù)能否被實(shí)現(xiàn);②提供完全定義函數(shù)，產(chǎn)生一個(gè)較小的LUTs結(jié)構(gòu)來實(shí)現(xiàn).

文中對(duì)①、②兩種情況都進(jìn)行考慮，提出一種適應(yīng)圖1 中CLB 結(jié)構(gòu)和一般性LUTs 結(jié)構(gòu)(見圖2)的布爾匹配方法，并將其應(yīng)用于以面積為優(yōu)化目標(biāo)的工藝映射后的重綜合中.在該應(yīng)用中，先考慮第①種情況(基于MUX 分解技術(shù)，將在第3.1 節(jié)中詳細(xì)介紹);在第①種情況無法滿足的情況下，考慮第②種情況(基于DSD 技術(shù)，將在第3.2 節(jié)中詳細(xì)介紹).最后，將文中提出的布爾匹配方法應(yīng)用于工藝映射后的重綜合，并通過實(shí)驗(yàn)證明:文中的算法利用圖1中CLB 結(jié)構(gòu)的特點(diǎn)，使電路在FPGA 實(shí)現(xiàn)上能得到很好的面積優(yōu)化效果.

3.1 基于MUX 的分解方法

3.1.1 香農(nóng)展開式

使用f(X)表示布爾函數(shù)f(x1，x2，…，xn)，其中X={x1，x2，…，xn}.對(duì)于給定的f(X)，使用fˉxi和fxi表示f(X)相對(duì)于xi的余因子.f(X)相對(duì)于多個(gè)變量的余因子的定義類似，例如f(X)相對(duì)于xi的香農(nóng)展開式［10-11］為f(X)=xifxi+ˉxifˉxi，f(X)相對(duì)于多個(gè)變量的香農(nóng)展開式的定義類似.

在圖1 中，將F、G 和H 的輸入信號(hào)集合分別表示為XF、XG和和分別表示LUT F和LUT G 的大小(即輸入數(shù))，輸出信號(hào)分別表示為oF、oG和oH，MUX H 選擇oF還是oG作為輸出取決于外部選擇信號(hào)xH.使用圖1 中1 個(gè)SLICE 來實(shí)現(xiàn)f(X)時(shí)，可以將f(X)表征為ˉxHy1(XF)+xHy2(XG)，即f(X)相對(duì)于變量xH的香農(nóng)展開式，其中XF∪XG∪{xH}=X，y1(XF)、y2(XG)表示f(X)相對(duì)于xH的余因子.

3.1.2 對(duì)SLICE/CLB 的布爾匹配

對(duì)布爾函數(shù)和SLICE/CLB 之間進(jìn)行布爾匹配，可以由香農(nóng)展開式獲得，偽代碼如下:

如果匹配成功則函數(shù)muxDecompose 返回1 值，否則返回0 值.

定理1 1 個(gè)SLICE 能夠?qū)崿F(xiàn)f(X)，當(dāng)且僅當(dāng)存在相對(duì)于xH∈X 的香農(nóng)展開式

因此，給定一個(gè)寬函數(shù)F，通過調(diào)用函數(shù)find-BestCofVar 遍歷輸入集合中的每個(gè)信號(hào)，將其作為MUX 的選擇信號(hào)，對(duì)該信號(hào)進(jìn)行香農(nóng)展開，獲得兩個(gè)余因子(cof0、cof1)的輸入集合數(shù)(cof0-＞nVars，cof1-＞nVars).遍歷結(jié)束后將兩個(gè)余因子的輸入集合總數(shù)最小的信號(hào)作為選擇信號(hào)bestVar.

如果香農(nóng)展開式中兩個(gè)余因子的輸入集合均不大于k(k 表示k-LUT 的大小)，則可獲得對(duì)于SLICE的一個(gè)匹配.如果遍歷輸入集合結(jié)束后，未獲得對(duì)于SLICE 的一個(gè)匹配，則嘗試去尋求該寬函數(shù)對(duì)CLB的匹配.

定理2 f(X)不能用1 個(gè)SLICE 實(shí)現(xiàn)，而能用1 個(gè)CLB 實(shí)現(xiàn)，當(dāng)且僅當(dāng)存在相對(duì)于xH∈X 的香農(nóng)展開式

式中，xH0、xH1分別表示圖1 中SLICE0 和SLICE1 中的xH信號(hào)，y01、y02表示f(X)相對(duì)于xH0的余因子，y11、y12表示f(X)相對(duì)于xH1的余因子.

如果寬函數(shù)對(duì)SLICE 的布爾匹配失敗，則對(duì)f(X)的輸入集合總數(shù)最小的兩個(gè)余因子分別進(jìn)行進(jìn)一步處理，如果兩個(gè)余因子的輸入集合數(shù)都大于LUT 的輸入數(shù)，則對(duì)兩個(gè)余因子分別調(diào)用函數(shù)muxDecompose進(jìn)行香農(nóng)展開，則可獲得f(X)的4 個(gè)子余因子;如果只有一個(gè)余因子的輸入集合數(shù)大于LUT 的輸入數(shù)，則只對(duì)這一個(gè)余因子調(diào)用函數(shù)muxDecompose進(jìn)行香農(nóng)展開，則可獲得f(X)的3 個(gè)子余因子.如果獲得的所有子余因子的輸入集合數(shù)都不大于LUT 的輸入數(shù)，則獲得寬函數(shù)f(X)對(duì)CLB的一個(gè)布爾匹配.

3.2 基于DSD 的分解方法

3.2.1 DSD 的一些基本概念

定義1 一個(gè)完全定義函數(shù)F，如果存在一種輸入組合，當(dāng)其中一個(gè)變量值切換時(shí)，F(xiàn) 的值發(fā)生變化，則稱該變量值為F 的必要依賴項(xiàng).

定義2 F 的支持集定義為F 的所有必要依賴項(xiàng)的集合.

定義3 如果兩個(gè)函數(shù)不包含相同的變量，則稱這兩個(gè)函數(shù)的支持集不相交.

定義4 一個(gè)完全定義函數(shù)的分解定義為一個(gè)只包含一個(gè)原始輸出(PO)的布爾網(wǎng)絡(luò)，該布爾網(wǎng)絡(luò)與原函數(shù)在功能性上等價(jià).

定義5 不相交支持集分解是指一個(gè)完全定義函數(shù)分解得到的布爾網(wǎng)絡(luò)，該網(wǎng)絡(luò)中各節(jié)點(diǎn)的支持集相互之間不相交［9］.

根據(jù)定義5，DSD 通常結(jié)果是一個(gè)樹形結(jié)構(gòu)(每個(gè)節(jié)點(diǎn)只含有一個(gè)扇出)，每個(gè)葉節(jié)點(diǎn)的支持集稱為約束集，其余變量稱為自由集.如果DSD 之后，每個(gè)節(jié)點(diǎn)都不能再進(jìn)行DSD，則稱這個(gè)DSD 為一個(gè)極大DSD.

3.2.2 對(duì)LUTs 結(jié)構(gòu)的布爾匹配

計(jì)算極大DSD 的文獻(xiàn)有［9，12-14］等，在這些文獻(xiàn)中所述算法的基礎(chǔ)上，文中提出了一種適用于可能包含SLICE 的LUTs 結(jié)構(gòu)的布爾匹配方法.使

用DSD 算法進(jìn)行布爾匹配的偽代碼如下:

函數(shù)decompose_rec 的輸入是完全定義函數(shù)F和用于限制分解模塊的支持集大小的限制數(shù)k，該函數(shù)可對(duì)自身進(jìn)行遞歸調(diào)用，直到F 分解完全或分解失敗.如果F 分解成功，則該函數(shù)返回1 值，否則返回0 值;

函數(shù)decompose_rec 首先會(huì)調(diào)用函數(shù)support-Minimize，該函數(shù)用于移除無意義的變量，并返回F的新支持集.例如，對(duì)于F = acd，如果其支持集為(a，b，c，d)，則b 是F 的無意義變量.函數(shù)support-Minimize 會(huì)將變量b 從F 的支持集中移除，新的支持集大小為3.

為充分使用圖1 中CLB 里的MUX，在進(jìn)行DSD之前，首先嘗試使用基于MUX 的分解，該方法已在3.1 節(jié)中詳細(xì)介紹.

函數(shù)dsdAnalyze 用于分析DSD 的可能性，該函數(shù)嘗試進(jìn)行DSD，計(jì)算出所有k 可行的約束集，從中選出最好的約束集，最后返回DSD 樹.

如果DSD 樹不為空，并且得出的約束集大小為k 或k-1，則對(duì)函數(shù)F 調(diào)用dsdSplit 進(jìn)行DSD，分解成約束集BSets 和自由集FSets.文中算法的特點(diǎn)是，dsdSplit 盡可能地一次分解出多個(gè)大小為k 的約束集.以圖2(a)為例，對(duì)于給定的12 輸入完全定義函數(shù)，在第1 次DSD 分解后，得到3 個(gè)大小為k 的約束集，分別用A、B、C 3 個(gè)節(jié)點(diǎn)來實(shí)現(xiàn).此時(shí)自由集已為空，小于k，不需要做進(jìn)一步分解，只需要新增一個(gè)D 節(jié)點(diǎn)，使其扇入分別為A、B、C 節(jié)點(diǎn)即可.至此，給定的寬函數(shù)用圖2(a)匹配成功.

假如dsdSplit 進(jìn)行DSD 分解后，自由集大于k，則需要對(duì)自由集做進(jìn)一步分解.以圖2(b)為例，對(duì)于給定的12 輸入完全定義函數(shù)，在第1 次DSD 分解后，BSets 用A 節(jié)點(diǎn)來實(shí)現(xiàn)，此時(shí)FSets 含有8 個(gè)變量，大于k，因此遞歸調(diào)用decompose_rec 對(duì)FSets 做進(jìn)一步的分解.假設(shè)此次基于MUX 的分解成功，則將FSets 用B 節(jié)點(diǎn)(SLICE)來實(shí)現(xiàn)(如果MUX 分解失敗，則需要調(diào)用dsdSplit 進(jìn)行DSD 分解).至此，給定的寬函數(shù)用圖2(b)匹配成功.

3.3 以面積為優(yōu)化目標(biāo)的重綜合

重綜合［15］是一項(xiàng)重寫電路結(jié)構(gòu)的技術(shù)，它可以在不改變電路功能的情況下有效地減小面積或延時(shí).重綜合通常與工藝映射同時(shí)進(jìn)行［14］，或者單獨(dú)作為映射后的優(yōu)化動(dòng)作［16］進(jìn)行.重綜合需要探尋龐大的解空間，所以與工藝映射同時(shí)進(jìn)行非常耗時(shí)，從而使這種方法只能對(duì)小的電路進(jìn)行優(yōu)化.而在映射后進(jìn)行重綜合，則可以選擇不同于工藝映射的策略，例如只選擇映射后網(wǎng)絡(luò)里的部分節(jié)點(diǎn)(如關(guān)鍵路徑或近關(guān)鍵路徑節(jié)點(diǎn))進(jìn)行重綜合，或者使用比映射過程中更簡(jiǎn)潔高效的截計(jì)算方法［17］，這些策略可以大大減小運(yùn)行時(shí)間，從而可以更好地處理大的電路.

有效地判斷完全定義的寬函數(shù)能否用LUTs 結(jié)構(gòu)實(shí)現(xiàn)(即寬函數(shù)與LUTs 結(jié)構(gòu)之間的布爾匹配問題)，是FPGA 重綜合算法中的核心問題.為解決此問題，文中將第3.1 節(jié)和第3.2 節(jié)介紹的布爾匹配算法應(yīng)用于映射后的重綜合中.

首先對(duì)映射后的布爾網(wǎng)絡(luò)進(jìn)行分析，將所有LUTs 節(jié)點(diǎn)從輸出(原始輸出和觸發(fā)器的輸入)到輸入(原始輸入和觸發(fā)器的輸出)按逆拓?fù)漤樞蚺帕?然后計(jì)算出每個(gè)節(jié)點(diǎn)的輸入變量數(shù)不大于16 (受當(dāng)前數(shù)據(jù)結(jié)構(gòu)限制，暫只支持16 以下輸入數(shù))的截，并將其中權(quán)重比較高的一部分存入截集合.

遍歷截集合，對(duì)每個(gè)截計(jì)算出截的函數(shù)(真值表).接著使用第3.2.2 節(jié)中介紹的函數(shù)decompose_rec 來分解截的函數(shù)，用功能性等價(jià)的LUTs 結(jié)構(gòu)與截的函數(shù)進(jìn)行布爾匹配.

以圖2 為例，假設(shè)截的根節(jié)點(diǎn)和葉節(jié)點(diǎn)之間形成的錐為圖2(a)，而匹配成功后新的LUTs 結(jié)構(gòu)為圖2(b)，圖2(b)比圖2(a)所包含的節(jié)點(diǎn)數(shù)目少.如果替換后網(wǎng)絡(luò)的關(guān)鍵路徑延時(shí)不會(huì)增加，則把錐替換成新的LUTs 結(jié)構(gòu).

也就是說，文中進(jìn)行的重綜合的目標(biāo)是在不損害電路延時(shí)的情況下去減小面積.

4 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證第3 節(jié)所提算法的優(yōu)化效果，文中從MCNC［18］和ISCAS’89 基準(zhǔn)電路集中選取20 個(gè)電路對(duì)第3.3 節(jié)中的重綜合(以下簡(jiǎn)稱ime)策略進(jìn)行測(cè)試.測(cè)試環(huán)境:CPU 為Intel core i7 CPU870 2.93 GHz，內(nèi)存為4 GB，操作系統(tǒng)為Windows XP，編譯環(huán)境為Visual C++2008.實(shí)驗(yàn)結(jié)果網(wǎng)表均通過ABC 里的驗(yàn)證工具證明與原始電路等價(jià).

實(shí)驗(yàn)中用到的ABC［19-20］命令有:

st:將當(dāng)前網(wǎng)表經(jīng)過一級(jí)結(jié)構(gòu)化哈希轉(zhuǎn)化成與非圖(AIG)網(wǎng)表;

resyn:迭代運(yùn)行5 次AIG 重寫［21］的邏輯綜合腳本命令;

dc2:迭代運(yùn)行10 次AIG 重寫的邏輯綜合腳本命令;

dch:一種累積結(jié)構(gòu)化選擇的邏輯綜合腳本命令，該命令運(yùn)行命令resyn 之后運(yùn)行命令dc2，并收集網(wǎng)表的3 個(gè)快照:原始網(wǎng)表、運(yùn)行resyn 之后的中間網(wǎng)表以及最終網(wǎng)表.

if:一種高效的FPGA 工藝映射命令，基于優(yōu)先截算法［22］，能夠?qū)Y(jié)構(gòu)化選擇的網(wǎng)表進(jìn)行映射.

mfs:一種以面積為優(yōu)化目標(biāo)的重綜合命令［15］，屬于基于SAT 的布爾匹配算法.

lutpack:一種以面積為優(yōu)化目標(biāo)的重綜合命令［9］，屬于基于余因子提取和DSD 分解技術(shù)的布爾匹配算法.

4.1 以4-LUT 為映射目標(biāo)的實(shí)驗(yàn)

本實(shí)驗(yàn)的映射目標(biāo)為圖1 中基于4-LUT 的CLB結(jié)構(gòu)，分別運(yùn)行如表1 所示的4 組命令.

“choices”欄:代表迭代運(yùn)行4 次基于結(jié)構(gòu)化選擇的工藝映射(st;dch;if-C 12)，并從4 次結(jié)果中選出面積最好的結(jié)果;

“l(fā)utpack”欄:代表迭代運(yùn)行4 次基于結(jié)構(gòu)化選擇的工藝映射，并交叉運(yùn)行重綜合命令lutpack(st;dch;if-C 12;lutpack)，并從4 次結(jié)果中選出面積最好的結(jié)果;

“mfs”欄:代表迭代運(yùn)行4 次基于結(jié)構(gòu)化選擇的工藝映射，并交叉運(yùn)行重綜合命令mfs(st;dch;if-C 12;mfs)，并從4 次結(jié)果中選出面積最好的結(jié)果;

“ime”欄:代表迭代運(yùn)行4 次基于結(jié)構(gòu)化選擇的工藝映射，并交叉運(yùn)行文中的重綜合算法ime(st;dch;if-C 12;ime)，并從4 次結(jié)果中選出面積最好的結(jié)果;

現(xiàn)有的工藝映射工具［2，22］無法使用圖1 中CLB里的MUX H 和I，造成很多資源的浪費(fèi)，而使用MUX H 和I 并不影響電路的面積，只是對(duì)電路的延時(shí)有一定增加，所以本實(shí)驗(yàn)中面積模型只統(tǒng)計(jì)最終使用的LUT 數(shù)量.由于工藝映射后無法得知布線資源里的延時(shí)，所以ABC 的延時(shí)模型只統(tǒng)計(jì)電路關(guān)鍵路徑上的LUT 層級(jí)，一個(gè)k-LUT 的延時(shí)為1.由文獻(xiàn)［1］可知，圖1 中F/G 的輸入端到X/Y 輸出端的最小延時(shí)為0.29 ns，F(xiàn)/G 的輸入端到F5 輸出端的最小延時(shí)為0.32 ns，F(xiàn)/G 的輸入端經(jīng)過H 后到X 輸出端的最小延時(shí)為0.36 ns，F(xiàn)/G 的輸入端經(jīng)過H 和I后到Y(jié) 輸出端的最小延時(shí)為0.44 ns.據(jù)此，本實(shí)驗(yàn)中ime 的延時(shí)模型在ABC 中標(biāo)準(zhǔn)的LUT 延時(shí)模型基礎(chǔ)上作了一定的適應(yīng)性改變，將1 個(gè)SLICE 的延時(shí)定為1.2，1 個(gè)CLB 的延時(shí)定為1.5，雖然是近似延時(shí)模型，但足以保證結(jié)果的合理性.

表1 中“比率1”一行的統(tǒng)計(jì)結(jié)果表明，與choices相比，在不增加電路關(guān)鍵路徑延時(shí)的基礎(chǔ)上，ime、lutpack、mfs 均能對(duì)工藝映射后的網(wǎng)表進(jìn)行面積優(yōu)化，減少LUT 的使用數(shù)量，優(yōu)化比例分別達(dá)到7.9%、6.1%和8.1%.實(shí)驗(yàn)結(jié)果表明，對(duì)于本實(shí)驗(yàn)的映射目標(biāo)，ime 比lutpack 有更好的面積優(yōu)化效果，運(yùn)行時(shí)間上也小于lutpack.表1 中“比率3”一行的統(tǒng)計(jì)結(jié)果表明，與mfs 相比，ime 在運(yùn)行時(shí)間上為mfs 的41.2%，而面積僅增加0.2%.

表1 k=4 時(shí)對(duì)CLB 工藝映射后進(jìn)行重綜合的實(shí)驗(yàn)結(jié)果Table 1 Resynthesis results after technology mapping for CLB when k=4

4.2 以6-LUT 為映射目標(biāo)的實(shí)驗(yàn)

為驗(yàn)證文中提出的算法的通用性，對(duì)文獻(xiàn)［23］中6-LUT 的器件另外進(jìn)行了一組映射實(shí)驗(yàn)，運(yùn)行命令與實(shí)驗(yàn)一中相同.據(jù)文獻(xiàn)［24］，6-LUT 的延時(shí)TILO 最小值為0.08 ns，使用F7MUX 組合出7-LUT 的延時(shí)TILO_2 最小值為0.20 ns，使用F8MUX 組合出8-LUT 的延時(shí)TILO_3 最小值為0.31 ns.據(jù)此，本實(shí)驗(yàn)ime 的延時(shí)模型中，將6-LUT 的延時(shí)層級(jí)定為1，7-LUT 的延時(shí)層級(jí)定為2.5，8-LUT 的延時(shí)層級(jí)定為4，雖然是近似延時(shí)模型，但足以保證結(jié)果的合理性.

表2 中“比率1”一行的統(tǒng)計(jì)結(jié)果表明，ime 對(duì)基于6-LUT 的SLICE 結(jié)構(gòu)也具有較好的面積優(yōu)化結(jié)果，與choices 相比，在不增加電路關(guān)鍵路徑延時(shí)的基礎(chǔ)上(2.2%的優(yōu)化)，ime 對(duì)工藝映射后的網(wǎng)表面積能達(dá)到7.8%的優(yōu)化結(jié)果，該結(jié)果優(yōu)于lutpack 的4.9%.對(duì)于mfs，表2 中“比率1”一行的統(tǒng)計(jì)結(jié)果表明，mfs 對(duì)6-LUT 網(wǎng)表有更好的優(yōu)化結(jié)果，達(dá)到驚人的27%.該結(jié)果與文獻(xiàn)［15］中不同的原因在于，無從得知文獻(xiàn)［15］中所用ABC 軟件的版本;為了合理公平地比較不同算法的優(yōu)化結(jié)果，在本實(shí)驗(yàn)中統(tǒng)一采用了ABC 2012 年7 月18 日的版本，而此版本中，choices 已對(duì)網(wǎng)表得到較好的映射結(jié)果，所以mfs 的優(yōu)化比率比文獻(xiàn)［15］中稍差.與mfs 相比，ime 在運(yùn)行時(shí)間方面優(yōu)勢(shì)明顯，僅為mfs 的29.8%，但在面積方面差距較大，差距主要在電路clma、ex5p、pdc、spla 等幾個(gè)電路上.mfs 的運(yùn)行結(jié)果表明，ime 在面積方面仍有較大的優(yōu)化空間，下一步的研究是在保證運(yùn)行時(shí)間較優(yōu)的情況下進(jìn)一步優(yōu)化電路面積.

表2 k=6 時(shí)對(duì)CLB 工藝映射后進(jìn)行重綜合的實(shí)驗(yàn)結(jié)果Table 2 Resynthesis results after technology mapping for CLB when k=6

實(shí)驗(yàn)1 和實(shí)驗(yàn)2 的結(jié)果表明:ime 能充分利用圖1 中CLB 里的邏輯資源;在合理的運(yùn)行時(shí)間內(nèi)，并且在不增加電路關(guān)鍵路徑延時(shí)的前提下，不僅對(duì)大規(guī)模組合電路有很好的面積優(yōu)化效果，對(duì)于時(shí)序電路中時(shí)序元件之間的組合邏輯同樣具有很好的面積優(yōu)化效果.由于Xilinx 公司大多數(shù)器件采用類似圖1中的CLB 結(jié)構(gòu)，器件之間僅在k-LUT 的大小和CLB中k-LUT 的數(shù)量上存在差異.因此，文中提出的算法對(duì)Xilinx 公司的器件具有一定的通用性和適用性.

5 結(jié)語

文中提出一種對(duì)寬函數(shù)與CLB 結(jié)構(gòu)進(jìn)行布爾匹配的方法，該方法結(jié)合使用香農(nóng)展開式和不相交支持集分解算法，主要針對(duì)Xilinx 公司的CLB 結(jié)構(gòu).將文中的布爾匹配方法應(yīng)用于工藝映射后的重綜合，能夠在不增加電路關(guān)鍵路徑延時(shí)的基礎(chǔ)上，對(duì)4-LUT 和6-LUT 工藝映射后的電路網(wǎng)表在面積上分別獲得7.9%和7.8%的優(yōu)化結(jié)果.文中提出的方法能充分利用CLB 的結(jié)構(gòu)特點(diǎn)，在普通工藝映射的基礎(chǔ)上，使輸入數(shù)不大于16 的寬函數(shù)能使用更少的LUT 數(shù)來實(shí)現(xiàn)，從而達(dá)到面積優(yōu)化的效果.

［1］Xilinx Inc.VirtexTM2.5 V field programmable gate arrays［EB/OL］.(2001-04-02)［2012-08-14］.http:∥china.xilinx.com/support/documentation/data _ sheets/ds003.pdf.

［2］Chen D，Cong J.DAOmap:a depth-optimal area optimization mapping algorithm for FPGA designs［C］∥Proceedings of the 2004 IEEE/ACM International Conference on Computer-Aided Design.San Jose:IEEE/ACM，2004:752-759.

［3］Mishchenko A，Chatterjee S，Brayton R.Improvements to technology mapping for LUT-based FPGAs ［J］.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2007，26(2):240-253.

［4］Cong J，Minkovich K.Improved SAT-based Boolean matching using implicants for LUT-based FPGAs［C］∥Proceedings of the 2007 ACM/SIGDA 15th International Symposium on Field Programmable Gate Arrays.New York:ACM，2007:139-147.

［5］Wang K，Chan C，Liu J.Simulation and SAT-based Boolean matching for large Boolean networks［C］∥Proceedings of the 46th ACM/IEEE Design Automation Conference.San Francisco:ACM，2009:396-401.

［6］Kennings A，Mishchenko A，Vorwerk K，et al.Efficient FPGA resynthesis using precomputed LUT structures［C］∥Proceedings of the 20th International Conference on Field Programmable Logic and Applications.Milano:IEEE，2010:532-537.

［7］Kennings A，Vorwerk K，Kundu A，et al.FPGA technology mapping with encoded libraries and staged priority cuts［J］.ACM Transactions on Reconfigurable Technology and Systems，2011，4(4):Article No.35.

［8］Mishchenko A，Wang X，Kam T.A new enhanced constructive decomposition and mapping algorithm ［C］∥Proceedings of the 40th Design Automation Conference.Anaheim:ACM，2003:143-148.

［9］Mishchenko A，Brayton R，Chatterjee S.Boolean factoring and decomposition of logic networks［C］∥Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design.San Jose:IEEE/ACM，2008:38-44.

［10］Wikipedia.Shannon’s expansion［EB/OL］.(2012-07-06)［2012-08-14］.http:∥en.wikipedia.org/wiki/Shannon%27s_expansion.

［11］Cong J，Hwang Y-Y.Boolean matching for LUT-based logic blocks with applications to architecture evaluation and technology mapping ［J］.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2001，20(9):1077-1090.

［12］Rytsar B.A new algorithm of functional decomposition for optimization logic synthesis［C］∥Proceedings of the 2008 Conference on Human System Interactions.Krakw:IEEE，2008:386-389.

［13］Ray S，Mishchenko A，Een N，et al.Mapping into LUTstructures［C］∥Proceedings of the 2012 Design Automation ＆ Test in Europe Conference ＆ Exhibition.Dresden:EDAA，2012:1579-1584.

［14］Bertacco V，Damiani M.The disjunctive decomposition of logic functions ［C］∥Proceedings of the 1997 IEEE/ACM International Conference on Computer-Aided Design.San Jose:IEEE/ACM，1997:78-82.

［15］Mishchenko A，Brayton R，Jian J-H R，et al.Scalable don't-care-based logic optimization and resynthesis［J］.ACM Transactions on Reconfigurable Technology and Systems，2011，4(4):Article No.34.

［16］Chen L.Post-mapping topology rewriting for FPGA area minimization ［D］.Waterloo:Department of Electrical and Computer Engineering，University of Waterloo，2009.

［17］Mishchenko A，Chatterjee S，Brayton R.Fast Boolean matching for LUT structures［R］.Berkeley:UC Berkeley，2007.

［18］Yang S.Logic synthesis and optimization benchmarks user guide［R］.Version 3.0.Durham:Microelectronics Center of North Carolina，1991.

［19］Berkeley Logic Synthesis and Verification Group.ABC:a system for sequential synthesis and verification ［EB/OL］.(2012-09-20)［2012-10-08］.http:∥www.eecs.berkeley.edu/～alanmi/abc.

［20］Brayton R，Mishchenko A.ABC:an academic industrial strength verification tool［C］∥Proceedings of the 22nd International Conference on Computer Aided Verification.Edinburgh:Springer，2010:24-40.

［21］Mishchenko A，Chatterjee S，Brayton R.DAG-aware AIG rewriting:a fresh look at combinational logic synthesis［C］∥Proceedings of the 43rd Design Automation Conference.Anaheim:ACM，2006:532-535.

［22］Mishchenko A，Cho S，Chatterjee S，et al.Combinational and sequential mapping with priority cuts ［C］∥Proceedings of the 2007 IEEE/ACM International Conference on Computer-Aided Design.San Jose:IEEE，2007:354-361.

［23］Xilinx Inc.Virtex-5 FPGA user guide［EB/OL］.(2012-03-16)［2013-01-10］.http:∥www.xilinx.com/support/documentation/user_guides/ug190.pdf.

［24］Xilinx Inc.Virtex-5 FPGA data sheet:DC and switching characteristics［EB/OL］.(2010-05-05)［2013-01-10］.http:∥www.xilinx.com/support/documentation/data_sheets/ds202.pdf.