Florent De
email: florent.de-dinechin@insa-lyon.fr!

On fixed-point hardware polynomials

Keywords: elementary function, hardware evaluator, polynomial approximation, computer arithmetic

Polynomial approximation is a general technique for the evaluation of numerical functions of one variable. This article addresses the automatic construction of fixed-point hardware polynomial evaluators. By systematically trying to balance the accuracy of all the steps that lead to an architecture, it simplifies and improves the previous body of work covering polynomial approximation, polynomial evaluation, and range reduction. This work is supported by an open-source implementation.

INTRODUCTION

This article addresses the automatic construction of fixedpoint polynomial evaluators for a real function f of one real variable x over a closed interval I. This is a very generally useful building block when designing hardware functions in fixed-point [START_REF] Cheung | Hardware generation of arbitrary random number distributions from uniform distributions via the inversion method[END_REF], [START_REF] De Dinechin | Fixed-point trigonometric functions on FPGAs[END_REF], [START_REF] De Dinechin | Hardware implementations of fixed-point Atan2[END_REF] or floating-point [START_REF] De Dinechin | Floating-point exponential functions for DSP-enabled FPGAs[END_REF], [START_REF] De Dinechin | Floating-point exponentiation units for reconfigurable computing[END_REF], [START_REF] Thomas | A general-purpose method for faithfully rounded floating-point function approximation in FPGAs[END_REF] for application-specific processors or reconfigurable computing [START_REF] Kapre | Accelerating SPICE model-evaluation using FPGAs[END_REF], [START_REF] De Dinechin | High-Performance Computing using FPGAs[END_REF]. This article refines several previous works describing generic function approximators [START_REF] Lee | Optimizing hardware function evaluation[END_REF], [START_REF] Lee | Hierarchical segmentation schemes for function evaluation[END_REF], [START_REF] De Dinechin | Automatic generation of polynomial-based hardware architectures for function evaluation[END_REF]: tools that input a function and parameters specifying its context, and produce an architecture, as illustrated by Figure 1.

The construction of a polynomial evaluator typically proceeds in three steps. The first is the computation if a polynomial that approximates the function f . The second is the generation of adders and multipliers that will evaluate this polynomial. These two steps are usually preceded by a range-reduction that transform the initial function into one more suited for polynomial approximation [START_REF] Muller | Elementary Functions, Algorithms and Implementation[END_REF], [START_REF] Lee | Hierarchical segmentation schemes for function evaluation[END_REF], [START_REF] Thomas | A general-purpose method for faithfully rounded floating-point function approximation in FPGAs[END_REF].

The main constribution of this article is to show that these three steps (Sections 2 to 4) are deeply linked by arithmetic considerations. Expliciting these links enables a very simple derivation of near-optimal values of most architectural parameters, for which previous works often Functional spec.

Performance spec.

architecture generator function f : [0, 1) →?

input precision in output format (mout, out) degree FPGA frequency vhdl Fig. 1. Interface to a generic fixed-point function approximator

× + × + × + σ 2 σ 1 a 0 a 1 a 2 a 3 Polynomial Coefficient Table x in i address α w x w -α x 3 x 2 x 3 = x p(x)
final round y Fig. 2. A polynomial evaluator (uniform segmentation, Horner scheme)

resort to complex heuristics. Several minor improvements are introduced on the way. This work is supported by an open-source implementation in the FloPoCo 1 generator [START_REF] De Dinechin | Designing custom arithmetic data paths with FloPoCo[END_REF]. Approximation and evaluation are implemented as the BasicPolyApprox and FixHornerEvaluator classes, while the FixFunctionBySimplePoly and FixFunctionByPiecewisePoly classes combine them to build architectures. The interested reader will find in their respective source code all the details not exposed here for clarity.

Unit intervals

We assume that f is continuously differentiable over a closed interval I up to a certain order. In this work, we will systematically normalize I to [0, 1] or [-1, 1]. Any function g that has a different input interval may be transformed into a function f on I = [0, 1] or I = [-1, 1] by means of a suitable change of variable. Technically, in all practical cases, there exists an affine transformation g such that g([-1, 1]) = I and g entails little or no additional hardware cost. We then consider f • g(x) on [-1, 1]. Examples will be given in the sequel.

The reason for normalizing functions to unit intervals is that it greatly simplifies the arithmetic analysis needed to build an efficient architecture. This is indeed at the core of the contributions of this article. In other words, if a function has, in its original context, a different input range (for instance [0, 2 -k ] after range reduction in [START_REF] De Dinechin | Fixed-point trigonometric functions on FPGAs[END_REF] or [START_REF] De Dinechin | Floating-point exponential functions for DSP-enabled FPGAs[END_REF]), the present work claims that rewriting it as a function on [0, 1] or [-1, 1] is relevant for a fixed-point implementation.

