Automatic Generation of Complete Polynomial Interpolation Design Space for Hardware Architectures
Pages 573 - 578
Abstract
Hardware implementations of elementary functions regularly deploy piecewise polynomial approximations. This work determines the complete design space of piecewise polynomial approximations meeting a given accuracy specification. Knowledge of this design space determines the minimum number of regions required to approximate the function accurately enough and facilitates the generation of optimized hardware which is competitive against the state of the art. Designers can explore the space of feasible architectures without needing to validate their choices. A heuristic based decision procedure is proposed to generate optimal ASIC hardware designs. Targeting alternative hardware technologies simply requires a modified decision procedure to explore the space. We highlight the difficulty in choosing an optimal number of regions to approximate the function with, as this is input width dependent.
References
[1]
Nicolas Brisebarre and Sylvain Chevillard. 2007. Efficient polynomial L-approximations. In Proceedings - Symposium on Computer Arithmetic. IEEE, 169--176.
[2]
Sylvain Chevillard, Mioara Joldeş, and Christoph Lauter. 2010. Sollya: An environment for the development of numerical codes. In International congress on mathematical software, Vol. 6327 LNCS. Springer, 28--31.
[3]
Florent De Dinechin, Mioara Joldes, and Bogdan Pasca. 2010. Automatic generation of polynomial-based hardware architectures for function evaluation. In Proceedings - International Conference on Application-Specific Systems, Architectures and Processors. IEEE, 216--222.
[4]
F. de Dinechin and B. Pasca. 2011. Custom Arithmetic Datapath Design for FPGAs using the FloPoCo Core Generator. Design & Test of Computers, IEEE 28, 4 (2011), 18--27.
[5]
Jérémie Detrey and Florent De Dinechin. 2005. Table-based polynomials for fast hardware function evaluation. In Proceedings - International Conference on Application-Specific Systems, Architectures and Processors. IEEE, 328--333.
[6]
Jérémie Detrey and Florent de Dinechin. 2007. Parameterized floating-point logarithm and exponential functions for FPGAs. Microprocessors and Microsystems 31, 8 (2007), 537--545.
[7]
Theo Drane, Wai Chuen Cheung, and George Constantinides. 2012. Correctly rounded constant integer division via multiply-add. In International Symposium on Circuits and Systems. IEEE, 1243--1246.
[8]
Dong U. Lee, Altaf Abdul Gaffar, Oskar Mencer, and Wayne Luk. 2005. Optimizing hardware function evaluation. IEEE Trans. Comput. 54, 12 (2005), 1520--1531.
[9]
Jean Michel Muller. 1994. Bkm:A New Hardware Algorithm for Complex Elementary Functions. IEEE Trans. Comput. 43, 8 (1994), 955--963.
[10]
Jean-Michel Muller. 2016. Elementary functions: algorithms and implementation (3rd ed.). Number 05. Birkhauser, Boston.
[11]
M. Schulte and E. Swartzlander. 2002. Exact rounding of certain elementary functions.
[12]
Antonio Giuseppe Maria Strollo, Davide De Caro, and Nicola Petra. 2011. Elementary functions hardware implementation using constrained piecewise-polynomial approximations. IEEE Trans. Comput. 60, 3 (2011), 418--432.
[13]
Synopsys. 2021. Design Compiler User Guide S-2021.06-SP2. Technical Report. Synopsys, Mountain View.
[14]
Ping Tak Peter Tang. 1991. Table-lookup algorithms for elementary functions and their error analysis. In Proceedings - Symposium on Computer Arithmetic. IEEE, 232--236.
[15]
Jack E. Volder. 1959. The CORDIC Trigonometric Computing Technique. IRE Transactions on Electronic Computers EC-8, 3 (1959), 330--334.
Index Terms
- Automatic Generation of Complete Polynomial Interpolation Design Space for Hardware Architectures
Recommendations
Recursive polynomial interpolation algorithm (RPIA)
Let x0, x1, ź , xn be a set of n+1 distinct real numbers (i.e., xi ź xj for i ź j) and y0, y1, ź , yn be given real numbers; we know that there exists a unique polynomial pn(x) of degree n such that pn(xi) = yi for i = 0, 1, ź , n; pn is the ...
System level hardware module generation
In complex modern day electronic systems, far more time is spent in designing the boards, writing the software to drive and integrate the hardware, and other such system level issues, than is spent in designing any application-specific ICs that may be ...
Classical multivariate Hermite coordinate interpolation on n-dimensional grids
AbstractIn this work, we study the Hermite interpolation on n-dimensional non-equally spaced, rectilinear grids over a field k of characteristic zero, given the values of the function at each point of the grid and the partial derivatives up to a maximum ...
Highlights- An algebraically simple coordinate Hermite interpolation formula.
- Partial derivatives of any degree up to a maximum, at points on nD-grid.
- The remainder of the interpolation is provided in integral form.
- The ideal of the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
In-Cooperation
- IPSJ
- IEEE CAS
- IEEE CEDA
- IEICE
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 31 January 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ASPDAC '23
Sponsor:
ASPDAC '23: 28th Asia and South Pacific Design Automation Conference
January 16 - 19, 2023
Tokyo, Japan
Acceptance Rates
ASPDAC '23 Paper Acceptance Rate 102 of 328 submissions, 31%;
Overall Acceptance Rate 466 of 1,454 submissions, 32%
Upcoming Conference
ASPDAC '25
- Sponsor:
- sigda
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 149Total Downloads
- Downloads (Last 12 months)70
- Downloads (Last 6 weeks)8
Reflects downloads up to 13 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in