基于近似计算技术的多级逻辑电路面积优化

赵维凯; 王伦耀; 岑旭梦; 夏银水; 储著飞

doi:10.13700/j.bh.1001-5965.2022.0742

基于近似计算技术的多级逻辑电路面积优化

doi: 10.13700/j.bh.1001-5965.2022.0742

1.
宁波大学信息科学与工程学院，宁波 315211
2.
宁波大学科学技术学院信息工程学院，宁波 315300

基金项目: 国家自然科学基金(U1709218,61471211,61871242)

详细信息

通讯作者:
E-mail：wanglunyao@nbu.edu.cn

中图分类号: TN431.2
计量
- 文章访问数: 221
- HTML全文浏览量: 109
- PDF下载量: 12
- 被引次数: 0
出版历程
- 收稿日期: 2022-08-29
- 录用日期: 2022-09-16
- 网络出版日期: 2022-11-01
- 整期出版日期: 2024-09-27

Area optimization of multilevel logic circuits using approximate computing

1.
Faculty of Electrical Engineering and Computer Science，Ningbo University，Ningbo 315211，China
2.
School of Information Engineering，College of Science & Technology Ningbo University，Ningbo 315300，China

Funds: National Natural Science Foundation of China (U1709218,61471211,61871242)

More Information

Corresponding author: E-mail：wanglunyao@nbu.edu.cn

摘要

摘要:
针对现有多级逻辑近似优化算法在大型电路优化时无法较好兼顾优化效果与算法速度的问题，提出一种基于常量替换的多级逻辑电路面积优化算法。该算法通过在与非图(AIG)中引入节点输出距离、常量传输距离等参数，并结合提出的多扇出节点常量替换过程中错误率控制方法，在全局范围内提取合适替换的候选节点集和每个候选节点输出的常量替换值；同时，通过根据电路规模选取不同的错误率计算方法等策略，实现了错误率约束下的多级逻辑电路面积近似优化并使算法速度得到提高。所提算法用C语言和ABC内置命令编程实现，使用EPFL及MCNC电路进行测试。实验结果表明：所提算法与已提出的常量替换方法相比，面积优化效果提升48.77%；相较于近似关心集重代换的近似逻辑综合(ALSRAC)优化算法，所提算法在面积优化和运算时间上分别有1.28%和60.91%的提升。
- 多级电路 /
- 近似计算 /
- 误差约束 /
- 常量替换 /
- 逻辑优化
Abstract:
According to the reported multi-level logic approximation optimization algorithm which can not balance the optimization effect and working speed well for largecircuits. It is proposed to use constant substitution in conjunction with and-inverter-graph (AIG) to optimize the logic at multiple levels for circuit areas. A set of candidate nodes to be replaced and a constant value for the node to be replaced are determined by employing the proposed error rate control technique of constant substitution of multiple fan-out nodes and a number of parameters known as node output distance, constant transmission distance, and so forth. Furthermore, according to the circuit size, different error rate calculation methods are selected to improve the speed of the algorithm. The proposed algorithm is programmed in C and implemented with the ABC tool and tested with EPFL and MCNC bench-marks. The experimental results show, compared with the report's similar methods, the proposed algorithm can save 48.77% area. When compared to approximate logic synthesis by resubstitution with approximate care (ALSRAC), this method achieves a 1.28% increase in area optimization and a 60.91% reduction in running time.
- multi-level circuit /
- approximate computing /
- error constraint /
- constant substitution /
- logic optimization

HTML全文

图 1 C17电路AIG

Figure 1. AIG of C17 circuit

下载: 全尺寸图片幻灯片

图 2 Miter电路

Figure 2. Miter circuit

下载: 全尺寸图片幻灯片

图 3 节点9扇出的不同常量替换结果

Figure 3. Results of the different constant replacement for node 9 fanout

下载: 全尺寸图片幻灯片

图 4 M_C17电路的AIG

Figure 4. AIG of benchmark M_C17

下载: 全尺寸图片幻灯片

图 5 对C17中节点9不同扇出优化结果

Figure 5. Optimization results for different fanouts of node 9 in C17

下载: 全尺寸图片幻灯片

表 1 本文使用的MCNC和EPFL测试电路参数

Table 1. Parameters of MCNC and EPFL benchmarks used in this paper

MCNC	电路输入端口数量	电路输出端口数量	初始面积	EPFL	电路输入端口数量	电路输出端口数量	初始面积
cm163	16	5	61	arbiter	25	129	23366
z4ml	7	4	61	cavlc	10	11	1124
alu2	10	6	636	ctrl	7	26	204
frg1	28	3	179	dec	8	256	649
alu4	14	8	1158	i2c	147	142	2103
unreg	36	16	163	int2float	11	7	379
x2	10	7	74	mem_ctrl	1204	1231	79153
count	35	16	203	priority	128	8	1270
term1	34	10	276	router	60	30	316
				voter	1001	1	16240

下载: 导出CSV

表 2 本文算法与文献[10]的比较结果

Table 2. Comparison results of the proposed algorithms and Ref.[10] %

