喻奇，王倫耀，夏銀水

(寧波大學(xué) 信息科學(xué)與工程學(xué)院， 浙江 寧波 315211)

邏輯電路綜合的效果，很大程度上取決于所使用的標(biāo)準(zhǔn)單元庫(standard cells library)包含的單元電路的質(zhì)量、種類和數(shù)量[1].集成電路技術(shù)的迅猛發(fā)展、工藝的不斷更新，給標(biāo)準(zhǔn)單元庫的維護(hù)和升級帶來了巨大挑戰(zhàn).另一方面，標(biāo)準(zhǔn)單元庫中功能有限的單元電路與電路功能的矛盾，也限制了邏輯電路在映射過程中進(jìn)一步優(yōu)化的可能性.而基于library-free映射，使用大型虛擬庫代替預(yù)先設(shè)計(jì)好的標(biāo)準(zhǔn)單元庫[2-3]，所有的門單元都是動態(tài)且按需生成的，映射過程中不必考慮使用的門單元是否存在，因此具有更大的解空間.同時，library-free映射因較靈活，常被應(yīng)用于新器件的映射[4-5].

基于library-free映射的面積優(yōu)化，主要包含動態(tài)單元電路的生成與性能評估[6-8]以及覆蓋策略[9-11]兩方面.在覆蓋策略方面，文獻(xiàn)[9]將電路表示為由“與/或/非”等基本邏輯運(yùn)算組合而成的n元樹(n-ary tree)，并以串并聯(lián)晶體管數(shù)量為約束條件，使用動態(tài)規(guī)劃對電路延時進(jìn)行優(yōu)化.文獻(xiàn)[10]使用多米諾邏輯進(jìn)行l(wèi)ibrary-free映射,首先使用節(jié)點(diǎn)映射算法獲得多米諾邏輯的初始映射，再沿關(guān)鍵路徑對邏輯單元重新排序，進(jìn)而實(shí)現(xiàn)延時優(yōu)化.文獻(xiàn)[11]使用邏輯努力(logical effort)對動態(tài)單元電路的延時進(jìn)行估算，并以延時為約束條件使用動態(tài)規(guī)劃實(shí)現(xiàn)面積的最優(yōu)覆蓋.動態(tài)規(guī)劃是一種常用的覆蓋策略方法，求解過程中須窮舉解空間的所有解，故隨著問題規(guī)模的增大，求解難度和時間復(fù)雜度將呈指數(shù)上升，導(dǎo)致運(yùn)算時間過長.因此，在求解大電路時，須引入其他算法，并在求解速度與優(yōu)化結(jié)果上進(jìn)行折中處理[12].

本文提出了一種基于library-free映射的面積優(yōu)化算法，包括動態(tài)單元電路的面積估算和覆蓋策略兩部分.在動態(tài)單元電路的面積估算中，通過動態(tài)單元電路對應(yīng)的“與/或/非”圖(and-or-inverter graph，AOIG)，結(jié)合邏輯努力對其面積進(jìn)行估算.在覆蓋策略上，將動態(tài)規(guī)劃與遺傳算法(genetic algorithm，GA)相結(jié)合，實(shí)現(xiàn)電路的library-free映射.實(shí)驗(yàn)結(jié)果表明，混合算法與動態(tài)規(guī)劃的優(yōu)化效果相差無幾，但能有效縮短求解時間.

1 動態(tài)單元的面積估算

1.1 AIG的切割

