基于對(duì)稱及特征的NPN布爾匹配算法

張菊玲，楊國(guó)武，吳盡昭，郭文強(qiáng)

(1. 電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院大數(shù)據(jù)研究中心 成都 611731；2. 廣西民族大學(xué)廣西混雜計(jì)算與集成電路設(shè)計(jì)分析重點(diǎn)實(shí)驗(yàn)室 南寧 530006；3. 新疆財(cái)經(jīng)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 烏魯木齊 830012)

在集成電路設(shè)計(jì)中，判定兩個(gè)布爾函數(shù)(NPN)等價(jià)問(wèn)題具有重要的意義。NPN布爾匹配在電路設(shè)計(jì)的工藝映射中是一個(gè)關(guān)鍵步驟。對(duì)于一個(gè)給定的電路，工藝映射需要從標(biāo)準(zhǔn)電路庫(kù)中找到一個(gè)與指定電路NPN等價(jià)的最優(yōu)邏輯門組合電路[1-3]。如果布爾函數(shù)f與g是NPN等價(jià)的，那么就可以使用函數(shù)f的電路來(lái)實(shí)現(xiàn)g的電路。

當(dāng)前，主要有3種NPN布爾匹配方法。1) 成對(duì)比較匹配算法。該方法對(duì)于給定的兩個(gè)布爾函f數(shù)與g，通過(guò)變量的特征尋找兩個(gè)函數(shù)的變量之間的關(guān)系，從而找到可以將f轉(zhuǎn)換為g /的變換[4-7]。2) 基于正規(guī)式的算法。該方法從每個(gè)NPN等價(jià)類中找到具有特殊值的某個(gè)布爾函數(shù)作為該等價(jià)類的正規(guī)式。文獻(xiàn)[8-13]中的作者研究了基于正規(guī)式的布爾匹配算法。正規(guī)式通常具有最大或最小真值，或是具有最大特征向量的函數(shù)。給定兩個(gè)待匹配的布爾函數(shù)f和g，該類算法分別計(jì)算f的正規(guī)式F與g的正規(guī)式G。如果滿足F=G，那么f與g是NPN等價(jià)的。3) 基于SAT(boolean satisfiability)的匹配算法，該類算法將布爾匹配問(wèn)題轉(zhuǎn)換為SAT問(wèn)題進(jìn)行求解[14-15]。

1 基本概念及問(wèn)題陳述

f(x1, x2,… ,xn)是n個(gè)輸入1個(gè)輸出的布爾函數(shù)，表示函數(shù)f的n維向量，文獻(xiàn)[7]將f的最小項(xiàng)個(gè)數(shù)記為|f|。布爾函數(shù)可以用真值表、BDD(binary decision diagram)或01串表示。因?yàn)椴捎肂DD可以快速的計(jì)算布爾函數(shù)的香農(nóng)余子式特征，所以本文采用BDD表示布爾函數(shù)。

定義 1 NP變換：NP變換T是對(duì)布爾函數(shù)輸入的非運(yùn)算和置換運(yùn)算，其中 π ( i) ∈ { 1,2,… ,n }是對(duì)xi的置換。

如π(1)=3表示變量x1被置換為x3；? ( i) ∈{0,1}是對(duì)xi的非運(yùn)算，當(dāng)?(i)=1時(shí)表示對(duì)變量xi做非運(yùn)算，否則不做非運(yùn)算。

定義 2 NPN等價(jià)：函數(shù) f(X)和g(X)是NPN等價(jià)的，當(dāng)且僅當(dāng)存在一個(gè)NP變換T滿足條件f(T X) = g(X )或者

定義 3 變量映射：NP變換T也可表示為在向量X上的一組映射。若布爾函數(shù) f和g在NP變換T的作用下是NP等價(jià)的，那么函數(shù)f中的變量xi與函數(shù)g中的變量xπ(i)之間有映射

變量xi和xj之間存在的映射分為兩種情況：1)同相映射異相映射例1中的NP變換T可以表示為：

定義 4 變量對(duì)稱：布爾函數(shù)f中的變量xi與xj/是對(duì)稱的，當(dāng)且僅當(dāng)交換xi與xj/之后函數(shù)f的值不變。

