Approximate computing

Approximate computing  is a computation which returns a possibly inaccurate result rather than a guaranteed accurate result, for a situation where an approximate result is sufficient for a purpose. [1] [2]  One example of such situation is for a search engine where no exact answer may exist for a certain search query and hence, many answers may be acceptable. Similarly, occasional dropping of some frames in a video application can go undetected due to perceptual limitations of humans. Approximate computing is based on the observation that in many scenarios, although performing exact computation requires large amount of resources, allowing bounded approximationcan provide disproportionate gains in performance and energy, while still achieving acceptable result accuracy. [ clarification needed ]  For example, in k-means clustering algorithm, allowing only 5% loss in classification accuracy can provide 50 times energy saving compared to the fully accurate classification. [1]

The key requirement in approximate computing is that approximation can be introduced only in non-critical data, since approximating critical data (e.g., control operations) can lead to disastrous consequences, such as program crash or erroneous output.


Several strategies can be used for performing approximate computing.

Approximate circuits
Approximate adders ,  [3]  [4]  multipliers and other logical circuits can reduce hardware overhead.  [5]  [6]  [7]  For example, an approximate multi-bit adder can ignore the carry chain and thus, allow all its sub-adders to perform additional operation in parallel.
Approximate storage
Instead of storing data values, exactly, they can be stored, eg, by truncating the lower-bit in floating point data. Another method is accept less reliable memory. For this, in DRAM  [8]  and eDRAM , refresh rate can be lowered and in SRAM , supply voltage can be lowered. In general, any error detection and correction mechanisms should be disabled.
Software-level approximation
There are several ways to approximate at software level. Memoization can be applied. Some iterations of loops can be skipped (termed as loop perforation ) to accomplish achieve a faster result. Some tasks may also be skipped, for example when a run-time condition suggests that these tasks are not going to be useful ( task skipping ). Monte Carlo algorithms and Randomized algorithms trade correctness for execution time guarantees  [9]  . The computation can be reformulated according to paradigms that can easily be accelerated to specialized hardware, eg neural processing unit.  [10]

Approximate system

In an approximate system  [11]  , different subsystems of the system such as the processor, memory, sensor, and communication modules are synergistically approximated to obtain a much better system-level QE tradeoff curve compared to individual approximations to each of the subsystems.

Application areas

Approximate computing has been used in a variety of fields where the applications are error-tolerant, such as multimedia processing, machine learning , signal processing , scientific computing , etc. Google is using this approach in their Tensor Processing Units (TPU, a custom ASIC).

Derived paradigms

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 with expertise in the field of computing and not having enough expertise on the application domain (and vice versa). In order to solve this problem, programming paradigms  [12]  [13]  have been proposed. They all-have in common the clear role separation entre implementation schedule and implementation domain expert . These approaches allow the spread of the most common optimizations and approximate computing techniques.

See also

  • Artificial neural network


  1. ^ Jump up to: b   Mittal, Sparsh (May 2016). “A Survey of Techniques for Approximate Computing”.  ACM Comput. Surv  . ACM.  48  (4): 62: 1-62: 33. doi : 10.1145 / 2893356 .
  2. Jump up^  A. Sampson, et al. “EnerJ: Approximate data types for safe and general low-power computation”, In ACM SIGPLAN Notices, vol. 46, no. 6, 2011.
  3. Jump up^  J. Echavarria, et al. “FAU: Fast and Error-Optimized Approximate Adder Units on LUT-Based FPGAs”, FPT, 2016.
  4. Jump up^  J. Miao, et al. “Modeling and synthesis of quality-energy optimal adders”, ICCAD, 2012
  5. Jump up^  S. Venkataramani, et al. “SALSA: systematic logic synthesis of approximate circuits”, DAC, 2012.
  6. Jump up^  J. Miao, et al. “Approximate logic synthesis under general error magnitude and frequency constraints”, ICCAD, 2013
  7. Jump up^  R. Hegde et al. “Energy-efficient signal processing via algorithmic noise-tolerance”, ISLPED, 1999.
  8. Jump up^   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 .
  9. Jump up^  C.Alippi Intelligence for Embedded Systems: a Methodological approach, Springer, 2014, pp. 283
  10. Jump up^  H. Esmaeilzadeh, et al. “Neural acceleration for general-purpose approximate programs”, MICRO, 2012
  11. Jump up^   Raha, Arnab; Raghunathan, Vijay (2017). “Towards Full-System Energy-Accuracy Tradeoffs: A Case Study of An Approximate Smart Camera System” .  Proceedings of the 54th Annual Design Automation Conference 2017  . DAC ’17. New York, NY, USA: ACM: 74: 1-74: 6. doi :10.1145 / 3061639.3062333 . ISBN  9781450349277 .
  12. Jump up^   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: 456-471.
  13. Jump up^   Silvano, Cristina; Agosta, Giovanni; Cherubin, Stefano; Gadioli, Davide; Palermo, Gianluca; Bartolini, Andrea; Benini, Luca; Martinovič, Jan; Palkovič, Martin; Slaninová, Kateřina; Bispo, João; Cardoso, João MP; Rui, Abreu; Pinto, Pedro; Cavazzoni, Carlo; Sanna, Nico; Beccari, Andrea R .; Cmar, Radim; Rohou, Erven (2016). “The ANTAREX approach to autotuning and adaptivity for energy efficient HPC systems”.  Proceedings of the ACM International Conference on Computing Frontiers  . ACM: 288-293.

Leave a Reply

Your email address will not be published. Required fields are marked *

Copyright 2018
Shale theme by Siteturner