不同于基于標(biāo)準(zhǔn)單元庫的映射，在library-free映射過程中，所有用于映射的單元電路都是動態(tài)生成的，本文將用于映射的子電路統(tǒng)稱為動態(tài)單元電路.這些動態(tài)單元電路均與待映射電路網(wǎng)表中滿足無輸出錐集(free fanout cone，F(xiàn)FC)[9,12]約束的切割相對應(yīng).待映射電路的初始表示數(shù)據(jù)結(jié)構(gòu)為與非圖(and-inverter graph，AIG)，電路的覆蓋過程即為對AIG的切割過程，而切割得到的子AIG必須滿足FFC約束，即子AIG中，除根節(jié)點(diǎn)外，其他內(nèi)部節(jié)點(diǎn)的輸出不作為錐外節(jié)點(diǎn)的輸入.為更好地滿足FFC約束，同時減少切割數(shù)量，筆者將待切割A(yù)IG中的多扇出節(jié)點(diǎn)作為切割后子AIG的根節(jié)點(diǎn)，將整個AIG切割成多個以電路根節(jié)點(diǎn)和內(nèi)部多扇出節(jié)點(diǎn)為根節(jié)點(diǎn)的最大無輸出錐集(maxinum free fanout cone，MFFC)[9].以圖1為例，圖1(a)為一個6輸入、2輸出的待映射電路的AIG，每一個圓圈表示1個“與”運(yùn)算，與圓圈相連的虛線表示取反運(yùn)算.節(jié)點(diǎn)4和5是AIG的2個根節(jié)點(diǎn)，節(jié)點(diǎn)2存在2個扇出，因此，本文也將節(jié)點(diǎn)2作為一個切割的根節(jié)點(diǎn)，于是得到如圖1(b)所示的3個MFFC.

圖1 滿足FFC約束的切割Fig.1 The cuts of meeting FFC constraint

在獲得電路根節(jié)點(diǎn)以及內(nèi)部多扇出節(jié)點(diǎn)的MFFC后，再對各個MFFC做進(jìn)一步切割，由MFFC切割出來的子AIG均滿足FFC約束，然后將子AIG轉(zhuǎn)化成用MOS晶體管實(shí)現(xiàn)的單元電路，從而完成電路的library-free映射.

1.2 基于AIG的CMOS電路生成方法

CMOS電路由產(chǎn)生高電平的pMOS和產(chǎn)生低電平的nMOS網(wǎng)絡(luò)組成.在輸入信號控制下，當(dāng)pMOS網(wǎng)絡(luò)導(dǎo)通時，CMOS電路輸出為邏輯1，反之輸出為邏輯0.此外，邏輯“與”可以用串聯(lián)的MOS管實(shí)現(xiàn)，邏輯“或”可用并聯(lián)的MOS管實(shí)現(xiàn)，利用MOS管的串并聯(lián)可實(shí)現(xiàn)邏輯函數(shù)的功能.

文中，待映射電路的邏輯功能用AIG表示，AIG結(jié)構(gòu)中無“或”運(yùn)算，方便起見，將AIG表示的邏輯功能用CMOS晶體管來實(shí)現(xiàn)，可以將AIG轉(zhuǎn)換為“與/或/非”圖，即AOIG.AOIG中的“與”節(jié)點(diǎn)對應(yīng)晶體管串聯(lián)，“或”節(jié)點(diǎn)對應(yīng)晶體管并聯(lián)，當(dāng)葉子節(jié)點(diǎn)輸出為虛邊時，表示該節(jié)點(diǎn)對應(yīng)的輸入帶反相器.

圖2 AIG轉(zhuǎn)化為AOIGFig.2 Convert AIG to AOIG

由AOIG得到對應(yīng)的CMOS電路的方法如下：

(2) AOIG中的每一個葉子節(jié)點(diǎn)對應(yīng)一個MOS管.“與”節(jié)點(diǎn)對應(yīng)MOS管串聯(lián)，“或”節(jié)點(diǎn)對應(yīng)MOS管并聯(lián).

(3) 下拉網(wǎng)絡(luò)的AOIG中，葉子節(jié)點(diǎn)對應(yīng)的輸入將作為整個CMOS電路的輸入.

圖3 由AOIG得到的CMOS電路Fig.3 CMOS circuits from AOIG

1.3 CMOS電路面積估算

在library-free映射中，用CMOS晶體管構(gòu)成的動態(tài)單元電路的面積，由電路各輸入的邏輯努力之和來衡量[13]：

(1)

式(1)中，S表示CMOS電路面積，I為CMOS電路的所有輸入的集合，gx為電路第x個輸入端的邏輯努力.

圖4 CMOS電路邏輯努力的計(jì)算方法Fig.4 Calculation method of logic effort in CMOS circuits

