Report Number: CSL-TR-00-790
Institution: Stanford University, Computer Systems Laboratory
Title: Reciprocal Approximation Theory with Table Compensation
Author: Liddicoat, Albert A.
Author: Flynn, Michael J.
Date: January 2000
Abstract: [Sch93] demonstrates the reuse of a multiplier partial product
array (PPA) to approximate higher order functions such as the
reciprocal, division, and square root. Schwarz generalizes
this technique to any higher order function that can be
expressed as A*B=C. Using this technique, the height of the
PPA increases exponentially to increase the result precision.
Schwarz added compensation terms within the PPA to reduce the
worst case error.
This work investigates the approximation theory of higher order
functions without the bounds of multiplier reuse. Additional
techniques are presented to increase the worst case precision
for a fixed height PPA.
A compensation table technique is presented in this work. This
technique combines the approximation computation with a
compensation table to produce a result with fixed precision.
The area-time tradeoff for three design points is studied.
Increasing the computation decreases the area needed to implement
the function but also increases the latency.
Finally, the applicability of this technique to the bipartite ROM
reciprocal table is discussed. We expect that this technique can
applied to the bipartite ROM reciprocal table to significantly
reduce the hardware area needed at a minimal increase in latency.
In addition, this work focuses on hardware reconfigurability and
ability of the hardware unit to be used to perform multiple
higher order functions efficiently. The PPA structure can be
used to approximate several higher order functions that can be
expressed as a multiply.