Fast approximate reciprocal approximations for iterative algorithms
The reciprocal function, 1/x, is important for many real-time algorithms. It is used in a large variety of algorithms from areas ranging from iterative estimation to machine learning. Many of these algorithms are iterative in nature and require the online computation of the reciprocal. Such an iterative structure often prevents effective use of pipelining for implementation of the reciprocal. For this reason, a reciprocal algorithm requiring only a low amount of clock cycles is desired. Many real-time algorithms, often being of approximate nature, can tolerate the use of only an approximate solution of the reciprocal. For this reason, we present a low complexity non-iterative approximation of the reciprocal function. This approximation can be calculated using only combinatorial logic. We present synthesis results showing that the proposed approach can be implemented with low area requirements at high clock frequencies. We analytically describe the error of the approximation and show that by optimizing a constant value used in the approximation, different variants with different error behaviors can be obtained. We furthermore present performance results of application examples that, when using our proposed method, show only negligible performance degradation compared to when using the exact reciprocal function, demonstrating the versatility of our proposed approach.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Reciprocal Learning
We demonstrate that a wide array of machine learning algorithms are specific instances of one single paradigm: reciprocal learning. These instances range from active learning over multi-armed bandits to self-training. We…
Active LearningMulti-Armed BanditsConstructing fast approximate eigenspaces with application to the fast graph Fourier transforms
We investigate numerically efficient approximations of eigenspaces associated to symmetric and general matrices. The eigenspaces are factored into a fixed number of fundamental components that can be efficiently manipula…
Iterative Methods for Vecchia-Laplace Approximations for Latent Gaussian Process Models
Latent Gaussian process (GP) models are flexible probabilistic non-parametric function models. Vecchia approximations are accurate approximations for GPs to overcome computational bottlenecks for large data, and the Lapl…
Safety-Constrained Learning and Control using Scarce Data and Reciprocal Barriers
We develop a control algorithm that ensures the safety, in terms of confinement in a set, of a system with unknown, 2nd-order nonlinear dynamics. The algorithm establishes novel connections between data-driven and robust…
Novel and Efficient Approximations for Zero-One Loss of Linear Classifiers
The predictive quality of machine learning models is typically measured in terms of their (approximate) expected prediction accuracy or the so-called Area Under the Curve (AUC). Minimizing the reciprocals of these measur…