Arnaud TISSERAND CNRS Researcher (CR1), IRISA Laboratory, CAIRN group in Lannion
Remark: This program was developped in the LIRMM laboratory and the ARITH research group in 2005.
Initial approximations or seeds are often used in the initialization of floating-point division and square root software iterations [3,4,5] (for reducing the number of iterations). Seedgen is an optimized and synthesizable VHDL generator for hardware seed approximation to the reciprocal and square root reciprocal functions. The generated operator is based on a very optimized polynomial approximation with specific coefficients and a table lookup. The corresponding architecture is very simple and leads to small and fast circuits. The main supported parameters are the target function (1/x or 1/sqrt(x)), argument width, internal accuracy and some hardware constraints. The seedgen program is based on a work by Ercegovac, Muller and Tisserand [1,2]. Seedgen is a C program distributed under the GNU General Public License (GPL).
In this example, we are looking for the initial approximation to the reciprocal function with 5-bit argument and without additional option.
The corresponding command line is:
seedgen -f r -n 4
It produces the following output:
<seedgen> max error = 1.512097e-02 (6.047306 bits) <seedgen> average error = 8.336747e-03 (6.906300 bits) <seedgen> max offset = 3 (2 bits) <seedgen> table size = 2^4 x 2 (32 bits)
and some automatically generated files:
| filename | description | download | graphical result |
|---|---|---|---|
res.vhdl |
the optimized seed architecture in VHDL | vhdl | |
res_approx.gnuplot |
approximation curve | gnuplot | |
res_error.gnuplot |
error curve | gnuplot | pdf (figure below) |
tar xvfz seeden-0.1.tar.gz cd seedgen-0.1
./configure [--prefix=path] make make install
test directory, there are test files for
some parameter sets functional simulation (read the test
documentation file readme)
A complete description of the implemented method and the various parameters specification is presented in the research report [2]. A shorter version was presented at the 39th Asilomar Conference on Signals, Systems and Computers in October 2005 [1].
The list of all supported parameters is available using the command:
seedgen -h
This gives for the version 0.1:
Usage: seedgen -f char -n int [-g int] [-o char] [-r char] [-t] [-h]
VHDL generator for seed approximation to 1/x and 1/sqrt(x) functions
Version 0.1 (2005-10-03)
Mandatory arguments:
-f approximated function
r 1/x
s 1/sqrt(x)
-n # fractional bits in the argument (2 <= int <= 16)
Optional arguments:
-g # guard bits
constraint for 1/x (1 <= int <= 4, default = 1)
constraint for for 1/sqrt(x) (2 <= int <= 4, default = 2)
-o optimizations (default: no optimization)
n table with negative offsets (in 2's complement)
-r register level (default: no register)
o for output only
i for input only
b for input and output
-t trace the computations
-h print this help page
[1] M. Ercegovac, J.-M. Muller and A. Tisserand. Simple seed architectures for reciprocal and square root reciprocal. 39th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, California, U.S.A., October 2005.
[2] M. Ercegovac, J.-M. Muller and A. Tisserand. Simple seed architectures for reciprocal and square root reciprocal. Research Report, October 2005.
[3] J.-M. Muller. Elementary Functions: Algorithms and Implementation. Birkhäuser, Boston, 1997.
[4] M. Ercegovac and T. Lang. Digital Arithmetic. Morgan Kaufmann, 2003.
[5] P. Markstein. IA-64 and Elementary Functions : Speed and Precision. Prentice Hall, 2000.