高级搜索

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

张会红 陈治文 汪鹏君

引用本文: 张会红, 陈治文, 汪鹏君. 二叉决策图映射电路的面积和延时优化[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]

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

    2. [2]

      庄陵, 关鹃, 马靖怡, 王光宇. 一种基于结构优化的FIR滤波器舍入噪声性能改进方案. 电子与信息学报, 2019, 41(4): 932-938.

    3. [3]

      丛雯珊, 余岚, 沃江海. 基于粒子群算法的宽带真延时方向图栅瓣抑制方法. 电子与信息学报, 2019, 41(7): 1698-1704.

    4. [4]

      何灏, 易卫东, 陈永锐, 王喆. 基于无迹卡尔曼滤波估计的无线传感器网络时钟分辨率优化. 电子与信息学报, 2019, 41(3): 687-693.

    5. [5]

      刘小强, 袁国顺, 乔树山. FPGA硬核处理器系统加速数字电路功能验证的方法. 电子与信息学报, 2019, 41(5): 1251-1256.

    6. [6]

      赵星, 彭建华, 游伟. 基于Lyapunov优化的隐私感知计算卸载方法. 电子与信息学报, 2019, 41(0): 1-8.

    7. [7]

      金松坡, 庄珊娜. 基于序列优化的认知雷达稳健旁瓣抑制方法. 电子与信息学报, 2019, 41(9): 2131-2136.

    8. [8]

      杨善超, 田康生, 刘仁争, 郑玉军. 基于价值优化的相控阵雷达任务调度算法. 电子与信息学报, 2019, 41(0): 1-7.

    9. [9]

      黄容兰, 刘云, 李啟尚, 唐文. 基于非正交多址接入中继通信系统的功率优化. 电子与信息学报, 2019, 41(8): 1909-1915.

    10. [10]

      兰巨龙, 于倡和, 胡宇翔, 李子勇. 基于深度增强学习的软件定义网络路由优化机制. 电子与信息学报, 2019, 41(0): 1-6.

    11. [11]

      景小荣, 陶红宝. 一种稀疏码本多址接入码本优化设计方法. 电子与信息学报, 2019, 41(1): 24-31.

    12. [12]

      卢昱, 刘益岑, 李玺, 陈兴凯, 乔文欣, 陈立云. 面向软件定义网络的服务功能链优化部署算法研究. 电子与信息学报, 2019, 41(1): 74-82.

    13. [13]

      张颖, 姚雨丰. 基于快速贝叶斯匹配追踪优化的海上稀疏信道估计方法. 电子与信息学报, 2019, 41(0): 1-7.

    14. [14]

      曾芳玲, 欧阳晓凤, 徐浩, 吕大千. 基于时频融合的长码直接捕获优化算法研究. 电子与信息学报, 2019, 41(2): 309-316.

    15. [15]

      史久根, 徐皓, 张径, 王继. 软件定义网络中基于效率区间的负载均衡在线优化算法. 电子与信息学报, 2019, 41(3): 694-701.

    16. [16]

      史久根, 张径, 徐皓, 王继, 孙立. 一种面向运营成本优化的虚拟网络功能部署和路由分配策略. 电子与信息学报, 2019, 41(4): 973-979.

    17. [17]

      李如春, 程云霄, 覃亚丽. 稀疏信号结构性噪声干扰下的感知矩阵优化. 电子与信息学报, 2019, 41(4): 911-916.

    18. [18]

      冯维, 徐永鑫, 刘浩, 许晓荣, 姚英彪. 无线多跳网络快速跨层资源优化分配算法. 电子与信息学报, 2019, 41(5): 1217-1224.

    19. [19]

      张海波, 李虎, 陈善学, 贺晓帆. 超密集网络中基于移动边缘计算的任务卸载和资源优化. 电子与信息学报, 2019, 41(5): 1194-1201.

    20. [20]

      刘政怡, 徐天泽. 基于优化的极限学习机和深度层次的RGB-D显著检测. 电子与信息学报, 2019, 41(9): 2224-2230.

  • 图 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下载量:  25
  • 文章访问数:  581
  • HTML全文浏览量:  142
文章相关
  • 通讯作者:  汪鹏君, 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搜索

/

返回文章