电路名称	面积优化		延时优化		错误率
电路名称	文献[10]	本文算法	文献[10]	本文算法	文献[10]	本文算法
cm163	53.85	68.85	47.37	67.48	21.00	24.82
z4ml	0.00	42.62	0.00	27.72	0.00	24.99
alu2	9.09	57.70	0.00	46.02	24.00	24.43
frg1	2.49	98.32	0.00	95.58	16.00	24.32
alu4	6.01	50.09	0.00	26.91	22.00	24.76
unreg	0.00	34.36	0.00	0.00	0.00	24.99
x2	10.81	72.27	1.72	38.46	12.00	24.25
count	57.85	58.13	79.45	80.62	24.00	24.77
term1	46.73	93.12	27.03	78.72	7.00	19.28

下载: 导出CSV

表 3 本文算法与文献[11]的比较结果

Table 3. The comparison results of the algorithms of this paper and Ref.[11]

电路名称	面积优化/%		耗时/s
电路名称	文献[11]	本文算法	文献[11]	本文算法
arbiter	90.15	90.79	9015.06	8593.68
cavlc	5.70	7.47	375.57	67.05
ctrl	3.80	4.90	2.24	3.67
dec	0.62	0.62	8.45	10.06
i2c	31.59	37.95	189.50	176.49
int2float	16.30	23.48	10.86	51.71
mem_ctrl		62.66	>86400.00	2278.56
priority	96.92	98.27	14.95	36.89
router	100.00	98.73	2.00	0.18
voter	5.72	0.09	13504.23	177.04

下载: 导出CSV

参考文献(17)

[1]	WALDROP M M. The chips are down for Moore’s law[J]. Nature, 2016, 530(7589): 144-147. doi: 10.1038/530144a
[2]	HAN J, ORSHANSKY M. Approximate computing: An emerging paradigm for energy-efficient design[C]//Proceedings of the 18th IEEE European Test Symposium. Piscataway: IEEE Press, 2013: 1-6.
[3]	SCARABOTTOLO I, ANSALONI G, CONSTANTINIDES G A, et al. A formal framework for maximum error estimation in approximate logic synthesis[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41(4): 840-853. doi: 10.1109/TCAD.2021.3075651
[4]	SCARABOTTOLO I, ANSALONI G, CONSTANTINIDES G A, et al. Approximate logic synthesis: A survey[J]. Proceedings of the IEEE, 2020, 108(12): 2195-2213. doi: 10.1109/JPROC.2020.3014430
[5]	PASANDI G, NAZARIAN S, PEDRAM M. Approximate logic synthesis: A reinforcement learning-based technology mapping approach[C]//Proceedings of the 20th International Symposium on Quality Electronic Design. Piscataway: IEEE Press, 2019: 26-33.
[6]	ZHOU Z Z, YAO Y, HUANG S Y, et al. DALS: Delay-driven approximate logic synthesis[C]//Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. Piscataway: IEEE Press, 2018: 1-7.
[7]	VENKATARAMANI S, ROY K, RAGHUNATHAN A. Substitute-and-simplify: A unified design paradigm for approximate and quality configurable circuits[C]//Proceedings of the Design, Automation & Test in Europe Conference & Exhibition. Piscataway: IEEE Press, 2013: 1367-1372.
[8]	SU S B, WU Y, QIAN W K. Efficient batch statistical error estimation for iterative multi-level approximate logic synthesis[C]//Proceedings of the 55th ACM/ESDA/IEEE Design Automation Conference. Piscataway: IEEE Press, 2018: 1-6.
[9]	PASANDI G, PETERSON M, HERRERA M, et al. Deep-PowerX: A deep learning-based framework for low-power approximate logic synthesis[C]//Proceedings of the ACM/IEEE International Symposium on Low Power Electronics and Design. New York: ACM, 2020: 73-78.
[10]	CHANDRASEKHARAN A, SOEKEN M, GROßE D, et al. Approximation-aware rewriting of AIGs for error tolerant applications[C]//Proceedings of the 35th International Conference on Computer-Aided Design. New York: ACM, 2016: 1-8.
[11]	MENG C, QIAN W K, MISHCHENKO A. ALSRAC: Approximate logic synthesis by resubstitution with approximate care set[C]//Proceedings of the 57th ACM/IEEE Design Automation Conference. Piscataway: IEEE Press, 2020: 1-6.
[12]	WU Y, QIAN W K. ALFANS: Multilevel approximate logic synthesis framework by approximate node simplification[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(7): 1470-1483. doi: 10.1109/TCAD.2019.2915328
[13]	SU S B, MENG C, YANG F, et al. VECBEE: A versatile efficiency-accuracy configurable batch error estimation method for greedy approximate logic synthesis[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41(11): 5085-5099.
[14]	BRAND D. Verification of large synthesized designs[C]//Proceedings of the International Conference on Computer Aided Design. Piscataway: IEEE Press, 1993: 534-537.
[15]	BRYANT. Graph-based algorithms for Boolean function manipulation[J]. IEEE Transactions on Computers, 1986, C-35(8): 677-691. doi: 10.1109/TC.1986.1676819
[16]	MISHCHENKO A, CHATTERJEE S, BRAYTON R. DAG-aware AIG rewriting: A fresh look at combinational logic synthesis[C]//Proceedings of the 43rd ACM/IEEE Design Automation Conference. Piscataway: IEEE Press, 2006: 532-535.
[17]	BRAYTON R, MISHCHENKO A. ABC: An academic industrial-strength verification tool[C]//International Conference on Computer Aided Verification. Berlin: Springer, 2010: 24-40.