layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # Approximate Multiplier Design Challenges 🚧 --- ## 1. Introduction: The Need for Approximate Computing 🚀💡 - Approximate computing (AxC) has emerged as a **new paradigm** for high-performance and energy-efficient circuit and system design 🌱⚡. - **Motivation**: Conventional technologies face challenges to improve circuit performance and power efficiency due to limits at the nanometer scale and increasing power density. This results in "**dark silicon**" where parts of the chip must be powered off. .mermaid[ <pre> graph LR A[Performance\nGoals] --> B[Nanometer\nLimits] B --> C[Power\nDensity] C --> D[Dark\nSilicon] D --> E[Approximate\nComputing] style A fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style B fill:#fff9c4,stroke:#f57f17,stroke-width:3px style C fill:#fff9c4,stroke:#f57f17,stroke-width:3px style D fill:#ffcdd2,stroke:#c62828,stroke-width:3px style E fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px </pre> ] --- ## Error-Tolerant Applications 🙏✅ - AxC is driven by challenges from **massive data** and **complex computations** in modern applications like AI 📊🤖. - Many applications like multimedia, recognition, classification, and **machine learning can tolerate some errors** 🙏✅. Humans often have perceptual limitations and tolerate meaning errors in output quality for image, audio, or video processing. .mermaid[ <pre> graph LR A[Approximate\nComputing] --> B[Multimedia] A --> C[Recognition] A --> D[Classification] A --> E[Machine\nLearning] style A fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style B fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style C fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style D fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style E fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px </pre> ] --- ### 2. Approximate Arithmetic Circuits & Multipliers ⚙️🔢 - Approximate arithmetic circuits offer trade-offs between **output accuracy and computation efforts**, yielding superior performance (delay and area) compared to traditional circuits at the cost of computational accuracy. - Approximate adders and multipliers trade **accuracy for hardware efficiency** ⚙️📉. - A multiplier typically involves three stages: .mermaid[ <pre> graph LR A[Partial Product\nGeneration] --> B[Partial Product\nReduction] B --> C[Final\nAddition] style A fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style B fill:#fff9c4,stroke:#f57f17,stroke-width:3px style C fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px </pre> ] - **Evaluation Metrics**: Both error characteristics and circuit measurements must be considered. Key metrics include Error Rate (ER), Error Distance (ED), Relative Error Distance (RED), Mean ED (MED), and **Mean Relative Error Distance (MRED)**. Circuit measurements cover delay, area, and power. --- ### Design Methodologies & Techniques 🛠️ - **Design Methodologies** for Approximate Arithmetic Circuits include: - **Voltage Overscaling (VOS)**: Lowers supply voltage to reduce power, increases critical path delay potentially causing timing errors. Error characteristics are **nondeterministic** and affected by variations. - **Redesigning Logic Circuits**: Modifying or removing elements, simplifying truth tables or Karnaugh maps. Results in circuits with **deterministic error characteristics**. - **Simplification Algorithms**: Converting complex operations (multiplication, division) into simpler ones (addition, subtraction). Can improve performance and energy efficiency, but accuracy tends to be relatively low. - **Hybrid Approaches**: Combining several approximate techniques. .mermaid[ <pre> graph TD A[Approximate Circuit\nDesign Methodologies] --> B[Voltage\nOverscaling] A --> C[Redesigning\nLogic Circuits] A --> D[Simplification\nAlgorithms] A --> E[Hybrid\nApproaches] style A fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style B fill:#ffcdd2,stroke:#c62828,stroke-width:3px style C fill:#fff9c4,stroke:#f57f17,stroke-width:3px style D fill:#fff9c4,stroke:#f57f17,stroke-width:3px style E fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px </pre> ] - **Approximate Multiplier Specific Techniques**: - Approximation in Partial Product (PP) generation or PP tree. - **Approximation including truncation** in the PP tree. Truncation is effective in reducing delay and energy for unsigned designs. - Using approximate adders, counters, or compressors in PP reduction. - Using **Logarithmic Approximation (LMs)**. LMs tend to be hardware-efficient but with rather low accuracy. - Using **Automated Processes** like genetic programming to generate designs. - Finding the **best trade-off** between quality and other design parameters such as power and delay is crucial. Energy (PDP) vs. Accuracy (MRED) plots are used to show trade-offs. --- ### 3. Challenges in Design (1/2) 🏗️🤔 - **Balancing Multiple Design Goals**: Approximate multipliers introduce accuracy as a key design parameter alongside performance, area, and power, making the identification of the most suitable design quite challenging. Achieving good **energy-accuracy tradeoffs** is a significant challenge. - **Selecting Approximation Techniques**: The computation error and energy efficiency largely depend on **how and where the approximation is introduced** into a design. Choosing the most effective techniques (e.g., truncation vs. LMs vs. simplified logic) for a given application is complex. Some methods like Voltage Overscaling introduce **nondeterministic errors**, which are harder to manage. .mermaid[ <pre> graph TD A[Accuracy] --> D[Design\nTrade-offs] B[Performance] --> D C[Power] --> D E[Area] --> D style A fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style B fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style C fill:#ffcdd2,stroke:#c62828,stroke-width:3px style E fill:#fff9c4,stroke:#f57f17,stroke-width:3px style D fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px </pre> ] - **Architecture and Integration**: Deciding on the multiplier architecture (e.g., array, Wallace tree, Booth) and determining the optimal placement of approximate and exact sub-modules within the main multiplier is critical. --- ### 3. Challenges in Design (2/2) 🏗️🤔 - **Designing Effective Error Compensation**: For designs like fixed-width Booth multipliers, sophisticated error compensation schemes are needed to improve accuracy, make errors symmetrical, and reduce bias/MSE. Designing these effectively is a challenge. - **Scalability and Customization**: The circuit and error characteristics of approximate arithmetic circuits, including multipliers, can vary significantly for different sizes or bit-widths, especially as some designs are tailored for specific widths. Creating designs that are efficiently scalable or easily customizable for various requirements is challenging. - **Lack of Advanced Design Automation Tools**: Developing comprehensive design automation tools for complex approximate systems is an area for future work. --- ### 4. Challenges in Evaluation (1/2) 🔬📊 - **Accurate Error Quantification**: Precisely quantifying and bounding the accuracy loss introduced by approximation is of paramount importance. Measuring the "degree of approximation" accurately is crucial for real-life applications. - **Efficient Error Metric Computation**: Computing error metrics is essential, but existing simulation techniques may not be effective for large complex designs due to immense runtime increase and accuracy decrease. Analytical approaches also become hard and complicated with increased design complexity if accuracy is considered. BDD-based approaches suffer from state explosion problems for larger circuits. Developing fast and accurate error metrics evaluation methodologies is a key challenge. SAT solvers are being explored to enable exact error metrics calculation in a more scalable way. However, the runtime of SAT-based methods can still increase significantly with the number of inputs and linearly with the number of errors that need to be discovered. .mermaid[ <pre> graph LR A[Error Metric\nEvaluation] --> B[Simulation] A --> C[Analytical] A --> D[BDD-based] A --> E[SAT\nSolvers] style A fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style B fill:#fff9c4,stroke:#f57f17,stroke-width:3px style C fill:#fff9c4,stroke:#f57f17,stroke-width:3px style D fill:#ffcdd2,stroke:#c62828,stroke-width:3px style E fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px </pre> ] --- ### 4. Challenges in Evaluation (2/2) 🔬📊 - **Characterizing Error Behavior**: It is important to study the errors for different input distributions using appropriate error/QoS metrics. Understanding and characterizing error biases is crucial, as large error biases can significantly degrade accuracy in applications. - **Joint Hardware-Accuracy Evaluation**: Conventionally, performance and power efficiency were pursued independently. A challenge is to jointly consider hardware efficiency (delay, area, power) and accuracy to guide design choices. This involves synthesizing circuits under different design constraints (delay-optimized, area-optimized) and evaluating both aspects. --- ### 5. Challenges in Application (1/2) 📱🤖 - **Application Analysis and Mapping**: It is essential to analyze the application in detail to identify acceptable Quality of Service (QoS) and specify error metrics. Not all computations can be approximated; identifying non-critical tasks and isolating them from critical ones is important. Accurately mapping approximate hardware (like multipliers) to specific program parts is part of this. .mermaid[ <pre> graph LR A[Analyze\nApplication] --> B[Specify QoS\n& Error Metrics] B --> C[Identify\nNon-critical Tasks] C --> D[Map Approx HW\nto Program Parts] style A fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style B fill:#fff9c4,stroke:#f57f17,stroke-width:3px style C fill:#fff9c4,stroke:#f57f17,stroke-width:3px style D fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px </pre> ] - **Managing Application Quality**: Inaccurate adders and multipliers can limit the overall application quality regardless of the paired circuit elements. Quantifying the quality loss of the whole system is a challenge. It is important to prove the resilience of the application and ensure QoS constraints are met. --- ### 5. Challenges in Application (2/2) 📱🤖 - **Error Accumulation in Complex Operations**: In applications involving complex computations like multiple matrix multiplications, errors can accumulate. While a larger approximation might be tolerable in the multiplication itself, errors in **addition** can be more vulnerable in such cases. - **Impact on Robustness and Critical Tasks**: The impact of approximate computing techniques on the robustness of Machine Learning models is merely explored. Understanding what types of approximations can still be utilized, especially for **critical applications**, and what are the limits of approximate computing in such domains are open challenges. **Verification** (quantifying and bounding accuracy loss) is a major open research challenge, particularly in the context of mission-critical tasks and applications. Approximation adds another degree of inaccuracy on top of ML models, which are inherently inexact. - **Software-Hardware Integration**: Integrating approximate arithmetic circuits requires support from the software stack, including approximation libraries/frameworks, compiler extensions, runtime systems, and language annotations. Enabling programmers to specify QoS constraints and mark code regions for approximation is part of this challenge. Java extensions and compiler frameworks have been proposed. --- ### 6. Conclusion (1/2) ✅🎯 - Approximate arithmetic circuits, particularly multipliers, are crucial components for achieving **significant efficiency gains** in error-tolerant applications like image processing and machine learning. - Evaluation shows that approximate circuits can provide performance and energy advantages with **minimal accuracy loss**. Different designs offer varying tradeoffs between hardware efficiency and accuracy. - However, their design, evaluation, and application present notable challenges 🚧. .mermaid[ <pre> graph LR A[Approximate\nMultipliers] --> B[Significant\nEfficiency Gains] B --> C[Minimal\nAccuracy Loss] C --> D[Design, Evaluation &\nApplication Challenges] style A fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style B fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style C fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style D fill:#ffcdd2,stroke:#c62828,stroke-width:3px </pre> ] --- ### 6. Conclusion (2/2): Key Challenges & Future Work 🎯 - **Key Challenges Reviewed**: - Balancing complex tradeoffs between accuracy, performance, area, and power ⚖️. - Developing **fast and accurate methodologies** for evaluating error metrics, especially for large designs, beyond traditional simulation ⏱️📈. - Effectively managing the impact of errors, including biases and accumulation, on **application-level quality** and robustness, especially in critical tasks and ML. - Developing scalable and customizable designs and integrating them effectively with the software stack. - **Future Work** involves developing more comprehensive error metrics, exploring new approximation techniques, developing advanced design automation tools for complex systems, and further understanding the impact on application robustness. --- ### Key Takeaways ✅ - This survey provides a comprehensive evaluation and comparison of recently proposed approximate arithmetic circuits. - The findings can guide the selection of appropriate designs for application-specific requirements (e.g., high performance or low power). - Future work involves addressing current challenges like developing more comprehensive error metrics, exploring new approximation techniques, and developing design automation tools for complex systems. --- count: false class: nord-dark, middle, center ### Thank You! Questions? 🤔🙏 - Thank you for your attention!