當(dāng)變量xi和xj滿足條件時(shí)，變量xi與變量xj對(duì)稱；當(dāng)變量xi和xj滿足條件時(shí)，xi變量對(duì)稱。

定義 7 1階特征向量：具有n個(gè)輸入的布爾函數(shù) f有n個(gè)變量，n個(gè)變量的1階特征集合稱為函數(shù) f的特征向量，記為

兩個(gè)NP等價(jià)的布爾函數(shù)具有相同的1階特征向量；若函數(shù) f與g是NP等價(jià)的，并且變量xi和xj之間有映射關(guān)系，xi和xj一定具有相同的1階特征[7]。

定義 8 變量映射集：布爾匹配中，布爾函數(shù)f的變量xi的所有變量映射構(gòu)成xi的變量映射集，記為

布爾函數(shù) f與g的匹配中， f的變量xi可能有零個(gè)或多個(gè)變量映射，|χi|記為變量xi的變量映射集的階，即變量xi具有的可能映射的個(gè)數(shù)。

因?yàn)镹P變換不會(huì)改變變量的對(duì)稱性，所以對(duì)稱變量和非對(duì)稱變量之間不存在映射。

香農(nóng)引理也稱為香農(nóng)分解，可以將n變量輸入的布爾函數(shù)f分解為兩個(gè)n-1變量輸入的布爾函數(shù)。若函數(shù) f和函數(shù)g關(guān)于是NP等價(jià)的，那么利用T中任意變量映射中的兩個(gè)變量分解后得的兩組函數(shù)一定也是NP等價(jià)的。假設(shè)T中有映射 xi→xj， f按xi分解得到，g按xj分解得到f1與g1是NP等價(jià)的，f2與g2是NP等價(jià)的。這里的變量xi和xj被稱為分解變量。

本文NPN布爾匹配的基本思想是：對(duì)于給定的兩個(gè)待匹配的布爾函數(shù)f和g，通過(guò)變量的1階特征和香農(nóng)分解搜索兩個(gè)函數(shù)的變量之間的映射關(guān)系T，檢測(cè)是否滿足 f (T X) = g(X)或者

2 提出的NPN布爾匹配算法

2.1 相位分配

給定兩個(gè)布爾函數(shù)f和g，NPN匹配需要確定對(duì)函數(shù)的輸入非、輸入置換和輸出非：

1) 輸出非：NPN等價(jià)的兩個(gè)布爾函數(shù)具有相同或互補(bǔ)的最小項(xiàng)個(gè)數(shù)。若|f|=|g|且|f|≠|(zhì)|， f 無(wú)非運(yùn)算，f和g同為正相；若|f|=||且|f|≠|(zhì)g|，f有非運(yùn)算， f為正相g為反相；若|f|=||且|f|=|g|，可能有輸出非，可能沒(méi)有輸出非，f為正相g的相位不定。

2) 輸入非：若變量xi和xj之間有映射關(guān)系，并且它們是同相位的，xi無(wú)非運(yùn)算；如果它們是相反相位的，xi有非運(yùn)算。若| fxi|＞||，xi的相位為正；若| fxi|＜||，xi的相位為反；若| fxi|=||，xi的相位不能確定。

3) 輸入置換：若變量xi和xj具有相同的1階特征，那么它們之間可能存在映射。

滿足式(1)時(shí)，兩個(gè)變量是同相；滿足式(2)時(shí)，兩個(gè)變量是反相；同時(shí)滿足式(1)和式(2)，兩個(gè)變量的相位不能確定，相位需要后續(xù)判定或同時(shí)檢測(cè)同相和反相兩種情況。

2.2 候選變換搜索

給定要匹配的布爾函數(shù)f和g，本算法的目的是找到一個(gè)NP變換T，該變換能夠?qū)?f轉(zhuǎn)換為g或者。對(duì)于任意n變量輸入的布爾函數(shù) f，有 n ! 2n+1個(gè)NPN變換，但是能夠?qū)轉(zhuǎn)換為g/的是少數(shù)。本算法通過(guò)對(duì)稱和1階特征向量搜索在 f和g之間可能存在的NP變換，這些變換稱為候選變換。每找到一個(gè)候選變換就驗(yàn)證該候選變換是否能將f轉(zhuǎn)換為g/。

