| 基于二分图完善匹配的布尔匹配算法 |
| |
| 引用本文： | 吕宗伟,林争辉,张镭. 基于二分图完善匹配的布尔匹配算法[J]. 计算机辅助设计与图形学学报, 2001, 13(11): 961-965 |
| |
| 作者姓名： | 吕宗伟 林争辉 张镭 |
| |
| 作者单位： | 上海交通大学大规模集成电路研究所,上海,200030 |
| |
| 基金项目： | 美国国家科学基金 ( 5 978East Asia and Pacific Program -96 0 2 485 )资助 |
| |
| 摘 要： | 提出了一种改进的基于二分图完善匹配的布尔匹配算法。该算法通过把布尔变量之间的匹配问题转换为二分图的完善匹配问题，避免了原算法中因乘积项过多而导致计算时间过长的缺点。对MCNC标准测试电路的实验结果表明；与原算法相比，改进后的算法可以减少21％左右的计算时间。同时，文中提出了布尔变量强匹配的概念，它是对传统布尔匹配概念的引申。
|
| 关 键 词： | 逻辑综合 工艺映射 图论 布尔匹配算法 二分图 集成电路 电路设计 |
| 修稿时间： | 2000-09-14 |
Boolean Mapping Algorithm Based on Perfect Matching of Bipartite Graph |
| |
| LU Zong-Wei LIN Zheng-Hui ZHANG Lei. Boolean Mapping Algorithm Based on Perfect Matching of Bipartite Graph[J]. Journal of Computer-Aided Design & Computer Graphics, 2001, 13(11): 961-965 |
| |
| Authors: | LU Zong-Wei LIN Zheng-Hui ZHANG Lei |
| |
| Abstract: | 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. |
| |
| Keywords: | logic synthesis Boolean matching technology mapping graph theory |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
