基于二分图完美匹配的布尔匹配算法  

Boolean Mapping Algorithm Based on Perfect Matching of Bipartite Graph

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

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

出　　处：《计算机辅助设计与图形学学报》2001年第11期961-965,共5页Journal of Computer-Aided Design & Computer Graphics

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

摘　　要：提出了一种改进的基于二分图完美匹配的布尔匹配算法 .该算法通过把布尔变量之间的匹配问题转换为二分图的完美匹配问题 ,避免了原算法中因乘积项过多而导致计算时间过长的缺点 .对 MCNC标准测试电路的实验结果表明 :与原算法相比 ,改进后的算法可以减少 2 1%左右的计算时间 .同时 ,文中提出了布尔变量强匹配的概念 ,它是对传统布尔匹配概念的引申 .An improved Boolean matching algorithm based on transforming the mapping between Boolean variables into the problem of perfect matching of bipartite graph is presented. This approach can overcome the shortcoming of the original algorithm, i.e., lengthy computation time caused by the excessive product terms. Experiments on MCNC benchmarks show that the improved approach can reduce computation time by about 21% compared to the original algorithm. Also, the concept of strong matching between Boolean variables is put forward as the generalization of conventional Boolean variable mapping.

关 键 词：逻辑综合 工艺映射 图论 布尔匹配算法 二分图 集成电路 电路设计 

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