每個(gè)候選變換由n個(gè)變量映射組成，本算法根據(jù)函數(shù)f和g的1階特征向量及香農(nóng)分解來(lái)搜索它們之間可能存在的NP變換。假設(shè)當(dāng)前搜索函數(shù)f的變量xi的映射，有以下幾種情況：

1) 函數(shù)g中只有一個(gè)變量xj與其具有相同的1階特征，并且變量xi的相位確定。那么|χi|=1，xi的映射唯一。

2) 函數(shù)g中只有一個(gè)變量xj與其具有相同的1階特征，并且變量xi的相位不確定。那么|χi|=2，算法生成映射 xi→xj和算法先處理xi→xj，如果該映射所生成的NP變換不能將f轉(zhuǎn)換為然后再處理

3) 變量xi是非對(duì)稱變量且相位確定，g有變量xj1, xj2,… ,xjk與其有相同的1階特征。那么|χi|=k，本算法按順序先生成xi和xj1之間的映射并處理由此映射所產(chǎn)生的NP變換。如果該NP變換不能將f轉(zhuǎn)換為g/g，那么算法選取下一個(gè)即xi和xj2之間的映射處理，直到有一個(gè)NP變換可以將f轉(zhuǎn)換為g/或χi中所有的映射處理完畢。

4) 變量xi是非對(duì)稱變量并且相位不確定，g中有變量 xj1, xj2,… ,xjk與其有相同的1階特征。那么|χi|= 2 k ，算法檢測(cè)映射集處理方式同步驟3)。

5) 變量xi是對(duì)稱變量且相位確定，所在對(duì)稱類是中只有一個(gè)對(duì)稱類與Si具有相同的變量個(gè)數(shù)和相同的1階特征。那么|βi|=1，算法只需檢測(cè)由Si和Sj之間產(chǎn)生的一個(gè)種映射關(guān)系即可。

6) 變量xi是對(duì)稱變量且相位不確定，所在對(duì)稱類為函數(shù)g中只有一個(gè)對(duì)稱類與Si具有相同的變量個(gè)數(shù)和相同的1階特征。令xi和xj分別為同相和異相兩種情況，在Si與Sj之間可以產(chǎn)生2組不同映射關(guān)系，即|βi|=2。算法先處理同相，若同相所產(chǎn)生的NP變換不能將 f轉(zhuǎn)換為g/，再處理異相。

7) 變量xi是對(duì)稱變量且相位確定，所在對(duì)稱類為，g有對(duì)稱類 Sj1, Sj2,… ,Sjk均與Si具有相同的變量個(gè)數(shù)和相同的1階特征。那么，對(duì)稱類Si有k組對(duì)稱映射關(guān)系，即|βi|= k ，算法依次處理每一種對(duì)稱映射關(guān)系，直到找到一個(gè)NP變換將f轉(zhuǎn)換為g/或所有的對(duì)稱映射關(guān)系處理完畢。

8) 變量xi是對(duì)稱變量且相位不確定，所在對(duì)稱類為有對(duì)稱類 Sj1,SJ2,… ,Sjk均與Si具有相同的變量個(gè)數(shù)和相同的1階特征。那么由于這些對(duì)稱類中變量的相位都是不確定的，算法在處理每個(gè)對(duì)稱映射關(guān)系時(shí)需要考慮正相和反相兩種情況，因此對(duì)稱類Si有2k組對(duì)稱映射關(guān)系，即|βi|= 2 k。對(duì)這2k組對(duì)稱映射關(guān)系的處理方式與情況7相同。

本算法采用樹來(lái)存儲(chǔ)每個(gè)變量可能的映射，樹中的每個(gè)節(jié)點(diǎn)是一個(gè)變量的一個(gè)映射，樹共有n層。若第k層只有一個(gè)節(jié)點(diǎn)，那么該層的變量只有一個(gè)映射；如果有多個(gè)節(jié)點(diǎn)，那么該層的變量有多個(gè)可能的映射。這顆樹稱之為候選變換樹，該樹的每個(gè)分支為一個(gè)候選NP變換。本算法采用深度優(yōu)先搜索方式，只要找到一個(gè)滿足條件的候選變換，算法就終止。用偽代碼描述的候選變換搜索如下：

Procedure 1 Search Transformation

Input data_f, data_g, f, g, map_tree

