Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Approximate computing
open-in-new
<h2 id="strategies">Strategies</h2> <p>Several strategies can be used for performing approximate computing. </p> Approximate circuits Approximate arithmetic circuits:<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> <a href="/facts/Adder_(electronics)/Bc81gxBD">adders</a>,<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a><a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> <a href="/facts/Binary_multiplier/GfkwufDb">multipliers</a><a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> and other <a href="/facts/Logical_circuit/RHLulvKI">logical circuits</a> can reduce hardware overhead.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a><a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a><a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> For example, an approximate multi-bit adder can ignore the <a href="/facts/Carry_chain/Bc81gxBD">carry chain</a> and thus, allow all its sub-adders to perform addition operation in parallel.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a><a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> Approximate storage and memory Instead of <a href="/facts/Computer_data_storage/wPHKFpdx">storing data</a> values exactly, they can be stored approximately, e.g., by <a href="/facts/Data_truncation/JN6c65JK">truncating</a> the lower-bits in <a href="/facts/Floating_point/eIckahxe">floating point</a> data. Another method is to accept less reliable memory. For this, in <a href="/facts/DRAM/koI9FGo5">DRAM</a><a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> and <a href="/facts/EDRAM/rf8jR3Ds">eDRAM</a>, <a href="/facts/Refresh_rate/7mGJs7Dz">refresh rate</a> assignments can be lowered or controlled.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> In <a href="/facts/Static_random-access_memory/Pmyo4V5e">SRAM</a>, supply voltage can be lowered<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> or controlled.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> Approximate storage can be applied to reduce <a href="/facts/Magnetoresistive_random-access_memory/WsgKzopf">MRAM</a>'s high write energy consumption.<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> In general, any <a href="/facts/Error_detection_and_correction/o2rH8e3n">error detection and correction</a> mechanisms should be disabled. Software-level approximation There are several ways to approximate at software level. <a href="/facts/Memoization/u08VhUKm">Memoization</a> or fuzzy memoization (the use of a <a href="/facts/Vector_database/aKotamhB">vector database</a> for approximate retrieval from a cache, <i>i.e.</i> fuzzy caching) can be applied. Some <a href="/facts/Iteration/AMc1p7BL">iterations</a> of <a href="/facts/Loop_(computing)/2XTDfErC">loops</a> can be skipped (termed as <a href="/facts/Loop_perforation/L4btGaIS">loop perforation</a>) to achieve a result faster. Some tasks can also be skipped, for example when a run-time condition suggests that those tasks are not going to be useful (<a href="/facts/Task_skipping/opoqAxa5">task skipping</a>). <a href="/facts/Monte_Carlo_algorithm/6Sqjsa6s">Monte Carlo algorithms</a> and <a href="/facts/Randomized_algorithm/Fngl1zgk">Randomized algorithms</a> trade correctness for execution time guarantees.<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> The computation can be reformulated according to paradigms that allow easily the acceleration on specialized hardware, e.g. a neural processing unit.<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a> Approximate system In an approximate system,<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a> <a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a> different subsystems of the system such as the processor, memory, sensor, and communication modules are synergistically approximated to obtain a much better system-level Q-E trade-off curve compared to individual approximations to each of the subsystems. <h2 id="application-areas">Application areas</h2> <p>Approximate computing has been used in a variety of domains where the applications are error-tolerant, such as <a href="/facts/Multimedia/PtJteq27">multimedia</a> processing, <a href="/facts/Machine_learning/e0w0XJTu">machine learning</a>, <a href="/facts/Signal_processing/Npaja6zb">signal processing</a>, <a href="/facts/Computational_science/PnVD19hw">scientific computing</a>. Therefore, approximate computing is mostly driven by applications that are related to human perception/cognition and have inherent error resilience. Many of these applications are based on statistical or probabilistic computation, such as different approximations can be made to better suit the desired objectives.<a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a> One notable application in <a href="/facts/Machine_learning/e0w0XJTu">machine learning</a> is that Google is using this approach in their <a href="/facts/Tensor_processing_unit/aVlg0LFF">Tensor processing units</a> (TPU, a custom <a href="/facts/Application-specific_integrated_circuit/YGUXpX50">ASIC</a>).<a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a> </p> <h2 id="derived-paradigms">Derived paradigms</h2> <p>The main issue in approximate computing is the identification of the section of the application that can be approximated. In the case of large scale applications, it is very common to find people holding the expertise on approximate computing techniques not having enough expertise on the application domain (and vice versa). In order to solve this problem, <a href="/facts/Programming_paradigm/7LwgRpB3">programming paradigms</a><a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a> have been proposed. They all have in common the clear role separation between application <a href="/facts/Programmer/WGTS1Jv9">programmer</a> and application <a href="/facts/Domain_expert/3kx3sVID">domain expert</a>. These approaches allow the spread of the most common <a href="/facts/Program_optimization/nXz6RpRM">optimizations</a> and approximate computing techniques. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Artificial_neural_network/6V1jMlkx">Artificial neural network</a></li> <li><a href="/facts/Metaheuristic/ECF71Rez">Metaheuristic</a></li> <li><a href="/facts/PCMOS/yqSxJrvW">PCMOS</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>J. Han and M. Orshansky, "Approximate computing: An emerging paradigm for energy-efficient design", in the 18th IEEE European Test Symposium, pp. 1-6, 2013. <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.701.4955&rep=rep1&type=pdf" target="_blank">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.701.4955&rep=rep1&type=pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>A. Sampson, et al. "EnerJ: Approximate data types for safe and general low-power computation", In ACM SIGPLAN Notices, vol. 46, no. 6, 2011. <a href="http://dl.acm.org/citation.cfm?id=1993518" target="_blank">http://dl.acm.org/citation.cfm?id=1993518</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Jiang et al., "Approximate Arithmetic Circuits: A Survey, Characterization, and Recent Applications", the Proceedings of the IEEE, Vol. 108, No. 12, pp. 2108 - 2135, 2020. <a href="http://www.ece.ualberta.ca/~jhan8/publications/survey.pdf" target="_blank">http://www.ece.ualberta.ca/~jhan8/publications/survey.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>J. Echavarria, et al. "FAU: Fast and Error-Optimized Approximate Adder Units on LUT-Based FPGAs", FPT, 2016. <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>J. Miao, et al. "Modeling and synthesis of quality-energy optimal approximate adders", ICCAD, 2012 <a href="https://repositories.lib.utexas.edu/bitstream/handle/2152/19706/miao_thesis_201291.pdf?sequence=1" target="_blank">https://repositories.lib.utexas.edu/bitstream/handle/2152/19706/miao_thesis_201291.pdf?sequence=1</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Rehman, Semeen; El-Harouni, Walaa; Shafique, Muhammad; Kumar, Akash; Henkel, Jörg (2016-11-07). Architectural-space exploration of approximate multipliers. ACM. p. 80. doi:10.1145/2966986.2967005. ISBN 9781450344661. S2CID 5326133. <a href="9781450344661" target="_blank">9781450344661</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>S. Venkataramani, et al. "SALSA: systematic logic synthesis of approximate circuits", DAC, 2012. <a href="http://algos.inesc-id.pt/projectos/approx/FCT/Ref-15.pdf" target="_blank">http://algos.inesc-id.pt/projectos/approx/FCT/Ref-15.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>J. Miao, et al. "Approximate logic synthesis under general error magnitude and frequency constraints", ICCAD, 2013 <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.453.7870&rep=rep1&type=pdf" target="_blank">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.453.7870&rep=rep1&type=pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>R. Hegde et al. "Energy-efficient signal processing via algorithmic noise-tolerance", ISLPED, 1999. <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.8929&rep=rep1&type=pdf" target="_blank">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.8929&rep=rep1&type=pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Camus, Vincent; Mei, Linyan; Enz, Christian; Verhelst, Marian (December 2019). "Review and Benchmarking of Precision-Scalable Multiply-Accumulate Unit Architectures for Embedded Neural-Network Processing". IEEE Journal on Emerging and Selected Topics in Circuits and Systems. 9 (4): 697–711. Bibcode:2019IJEST...9..697C. doi:10.1109/JETCAS.2019.2950386. ISSN 2156-3357. The implementation chosen in this study assumes a rightshifting sequential multiplier as it requires a smaller firststage adder than a left-shifting design, preventing long carry propagation and sign-bit extension. <a href="https://doi.org/10.1109%2FJETCAS.2019.2950386" target="_blank">https://doi.org/10.1109%2FJETCAS.2019.2950386</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Nagornov, Nikolay N.; Lyakhov, Pavel A.; Bergerman, Maxim V.; Kalita, Diana I. (2024). "Modern Trends in Improving the Technical Characteristics of Devices and Systems for Digital Image Processing". IEEE Access. 12: 44659–44681. Bibcode:2024IEEEA..1244659N. doi:10.1109/ACCESS.2024.3381493. ISSN 2169-3536. Addition and accumulation of high order bits are not performed until the partial product reduction for the next multiplication in the proposed architecture. <a href="https://doi.org/10.1109%2FACCESS.2024.3381493" target="_blank">https://doi.org/10.1109%2FACCESS.2024.3381493</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Raha, A.; Sutar, S.; Jayakumar, H.; Raghunathan, V. (July 2017). "Quality Configurable Approximate DRAM". IEEE Transactions on Computers. 66 (7): 1172–1187. doi:10.1109/TC.2016.2640296. ISSN 0018-9340. <a href="https://doi.org/10.1109%2FTC.2016.2640296" target="_blank">https://doi.org/10.1109%2FTC.2016.2640296</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Kim, Yongjune; Choi, Won Ho; Guyot, Cyril; Cassuto, Yuval (December 2019). "On the Optimal Refresh Power Allocation for Energy-Efficient Memories". 2019 IEEE Global Communications Conference (GLOBECOM). Waikoloa, HI, USA: IEEE. pp. 1–6. arXiv:1907.01112. doi:10.1109/GLOBECOM38437.2019.9013465. ISBN 978-1-7281-0962-6. S2CID 195776538. <a href="978-1-7281-0962-6" target="_blank">978-1-7281-0962-6</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Frustaci, Fabio; Blaauw, David; Sylvester, Dennis; Alioto, Massimo (June 2016). "Approximate SRAMs With Dynamic Energy-Quality Management". IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 24 (6): 2128–2141. doi:10.1109/TVLSI.2015.2503733. ISSN 1063-8210. S2CID 8051173. <a href="/wiki/David_Blaauw" target="_blank">/wiki/David_Blaauw</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Kim, Yongjune; Kang, Mingu; Varshney, Lav R.; Shanbhag, Naresh R. (2018). "Generalized Water-filling for Source-aware Energy-efficient SRAMs". IEEE Transactions on Communications. 66 (10): 4826–4841. arXiv:1710.07153. doi:10.1109/TCOMM.2018.2841406. ISSN 0090-6778. S2CID 24512949. <a href="https://ieeexplore.ieee.org/document/8368137" target="_blank">https://ieeexplore.ieee.org/document/8368137</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Kim, Yongjune; Jeon, Yoocharn; Choi, Hyeokjin; Guyot, Cyril; Cassuto, Yuval (2022). "Optimizing Write Fidelity of MRAMs by Alternating Water-filling Algorithm". IEEE Transactions on Communications. 70 (9): 5825–5836. doi:10.1109/TCOMM.2022.3190868. ISSN 0090-6778. S2CID 250565077. <a href="https://ieeexplore.ieee.org/document/9829735" target="_blank">https://ieeexplore.ieee.org/document/9829735</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>C.Alippi, Intelligence for Embedded Systems: a Methodological approach, Springer, 2014, pp. 283 <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>Esmaeilzadeh, Hadi; Sampson, Adrian; Ceze, Luis; Burger, Doug (2012). Neural acceleration for general-purpose approximate programs. 45th Annual IEEE/ACM International Symposium on Microarchitecture. Vancouver, BC: IEEE. pp. 449–460. doi:10.1109/MICRO.2012.48. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>Raha, Arnab; Raghunathan, Vijay (2017). "Towards Full-System Energy-Accuracy Tradeoffs". Proceedings of the 54th Annual Design Automation Conference 2017. DAC '17. New York, NY, USA: ACM. pp. 74:1–74:6. doi:10.1145/3061639.3062333. ISBN 9781450349277. S2CID 2503638. <a href="9781450349277" target="_blank">9781450349277</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>Ghosh, Soumendu Kumar; Raha, Arnab; Raghunathan, Vijay (2023-07-24). "Energy-Efficient Approximate Edge Inference Systems". ACM Transactions on Embedded Computing Systems. 22 (4): 77:1–77:50. doi:10.1145/3589766. ISSN 1539-9087. <a href="https://dl.acm.org/doi/10.1145/3589766" target="_blank">https://dl.acm.org/doi/10.1145/3589766</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>Liu, Weiqiang; Lombardi, Fabrizio; Schulte, Michael (Dec 2020). "Approximate Computing: From Circuits to Applications". Proceedings of the IEEE. 108 (12): 2103. doi:10.1109/JPROC.2020.3033361. <a href="https://doi.org/10.1109%2FJPROC.2020.3033361" target="_blank">https://doi.org/10.1109%2FJPROC.2020.3033361</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>Liu, Weiqiang; Lombardi, Fabrizio; Schulte, Michael (Dec 2020). "Approximate Computing: From Circuits to Applications". Proceedings of the IEEE. 108 (12): 2104. doi:10.1109/JPROC.2020.3033361. <a href="https://doi.org/10.1109%2FJPROC.2020.3033361" target="_blank">https://doi.org/10.1109%2FJPROC.2020.3033361</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>Nguyen, Donald; Lenharth, Andrew; Pingali, Keshav (2013). "A lightweight infrastructure for graph analytics". Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles. ACM. pp. 456–471. doi:10.1145/2517349.2522739. ISBN 9781450323888. <a href="9781450323888" target="_blank">9781450323888</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> </ol>