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.