Output 0 or 1

Function Search(data_f, data_g, f, g, map_tree)

Int min_num=32 768, min;

If D1

Generate a candidate transformation

Return Verify(f, g, map_tree)

Else if compute_vector(f, g, data_f, data_g)=0 then

Return 0

Else

For each xi∈f(X)

|χi/βi|=num(xi, f, g)

If |χi|=1 then

αi→map_tree

Else if |βi|=1

βi→map_tree

Else if |βi|=k1

If (k1＜min_num)

min_num= k1

min=i

End if

Else // |χi|=k2

If(k2＜min_num)

min_num= k2

min=i

End if

End if

End for

If |χi|=1 || |βi|=1

Update data_f, data_g

Search(data_f, data_g, f, g, map_tree)

Else

For each α∈χminor β∈βmin

α/β→map_tree

Update data_f, data_g

Search(data_f, data_g, f, g, map_tree)

End for

End if

Return 0

End function

Procedure 1中的條件D1表示map_tree是否產(chǎn)生一個(gè)完整分支，每產(chǎn)生一個(gè)完整分支即生成一個(gè)候選變換T，Procedure 1調(diào)用verify()驗(yàn)證T。data_f和data_g是由分解變量構(gòu)成的兩個(gè)BDD表達(dá)式。data_f和data_g的初始值為常量bddtrue，函數(shù)Search()每調(diào)用一次需要更新data_f和data_g。若第k次調(diào)用時(shí)的分解變量分別是 xl和 xp，那么data_f=data_f∧xl,data_g=data_g∧xp。 然 后 ， Procedure 1 調(diào) 用compute_vector()更新變量的1階特征并判斷兩個(gè)1階特征向量是否相等，如果不相等則返回0。

2.3 匹配算法

NPN布爾匹配可描述如下：給定兩個(gè)布爾函數(shù)f(X )和g(X)，是否存在一個(gè)NP變換T使得條件f(T X) = g (X)或f(T X) =成立，如果存在這樣的T，那么 f(X)與g(X)NPN等價(jià)，否則，f(X)與g(X )不NPN等價(jià)。

匹配算法首先確定函數(shù)f和g的相位，如果相位能夠確定，則計(jì)算f和g/的1階特征向量，同時(shí)計(jì)算變量的相位。然后，比較兩個(gè)1階特征向量是否相等。如果不相等，則 f和g不NPN等價(jià)；如果相等，則調(diào)用Search()函數(shù)。如果Search()返回1，則f和g是NPN等價(jià)的，否則，不NPN等價(jià)。

1) data_f=bddtrue，data_g=bddtrue，建立 f和g的BDD，計(jì)算1階特征向量，結(jié)果為Vf={(9,7), (8,8),(8,8), (8,8), (8,8)}, Vg={(8,8), (8,8), (8,8), (8,8),(9,7)}。經(jīng)過(guò)對(duì)稱檢測(cè)得到函數(shù) f有對(duì)稱類S2={x2,x5}，函數(shù)g有對(duì)稱類 S2={x2,x4}。根據(jù)1階特征向量可知f的變量x1相位為正，g的變量x5相位為正，其他變量相位不能確定。計(jì)算f中每個(gè)變量的變量映射集，可得 χ1= { x1→ x5}是第一個(gè)要處理的映射集，data_f更新為x1,data_g更新為x5。

2) 更新1階特征向量，結(jié)果為：Vf={(0,0), (5,4),(4,5), (4,5), (5,4)}, Vg={(4,5), (5,4), (4,5), (4,5),(0,0)}，已經(jīng)確定了的映射關(guān)系中的變量的1階特征更新為(0,0)。從該結(jié)果可以看出，所有變量的相位已經(jīng)確定，并且可以得到 χ2= { S2→ S2}是當(dāng)前要處理的映射集。算法搜索到一種對(duì)稱映射關(guān)系更新data_f為x1x2、data_g為x5x2。

3) 更新1階特征向量，結(jié)果為Vf={(0,0), (0,0),(2,3), (3,2), (0,0)},Vg={(2,3), (0,0), (3,2), (0,0), (0,0)}。搜索到要處理的映射集為。算法選擇第一個(gè)變量映射處理并更新data_f和data_g，并且

