高级搜索

具有高资源利用率特征的改进型查找表电路结构与优化方法

高丽江 杨海钢 李威 郝亚男 刘长龙 石彩霞

引用本文: 高丽江, 杨海钢, 李威, 郝亚男, 刘长龙, 石彩霞. 具有高资源利用率特征的改进型查找表电路结构与优化方法[J]. 电子与信息学报, 2019, 41(10): 2382-2388. doi: 10.11999/JEIT190095 shu
Citation:  Lijiang GAO, Haigang YANG, Wei LI, Yanan HAO, Changlong LIU, Caixia SHI. A Circuit Optimization Method of Improved Lookup Table for Highly Efficient Resource Utilization[J]. Journal of Electronics and Information Technology, 2019, 41(10): 2382-2388. doi: 10.11999/JEIT190095 shu

具有高资源利用率特征的改进型查找表电路结构与优化方法

    作者简介: 高丽江: 男,1982年生,博士生,研究方向为可编程芯片结构设计;
    杨海钢: 男,1960年生,研究员,博士生导师,研究方向为大规模集成电路设计、电子设计自动化(EDA)技术;
    李威: 女,副研究员,1983年生,硕士生导师,研究方向为高性能芯片设计技术、大规模集成电路设计、FPGA优化结构;
    郝亚男: 女,1983年生,高级工程师,研究方向为网络与通信SoC架构与芯片设计;
    刘长龙: 男,1985年生,高级工程师,主要研究方向为通信SoC架构与芯片设计;
    石彩霞: 女,1991年生,硕士,研究方向为FPGACAD设计
    通讯作者: 杨海钢,yanghg@mail.ie.ac.cn
摘要: 该文着重研究了FPGA芯片中核心模块基本可编程逻辑单元(BLE)的电路结构与优化设计方法,针对传统4输入查找表(LUT)进行逻辑操作和算术运算时资源利用率低的问题,提出一种融合多路选择器的改进型LUT结构,该结构具有更高面积利用率;同时提出一种对映射后网表进行统计的评估优化方法,可以对综合映射后网表进行重新组合,通过预装箱产生优化后网表;最后,对所提结构进行了实验评估和验证。结果表明:与Intel公司Stratix系列FPGA相比,采用该文所提优化结构,在MCNC电路集和VTR电路集下,资源利用率平均分别提高了10.428% 和 10.433%,有效提升了FPGA的逻辑效能。

