高级搜索

二叉决策图映射电路的面积和延时优化

张会红 陈治文 汪鹏君

引用本文: 张会红, 陈治文, 汪鹏君. 二叉决策图映射电路的面积和延时优化[J]. 电子与信息学报, 2019, 41(3): 725-731. doi: 10.11999/JEIT180443 shu
Citation:  Huihong ZHANG, Zhiwen CHEN, Pengjun WANG. Area and Delay Optimization of Binary Decision Diagrams Mapped Circuit[J]. Journal of Electronics and Information Technology, 2019, 41(3): 725-731. doi: 10.11999/JEIT180443 shu

二叉决策图映射电路的面积和延时优化

    作者简介: 张会红: 女,1976年生,副教授,研究方向为集成电路设计与优化、控制理论与应用;
    陈治文: 男,1993年生,硕士,研究方向为集成电路逻辑优化;
    汪鹏君: 男,1966年生,教授,博士生导师,研究方向为低功耗、高信息密度集成电路和安全芯片设计及理论研究
    通讯作者: 汪鹏君,wangpengjun@nbu.edu.cn
  • 基金项目: 国家自然科学基金(61474068, 61306041),浙江省公益技术应用研究计划项目(2016C31078),宁波大学研究生科研创新基金

摘要: 二叉决策图(BDD)是一种数据结构,广泛应用于数字电路的逻辑综合、测试和验证等领域。将BDD每个结点映射成2选1数据选择器(MUX)可得到BDD映射电路。该文提出一种BDD映射电路的面积和延时优化方法。首先把待优化电路转换成BDD形式,然后逐一搜索BDD中存在的菱形结构,进而通过路径优化实现结点的删减和控制变量的更改,并将所得结果BDD映射成MUX电路,最后用多个MCNC基准电路进行测试,将该文方法与经典综合工具BDS, SIS等方法相比较,BDD总结点数比BDS减少了55.8%,映射电路的面积和延时比SIS分别减小了39.3%和44.4%。

