-
自十九世纪30年代开始就有学者发现并意识到布尔匹配和布尔分类在开关电路中扮演着重要角色,人们开始从各个方面研究电路的设计与优化[1-3]。布尔等价分类和等价匹配作为电路设计和电路优化中的重要技术,逐渐被更多的学者研究[4-5]。
对布尔函数输入或输出的置换运算称为P操作,对输入或输出的非运算称为N操作。根据对布尔函数输入和输出执行P操作和N操作的组合,可产生N变换、P变换、NP变换和NPN变换等,也由此形成了布尔函数的P等价匹配、NP等价匹配和NPN等价匹配。其中NPN等价匹配研究较多,第一个N表示输入非,P表示输入置换,第二个N表示输出非。给定一个
$ n $ 输入布尔函数,其NPN变换共有$ n!{2^{n + 1}} $ 个,采用穷尽法进行匹配,其复杂度是$ O(n!{2^{n + 1}}) $ 。因此,布尔函数的NPN等价分类和匹配是NP难问题。当前,NPN等价分类中n的最大值是10[6]。在数字电路的技术映射和工艺库绑定中,布尔函数NPN等价匹配是一个必要环节,其目的是为当前设计的电路找到一个最优的替代电路[7]。现有的布尔函数NPN等价匹配方法主要集中在成对比较法、基于正规式和基于SAT的方法[8-12]。除此之外,还存在一些基于Walsh谱特征和学习的方法[13-15]。
本文基于对香农扩展定理代数余子式运算的研究发现:1)布尔函数的变量在NP变换中其对称性和独立性不变;2)独立变量具有相位不确定性;3)利用独立变量区分其他变量的不可用性。利用这些特性首先能更早地判定两个布尔函数的不等价性,其次能有效地减少匹配中产生的候选正规式分支数量,从而减少匹配算法的空间复杂度,提高匹配速度。
-
基于MCNC标准电路库中电路和随机生成电路的布尔函数,对本文提出的算法和文献[1]中的基于高阶通用特征的算法进行了测试、比较和验证。测试环境配置为3.3 GHz CPU、8 GB RAM。
n AVG/s A.T/个 AVG[1]/s A.T[1]/个 7 0.00024 1.7 0.00215 66.7 8 0.00591 20.0 0.00989 27.1 9 0.00108 2.1 0.00163 3.0 10 0.00067 1.5 0.00098 2.1 11 0.00138 1.7 0.00283 3.2 12 0.00112 1.6 0.00177 2.7 13 0.01932 5.0 0.04242 7.8 14 0.00507 1.5 0.00713 2.1 15 0.01834 1.7 0.02730 2.4 16 0.01601 1.8 0.02380 2.9 17 0.12548 1.9 0.18872 2.8 18 0.14111 1.8 0.21707 4.4 19 0.68186 1.5 1.13960 3.4 20 1.34587 2.6 1.90159 3.8 21 4.34512 1.3 7.12478 2.0 22 9.30826 2.1 13.95470 4.5 表1为对MCNC标准电路库中电路的布尔函数NPN等价匹配的实验结果,表2为随机生成电路的布尔函数NPN等价匹配的结果。两表中的第1列是变量个数,第2~3列和4~5列是本文和文献[1]算法的匹配平均时间(AVG)和平均候选正规变换数(A.T)。
根据表1中的实验结果可以看出,本文算法对MCNC标准电路库中电路的布尔函数的匹配速度比文献[1]提升了40.1%,搜索空间减少了42.1%。根据表2可以看出本文算法对随机电路的布尔函数匹配速度比文献[1]提升了51%,搜索空间减少75.4%。可以NPN等价匹配对随机电路的布尔函数匹配速度提升更高,其原因是随机产生电路的布尔函数中具有独立变量的情况更多一些。
通过实验可以看出,本文算法能够大大减少计算正规式过程中的搜索空间,并大幅提高了布尔函数匹配速度。
n AVG/s A.T/个 AVG[1]/s A.T[1]/个 7 0.00020 5.4 0.0007 13.2 8 0.00031 4.2 0.0009 22.1 9 0.00055 4.7 0.0010 16.8 10 0.00033 2.8 0.0013 19.6 11 0.00164 3.2 0.0032 19.1 12 0.00372 3.1 0.0068 12.5 13 0.00342 2.9 0.0099 17.2 14 0.00496 3.0 0.0097 14.8 15 0.00352 3.1 0.0078 16.5 16 0.01053 3.8 0.0249 13.9 17 0.01646 4.5 0.0326 23.4 18 0.02117 3.8 0.0423 13.3 19 0.08473 4.2 0.1565 15.8 20 0.07691 4.4 0.1195 12.5 21 0.05598 3.7 0.0859 13.3 22 0.09480 5.4 0.1349 18.3
A Boolean Function NPN Equivalent Matching Algorithm Based on Canonical Form
doi: 10.12178/1001-0548.2022064
- Received Date: 2022-03-07
- Rev Recd Date: 2022-08-31
- Available Online: 2023-01-13
- Publish Date: 2023-01-25
-
Key words:
- Boolean difference /
- canonical form /
- NPN equivalence /
- independent variable /
- Shannon decomposition
Abstract: By studying the operation of the cofactor of Shannon decomposition, six attributes of symmetric variables and independent variables in NP equivalent transformation are found. By making full use of the invariance of the symmetry and independence of variables after NP transformation, the phase uncertainty of independent variables, the unavailability of both independent variables to identify other variables and other variables to identify independent variables in the process of matching, we propose an NPN equivalent matching algorithm based on canonical form. We performed matching experiments on the 7-22 variable Boolean functions of a large number of MCNC benchmark circuits and randomly generated circuits.. The experimental results show that the algorithm of this paper reduces the search space in the matching process by 58.8% and increases matching speed by 45.6% on the two experimental circuit sets compared with the algorithm based on higher order general signature. This indicates that the algorithm of this paper can provide faster and more effective Boolean matching for circuit optimization and circuit mapping.
Citation: | ZHANG Juling, GUO Wenqiang, YANG Xiaomei, ZHU Yixin, YANG Guowu. A Boolean Function NPN Equivalent Matching Algorithm Based on Canonical Form[J]. Journal of University of Electronic Science and Technology of China, 2023, 52(1): 102-107. doi: 10.12178/1001-0548.2022064 |