具有高資源利用率特征的改進型查找表電路結(jié)構(gòu)與優(yōu)化方法

高麗江; 楊海鋼; 李威; 郝亞男; 劉長龍; 石彩霞

doi:10.11999/JEIT190095

具有高資源利用率特征的改進型查找表電路結(jié)構(gòu)與優(yōu)化方法

doi: 10.11999/JEIT190095

高麗江^{1, 2},
楊海鋼^{1, 2, ,},
李威³,
郝亞男⁴,
劉長龍⁴,
石彩霞¹

1.
中國科學(xué)院電子學(xué)研究所北京 100190
2.
中國科學(xué)院大學(xué) 北京 100049
3.
中國科學(xué)院計算技術(shù)研究所北京 100190
4.
中國電子科技集團公司第五十四研究所石家莊 050081

詳細信息

作者簡介:
高麗江：男，1982年生，博士生，研究方向為可編程芯片結(jié)構(gòu)設(shè)計

楊海鋼：男，1960年生，研究員，博士生導(dǎo)師，研究方向為大規(guī)模集成電路設(shè)計、電子設(shè)計自動化(EDA)技術(shù)

李威：女，副研究員，1983年生，碩士生導(dǎo)師，研究方向為高性能芯片設(shè)計技術(shù)、大規(guī)模集成電路設(shè)計、FPGA優(yōu)化結(jié)構(gòu)

郝亞男：女，1983年生，高級工程師，研究方向為網(wǎng)絡(luò)與通信SoC架構(gòu)與芯片設(shè)計

劉長龍：男，1985年生，高級工程師，主要研究方向為通信SoC架構(gòu)與芯片設(shè)計

石彩霞：女，1991年生，碩士，研究方向為FPGA CAD設(shè)計

通訊作者:
楊海鋼　yanghg@mail.ie.ac.cn

中圖分類號: TN402
計量
- 文章訪問數(shù): 2555
- HTML全文瀏覽量: 1126
- PDF下載量: 58
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2019-02-17
- 修回日期: 2019-04-12
- 網(wǎng)絡(luò)出版日期: 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)的電路結(jié)構(gòu)與優(yōu)化設(shè)計方法，針對傳統(tǒng)4輸入查找表(LUT)進行邏輯操作和算術(shù)運算時資源利用率低的問題，提出一種融合多路選擇器的改進型LUT結(jié)構(gòu)，該結(jié)構(gòu)具有更高面積利用率；同時提出一種對映射后網(wǎng)表進行統(tǒng)計的評估優(yōu)化方法，可以對綜合映射后網(wǎng)表進行重新組合，通過預(yù)裝箱產(chǎn)生優(yōu)化后網(wǎng)表；最后，對所提結(jié)構(gòu)進行了實驗評估和驗證。結(jié)果表明：與Intel公司Stratix系列FPGA相比，采用該文所提優(yōu)化結(jié)構(gòu)，在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結(jié)構(gòu)

下載: 全尺寸圖片幻燈片

圖 2 Stratix傳統(tǒng)查找表結(jié)構(gòu)

下載: 全尺寸圖片幻燈片

圖 3 改進型查找表

下載: 全尺寸圖片幻燈片

圖 4 雙LUT模式示意圖

下載: 全尺寸圖片幻燈片

圖 5 單位全加器運算結(jié)構(gòu)示意圖

下載: 全尺寸圖片幻燈片

圖 6 常規(guī)模式仿真結(jié)果

下載: 全尺寸圖片幻燈片

圖 7 10位加法器波形圖

下載: 全尺寸圖片幻燈片

圖 8 結(jié)構(gòu)評估流程圖

下載: 全尺寸圖片幻燈片

圖 9 MCNC電路集改進比例直方圖

下載: 全尺寸圖片幻燈片

圖 10 VTR電路集改進比例直方圖

下載: 全尺寸圖片幻燈片

表 1 統(tǒng)計程序偽代碼


1 //假設(shè)：lcell_set是電路中所有l(wèi)cell(非算術(shù)模式下，數(shù)據(jù)輸入數(shù)少于等于3)的集合；
2 //　　　Size是lcell_set中l(wèi)cell的數(shù)目；
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共享的輸入數(shù)個數(shù)；
9 //　　　num_ datain(lcell(i))為lcell_set中第i個lcell的數(shù)據(jù)輸入數(shù)；
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　}

下載: 導(dǎo)出CSV

表 2 MCNC與VTR測試電路集測試結(jié)果

MCNC測試電路	優(yōu)化前面積(Stratix結(jié)構(gòu))(單位：個)	可優(yōu)化對數(shù)	VTR測試電路	優(yōu)化前面積(Stratix結(jié)構(gòu))(單位：個)	可優(yōu)化對數(shù)
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

下載: 導(dǎo)出CSV

表 3 MCNC測試電路集下本文結(jié)構(gòu)優(yōu)化效果與WHUpacker優(yōu)化效果對比(%)

	文獻[11]	本文結(jié)構(gòu)
面積減少比例	7.315	10.428

下載: 導(dǎo)出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邏輯單元結(jié)構(gòu)的裝箱工具[J]. 復(fù)旦學(xué)報(自然科學(xué)版), 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結(jié)構(gòu)的FPGA映射工具[J]. 電子與信息學(xué)報, 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.

相關(guān)文章

施引文獻

資源附件(0)

訪問統(tǒng)計