English

    1. [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. [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 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

    3. [3]

      符强, 汪鹏君, 童楠, 等. 基于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

    4. [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. [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. [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. [7]

      AMARU L. New Data Structures and Algorithms for Logic Synthesis and Verification[M]. Switzerland: Springer International Publishing, 2017: 17–19.

    8. [8]

      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.

    9. [9]

      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

    10. [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. [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. [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. [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. [14]

      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

    15. [15]

      SOMENZI F. CUDD: CU Decision Diagram package release 3.0.0[OL]. http://vlsi.colorado.edu/~fabio/CUDD, 2017.

    16. [16]

      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.

    17. [17]

      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.

    18. [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.

    1. [1]

      李龙, 古天龙, 常亮, 徐周波, 钱俊彦. 快速解密且私钥定长的密文策略属性基加密方案. 电子与信息学报, 2018, 40(7): 1661-1668.

    2. [2]

      秋小强, 杨海钢, 周发标, 谢元禄. 长互连链延时功耗建模与基于混合粒子群算法的优化. 电子与信息学报, 2011, 33(6): 1481-1486.

    3. [3]

      杭大明, 马正新, 曹志刚. 无线网络中平均功率受限的延时确保调度机制的最优化研究. 电子与信息学报, 2006, 28(2): 272-276.

    4. [4]

      姜文彬. 多路选择器树形结构逻辑网络设计. 电子与信息学报, 1992, 14(1): 21-28.

    5. [5]

      吴建军, 梁庆林, 项海格. 非相干UWB-PPM接收机前置滤波器带宽的优化选择. 电子与信息学报, 2007, 29(9): 2161-2167.

    6. [6]

      谭文, 王耀南, 黄创霞, 伍雪冬. 不确定蔡氏电路混沌系统的神经网络优化控制. 电子与信息学报, 2007, 29(7): 1749-1752.

    7. [7]

      符强, 汪鹏君, 童楠, 王铭波, 张会红. 基于MODPSO算法的FPRM电路多约束极性优化方法. 电子与信息学报, 2017, 39(3): 717-723.

    8. [8]

      张会红, 汪鹏君, 俞海珍. 基于新型极性转换技术的XNOR/OR电路面积优化. 电子与信息学报, 2012, 34(7): 1767-1772.

    9. [9]

      王少庆, 林为干, 张梅. 短槽混合电路功率合成器的优化设计. 电子与信息学报, 1994, 16(2): 198-202.

    10. [10]

      陆跃, 沈永朝. 一个开关电容电路的模拟和优化程序. 电子与信息学报, 1987, 9(5): 395-403.

    11. [11]

      曹韬, 刘友江, 杨春, 周劼. 高效宽带包络跟踪系统电路性能优化及非线性行为校正. 电子与信息学报, 2019, 41(0): 1-8.

    12. [12]

      高伟, 黄建国, 徐振华, 张群飞. 基于二阶锥优化方法的MIMO阵列发射方向图设计. 电子与信息学报, 2012, 34(5): 1126-1130.

    13. [13]

      吕增威, 魏振春, 韩江洪, 孙仁浩, 夏成凯. 基于多目标优化的无线传感器网络移动充电及数据收集算法. 电子与信息学报, 2019, 41(8): 1877-1884.

    14. [14]

      胡文龙, 毛士艺. 基于组合优化的多传感器多目标数据互联. 电子与信息学报, 1996, 18(6): 561-566.

    15. [15]

      王小华, 何怡刚, 彭玉楼. 二维线性相位FIR数字滤波器的优化设计. 电子与信息学报, 2005, 27(11): 1755-1759.

    16. [16]

      丁治国, 郭立, 朱学永, 汪赵华. 基于二叉树分解的自适应防碰撞算法. 电子与信息学报, 2009, 31(6): 1395-1399.

    17. [17]

      张江霄, 郭华, 李舟军. 基于逆序二叉树的高效可分电子现金系统. 电子与信息学报, 2014, 36(1): 22-26.

    18. [18]

      张磊, 潘泉, 张洪才, 戴冠中. 基于二叉树搜索的小波变换信号压缩. 电子与信息学报, 2002, 24(5): 615-620.

    19. [19]

      高丽江, 杨海钢, 李威, 郝亚男, 刘长龙, 石彩霞. 具有高资源利用率特征的改进型查找表电路结构与优化方法. 电子与信息学报, 2019, 41(10): 2382-2388.

    20. [20]

      王文远. 基于图像信噪比选择优化高斯滤波尺度. 电子与信息学报, 2009, 31(10): 2483-2487.

  • 图 1  式(1)函数f 的BDD及其化简后的ROBDD

    图 2  菱形结构及其优化

    图 3  路径合并

    图 4  优化示例

    图 5  优化示例

    图 6  优化示例

    表 1  本文菱形结构BDD优化算法的伪代码

     Begin algorithm
     Read_pla_benchmark_circuit();
     Apply_CUDD_package(); //obtain circuit’s BDD
     Number_nodes(); //number nodes from 1 to num_of_BDD
     M=0;
     While (M<num_of_BDD) //handle all the non-terminals
      M=M+1;
      if(is_nodeM_diamond_structure()) //judge nodeM
       compute_mixed_paths();
       reconstruct_BDD();
      End if
     End while
     Output_logic_circuit();
     Apply_area_model(); //calculate area and delay according to
     model
     Apply_delay_model();
     Output_results();
     Free_memory_unit();
     End algorithm
    下载: 导出CSV

    表 2  所提方法的结点优化情况

    电路输入/输出原结点BDS[12]DDBDD[14]本文方法
    结点时间(s)结点时间(s)结点时间(s)rate1(%)rate2(%)
    rd848/442730.02840.20190.0373.9777.38
    cordic23/242490.01660.18390.1020.4140.91
    b1215/955510.01700.18510.01027.14
    misex225/1880710.01930.21780.02–9.8616.13
    duke222/293364850.236121.773300.3231.9646.08
    in432/203503710.534121.433460.366.7416.02
    alu414/856610040.5812444.785440.7845.8256.27
    pdc16/406026190.49104222.405720.937.5945.11
    table517/1566722761.95256717.346630.5970.8774.17
    table314/1475123261.27224621.247440.7568.0166.87
    mainpla27/54176646716.70534738.2417484.7862.5867.31
    b433/231884351.541801.4358.62
    cps24/108971141516.429581.6532.30
    平均34.3748.02
    下载: 导出CSV

    表 3  所提方法的面积(a.u.)和延时(a.u.)优化情况

    电路输入/输出SIS[17] BBDD[7] CGMP[18] 本文方法 ratea/rated(%)
    面积延时面积延时面积延时面积延时SISBBDDCGMP
    cordic23/219411 22514 16416 16216 16.5/–45.528.0/–14.31.2/0
    9sym9/1528149071767125776.3/50.0–38.9/029.0/0
    rd848/44021419072156166658.7/57.112.6/14.322.8/0
    t216/136451789013620104831225.1/29.445.7/7.722.1/–20.0
    duke222/2915982044101718361614381510.0/25.067.4/11.821.7/6.3
    alu414/81614133000132986825328–56.9/38.515.6/38.515.2/0
    misex314/14366821448012253082030644.7/71.454.7/50.019.8/25.0
    bc026/1140252462502026401621911545.6/37.264.9/25.017.0/6.3
    e6465/6442351664064145312639784.9/56.30.2/89.156.0/41.7
    table517/1550692446601530241428631143.5/54.238.6/26.75.3/21.4
    table314/14523023436512387683473833.6/65.220.4/33.310.4/0
    cps24/10855252050131739901427.8/30.020.4/17.6
    平均34.2/39.128.1/25.620.1/8.2
    下载: 导出CSV
  • 加载中
图(6)表(3)
计量
  • PDF下载量:  27
  • 文章访问数:  1198
  • HTML全文浏览量:  196
文章相关
  • 通讯作者:  汪鹏君, wangpengjun@nbu.edu.cn
  • 收稿日期:  2018-05-10
  • 录用日期:  2018-11-21
  • 网络出版日期:  2018-12-04
  • 刊出日期:  2019-03-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章