Table-based polynomials for fast hardware function evaluation

Jérémie Detrey (1) , Florent de Dinechin (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

Many general table-based methods for the evaluation in hardware of elementary functions have been published. The bipartite and multipartite methods implement a first-order approximation of the function using only table lookups and additions. Recently, a single-multiplier second-order method of similar inspiration has also been published. This paper presents a general framework extending such methods to approximations of arbitrary order, using adders, small multipliers, and very small ad-hoc powering units. We obtain implementations that are both smaller and faster than all previously published approaches. This paper also deals with the FPGA implementation of such methods. Previous work have consistently shown that the more complex methods were also faster: The reduction of the table size meant a reduction of its lookup time, which compensated for the addition and multiplication time. A second contribution is therefore to finally create a tradeoff between space and time among table-based methods.

De nombreuses méthodes générales à base de tables pour l’évaluation matérielle de fonctions élémentaires ont été publiées. Les mathodes bipartite et multipartite implémentent une approximation du premier ordre de la fonction en utilisant uniquement des accès à des tables et des additions. Récemment, une méthode du second ordre n’utilisant qu’un multiplieur,inspirée des précédentes, a aussi été publiée. Cet article présente un cadre général pour étendre de telles méthodes à des approximations d’ ordres supérieurs,utilisant des additionneurs, de petits multiplieurs, et de très petites unités dédiées d’élévation à une puissance donnée. Nous obtenons des implémentations qui sont tant plus petites que plus rapides que toutes les méthodes précèdemment publiées. Cet article présente aussi l’implémentation de telles méthodes sur FPGA. Des travaux antérieurs ont montré`a plusieurs reprises que des méthodes plus complexes sont aussi plus rapides : la réduction de la taille des tables entraîne une réduction du temps d’accès,qui contre-balancele coût des additions et des multiplications. Cette contribution vise donc à trouver où se situe le compromis entre surface et latence pour les méthodes à base de tables.

Mots clés: Function evaluation; Hardware operators; Polynomial approximation; Table-based method

Mots clés: FPGA; approximation polynomiale; ´Evaluation de fonctions; méthode à base de tables; opérateurs matériels

Domaines: Informatique [cs]

Jérémie Detrey, Florent de Dinechin. Table-based polynomials for fast hardware function evaluation. [Research Report] LIP RR-2004-52, Laboratoire de l'informatique du parallélisme. 2004, 2+11p. ⟨hal-02101996⟩