Approximate Computing

This book explores the technological developments at various levels of abstraction, of the new paradigm of approximate computing. The authors describe in a single-source the state-of-the-art, covering the entire spectrum of research activities in approximate computing, bridging device, circuit, architecture, and system levels. Content includes tutorials, reviews and surveys of current theoretical/experimental results, design methodologies and applications developed in approximate computing for a wide scope of readership and specialists. Serves as a single-source reference to state-of-the-art of approximate computing; Covers broad range of topics, from circuits to applications; Includes contributions by leading researchers, from academia and industry. Preface References Acknowledgment Contents About the Editors Part I Introduction: Approximate Arithmetic Circuits 1 Introduction: Approximate Arithmetic Circuits 1 Introduction 2 Approximate Arithmetic Unit 2.1 Approximate Adder 2.2 Approximate Multiplier 2.3 Approximate Divider 3 Approximate Blocks 3.1 Approximate FFT 3.2 Approximate MAC 4 Applications Based on Approximate Arithmetic 4.1 Approximate Redundancy 4.2 Approximate 2D Convolver for Image Processing 5 Error Compensation for Approximate Arithmetic 6 Conclusion References 2 An Automated Logic-Level Framework for Approximate Modular Arithmetic Circuits 1 Introduction 2 Related Work 3 Problem Formulation and Approach 3.1 Problem Statement 3.2 Basic Approach 3.2.1 1-to-0 Complement 3.2.2 0-to-1 Complement 4 The Proposed Automated Framework 4.1 Symmetry Finder (SF) Algorithm 4.2 Mine Sweeper (MS) Algorithm 5 Design Exploration of Approximate Arithmetic Units 5.1 22 Multipliers 5.2 44 Multipliers 5.3 Larger Multipliers 6 Performance Evaluation 6.1 Error Analysis 6.2 Hardware Analysis 6.3 MRED vs PDP Comparison 7 Case Study 7.1 Image Sharpening 7.2 Canny Edge Detection 8 Conclusion References 3 Approximate Multiplier Design for Energy Efficiency: From Circuit to Algorithm 1 Introduction 2 Background 2.1 Fixed Point vs. Floating Point 2.2 Binary Multiplier 2.3 Approximate Multiplier 3 Approximate Multiplier with Architecture Level Approximation 3.1 Approximation at Input 3.2 Approximation at Partial Product Generation 3.3 Approximation at Accumulation 3.4 Approximate at Booth Encoding 4 Approximate Multiplier with Algorithm Level Approximation 4.1 Logarithm-Based Approximation 4.2 Approximation with Linearization 4.3 Hybrid Approximation 5 Approximate Multiplier with Circuit Level Approximation 5.1 K-Map Modification 5.2 Gate-Level Pruning 5.3 Voltage Over-Scaling 6 Conclusions References 4 Low-Precision Floating-Point Formats: From General-Purpose to Application-Specific 1 Introduction 2 Low-Precision Floating-Point Formats 2.1 IEEE-Style FP Formats 2.1.1 General-Purpose IEEE-Standard FP Formats 2.1.2 Application-Specific FP Formats 2.2 Block Floating-Point Formats 2.3 Posit Floating-Point Formats 3 Application-Specific FP Formats: Case Study 3.1 Mixed-Precision PageRank: CPMS Approach 3.2 Low-Precision PageRank: Half-Precision with APHP 4 Low-Precision FP Formats: Performance Impact 4.1 Low Precision in CPU 4.2 Low Precision in TPUs/GPUs 4.3 Low Precision in ASIC/FPGA 5 Application-Specific Low-Precision FP Formats: Design Guidelines 6 Conclusions References 5 Spintronic Solutions for Approximate Computing 1 Introduction 2 Basics of Spintronic Devices 3 STT-MRAM-Based Approximate Computing 3.1 STT-MRAM-Based Traditional Approximate Full Adders 3.2 Write-Only Bitwise Approximate Full Adders Based on SOT-MTJ and VCMA-MTJ 3.2.1 AxFAs Energy-Delay Performance 3.2.2 Accuracy Tradeoff 4 Summary References 6 Majority Logic-Based Approximate Multipliers for Error-Tolerant Applications 1 Introduction 2 ML-Based Approximate Unsigned Multipliers 2.1 Preliminaries 2.2 Approximation in Generating Partial Products 2.2.1 Design 2.2.2 Evaluation 2.3 Approximation in Partial Product Accumulation 2.3.1 Design 2.3.2 Evaluation 2.4 Approximation in the Partial Product Tree 2.4.1 Design 2.4.2 Evaluation 2.5 Application 2.6 Discussion 3 ML-Based Approximate Signed Radix-4 Booth Multipliers 3.1 Preliminaries 3.1.1 Radix-4 Booth Encoding 3.1.2 ML Implementations of Partial Product Generators 3.2 Approximation in Partial Product Generation 3.2.1 Design 3.2.2 Evaluation 3.3 Approximation in PP Reduction and Compression 3.3.1 Design 3.3.2 Evaluation 3.4 Application 3.4.1 Image Processing 3.4.2 Classification 3.4.3 Face Detection and Alignment 3.5 Discussion 4 Conclusion References Part II Introduction: Design Automation and Test 7 Approximate Logic Synthesis for FPGA by Decomposition 1 Introduction 2 Related Work 2.1 Approximate Logic Synthesis for FPGA 2.2 Approximate Logic Synthesis Based on Decomposition 3 Preliminaries 3.1 Simple Disjoint Decomposition 3.2 Fanout-Free Cone (FFC) 3.3 Error Rate and Monte Carlo Simulation 4 Methodology 4.1 Basic Idea 4.2 Approximate Disjoint Decomposition 4.3 Approximate Non-disjoint Decomposition 4.4 Iterative Approximate Decomposition 4.5 Iterative Input Removal 4.6 Overall ALS Flow 5 Experimental Results 5.1 The Performance of Our Method 5.2 Comparison with the Existing ALS Methods for FPGA 6 Conclusion References 8 Design Techniques for Approximate Realization of Data-Flow Graphs 1 Introduction 2 Preliminaries 2.1 Energy and Power Consumption in Compute Units 2.2 Approximate Computing and DSE in Multi-Objective Optimization Problems 2.3 Approximate High-Level Synthesis 2.4 Error Evaluation Metrics 3 DSE Algorithms in Optimization of Approximate Circuits 3.1 First Category Local Search Approaches 3.1.1 Automated Behavioral Approximate Circuit Synthesis (ABACUS) Technique 3.1.2 Other Works in the First Category 3.2 Second Category Evolutionary Approaches 3.2.1 Exploring the Trade-Off Between Accuracy and Energy Efficiency (EGAN) Framework 3.2.2 Modified ABACUS Work 3.2.3 Other Works in the Second Category 3.3 Comparison of the Works 4 Future Directions References 9 Approximation on Data Flow Graph Execution for Energy Efficiency 1 Introduction 2 Chapter Overview 3 Approximation on DFG Execution: Challenges and Solutions 3.1 Data Flow Graph Basics 3.2 Main Questions for Approximation on DFGs and Their Execution 3.3 Approximation Techniques 4 Probabilistic Design for Multimedia Systems 4.1 An Illustrative Example 4.2 Probabilistic Design Overview 4.3 Probabilistic Timing Performance Profiling and Estimation 4.4 Offline and Online Resource Management 5 Estimate and Recompute During DFG Execution 5.1 Conversion from Floating Point to Logarithmic 5.2 Arithmetic Operations in Logarithmic Representations 5.3 Noncriticality Truncation 5.4 Runtime DFG Approximation Algorithms 6 Approximate Logarithms by Bit-Width Optimization 6.1 Error Analysis for Logarithms 6.2 Energy Analysis for Logarithms 6.3 BWOLF System Structure 7 Summary References 10 Test and Reliability of Approximate Hardware 1 Introduction and Background 1.1 Reliability Issues in Nanometer Technology 1.2 Reliability Improvement Approaches 1.2.1 Fault-Tolerant Architectures 1.2.2 Selective Hardening Approaches 1.3 Toward Approximate-Computing-Based Reliable Hardware 2 Testing Approximate Hardware 2.1 Approximation-Aware Fault Classification 2.2 Approximation-Aware Test Pattern Generation 2.3 Approximation-Aware Test Set Application 3 Fault-Tolerant Architectures Based on Approximate Computing 3.1 Selective Hardening Based on Approximate Duplication 3.1.1 Structural Susceptibility Analysis 3.1.2 Selective Error Detection Architectures for Arithmetic Circuits 3.1.3 Comparisons 3.2 Ensuring Fault Tolerance Through Approximate Redundancy 3.2.1 The QAMR Scheme 4 Conclusion References Part III Introduction: Security 11 Security Vulnerabilities and Countermeasures for Approximate Circuits 1 Introduction 2 Approximate Arithmetic Circuits 3 Hardware Trojans 4 Security Vulnerabilities in Circuit Designs 4.1 Malicious Modification 4.2 Hardware Trojans Attacks 4.2.1 Transition Probability 4.2.2 Approximate Circuit Analysis 5 Security Threats in Approximate Testing Techniques 5.1 Approximate Testing Techniques 5.2 Malicious Tampering Attack 5.3 Countermeasures Test Pattern Generation 5.4 Experimental Analysis 5.4.1 Experimental Setup 5.4.2 Experimental Results 6 Conclusion References 12 Voltage Overscaling Techniques for Security Applications 1 Introduction 2 Voltage Overscaling 3 VOS in Processing Elements 3.1 VOS Example 3.2 Errors in an Approximated Circuit 4 VOS in Memory 4.1 Basics of Dynamic Random Access Memory (DRAM) System 4.2 VOS in DRAM 5 Security Applications of Voltage Overscaling 5.1 Simple Authentication Protocol Design Using Voltage Overscaling 5.1.1 Notations 5.1.2 Description of the Protocol 5.1.3 Evaluation of the Protocol 5.1.4 Reliability Issues in VOS-Based Designs 5.1.5 Mitigating Reliability Issues 5.2 Model Inversion Defense Using Voltage-Overscaled Memory 5.2.1 Model Inversion Attacks 5.2.2 Hardware-Oriented Defense Against MIA 5.2.3 Accuracy and Security Issues for VOS-Based MIA Defense 6 Voltage Overscaling and Security Vulnerabilities 7 Conclusions References 13 Approximate Computing for Cryptography 1 Introduction 2 Approximate Hash 2.1 Approximate Bitcoin Mining 2.2 The Economics of Bitcoin Mining 2.3 Mining Approximation 3 Approximate Learning with Error (LWE) 3.1 Homomorphic Encryption 4 Conclusions References 14 Towards Securing Approximate Computing Systems: Security Threats and Attack Mitigation 1 Introduction 2 Security Threat Models in Approximate Computing 3 Hardware Attacks in Conventional Computing vs in Approximate Computing Systems 3.1 Hardware Trojans 3.2 Fault Attacks 3.3 Covert Channel Attacks 3.4 Reverse Engineering Attacks 4 General Guideline of Countermeasure Designs for AC Systems 4.1 Randomization 4.2 Access Prohibition 4.3 Noise Injection 4.4 Design Obfuscation 5 Example of Attack Detection Methods 5.1 Metric Based Attack Detection 5.1.1 Metrics 5.1.2 Precise Approximate Unit Under Test for Security Examination Method 5.1.3 Attack Success Rate Assessment Using PAUSE Attack Detection 5.2 Logic Function Based Attack Detection 5.2.1 Integrity Check and Exclusive Logic Based Attack Detection 5.2.2 Assessment of Attack Detection Rate 6 Pro-Active Defense Mechanisms 6.1 Obfuscate WHEN to Approximate (WNA) 6.2 Obfuscate WHAT to Approximate (WTA) 6.3 Obfuscate HOW to Approximate (HWA) 6.4 Case Study : Design Obfuscation Using Image Classification Application 7 Summary and Future Research Directions References Part IV Introduction: Neural Networks and Machine Learning 15 Approximate Computing for Machine Learning Workloads: A Circuits and Systems Perspective 1 Introduction 2 What Is Approximate Computing? 3 Neural Networks: Background 3.1 Fully Connected Networks (FCN) 3.2 Convolutional Neural Networks (CNN) 4 Approximate Hardware Design 4.1 Approximate Multiplication for Neuronal Computation 4.2 Approximate Adders 4.3 Voltage-Scaled Approximate Memory for On-chip Storage 4.4 Analog In-Memory Computing 5 Approximate Hardware-Algorithm Co-design 5.1 Lower Complexity Networks 5.2 Pruning 6 Approximate Hardware-in-the-Loop Training 6.1 Retraining to Mitigate Accuracy Loss 6.2 Simulation Framework: Circuits to Systems 6.3 Optimized Baseline Deep Neural Networks 6.4 Approximations at Algorithm Level 6.4.1 Lower Complexity Networks 6.4.2 Synaptic Pruning 6.5 Approximations at Hardware Level 6.5.1 Approximate Multiplier Based Networks 6.5.2 Voltage-Scaled Approximate Synaptic Memory 6.6 Combined Approximate Networks 7 Comparing Approximate Networks References 16 Approximate Computing for Efficient Neural Network Computation: A Survey 1 Introduction 2 Background 2.1 Neural Network Computation 2.2 Error Resilience of Neural Networks 2.3 Evaluation Metrics 3 Approximate Multiplier for Neural Network Computation 3.1 Linear Domain Approximate Multiplier 3.1.1 Design Methodology 3.1.2 The Selection of Approximate Multiplier 3.2 Logarithm Domain Approximate Multipliers 3.2.1 Design Methodology 3.2.2 Comparison of Logarithm and Linear Domain Multipliers 4 Discussion and Perspectives 4.1 Evaluation Process 4.2 Challenges 4.3 Future Research Directions 5 Conclusion References 17 Enabling Efficient Inference of Convolutional Neural Networks via Approximation 1 Introduction 2 CNN Inference with Approximate Multipliers 2.1 Optimizing Approximate Multipliers 2.2 Error Compensation 2.3 Inference Accuracy 3 CNN-Oriented Reconfigurable Approximation 3.1 Design of Reconfigurable Multipliers 3.1.1 Error Variance Based Reconfigurable Approximate Multiplier 3.1.2 Positive/Negative Reconfigurable Approximate Multiplier 3.2 Weight-Based Mapping 3.3 Energy Gains Under Accuracy Drop Thresholds 4 Mitigating Temperature and Aging Effects in NPUs Through Approximation 4.1 Thermal Challenges in NPUs 4.2 Aging Effects in Transistors 4.3 Fighting Temperature Effects via Approximation 4.4 Fighting Aging Effects via Approximation References 18 Approximate Computing for Energy-Constrained DNN-Based Speech Recognition 1 Algorithm-Level Approximate Computing for KWS 1.1 Feature Extraction and DNN-Based Keywords Classification 1.2 Quantization and Compression for DNN 2 Circuit-Level Approximate Computing for KWS 2.1 Analog/Analog–Digital Mixed Approximate Computing 2.2 Digital Approximate Computing 2.2.1 Design Metrics of Approximate Computing Units 2.2.2 Approximate Adder 2.2.3 Approximate Multiplier 2.3 Approximate Computing with Emerging Microelectronic Device 3 Architecture-Level Approximate Computing for KWS 3.1 Reconfigurable Architecture Using Approximate Computing 3.2 Co-design Framework of Software and Hardware Approximate Computing for KWS 4 Conclusion References 19 Efficient Approximate DNN Accelerators for Edge Devices: An Experimental Study 1 Introduction 2 Designing a Re-configurable Approximate Booth Multiplier for Inference of DNNs 2.1 Step 1: Removing Correction Terms 2.2 Step 2: Truncation of Partial Products 2.3 Step 3: Replacing Exact Partial Products with Inexact Ones 2.3.1 Step 3 (A) 2.3.2 Step 3 (B) 2.4 Step 4: Applying Dynamic Approximation into Partial Products While Performing Shift Operation 2.4.1 Step 4 (A) 2.4.2 Step 4 (B) 3 Proposed Architecture 3.1 MAC Unit and PE Specifications 3.2 Distributor Units 3.3 Global Buffers 4 Experimental Results and Discussion 4.1 Accuracy Analysis 4.2 Hardware Implementation 5 Conclusion References Part V Introduction: Applications 20 Cross-Level Design of Approximate Computing for Continuous Perception System 1 General Framework of Approximate Computing in Continuous Perception System 2 Approximate Digital and Analog Arithmetic Units 2.1 Analog Circuit Design for Approximate Adder and Multiplier 2.2 Digital Circuit Design for Approximate Adder 3 Approximate Memory Design 4 Cross-Layer Optimization of Approximate Computing 5 Summary References 21 Approximate Computing in Image Compression and Denoising 1 Introduction 2 Zigzag Low-Complexity Approximate DCT 2.1 Preliminaries of DCT in Image Compression 2.2 Principle of ZLCADCT Technique 2.3 Modeling of ZLCADCT 2.4 Evaluation by Simulation for ZLCADCT 2.4.1 Resources and Complexity Analysis 2.4.2 Output Image Evaluation 3 Approximate Newton Method for Unconstrained Total Variation–Based Image Denoising 3.1 Preliminaries of the Approximate Newton Method 3.2 Approximate Newton Method Using Additional Step Length Parameter 3.3 Evaluation by Simulation for Additional Step Length Parameter 4 Summary References 22 Approximate Computation for Baseband Processing 1 Stochastic Computing 2 Stochastic-Computing-Based Decoders 2.1 Stochastic Polar Code Decoder 2.1.1 Stochastic SC (SSC) Decoder 2.1.2 Stochastic SCL (SSCL) Decoder 2.1.3 Stochastic BP (SBP) Decoder 2.2 Stochastic LDPC Decoder 3 Stochastic-Computing-Based MIMO Detector 3.1 Stochastic BP Detector 3.1.1 The Stochastic Architecture for Observation Nodes 3.1.2 The Stochastic Architecture for Symbol Nodes 3.1.3 The Stochastic Architecture of Decision Module 3.1.4 The Overall Architecture for Stochastic BP Detector 3.2 Stochastic MMSE Detector 3.3 Stochastic Markov Chain Monte Carlo (MCMC) Detector References Index