| Citation: | Huihong ZHANG, Zhiwen CHEN, Pengjun WANG. Area and Delay Optimization of Binary Decision Diagrams Mapped Circuit[J]. Journal of Electronics & Information Technology, 2019, 41(3): 725-731. doi: 10.11999/JEIT180443
|
Binary Decision Diagrams (BDD) is a data structure that can be used to describe a digital circuit. By replacing each node in a BDD with a 2-to-1 Multiplexer (MUX), a BDD can be mapped to a digital circuit. An area and delay optimization method on BDD mapped circuit is presented. A traditional Boolean circuit is converted into BDD form, and then diamond structure constructed by nodes is searched in the BDD, corresponding nodes are deleted and control signals of the modified nodes are updated by paths optimization, finally, the result BDD is mapped to a MUX circuit. The proposed method is test by a number of Microelectronics Center of North Carolina (MCNC) Benchmarks. Compared with the classical synthesis tools Sequential Interactive System (SIS) and BDD-based logic optimization System (BDS), the average number of nodes by the proposed methods is 55.8% less than that of BDS, and average circuit’s area and delay are reduced by 39.3% and 44.4% than that of the SIS, respectively.
|
DAS A, DEBNATH A, and PRADHAN S. Area, power and temperature optimization during binary decision diagram based circuit synthesis[C]. Devices for Integrated Circuit, Kalyani, India, 2017: 778–782.
|
|
符强, 汪鹏君, 王铭波, 等. 求解FPRM电路极性优化问题的改进多目标粒子群算法[J]. 计算机辅助设计与图形学学报, 2018, 30(3): 540–548. doi: 10.3724/SP.J.1089.2018.16297
FU Qiang, WANG Pengjun, WANG Mingbo, et al. An improved multi-objective particle swarm optimization algorithm for polarity optimization of FPRM circuits[J]. Journal of Computer-Aided Design &Computer Graphics, 2018, 30(3): 540–548. doi: 10.3724/SP.J.1089.2018.16297
|
|
符强, 汪鹏君, 童楠, 等. 基于MODPSO算法的FPRM电路多约束极性优化方法[J]. 电子与信息学报, 2017, 39(3): 717–723. doi: 10.11999/JEIT160458
FU Qiang, WANG Pengjun, TONG Nan, et al. Multi-constrained polarity optimization of large-scale FPRM circuits based on multi-objective discrete particle swarm optimization[J]. Journal of Electronics &Information Technology, 2017, 39(3): 717–723. doi: 10.11999/JEIT160458
|
|
YU Cunxi, CIESIELSKI M, and MISHCHENKO A. Fast algebraic rewriting based on and-inverter graphs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017, 37(9): 1907–1911. doi: 10.1109/TCAD.2017.2772854
|
|
NOUREDDINE M and ZARAKET F. Model checking software with first order logic specifications using AIG solvers[J]. IEEE Transactions on Software Engineering, 2016, 42(8): 741–763. doi: 10.1109/TSE.2016.2520468
|
|
CHUN Chechung, YUNG Chichen, CHUN Yaowang, et al. Majority logic circuits optimisation by node merging[C]. Design Automation Conference, Chiba, Japan, 2017: 714–719.
|
|
AMARU L. New Data Structures and Algorithms for Logic Synthesis and Verification[M]. Switzerland: Springer International Publishing, 2017: 17–19.
|
|
FRIED D, TABAJARA L M, and VARDI M Y. BDD-Based boolean functional synthesis[C]. International Conference on Computer Aided Verification, Toronto, Canada, 2016: 402–421.
|
|
MESKI A, PENZEK W, SZRETER M, et al. BDD-versus SAT-based bounded model checking for the existential fragment of linear temporal logic with knowledge: Algorithms and their performance[J]. Autonomous Agents and Multi-Agent Systems, 2014, 28(4): 558–604. doi: 10.1007/s10458-013-9232-2
|
|
KERTTU M, LINDGREN P, DRECHSLER R, et al. Low power optimization yechnique for BDD mapped finite state machines[C]. International Workshop on Logic & Synthesis, San Diego, USA, 2007: 143–148.
|
|
SHIRINZADEH S, SOEKEN M, and DRECHSLER R. Multi-objective BDD optimization with evolutionary algorithms[C]. Conference on Genetic & Evolutionary Computation, Madrid, Spain, 2015: 751–758.
|
|
YANG Congguang and CIESIELSKI M. BDS: A BDD-based logic optimization system[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002, 21(7): 866–876. doi: 10.1109/TCAD.2002.1013899
|
|
KUBICA M and KANIA D. SMTBDD: New form of BDD for logic synthesis[J]. International Journal of Electronics and Telecommunications, 2016, 62(1): 33–41. doi: 10.1515/eletel-2016-0004
|
|
CHENG Lei, CHEN Deming, and WONG M. Martin DDBDD: Delay-Driven BDD synthesis for FPGAs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(7): 1203–1213. doi: 10.1109/TCAD.2008.923088
|
|
SOMENZI F. CUDD: CU Decision Diagram package release 3.0.0[OL]. http://vlsi.colorado.edu/~fabio/CUDD, 2017.
|
|
BRACE K S, RUDELL R L, and BRYANT R E. Efficient implementation of a BDD package[C]. IEEE Design Automation Conference, Orlando, USA, 1991, 40–45.
|
|
SENTOVICH E M, SINGH K J, LAVAGNO L, et al. SIS: A system for sequential circuit synthesis[OL]. https://embedded.eecs.berkeley.edu/pubs/downloads/sis/index.htm, 2017.
|
|
岑旭梦, 王伦耀, 夏银水. 基于逻辑复合门映射的电路面积优化[J]. 宁波大学学报, 2016, 29(4): 38–43.
CEN Xumeng, WANG Lunyao, and XIA Yinshui. Area optimization based on the complex logic gates mapping[J]. Journal of Ningbo University (NSEE)
|
Figures(6) / Tables(3)
DownLoad:
