二叉決策圖映射電路的面積和延時(shí)優(yōu)化

張會(huì)紅; 陳治文; 汪鵬君

doi:10.11999/JEIT180443

二叉決策圖映射電路的面積和延時(shí)優(yōu)化

doi: 10.11999/JEIT180443

寧波大學(xué)電路與系統(tǒng)研究所 ??寧波 ??315000

基金項(xiàng)目: 國(guó)家自然科學(xué)基金(61474068, 61306041)，浙江省公益技術(shù)應(yīng)用研究計(jì)劃項(xiàng)目(2016C31078)，寧波大學(xué)研究生科研創(chuàng)新基金

詳細(xì)信息

作者簡(jiǎn)介:
張會(huì)紅：女，1976年生，副教授，研究方向?yàn)榧呻娐吩O(shè)計(jì)與優(yōu)化、控制理論與應(yīng)用

陳治文：男，1993年生，碩士，研究方向?yàn)榧呻娐愤壿媰?yōu)化

汪鵬君：男，1966年生，教授，博士生導(dǎo)師，研究方向?yàn)榈凸摹⒏咝畔⒚芏燃呻娐泛桶踩酒O(shè)計(jì)及理論研究

通訊作者:
汪鵬君　wangpengjun@nbu.edu.cn

中圖分類(lèi)號(hào): TN79+1; TP391.7
計(jì)量
- 文章訪(fǎng)問(wèn)數(shù): 2706
- HTML全文瀏覽量: 860
- PDF下載量: 60
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2018-05-10
- 修回日期: 2018-11-21
- 網(wǎng)絡(luò)出版日期: 2018-12-04
- 刊出日期: 2019-03-01

Area and Delay Optimization of Binary Decision Diagrams Mapped Circuit

Institute of Circuits and Systems, Ningbo University, Ningbo 315000, China

Funds: The National Natural Science Foundation of China (61474068, 61306041), Zhejiang Province Public Welfare Technology Application Research Project (2016C31078), The Scientific Research Foundation of Graduate School of Ningbo University

摘要

摘要:
二叉決策圖(BDD)是一種數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于數(shù)字電路的邏輯綜合、測(cè)試和驗(yàn)證等領(lǐng)域。將BDD每個(gè)結(jié)點(diǎn)映射成2選1數(shù)據(jù)選擇器(MUX)可得到BDD映射電路。該文提出一種BDD映射電路的面積和延時(shí)優(yōu)化方法。首先把待優(yōu)化電路轉(zhuǎn)換成BDD形式，然后逐一搜索BDD中存在的菱形結(jié)構(gòu)，進(jìn)而通過(guò)路徑優(yōu)化實(shí)現(xiàn)結(jié)點(diǎn)的刪減和控制變量的更改，并將所得結(jié)果BDD映射成MUX電路，最后用多個(gè)MCNC基準(zhǔn)電路進(jìn)行測(cè)試，將該文方法與經(jīng)典綜合工具BDS, SIS等方法相比較，BDD總結(jié)點(diǎn)數(shù)比BDS減少了55.8%，映射電路的面積和延時(shí)比SIS分別減小了39.3%和44.4%。
- 電路優(yōu)化 /
- 二叉決策圖 /
- 數(shù)據(jù)選擇器 /
- 延時(shí)優(yōu)化
Abstract:
Binary Decision Diagrams (BDD) is a data structure that can be used to describe a digital circuit. By replacing each node in a BDD with a 2-to-1 Multiplexer (MUX), a BDD can be mapped to a digital circuit. An area and delay optimization method on BDD mapped circuit is presented. A traditional Boolean circuit is converted into BDD form, and then diamond structure constructed by nodes is searched in the BDD, corresponding nodes are deleted and control signals of the modified nodes are updated by paths optimization, finally, the result BDD is mapped to a MUX circuit. The proposed method is test by a number of Microelectronics Center of North Carolina (MCNC) Benchmarks. Compared with the classical synthesis tools Sequential Interactive System (SIS) and BDD-based logic optimization System (BDS), the average number of nodes by the proposed methods is 55.8% less than that of BDS, and average circuit’s area and delay are reduced by 39.3% and 44.4% than that of the SIS, respectively.
- Circuit optimization /
- Binary Decision Diagrams (BDD) /
- Multiplexer /
- Delay optimization

HTML全文

圖 1 式(1)函數(shù)f 的BDD及其化簡(jiǎn)后的ROBDD

下載: 全尺寸圖片幻燈片

圖 2 菱形結(jié)構(gòu)及其優(yōu)化

下載: 全尺寸圖片幻燈片

圖 3 路徑合并

下載: 全尺寸圖片幻燈片

圖 4 優(yōu)化示例

下載: 全尺寸圖片幻燈片

圖 5 優(yōu)化示例

下載: 全尺寸圖片幻燈片

圖 6 優(yōu)化示例

