Efficient Table-based Function Approximation on FPGAs Using Interval Splitting and BRAM Instantiation
Open Access
- 24 July 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Embedded Computing Systems
- Vol. 22 (4) , 1-24
Abstract
This article proposes a novel approach for the generation of memory-efficient table-based function approximation circuits for edge devices in general and FPGAs in particular. Given a function f(x) to be approximated in a given interval [ x 0 , x 0+a ) and a maximum approximation error E a , 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 equidistant 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, we propose and compare three algorithms for splitting the given interval into sub-intervals 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 while guaranteeing the maximum interpolation error bound E a . 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, for 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. The approach presented here for FPGAs can equally be applied to other circuit technologies for fast and, at the same time, memory-optimized function approximation at the edge.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- q LUTACM Transactions on Embedded Computing Systems, 2017
- Deep Learning for Mobile MultimediaACM Transactions on Multimedia Computing, Communications, and Applications, 2017
- Algorithm and Design of a Fully Parallel Approximate Coordinate Rotation Digital Computer (CORDIC)IEEE Transactions on Multi-Scale Computing Systems, 2017
- FAU: Fast and error-optimized approximate adder units on LUT-Based FPGAs2016
- Approximate Computing: A SurveyIEEE Design & Test, 2015
- Energy-Efficient Approximate Multiplication for Digital Signal Processing and Classification ApplicationsIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2014
- 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
- A survey of CORDIC algorithms for FPGA based computers1998