Fixed-point formats

Following the VHDL standard, a fixed-point format is defined by two integers (m, ) that respectively denote the position of the most significant and least significant bit (MSB and LSB) of the data. The respective values of the MSB and LSB are thus 2 m and 2 . The LSB position denotes the precision of the format. The MSB position denotes its range. Both m or can be negative if the format includes fractional bits. In signed arithmetic, m is the position of the sign bit.

For instance, on Figure 1, an input in [0, 1] is represented in the (-1, in ) format.

Error analysis for computing just right

One key idea of this work is that architectures should compute, at each step, accurately enough, but no more, if more accuracy costs hardware or latency. Formally, accuracy is achieved by bounding errors. An error, denoted ε, is always defined as the difference between two values, one being more accurate than the other. For instance, ε total = y -f (x) is the error of the computed output y with respect to the real value of the function f (x). This error should not exceed the value of the LSB of the output: ∀x ∈ I, |ε total | < 2 out . In- deed, a higher accuracy cannot be expressed on the output, while a lower accuracy would mean that some outputs bits hold no useful information. Therefore, the output precision out also serves to specify the accuracy of the implementation (Figure 1). This accuracy objective is often termed faithful rounding in the literature.

The maximal absolute value of an error ε over the interval I is noted ε, so the previous objective can also be stated as ε total < 2 out . This total error is decomposed as follows. The function f is approximated by a polynomial p, with error ε approx (x) = p(x)-f (x). The evaluation of p(x) involves rounding errors: the value actually computed by the hardware will be noted p(x). The sum of all rounding errors in the architecture is noted ε eval (x) = p(x) -p(x). As p(x) must be evaluated to an internal precision slightly higher than out , it finally needs to be rounded to the target format: ε final round = y -p(x) is the corresponding error. Thus,

ε total = y -f (x) = y -p(x) + p(x) -p(x) + p(x) -f (x) = ε final round + ε eval + ε approx (1)
Here, ε final round is actually the dominant source of error. It is, at worst, one half of the weight of the output LSB: ε final round = 2 out -1 . The constraint on the two other errors to ensure ε total < 2 out is therefore ε approx + ε eval < 2 out -1 .

To balance the errors, the polynomial approximation step is given the error budget ε target appprox = 2 out -2 . The approximation step computes the polynomial of minimum degree that allows to match this error budget. It also reports the actual ε approx . This defines the error budget for the evaluation as ε target eval = ε final round -ε approx . This value is passed to the generator of polynomial hardware, whose task is to dimension the adders and multipliers to achieve it. This process is illustrated on Figure 3.

Generic range reduction techniques

This general error analysis scheme may be adapted to most range reduction techniques. For example, the architecture of Figure 2 implements the uniform segmentation scheme [START_REF] Lee | Optimizing hardware function evaluation[END_REF], [START_REF] De Dinechin | Automatic generation of polynomial-based hardware architectures for function evaluation[END_REF]: it splits the input interval into 2 α sub-intervals of identical size (Figure 5, left). An approximation polynomial can then be used on each interval. The coefficients are stored in a table addressed by the α MSBs of the input (noted i throughout this paper). The motivation for this is that the same accuracy can be obtained with polynomials of smaller degree on the smaller intervals. Actually, in such a scheme, the degree is an input to the generator. The generator computes the smallest α that entails that the target accuracy can be reached with this degree (see Figure 4). Thus, the degree is a way of controlling the trade-off between table cost and arithmetic cost.

FixFunctionByPiecewisePoly PiecewisePolyApprox BasicPolyApprox FixHornerEvaluator FixMultAdd .vhdl f , in , out , d f , ε target appprox , d α, {pi}, εapprox fi, ε target appprox pi, εapprox,i {pi}, ε target eval {(mj, j )}

Fig. 4. Execution flow of FixFunctionByPiecewisePoly

In such a scheme, the previous error analysis simply needs to consider the worst case over the sub-intervals i: the error approximation target must be reached by all the approximation polynomials p i , each on its sub-interval; the evaluation error budget is computed out of the worst-case error over i; finally, the evaluation hardware needs to be shared among all the intervals, so its datapath must be dimensioned to fit all i. This simply consists in considering, for each fixed-point format, the max (over i) of the MSBs and the min of the LSBs. Some functions have singularities on the interval endpoints (for instance the square root depicted on Figure 5, right). They may be best implemented by power-of-two segmentation [START_REF] Lee | Hierarchical segmentation schemes for function evaluation[END_REF]. The only difference with uniform seg-

