基于对称及特征的NPN布尔匹配算法

张菊玲，杨国武，吴尽昭，郭文强

(1. 电子科技大学计算机科学与工程学院大数据研究中心 成都 611731；2. 广西民族大学广西混杂计算与集成电路设计分析重点实验室 南宁 530006；3. 新疆财经大学计算机科学与工程学院 乌鲁木齐 830012)

在集成电路设计中，判定两个布尔函数(NPN)等价问题具有重要的意义。NPN布尔匹配在电路设计的工艺映射中是一个关键步骤。对于一个给定的电路，工艺映射需要从标准电路库中找到一个与指定电路NPN等价的最优逻辑门组合电路[1-3]。如果布尔函数f与g是NPN等价的，那么就可以使用函数f的电路来实现g的电路。

当前，主要有3种NPN布尔匹配方法。1) 成对比较匹配算法。该方法对于给定的两个布尔函f数与g，通过变量的特征寻找两个函数的变量之间的关系，从而找到可以将f转换为g /的变换[4-7]。2) 基于正规式的算法。该方法从每个NPN等价类中找到具有特殊值的某个布尔函数作为该等价类的正规式。文献[8-13]中的作者研究了基于正规式的布尔匹配算法。正规式通常具有最大或最小真值，或是具有最大特征向量的函数。给定两个待匹配的布尔函数f和g，该类算法分别计算f的正规式F与g的正规式G。如果满足F=G，那么f与g是NPN等价的。3) 基于SAT(boolean satisfiability)的匹配算法，该类算法将布尔匹配问题转换为SAT问题进行求解[14-15]。

1 基本概念及问题陈述

f(x1, x2,… ,xn)是n个输入1个输出的布尔函数，表示函数f的n维向量，文献[7]将f的最小项个数记为|f|。布尔函数可以用真值表、BDD(binary decision diagram)或01串表示。因为采用BDD可以快速的计算布尔函数的香农余子式特征，所以本文采用BDD表示布尔函数。

定义 1 NP变换：NP变换T是对布尔函数输入的非运算和置换运算，其中 π ( i) ∈ { 1,2,… ,n }是对xi的置换。

如π(1)=3表示变量x1被置换为x3；ϕ ( i) ∈{0,1}是对xi的非运算，当ϕ(i)=1时表示对变量xi做非运算，否则不做非运算。

定义 2 NPN等价：函数 f(X)和g(X)是NPN等价的，当且仅当存在一个NP变换T满足条件f(T X) = g(X )或者

定义 3 变量映射：NP变换T也可表示为在向量X上的一组映射。若布尔函数 f和g在NP变换T的作用下是NP等价的，那么函数f中的变量xi与函数g中的变量xπ(i)之间有映射

变量xi和xj之间存在的映射分为两种情况：1)同相映射异相映射例1中的NP变换T可以表示为：

定义 4 变量对称：布尔函数f中的变量xi与xj/是对称的，当且仅当交换xi与xj/之后函数f的值不变。

当变量xi和xj满足条件时，变量xi与变量xj对称；当变量xi和xj满足条件时，xi变量对称。

定义 7 1阶特征向量：具有n个输入的布尔函数 f有n个变量，n个变量的1阶特征集合称为函数 f的特征向量，记为

两个NP等价的布尔函数具有相同的1阶特征向量；若函数 f与g是NP等价的，并且变量xi和xj之间有映射关系，xi和xj一定具有相同的1阶特征[7]。

定义 8 变量映射集：布尔匹配中，布尔函数f的变量xi的所有变量映射构成xi的变量映射集，记为

布尔函数 f与g的匹配中， f的变量xi可能有零个或多个变量映射，|χi|记为变量xi的变量映射集的阶，即变量xi具有的可能映射的个数。

因为NP变换不会改变变量的对称性，所以对称变量和非对称变量之间不存在映射。

香农引理也称为香农分解，可以将n变量输入的布尔函数f分解为两个n-1变量输入的布尔函数。若函数 f和函数g关于是NP等价的，那么利用T中任意变量映射中的两个变量分解后得的两组函数一定也是NP等价的。假设T中有映射 xi→xj， f按xi分解得到，g按xj分解得到f1与g1是NP等价的，f2与g2是NP等价的。这里的变量xi和xj被称为分解变量。

本文NPN布尔匹配的基本思想是：对于给定的两个待匹配的布尔函数f和g，通过变量的1阶特征和香农分解搜索两个函数的变量之间的映射关系T，检测是否满足 f (T X) = g(X)或者

2 提出的NPN布尔匹配算法

2.1 相位分配

给定两个布尔函数f和g，NPN匹配需要确定对函数的输入非、输入置换和输出非：

1) 输出非：NPN等价的两个布尔函数具有相同或互补的最小项个数。若|f|=|g|且|f|≠||， f 无非运算，f和g同为正相；若|f|=||且|f|≠|g|，f有非运算， f为正相g为反相；若|f|=||且|f|=|g|，可能有输出非，可能没有输出非，f为正相g的相位不定。