以圖4電路為例，圖中晶體管上的數(shù)字表示溝道寬長比W/L.圖4(a)為CMOS反相器，考慮到pMOS管與nMOS管的電阻率，將pMOS管的溝道寬度設(shè)置為nMOS管溝道寬度的2倍，使得電路上拉或下拉的驅(qū)動電流基本一致.圖4(b)為3輸入或非門，其上拉網(wǎng)絡(luò)為3個串聯(lián)的pMOS管，下拉網(wǎng)絡(luò)為3個并聯(lián)的nMOS管.在晶體管溝道長度相同的情況下，為使圖4(b)電路的最小驅(qū)動電流強(qiáng)度與圖4(a)相同，須將3個串聯(lián)的pMOS管的溝道寬度擴(kuò)大3倍.現(xiàn)定義單輸入的反相器面積為1個單位面積，由式(1)，則3輸入的或非門的面積為

S=(gA+gB+gC)/(2+1)=21/3=7個單位面積.

根據(jù)AOIG中邏輯運(yùn)算與CMOS電路中MOS管連接的對應(yīng)關(guān)系，由式(1)可直接在AOIG中計(jì)算各輸入的邏輯努力，進(jìn)而求解CMOS電路面積.電路面積估算規(guī)則如下：

1) 考慮到下拉nMOS網(wǎng)絡(luò)與上拉pMOS網(wǎng)絡(luò)的電阻率，令下拉網(wǎng)絡(luò)AOIG的根節(jié)點(diǎn)溝道寬長比初值為1，上拉網(wǎng)絡(luò)AOIG的根節(jié)點(diǎn)溝道寬長比初值為2.

2) 從AOIG的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)逐層遞歸計(jì)算.對于“與”節(jié)點(diǎn)： 往下遍歷各節(jié)點(diǎn)，當(dāng)某條路徑遍歷到“或”節(jié)點(diǎn)或葉子節(jié)點(diǎn)時，該條路徑遍歷截止.當(dāng)所有遍歷路徑都截止時，該“與”節(jié)點(diǎn)的遍歷結(jié)束.若初始“與”節(jié)點(diǎn)的晶體管溝道寬長比為λ，該“與”節(jié)點(diǎn)共遍歷t個“或”節(jié)點(diǎn)以及葉子節(jié)點(diǎn)，則這t個節(jié)點(diǎn)的溝道寬長比均為λ′=tλ.對于“或”節(jié)點(diǎn)： “或”節(jié)點(diǎn)的2個輸入節(jié)點(diǎn)的溝道寬長比等于該“或”節(jié)點(diǎn)的溝道寬長比.

圖5 在AOIG上計(jì)算邏輯努力的方法Fig.5 Calculation method of logic effort in the AOIG

CMOS電路的總面積可由式(2)計(jì)算：

S=Sp+Sn+Sinv-in+Sinv-out,

(2)

其中,Sp表示上拉網(wǎng)絡(luò)面積，Sn表示下拉網(wǎng)絡(luò)面積，Sinv-in表示輸入反相器面積，Sinv-out表示輸出反相器面積.

(3)

(4)

由式(3)可得，圖3(a)中的CMOS電路總面積S=20/3+14/3+2+1=43/3個單位面積；由式(4)可得，圖3(b)的CMOS電路總面積S=40/3+7/3+(5-2)=56/3個單位面積.計(jì)算結(jié)果表明： 適當(dāng)選擇上下拉網(wǎng)絡(luò)可優(yōu)化CMOS電路面積.

本文提出的面積估算方法的偽代碼如下，其中子函數(shù)Cal_WL(pNet，nNet)為按照電路面積估算規(guī)則在AOIG上計(jì)算葉子節(jié)點(diǎn)的晶體管溝道寬長比，pNet表示用于實(shí)現(xiàn)上拉網(wǎng)絡(luò)的邏輯函數(shù)，nNet表示用于實(shí)現(xiàn)下拉網(wǎng)絡(luò)的邏輯函數(shù).子函數(shù)Cal_Area_1()為用式(1)計(jì)算的CMOS電路面積.子函數(shù)Cal_Area_2()為用式(2)計(jì)算的CMOS電路面積.

Algorithm1Calculate area of dynamic cell

Inputf.AIG

OutputArea of dynamic cell

FunctionCal_Cell_Area

f.AOIG←De·Morgen Theorem (f.AIG);

S1=Cal_Area_1(AOIG_WL_1);

S2=Cal_Area_2(AOIG_WL_2);

