Fausto Galetto
email: fausto.galetto@gmail.com

Independent Researcher

Proof of Syracuse_Collatz Conjecture by Flow Graphs

Keywords: Quality Methods, Numerical Methods, Hailstone Conjecture, SPQR

In a previous paper we provided a probabilistic proof of the Conjecture and then, in another paper, we analysed two probabilistic methods for the proof comparing them by the Reliability Integral Theory and the SPQR Principle. Now we show a proof (non-probabilistic) using Flow Graphs and the SPQR Principle.

Introduction

In a previous paper [START_REF] Galetto | Proof of the Syracuse_Collatz Conjecture[END_REF] we provided a probabilistic proof of the Conjecture; later, after we saw the interesting paper [START_REF] Carletti | Quantifying the degree of average contraction of Collatz orbits[END_REF]; both the papers tried to prove the Hailstone Conjecture using Markov processes. In another paper [START_REF] Galetto | Syracuse_Collatz Conjecture: Comparison of two Markov approaches towards the proof[END_REF], we compared the two probabilistic methods using the Reliability Integral Theory [START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF][START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF] and the SPQR Principle [START_REF] Galetto | The SPQR («Semper Paratus ad Qualitatem et Rationem[END_REF]. Any probabilistic method makes "probable" the proof, but it is not really a mathematical proof. To overcome such a drawback now we provide show a non-probabilistic proof using Flow Graphs and the SPQR Principle. A graph G is an orders couple G=(V, E) of two sets of items: V the set of "vertices" v k (1km) and the set E of "edges" e j (1jn). Any edge connects two vertices, say v s and v t , by an arrow from one vertex v s (1sm) to the other vertex v t (1tm) and it is indicated with the symbol e z =(v s ,v t ) [the ordered couple of the two vertices]. If the two vertices are actually one vertex the arrow leaves the vertex and re-enter into it. Let's remember the Syracuse_Collatz problem (also called the 3x+1 mapping, hailstone problem, ..). It was posed by L. Collatz in 1937, states that the system of the two difference equations, involving natural numbers, [START_REF] Carletti | Quantifying the degree of average contraction of Collatz orbits[END_REF] given the initial condition y 0 (any integer positive number) arrives after some (n is a number not known in advance) "continued" iterations to the value y n =1. It is considered a very difficult problem to be solved, in spite of its very simple definition; they say that Erdős commented that "mathematics is not yet ready for such problems". If we name "state of the system" the integer positive number generated by (1), we see that the problem is transformed into the following:

given any initial state y 0 the system makes a certain number n of transitions (n is a number not known in advance) and finally it ends into the state y n =1. Any state of the system is a vertex in the graph. The rules [START_REF] Carletti | Quantifying the degree of average contraction of Collatz orbits[END_REF] give the next state of the system i.e. the next vertex in the graph: the edge traversed at time k+1 which we name e k+1 is (y k , y k+1 ).

Numerical experiments confirmed the validity of the conjecture for extraordinarily large values of the starting integer y 0 : it always reached 1 for all numbers up to 5.48 10 18 . (Oliveira e Silva 2008)

The system (1) can be reduced to a non-linear difference equation, as the following one [START_REF] Galetto | Proof of the Syracuse_Collatz Conjecture[END_REF] The numbers y k+1 of the sequence [the state of the system] provided by the previous (Collatz) equations are sometimes named hailstone numbers. We can associate to any state of the system y k of the edge e k+1 =(y k , y k+1 ) traversed at time k+1 the index of the row of a matrix P and to state y k+1 the index of the column of the same matrix P; then we can describe the graph by the matrix P with entries 1 related to the arrow of the transition y k y k+1 for any edge e k+1 =(y k , y k+1 ). Then for any state of the system y k there is an infinite dimensional row vector u(k), with all entries u i (k)=0, but one entry u y (k)=1, related to the edge e k+1 =(y k , y k+1 ): it is a unit vector of vector space. The vector u(k) refers to the k-th iteration of a mapping T: the result of the mapping T to the vector u(k) is denoted u(k+1)=u(k)T. The vector u(k+1) is unit vector with all entries u j (k+1)=0, but one entry u y* (k+1)=1, where we have the subindexes y*y. The subindexes are according to (1): if u y (k)=1, then y=y k and the index y* of entry u y* (k+1)=1 of the vector u(k+1) has index y*=y k /2 IF y k is even, and y*=3y k +1 IF y k is odd. The mapping T [related to the graph G] is provided by an infinite-dimensional matrix P=[a ij ], named transition matrix (with infinite rows and columns); rows and columns are indexed by the natural numbers (states of the system) 1, 2, 3, 4, ..., n, n+1, ...; every a ij entry is 0, except ........ [START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF] where the indexes i and j are given by ( 1), for the arrows e k+1 =(y k , y k+1 ). Accordingly we have u(k+1)=u(k)P (4) In the figure 1 we show the transition matrix; the 3 by 3 matrix with rows and columns indexed by the numbers 1, 2, 4, is highlighted due to its importance:  when the system is in the state 1, the next transition is to state 4: 1  4  when the system is in the state 2, the next transition is to state 1: 2  1  when the system is in the state 4, the next transition is to state 2: 4  2 All this means that when the system enters one of those 3 states [START_REF] Carletti | Quantifying the degree of average contraction of Collatz orbits[END_REF][START_REF] Galetto | Proof of the Syracuse_Collatz Conjecture[END_REF][START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF] it never leaves out of them, the system (or the process) circulates in the set [START_REF] Carletti | Quantifying the degree of average contraction of Collatz orbits[END_REF][START_REF] Galetto | Proof of the Syracuse_Collatz Conjecture[END_REF][START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF] forever. It is a "periodic process".

The matrix P can be partitioned into 4 submatrices, written simply as where P11 and P22 are square matrices, given more explicitly by (notice that P11 refers to the states 1, 2, 4)

Notice that the submatrix P 11 is orthogonal: its inverse is its transpose = . It is important to notice that P 3 , the 3 rd power of the matrix P, is such that the submatrix [START_REF] Galetto | The SPQR («Semper Paratus ad Qualitatem et Rationem[END_REF] is the identity matrix; when the system reaches the set 1, 2, 4 of the states it remains there forever. It follows that = = .

state 1 2 4 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ……………………………… 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… 4 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… 3 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 ……………………………… 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 ……………………………… 6 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… 8 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… 10 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… 12 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… 14 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… 16 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… 18 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 ……………………………… 19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… 20 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 ……………………………… … 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… … 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 ……………………………… … 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… … 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 ……………………………… … 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… … 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 ……………………………… … 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… … 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 ……………………………… … 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… … 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 ……………………………… … 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……………………………… … 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 ……………………………… Figure 1. The transition matrix P [only a part is shown], related to the graph G

Generating function (z-transform) and graphs

Let's consider a function f(n), n=0, 1, 2, ….., . The generating function F(z), written as G[f(n)]=F(z), is the complex function given by

( ) = ( )
where z is the complex variable z=x+iy. [actually in some documents one finds that z n is z -n ]. For a finite sequence it is the "characteristic polynomial" of the equation f

(k)+f(k-1)+….+ f(1)+f(0)=0 One important property of F(z) is that G[f(n-k)]= z k F(z).
We can apply the z-transform to the graph of the Siracuse_Collatz sequence; we name n=0 the "starting time point" of the sequence which has y(0), a chosen integer number N, as the state of the system: let be y(0)=N; the initial state is related to the infinite row vector u N (0) of the matrix P. Since, according to (4), u(k+1)=u(k)P, we can find the generating transform [START_REF] Galetto | The SPQR («Semper Paratus ad Qualitatem et Rationem[END_REF] of the sequence y k (of the hailstone numbers). From ( 5) we derive [START_REF] Galetto | Syracuse_Collatz Conjecture: Comparison of two Markov approaches towards the proof[END_REF] We consider two superstates A and B of our system:  A comprises the states 1, 2, 4  B comprises all the other states 3, 5, 6, …… For such a "process" we can draw the diagram (figure 2), where the submatrices are the ones given before From figure 2 we can draw the flow graph, with the z-transform, of the process (figure 3)

The flow graph solution

Let (z) the transform of the functional relationship (4). Let name the function  i,j (z) the transmission from the state i and the state j. For example, if i=5 and j=23, the transmission  5,23 (z) represent the infinite vector (sequence) of values  5,23 (0),  5,23 (1), …,  5,23 (n), …,  5,23 ()=0, 0, …, 0, …., 0, where we cannot tell if there can be a value 1 in the sequence; if i=5 and j=16, we know that  5,16 (0)=1 [see the matrix P], which means that the states 5 and 16 are connected at step 0; are they connected at some other step? We can partition the matrix (z)=[ i,j (z)] according the flow graph of figure 3

where  A,A (z) is the transmission between the various states in the set A,  A,B (z) is the transmission from the various states of the set A to the set B,  B,A (z) is the transmission from the various states of the set B to the set A and  B,B (z) is the transmission between the various states z in the set B.

Let now consider the transmissions  i,j (z) with iB and jB; they collectively provide all the transitions of the Collatz process before entering the Collatz cycle A= [START_REF] Carletti | Quantifying the degree of average contraction of Collatz orbits[END_REF][START_REF] Galetto | Proof of the Syracuse_Collatz Conjecture[END_REF][START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF] where it stays forever ("periodic process").

We consider the following flow graph

Looking at the matrix P and its partition, it is clear that ,

which means  red,green (0),  red,green [START_REF] Carletti | Quantifying the degree of average contraction of Collatz orbits[END_REF], …,  red,green (n), …,  red,green ()=0, 0, …, 0, …., 0 (10) unless, at step 0, the states red and green are chosen to satisfy It follows that the process [Collatz] is such that it cannot stay in the set B forever. Therefore it enters, at some step, the Collatz cycle A= [START_REF] Carletti | Quantifying the degree of average contraction of Collatz orbits[END_REF][START_REF] Galetto | Proof of the Syracuse_Collatz Conjecture[END_REF][START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF] ("periodic process"), where it stays forever. This is the "almost the same" result we found in the paper [START_REF] Galetto | Proof of the Syracuse_Collatz Conjecture[END_REF]; the only difference is that there we used the Stochastic Processes Theory, given in the books [START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF][START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF] The process is probabilistically bound to enter the set S 1 =1, 2, 4 because the rectangular submatrix in the lower left corner has only one 1 entry [the other entries are all 0]. The "periodic process" circulating in the set S 1 =1, 2, 4 is ruled by the submatrix P 11 . The infinite set S 2 =3, 5, 6, 7, …. comprises all the other states. The transitions are given in figure 5. In this paper, on the contrary without using any probability argument, we found that the process [Collatz] is such that it cannot stay in the set B forever and it enters, at some step, the Collatz cycle A= [START_REF] Carletti | Quantifying the degree of average contraction of Collatz orbits[END_REF][START_REF] Galetto | Proof of the Syracuse_Collatz Conjecture[END_REF][START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF] ("periodic process"), where it stays forever.

Conclusion

Having applied the SPQR («Semper Paratus ad Qualitatem et Rationem») Principle, the author thinks that his non_probabilistic method is able to show the proof of the Syracuse_Collatz Conjecture [he did probabilistically in a previous paper]. Flow graph theory provided us the means to solve the problem.

Figure 2 .

 2 Figure 2. The transition diagram related to the graph G

Figure 3 .

 3 Figure 3. The flow graph (z-transform) related to the graph G

Figure 4 .

 4 Figure 4. The flow graph when we consider the transmissions from the read state to the green state, both in the same set B

z

  Notice that S 1 is the superstate A and S 1 is the superstate B. Compare the figure 2 with figure5.

Figure 5 .

 5 Figure 5. The two disjoint sets S 1 and S 2

  related to Reliability Integral Theory[RIT]; using it one can find two vectors z 1 and z 2 defined, as follows,  z 1 is the vector of the (steady state) probabilities of entering into one of the states 1, 2, 4 [S 1 ], when there is a transition S 2 =3, 5, 6, ..., n, n+1, ....  S 1 =1, 2, 4.  z 2 is the vector of the (steady state) probabilities of entering into one of the states 3, 5, 6, ..., n, n+1, .... [S 2 ], when there is a transition from S 1 =1, 2, 4  S 2 =3, 5, 6, ..., n, n+1, ..... z 1 is by definition a three-dimensional row vector [0, 0, 1] related to the set S 1 ; see the figure2.The system enters into the set S 1 only through the state 4.


Yu Li

A class of cutoff functions for non-trivial Riemann zeros

Keywords: Riemann hypothesis, non-trivial Riemann zero, Pseudo hermitian operator, Berry-Keating operator

In this paper we construct a pseudo ermitian operator H on the Hilbert space L 2 [ 1 2 , 1] and show that the Hurwitz zeta functions over the interval [ 1 2 , 1] are eigenfunctions of H for all complex numbers.

Introduction

One of the most attracting problems in Mathematics is Riemann hypothesis and it states that all the non-trivial zeros of Riemann zeta function

ζ(s) = n≥1 1 n s = 1 Γ(s) ∞ 0 t s-1 e t -1 dt
have the real part 1 2 . One proposed way of proving Riemann hypothesis, known as Hilbert-Pólya conjecture, is to find an unbounded self-adjoint operator such that the imaginary part of Riemann zeros corresponds to the eigenvalues of this operator. It has been suggested [START_REF] Berry | H = XP and the Riemann zeros[END_REF] that the possible approach to solve Hilbert-Póplya conjecture lies in a quantization of the classical Hamiltonian H = XP , where P is the canonical momentum operator associated with position operator X. Inspired of the previous works, an operator H similar to quantum analogy was proposed [START_REF] Bender | Hamiltonian for the Zeros of the Riemann Zeta Function[END_REF] and asymptotic analysis was performed [START_REF] Bender | Asymptotic analysis on a pseudo-Hermitian Riemann-zeta Hamiltonian[END_REF]. However, the momentum operator P in this case has no self-adjoint extension [START_REF] Belissard | Comment on "Hamiltonian for the Zeros of the Riemann Zeta Function[END_REF].

Hurwitz Zeta functions

The Hurwitz zeta function is originally defined for complex arguments s with R(s) > 1 and x > 0 by

ζ(s, x) = n≥0 1 (n + x) s
Hurwitz zeta function has an analytic continuation on C with the only singularity s = 1 and it can be represented [START_REF] Bailey | Experimental Mathematics in Action[END_REF][START_REF] Olver | NIST Handbook of Mathematical Functions Paperback and CD-ROM[END_REF]

ζ(s, x) = - Γ(1 -s) 2πi C ξ s-1 e xξ e ξ -1 dξ, s = 1 ( 1
)
where C is the contour around the negative real axis and it starts at -∞, encircles the origin once in the positive direction without enclosing any of the points ξ = ±2ni, ±4ni, ... and returns to -∞ [START_REF] Olver | NIST Handbook of Mathematical Functions Paperback and CD-ROM[END_REF]. The famous Riemann zeta function is the special case of Hurwitz zeta function with

x = 1 ζ(s, 1) = ζ(s)
and also with

x = 1 2 ζ(s, 1 2 ) = (2 s -1)ζ(s) (2)
The partial derivative of Hurwitz zeta function with respect to

x ∂ζ(s, x) ∂x = -sζ(s + 1, x), s = 0, 1; x > 0 (3)
Let s denote a point in critical strip 0 < R(s) < 1 and we define a cutoff function

ζ s of Hurwitz function on interval [ 1 2 , 1] ζ s (x) := ζ(s, x), 1 2 ≤ x ≤ 1 (4)
The functions ζ s is continuous and even smooth on the closed interval [

ζ z ( 1 2 ) = 0 3 Operators in Hilbert space L 2 [ 1 2 , 1]
We confine our discussion over the region [ 1 2 , 1]. Let X be the position operator on L 2 [ 1 2 , 1] and P 0 the momentum operator P 0 = -i d dx densely defined on L 2 [ 1 2 , 1] with domain

D(P 0 ) = f ∈ C ∞ [ 1 2 , 1] : f ( 1 2 ) = f (1) (5)
[6] and it has a unique self-adjoint extension P 0 = P . The closure of the graph of P 0 is the graph of P

Γ(P ) = Γ(P 0 ) = L 2 [ 1 2 , 1] × L 2 [ 1 2 , 1]
From the Stone's theorem on one-parameter unitary groups, e itP t is a strongly continuous one-parameter group of unitary operators on L 2 [ 1 2 , 1]. Thus, both operators e ±iP -I are bijective and bounded, and then the bounded inverses (e ±iP -I) -1 exist, from the bounded inverse theorem in functional analysis.

We construct an operator H on

L 2 [ 1 2 , 1]
H = e iP -I -1 (XP + P X) e iP -I It holds obviously for 1 2 ≤ x ≤ 1 and 0 < R(s) < 1

(XP + P X)x -s = i(2s -1)x -s (6)
The operator H is pseudo hermitian [START_REF] Mackey | Commutative Banach Algebras[END_REF][START_REF] Mostafazadeh | Pseudo-Hermiticity versus PT symmetry: The necessary condition for the reality of the spectrum of a non-Hermitian Hamiltonian[END_REF][START_REF] Mostafazadeh | Pseudo-supersymmetric quantum mechanics and isospectral pseudo-Hermitian Hamiltonians[END_REF], i.e. there exists an invertible and selfadjoint operator η such that the adjoint operator H † can be represented

H † = η Hη -1 Proposition 3.1.
H is pseudo hermitian and all eigenvalues are real.

Proof. Let η = (e iP -I) † (e iP -I) and it is obviously self-adjoint, then

H † = η Hη -1
The operator η is positive definite and self-adjoint by construction, the operator H is hermitian in the new inner product with respect to η

Hφ, ϕ η = Hφ, ηϕ = φ, η Hη -1 ηϕ = φ, Hϕ η , φ, ϕ ∈ L 2 [ 1 2 , 1]
Then all eigenvalues of H are real.

Proposition 3.2. For any complex number z, the function

ζ z (x) -ζ z ( 1 2 ) is an eigen- function of H with eigenvalue i(2z -1) H ζ z (x) -ζ z ( 1 2 ) = i(2z -1) ζ z (x) -ζ z ( 1 2 )
Proof. We consider for non-trivial Riemann zeros z the term

1 iP iP e iP -I x -z , 1 2 ≤ x ≤ 1
where 1 iP is defined as an integral operator on

L 2 [ 1 2 , 1] with boundary x = 1 2 1 iP f (x) := x 1 2 f (ξ)dξ, f ∈ L 2 [ 1 2 , 1]
and iP e iP -I f is defined as a Bernoulli generating function iP e iP -I f (x) :

= n≥0 B n n! (iP ) n f (x), f ∈ L 2 [ 1 2 , 1] Notice (iP ) n x -z = Γ(-z + 1) Γ(-z + 1 -n) x -z-n
We use Hankel loop contour integral formula [START_REF] Olver | NIST Handbook of Mathematical Functions Paperback and CD-ROM[END_REF][START_REF] Schmelzer | Computing the Gamma function using contour integrals and rational approximation[END_REF] 1

Γ(-z + 1 -n) = 1 2πi C ξ -(1-z-n) e ξ dξ
where the integration is done along the Hankel-Bromwich contour and it begins at -∞, circles the origin once in the positive direction, and returns to -∞

(iP ) n x -z = Γ(1 -z) 1 2πi C ξ -(1-z-n) e ξ dξ x -z-n = Γ(1 -z) 2πi C ξ x z+n-1 e ξ d ξ x
and then -zζ(z + 1, ξ)dξ

iP e iP -I x -z = n≥0 B n n! (iP ) n x -z = Γ(1 -z) 2πi n≥0
= ζ(z, x) -ζ(z, 1 2 ) (7)

  Let u = ξx and C = Cx is still a loop around the negative real axis. Uniform convergence on closed interval justifies the interchange of integral and sum. Then Hurwitz zeta function can be reproduced (1)iP e iP -I x -z = Γ(1 -z) 2πi C u z e u -1 e ux du = -zζ(z + 1, x)and the inverse iP e iP -Ix -z = -zζ(z + 1, x)

  1 2 , 1] and have finite norm and belong to the Hilbert space, ζ s ∈ L 2 [ 1

2 , 1]. If a complex number z is a non-trivial Riemann zero, ζ z (1) = 0 then the function ζ z vanishes at x = 1 2 from (2)


D Berthelot

M L Flottes

B Rouzeyre

A Method for Trading Test Time, Area and Fault Coverage in Datapath BIST Synthesis

This paper presents a method for deriving a BIST specification from the initial specification of datapaths. This method minimizes BIST area overhead under test time constraint while guaranteeing a user chosen fault coverage. The designer can thus explore a wide range of solutions and keep the one that best fits with design constraints. Results show great improvements over lower level techniques.

Introduction

The expected benefits of BIST insertion techniques at gate or RT level (e.g. [START_REF] Stroele | Hardware-Optimal Test Register Insertion[END_REF][START_REF] Krasniewski | Automatic Design of Exhaustively Self-Testing Chips with BILBO Operators[END_REF][START_REF] Hudson | Parallel Self-Test with Pseudo-Random Test Patterns[END_REF][START_REF] Chalasani | Design of Testable VLSI Circuits with Minimum Area Overhead[END_REF][START_REF] Basu | An Approach to Minimize Testability Overhead for BILBO based Buil-In Self-Test[END_REF][START_REF] Lin | Generating a Family of testable Designs Using the BILBO Methodology[END_REF][START_REF] Gizopoulos | An effective BIST scheme for Datapaths[END_REF]) are limited because the architecture is fixed. After synthesis, test insertion can only degrade the initial design by adding extra test resources and interconnects. That is the reason why many research groups study BIST insertion before architecture definition. In fact, BIST scheme may be decided during HLS (High Level Synthesis) e.g [START_REF] Parulkar | Introducing Redundant Computations in a Behavior for Reducing BIST Resources[END_REF] or even before at behavioral level. Several high level BIST insertion methods have been proposed in the literature, they can be broadly classified into two categories: those that target minimal area overhead [START_REF] Avra | Allocation and Assignment in High-Level Synthesis for Self-Testable Data Paths[END_REF][START_REF] Harmanani | SYNTEST: An Environment for System-Level Design for Test[END_REF][START_REF] Parulkar | Allocation Techniques for Reducing BIST Area Overhead of Data Paths[END_REF] and those that target minimal number of test sessions [START_REF] Harris | Micro-architectural Synthesis of VLSI Designs with High Test Concurrency[END_REF]. Three remarks can be made concerning these works. First, in any case they are based on specific HLS for BIST algorithms and, consequently, corresponding techniques cannot be used with a classical HLS flow. Second, the FC (Fault Coverage) is evaluated a posteriori, by fault simulation for instance. Consequently, it cannot be used to guide the test insertion process. Finally, related methods suffer from lack of generality in the sense they target a single type of TPGs (Test Vector Generators) and CMPs (response CoMPactors). However, the need to combine several test pattern generation and compaction techniques arises because each technique has its strong and weak points. In one hand, the initial design may be more or less favorable to the intrusion of a given type of test resources in terms of area overhead. On the other hand, pseudo-exhaustive test pattern generators, as arithmetic ones, are well suited for testing regular structures (adders, substracters, multipliers...) while pseudo-random sequences, generated with the help of LFSRs for instance, give better results on random logic. Combining several test resources types has already been proven to be very powerful at RT level [START_REF] Berthelot | BISTing Datapaths under heterogeneous Test Schemes[END_REF] as well as behavioral level [START_REF] Berthelot | BISTing Data Paths at Behavioral Level[END_REF]. This paper describes a new method for implementing a testper-clock BIST scheme for operators in data-paths. This method targets minimal area overhead while respecting a test time limit (TL). It aims at BISTing data paths as soon as possible in the design flow. The FC to achieve on data path's operators is a user-given parameter; it is used to guide the choice of a TPG among all possibilities. Finally, several types of TPGs/CMPs are eventually inserted within the same design for better optimization. Section 2 discusses our objectives. Section 3 describes the proposed test synthesis methodology. Experimental results are presented in section 4.

Test Time and Definitions

While area overhead is the usual main criterion when BISTing a circuit, it had been shown [START_REF] Berthelot | BISTing Datapaths under heterogeneous Test Schemes[END_REF] that a light increase in area may lead to large savings on test time. So we state the problem as minimizing area while respecting TL. Using various TL values, the designer can thus explore a wide range of BIST solutions and select the one that best fits with its constraints. Apart from the above mentioned drawbacks, published methods targeting test time minimization suffer from the following limitations: -All operators are assumed to be tested by the same type of TPG with the same number of test patterns. In other words, these methods minimize the number of test sessions and not really the test time. Test parallelism is limited by test resources conflicts. -Area overhead is not an input parameter but just a consequence. Thus these methods do not allow trade-off between area overhead and test time. An exception is the method presented in [START_REF] Papachristou | High Level Test Synthesis for Behavioral and Structural Design[END_REF]. In this method datapath is not partitioned into kernels. A single LFSR and a single MISR are connected to the primary I/Os. For a given test length some control/observation points are added to the datapath in order to increase fault coverage. If achieved fault coverage is not sufficient, test length is increased and so on and so forth. This method leads generally to very long test time if a high FC is desired because of the use of a single pseudorandom TPG and the highly sequential nature of the datapaths. Here we do not assume such restrictions. Test time depends on both the kinds of TPG used for each operator and on scheduling of test sessions.

Test resource characteristics are stored in a test library. For each resource, the library includes a functional model and the logic implementation when necessary (e.g. feedback loop and shift operation of an LFSR). Concerning the TPGs, the test library also includes the corresponding achievable FC for a given test length. Fig. 1 gives some examples. From this table we can see that TPG1, an arithmetic TPG, achieves 100% of FC on RC-Adder, a Ripple-Carry adder, with the help of 15 test vectors. TPG5 is an other example. It achieves respectively 90,4% and 95,2% of FC on operator RandomLogic, if the test length is extended from 255 to 1200 vectors. FCs and test lengths are computed in a pre-process task for every pair (TPG, operator). For each entry in this table, area corresponding to the modification of registers in test resources is also stored. Only entries in the library for which the desired fault coverage can be achieved are considered in the following. We use the following notations and definitions. TPG(M i ) and CMP(M i ) denotes the type of TPG and CMP used to test operator M i . Test time necessary to test M i with TPG(M i ) is denoted Time (M i , TPG(M i )). Definition 1: A test session is a set of operators tested concurrently. In order to simplify the BIST controller, we assume that in a session the tests of concerned modules start and end at the same time. TS is the set of test sessions. Definition 2: The duration T of a test session S is the test time of the longest-test-time operator in the session, that is T(S) = Max {Time(M i ,TPG(M i )). Definition 3 : The total time TT for testing operators grouped into test sessions is given by :

3.

Test Synthesis BIST definition is performed at behavioral level. It consists in deriving a behavioral description for the test mode from the original specification of the design. Both TBD (Test Behavioral Description) and IBD (Initial Behavioral description) are then jointly synthesized using a classical high level synthesis flow for full optimization of the entire architectural solution. The IBD is first scheduled under timing and hardware constraints, then operators are allocated and assigned to operations. The actual operators to test are thus determined. The so-computed intermediate level of representation, SDFG (Scheduled Data Flow Graph), and the test library support the TBD definition. The TBD is built up from fragments extracted from the SDFG, these fragments are called BPs (Behavioral Patterns) in the following. Section 3.1 discusses BPs extraction and section 3.2 describes TBD definition.

Behavioral Patterns in the SDFG

A BP is a fragment of the original SDFG. It defines the behavioral components involved in a future test resource and the way they are interconnected. It exists two types of behavioral patterns. A type1-BP is complete in the sense that the pattern is sufficient to lead to the generation of a test resource after register assignation. Conversely, a type-2 BP may lead to the generation of a test resource if a test function is used to complete the pattern. Fig. 2 gives two examples of type1-BPs; both of them may be used to implement a CMP based on an arithmetic compaction technique. The fragment in Fig. 2.a includes an adder performing an operation between two variables t and z. The result of this operation is written back into variable z. The BP in this case is composed of one operator and two variables: (Add 1 , t, z). After synthesis, this BP leads to the RTL pattern presented on the right-hand side Fig. 2.a. Such a type1-BP is said 'obligatory' since it leads to the generation of an arithmetic compactor whatever the register assignation is. Conversely, the type1-BP (Add 1 , t, y, z) presented in Fig. 2.b is a 'potential' pattern. In fact, it leads to the generation of an arithmetic compactor if, and only if, variables z and y are stored into the same register. When a test solution is selected for a given operator, register assignations involved by the corresponding BP are stored (e.g. assignations involved by a potential type1-BP). Fig. 3 gives an example of a type2-BP. This BP (x, y) can be 3). The area overhead of the test function comes from the test library (col.6 in Fig. 1). Note that any pair of variables connected to the operator under consideration in the original SDFG is a candidate type2-BP for this operator. For instance the pairs (x,u), (t,u) and (t,y) are also candidate BPs for the test of the adder.

Note that if several operators can be tested by the same type2-BP, only one test generation function (e. g. LF1) is introduced in the data path. All pairs of registers used to store test patterns on concerned operator's inputs are connected to this extra function (see Fig. 4).

The first task to perform before TBD definition is to build up a set of test solutions for each operator in the data path. These solutions are BPs extracted from the SDFG.

TBD Definition

The problem to define a test scheme is threefold: 1/ We have to determine the type of test resource used for each operator. This influences the area overhead and the test time. 2/ Test resources have to be instantiated. The number of implemented test resources influences the test time and the area overhead too. For instance two CMPs of the same type may be used to test two operators in parallel, while if only one CMP is instantiated the two operators must be tested in two distinct sessions. 3/ We have to determine the test sessions schedule to respect the user given time limit TL. The main problem while defining the TBD is to evaluate a very large number of test scheme solutions in order to select the best one. Test schemes need to be evaluated in terms of test time and in terms of area overhead. Test time has already been discussed in section 2. The constraint is TT<TL. Area overhead evaluation is discussed in section a/ below. In order to find the best solution in an acceptable amount of time, the search process is based on a branch and bound technique. Solutions are ordered before their evaluation in order to speed up the convergence to the best solution and to improve the pruning process. The procedure used to find the best overall solution is detailed in section b/. a/ Area overhead estimation As already mentioned above, a large number of solutions need to be evaluated, consequently area overhead must be evaluated with low computational effort. It is thus estimated as the sum of the area overhead introduced by test resources and the area overhead introduced by extra registers. Area overhead introduced by a given type of test resource is taken from the test library. Area overhead related to extra registers is the difference between the number of registers needed to implement the whole specification (IBD+TBD) and the number of registers needed to implement the initial specification (IBD). Let N Reg be the number of registers required to implement the IBD. N Reg can be computed by performing a first register assignation on the IBD. Let Test Reg be the minimal number of registers used during the test mode, it can be computed from the number of the number of registers required in every test session as follows. Let {Op k }be the set of operators tested during a test session S, TPG(Op k ) and CMP(Op k ) the test resources involved during Op k testing, Reg(TPG(Op k )) resp. Reg(CMP(Op k )) be the number of registers necessary to implement TPG(Op k ) resp. CMP(Op k ). Test Reg is given by:

      + = ∑ ∈ ∑ ∈ S k Op k Op k k TS S Reg Op CMP Reg Op TPG Reg Test )) ( ( )) ( ( max
Since the IBD and TBD lie in exclusive branches, the lifetimes of their variables do not overlap. Thus their variables can share the same registers. The number of registers necessary to implement IBD+TBD is estimated as max(Test Reg , N Reg ). The number of extra test registers due to BIST synthesis is taken as:

Reg Reg Reg Reg N N Test Test - = ∆ ) , max(

b/ Branch and bound

Best solution search process is detailed in Fig. 5. First pruning is performed on TPGs ( •). Each operator, Op k , can be tested with the help of several TPGs, TPGs(Op k )={TPG(Op k ) m , m =1,...} in the following. TPGs(Op k ) is ordered in such a way that TPGs that can be shared by a maximum of operators are considered first. Priority1(TPG(Op k ) m ) allows ordering TPGs(Op k ):

∑ ≠ ∈ =           k i i m k m k Op Op otherwise Op TPGs ) TPG(Op if ) TPG(Op iority 0 ) ( 1 ) ( 1 Pr
TPGSet represents a sufficient set of test generators for testing all operators Op k . TPGSets are built up from all combinations of the ordered sets TPGs(Op k ). The second pruning is performed with respect to the usergiven test time threshold TL ('). A scheduling solution, SS, is build up incrementally. At each step, the test of a new operator is added to the preceding partial schedule, partial-SS. If the corresponding test time, Tt(partial-SS), go beyond TL, partial-SS is not further explored. Here again, a priority function, Priority2(Op k ), is used to order the operators to schedule. The ones that need the largest number of test patterns are considered first:

)) k ,TPG(Op k Time(Op ) k Op Priority2( =
The last step is dedicated to the selection of CMPs (ƒ). As for TPG's selection, we have to evaluate several sets of solutions, CMPSets. These sets are build up incrementally, if Area(partial-CMPSet)>BestArea then the process stop for the corresponding set of compactors and a new CMPSet is built up. At the end of the procedure, test sessions are scheduled and TPGs/CMPs are assigned to operators. The TBD is build up from this information. Extra area due to the BIST intrusion is determined after synthesis of the new behavioral description that includes both TBD and IBD.

Results

We applied this method to three classical HLS benchmarks: elliptic wave filter EWFIL, auto-regressive filter ARFIL, and differential equation solver DIFEQ. Each circuit has been synthesized using various area constraints, expressed as number of operators. In all experiments, the desired fault coverage has been fixed to 100%. The results are presented in the tables below divided into horizontal blocks. Each block compares several BIST strategies for the same area constraints. Column 2 gives the user given test time limit on line 'Initial' (e.g. < 500) and the actual test time for different strategies. Columns 3 to 7 give the number of operators, registers and multiplexor inputs in the designs. Columns 8 and 9 refer to the number of EXOR-based feedback operators used to create LFSR and MISR. The arithmetic TPGs/CMPs, which do not involve area overhead, are not referred in the tables. Signatures are propagated to observation points (primary output or observable registers) via I-paths [START_REF] Abadir | Constructing optimal test schedules for VLSI circuits having built-in test hardware[END_REF] when possible. Otherwise a shift facility is added to the register storing the signature, this is referred by ShiftReg column.

After BIST insertion, designs are expanded to gate-level using a commercial tool and a 0.7 µ.m library. Areas are measured in terms of number of cell units. Area overhead is given in columns 11 to 14 for 4 datapath bit-widths. A first set of experiment aims at proving the interest of a high-level test synthesis compared to a RTL technique [START_REF] Berthelot | BISTing Datapaths under heterogeneous Test Schemes[END_REF]. A second set of experiments highlights the interest of hybrid test schemes including several types of test resources.

Comparison with RT approach

In this section, we compare the results of the presented methods (referred as BBIST for behavioral BIST in the tables below) with those obtained using a RT level BIST insertion method (referred as RTBIST). We used our HLS tool (MACH) to generate the RTL descriptions. The line BMinArea refers to designs obtained through the method presented in [START_REF] Berthelot | BISTing Data Paths at Behavioral Level[END_REF], i.e. a behavioral test synthesis technique targeting minimal area overhead. It can be seen on these tables that in some case BIST insertion at RT level does not allow satisfying the test time limit. The main reason is the fixed structure of the interconnection network. It can also be seen that our method always leads to the best designs whatever the example and the test time limit. They are generally far better than those obtained at RT level. That's mainly because the RTBIST method must adapt/modify the structure of the circuit in order to parallelize test sessions. Conversely our method generates one (adapted) architecture for each test time constraint. Finally it can be observed that for a low increase over the minimal area overhead (e.g. 6.37% to compare with 6,51% i.e. an increase of 0.14% in first block in table 1), test time decreases a lot (from 496 to 248).

Benefit of using various test resources types

Here we applied our method in restricting the set of usable test resources to LFSR and MISR (line LFSR). Then the so synthesized solutions are compared with synthesis solutions where all kinds of TPGs/CMPs are accepted (line all). Using various kinds of resources types always leads to better results than using a single kind of TPGs and CMPs. Area overheads vary by twice as much. One of the reasons is that arithmetic CMP, which do not involve area overhead, can be used instead of MISR. In a counterpart, some designs can not be tested if TPGs/CMPs types are restricted to arithmetic structures.

Conclusion

The proposed method is the first one to seek a minimal area BIST solution while respecting a test time constraint. Acting at behavioral level, it lets the high-level synthesis process to care about the optimization of both the initial behavioral description and the BIST behavioral description.

  individual tests into test sessions is constrained by the following properties. Property 1: A TPG can be used for testing several operators in a test session or in different sessions. Property 2: Several operators can not share a CMP in one test session. Conversely, a CMP can be used for several operators in different sessions. Theorem: The number of ways of grouping the tests of n operators into test sessions is given by: are known as the Stirling coefficients). P n growths very quickly with n (e.g. P 7 = 876)

2 Fig. 4 :

 24 Fig. 3: Type-2 Behavioral pattern

.2: Type-1 Behavioral patterns used

  for generating an LFSR-type TPG if a test function (LF1) is added to complete the pattern (see right-hand side, Fig.

	TPG	Module	FC	#Vect	Type	Area
	TPG1	RC-Adder	100.0	15	Arith based	-
	TPG2	RC-Adder	100.0	15	LFSR based	10
	TPG3	RC-Adder	100.0	17	LFSR based	20
	TPG4 CS-Multiplier 100.0	214	LFSR based	15
	TPG5	RandomLog1	95.2	1200	LFSR	5
	TPG5	RandomLog1	90.4	255	LFSR	5
		Fig. 1: TPG's Test Library sample
						BP	t	z	t,... z,...	BP	t y	t,... z,y,...
						Add 1		+	Add 1	Add 1	+	Add 1
								z	z
						a: Obligatory type1-BP	b: Potential type1-BP
								Fig

: Test resource selection under test time constraint

	•For each TPGSet i
	If Area(TPGSet i )+Area(?Test Reg )<BestArea 'For each schedule solution If TT<TL ƒ For each CMPSet j If Area(TPGSet i )+ Area(CMPSet j ) +Area(?TestReg)<BestArea BestArea= Area(TPGSet i )+ Area(CMPSet j ) +Area(?TestReg) Store TPGSet i ,CMPSet j EndIf EndFor EndIf EndFor EndIf EndFor Test Time + -* Reg Mux LFSR MISR Shift Reg Initial <300 2 0 2 8 34 RTBIST 248 2 0 2 8 48 2 1 1 HLS Bist 248 2 0 2 8 44 1 0 1 BMinArea 496 2 0 2 8 42 1 1 0 Initial <300 2 0 3 8 41 RTBIST -2 0 3 8 41 HLS Bist 248 2 0 3 8 51 1 1 0 Initial <500 2 0 3 8 41 RTBIST 462 2 0 3 8 55 2 2 1 HLS Bist 462 2 0 3 8 54 1 0 1 BMinArea 727 2 0 3 7 52 1 0 2 Initial <300 2 0 4 8 48 RTBIST -2 0 4 8 48 HLS Bist 231 2 0 4 8 59 1 2 0 Fig. 5Circuit Initial <500 2 0 4 8 48	Area 8 bits Initial Circuit 9.79% 6.51% 6.37% Initial Circuit No solution at RTL Area 16 bits 5.45% 3.02% 2.90% 6.64% 3.06% Initial Circuit 9.22% 4.85% 6.28% 2.85% 2.29% 0.86% Initial Circuit No solution at RTL 7.76% 3.26% Initial Circuit	Area 32 bits 2.87% 1.70% 1.60% 1.52% 2.35% 1.54% 0.45% 1.52%	Area 64 bits 1.52% 0.90% 0.87% 0.79% 1.21% 0.80% 0.23% 0.78%
	RTBIST	445	2 0 4	8	64	2	2	0	8.23%	4.16%	1.99%	1.02%
	HLS Bist	445	2 0 4	8	59	1	1	0	5.79%	2.59%	1.26%	0.65%
	BMinArea	958	2 0 4	8	62	1	0	1	4.78%	2.42%	1.28%	0.66%
	Initial	<300	2 0 5	8	51				Initial Circuit
	RTBIST	-	2 0 5	8	51				No solution at RTL
	HLS Bist	231	2 0 5	8	64	1	4	0	10.61%	4.11%	1.81%	0.91%
	Initial	<500	2 0 5	8	51				Initial Circuit
	RTBIST	462	2 0 5	8	75	4	4	0	11.92%	5.79%	2.66%	1.34%
	HLS Bist	462	2 0 5	8	64	1	1	0	5.52%	2.43%	1.18%	0.60%
	BMinArea	1189	2 0 5	7	62	1	0	2	3.28%	1.40%	0.73%	0.37%

Table 1 : Comparison RTBIST / BBIST (trade-off time/area)ARFIL

 1

	Initial	<300	1 1 2	5	19				Initial Circuit
	RTBIST	-	1 1 2	5	19				No solution at RTL
	HLS Bist	253	1 1 2	5	27	1	1	0	11.19%	5.07%	2.50%	1.29%
	BMinArea	270	1 1 2	5	25	1	1	0	8.58%	4.41%	2.15%	1.10%
	Initial	<300	1 1 3	6	18				Initial Circuit
	RTBIST	-	1 1 3	6	18				No solution at RTL
	HLS Bist	236	1 1 3	6	35	1	2	0	13.89%	5.90%	2.80%	1.42%
	Initial	<500	1 1 3	6	18				Initial Circuit
	RTBIST	467	1 1 3	6	40	4	1	1	13.54%	6.36%	3.13%	1.58%
	HLS Bist	467	1 1 3	6	40	1	0	1	11.55%	5.20%	2.72%	1.39%
	BMinArea	501	1 1 3	6	34	1	1	0	9.59%	4.74%	2.34%	1.19%

Table 2 : Comparison RTBIST / BBIST (trade-off time/area)DIFEQ Results

 2 show the interest of directly synthesizing circuits adapted to the test time constraint rather than to work at RT level. This work is the first one in our knowledge to use various kinds of test resource sin a single design. This feature leads to minimize area overhead for a given test parallelism. Moreover test time of individual MUTs can be optimized by the choice of the TPG type. Presented results show that area overheads are up to 50% less than when BIST insertion is considered at RT level or when a single test scheme is considered.


M L Flottes

D Hammad

B Rouzeyre

Improving Testability of Non-Scan Designs during Behavioral Synthesis

We present a behavioral synthesis method aimed at generating testable datapaths. A non-scan testing strategy is targeted. Given performance and area constraints, the system is aimed at seeking among potential design alternatives the one presenting the least testability problems. The backbone of this methodology is a testability analysis method that works at different abstraction levels of the design description -from strictly behavioral domain to purely structural domain-. Considering a partially mapped behavioral specification, the testability analysis identifies the testability problems of the future structure. These problems are solved along the synthesis process, for example during the register allocation/binding task as presented in this paper.

I Introduction

High Level Synthesis (HLS) systems generate a structural hardware implementation at Register Transfer Level (RTL), given a behavioral description of design and user defined constraints like area and performance. The behavioral description is first translated into an intermediate description such as a Data Flow Graph (DFG) or a Control Flow Graph (CFG). Nodes and arcs in a DFG correspond respectively to operations and variables in the behavioral description. In a CFG, arcs represent sequencing and nodes define data transformations or control branching. Then, HLS algorithms act on this intermediate description. They perform scheduling (partitioning the description into time intervals called control steps), binding (assigning variables to storage components and operations to functional units), as well as generating interconnect network and control logic. The final output is an RTL structure composed of a datapath and of a controller. The datapath contains the functional units (f.u.s), the storage components, and the interconnect network connecting these various physical resources. The controller is a finite-state machine which drives the control signals of datapath elements in order to achieve the intended behavior.

Progress in technology and CAD tools has allowed a constant increase of the VLSI circuits performances, however the problems related to their testing have multiplied. Nowadays, it is universally acknowledged that test has to be taken into account as soon as possible in the design cycle in order to reduce its cost -and consequently the global electronic component production cost-

The first Design For Testability (DFT) issues were addressed in the early 1980's, while presently, High Level Synthesis For Testability (HLSFT) approaches are under consideration.

DFT tools are totally independent of synthesis. Working on structural representations at RTL or at gate level, they are applied as post-processors and cannot modify the allocation/binding of physical resources. The 'S-graph' model [START_REF] Cheng | Synthesis of testable finite state machine[END_REF] is commonly used to represent the topology of a sequential circuit to be made testable. At gate level, each node in the S-graph represents a flip-flop (FF) of the circuit. A directed edge from node-1 to node-2 means that the FF corresponding to node-1 is connected to the FF corresponding to node-2 through combinational logic. The sequential depth between two FFs is defined as the number of edges between the two corresponding nodes in the S-graph. When several paths exist between two nodes, the sequential depth is determined by the shortest.

It has been observed ( [START_REF] Cheng | A Partial Scan Method for Sequential Circuits with Feedback[END_REF], [START_REF] Lee | On Determining Scan Flip-Flops in Partial Scan Designs[END_REF]) that the automatic sequential test pattern generation (SATPG) complexity grows exponentially with the length of cycles in the S-graph and linearly with the sequential depth between FFs directly connected to primary inputs and FFs directly connected to primary outputs. Consequently, numerous DFT techniques use these measures to improve testability. For instance, scan FFs are inserted in order to break cycles longer than one and to minimize the sequential depth between inputs and outputs.

Since the early 90's, HLSFT have been proposed for considering testability earlier in the design flow. Because different hardware solutions can meet area/performance constraints, HLSFT systems use criteria associated with specified testability requirements to drive synthesis towards a design which also satisfies testability constraints (see [START_REF] Avra | High-Level Synthesis of Testable Design: An Overview of University Systems[END_REF] for an overview of University HLSFT systems).

Such an approach may avoid the drawbacks inherent in gate-level DFT techniques where test overhead may conflict with initial area and performance requirements.

HLSFT systems target BISTed structures ( [START_REF] Harris | Micro-architectural Synthesis of VLSI Designs with High Test Concurrency[END_REF], [START_REF] Papachristou | SYNTEST: a method for high-level SYNthesis with self-TESTability[END_REF], [START_REF] Avra | Allocation and Assignment in High-Level Synthesis for Self-Testable Data-Paths[END_REF]), or non-scan ( [START_REF] Bhatia | Genesis: A Behavioral Synthesis for Hierarchical Testability[END_REF], [START_REF] Mujumdar | Behavioral Synthesis of Testable Designs[END_REF], [START_REF] Lee | Behavioral Synthesis for Easy Testability in Data Path Allocation[END_REF], [START_REF] Mujumdar | Incorporating Testability Considerations in High-Level Synthesis[END_REF], [START_REF] Kim | A Stepwise Refinement DataPath Synthesis Procedure for Easy Testability[END_REF], [START_REF] Chen | Structural and Behavioral Synthesis for Testability Techniques[END_REF]) or partial scan designs ( [START_REF] Dey | Transforming behavioral specifications to facilitate synthesis of testable designs[END_REF], [START_REF] Lee | Conditional resource sharing method for behavioral synthesis of highly testable data paths[END_REF], [START_REF] Dey | Exploiting Hardware Sharing in High-Level Synthesis for Partial Scan Optimization[END_REF], [START_REF] Potkonjak | Behavioral synthesis of Area-Efficient Testable Designs using interaction between Hardware Sharing and Partial Scan[END_REF], [START_REF] Lee | Behavioral Synthesis for Highly Testable Data Paths under Non-Scan and Partial-Scan Environments[END_REF]). For non-scan and partial scan designs, HLSFT systems attempt to generate structures which can be tested 'easily' by SATPGs. The easiness of testing is evaluated in terms of fault coverage, test efficiency, test sequence length or test generation time. RTL structures are generally extended to gate level descriptions in order to use state-of-the-art SATPGs. Note an exception for the Genesis system [START_REF] Bhatia | Genesis: A Behavioral Synthesis for Hierarchical Testability[END_REF] where both RTL and gate level descriptions are used to perform hierarchical testing.

Using a S-graph-like model to specify the structure of datapath logic, numerous HLSFT process target the same goals as DFT techniques: break the cycles and minimize the sequential depth at low cost. These systems are aimed at (i) avoiding the formation of cycles and/or restricting the number of scan registers needed to break them ( [START_REF] Mujumdar | Behavioral Synthesis of Testable Designs[END_REF], [START_REF] Lee | Behavioral Synthesis for Easy Testability in Data Path Allocation[END_REF], [START_REF] Mujumdar | Incorporating Testability Considerations in High-Level Synthesis[END_REF], [START_REF] Dey | Transforming behavioral specifications to facilitate synthesis of testable designs[END_REF], [START_REF] Lee | Conditional resource sharing method for behavioral synthesis of highly testable data paths[END_REF], [START_REF] Dey | Exploiting Hardware Sharing in High-Level Synthesis for Partial Scan Optimization[END_REF], [START_REF] Potkonjak | Behavioral synthesis of Area-Efficient Testable Designs using interaction between Hardware Sharing and Partial Scan[END_REF], [START_REF] Lee | Behavioral Synthesis for Highly Testable Data Paths under Non-Scan and Partial-Scan Environments[END_REF]), then at (ii) minimizing the sequential depth between registers directly connected to primary inputs/outputs (I/O registers) ( [START_REF] Lee | Behavioral Synthesis for Easy Testability in Data Path Allocation[END_REF], [START_REF] Kim | A Stepwise Refinement DataPath Synthesis Procedure for Easy Testability[END_REF], [START_REF] Lee | Conditional resource sharing method for behavioral synthesis of highly testable data paths[END_REF], [START_REF] Dey | Exploiting Hardware Sharing in High-Level Synthesis for Partial Scan Optimization[END_REF], [START_REF] Potkonjak | Behavioral synthesis of Area-Efficient Testable Designs using interaction between Hardware Sharing and Partial Scan[END_REF], [START_REF] Lee | Behavioral Synthesis for Highly Testable Data Paths under Non-Scan and Partial-Scan Environments[END_REF]). In [START_REF] Mujumdar | Incorporating Testability Considerations in High-Level Synthesis[END_REF] and [START_REF] Kim | A Stepwise Refinement DataPath Synthesis Procedure for Easy Testability[END_REF], it has also been proposed to reduce the testability overheads by producing designs including as few self-loops (cycles of length one) as possible. But this new constraint may lead the HLSFT system to produce a larger number of cycles longer than one thus lessening testability ( [START_REF] Mujumdar | Incorporating Testability Considerations in High-Level Synthesis[END_REF]). Another goal widely addressed in HLSFT is to generate designs with a maximum number of I/O registers ( [START_REF] Mujumdar | Behavioral Synthesis of Testable Designs[END_REF], [START_REF] Lee | Behavioral Synthesis for Easy Testability in Data Path Allocation[END_REF], [START_REF] Mujumdar | Incorporating Testability Considerations in High-Level Synthesis[END_REF], [START_REF] Lee | Conditional resource sharing method for behavioral synthesis of highly testable data paths[END_REF], [START_REF] Lee | Behavioral Synthesis for Highly Testable Data Paths under Non-Scan and Partial-Scan Environments[END_REF]). Since such registers are easily controlled and observed, they improve the accessibility of the datapath components, and indirectly they entail sequential depth reduction.

Testability constraints can be inserted at several levels of the HLS process. Formation of cycles can be avoided by analyzing the alternatives offered during scheduling or allocation/binding tasks ( [START_REF] Mujumdar | Behavioral Synthesis of Testable Designs[END_REF], [START_REF] Mujumdar | Incorporating Testability Considerations in High-Level Synthesis[END_REF]). Nevertheless, datapath cycles may be either inherent in the behavioral description, or created during the synthesis process (see [START_REF] Dey | Exploiting Hardware Sharing in High-Level Synthesis for Partial Scan Optimization[END_REF] for an overview). If scan registers are used for breaking remaining cycles in a datapath, their number can be minimized by analyzing the structural implantation alternatives during scheduling and allocation/binding tasks ( [START_REF] Potkonjak | Behavioral synthesis of Area-Efficient Testable Designs using interaction between Hardware Sharing and Partial Scan[END_REF], [START_REF] Lee | Behavioral Synthesis for Highly Testable Data Paths under Non-Scan and Partial-Scan Environments[END_REF]) or by modifying the behavioral specification before synthesis process ( [START_REF] Dey | Transforming behavioral specifications to facilitate synthesis of testable designs[END_REF]). Scheduling and allocation/binding alternatives are also probed in order to minimize the sequential depth between I/O registers ( [START_REF] Kim | A Stepwise Refinement DataPath Synthesis Procedure for Easy Testability[END_REF]), and to maximize the number of I/O registers ( [START_REF] Lee | Behavioral Synthesis for Easy Testability in Data Path Allocation[END_REF], [START_REF] Mujumdar | Incorporating Testability Considerations in High-Level Synthesis[END_REF], [START_REF] Kim | A Stepwise Refinement DataPath Synthesis Procedure for Easy Testability[END_REF]).

A few comments can be made concerning datapath testability evaluation by means of cycles and sequential depth. First, problems related to cycles and sequential depth are generally less crucial in datapaths than in state machines found in the control logic, due to a 'weaker' interconnect network.

Moreover, today commercial SATPGs deal more easily with cycles and sequential depth. Sequential depth minimization can be considered as a second rate objective and cycles have to be distinguished according to the difficulties they involve. For instance in Figure 1.a, there is a path through the adder allowing to control the register R to any particular value from primary inputs.

Consequently, in spite of the presence of the cycle, an SATPG can easily find a justification path for a fault in R, in the subtracter, or in some downstream entities. On the contrary, no path allows to control registers R1 and R2 from primary inputs in the cycle of Figure 1.b. This cycle, referred to as 'strongly closed loops' in the rest of this article, can lead to the impossibility of setting necessary test data into R1 or R2 and has to be considered as a testability bottleneck. Test data propagation problems are addressed only partially and implicitly in HLSFT systems attempting to maximize the number of I/O registers. Essentially, in an ideal binding solution, all registers would be directly connected to primary inputs and outputs. Consequently, the registers and other datapath components connected to them would be fully controllable and observable.

Unfortunately, the upper bound of the amount of input and output registers is fixed by the number of DFG variables directly set from primary inputs and directly read through primary outputs. As a consequence, when a maximum number of variables have been assigned to I/O registers, the remainder are assigned into new registers blindly w.r.t. their controllability/observability. Conversely, the two approaches presented in [START_REF] Bhatia | Genesis: A Behavioral Synthesis for Hierarchical Testability[END_REF] and [START_REF] Chen | Structural and Behavioral Synthesis for Testability Techniques[END_REF] are based on testability analysis. In [START_REF] Bhatia | Genesis: A Behavioral Synthesis for Hierarchical Testability[END_REF], the possibility of transmitting test data to the DFG nodes through arithmetic units and gates are analyzed by a set of rules. For example, to set a test pattern on a multiplier output, an input will be controlled to the value 'one' and the other to the desired test pattern value. Testability analysis results are used to drive the f.u.s/registers binding process. The goal is to generate a datapath structure in such a way that every f.u. in the final structure can be controlled from primary inputs and observed through primary outputs. Control/observation paths, extracted from the DFG paths, form the test environment for the corresponding f.u.s. Test environments are used to propagate test data computed at gate level on f.u.s boundaries. Nevertheless, one limitation of this method is that the set of rules for the testability analysis applies only to specific modules namely, the ones with a neutral element.

In the approach proposed in [START_REF] Chen | Structural and Behavioral Synthesis for Testability Techniques[END_REF], behavioral modifications for improving testability are applied to hard-to-test sections before HLS. Hard-to-test sections are identified by analyzing the CFG, then variables are classified according to the results of the analysis. For instance, a variable is 'completely controllable' if there exists a sequence of executable paths in the CFG such that, after the execution of these paths, the content of the variable can take any possible value by adjusting the primary input values. A common drawback of both this approach and the one presented in [START_REF] Bhatia | Genesis: A Behavioral Synthesis for Hierarchical Testability[END_REF] is that the testability analysis is limited to the set of paths already existing in the initial specification namely, in the DFG [START_REF] Bhatia | Genesis: A Behavioral Synthesis for Hierarchical Testability[END_REF] and in the CFG in [START_REF] Chen | Structural and Behavioral Synthesis for Testability Techniques[END_REF]. These paths, exercised during the normal execution flow of the circuit, represent only a subset of all the paths connecting datapath components, even though the activation of other paths does not respect the initial sequencing. This point is examined in detail in section III. Now let us describe the HLSFT system developed at LIRMM for generating datapaths in which as many modules as possible (storage components, f.u.s,... but also muxes and wires) can be tested using parallel test data propagated through primary input/output ports. This system is aimed at exploring the design space to generate easily testable designs while respecting other design constraints, without using partial scan insertion. Test patterns are actually obtained using a gatelevel SATPG.

For improving datapath testability, binding/allocation possibilities are explored to enhance the 'accessibility' of all modules. The main features of the presented method are the following:

-It is based on a testability analysis with no restrictive assumptions on the type of f.u.s usable in the designs.

-Each RTL structural path, which exists in the final architecture and that can be derived during the HLS flow, is considered for test data propagation.

-It supports behavioral specifications containing control constructs (with conditional statements and/or cyclic CDFG).

-The strongly closed loops are within the scope of this method (other cycles are not considered as testability bottlenecks).

-Since it deals with datapaths, the sequential depth is considered as a second rate factor allowing to choose between two binding solutions when they are equivalent in terms of other test measures.

-There is no assumption on the value of the test patterns during the HLS process.

II Overview of the system

The primary goal is to take advantage of synthesis possibilities -mainly during the binding phase-in order to obtain a design in which as many modules as possible have their test paths. These test paths being 1/ the controllability paths allowing to apply test patterns on the module's inputs from primary input ports and 2/ the propagation paths allowing to observe test responses through circuit's outputs. Due to the excessive CPU time required by SATPG programs to find test patterns, the secondary goal is to generate designs that are easily testable by SATPG.

The circuit architecture targeted by the synthesis system -depicted in Figure 2-is composed of a datapath and a controller (a set of FSMs) driving the datapath command signals and sequencing the given behavior. Only the testability of the datapath is dealt with in this paper. The controller is assumed to be made testable using a BIST ( [START_REF] Hellebrand | Synthesis of Self-Testable Controllers[END_REF]) or a scan approach. Regarding datapath testability, we consider that any desired value can be set on the control signals, see Figure 2. Therefore, at least two solutions are possible: either the control signals/flags are made fully controllable/observable by using scan method -only to introduce FFs on control signals-or the desired datapath test plan is incorporated within the control logic. Thus the sequencing of the datapath test is independent of the normal mode of execution (contrary to the approaches [START_REF] Bhatia | Genesis: A Behavioral Synthesis for Hierarchical Testability[END_REF] and [START_REF] Chen | Structural and Behavioral Synthesis for Testability Techniques[END_REF] discussed in the introduction). The synoptic of the system is shown in Figure 3. White and shadowed boxes are the usual tasks performed during standard HLS of datapath: after the behavioral specification has been translated into a DFG, the scheduling phase assigns operations to control steps. Then operations are bound to f.u.s. Register binding determines the required memory elements (allocation) and binds variables to the registers. Finally, the architectural structure is completed by allocating interconnect elements (muxes, wires, busses) between f.u.s and registers for implementing the data transfers of the initial specification.

To perform HLSFT, several tasks are added and some others modified (stripped and shadowed boxes in Figure 3, respectively). Shaded boxes represent synthesis tasks aimed at improving testability. As shown on the figure, this synthesis for testability method is based on a testability analysis used at different stages of the HLS process. Its results are required for driving register binding and generating interconnections.

Considering the influence of testability improvement on design performance, it is worth noting that:

the number of control steps stays unchanged since testability is considered after the scheduling phase,

the clock period may be shortened or lengthened: since from the timing point of view, testability improvement tasks change exclusively the multiplexing resources, delays only through the interconnect network are affected. These multiplexing modifications may change the sum of gates on the critical path. Consequently, the clock period (fixed by the critical path) may be increased or decreased. depending on the sum of gate delays, which is only a rough estimation of the actual delays.

III Behavioral testability analysis

This section deals exclusively with the testability analysis method used before register binding, other invocations of the testability analysis being very alike.

At this point of the synthesis process, circuit's behavior is expressed as a DFG in which operations are bound to f.u.s. Thus, the nodes of the DFG are f.u.s and edges denote data transfers with or without memorization (a variable being associated to each transfer with memorization).

Testability criteria analyzed by our system are essentially the existence of 1/ paths allowing to justify test patterns and 2/ paths allowing to observe test responses. Since testability applies to the structural domain, the question is to know whether such paths will exist in the future structure, given the set of data transfers described at the algorithmic level. These paths are to be built from the data transfers regardless of both their grouping into statements and their schedule in the normal flow of execution (contrary to the analysis method presented in [START_REF] Bhatia | Genesis: A Behavioral Synthesis for Hierarchical Testability[END_REF] and [START_REF] Chen | Structural and Behavioral Synthesis for Testability Techniques[END_REF]). For instance, if the specification contains a statement like a := b + c, the three transfers a -> +, b -> + and + -> c are considered independently. The future structure will contain a physical path from the registers implementing a and b to the f.u implementing the addition, and from this f.u to the register implementing c. Data transfers are then reorganized in order to create, when possible, justification paths from primary input(s) and propagation paths to primary output(s).

Without loss of generality, we shall assume in the remainder of the text that all the f.u.s have Definition 3: A C-path of a module's port p is a lattice of data transfers rooted on primary inputs and ending at p such that 1/ in every transfer a->b belonging to this C-path, a and b are either variables or ports of C-transparent modules 2/ it does not contain reconvergences, for instance a variable does not feed both inputs of a f.u. A variable or a register with a C-path is said to be controllable, it can be set to any value. In the same way a f.u is controllable if there exist two distinct controllable variables linked to its inputs (second above condition).

two
Definition 4: A O-path of a module's port p is an ordered set of data transfers starting at p and ending on a primary output, such that for every transfer a->b belonging to the O-path, a and b are either variables, or an input port I1 of a f.u O-transparent for I1, or an output port of O-transparent f.u or a primary output.

Definition 5: To validate a propagation through a O-transparent f.u from I1 to O, a particular value must be justified on I2. Consequently, the propagation is possible if there exist a transfer v->I2 such that v posses a C-path. Such a C-path is called a lateral C-path. Thus, any fault on p can be observed (p is said to be observable) if: 1/ x has an O-path, 2/ there exist a complete set of lateral C-paths not containing x. The second condition is set in order to avoid fault masking problems. It is not a necessary condition but the knowledge of gate-level information would be required for its removal. In the remainder of the text, O-path stands for the union of an O-path and its lateral Cpaths.

Definition 6: A module is testable iff it is controllable and observable.

The extension of the above definitions to actual test patterns is straightforward if a hierarchical testing methodology is envisaged. C-paths and O-paths are a generalization of I-paths and S-paths defined in [START_REF] Abadir | A knowledge-based System for Designing Testable VLSI chips[END_REF] and [START_REF] Freeman | Test Generation for Data-Path Logic: The F-path method[END_REF].

It is important to note that no assumptions are made on test patterns, mainly because this level of design is far from the structural level (registers, muxes, wires have not yet been determined). Thus, this definition of 'testable' is pessimistic. For example, a module may happen to be found as noncontrollable by the proposed testability analysis while the actual test patterns can be justified.

On the other hand, due to these very conservative assumptions, a SATPG can very easily find test patterns for a module in case it is found testable. Conversely, if the module is determined to be nontestable SATPG may have difficulties either to find test patterns or to prove this module to be actually non-testable.

The testability analysis process returns classification of variables depending on their respective controllability/observability. Moreover, when a variable is found either controllable or observable, corresponding C-paths or O-paths are generated, respectively. The sequential depth of a controllable variable is defined as the minimum number of clock cycles required to set a test pattern in this variable. For example, the sequential depth of the controllable variables b, c, d, e and i,

shown on the DFG of Figure 4, is equal to 1, while the controllable variable k has a sequential depth equal to 2.

This paragraph describes the classification of non-controllable variables (non-observable variables can be classified using a similar approach). The example of Figure 4 Let us recall that the cycles considered as testability bottlenecks are only the strongly closed ones. For example, the cycle involving the variable a in the DFG shown in Figure 5 is not of the 'strongly closed loop' one. This variable can be set from primary inputs through functional unit f.u.1 which implements both +1 and +2 operations and is considered as a controllable variable. transfers and checking the transparency of the involved f.u.s. Concerning C-paths, initially the variables linked to primary inputs are controllable, their C-path containing only one transfer. Let us assume that after several iterations, the data transfer from a C-transparent f.u. F to a variable V is under consideration. If both F inputs have been found controllable during previous iterations, and if their respective C-paths end on different variables (see Def3 about reconvergence), then V is controllable and its C-path is the union of the two C-paths plus the transfers F->V. This C-path is added to the list of C-path for V. The process is iterated until no change occurs. The interested reader can refer to [START_REF] Hammad | Testability and architectural synthesis of digital circuits[END_REF] for more details on the testability analysis algorithm.

Figure 6 shows the scheduled DFG obtained for the 'differential equation' high level synthesis benchmark [START_REF] Paulin | Scheduling and binding algorithm for high level synthesis[END_REF]. Operations have been bound to two multipliers MULT1 and MULT2, one adder ADD and one subtracter SUB. The DFG is cyclic, feedback edges are not represented on the figure.

Variables x, y and u are loaded from primary inputs in the first iteration, then loaded from the f.u.s in the following iterations. For illustration purposes, we assumed that all f.u.s are C-transparent and O-transparent except the subtracter which actually is transparent. Table 1 shows the results of the testability analysis on this example. Rows 2 and 3 respectively assess the controllability/observability of the variables. Rows 2 and 3 in Table 2 give the number of possible justification paths for each input of the f.u.s. Row 4 (Table2) gives the number of propagation paths for each f.u.

IV Synthesis algorithms

According to analysis results, testability is considered during the synthesis steps represented by shadowed boxes in Figure 3 namely, the register binding phase and the generation of the interconnect network (insertion of busses, muxes and wires necessary to interconnect registers and f.u.s). Allocation and binding choices are sought in order to improve testability. Only register allocation for testability improvement is detailed here, the principle being the same as for generating the interconnect network.

a-Register allocation:

Let us first recall the basic principle of register allocation: variables can share the same register if their life times do not overlap. The merging possibilities of variables are extracted by performing a life time analysis and a compatibility graph is built up. In this graph, nodes and edges stand for variables and merging possibilities, respectively. Every clique of the graph represents a set of variables which can be assigned to the same register.

In standard HLS, a solution for minimizing the area expressed by a cost function f a (# registers, # multiplexer inputs,...) is reached by seeking an adequate clique partitioning in the compatibility graph. Generally, the search is guided by weighting the graph edges by the area gain Df a -i.e. the area gained by merging the two involved variables-. In the algorithm used in our standard HLS system [START_REF] Rouzeyre | A new method for the minimization of memory related area[END_REF], the pair of variables (registers) joined by the edge of maximal weight is merged. After each coupling, all weights and compatibility edges are updated. The process is iterated until no further coupling is possible.

The principle underlying testability improvement is to assign the same register to noncontrollable (non-observable) variables and to controllable (observable) ones rather than assign only non-controllable variables to the register. In the first case, the resulting register is controllable while in the second case it is not. Registers inherit the testability properties of variables assigned to them, e.g. the C-path (O-path) of a controllable (observable) variable becomes the C-path (O-path) of the register. Figure 8 illustrates the principle underlying register allocation for testability improvement. The proposed method does not differ from other related works in the general principle but in the objectives targeted to improve testability. As in many other HLSFT systems, the rule is to assign non-testable behavioral components together with testable ones -since structural components resulting from the assignations inherit testability properties-.

Concerning the objectives, the problem to solve is how to bind variables onto registers in such a way that as many structural components as possible would possess C-path and O-path. tradeoffs between area and testability. The controllability gain is intended to measure the effect of a merge on the controllability of the whole circuit. As mentioned earlier, merging a non-controllable variable with a controllable one into a register makes this register and the downstream f.u input port connected to it by a transfer both controllable. Therefore, controllability gain is expressed as a linear combination of:

the number of f.u.s that this merge would make controllable, -the number of f.u.s' inputs made controllable while the f.u remains non-controllable,

the number of registers made controllable,

the difference of sequential depth between these two registers, -a priority factor taking into account the controllability nature of the two registers. For instance , a high coefficient is given if this coupling breaks a sequential loop.

Observability gain is computed in a similar way. The interested reader can refer to [START_REF] Flottes | High Level Synthesis for Easy Testability[END_REF] for details on gain computation. Table 3 gives the results of register allocation for the Differential Equation example after an allocation taking no account of testability (i.e. b=0) and an allocation including testability (a=b=1) using the above algorithm. In the first case, register Reg8, assigned only to variable h, is neither controllable nor observable. In the second case, each register is controllable and observable. Consequently any test pattern can be justified on primary inputs and any test response can be observed on the primary outputs, from each f.u and register ports. The pseudo-code describing the possible transfer sequence for testing the MULT1 f.u (its C-Path and O-Path) is given below:

If a wiring model allowing to share interconnections is chosen (e.g. a bus based model), hardware sharing possibilities can also be sought either to enhance or to guarantee testability. In the first case, an interconnect network maximizing the number of testable points is generated while keeping the number of connections to a minimum. In the second case, all the points are made testable while adding as few extra connections as possible. Arguments and method are similar to those used for register allocation.

V Results

This test/synthesis method has been applied to four behavioral synthesis benchmarks. Their characteristics before register allocation are given in Table 4. Tseng's example is borrowed from [START_REF] Tseng | Automated Synthesis of Data Paths in Digital Systems[END_REF], the differential equation example from [START_REF] Paulin | Scheduling and binding algorithm for high level synthesis[END_REF], the AR filter from [START_REF] Jain | Experience with ADAM synthesis system[END_REF] and the elliptical filter (EW) from [START_REF] Dewilde | Parallel and pipelined VLSI implementation of signal processing algorithms[END_REF]. Columns 2 to 7 show respectively the number of control steps, f.u.s, variables, constants and primary inputs outputs. Columns 8 and 9 give the number of controllable and observable variables. All the designs have a constant bitwidth. Unfortunately, in the first two HLS examples, the operations are only additions, subtractions and multiplications which do not demonstrate our purposes as they are implemented by transparent f.u.s. For illustration purposes on transparency, we replaced the subtracters by modules which are neither C-transparent nor O-transparent -actually we replaced the "subtracters" by "multipliers" where only the n/2 most significant bits are used-. In the two filters, multipliers are used for implementing multiplications by constants. As a consequence, and according to the assumption on controllability, there is no way to make their outputs and downstream registers controllable. Thus, some of the f.u.s of these examples present transparency bottlenecks at behavioral level and at gate-level as well.

The examples were synthesized with point-to-point style interconnections. A one level of multiplexers network was used to connect the modules. In this model, no connection sharing possibilities can be used to enhance testability. The improvement is only due to register allocation.

Area comparisons are reported in Table 5 while testability results are given in Table 6 where the two lines associated to each benchmark correspond respectively to a synthesis style without testability constraint (w/o test) and with testability constraint (with test). Columns 3 to 7 in Table 5 show respectively the number of registers, multiplexers, multiplexers' inputs, wires and point-topoint wires. It must be noticed that areas are roughly the same. In order to improve the evaluation of the designs produced by our behavioral synthesis system and to compare actual testability criteria with ours, we expanded our RT-designs into gate-level designs and used the commercial SATPG tool Sunrise [START_REF]Testgen" reference manual[END_REF]. Table 7 gives SCOAP based testability results at gate-level. Column 4 gives the number of nodes with SCOAP testability measure between 0 and 10, column 5 gives the number of nodes with SCOAP testability measure between 10 and 50, etc. ATPG results are reported on the right hand side columns. The results clearly show a good correlation between the metrics we used to orient behavioral synthesis and the actual testability of the designs and the reduction of the number of non testable faults. In the previous experiments, the examples present relatively few design alternatives.

Furthermore, a 100% efficiency is easily obtained due to their small size. In order to demonstrate the sensitivity of our test/synthesis algorithms to user defined constraints (ratio b /a), we have generated larger designs with a higher sequential depth. Therefore, on the same benchmarks, we used registers made with latches instead of flip-flops which lead to larger designs since the compatibility graph is less dense. We kept the same set of f.u.s as before except for the ewf filter, which had three adders instead of two and three multipliers instead of one. The designs were synthesized for various ( b / a ) values. Results are reported in Table 8. For each example, "Original" denotes the synthesized circuit without testability considerations (b=0), while "Testsyn" et "Testsyn1" represent versions in which the ratio testability/area (b /a) was respectively set to 100 and 1. It's well worth noting that the testsyn designs' testability was drastically improved while the area was kept roughly the same moreover, testability evolved in the same direction as the ratio b / a as was expected.

We expanded four of these designs to gate-level and ran sequential ATPG on them. The results are reported in Tables 9 and10. The second column indicates the maximum allowed CPU time per fault. The number of aborted faults is computed on the reduced fault list (i.e. after fault equivalence checking). This experiment demonstrates that the designs obtained by taking testability into account are far more easy to test than those without testability. This table shows that the CPU time, to obtain the same ATPG efficiency, is considerably shortened for the testsyn designs.

Finally we compared this HLSFT method with a classical DFT method (namely partial scan).

On a collection of examples, we used the automatic partial scan chain extraction tool from the Sunrise suite [START_REF]Testgen" reference manual[END_REF]. This tool is ATPG driven. We used this tool on "original" designs and constrained it to achieve the same fault coverage as in the testsyn designs.

Firstly, the area overhead (as estimated with the Synopsys [START_REF]Synopsys reference manual : "design analyzer[END_REF] on 1.0. micron technology) ) is on average 5% for testsyn designs versus 9% for partial scan designs (for information, the full scan versions of original designs present an average area overhead of 19.5%).

Secondly, considering test application time, the average ratio (time for partial scan design / time for testsyn design) is 24.93 with a maximum of 58.41. Nevertheless, on one example, test application time is a little bit shorter for the partial scan design than for the testsyn one (ratio 0.9).

Finally, concerning CPU time, the scan chain extraction requires several additional CPU hours (or even days) due to the necessity of SATPG runs, while HLSFT needs just a few seconds more than standard HLS.

VI Conclusion and directions for future research

The methods presented here demonstrate how the design testability can be questioned and improved during behavioral synthesis. Such an approach may avoid or at least simplify the prevalent approach where testability issues are considered at gate level as it is based on a testability analysis method working at different abstraction levels of the circuit specification. Two synthesis tasks (register binding and interconnect generation) have been explored for taking into account testability criteria. Results show a drastic improvement both on the testability of the final circuit and on the effectiveness of SATPG.

Experiments show that this HLSFT method is a valuable alternative to classical gate-level DFT techniques. From the present version of the system, a number of improvements and extensions are possible.

Presently, the coefficients used during register allocation -area and test weights as well as coefficients used in the linear function of controllability and observability gain-are static. In a future version, these coefficients will be dynamically tuned depending on the remaining testability problems, for instance it may be misleading to give a non null coefficient to controllability gain while the remaining problems concern observability.

Functional units allocation and binding as well as scheduling will also be questioned since they affect the number and nature of data transfers from which testability is predicted.

As long as a point is identified to be testable by the testability analysis method (in which case justification and propagation paths are given), there is no need to use a SATPG to find test patterns and to generate a test plan. Future research will be devoted to the study of the quality of such a generated test plan and its implementation within the controller.

Finally, the extension of this method to partial scan is currently under development which will imply new modifications of the allocation/binding algorithms.

Figure 1 .

 1 Figure 1. Loops in datapaths It's worth noting that the difficulty of propagating test data through datapath components is addressed only in few of the works referred above.

Figure 2 Figure 3 .

 23 Figure 2. Target architecture

  will serve as a support for illustrating this classification. Non-controllable variables are iteratively clustered into three classes. These classes are successively built up starting from (1) the class of non-controllable variables because they are only fed by not C-transparent f.u.s (e.g. variables h, a), continuing by[START_REF] Cheng | A Partial Scan Method for Sequential Circuits with Feedback[END_REF] the class of variables that would become controllable if some of the variables of the previous class were made controllable (e.g. variables g, j), and ending by (3) the class of remaining variables. This last class contains first, (3.1) the variables belonging to strongly closed loops (e.g. variable f) and second, (3.2) the variables that would become controllable if some of the variables of (3.1) were made controllable (e.g. variable l). This allows the set of strongly closed loops to be limited to the those containing only transparent f.u.s. The variables belonging to strongly closed loops containing non-transparent f.u.s are included in the first two classes (e.g. variables a, g) since even if such loops were open the concerned variables would still remain non-controllable.

Figure 5 .

 5 Figure 4. DFG with strongly closed loop

Figure 7 .Figure 7

 77 Figure 6. Scheduled DFG

Figure 8 . 2 Figure 9 .

 829 Figure 8. Register allocation for testability : principle Figure9shows how register allocation affects not only the testability of the registers but also of f.u.s, muxes and wires (only controllability is illustrated). A partially hardware mapped algorithmic specification is given in a). Assuming that F.U.1 is not C-transparent, all variables except a and b

  Consequently, breaking cycles (except strongly closed loops) is not targeted, and the sequential depth is only a second rate factor allowing to choose among different assignations of like interest w.r.t. C-paths and O-paths establishment. To take into account testability as well as area, Df a is replaced by aDf a /Df amax +b(Df c /Df cmax + Df o /Df omax ) where Df c (resp. Df o ) is the controllability (resp. observability) gain, Df amax , Df cmax and Df omax are normalization factors. a and b are user defined tuning factors allowing

Table 1 :

 1 Testability characteristics of variables

	var.	y	x	u	b	d	k	e	f	c	h	m	g
	cont.	yes yes yes yes yes yes yes yes yes no	no yes
	obs.	yes yes yes no no yes no	no no	no yes yes

Table 2 :

 2 Testability characteristics of functional units

		Mult1	Mult2	Add	Sub
	input 1 (just. paths)	1	1	2	1
	input 2 (just. paths)	1	1	1	4
	output (prop. paths)	1	0	1	1

Table 3 :

 3 Comparison of registers controllability/observability

		Without testability			With testability
	var.	Reg.	cont.	obs.	var.	Reg.	cont.	obs.
	u	Reg1	yes	yes	u	Reg1	yes	yes
	x	Reg2	yes	yes	x	Reg2	yes	yes
	y	Reg3	yes	yes	y	Reg3	yes	yes
	b,k	Reg4	yes	yes	b,m	Reg4	yes	yes
	d,g	Reg5	yes	yes	d,h	Reg5	yes	yes
	e,c	Reg6	yes	yes	k,f	Reg6	yes	yes
	f,m	Reg7	yes	yes	e,c	Reg7	yes	yes
	h	Reg8	no	no	g	Reg8	yes	yes

Table 4 :

 4 Benchmarks characteristics

	Example	# steps	# f.u.	# var	# constants # Primary	# Primary	# c. var.	# o. var.
						Inputs	Outputs
	tseng	13	2+,2-	11	0	2	1	5	3
	differential	9	1+,1-,2*	12	2	3	1	10	6
	ar filter	21	1+,2*	20	2	4	2	4	6
	ew filter	19	2+,1*	39	3	1	1	2	1

Table 5 :

 5 Area comparison

	Design	synthesis	# reg	# mux	# mux in.	# wires	# wire fanout
		style
	tseng	w/o test	5	7	17	18	67
		with test	5	10	24	21	81
	differential	w/o test	5	9	23	23	79
		with test	5	11	30	25	93
	ar filter	w/o test	9	9	27	27	97
		with test	8	12	36	29	112
	ewf filter	w/o test	12	8	36	25	122
		with test	11	11	54	27	155
	In Table 6, columns 3, 5, 7 and 9 give respectively the number of non controllable (NC)
	registers, f.u.s, wires and mux. inputs. Columns 4, 6, 8, 10 give the number of non observable (NO)
	registers, f.u.s, wires and mux. outputs. The last two columns give respectively the ratio of testable
	registers and f.u.s.

Table 6 :

 6 Designs testability (RT level)

	Design	synthesis	NC reg.	NO	NC f.u NO f.u	NC	NO wire	NC mux	NO mux	Testable	Testable
		style		reg.			wires	fanouts	inputs	outputs	registers	f.u.s
	tseng	w/o test	2	1	2	0	14	25	18	6	3 / 5	2 / 4
		with test	1	1	0	0	6	27	12	8	4 / 5	4 / 4
	differential	w/o test	0	1	0	1	6	23	12	4	4 / 5	3 / 4
		with test	0	0	0	0	6	8	14	2	5 / 5	4 / 4
	ar filter	w/o test	5	5	3	1	28	59	38	12	0 / 9	0 / 3
		with test	0	0	2	0	12	24	12	4	8 / 8	1 / 3
	ewf filter	w/o test	1	11	1	2	6	115	6	16	0 / 12	0 / 3
		with test	0	0	1	0	4	14	12	2	11 / 11	2 / 3

Table 7 :

 7 Designs testability (gate-level)

				Testability measures			Sequential ATPG results
	Design	Synthesis	# Nodes	10	50	100	500	∞	fault coverage for	ATPG CPU time
		style							100% efficiency	(in sec.)
	tseng	w/o test	437	0	349	49	0	39	95.18	11,69
		with test	501	0	446	26	0	29	96.98	11,66
	differential	w/o test	558	0	322	107	41	88	85.35	41.68
		with test	638	0	330	248	11	49	94.29	34.23
	ar filter	w/o test	792	0	407	15	0	370	56.87	4.68
		with test	849	0	526	62	0	261	66.99	12.68

Table 8 :

 8 Area and testability estimations of designs at RT level

					Area							Testability
	Design		reg	mux	mux	wires	wire	NC	NO	NC	NO	NC	NO wire	NC mux	NO mux
					inputs		fanout	reg.	reg.	f.u.s	f.u.s	wires	fanouts	inputs	outputs
	tseng	Original	7	10	22	23	38	2	4	2	1	5	26	7	7
		Testsyn	7	11	24	24	40	2	0	1	0	4	9	7	2
	differential	Original	8	13	29	30	46	1	1	0	0	4	7	7	2
		Testsyn	8	14	32	31	49	0	0	0	0	3	6	7	2
	ar filter	Original	10	9	28	28	46	6	6	3	1	10	31	14	7
		Testsyn1	10	11	32	30	50	0	2	2	0	4	11	4	2
		Testsyn	9	11	31	29	48	0	1	2	0	4	9	4	2
	ewf filter	Original	19	13	52	42	84	4	18	3	5	9	81	8	13
		Testsyn1	18	14	60	42	91	3	0	3	0	8	10	7	2
		Testsyn	17	21	81	48	111	1	0	3	0	6	9	5	2

Table 9 :

 9 ATPG results: EW filter (Total faults: Original = 3768, TestSyn = 3552)

	Design	CPU limit	Detected	Potentially	Aborted	"Untestable"	Testable Faults	Test	CPU (s)
		per fault	faults	detected	faults	faults	Coverage	Efficiency
	Original	1 sec	3213	28	63	489	97.98	98.24	462
	TestSyn	1 sec	3166	35	37	349	98.84	98.95	116
	Original	100 sec	3228	6	25	511	99.1	99.23	10573
	TestSyn	100 sec	3171	0	0	381	100	100	726
	Original	200 sec	3197	3	14	514	99.5	99.57	19691
	TestSyn	200 sec	3171	0	0	381	100	100	726

Table 10 :

 10 ATPG results: Differential equation (Total faults: Original = 1926 , TestSyn = 2022)

	Design	CPU per	Detected	Potentially	Aborted	"Untestable"	%Testable Faults	Efficiency	CPU (s)
		fault	faults	detected	faults	faults	Coverage
	Original	1 sec	1252	0	328	177	71.58	74.19	478.8
	TestSyn	1 sec	1650	0	114	181	89.62	90.55	402.3
	Original	100 sec	1739	0	6	181	99.65	99.68	3372
	TestSyn	100 sec	1819	0	6	185	99.02	99.1	1614
	Original	300 sec	1740	0	4	182	99.77	99.79	5003
	TestSyn	300 sec	1835	0	1	186	99.94	99.95	2237

Acknowledgment

The authors wish to thank the reviewers for their suggestions and comments. References