2) 输入非：若变量xi和xj之间有映射关系，并且它们是同相位的，xi无非运算；如果它们是相反相位的，xi有非运算。若| fxi|＞||，xi的相位为正；若| fxi|＜||，xi的相位为反；若| fxi|=||，xi的相位不能确定。

3) 输入置换：若变量xi和xj具有相同的1阶特征，那么它们之间可能存在映射。

满足式(1)时，两个变量是同相；满足式(2)时，两个变量是反相；同时满足式(1)和式(2)，两个变量的相位不能确定，相位需要后续判定或同时检测同相和反相两种情况。

2.2 候选变换搜索

给定要匹配的布尔函数f和g，本算法的目的是找到一个NP变换T，该变换能够将 f转换为g或者。对于任意n变量输入的布尔函数 f，有 n ! 2n+1个NPN变换，但是能够将f转换为g/的是少数。本算法通过对称和1阶特征向量搜索在 f和g之间可能存在的NP变换，这些变换称为候选变换。每找到一个候选变换就验证该候选变换是否能将f转换为g/。

每个候选变换由n个变量映射组成，本算法根据函数f和g的1阶特征向量及香农分解来搜索它们之间可能存在的NP变换。假设当前搜索函数f的变量xi的映射，有以下几种情况：

1) 函数g中只有一个变量xj与其具有相同的1阶特征，并且变量xi的相位确定。那么|χi|=1，xi的映射唯一。

2) 函数g中只有一个变量xj与其具有相同的1阶特征，并且变量xi的相位不确定。那么|χi|=2，算法生成映射 xi→xj和算法先处理xi→xj，如果该映射所生成的NP变换不能将f转换为然后再处理

3) 变量xi是非对称变量且相位确定，g有变量xj1, xj2,… ,xjk与其有相同的1阶特征。那么|χi|=k，本算法按顺序先生成xi和xj1之间的映射并处理由此映射所产生的NP变换。如果该NP变换不能将f转换为g/g，那么算法选取下一个即xi和xj2之间的映射处理，直到有一个NP变换可以将f转换为g/或χi中所有的映射处理完毕。

4) 变量xi是非对称变量并且相位不确定，g中有变量 xj1, xj2,… ,xjk与其有相同的1阶特征。那么|χi|= 2 k ，算法检测映射集处理方式同步骤3)。

5) 变量xi是对称变量且相位确定，所在对称类是中只有一个对称类与Si具有相同的变量个数和相同的1阶特征。那么|βi|=1，算法只需检测由Si和Sj之间产生的一个种映射关系即可。

6) 变量xi是对称变量且相位不确定，所在对称类为函数g中只有一个对称类与Si具有相同的变量个数和相同的1阶特征。令xi和xj分别为同相和异相两种情况，在Si与Sj之间可以产生2组不同映射关系，即|βi|=2。算法先处理同相，若同相所产生的NP变换不能将 f转换为g/，再处理异相。

7) 变量xi是对称变量且相位确定，所在对称类为，g有对称类 Sj1, Sj2,… ,Sjk均与Si具有相同的变量个数和相同的1阶特征。那么，对称类Si有k组对称映射关系，即|βi|= k ，算法依次处理每一种对称映射关系，直到找到一个NP变换将f转换为g/或所有的对称映射关系处理完毕。

8) 变量xi是对称变量且相位不确定，所在对称类为有对称类 Sj1,SJ2,… ,Sjk均与Si具有相同的变量个数和相同的1阶特征。那么由于这些对称类中变量的相位都是不确定的，算法在处理每个对称映射关系时需要考虑正相和反相两种情况，因此对称类Si有2k组对称映射关系，即|βi|= 2 k。对这2k组对称映射关系的处理方式与情况7相同。

本算法采用树来存储每个变量可能的映射，树中的每个节点是一个变量的一个映射，树共有n层。若第k层只有一个节点，那么该层的变量只有一个映射；如果有多个节点，那么该层的变量有多个可能的映射。这颗树称之为候选变换树，该树的每个分支为一个候选NP变换。本算法采用深度优先搜索方式，只要找到一个满足条件的候选变换，算法就终止。用伪代码描述的候选变换搜索如下：

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是否产生一个完整分支，每产生一个完整分支即生成一个候选变换T，Procedure 1调用verify()验证T。data_f和data_g是由分解变量构成的两个BDD表达式。data_f和data_g的初始值为常量bddtrue，函数Search()每调用一次需要更新data_f和data_g。若第k次调用时的分解变量分别是 xl和 xp，那么data_f=data_f∧xl,data_g=data_g∧xp。 然 后 ， Procedure 1 调 用compute_vector()更新变量的1阶特征并判断两个1阶特征向量是否相等，如果不相等则返回0。

