臺灣博碩士論文加值系統

近似計算是一種針對可容忍錯誤之應用的新興設計技術，它可以透過換取電路的正確性來改善電路的面積、延遲或功耗。我們於此論文提出一種基於基因演算法的近似邏輯合成方法，該方法在保證錯誤率的情況下顯著地減少了電路的面積及深度。我們在IWLS2005和MCNC的電路上進行實驗，實驗結果顯示在5%的錯誤率限制下，我們提出的方法能夠減少多達80%的面積和50%的深度。與最新的方法相比，我們提出的方法在相同的5%錯誤率限制下平均能夠多減少11%的面積和188%的深度。

Approximate computing is an emerging design technique for error-tolerant applications, which may improve circuit area, delay, or power consumption by trading off a circuit's correctness. In this paper, we propose a novel approximate logic synthesis approach based on genetic algorithm, and the approach significantly reduces circuit sizes and depths with an error rate guarantee. We conduct experiments on a set of IWLS 2005 and MCNC benchmarks. The experimental results demonstrate that the area and depth can be reduced by up to 80% and 50% under a 5% error rate constraint, respectively. As compared with the state-of-the-art method, our approach can achieve an average of 11% more area savings and 188% more depth reduction under the same 5% error rate constraint.

中文摘要
Abstract
Acknowledgement
Contents
List of Tables
List of Figures
1 Introduction 1
2 Preliminaries 3
2.1 Error Metrics 3
2.2 And-Inverter-Graphs 3
2.3 Genetic Algorithm 4
3 Proposed Approach 5
3.1 Node to Constant 5
3.2 Circuit Partitioning 6
3.3 Genetic Algorithm Design 7
3.4 Subcircuit Selection and Combination 15
3.5 Overall Flow 17
4 Experimental Results 19
5 Conclusion 25

[1] M. Barbareschi et al., “A Catalog-based AIG-Rewriting Approach to the Design of Approximate Components,” IEEE Trans. Emerg. Topics Comput., 2022.
[2] J. Echavarria et al., “Probabilistic Error Propagation through Approximated Boolean Networks,” Proc. DAC, 2020, pp. 1-6.
[3] C. M. Fiduccia et al., “A Linear-Time Heuristic for Improving Network Parti- tions,” Proc. DAC, 1982, pp. 175-181.
[4] J. Han et al., “Approximate Computing: An Emerging Paradigm for Energy- Efficient Design,” Proc. ETS, 2013, pp. 1-6.
[5] J. H. Holland, “Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence,” MIT Press, 1992.
[6] S. Karakatic et al., “Optimization of Combinational Logic Circuits with Genetic Programming,” Elektronika ir Elektrotechnika, 2013.
[7] B. W. Kernighan et al., “An Efficient Heuristic Procedure for Partitioning Graphs,” The Bell System Technical Journal, 1970, pp. 291-307.
[8] Y. Kim et al., “An Energy Efficient Approximate Adder with Carry Skip for Error Resilient Neuromorphic VLSI Systems,” Proc. ICCAD, 2013, pp. 130-137.
[9] P. Kulkarni et al., “Trading Accuracy for Power with an Underdesigned Multi- plier Architecture,” Proc. VLSID, 2011, pp. 346-351.
[10] K. Y. Kyaw et al., “Low-Power High-Speed Multiplier for Error-Tolerant Ap- plication,” Proc. EDSSC, 2010, pp. 1-4.
[11] Y.-A Lai et al., “Efficient Synthesis of Approximate Threshold Logic Circuits with an Error Rate Guarantee,” Proc. DATE, 2018, pp. 773-778.
[12] J. Liang et al., “New Metrics for the Reliability of Approximate and Proba- bilistic Adders,” IEEE Trans. Comput., 2013, pp. 1760-1771.
[13] C. Liu et al., “A Low-Power, High-Performance Approximate Multiplier with Configurable Partial Error Recovery,” Proc. DATE, 2014, pp. 1-4.
[14] C. Meng et al., “ALSRAC: Approximate Logic Synthesis by Resubstitution with Approximate Care Set,” Proc. DAC, 2020, pp. 1-6.
[15] L. Hellerman, “A Catalog of Three-Variable Or-Invert and And-Invert Logical Circuits,” IEEE Trans. Electron. Comput., 1963, pp. 198-223.
[16] I. Scarabottolo et al., “Partition and Propagate: an Error Derivation Algorithm for the Design of Approximate Circuits,” Proc. DAC, 2019, pp. 1-6.
[17] S. Su et al., “Efficient Batch Statistical Error Estimation for Iterative Multi- level Approximate Logic Synthesis,” Proc. DAC, 2018, pp. 1-6.
[18] K. S. Tam et al., “An Efficient Approximate Node Merging with an Error Rate Guarantee,” Proc. ASP-DAC, 2021, pp. 266-271.
[19] Z. Vasicek et al., “Evolutionary Approach to Approximate Digital Circuits De- sign,” IEEE Trans. Evol. Comput., 2015, pp. 432-444.
[20] S. Venkataramani et al., “Substitute-and-Simplify: A Unified Design Paradigm for Approximate and Quality Configurable Circuits,” Proc. DATE, 2013, pp. 1367-1372.
[21] A. Wendler et al., “A fast BDD Minimization Framework for Approximate Computing,” Proc. DATE, 2020, pp. 1372-1377.
[22] S. Yang, “Logic Synthesis and Optimization Benchmarks,” Microelectronics Center of North Carolina, Tech. Rep., 1991.
[23] N. Zhu et al., “An Enhanced Low-Power High-Speed Adder for Error-Tolerant Application,” Proc. ISIC, 2009, pp. 69-72.
[24] Berkeley Logic Synthesis and Verification Group. ABC: A Sys- tem for Sequential Synthesis and Verification [Online]. Available: http://www.eecs.berkeley.edu/ alanmi/abc
[25] http://iwls.org/iwls2005/benchmarks.html