English

    1. [1]

      ROSE J, FRANCIS R J, LEWIS D, et al. Architecture of field-programmable gate arrays: The effect of logic block functionality on area efficiency[J]. IEEE Journal of Solid-State Circuits, 1990, 25(5): 1217–1225. doi: 10.1109/4.62145

    2. [2]

      Intel Corporation. Stratix device handbook[EB/OL]. San Jose, CA, 2-104-2-129. http://www.altera.com, 2005.

    3. [3]

      GAILLARDON P E, TANG Xifan, KIM G, et al. A novel FPGA architecture based on ultrafine grain reconfigurable logic cells[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2015, 23(10): 2187–2197. doi: 10.1109/TVLSI.2014.2359385

    4. [4]

      SMITH S C. Design of an FPGA logic element for implementing asynchronous null convention logic circuits[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2007, 15(6): 672–683. doi: 10.1109/TVLSI.2007.898726

    5. [5]

      AOKI T, OKAMOTO Y, NAKAGAWA T, et al. Normally-off computing for crystalline oxide semiconductor-based multicontext FPGA capable of fine-grained power gating on programmable logic element with nonvolatile shadow register[J]. IEEE Journal of Solid-State Circuits, 2015, 50(9): 2199–2211. doi: 10.1109/JSSC.2015.2438824

    6. [6]

      PARANDEH-AFSHAR H, ZGHEIB G, NOVO D, et al. Shadow and-inverter cones[C]. The 23rd International Conference on Field Programmable Logic and Applications, Porto, Portugal, 2013: 1–4. doi: 10.1109/FPL.2013.6645566.

    7. [7]

      PROKHOROV A S and TYURIN S F. Modified logical FPGA element[C]. 2017 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, St. Petersburg, Russia, 2017: 973–975.

    8. [8]

      VIKHOREV R V. Improved FPGA logic elements and their simulation[C]. 2018 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, Moscow, Russia, 2018: 259–264.

    9. [9]

      VERCRUYCE D, VANSTEENKISTE E, and STROOBANDT D. How preserving circuit design hierarchy during FPGA packing leads to better performance[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(3): 629–642. doi: 10.1109/TCAD.2017.2717786

    10. [10]

      LIU Ying, JIANG Xianyang, SUN Shilei, et al. An efficient FPGA packing algorithm based on simple dual-output basic logic element[C]. The 8th IEEE International Conference on ASIC, Changsha, China, 2009: 690–693. doi: 10.1109/ASICON.2009.5351300.

    11. [11]

      JIANG Xianyang, LIU Ying, SUN Shilei, et al. An improved packing tool based on a dual-output basic logic element[C]. The 9th IEEE International Conference on ASIC, Xiamen, China, 2011: 377–380.

    12. [12]

      汪宇, 王伶俐, 童家榕. 一种新型FPGA逻辑单元结构的装箱工具[J]. 复旦学报(自然科学版), 2006, 45(4): 529–532. doi: 10.15943/j.cnki.fdxb-jns.2006.04.021
      WANG Yu, WANG Lingli, and TONG Jiarong. Packing tool for a new FPGA logic structure[J]. Journal of Fudan University (Natural Science), 2006, 45(4): 529–532. doi: 10.15943/j.cnki.fdxb-jns.2006.04.021

    13. [13]

      江政泓, 林郁, 黄志洪, 等. 面向AIC结构的FPGA映射工具[J]. 电子与信息学报, 2015, 37(7): 1769–1773. doi: 10.11999/JEIT141403
      JIANG Zhenghong, LIN Yu, HUANG Zhihong, et al. Mapper for AIC-based FPGAs[J]. Journal of Electronics &Information Technology, 2015, 37(7): 1769–1773. doi: 10.11999/JEIT141403

    14. [14]

      YANG S. Logic synthesis and optimization benchmarks user guide, version 3.0[EB/OL]. http://ddd.fit.cvut.cz/prj/Benchmarks/LGSynth91.pdf, 1991: 1–44.

    15. [15]

      MURRAY K E, WHITTY S, LIU Suya, et al. Titan: Enabling large and complex benchmarks in academic CAD[C]. The 23rd International Conference on Field Programmable Logic and Applications, Porto, Portugal, 2013: 1–8.

    1. [1]

      张红旗, 黄睿, 常德显. 一种基于匹配博弈的服务链协同映射方法. 电子与信息学报, 2019, 41(2): 385-393.

    2. [2]

      廖莎莎, 廖柯, 廖希, 刘力. 高形状因子可编程微波光子滤波器集成芯片. 电子与信息学报, 2019, 41(11): 2606-2613.

    3. [3]

      庄雷, 田帅魁, 和孟佯, 宋玉, 王国卿, 刘文覃, 马岭. 基于滑动区域的粒子群虚拟网节能映射算法. 电子与信息学报, 2019, 41(0): 1-7.

    4. [4]

      张会红, 陈治文, 汪鹏君. 二叉决策图映射电路的面积和延时优化. 电子与信息学报, 2019, 41(3): 725-731.

    5. [5]

      和孟佯, 庄雷, 龙卫兵, 王国卿. 基于纳什议价的虚拟网多目标映射算法. 电子与信息学报, 2019, 41(4): 980-986.

    6. [6]

      周牧, 王烟濛, 袁慧, 田增山. 基于Mann-Whitney秩和检验的无线局域网室内映射与定位方法. 电子与信息学报, 2019, 41(7): 1555-1564.

    7. [7]

      涂开辉, 黄志洪, 侯峥嵘, 杨海钢. 基于配置模式匹配和层次化映射结构的高效FPGA码流生成系统研究. 电子与信息学报, 2019, 41(11): 2585-2591.

    8. [8]

      刘焕淋, 林振宇, 王欣, 陈勇, 向敏, 马跃. 弹性光网络中基于安全性感知的差异化虚拟光网络的映射策略. 电子与信息学报, 2019, 41(2): 424-432.

    9. [9]

      王新玉, 李治莹, 邵帅, 虞志刚. 考虑任务不确定性的片上网络鲁棒性应用映射问题研究. 电子与信息学报, 2019, 41(5): 1152-1159.

    10. [10]

      殷茗, 王文杰, 张煊宇, 姜继娇. 一种基于邻接表的最大频繁项集挖掘算法. 电子与信息学报, 2019, 41(8): 2009-2016.

    11. [11]

      胡致远, 宋晓凤, 黄天聪, 李晓娣, 周瑞芳, 徐鑫, 蒙占宇, 彭强. 四表集抄通信网络虚拟化方案及组网算法研究. 电子与信息学报, 2019, 41(3): 588-593.

    12. [12]

      苏玉泽, 孟相如, 康巧燕, 韩晓阳. 核心链路感知的可生存虚拟网络链路保护方法. 电子与信息学报, 2019, 41(7): 1587-1593.

    13. [13]

      伊鹏, 谢记超, 张震, 谷允捷, 赵丹. 抗侧信道攻击的服务功能链部署方法. 电子与信息学报, 2019, 41(11): 2699-2707.

    14. [14]

      路新华, MANCHÓNCarles Navarro, 王忠勇, 张传宗. 大规模MIMO系统上行链路时间-空间结构信道估计算法. 电子与信息学报, 2019, 41(0): 1-7.

    15. [15]

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

    16. [16]

      陈前斌, 杨友超, 周钰, 赵国繁, 唐伦. 基于随机学习的接入网服务功能链部署算法. 电子与信息学报, 2019, 41(2): 417-423.

    17. [17]

      刘江义, 王春平. 基于双马尔科夫链的势概率假设密度滤波. 电子与信息学报, 2019, 41(2): 492-497.

    18. [18]

      黄海, 冯新新, 刘红雨, 厚娇, 赵玉迎, 尹莉莉, 姜久兴. 基于随机加法链的高级加密标准抗侧信道攻击对策. 电子与信息学报, 2019, 41(2): 348-354.

    19. [19]

      李丹, 兰巨龙, 王鹏, 胡宇翔. 基于最长有效功能序列的服务功能链部署算法. 电子与信息学报, 2019, 41(3): 680-686.

    20. [20]

      王凯, 刘树新, 陈鸿昶, 李星. 一种基于节点间资源承载度的链路预测方法. 电子与信息学报, 2019, 41(5): 1225-1234.

  • 图 1  基于查找表的典型BLE结构

    图 2  Stratix传统查找表结构

    图 3  改进型查找表

    图 4  双LUT模式示意图

    图 5  单位全加器运算结构示意图

    图 6  常规模式仿真结果

    图 7  10位加法器波形图

    图 8  结构评估流程图

    图 9  MCNC电路集改进比例直方图

    图 10  VTR电路集改进比例直方图

    表 1  统计程序伪代码

     1 //假设:lcell_set是电路中所有lcell(非算术模式下,数据输入数少于等于3)的集合;
     2 //   Size是lcell_set中lcell的数目;
     3 //   lcell(i)是lcell_set中第i个lcell;
     4 //   Count是满足条件的lcell对;
     5 //   has_cin(lcell(i))表示lcell_set中第i个lcell是否有cin端口,true为有,false为没有;
     6 //   is_reg_mode(lcell(i))表示lcell_set中第i个lcell是否为寄存模式,true为是,false8为否;
     7 //   compare_lcell_pair(lcell(i), lcell(j))为比较两个lcell是否可以组成一个4输入lcell, true为是,false为否;
     8 //   num_share_datain(lcell(i), lcell(j))为两个lcell共享的输入数个数;
     9 //   num_ datain(lcell(i))为lcell_set中第i个lcell的数据输入数;
     10 bool compare_lcell_pair(lcell(i), lcell(j))
     11 {
     12  if(num_datain(lcell(i))==0 || num_datain(lcell(j))==0)
     13  {
     14  return true;
     15  }
     16  if(num_datain(lcell(i)<=2)
     17  {
     18   if(num_share_datain(lcell(i), lcell(j))<=1)
     19   {
     20    return true;
     21   }
     22  }
     23  if(num_datain(lcell(i))==2 && num_datain(lcell(j))==2)
     24  {
     25   return true;
     26  }
     27  if(num_share_datain(lcell(i), lcell(j))==3)
     28  {
     29   return true;
     30  }
     31  if(num_share_datain(lcell(i), lcell(j))==2)
     32  {
     33   return true;
     34  }
     35  return false;
     36 }
     37 for(i=1;i<=size; i++)
     38 {
     39  for(j=1; j<=size; j++)
     40  {
     41   if(i!=j && !(has_cin(lcell(i))==true && has_cin(lcell(j))==true) && !(is_reg_mode (lcell(i)) &&
    is_reg_mode(lcell(j))))
     42   {
     43    if(compare_lcell_pair(lcell(i), lcell(j))==true)
     44    {
     45     count++;
     46    }
     47   }
     48  }
     49 }
    下载: 导出CSV

    表 2  MCNC与VTR测试电路集测试结果

    MCNC测试电路 优化前面积(Stratix结构)(单位:个) 可优化对数 VTR测试电路 优化前面积(Stratix结构)(单位:个) 可优化对数
    spla 1924 92 bgm 19088 3738
    seq 1124 108 blob_merge 6627 129
    s38584 3109 441 boundtop 1793 704
    s38417 3875 716 ch_itrinsics 44 2
    s298 741 80 diffeq1 0 1
    pdc 2278 124 diffeq2 320 5
    misex3 930 101 LU8PEEng 633 66
    frisc 2177 218 LU32PEEng 743 84
    ex1010 853 24 LU64PEEng 785 77
    ex5p 213 26 mcml 78887 6879
    elliptic 1767 283 mkDelayWorker32B 10 0
    dsip 914 53 mkPktMerge 108 15
    des 1234 45 mkSMAdapter4B 9 2
    clma 4787 313 or1200 2873 369
    bigkey 1023 58 raygentop 2818 985
    apex4 842 49 sha 1624 179
    apex2 1051 103 stereovision0 7959 146
    alu4 997 124 stereovision1 9484 54
    stereovision2 38716 2548
    stereovision3 172 13
    spree 1 0
    下载: 导出CSV

    表 3  MCNC测试电路集下本文结构优化效果与WHUpacker优化效果对比(%)

    文献[11]本文结构
    面积减少比例7.31510.428
    下载: 导出CSV
  • 加载中
图(10)表(3)
计量
  • PDF下载量:  18
  • 文章访问数:  544
  • HTML全文浏览量:  352
文章相关
  • 通讯作者:  杨海钢, yanghg@mail.ie.ac.cn
  • 收稿日期:  2019-02-17
  • 录用日期:  2019-04-12
  • 网络出版日期:  2019-04-25
  • 刊出日期:  2019-10-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章