2.3 匹配算法

NPN布尔匹配可描述如下：给定两个布尔函数f(X )和g(X)，是否存在一个NP变换T使得条件f(T X) = g (X)或f(T X) =成立，如果存在这样的T，那么 f(X)与g(X)NPN等价，否则，f(X)与g(X )不NPN等价。

匹配算法首先确定函数f和g的相位，如果相位能够确定，则计算f和g/的1阶特征向量，同时计算变量的相位。然后，比较两个1阶特征向量是否相等。如果不相等，则 f和g不NPN等价；如果相等，则调用Search()函数。如果Search()返回1，则f和g是NPN等价的，否则，不NPN等价。

1) data_f=bddtrue，data_g=bddtrue，建立 f和g的BDD，计算1阶特征向量，结果为Vf={(9,7), (8,8),(8,8), (8,8), (8,8)}, Vg={(8,8), (8,8), (8,8), (8,8),(9,7)}。经过对称检测得到函数 f有对称类S2={x2,x5}，函数g有对称类 S2={x2,x4}。根据1阶特征向量可知f的变量x1相位为正，g的变量x5相位为正，其他变量相位不能确定。计算f中每个变量的变量映射集，可得 χ1= { x1→ x5}是第一个要处理的映射集，data_f更新为x1,data_g更新为x5。

2) 更新1阶特征向量，结果为：Vf={(0,0), (5,4),(4,5), (4,5), (5,4)}, Vg={(4,5), (5,4), (4,5), (4,5),(0,0)}，已经确定了的映射关系中的变量的1阶特征更新为(0,0)。从该结果可以看出，所有变量的相位已经确定，并且可以得到 χ2= { S2→ S2}是当前要处理的映射集。算法搜索到一种对称映射关系更新data_f为x1x2、data_g为x5x2。

3) 更新1阶特征向量，结果为Vf={(0,0), (0,0),(2,3), (3,2), (0,0)},Vg={(2,3), (0,0), (3,2), (0,0), (0,0)}。搜索到要处理的映射集为。算法选择第一个变量映射处理并更新data_f和data_g，并且

4) 更新1阶特征向量，结果为Vf={(0,0), (0,0),(0,0), (1,2), (0,0)}, Vg={(0,0), (0,0), (1,2), (0,0), (0,0)}。搜索到变量映射集至此，找到一个候选变换通过验证 f (T X) = g(X )，所以f和g是NPN等价的。

图1 例1的候选变换树

例2的候选变换树如图1所示。步中要处理的变量映射集是 χ2= { x2→ x2,x2→那么其候选变换树中的第二层将会产生4个分支。从例1可以看出，本算法相对文献[7]的搜索空间减小了很多，其主要原因是对称变量的使用。

3 实验结果

使用本算法在大量的电路函数中进行测试，并与文献[7]的结果进行对比。测试中检测了等价和非等价电路函数的匹配速度，测试电路包括随机生成的电路函数和部分MCNC标准电路库中的函数。实验设备的配置为3.3 GHz CPU、4 GB RAM。

表1～表3列出了对等价和非等价电路匹配测试的结果，包括匹配的最短时间、最长时间和平均时间，运行时间以秒为单位。表1中列出了对MCNC标准电路库的等价电路函数的匹配运行结果，表2中列出了对随机产生的等价电路函数的匹配运行结果。

表1 等价的MCNC标准电路函数匹配测试结果 s

表2 等价随机电路函数匹配测试结果 s

5变量输入布尔函数有NP变换 5 !25个，例1中的候选变换树总共可能的NP变换为2个，匹配中验证第一个NP变换后算法就终止了。如果采用文献[7]中的算法对例1的两个函数进行匹配，在上述的第2

从等价的测试中可以看出，就平均匹配速度而言，在MCNC等价电路匹配测试中，本算法相比文献[7]的算法提高了86%；在随机等价电路匹配中相比文献[7]的算法提高了83%。本算法对非等价电路函数匹配结果如表3所示。

表3 非等价电路函数匹配测试结果 s

从非等价电路匹配测试结果中可以看出，本算法相对文献[7]中的算法，平均匹配速度提高了79%。

整体来说，本算法实现了快速的NPN布尔匹配，是一种非常有效的NPN布尔匹配算法。

4 结 束 语

本文提出了一种基于对称及特征的NPN布尔匹配算法，通过1阶特征向量和香农分解建立两个布尔函数之间的变量映射，采用深度优先搜索查找使得一个布尔函数转换为另外一个布尔函数的NP变换。利用变量的对称特性进一步减少了候选NP变换的搜索空间，从而提高了NPN布尔匹配的速度。通过实验证明了本算法的有效性，能够应用于电路设计的工艺映射中。未来的研究方向是将本算法扩展到多输出布尔函数及含有无关项的布尔函数的NPN等价匹配中。