if(S1

returnS1;

else

returnS2;

endif

2 Library-free映射的覆蓋算法

動態(tài)規(guī)劃是常用的一種覆蓋算法，首先自頂向下將整個電路切割成以電路根節(jié)點(diǎn)和內(nèi)部多扇出節(jié)點(diǎn)為根節(jié)點(diǎn)的多個MFFC.對于每一個MFFC，動態(tài)規(guī)劃會再次自底向上遍歷每個節(jié)點(diǎn)所有可能的切割方式，從而完成對MFFC的切割[13].假設(shè)圖6(a)為某MFFC，動態(tài)規(guī)劃會依次遍歷節(jié)點(diǎn)1、2、3，切割方式如圖6(b)～(h)所示.

圖6 使用動態(tài)規(guī)劃對MFFC進(jìn)行切割Fig.6 Cut the MFFC using dynamic programming

當(dāng)MFFC中有n個內(nèi)部節(jié)點(diǎn)時，整個MFFC有2n種不同的切割方式，覆蓋的計(jì)算量和時間復(fù)雜度將隨著MFFC內(nèi)部節(jié)點(diǎn)數(shù)的增多呈指數(shù)上升.因此，當(dāng)某個MFFC中包含的節(jié)點(diǎn)較多時，就需要平衡覆蓋速度和解的質(zhì)量，為此，本文使用一種混合算法對電路進(jìn)行覆蓋，即根據(jù)MFFC的大小(內(nèi)部節(jié)點(diǎn)數(shù)量)選擇不同的覆蓋算法.當(dāng)MFFC較大時，使用GA進(jìn)行覆蓋，此時啟發(fā)式算法的速度優(yōu)勢得以發(fā)揮；而當(dāng)MFFC較小時，依然使用動態(tài)規(guī)劃進(jìn)行覆蓋.因?yàn)镸FFC較小時，MFFC的可行切割方式數(shù)量有限，其計(jì)算成本也不會太高，此時動態(tài)規(guī)劃所耗時間和GA相差不大，但求得的解的質(zhì)量優(yōu)于GA.

圖7 染色體編碼及其對應(yīng)的覆蓋Fig.7 Chromosome’s code and its cover

當(dāng)使用GA對MFFC進(jìn)行覆蓋時，每一根染色體對應(yīng)MFFC覆蓋過程中的1個可行解.染色體采用0-1二進(jìn)制編碼方式，編碼的基本思想是： MFFC中每一個內(nèi)部節(jié)點(diǎn)對應(yīng)染色體中的一位基因，染色體Xi表示一個有δ位的0-1序列串，Xi=(xi1,xi2, …,xiδ).其中，染色體長度δ等于MFFC的內(nèi)部節(jié)點(diǎn)數(shù)加上根節(jié)點(diǎn)的數(shù)目，即MFFC的內(nèi)部節(jié)點(diǎn)數(shù)加1.xiτ表示染色體第τ個基因位上的取值，τ≤δ，也代表AOIG中編號為τ的節(jié)點(diǎn)的取值，xiτ=1表示以節(jié)點(diǎn)τ為根節(jié)點(diǎn)生成當(dāng)前編碼約束下的MFFC.以圖7為例，圖7(a)是圖7(b)中MFFC使用GA覆蓋對應(yīng)的7位0-1染色體編碼，染色體1生成的覆蓋如圖7(b)所示.染色體1中第2、6、7個基因位的值為1，分別生成以節(jié)點(diǎn)2、6、7為根節(jié)點(diǎn)的3個MFFC.同理，染色體2對應(yīng)的覆蓋中將生成以節(jié)點(diǎn)5、7為根節(jié)點(diǎn)的MFFC.但在染色體3中只有5、6基因位的值為1，根節(jié)點(diǎn)7對應(yīng)的基因位的值為0，因此該染色體編碼不能覆蓋整個電路，為錯誤染色體編碼.為避免出現(xiàn)上述錯誤的染色體編碼，在生成染色體初期，將MFFC根節(jié)點(diǎn)對應(yīng)的基因位的值統(tǒng)一設(shè)置為1.

