Efficient Table-based Function Approximation on FPGAs using Interval Splitting and BRAM Instantiation
Preprint
Abstract
This paper proposes a novel approach for the generation of memory-efficient table-based function approximation circuits for FPGAs. Given a function f(x) to be approximated in a given interval [x0,x0+a] and a maximum approximation error Ea, the goal is to determine a function table implementation with a minimized memory footprint, i.e., number of entries that need to be stored. Rather than state-of-the-art work performing an even sampling of the given interval by so-called breakpoints and using linear interpolation between two adjacent breakpoints to determine f(x) at the maximum error bound, first, we propose three interval-splitting algorithms to reduce the required memory footprint drastically based on the observation that in sub-intervals of low gradient, a coarser sampling grid may be assumed to satisfy the maximum interpolation error bound. Experiments on elementary mathematical functions show that a large fraction in memory footprint may be saved. Second, a hardware architecture implementing the sub-interval selection, breakpoint lookup and interpolation at a latency of just 9 clock cycles is introduced. Third, within each generated circuit design, BRAMs are automatically instantiated rather than synthesizing the reduced footprint function table using LUT primitives providing an additional degree of resource efficiency.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Energy and area efficient imprecise compressors for approximate multiplication at nanoscaleAEU - International Journal of Electronics and Communications, 2019
- ApproxLUT: A novel approximate lookup table-based accelerator2017
- Algorithm and Design of a Fully Parallel Approximate Coordinate Rotation Digital Computer (CORDIC)IEEE Transactions on Multi-Scale Computing Systems, 2017
- Compressed Sensing Approaches for Polynomial Approximation of High-Dimensional Functions2017
- FAU: Fast and error-optimized approximate adder units on LUT-Based FPGAs2016
- Energy-Efficient Approximate Multiplication for Digital Signal Processing and Classification ApplicationsIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2014
- Approximate computing: An emerging paradigm for energy-efficient design2013
- Efficient Logarithmic Converters for Digital Signal Processing ApplicationsIEEE Transactions on Circuits and Systems II: Express Briefs, 2011
- A fast segmentation algorithm for piecewise polynomial numeric function generatorsJournal of Computational and Applied Mathematics, 2011
- Hierarchical Segmentation for Hardware Function EvaluationIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2008