x i = 0 1 2 3 4 5 6 7 2 -α x i = 0 i = 1
Fig. 5. Uniform (left) and power-of-two (right) segmentation mentation is that the interval index is obtained by a leadingzero or leading-one counter, while the reduced argument is obtained by the corresponding shift on the input. These leading zero counters and shifters must be added to Figure 2.

Hierarchical segmentation is studied in [START_REF] Lee | Hierarchical segmentation schemes for function evaluation[END_REF]. The conclusion is that two levels always suffice in practice, with only the outer one needing power-of-two splitting.

This paper is demonstrated on the simpler uniform segmentation scheme, but the techniques presented here (in particular in Section 3) apply to all these other generic range reduction techniques, and even to function-specific range reductions [START_REF] Muller | Elementary Functions, Algorithms and Implementation[END_REF], [START_REF] De Dinechin | Fixed-point trigonometric functions on FPGAs[END_REF], [START_REF] De Dinechin | Hardware implementations of fixed-point Atan2[END_REF], [START_REF] De Dinechin | Floating-point exponential functions for DSP-enabled FPGAs[END_REF], [START_REF] Thomas | A general-purpose method for faithfully rounded floating-point function approximation in FPGAs[END_REF].

POLYNOMIAL APPROXIMATION

Textbooks [START_REF] Muller | Elementary Functions, Algorithms and Implementation[END_REF] provide many methods for approximating a function with a polynomial. Taylor or Chebyshev are wellknown analytical methods, but the best approximations are provided by Remez' algorithm, a numerical process that, under some conditions, converges to the minimax approximation: the polynomial p remez of degree d that minimizes ||p-f || ∞ . A problem is that the coefficients of p remez are real numbers that must be rounded to finite-precision machine numbers. This introduces a new error that has to be taken into account [START_REF] Lee | Optimizing hardware function evaluation[END_REF], [START_REF] Lee | Hierarchical segmentation schemes for function evaluation[END_REF]. Besides, this gives a new polynomial p remez which is in general no longer the best possible among the polynomials whose coefficients are machine numbers.

The state of the art is therefore the modified Remez algorithm [START_REF] Brisebarre | Efficient polynomial L ∞ -approximations[END_REF] available as the fpminimax command of the Sollya tool [START_REF] Chevillard | Sollya: An environment for the development of numerical codes[END_REF]. It directly provides a minimax polynomial among the polynomials whose coefficients satisfy some user-specified constraints. These constraints specify the LSB weight of each coefficient.

To define these constraints, consider a theoretical architecture evaluating the developed form of a polynomial

a 0 + a 1 x + a 2 x 2 + . . . + a d x d on I = [0, 1] or I = [-1, 1].
It would first compute each monomial a j x j , then align them to compute the fixed-point sum. Such an alignment is depicted on Figure 6 for a polynomial evaluating f (x) = e x on [0, 1] to an accuracy of 10 -6 (it is close to the Taylor series).

As |x| ≤ 1 we also have

|x j | ≤ 1, hence |a j x j | ≤ |a j |.
Therefore the MSB of each monomial term a j x j is that of a j .

Let us now discuss the LSBs to derive the constraints to input to fpminimax. There is no point in evaluating one of the monomials much more accurately than the others, as the sum will be no more accurate than its least accurate term. Besides, for x close to 1, the monomial a j x j cannot be more accurate than a j itself. A near-optimal design decision is therefore to have each a j accurate to the same LSB a . The maximal value of a may be determined out of the accuracy a a 0 1.000000000000 a 1 0.111111111100 a 2 0.100000100101 a 3 0.001001000010 a 4 0.000100011011 a 0 1.000000000000 +a 1 x 0.xxxxxxxxxxxx... +a 2 x 2 0.xxxxxxxxxxxx... +a 3 x 3 0.00xxxxxxxxxx... +a 4 x 4 0.000xxxxxxxxx... = s.ssssssssssss...

Fig. 6. If x ∈ [-1, 1],
the alignment of the a j x j follows that of the a j objective ε target appprox . Intuitively, we need 2 a ≤ ε target appprox so the coefficients hold information that is at least as accurate as ε target appprox . In practice, surprisingly, there usually exist polynomials satisfying ε approx ≤ ε target appprox even when 2 a is sligthly larger than ε target appprox . This effect improves with the degree d, therefore a good heuristic is to start by calling fpminimax with a = log 2 (ε target appprox × d) . If fpminimax fails to obtain a polynomial that satisfies ε approx < ε target appprox , then a is decreased until it succeeds. This loop (formalized in Algorithm 1) rarely needs more than a few attempts and its execution time remains well below one second. It is implemented in FloPoCo in the BasicPolyApprox class. The computation of ε approx is performed with Sollya supnorm(p, f, I) command [START_REF] Chevillard | Certified and fast computation of supremum norms of approximation errors[END_REF].

