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

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

doi:10.11999/JEIT190095

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

doi: 10.11999/JEIT190095

高丽江^{1, 2},
杨海钢^{1, 2, ,},
李威³,
郝亚男⁴,
刘长龙⁴,
石彩霞¹

1.
中国科学院电子学研究所北京 100190
2.
中国科学院大学北京 100049
3.
中国科学院计算技术研究所北京 100190
4.
中国电子科技集团公司第五十四研究所石家庄 050081

详细信息

作者简介:
高丽江：男，1982年生，博士生，研究方向为可编程芯片结构设计

杨海钢：男，1960年生，研究员，博士生导师，研究方向为大规模集成电路设计、电子设计自动化(EDA)技术

李威：女，副研究员，1983年生，硕士生导师，研究方向为高性能芯片设计技术、大规模集成电路设计、FPGA优化结构

郝亚男：女，1983年生，高级工程师，研究方向为网络与通信SoC架构与芯片设计

刘长龙：男，1985年生，高级工程师，主要研究方向为通信SoC架构与芯片设计

石彩霞：女，1991年生，硕士，研究方向为FPGA CAD设计

通讯作者:
杨海钢　yanghg@mail.ie.ac.cn

中图分类号: TN402
计量
- 文章访问数: 2323
- HTML全文浏览量: 1023
- PDF下载量: 56
- 被引次数: 0
出版历程
- 收稿日期: 2019-02-17
- 修回日期: 2019-04-12
- 网络出版日期: 2019-04-25
- 刊出日期: 2019-10-01

A Circuit Optimization Method of Improved Lookup Table for Highly Efficient Resource Utilization

Lijiang GAO^{1, 2},
Haigang YANG^{1, 2
, ,},
Wei LI³,
Yanan HAO⁴,
Changlong LIU⁴,
Caixia SHI¹

1.
Institure of Electronics, Chinese Academy of Sciences, Beijing 100190, China
2.
University of Chinese Academy of Sciences, Beijing 100049, China
3.
Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
4.
The 54th Research Institute of CETC, Shijiazhuang 050081, China

摘要

摘要: 该文着重研究了FPGA芯片中核心模块基本可编程逻辑单元(BLE)的电路结构与优化设计方法，针对传统4输入查找表(LUT)进行逻辑操作和算术运算时资源利用率低的问题，提出一种融合多路选择器的改进型LUT结构，该结构具有更高面积利用率；同时提出一种对映射后网表进行统计的评估优化方法，可以对综合映射后网表进行重新组合，通过预装箱产生优化后网表；最后，对所提结构进行了实验评估和验证。结果表明：与Intel公司Stratix系列FPGA相比，采用该文所提优化结构，在MCNC电路集和VTR电路集下，资源利用率平均分别提高了10.428% 和 10.433%，有效提升了FPGA的逻辑效能。
- 基本可编程逻辑单元 /
- 查找表 /
- 进位链 /
- 映射 /
- 装箱
Abstract: The circuit structure optimization method for Basic programmable Logic Element (BLE) of FPGA is studied. Considering finding the solution to the bottleneck problem of low resource utilization efficiency in logic and arithmetic operations with 4-input Look Up Table (LUT), some efforts to improve BLE design based on 4-input LUT are explored. A high area-efficient LUT structure is proposed, and the possible benefits of such a new structure are analyzed theoretically and simulated. Further, a statistical method for evaluation of the post synthesis and mapping netlist is also proposed. Finally, a number of experiments are carried out to assess the proposed structure based on the MCNC and VTR benchmarks. The results show that, compared with Intel Stratix series FPGAs, the optimized structure proposed in this paper improves respectively the area efficiency of the FPGA by 10.428% and 10.433% in average under the MCNC and VTR benchmark circuits.
- Basic programmable Logic Element (BLE) /
- Look Up Table (LUT) /
- Carry chain /
- Mapping /
- Packing

HTML全文

图 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.315	10.428

下载: 导出CSV

参考文献(15)

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

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

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

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

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

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.

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.

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.

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

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.

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.

汪宇, 王伶俐, 童家榕. 一种新型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

江政泓, 林郁, 黄志洪, 等. 面向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

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.

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.

施引文献

资源附件(0)

访问统计