加速布尔匹配算法的研究  

Research Over Speeding up Boolean Matching

作　　者：张镭[1] 林争辉[1] 吕宗伟[1] 

机构地区：[1]上海交通大学大规模集成电路研究所,上海200030

出　　处：《上海交通大学学报》2002年第3期319-322,共4页Journal of Shanghai Jiaotong University

基　　金：美国国家科学基金资助项目 ( 5 978East Asia andPacific Program -96 0 2 485 )

摘　　要：逻辑验证和综合中 ,布尔匹配利用有序二叉判定图 (Ordered Binary Decision Diagram,OBDD)检验两个给定的逻辑函数是否相等 .直接枚举每个函数中输入变量的各种排列顺序 ,并根据这些顺序进行匹配 ,算法时间复杂度为 O(n!2 n2 ) ,n为变量数 .为了提高匹配算法的效率 ,文中用最小项数目作为标签标定变量 (变量组 ) .对比两函数中变量 (变量组 )的标签 ,可删除不可能的排序 ,加快匹配过程 .在此基础之上 ,利用重构将待匹配变量压缩在 OBDD图的底部 .利用这部分结构可以进一步区分变量 .实验结果表明 ,该算法不仅变量区分能力要好于其他算法 ,且执行速度快 。In logic verification and logic synthesis, Boolean matching is widely used to testify whether two given function is logically equal by means of OBDD. Without any pretreatment, the time complexity of matching algorithm is O(n!2 n2) in the light of all the possible orders of variables, where n is the number of variables. In order to improve the efficiency of matching algorithm, the numbers of minterms connected with every single variable or every variable composition are used as “signature” of the variables. The impossible orders of variables are pruned during matching and time is saved. This paper introduced a new method to distinguish variables, which reduces variables unrecognized to the bottom of OBDD by restructuring. According to those parts of OBDD, variables can be efficiently recognized. The experiment results show that the algorithm in this paper can distinguish variables in some complex circuits while others can't.

关 键 词：布尔匹配算法 大规模集成电路 变量标签 最小项 有序二叉判定树 

分 类 号：TN47[电子电信—微电子学与固体电子学]