Algorithm 1 Approximation for

I = [0, 1] or I = [-1, 1] 1: procedure FIXEDPOINTPOLYAPPROX(f, d, I, ε target appprox ) 2: a ← log 2 (ε target appprox × d) -1 3: repeat 4: a ← a + 1 5: p ← fpminimax(f, d, I, { a }) 6: ε approx ← supnorm(p, f, I) 7: until ε approx ≤ ε target appprox 8: end procedure
This reasoning assumed a theoretical architecture evaluating the developed form, but it actually holds for any evaluation scheme. For instance, let us consider the classical Horner evaluation scheme, used in most previous work [START_REF] Lee | Optimizing hardware function evaluation[END_REF], [START_REF] Lee | Hierarchical segmentation schemes for function evaluation[END_REF], [START_REF] De Dinechin | Automatic generation of polynomial-based hardware architectures for function evaluation[END_REF] because it minimizes the number of operations :

p(x) = a 0 + x × (a 1 + x × (a 2 + .... + x × a d )...) . (2)
It can be expanded in the following recurrence:

       σ d = a d π j = x × σ j+1 ∀j ∈ {0 . . . d -1} σ j = a j + π j ∀j ∈ {0 . . . d -1} p(x) = σ 0 (3)
The reader may observe that, for |x| ≤ 1, having all the a j accurate to the same LSB a again entails a recurrence where no step is needlessly more accurate than the others: Algorithm 1 also works in this case. The same will be true of evaluation schemes intermediate between Horner and the developed form, such as Estrin's [START_REF] Muller | Elementary Functions, Algorithms and Implementation[END_REF].

ARGUMENT RANGE REDUCTION

The analysis of the previous section is based on the fact that the function input range is normalized to [0,1] or [-1,1]. But the purpose of argument range reduction is, as the name suggest, to reduce this interval. For instance, the architecture of Figure 2 actually evaluates f (x in ) on small sub-intervals, e.g. x in ∈ [0, 2 -α ], enabling smaller-degree polynomial than on the full interval.

Let us define the change of variable [START_REF] Cheung | Hardware generation of arbitrary random number distributions from uniform distributions via the inversion method[END_REF]. Note that it translates both the MSB and the LSB of x in by α positions. Applied to an approximation polynomial, this change of variables gives

