-
摘要:
考虑到在相同错误率约束下，同一逻辑电路的二级和多级近似优化效果并不一样，且逻辑电路的二级表示与多级表示之间可以等效转化，提出一种基于错误率分配的逻辑电路近似面积优化算法。该算法包括错误率分配算法，二级错误率快速估算算法及二级/多级近似优化算法。所提算法使用C语言和面向时序逻辑综合与形式验证系统(ABC)工具内置命令编程实现，使用北卡罗莱纳微电子中心(MCNC)基准电路进行测试。实验结果表明，在错误率约束为5%情况下，所提算法在面积和延时优化上分别为42.36%和25.15%；与单纯使用多级近似优化方法相比，面积和延时的优化分别进一步提升了5.05%和9.36%。
Abstract:A multi-level area optimization algorithm for logic circuits based on error rate allocation is proposed, taking into account that the approximate optimization effects of a logic function under the same error rate constraint differ when the function is expressed in two-level or multi-level forms and that there is an equivalent conversion between two-level and multi-level forms. This algorithm consists of a two-level error rate estimation technique, an error rate coefficient search method for error rate division, and a two-level/multi-level approximate optimization method. The proposed algorithm is implemented using C, the commands of a system for sequential logic synthesis and formal verification (ABC) tools and tested with Microelectronics Center of North Carolina (MCNC) benchmarks. The experimental results show that, compared to the ABC tools, with the 5% error rate, the proposed algorithm achieves 42.36% and 25.15% in area and delay optimization, respectively. Compared to those approximate methods that only use the multi-level approximation method, further improvement in area and delay can be obtained by 5.05% and 9.36%, respectively.
-
图 5 1位全加电路经二级/多级近似优化后的AIG表示
Figure 5. AIG of 1-bit full adder circuit after optimized using two-level/multi-level approximate computing
表 1 本文使用的MCNC测试电路
Table 1. The parameters of MCNC benchmarks used in this paper
电路名称 I/O 初始面积 初始延迟/ns alu4 14/8 1158 49.81 table3 14/14 2836 29.9 b12 15/9 98 8.5 table5 17/9 2563 31.6 t481 16/1 1400 24.9 clip 9/5 193 14 sqrt8 8/4 101 11.9 rd84 8/4 301 18.4 apex4 9/19 4685 27.4 misex1 8/7 103 9.2 5xp1 7/10 160 12.1 inc 7/9 184 10.3 
下载: 导出CSV
表 2 本文算法与文献[11]算法和文献[12]算法的比较结果
Table 2. Comparison results of the proposed algorithm with references [11] and [12] algorithm
电路名称 面积优化/% 延迟优化/% 文献[11] 文献[12] 本文算法 文献[11] 文献[12] 本文算法 alu4 11.20 24.84 22.71 7.25 19.03 46.80 table3 90.63 90.09 91.27 48.61 57.41 54.07 b12 24.49 21.77 26.53 16.47 7.84 16.47 table5 94.49 92.91 94.98 63.83 55.49 62.45 t481 87.64 93.21 96.93 36.55 40.03 66.27 clip 28.67 0 28.15 0 0 4.29 sqrt8 42.57 37.29 43.56 13.45 0 7.56 rd84 19.93 48.28 36.10 0 23.55 20.65 apex4 4.55 14.88 20.65 0 11.19 11.20 misex1 6.80 3.56 10.68 0 3.26 8.70 5xp1 16.67 0.42 16.67 3.31 0 3.31 inc 20.11 2.17 20.11 0 0 0 注：各列平均值为37.31%，35.79%，42.36%，15.79%，18.15%，25.15%。
下载: 导出CSV
表 3 本文算法与文献[11]算法和文献[12]算法的运行时间
Table 3. Runtime of the proposed algorithm with references [11] and [12] algorithm
电路名称 时间/s 文献[11]算法 文献[12]算法 本文算法 alu4 78.64 318.06 1688.56 table3 706.42 2224.44 2284.05 b12 1.46 0.53 7.76 table5 542.00 632.45 1285.45 t481 209.88 246.85 245.48 clip 8.41 0.33 43.81 sqrt8 0.81 0.53 6.19 rd84 14.37 4.83 34.12 apex4 289.43 5573.21 926.52 misex1 0.98 0.68 4.64 5xp1 2.62 2.45 16.74 inc 2.31 1.09 13.06 注：各列平均值为154.78，750.45，546.36 s。
下载: 导出CSV
-
[1] XU Q, MYTKOWICZ T, KIM N S. Approximate computing: a survey[J]. IEEE Design & Test, 2016, 33(1): 8-22. [2] SEKANINA L. Introduction to approximate computing: embedded tutorial[C]//Proceedings of the IEEE 19th International Symposium on Design and Diagnostics of Electronic Circuits & Systems. Piscataway: IEEE Press, 2016: 1-6. [3] WU Y, CHEN C T, XIAO W H, et al. A survey on approximate multiplier designs for energy efficiency: from algorithms to circuits[J]. ACM Transactions on Design Automation of Electronic Systems, 2024, 29(1): 1-37. [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. [5] SEO H, KIM Y. A low latency approximate adder design based on dual sub-adders with error recovery[J]. IEEE Transactions on Emerging Topics in Computing, 2023, 11(3): 811-816. [6] MANNEPALLI Y, KOREDE V B, RAO M. Novel approximate multiplier designs for edge detection application[C]//Proceedings of the Great Lakes Symposium on VLSI. New York: ACM, 2021: 371-377. [7] NGUYEN D T, KIM H, LEE H J, et al. An approximate memory architecture for a reduction of refresh power consumption in deep learning applications[C]//Proceedings of the IEEE International Symposium on Circuits and Systems. Piscataway: IEEE Press, 2018: 1-5. [8] SEN S, RAGHUNATHAN A. Approximate computing for long short term memory (LSTM) neural networks[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(11): 2266-2276. [9] SHIN D, GUPTA S K. Approximate logic synthesis for error tolerant applications[C]//Proceedings of the Design, Automation & Test in Europe Conference & Exhibition (DATE 2010). Piscataway: IEEE Press, 2010: 957-960. [10] FUJITA M. An approach to approximate computing: logic transformations for one-minterm changes in specification[C]//Proceedings of the IEEE International High Level Design Validation and Test Workshop. Piscataway: IEEE Press, 2017: 91-94. [11] 赵维凯, 王伦耀, 岑旭梦, 等. 基于近似计算技术的多级逻辑电路面积优化[J]. 北京航空航天大学学报, 2024, 50(9): 2893-2901.ZHAO W K, WANG L Y, CEN X M, et al. Area optimization of multilevel logic circuits using approximate computing[J]. Journal of Beijing University of Aeronautics and Astronautics, 2024, 50(9): 2893-2901(in Chinese). [12] 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. [13] 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. [14] MENG C, ZHOU Z Z, YAO Y, et al. HEDALS: highly efficient delay-driven approximate logic synthesis[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2023, 42(11): 3491-3504. [15] 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. [16] SU S B, ZOU C, KONG W J, et al. A novel heuristic search method for two-level approximate logic synthesis[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(3): 654-669. [17] 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. [18] AMMES G, NETO W L, BUTZEN P, et al. A two-level approximate logic synthesis combining cube insertion and removal[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41(11): 5126-5130. [19] 王伦耀, 夏银水, 储著飞. 基于近似计算技术的FPRM电路面积优化[J]. 电子学报, 2019, 47(9): 1868-1874.WANG L Y, XIA Y S, CHU Z F. Area optimization of FPRM circuits using approximate computing[J]. Acta Electronica Sinica, 2019, 47(9): 1868-1874(in Chinese). [20] BRAYTON R K, HACHTEL G D, MCMULLEN C T, et al. Logic minimization algorithms for VLSI synthesis[M]. Berlin: Springer, 1984. [21] YANG S. Logic synthesis and optimization benchmarks user guide: version 3.0[M]. North Carolina: Microelectronics Center of North Carolina, 1991. -
下载:
点击查看大图
计量
- 文章访问数: 253
- HTML全文浏览量: 190
- PDF下载量: 2
- 被引次数: 0