4) 更新1階特征向量，結(jié)果為Vf={(0,0), (0,0),(0,0), (1,2), (0,0)}, Vg={(0,0), (0,0), (1,2), (0,0), (0,0)}。搜索到變量映射集至此，找到一個(gè)候選變換通過(guò)驗(yàn)證 f (T X) = g(X )，所以f和g是NPN等價(jià)的。

圖1 例1的候選變換樹

例2的候選變換樹如圖1所示。步中要處理的變量映射集是 χ2= { x2→ x2,x2→那么其候選變換樹中的第二層將會(huì)產(chǎn)生4個(gè)分支。從例1可以看出，本算法相對(duì)文獻(xiàn)[7]的搜索空間減小了很多，其主要原因是對(duì)稱變量的使用。

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

使用本算法在大量的電路函數(shù)中進(jìn)行測(cè)試，并與文獻(xiàn)[7]的結(jié)果進(jìn)行對(duì)比。測(cè)試中檢測(cè)了等價(jià)和非等價(jià)電路函數(shù)的匹配速度，測(cè)試電路包括隨機(jī)生成的電路函數(shù)和部分MCNC標(biāo)準(zhǔn)電路庫(kù)中的函數(shù)。實(shí)驗(yàn)設(shè)備的配置為3.3 GHz CPU、4 GB RAM。

表1～表3列出了對(duì)等價(jià)和非等價(jià)電路匹配測(cè)試的結(jié)果，包括匹配的最短時(shí)間、最長(zhǎng)時(shí)間和平均時(shí)間，運(yùn)行時(shí)間以秒為單位。表1中列出了對(duì)MCNC標(biāo)準(zhǔn)電路庫(kù)的等價(jià)電路函數(shù)的匹配運(yùn)行結(jié)果，表2中列出了對(duì)隨機(jī)產(chǎn)生的等價(jià)電路函數(shù)的匹配運(yùn)行結(jié)果。

表1 等價(jià)的MCNC標(biāo)準(zhǔn)電路函數(shù)匹配測(cè)試結(jié)果 s

表2 等價(jià)隨機(jī)電路函數(shù)匹配測(cè)試結(jié)果 s

5變量輸入布爾函數(shù)有NP變換 5 !25個(gè)，例1中的候選變換樹總共可能的NP變換為2個(gè)，匹配中驗(yàn)證第一個(gè)NP變換后算法就終止了。如果采用文獻(xiàn)[7]中的算法對(duì)例1的兩個(gè)函數(shù)進(jìn)行匹配，在上述的第2

從等價(jià)的測(cè)試中可以看出，就平均匹配速度而言，在MCNC等價(jià)電路匹配測(cè)試中，本算法相比文獻(xiàn)[7]的算法提高了86%；在隨機(jī)等價(jià)電路匹配中相比文獻(xiàn)[7]的算法提高了83%。本算法對(duì)非等價(jià)電路函數(shù)匹配結(jié)果如表3所示。

表3 非等價(jià)電路函數(shù)匹配測(cè)試結(jié)果 s

從非等價(jià)電路匹配測(cè)試結(jié)果中可以看出，本算法相對(duì)文獻(xiàn)[7]中的算法，平均匹配速度提高了79%。

整體來(lái)說(shuō)，本算法實(shí)現(xiàn)了快速的NPN布爾匹配，是一種非常有效的NPN布爾匹配算法。

4 結(jié) 束 語(yǔ)

本文提出了一種基于對(duì)稱及特征的NPN布爾匹配算法，通過(guò)1階特征向量和香農(nóng)分解建立兩個(gè)布爾函數(shù)之間的變量映射，采用深度優(yōu)先搜索查找使得一個(gè)布爾函數(shù)轉(zhuǎn)換為另外一個(gè)布爾函數(shù)的NP變換。利用變量的對(duì)稱特性進(jìn)一步減少了候選NP變換的搜索空間，從而提高了NPN布爾匹配的速度。通過(guò)實(shí)驗(yàn)證明了本算法的有效性，能夠應(yīng)用于電路設(shè)計(jì)的工藝映射中。未來(lái)的研究方向是將本算法擴(kuò)展到多輸出布爾函數(shù)及含有無(wú)關(guān)項(xiàng)的布爾函數(shù)的NPN等價(jià)匹配中。