二叉决策图映射电路的面积和延时优化
|
摘要
二叉决策图(BDD)是一种数据结构,广泛应用于数字电路的逻辑综合、测试和验证等领域。将BDD每个结点映射成2选1数据选择器(MUX)可得到BDD映射电路。该文提出一种BDD映射电路的面积和延时优化方法。首先把待优化电路转换成BDD形式,然后逐一搜索BDD中存在的菱形结构,进而通过路径优化实现结点的删减和控制变量的更改,并将所得结果BDD映射成MUX电路,最后用多个MCNC基准电路进行测试,将该文方法与经典综合工具BDS, SIS等方法相比较,BDD总结点数比BDS减少了55.8%,映射电路的面积和延时比SIS分别减小了39.3%和44.4%。
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.
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.
引文
[1]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.
[2]符强,汪鹏君,王铭波,等.求解FPRM电路极性优化问题的改进多目标粒子群算法[J].计算机辅助设计与图形学学报, 2018,30(3):540–548. doi:10.3724/SP.J.1089.2018.16297.FU Qiang, WANG Pengjun, WANG Mingbo, et al. An improvedmulti-objective particles warmoptimization 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.
[3]符强,汪鹏君,童楠,等.基于MODPSO算法的FPRM电路多约束极性优化方法[J].电子与信息学报, 2017, 39(3):717–723.doi:10.11999/JEIT160458.FU Qiang, WANG Pengjun, TONG Nan, et al. Multiconstrained 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.
[4]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.
[5]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.
[6]CHUN Chechung, YUNG Chichen, CHUN Yaowang, et al.Majority logic circuits optimisation by node merging[C].Design Automation Conference,Chiba,Japan,2017:714–719.
[7]AMARU L. New Data Structures and Algorithms for Logic Synthesis and Verification[M].Switzerland:Springer International Publishing, 2017:17–19.
[8]FRIED D, TABAJARA L M, and VARDI M Y. BDD Basedboolean function alsynthesis[C].International Conference on Computer Aided Verification,Toronto,Canada, 2016:402–421.
[9]MESKI A, PENZEK W, SZRETER M, et al. BDD-versus SAT-based bounded model checking for the existential fragment of lineartem porallogic 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.
[10]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.
[11]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.
[12]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.
[13]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.
[14]CHENGLei,CHENDeming,andWONGM.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.
[15]SOMENZI F. CUDD:CU Decision Diagram package release3.0.0[OL]. http://vlsi.colorado.edu/~fabio/CUDD, 2017.
[16]BRACE K S, RUDELL R L, and BRYANT R E. Efficient implementation of a BDD package[C].IEEEDesign Automation Conference, Orlando, USA, 1991, 40–45.
[17]SENTOVICH E M, SINGH K J, LAVAGNO L, et al. SIS:Asystem for sequential circuit synthesis[OL].https://embedded.eecs.berkeley.edu/pubs/downloads/sis/in dex.htm, 2017.
[18]岑旭梦,王伦耀,夏银水.基于逻辑复合门映射的电路面积优化[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), 2016, 29(4):38–43.
[2]符强,汪鹏君,王铭波,等.求解FPRM电路极性优化问题的改进多目标粒子群算法[J].计算机辅助设计与图形学学报, 2018,30(3):540–548. doi:10.3724/SP.J.1089.2018.16297.FU Qiang, WANG Pengjun, WANG Mingbo, et al. An improvedmulti-objective particles warmoptimization 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.
[3]符强,汪鹏君,童楠,等.基于MODPSO算法的FPRM电路多约束极性优化方法[J].电子与信息学报, 2017, 39(3):717–723.doi:10.11999/JEIT160458.FU Qiang, WANG Pengjun, TONG Nan, et al. Multiconstrained 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.
[4]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.
[5]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.
[6]CHUN Chechung, YUNG Chichen, CHUN Yaowang, et al.Majority logic circuits optimisation by node merging[C].Design Automation Conference,Chiba,Japan,2017:714–719.
[7]AMARU L. New Data Structures and Algorithms for Logic Synthesis and Verification[M].Switzerland:Springer International Publishing, 2017:17–19.
[8]FRIED D, TABAJARA L M, and VARDI M Y. BDD Basedboolean function alsynthesis[C].International Conference on Computer Aided Verification,Toronto,Canada, 2016:402–421.
[9]MESKI A, PENZEK W, SZRETER M, et al. BDD-versus SAT-based bounded model checking for the existential fragment of lineartem porallogic 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.
[10]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.
[11]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.
[12]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.
[13]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.
[14]CHENGLei,CHENDeming,andWONGM.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.
[15]SOMENZI F. CUDD:CU Decision Diagram package release3.0.0[OL]. http://vlsi.colorado.edu/~fabio/CUDD, 2017.
[16]BRACE K S, RUDELL R L, and BRYANT R E. Efficient implementation of a BDD package[C].IEEEDesign Automation Conference, Orlando, USA, 1991, 40–45.
[17]SENTOVICH E M, SINGH K J, LAVAGNO L, et al. SIS:Asystem for sequential circuit synthesis[OL].https://embedded.eecs.berkeley.edu/pubs/downloads/sis/in dex.htm, 2017.
[18]岑旭梦,王伦耀,夏银水.基于逻辑复合门映射的电路面积优化[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), 2016, 29(4):38–43.