A Survey on Approximate Multiplier Designs for Energy Efficiency: From Algorithms to Circuits

Ying Wu, Chuangtao Chen, Weihua Xiao, Xuan Wang, Chenyi Wen, Jie Han, Xunzhao Yin, Weikang Qian, Cheng ZhuoACM Trans. Design Autom. Electr. Syst 2024 · DOI

TL;DR

This paper provides a comprehensive survey of approximate multiplier designs, bridging the gap between algorithmic approximations and circuit-level implementations. It offers a structured overview of various techniques, their trade-offs, and their impact on energy efficiency, crucial for resource-constrained edge devices.

What Problem Does This Paper Address?

The ever-increasing demand for energy efficiency in edge devices, particularly for Internet-of-Things (IoT) applications, presents a significant challenge. Conventional processors often use full precision for computations, leading to wasted energy. However, many applications, like neural networks, can tolerate some level of inaccuracy without compromising their overall performance. This paper addresses the need for energy-efficient computational components, specifically multipliers, by exploring "approximate computing" – a paradigm that trades precision for efficiency. The core problem is how to effectively introduce approximation into multiplier designs across different levels (algorithms, architectures, and circuits) to achieve significant energy savings while maintaining acceptable accuracy for error-tolerant applications.

Methods

The paper systematically reviews and categorizes approximate multiplier designs based on where the approximation is introduced:

  • Algorithm-Level Approximation: This involves modifying the fundamental mathematical approach to multiplication. Techniques discussed include logarithm-based approximation (e.g., Mitchell's multiplier), linearization-based approximation (approximating the non-linear multiplication function with piecewise linear functions), and hybrid approaches that combine accurate and approximate multipliers.
  • Architecture-Level Approximation: This focuses on modifying the structure of the multiplier. Techniques include input truncation (removing less significant bits), altering partial products, and approximating components within the accumulation stage, such as compressors.
  • Circuit-Level Approximation: This delves into modifying the logic gates and expressions. Methods include Boolean rewriting (simplifying logic using Karnaugh maps), gate-level pruning (removing less active gates), evolutionary circuit design (using genetic algorithms to evolve circuits), and voltage over-scaling (reducing supply voltage to induce controlled errors).

The authors also implemented representative designs in Verilog to ensure a fair comparison and released them as an open-source library (AM-Lib).

Datasets

The paper does not introduce new datasets. Instead, it evaluates the performance of approximate multipliers in three representative machine learning applications:

  • MNIST (MLP): A multi-layer perceptron network trained on the MNIST dataset.
  • CIFAR10 (AlexNet): A convolutional neural network (AlexNet) trained on the CIFAR10 dataset.
  • ImageNet (SqueezeNet): A lightweight convolutional neural network (SqueezeNet) trained on the ImageNet dataset.

These applications are chosen because they are multiplication-intensive and inherently error-tolerant.

Key Insights and Ideas

  • No One-Size-Fits-All: The effectiveness of an approximate multiplier is highly dependent on the specific application and the synthesis mode (delay-optimized vs. area-optimized). What works best for one application might not be optimal for another.
  • Top-Down Design is Crucial: Simply optimizing for metrics like Mean Relative Error Distance (MRED) doesn't always translate to good application-level accuracy. A "top-down" approach that links application-level specifications to error metrics is needed.
  • Algorithm-Circuit Co-Optimization: There's a significant opportunity in designing algorithms that are "approximation-friendly" to fully leverage the benefits of approximate multipliers, rather than just fitting approximate multipliers into existing algorithms.
  • Trade-offs are Inherent: All approximate multiplier designs involve trade-offs between accuracy, energy efficiency (power and delay), and area. Understanding these trade-offs is key to selecting the right design.
  • Iterative Schemes Offer Better Accuracy at a Cost: While iterative approximation techniques can improve accuracy, they often come with increased hardware overhead for error compensation.

Key Results

The paper presents extensive experimental results comparing various approximate multipliers against exact designs across fixed-point unsigned, fixed-point signed, and floating-point categories.

  • Energy Efficiency: Many designs achieve significant power reductions, with some exceeding 95% power saving.
  • Accuracy vs. Efficiency Trade-off: Figures 32, 35, and 37 illustrate the trade-off between accuracy loss and PDP (Power-Delay Product) reduction. Designs closer to the lower-right corner of these plots are generally preferred, indicating good energy efficiency with minimal accuracy degradation.
  • Application-Specific Performance:
    • For fixed-point unsigned multipliers in ML applications, OPACT, BAM(8,16), SSM, ALM_SOA, AW, APP2, BAM(4,8), DRUM, LM, and mul16u_1UG showed good energy efficiency with limited accuracy loss on MNIST (MLP).
  • For fixed-point signed multipliers, mul16s_GRU offered the best performance on MNIST (MLP), while R4ABE1 was superior on CIFAR10 (AlexNet) and ImageNet (SqueezeNet).
  • For floating-point multipliers, most designs achieved dramatic power reduction with negligible accuracy losses across all three ML applications, benefiting from the larger dynamic range.

Limitations and Future Work

  • Top-Down Design Methodology: The paper highlights the need for a better link between application-level specifications and the error metrics of approximate multipliers. Developing a general design methodology that supports this top-down flow is crucial.
  • Design Automation Methods: Most existing approximate multipliers are manually designed. There's a significant need for automated methods to explore the vast design space and find optimized solutions.
  • Algorithm-Circuit Co-Optimization: Further research is needed to understand the interplay between algorithms and approximate multiplier circuits. Designing "approximation-friendly" algorithms that can fully exploit the benefits of approximate multipliers is a key future direction.
  • Synthesis Mode Sensitivity: The evaluation showed that approximation techniques can have different sensitivities to synthesis modes (delay-optimized vs. area-optimized), suggesting that this aspect needs careful consideration.

Summary updated

BibTeX
@article{wu2024survey,
  author = {Ying Wu and Chuangtao Chen and Weihua Xiao and Xuan Wang and Chenyi Wen and Jie Han and Xunzhao Yin and Weikang Qian and Cheng Zhuo},
  title = {{A Survey on Approximate Multiplier Designs for Energy Efficiency: From Algorithms to Circuits}},
  journal = {ACM Trans. Design Autom. Electr. Syst},
  year = {2024},
  doi = {10.1145/3610291},
}

Loading related content...

Figure