下載: 全尺寸圖片幻燈片

表 1 本文菱形結(jié)構(gòu)BDD優(yōu)化算法的偽代碼

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

下載: 導(dǎo)出CSV

表 2 所提方法的結(jié)點(diǎn)優(yōu)化情況

電路	輸入/輸出	原結(jié)點(diǎn)	BDS^[12]		DDBDD^[14]		本文方法
電路	輸入/輸出	原結(jié)點(diǎn)	結(jié)點(diǎn)	時(shí)間(s)	結(jié)點(diǎn)	時(shí)間(s)	結(jié)點(diǎn)	時(shí)間(s)	rate₁(%)	rate₂(%)
rd84	8/4	42	73	0.02	84	0.20	19	0.03	73.97	77.38
cordic	23/2	42	49	0.01	66	0.18	39	0.10	20.41	40.91
b12	15/9	55	51	0.01	70	0.18	51	0.01	0	27.14
misex2	25/18	80	71	0.01	93	0.21	78	0.02	–9.86	16.13
duke2	22/29	336	485	0.23	612	1.77	330	0.32	31.96	46.08
in4	32/20	350	371	0.53	412	1.43	346	0.36	6.74	16.02
alu4	14/8	566	1004	0.58	1244	4.78	544	0.78	45.82	56.27
pdc	16/40	602	619	0.49	1042	22.40	572	0.93	7.59	45.11
table5	17/15	667	2276	1.95	2567	17.34	663	0.59	70.87	74.17
table3	14/14	751	2326	1.27	2246	21.24	744	0.75	68.01	66.87
mainpla	27/54	1766	4671	6.70	5347	38.24	1748	4.78	62.58	67.31
b4	33/23	188	—	—	435	1.54	180	1.43	—	58.62
cps	24/108	971	—	—	1415	16.42	958	1.65	—	32.30
平均									34.37	48.02

下載: 導(dǎo)出CSV

表 3 所提方法的面積(a.u.)和延時(shí)(a.u.)優(yōu)化情況

電路	輸入/輸出	SIS^[17]		BBDD^[7]		CGMP^[18]		本文方法		rate_a/rate_d(%)
電路	輸入/輸出	面積	延時(shí)	面積	延時(shí)	面積	延時(shí)	面積	延時(shí)	SIS	BBDD	CGMP
cordic	23/2	194	11	225	14	164	16	162	16	16.5/–45.5	28.0/–14.3	1.2/0
9sym	9/1	528	14	90	7	176	7	125	7	76.3/50.0	–38.9/0	29.0/0
rd84	8/4	402	14	190	7	215	6	166	6	58.7/57.1	12.6/14.3	22.8/0
t2	16/13	645	17	890	13	620	10	483	12	25.1/29.4	45.7/7.7	22.1/–20.0
duke2	22/29	1598	20	4410	17	1836	16	1438	15	10.0/25.0	67.4/11.8	21.7/6.3
alu4	14/8	1614	13	3000	13	2986	8	2532	8	–56.9/38.5	15.6/38.5	15.2/0
misex3	14/14	3668	21	4480	12	2530	8	2030	6	44.7/71.4	54.7/50.0	19.8/25.0
bc0	26/11	4025	24	6250	20	2640	16	2191	15	45.6/37.2	64.9/25.0	17.0/6.3
e64	65/64	4235	16	640	64	1453	12	639	7	84.9/56.3	0.2/89.1	56.0/41.7
table5	17/15	5069	24	4660	15	3024	14	2863	11	43.5/54.2	38.6/26.7	5.3/21.4
table3	14/14	5230	23	4365	12	3876	8	3473	8	33.6/65.2	20.4/33.3	10.4/0
cps	24/108	5525	20	—	—	5013	17	3990	14	27.8/30.0	—	20.4/17.6
平均										34.2/39.1	28.1/25.6	20.1/8.2

下載: 導(dǎo)出CSV

參考文獻(xiàn)(18)

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.

符強(qiáng), 汪鵬君, 王銘波, 等. 求解FPRM電路極性?xún)?yōu)化問(wèn)題的改進(jìn)多目標(biāo)粒子群算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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

符強(qiáng), 汪鵬君, 童楠, 等. 基于MODPSO算法的FPRM電路多約束極性?xún)?yōu)化方法[J]. 電子與信息學(xué)報(bào), 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

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

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

CHUN Chechung, YUNG Chichen, CHUN Yaowang, et al. Majority logic circuits optimisation by node merging[C]. Design Automation Conference, Chiba, Japan, 2017: 714–719.

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

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.

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

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.

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.

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

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

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

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

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.

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.

岑旭夢(mèng), 王倫耀, 夏銀水. 基于邏輯復(fù)合門(mén)映射的電路面積優(yōu)化[J]. 寧波大學(xué)學(xué)報(bào), 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.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪(fǎng)問(wèn)統(tǒng)計(jì)