遺傳算子操作主要包括染色體的選擇、交叉和變異.在MFFC的覆蓋過程中，交叉會產(chǎn)生新的染色體，其主要目的是為了探索不同的切割方式；選擇過程將會在種群中留下相對優(yōu)秀的切割方式；變異除了會探索新的切割方式外，更重要的是，防止種群早熟.而在變異過程中，為了使每一根染色體對應(yīng)MFFC的完整覆蓋，預(yù)先設(shè)定MFFC根節(jié)點(diǎn)對應(yīng)的基因位不發(fā)生變異.

GA的求解目標(biāo)是面積的最小覆蓋，適應(yīng)值函數(shù)為

(5)

其中，p表示將整個電路切割成p個MFFC，Si表示第i個MFFC的面積.覆蓋面積越小時，其適應(yīng)值f越大.

算法2為GA和動態(tài)規(guī)劃相結(jié)合的面積優(yōu)化覆蓋算法，偽代碼如下：

Algorithm2GA+DP covering

InputBenchmark circuits(BC)

OutputMinArea

FunctionCalculate minimization area of BC

AIG=read_blif(BC);

MinArea=0;

fori=1 topthen// Step B

n=Inner_node(Vi);

ifn>kthen// Step C

popsize=n*2;

oldpop=initial(popsize);

fitness(oldpop);

find_MinArea(oldpop,best_chrom);

forj=1 to NGthen

mate1=slection(oldpop,popsize);

mate2=slection(oldpop,popsize);

crossover(mate1,mate2,newpop);

mutation(mate1,mate2,newpop);

fitness(newpop);

find_MinArea(newpop,best_chrom);

update_pop(oldpop,newpop);

endfor

else

foreach Node c inVithen// Step D

find_MinArea(c);

endfor

Vi_MinArea=Ni_MinArea;

endif

MinArea=MinArea+Vi_MinArea;

endfor

混合算法中，step A將整個電路切割成多個MFFC，其作用如圖1所示.而MFFC的大小將影響算法的選擇.若MFFC內(nèi)部節(jié)點(diǎn)大于閾值k，則執(zhí)行step C，即GA覆蓋，每一個染色體對應(yīng)MFFC的一種可行切割方式，fitness( )函數(shù)為計(jì)算種群中每個染色體的適應(yīng)值，而計(jì)算由MFFC切割出來的子電路的面積使用本文中的Algorithm 1；若MFFC內(nèi)部節(jié)點(diǎn)小于等于閾值k，執(zhí)行step D，使用動態(tài)規(guī)劃自底向上遍歷MFFC中各個節(jié)點(diǎn)所有可能的切割方式，直至遍歷MFFC的根節(jié)點(diǎn).

最終，整個電路的最小面積等于所有MFFC的最小面積之和.

3 實(shí)驗(yàn)結(jié)果與分析

本文提出的混合算法用C語言實(shí)現(xiàn)，待映射電路的AIG結(jié)構(gòu)由邏輯綜合工具ABC生成，所用的計(jì)算機(jī)配置為Windows 7/64位操作系統(tǒng)，8 GB內(nèi)存和3.30 GHz處理器.遺傳算法的相關(guān)參數(shù)為： 交叉率為0.8，變異率為0.05，最高迭代次數(shù)為500.電路覆蓋過程中，為了提高遺傳算法的效率，其他參數(shù)將根據(jù)MFFC的大小設(shè)置.本文中設(shè)置種群規(guī)模為MFFC內(nèi)部節(jié)點(diǎn)數(shù)目的2倍；當(dāng)MFFC內(nèi)部節(jié)點(diǎn)數(shù)小于等于20時，連續(xù)3代種群最優(yōu)解不發(fā)生變化時算法終止；當(dāng)MFFC內(nèi)部節(jié)點(diǎn)數(shù)大于20時，連續(xù)5代種群最優(yōu)解不發(fā)生變化時算法終止.另外，通過多次實(shí)驗(yàn)，在兼顧解的質(zhì)量和覆蓋速度下，將觸發(fā)2種算法切換的閾值k設(shè)為10.