x in = 2 -α x, such that f (x in ) = f (2 -α x) = g(x) for x ∈ [0,
p f (x in ) = a 0 + a 1 x in + a 2 x in 2 . . . = a 0 + 2 -α a 1 x + 2 -2α a 2 x 2 . . . = p g (x)
. In other words, range reduction can also be viewed as a reduction of the polynomial coefficients, here by a factor 2 jα for the coefficient of degree j. This is illustrated by Figure 7 on a few examples extracted from uniform piecewise approximations to exp and log. Having normalized the function to a unit interval then enables the use of Algorithm 1.

As a parenthesis, Figure 7 also gives a visual clue how the degree is determined by the target accuracy. Indeed, on Figures 7b/ and 7c/, a 4-th degree coefficient a 4 would be to the right of the picture, contributing no useful bits. However, this is only true if all the coefficients have the same sign, as Figure 7d/ illustrates. In the general case, the Sollya command guessdegree(f, I, ε target appprox ) provides a good estimate of the degree needed to reach a given accuracy.

In [START_REF] Lee | Optimizing hardware function evaluation[END_REF], [START_REF] Lee | Hierarchical segmentation schemes for function evaluation[END_REF], or [START_REF] De Dinechin | Automatic generation of polynomial-based hardware architectures for function evaluation[END_REF], the change of variable used is

x in = 2 -α (i + x) for x ∈ [0, 1) and i ∈ {0, 1 . . . 2 α -1}. The normalised i-th function is f u i (x) = f (2 -α (i + x)).
The reduced argument x is obtained as the LSBs of x in in the case of uniform segmentation (Figure 2), as a shift of x in in the case of power-of-two segmentation.

One novelty of the present work is to center x on its sub-interval: we introduce the change of variable

x in = 2 -α (i+ 1 2 + x 2 ) for x ∈ [-1, 1). The normalised i-th function becomes f s i (x ) = f (2 -α (i + 1 2 + x 2 )).
In general, this leads to smaller coefficients for the approximation polynomials, as illustrated by Figure 7c/ versus 7b/. The architectural overhead to obtain x out of x is limited to one inverter (not shown on Figure 2 for simplicity) to complement the MSB of x. Its delay is largely hidden by the table access delay.

Another remark can be made about the sign of the coefficients: analytical properties of the function (monotinicity, convexity, and so on) are defined by the signs of the successive derivatives. Good approximation polynomials typically inherit these properties, which are then often reflected in the signs of the corresponding coefficients. For instance, on Figure 7, all the coefficients for the various exponentials are positive. As a consequence, for a piecewise approximation of an elementary function, it is typical (but not automatic due to numerical artifacts) that all the coefficients of a given degree have the same sign. In this case, the sign bit need not be stored, saving one bit per coefficient.

POLYNOMIAL EVALUATION

This section discusses the sizing of all variables on the Horner evaluator of Figure 2. As for evaluation, it can be straightforwardly extended to other schemes. . Consider one Horner step of (3). As the a j are known, it is possible to compute the ranges of the π j and σ j , hence their MSBs, by straightforward interval evaluation of (3) on [-1, 1]. This is implemented in a procedure COMPUTE-HORNERMSBS. In the typical scenario where x is a reduced argument, a j is larger in magnitude than π j , therefore the MSB of σ j will be that of a j , sometimes plus one (overflow bit to the left). This is the case depicted on Figure 8. However it may also happen that a j is smaller in magnitude than π j .

Concerning the LSBs, we have two opportunities of reducing the size of intermediate computations. Firstly, the product π j may be rounded or truncated at each step, a/ f (x) = exp(x) on [0, 1] a 0 = 1.0000000000000000000 a 1 = 0.1111111111111111100 a 2 = 0.1000000000001000011 a 3 = 0.0010101001111100010 a 4 = 0.0000101100011110111 a 5 = 0.0000000110010100000 a 6 = 0.0000000010101010011 b/ f u 10 (x) = exp( 10 16 + 2 -4 x) on [0, 1] a 0 = 11.101111001000101011 a 1 = 00.001110111100100010 a 2 = 00.000000011101111011 a 3 = 00.000000000000100111 c/ f s 10 (x) = exp( 10.5 16 + 2 -5 x) on [-1, 1] a 0 = 11.110110101110100000 a 1 = 00.000111101101011101 a 2 = 000.00000000111101101 a 3 = 000.00000000000000101 d/ log(1 + 10. 5 16 + 2 -5 x) on [-1, 1] a 0 = 0100000010010101010011 a 1 = 0.00001001101010010100 a 2 = 1111111111111010001010 Fig. 7. Range reduction reduces the a j . All the polynomials are accurate to 10 -6 ; f u 10 and f s 10 cover the same sub-interval of exp(x).

entailing an error bounded by ε π (j). Secondly, x may also be truncated to reduce the multiplier size (informally, to remove bits of x that the multiplication by σ j+1 will shift so far right that they don't affect the result -the formal formulation follows). This truncation of x was a contribution of [START_REF] De Dinechin | Automatic generation of polynomial-based hardware architectures for function evaluation[END_REF].

The recurrence that is actually computed is thus:

       σ d = a d π j = x j × σ j+1 + ε π (j) ∀j ∈ {0 . . . d -1} σ j = a j + π j ∀j ∈ {0 . . . d -1} p(x) = σ 0
Remark that the addition is exact, since it is a fixed-point addition.

The evaluation error of step j can now be defined as:

ε eval (j) = σ j -σ j = (a j + π j ) -(a j + π j ) = π j -π j = π j -x j σ j+1 + x j σ j+1 -x j σ j+1 = ε π (j) + x j σ j+1 -x j σ j+1 + x j σ j+1 -x j σ j+1 = ε π (j) + ( x j -x j ) σ j+1 + x j ε eval (j + 1) . (4) Algorithm 2 computes all the MSBs and LSBs of the Horner datapath of Figure 2 according to (4). It is a loop again: it computes ε eval = ε eval (0), and adds more LSB bits if this error exceeds the target. Again, the argument that no step needs to be more accurate than the others drives us to have a common LSB σ . It will be the LSB of all the σ j but also of the π j (see Figure 8). As σ j = a j + π j , σ j must be at least as accurate as a j , otherwise bits of a j would be useless. Therefore, line 3 of Algorithm 2 initializes σ to a .

Let us now address the truncation of x. If x j has the LSB x,j , we have | x j -x j | < 2 x,j , and the term ( x jx j ) σ j+1 can be bounded as | σ j+1 ( x j -x j )| ≤ 2 mσ,j+1 • 2 x,j where m σ,j+1 is the MSB of σ j+1 . Balancing this error term and ε π (j) yields 2 mσ,j+1 • 2 x,j = 2 σ . This defines x,j = a σ a j aaaaaaaaaaaa 1 +π j pppppppppppppppppppp = σ j ssssssssssssssss rounding bit Fig. 8. Fixed-point alignment of one Horner step σ -m σ,j+1 . In practice, it is a truncation only if x,j < x . Otherwise, x is not truncated and this first error term is zero. In the typical case where the MSB of a j (hence σ j ) grows as j decreases (Figure 6), truncation of x happens in the earlier Horner steps.

A word now on the truncation of the product. If the hardware (for instance a fixed-size FPGA DSP block) computes the full product x j σ j+1 , rounding it to π j is almost for free: it can be achieved by extending the addition a j + π j one bit on the right to add a constant bit before truncation to σ (Figure 8). In this case ε π = 2 σ -1 . Otherwise, a cheaper alternative is to use an ad-hoc FixMultAdd operator which combines a faithful truncated multplier and an adder in a single compression tree. In this case ε π = 2 σ . Algorithm 2 Determining Horner evaluator parameters

for i = d -1 down to 0 do 7: x,j ← max( x , σ -m σ,j+1 ) 8: if x,j = x then if x truncated 9:
ε eval = ε eval + ε x add its error

RESULTS AND CONCLUSION

The techniques described in this article lead to consistently improved architectures with respect to those previously published. Table 1 shows typical improvements of coefficient sizes and multiplier sizes with respect to the previous state of the art: FloPoCo 2.3.1, which was used to write [START_REF] De Dinechin | Automatic generation of polynomial-based hardware architectures for function evaluation[END_REF]. All the architectures reported there were tested for last-bit accuracy thanks to the FloPoCo test framework [START_REF] De Dinechin | Designing custom arithmetic data paths with FloPoCo[END_REF].

However the main contribution of this work is a much simpler view of the problem, thanks to normalization to unit intervals and systematic balancing of errors. This lead to much cleaner and more robust open-source code. This is a solid foundation on which to explore other range reductions [START_REF] Lee | Hierarchical segmentation schemes for function evaluation[END_REF], other evaluation schemes [START_REF] Muller | Elementary Functions, Algorithms and Implementation[END_REF], [START_REF] Detrey | Table-based polynomials for fast hardware function evaluation[END_REF], and FPGA-specific optimizations based on fixed-size memory and DSP blocks. Also, we have used the phrase "near optimal" in the introduction: it is usually still possible to shave one more bit here and there by relaxing the constraint that all the degrees share the same LSB. Is it worth the increased code complexity?

Fig. 3 .

 3 Fig. 3. Execution flow of a basic polynomial approximator

1 :

 1 procedure HORNERSIZING( x , {m a,j }, a , ε

TABLE 1

 1 The proposed method leads to smaller data paths.(x) = log(1 + x), in = out = -23, d = 2 (x) = log(1 + x), in = out = -52, d = 4

	Version f (x) = 0.5	√	Table 1 + x, in = out = -23, d = 2	Multipliers
	2.3.1		256×(27+19+10)		16×20, 16×10
	Present f (x) = 0.5	√	64×(26+17+9) 1 + x, in = out = -52, d = 4	17×18, 10×10
	2.3.1	256×(56+46+36+28+19)	44×49, 35×37, 25×29, 25×19
	Present	256×(56+44+33+23+14)	44×47, 36×36, 26×26, 15×15
	2.3.1		256×(27+21+13)		16×22, 16×13
	Present		128×(26+18+9)		16×20, 10×10
	2.3.1	512×(56+49+40+32+23)	44×50, 44×41, 35×33, 25×23
	Present	512×(56+46+35+24+14)	43×48, 37×37, 26×26, 15×15

f f

Acknowledgments to the Sollya team (N. Brisebarre, S. Chevillard, M. Joldes, Ch. Lauter), and to D. Thomas and J.M. Muller for discussions on this subject. This work was supported by the ANR INS MetaLibm project.


Gil Francopoulo
email: gil.francopoulo@wanadoo.fr

Thierry Declerck
email: declerck@dfki.de

Monica Monachini
email: monica.monachini@ilc.cnr.it

Laurent Romary
email: laurent.romary@loria.fr

The relevance of standards for research infrastructures

In this paper, we show the importance of standards as an essential aspect for any research infrastructure in the humanities. In the context of the current activities within ISO committee TC 37/SC 4 (Language Resource Management), we show in particular how important it is to provide means to compare linguistic representations through the use of a shared semantics for elementary descriptors. This is further exemplified by describing the ongoing work to define a central data category registry, which aims at being a reference point in the language resource community, in conjunction to the definition of basic standards for linguistic annotation, as illustrated with the current work that is being carried out in the domain of morpho-syntactic categories.

1.

2.

Standards: are they at all needed ?

For many years, the language resource community has been the place of numerous projects [see Cole] that have aimed to produce resources and tools to facilitate the study or automatic processing of language. Still, we have all faced the issue of ensuring long-term availability of the corresponding results, with the consequence that researchers still have to carry out technical tasks of corpus gathering, lexical description or tool implementation that others are supposed to have achieved beforehand, and above all that should be the duty of shared research infrastructures working for the benefit of all.

One of the key issues to define such research infrastructures is our ability, as a mature scientific community, to be able to identify that new research results should be based upon the stabilization of shared knowledge by means of a range of internationally agreed upon standards. Such standards would obviously bring the following benefits:

• Ensure wide accessibility of data in space (between research sites) and time (in the perspective of providing long-term preservation of data).

Standards are there to provide a stable representational basis as well as maintained documentation, that researchers are not able to produce on their own; • Facilitate the reusability of software by making it independent from the actual proprietary data formats an implementer might use; • Guaranty that research results are comparable, by, for instance, making sure that the same underlying data has been used in the context of the elicitation of statistical results; • Create communities of practice that will share the knowledge of such standards and create new concepts on the basis of this common culture. As a matter of fact such benefits have already been observed in the context of the wide deployment of the Text Encoding Initiative guidelines, which have both been the basis of numerous projects worldwide1 , but also have been the basis of a shared understanding of basic textual descriptions that now leads to the explorations of new textual types or phenomena2 .

Still, the language resource community requires even more standards to cope with both the variety of linguistic phenomena that have to be taken into account as well as the diversity of human languages. This is why, a the International Organization for Standardization3 has put together a new committee dedicated to language resources, known as ISO/TC 37/SC 4 and started to foster several standardization projects to deal with what has been identified as priorities for the progress of the management of language resources.

In the remaining sections, we first provide a few elements related to the role we think research infrastructures should play with regards standards. We then outline the working agenda of ISO/TC 37/SC 4 and we present our opinion concerning standards when applied to Research Infrastructure (RI). Then, as an illustration, we present the work in progress within ISO-TC37/SC4 on the morpho-syntactic profile of the data category registry (DCR).

Research infrastructures and standards

As we have seen, standards are an essential component of any language resource related activity. In this context research infrastructures should consider standardization as one essential point of their activities. More precisely we consider that at least the three following missions should be allocated to research infrastructures:

• They should contribute the wide dissemination of standards by initiating training sessions and providing teaching materials and samples on line;

• They should actually implement available standards in all their activities, with the constant objective of long-term availability of the data or tools they produce (see above); • They should be at the forefront of standardization activities by explicitly reviewing existing standards, contribute to their evolution and even participate to the definition of new standards when needed by the corresponding research community.

3.

4.

5.

6.

6.1.

6.2.

6.3.

7.

Work in progress within ISO-TC37

ISO committee TC 37/SC 4 is dedicated to the specification of a full family of standards for NLP and language resources. These standards can be categorized according to two levels:

Low level standards, describing the linguistic constants. More precisely, this is a pair: a) revision of ISO-12620 that specifies the rules for describing and maintaining data categories.

b) data category registry There are also some other important low-level standards that we can use: the standards for character encoding (ISO/IEC 10646 i.e. Unicode), language codes (ISO-639), script codes (ISO-15924), country codes (ISO-3166) and dates (ISO-8601).

High level standards, describing structural models (sometimes called meta-models) that specify how to represent linguistic resources. The structural model provides classes (in UML terminology) and the relations between classes together with a textual usage description for each class.

The registry provides the needed attributes and values that are used to adorn the classes. The structural models being currently developed deal with wordsegmentation, morpho-syntactic annotation (aka MAF), syntactic annotation (aka SynAF) [Declerck] and lexicon (aka LMF) [Francopoulo].

Objective

The objective is to propose to the user and developer of language resources a coherent family of standards. All these standards have the following property: they allow the definition of a model of linguistic resource by combining structural elements with constants taken in low-level standards. All the resources share thus the same set of constants, supporting our goal of providing interoperability between segmentation, annotation and lexicon.

Roadmap

As said before, the duration for defining an ISO standard is rather long. It takes around four years. So, instead of defining low-level standards then high level standards (or the contrary), the various ISO groups works in parallel with a closed collaboration between them.

Some basic definitions A data category

A data category is a linguistic constant. A data category is either an attribute name like /partOfSpeech/ or a value dedicated to populate an attribute. An example of value is /noun/.

Profiles

A profile is a specific set of data categories in the DCR. The current profiles are:

For Terminology within TC37/SC3 One profile For NLP within TC37/SC4

Three profiles: Meta-data Morpho-syntax Semantics You can notice that to ensure interoperability in NLP between word-segmentation, annotation and lexicon, the distinction between each profile is made according to linguistic criteria and not according to the resources. Another point to mention, is that a data category may belong to several profiles but we try to avoid this situation in order to avoid conflicts.

The data category registry

The registry is the union of all data categories.

Morpho-syntactic profile

The DCR structure is specified by the ISO-12620 revision. In the morpho-syntactic profile we restrict ourselves for the time being to the following features: We differentiate between the notion of /broader/ relation and the notion of /conceptual domain/.

The /broader/ link allows a hierarchy of constants to be defined. Example: a common noun is a more specialized value than noun.

: DataCategory commonNoun : DataCategory noun hasABroaderDataCategory

The notion of conceptual domain allows a set of valid values to be identified. Example: noun is a value for partOfSpeech.

9.

What has been done in the morphosyntactic profile?

We proceeded in three phases: Phase-1: collect Phase-2: group, structure and write a first draft of the definitions Phase-3: revise An initial long and flat list of data categories has been collected from:

• Current ISO-12620

• Eagles and Multext-East

• A couple of values for the NLP sections in LMF The ISO-12620 constants are general purpose values like /language/ or /derivation/ and cover only terminological resources. For instance, for /partOfSpeech/, the only values are /noun/, /adjective/ and /verb/.

By comparison, in NLP, we need much more values including /preposition/ and /pronoun/ etc.

We propose a set of constants according to the following criteria:

• broad linguistic coverage within the morpho-syntactic perimeter • no semantic overlap • good choice of a name associated with a good textual definition

What has been recorded so far in the DCR?

The list being rather huge we created 11 directories within the Syntax software (see next section) in order to help data category organization. It easier to work on medium sized list than on a list with 300 items.

In each directory: one or several attributes names and related values are recorded.

Software

We use the Syntax software hosted by CNRS-INIST in Nancy (see http://syntax.inist.fr) in order to edit the data categories. This is a server based on a relational database with a set of PHP programs in order to manage the interaction. Here is a screen dump: 11. 12.

13.

APIs

In order to allow programs to access to the DCR, a set of Application Programming Interfaces are being specified and implemented by Max Planck Institute for Psycholinguistics of Nijmegen, INRIA-Loria and University of Sheffield.

  speech values are structured with a top level set composed of 10 values like noun or verb. A very precise ontology is specified for grammatical words. Most of parts of speech are common to lexicons and annotations but two set of values (i.e. punctuation and residual) are specific to annotation and are not usually used in lexical descriptions. Reference 5 The constants are anaphora, antecedent, cataphora, coreference, endophora and referent. This is some doubt to maintain these constants in the morpho-syntactic profile. Register, dating and frequency 19 The constants are slangRegister or rarelyUsed. Semantically motivated 16 The constants are agent, intensive. This is some doubt to maintain these constants in the morphosyntactic profile. Syntactically motivated 36 Attributes are function or voice. Values are subject, activeVoice for instance.

	Basics	29 items
	These are general purpose linguistic constants, like: comment, derivation, elision, foreignText, label.
	Cases	33
	Examples of values: ablativeCase or dativeCase.
	FormRelated	33
	These are constantes for the specifications of forms like: spokenForm, writtenForm, abbreviation,
	expansionVariation, transliteration, romanization, transcription, script.
	Language Typology	4
	An attribute is languageTypology and values are agglutinating, inflectional and isolating.
	Morphological Features excluding cases	72
	Attributes are for instance grammaticalGender, mood and tense. Values are for instance feminine,
	indicative, present.
	Operations	8
	The constants are for instance addAfter, addBefore, copy etc.
	Part of speech	93
	The part of Total	348 items

See the TEI projects page under http://www.teic.org/Applications/

2 See the P5 edition of the guidelines: http://www.teic.org

/P5/ 3 http://www.iso.org

http://lirics.loria.fr

http://www.technolangue.net

Acknowledgements

The work presented here is partially funded by the EU eContent-22236 LIRICS project 4 , and by the French TECHNOLANGUE program 5 .