表1為使用混合算法和動態(tài)規(guī)劃針對MCNC電路的實(shí)驗(yàn)結(jié)果對比，其中動態(tài)規(guī)劃的運(yùn)行環(huán)境與混合算法的運(yùn)行環(huán)境相同.考慮到MFFC的大小和數(shù)量與待優(yōu)化電路的內(nèi)部節(jié)點(diǎn)數(shù)和單扇出節(jié)點(diǎn)數(shù)有關(guān)，因此，本文也將上述數(shù)據(jù)列入表1.表1中的i/o/γ/η分別代表電路的原始輸入、原始輸出、內(nèi)部節(jié)點(diǎn)以及內(nèi)部單扇出節(jié)點(diǎn)數(shù).面積增加百分比指混合算法較動態(tài)規(guī)劃求得的面積最優(yōu)解增加的百分比，時間減少百分比指混合算法較動態(tài)規(guī)劃所用時間減少的百分比.

面積增加百分比=(A2-A1)/A1×100%，

(5)

時間減少百分比=(T1-T2)/T1×100%.

(6)

表1 混合算法與動態(tài)規(guī)劃的實(shí)驗(yàn)結(jié)果對比

從表1中可以看出，當(dāng)電路規(guī)模較小時，本文的混合算法作用不明顯，如電路newapla2.這主要是因?yàn)殡娐份^小時，其內(nèi)部不存在大型MFFC，對每一個MFFC，混合算法也只是使用其中的動態(tài)規(guī)劃策略進(jìn)行覆蓋.對于中小型電路，如電路dk17，其內(nèi)部只有少量MFFC會使用GA進(jìn)行覆蓋，混合算法減少的時間未超過1 ms，統(tǒng)計(jì)時間均為8 ms，速度優(yōu)勢不明顯.由于GA的求解精度不如動態(tài)規(guī)劃，此時，用混合算法求得的面積最優(yōu)解亦不如動態(tài)規(guī)劃.也即，本文的混合算法不適合中小型電路.

同時，從表1中也可以看出，混合算法能有效減少大電路的覆蓋時間，如表1中最大的電路prom1，混合算法的覆蓋時間較動態(tài)規(guī)劃減少了77.20%.這是由于當(dāng)電路面積增大時，其內(nèi)部用于GA覆蓋的MFFC數(shù)量相對增多.除此之外，當(dāng)電路中存在特別大型的MFFC時，GA相對于動態(tài)規(guī)劃的速度優(yōu)勢也非常明顯.以電路i10為例，其內(nèi)部單扇出節(jié)點(diǎn)較為集中，有些MFFC包含的節(jié)點(diǎn)非常多，此時使用混合算法獲得的時間優(yōu)化程度甚至超過了一些規(guī)模更大的電路.

混合算法較于動態(tài)規(guī)劃電路覆蓋時間大幅度縮短的主要原因是在處理內(nèi)部節(jié)點(diǎn)較多的MFFC時使用了GA.當(dāng)電路中的大型MFFC較多時，或者當(dāng)電路中某個MFFC內(nèi)部節(jié)點(diǎn)特別多時，使用混合算法可明顯縮短覆蓋時間.當(dāng)然，速度的優(yōu)勢是以犧牲解的質(zhì)量為代價(jià)的，實(shí)驗(yàn)結(jié)果也表明，混合算法解的質(zhì)量下降并不大. 若將映射時間“<1”統(tǒng)計(jì)為1 ms，相較于動態(tài)規(guī)劃，混合算法平均只犧牲了0.89%的優(yōu)化百分比，但求解時間卻節(jié)省了35.78%.

4 結(jié) 論

所提出的電路面積優(yōu)化方法包含電路覆蓋策略和基于MOS晶體管的動態(tài)單元電路面積估算方法.其中，覆蓋策略是為了平衡求解速度與優(yōu)化效果而提出的將動態(tài)規(guī)劃與遺傳算法相結(jié)合的混合方法.此混合方法同時具有動態(tài)規(guī)劃算法在求解小電路時優(yōu)化效果較好和遺傳算法在求解大電路時速度較快的特點(diǎn).為了提高電路面積的估算精度，利用邏輯努力和基于AOIG動態(tài)單元生成方法，提出了用MOS晶體管溝道寬長比作為衡量電路面積的關(guān)鍵參數(shù).實(shí)驗(yàn)結(jié)果顯示，該優(yōu)化算法在面積增加不到1%的情況下，求解時間節(jié)省了35%以上.