Dominique Dehay

Limiting distributions for explosive PAR(1) time series with strongly mixing innovation

Keywords: Parameter estimation, Explosive autoregressive time series, Periodic models, Strong mixing 62M10, 62M09

This work deals with the limiting distribution of the least squares estimators of the coefficients a r of an explosive periodic autoregressive of order 1 (PAR(1)) time series X r = a r X r-1 +u r when the innovation {u k } is strongly mixing. More precisely {a r } is a periodic sequence of real numbers with period P > 0 and such that P r=1 |a r | > 1. The time series {u r } is periodically distributed with the same period P and satisfies the strong mixing property, so the random variables u r can be correlated.

Introduction

Many man-made signals and data, even natural ones, exhibit periodicities. The nonstationary and seasonal behavior is quite common for many random phenomena as rotating machinery in mechanics (see [START_REF]Cyclostationarity by Examples[END_REF], seasonal data in econometrics and climatology, but also signals in communication theory, biology to name a few (see e.g. [START_REF] Bloomfield | Periodic correlation in Stratospheric ozonz data[END_REF] [START_REF] Gardner | Cyclostationarity : half a century of research[END_REF][START_REF] Serpedin | Bibliography on Cyclostationarity[END_REF]; and references therein). Periodic autoregressive (PAR) models are one of the simplest linear models with a periodic structure. After more than fifty years of study these models and their generalizations (periodic ARMA (PARMA), etc.) remain a subject of investigations of great interest as they can be applied in modeling periodic phenomena for which seasonal ARIMA models do not fit adequatly (see e.g. [START_REF] Adams | Parameter estimation for periodic ARMA models[END_REF][START_REF] Bittanti | Periodic Systems: Filtering and Control[END_REF][START_REF] Francq | Asymptotic properties of weighted least squares estimation in weak PARMA models[END_REF][START_REF] Chui | Seasonality and the order of integration for consumption[END_REF].

It is well known that such linear models can be represented as vectorial autoregressive (VAR) models. However the general results known for VAR models do not take into account the whole periodic structure of the PARMA models [START_REF] Basawa | Large sample properties of parameter estimates for periodic ARMA models[END_REF]; Tia and Grupe 1980) in particular the fact that the innovation can be periodically distributed. Thus specific methods have been developped for PAR and PARMA models.

There is a large amount of publications on the estimation problem for the coefficients of PARMA models essentially whenever the model is stable, that is periodic stationary also called cyclostationary (see e.g. Adams ;[START_REF] Troutman | Some results in periodic autoregressions[END_REF][START_REF] Vecchia | Maximum likelihood estimation for periodic autoregressive moving average models[END_REF]. The unstable case has been also studied when some autoregressive coefficients are in the boundary of the periodic stationary domain (see e.g. Aknouche 2012a, 2012b; Aknouche and Al-Eid 2012; Boswijk andFranses 1995, 1996; Ghyshels and Osborn 2001 and references therein).

There are few results concerning explosive PAR model. [START_REF] Aknouche | Knife edge effect in strong periodic autoregressions[END_REF] studies the case of explosive PAR models driven by a periodically distributed independent innovation. However the independence of the innovation is too stringent in practice (see e.g. [START_REF] Aknouche | Quasi-maximum likelihood estimation of periodic GARCH and periodic ARMA-GARCH processes[END_REF]Francq et al. 2011 and references therein).

In this work we relax the independence condition, and for simplicity of presentation, we consider periodic autoregressive of order 1 time series that is PAR(1) models. To state the convergence in distribution of the estimators (Theorems 1 and 2) we impose that the periodically distributed innovation is strongly mixing (see e.g. [START_REF] Bradley | Basic properties of strong mixing conditions. A survey and some open questions[END_REF]). Thus it can be correlated and it satisfies some asymptotic independence between its past and its future (see condition (M) in Section 4). However there is no condition on the rate of the asymptotic independence. This is similar to what [START_REF] Phillips | Time series regression with a unit root[END_REF] showed for the autoregressive time series with a unit root and constant coefficients.

Here we study the least squares estimators (LSE) of the PAR(1) coefficients, and the limiting distributions stated in Theorem 1 below generalize the results obtained by [START_REF] Monsour | On Limiting Distributions in Explosive Autoregressive Processess[END_REF] for explosive AR models with independent Gaussian innovation (see also [START_REF] Anderson | On asymptotic distributions of estimates of parameters of stochastic difference equations[END_REF][START_REF] Stigum | Asymptotic properties of dynamic stochastic parameter estimates (III)[END_REF]) and by [START_REF] Aknouche | Knife edge effect in strong periodic autoregressions[END_REF] for explosive PAR models with independent innovation. The rate of convergence of the estimators depends on the product of the periodic PAR(1) coefficients of the PAR(1) model (Theorem 1). Actually this product determines whether the model is stable, unstable or explosive. Thus it is subject of great interest and we takle the problem of its estimation. For this purpose we consider two estimators : the product of the LSE of the PAR(1) coefficients (see [START_REF] Aknouche | Knife edge effect in strong periodic autoregressions[END_REF]) for independent innovation), and a least squares estimator (Theorem 2). By simulation we detect no specific distinction between these estimators for the explosive PAR(1) models. The theoretical comparison of the limiting distributions of the two estimators is out of the scope of the paper and will be subject to another work.

The paper is organized as follows. In Section 2 the model under study is defined as well as the notations. Then the asymptotic behaviour as n → ∞ of the scaled vector-valued time series φ -n X nP +r : r = 1, . . . , P is stated in Section 3 where φ is the product of the periodic coefficients a r of the explosive PAR(1) model, thus |φ| > 1. The period is P > 0. Section 4 deals with the consistency of the least squares estimators a r of the PAR coefficients a r , r = 1, . . . , P , as well as the limiting distributions of the scaled errors φ n ( a ra r ), as n → ∞. Next in Section 5 we consider the problem of estimation of the product φ. The asymptotic behaviour of the estimators introduced in this paper are illustrated by simulation in Section 6. For an easier reading and understanding of the statements of the paper, the proofs of the results are presented in Appendix.

Background : PAR(1) time series

Consider the following PAR(1) model

X k = a k X k-1 + u k , k = 1, 2, . . . , (1)
where {a k } is a periodic sequence of real numbers and {u k } is a real-valued periodically distributed sequence of centered random variables defined on some underlying probability space (Ω, F, P). We assume that the periods of {a k } and of {u k } have the same value P > 0. Thus a P +r = a r and L[u P +s , . . . , u P +r ] = L[u s , . . . , u r ] for all integers s and r. To be short, in the sequel the sequence {ǫ k } is called innovation of the model although it is not necessarily uncorrelated. Denote

X nP +r = A r 1 X nP + U (r) n = A r 1 φ n X 0 + Z n-1 + U (r) n (2)
where

U (r) n := r s=1
A r s+1 u nP +s , Z -1 := 0 and for n ≥ 1

Z n := n l=0 φ -l-1 P s=1 A P s+1 u lP +s = n l=0 φ -l-1 U (P ) l .
Note that the sequence U

n , . . . , U (P ) n

: n ∈ Z is strictly stationary (stationarily distributed).

If |φ| < 1, the model is stable and X nP +r converges in distribution to some random variable ζ (r) as n → ∞. If |φ| = 1, the model is unstable : its behaviour is similar to a random walk; indeed for each r, the time series {X nP +r } is a random walk when the innovation {u k : k > nP + r} is independent with respect to the random variable X nP +r . Henceforth we assume that the time series {X k } satisfies the PAR(1) equation ( 1) with |φ| > 1. We also assume that the initial random variable X 0 is square integrable. Moreover the innovation {u k } is centered periodically distributed with second order moments. Thus {u k } is periodically correlated (see [START_REF] Hurd | On AR(1) models with periodic and almost periodic coefficients[END_REF]) and we have

E[U (r) n ] = 0 as well as cov U (r 1 ) n 1 , U (r 2 ) n 2 = r 1 s 1 =1 r 2 s 2 =1 A r 1 s 1 +1 A r 2 s 2 +1 cov u s 1 , u (n 2 -n 1 )P +s 2
for all integers n, n 1 ≤ n 2 , and r, r 1 , r 2 = 1, . . . , P . Denote σ r := var[u r ] and

K (r) n := cov U (r) l , U (r)
l+n .

Explosive asymptotic behaviour of the model

In the forthcoming proposition we study the asymptotic behaviour of the time series {X k }. Recall that we assume that |φ| > 1.

Proposition 1 For any r = 1, . . . , P

lim n→∞ φ -n X nP +r = A r 1 (X 0 + ζ)
a.s. and in q.m.

where

ζ := lim n→∞ Z n = lim n→∞ n l=0 φ -l-1 U (P ) l
a.s. and in q.m.

Moreover

lim n→∞ L [X nP +r -φ n A r 1 (X 0 + ζ) : r = 1, . . . , P ] = L U (r) 0 -A r 1 ζ : r = 1, . . . , P .
Remarks 1) Assume that Pr[X 0 + ζ = 0] = 0, then conditionally that X 0 + ζ = 0, the sequence {|X k |} converges to infinity almost surely as k → ∞. Thus conditionally that X 0 + ζ = 0, the paths of the time series {X k } are explosive.

2) When X 0 = -ζ almost surely, the time series {X k } which follows the PAR(1) model with |φ| > 1, is periodically distributed and satisfies the following stable PAR(1) equation

X k = a -1 k X k-1 + u * k
where {u * k } is some periodically distributed time series. More precisely 3) To state the convergence in quadratic mean in Proposition 1 we can easily replace the assumption that the innovation {u k } is periodically distributed by the less stringent one that the innovation is periodically correlated.

u * nP +r = A r-1 1 (a r -a -1 r ) ∞ l=0 φ -l-1 U (P ) n+l + U (r-
4) When the innovation {u k } is uncorrelated and periodically distributed we obtain that

E (Z n -ζ) 2 = φ -2n K (P ) 0 φ 2 -1 and var [ζ] = K (P ) 0 φ 2 -1 , with K (P ) 0 = P s=1 (A P s+1 ) 2 σ s .
4 Least squares estimation of the coefficients Now we deal with the estimation problem of the coefficients a r , r = 1, . . . , P, from the observation X k , k = 0, . . . , nP , as n → ∞. For that purpose we determine the periodic sequence {b k } that minimizes the sum of the squared errors

nP k=1 X k -b k X k-1 2 = P r=1 n-1 j=0 X jP +r -b r X jP +r-1 2 .
Since X jP +r = a r X jP +r-1 + u jP +r , for j = 0, . . . , n -1, and r = 1, . . . , P , the least squares estimator (LSE) of a r is defined by

a r := n-1 j=0 X jP +r-1 X jP +r n-1 j=0 (X jP +r-1 ) 2 = a r + n-1 j=0 X jP +r-1 u jP +r n-1 j=0 (X jP +r-1 ) 2 = a r + C (r) n B (r) n ,
where from expression (2) we can write

B (r) n := n-1 j=0 X jP +r-1 2 = n-1 j=0 A r-1 1 φ j (X 0 + Z j-1 ) + U (r-1) j 2 (3)
and

C (r) n := n-1 j=0 X jP +r-1 u jP +r = A r-1 1 n-1 j=0 φ j (X 0 + Z j-1 )u jP +r + n-1 j=0 U (r-1) j u jP +r . (4)
Here U (0) j := 0.

Note that under Gaussian and independence assumptions on the periodically distributed innovation {u k }, the LSE a r coincides with the maximum likelihood estimator of a r .

To prove the convergence in distribution of the scaled errors in the following results we use the next strong mixing condition. The notion of strong mixing, also called α-mixing, was introduced by [START_REF] Rosenblatt | A central limit theorem and a strong mixing condition[END_REF] and it is largely used for modeling the asymptotic independence in time series. The condition could be weakened using the notion of weak dependence, but this is out of the scope of the paper. For more information about mixing time series and weak dependence see e.

F k := F(X 0 , u j : j ≤ k) and F k+n := F(u j : j ≥ k + n).
Furthermore, in the following we assume that the underlying probability space (Ω, F, P) is sufficiently large so that there is a sequence of real valued random variables {u * k } which is independent with respect to X 0 and the innovation {u k }, and such that L u * 0 , . . . , u * nP -1 = L [u nP , . . . , u 1 ] for any integer n > 1. This is always possible at least by enlarging the probability space. Now we state the strong consistency of the LSE a r of a r , as well as the asymptotic limiting distribution of the scaled error φ n a r -a r for the explosive PAR(1) model ( 1).

Theorem 1 Conditionally that X 0 + ζ = 0, the least squares estimator a r converges to a r almost surely as n → ∞, for r = 1, . . . , P . Furthermore assume that P[X 0 +ζ = 0] = 0 and the mixing condition (M) is fulfilled, then the random vector of the scaled errors φ n a ra r : r = 1, . . . , P converges in distribution to

(φ 2 -1)ζ * r A r-1 1 (X 0 + ζ) : r = 1, . . . , P
as n → ∞. The random variable ζ is defined in Proposition 1, the random vector ζ * 1 , . . . , ζ * P is independent with respect to (X 0 , ζ), and its distribution is defined by

L [ζ * r : r = 1 . . . , P ] = L   ∞ j=1 φ -j u * jP -r : r = 1, . . . , P  
where the sequence {u * k } is independent with respect to X 0 and {u k }, and such that

L u * 0 , . . . , u * nP -1 = L [u nP , . . . , u 1 ] for any integer n > 1.
Note that in general the limiting distribution of φ n ( a ra r ) is not parameter free, that is, it depends on the parameters we are estimating. Under Gaussian assumption on the periodically distributed innovation {u k }, the random variables ζ and ζ * r are Gaussian and independent, so the distribution of ratio ζ * r /ζ is a Cauchy distribution (see also [START_REF] Aknouche | Knife edge effect in strong periodic autoregressions[END_REF]. In fact, the limiting distributions in Theorem 1 have heavy tails.

Estimation of φ

To estimate φ, the product of the coefficients a r , r = 1, . . . , P , we can consider the product of the estimators a r :

φ = P r=1 a r .
Then from Theorem 1, the estimator φ converges almost surely to φ conditionally that X 0 + ζ = 0. Thanks to the Delta-method (Theorem 3.1, Van der Vaart 1998) we readily deduce the asymptotic law of the normalized error

φ n φ -φ . lim n→∞ L φ n φ -φ = L φ 2 -1 X 0 + ζ × P r=1 A P r+1 ζ * r
when we assume that P[X 0 + ζ = 0] = 0 and the mixing condition (M) is fulfilled. See (Aknouche 2013) for independent innovation.

Besides, we can define a least squares estimator of φ. For that purpose, note that from relation [START_REF] Adams | Parameter estimation for periodic ARMA models[END_REF] and the periodicity of the coefficients, we obtain for all j ∈ N * and r = 1, . . . , P , that X jP +r = φX (j-1)P +r + V Since the innovation {u k } is periodically distributed with the same period P , the sequence V

(1) j , . . . , V (P ) j

: j ∈ Z is strictly stationary (stationarily distributed). Then minimizing the sum of the squared errors

nP k=P +1 X k -bX k-P 2 = n-1 j=1 P r=1 X jP +r -bX (j-1)P +r 2 ,
we define the least squares estimator φ as

φ := nP k=P +1 X k X k-P nP k=P +1 (X k-P ) 2 = φ + C n B n
where

C n = n-1 j=1 P r=1 X (j-1)P +r V (r) j and B n = nP k=P +1 (X k-P ) 2 = n-1 j=1 P r=1 X (j-1)P +r 2 .
Then following the same arguments as for the LSE a r , we can state the forthcoming result.

Theorem 2 Conditionally that X 0 + ζ = 0, the least squares estimator φ converges to φ almost surely. Assume that P[X 0 + ζ = 0] = 0 and the mixing condition (M) is fulfilled, then the scaled error φ n φφ converges in distribution

lim n→∞ L φ n φ -φ = L (φ 2 -1)ζ * P r=1 A P r+1 -2 (X 0 + ζ) (5)
conditionally that X 0 + ζ = 0, as n → ∞. Here ζ * is a random variable independent with respect to X 0 and ζ. The distribution of ζ * coincides with the distribution of

P r=1 P -1 k=0 A P r+1 A r r-k+1 ∞ j=1 φ -j u * jP -r+k .
In the next section we see by simulation that the distributions of φ and of φ seem to be similar when |φ| > 1. The theoretical comparison of these distributions is out of the scope of the paper.

Simulation

Here we present the simulations of some explosive PAR(1) time series, and we illustrate the behaviour of the LSE a r , φ and of φ for different values of the coefficients a r , r = 1, . . . , P and for different types of innovation. For that purpose we consider the PAR(1) model ( 1) with period P = 6. The periodic coefficients a r s are given in Table 1.

u k = cos πk 3 v k where v k = 1 √ m + 1 m i=0 ǫ k+i ,
the random variables ǫ k , k ∈ N, are independent and identically distributed, and m ∈ {0 , 2000}. When m = 0, we have v k = ǫ k , k ∈ N, and the random variables u k are periodically distributed and independent. When m = 2000, the random variables u k are periodically distributed and correlated. Actually they are m-dependent, thus strongly mixing. We consider two distributions for the ǫ k s : the standard normal distribution N (0, 1), and the uniform distribution U [-1000, 1000]. Hence in the last case the distribution of the ǫ k s is spread out.

To sum up, for each family of coefficients, we obtain four PAR(1) time series that we simulate with different lengths T = nP = 6n. In each case we perform 100 replications. The algorithm of the simulation is implemented in 'R' software code. Below we present some of the tables and histograms that we obtain to compare the results. In each table we write down the mean and the median of the values of each estimator that we have obtained from the 100 replications, as well as some box-plot characteristics of the errors : extrem of upper whishers, upper hinge (3rd quarter), lower hinge (1rt quarter) and extrem of the lower whishers. We also give the 95% percentiles of the absolute values of the errors. First we not that the rates of convergence of the estimates decrease with |φ| (see Tables 2,3, 4, 7 and 8). Actually, from the theoretical point of view, the rate of convergence is |φ| n when |φ| > 1 (Theorems 1 and 2 above). It is n when |φ| = 1 (Boswijk and Franses 1995) and n 1/2 when |φ| < 1 (Basawa and Lund 2001). Thus we produce the histograms of scaled errors, the scale factor being φ -n when |φ| > 1, n -1 when φ = 1 and n -1/2 when |φ| < 1.

We observe when φ = 1.4256 and when φ = 1.0164 in Figures 1, 2, 3, 4 and 5, that the histograms of the scaled errors have long tails. In Tables 2, 3, 4, 5 and 6, we note that the ratios of the hinges (upper hinge, lower hinge) to the sigmas of the errors are of order of magnitude 10 -1 or less. It is the same for the ratios of the hinges to the whiskers. These phenomena correspond to the fact that the limiting distributions have heavy tails. See (Aknouche 2013) for independent innovation. When φ = 1, in Figure 6 and in Table 7 we observe the distributions for some estimates ( a 1 , a 3 , a 6 , φ) have also relatively long tails. But the phenomenon is very less apparent than previously. See [START_REF] Phillips | Time series regression with a unit root[END_REF]) for the autoregressive model with a unit root.

When φ = 0.972, in Figure 7 the tails of the histograms are shorter than for the others values of φ. In Table 8 the hinges and the whishers are often with the same order of magnitude or larger than the sigmas. This fits to the theoretical result, the limiting distribution being Gaussian [START_REF] Basawa | Large sample properties of parameter estimates for periodic ARMA models[END_REF].

When the innovation {u k } is correlated with m = 2000 for φ = 1.0162, in Table 5 we observe few change in the performances of the estimates with respect to the case when the innovation is independent (Table 4). The confidence intervals are smaller for a 3 = 1, and larger for a 4 = 1.5. However in Figure 4 with φ = 1.0164 and m = 2000, the tails of the histograms are farther from 0 than in Figure 3 when

m = 0.
Finally, comparing the statistics of the errors of the two estimates φ and φ in each table, we find out that they have globally the same order of magnitude whenever |φ| > 1 and the histograms are quite similar. However when |φ| ≤ 1 it seems that φ gives better results than φ. The comparison of these two estimators need more investigation to determine whether one of them is better than the other.

Conclusion

In this paper we have studied the least squares estimators of the coefficients of explosive PAR(1) time series under relatively weak dependence assumptions. It is quite interesting to see how heavy tailed distributions enter in this context. We have also constructed two estimators of the product of these coefficients, which characterizes the explosive behaviour of the model. It would be worth to investigate the comparison of these estimators and also to consider more general PAR and PARMA models.

(P ) l + 2 k-1 l 1 =j k l 2 =l 1 +1 φ -l 1 -l 2 -2 cov U (P ) l 1 , U (P ) l 2 ≤ φ -2j K (P ) 0 φ 2 -1 + 2 φ -2j K (P ) 0 (φ 2 -1)(|φ| -1) = φ -2j K (P ) 0 (|φ| -1) 2 . (6)
Then the sequence {Z n } is a Cauchy sequence in the Hilbert space L 2 (P), thus this sequence converges to some random variable ζ in quadratic mean. Moreover

E (Z n -ζ) 2 ≤ φ -2n K (P ) 0 (|φ| -1) 2 .
From the exponential decreasing to 0 of the right hand side of the last inequality, we can readily deduce the convergence almost sure following the usual method applying Borel Cantelli lemma.

As for the second part of the proposition, note that and

X nP +r -φ n A r 1 (X 0 + ζ) = U (r) n + φ n A r 1 (Z n-1 -ζ)
φ n (Z n-1 -ζ) = - ∞ l=n φ n-l-1 U (P ) l = - ∞ l=0 φ -l-1 U (P ) n+l .
Since the sequence of random vectors {(U 1 n , . . . , U

(P ) n ) : n ∈ Z} is stationarily dis- tributed, we deduce that L U (r) n , ∞ l=0 φ -l-1 U (r) n+l : r = 1, . . . , P = L U (r) 0 , ∞ l=0 φ -l-1 U (r) l : r = 1, . . . , P .
Then from the definition of ζ, we readily achieve the proof of Proposition 1 .

Proof of Theorem 1

First in the two following lemmas we study the asymptotic behaviours of B

n and

C (r) n . Lemma 1 lim n→∞ φ -2n B (r) n = A r-1 1 2 φ 2 -1 (X 0 + ζ) 2
a.s. and in L 1 (P).

Proof We have seen that that φ -n X nP +r-1 converges to A r-1 1 (X 0 +ζ) almost surely and in quadratic mean. Then Toeplitz lemma on series convergence gives the result. Proof To prove the lemma we study the left hand side of equality (4).

1) For the last term of equality (4), Cauchy Schwarz inequality entails

E   n-1 j=0 U (r-1) j u jP +r   ≤ n-1 j=0 E U (r-1) j 2 1/2 E u jP +r 2 1/2 .
As the sequences {u jP +r } and {U u jP +r = 0 a.s.

2) To study the first term of left hand side of equality (4) the idea is first to isolate the sums of Z j-1 and of u jP +r . Then define blocks that separate the first and the last terms of the time series in order to be able to use the asymptotic independence which is given by the strong mixing condition on the innovation. Thus assume without lost of generality that n is a multiple of 4 and let n 1 = n/4, and n 2 = n/2. Then we can write (i) Thanks to inequality [START_REF] Aknouche | Quasi-maximum likelihood estimation of periodic GARCH and periodic ARMA-GARCH processes[END_REF] we have

n-1 j=0 φ j (X 0 + Z j-1 )u jP +r = n-1 j=0 φ j (Z j-1 -Z n 1 )u jP +r + n 2 -1 j=0 φ j (X 0 + Z n 1 )u jP +r + n-1 j=n 2 φ j (X 0 + Z n 1 )u jP +r . (7)
E   n-1 j=0 φ j (Z j-1 -Z n 1 )u jP +r   ≤ n-1 j=0 |φ| j E |Z j-1 -Z n 1 | 2 1/2 E |u jP +r | 2 1/2 ≤ n 1 j=0 |φ| j E |Z j-1 -Z n 1 | 2 1/2 σ r + n-1 j=n 1 +1 |φ| j E |Z j-1 -Z n 1 | 2 1/2 σ r ≤ n 1 + 1 + |φ| n-n 1 |φ| -1 K (P ) 0 σ r . Hence lim n→∞ φ -n n-1 j=0 φ j (Z j-1 -Z n 1 )u jP +r = 0 in L 1 (P).
Using Borel Cantelli lemma, the exponential decreasing rate of convergence permits to prove the almost sure convergence. (ii) Besides, the second term of the right hand side of equality ( 7) can be estimated as follows

E   (X 0 + Z n 1 ) n 2 -1 j=0 φ j u jP +r   ≤ E |X 0 + Z n 1 | 2 1/2 n 2 -1 j=0 |φ| j E |u jP +r | 2 1/2 ≤   E |X 0 | 2 1/2 + n 1 -1 j=0 |φ| -l-1 E |U (P ) l | 2 1/2     n 2 -1 j=0 |φ| j E (u jP +r ) 2 1/2   ≤ E |X 0 | 2 1/2 (|φ| -1) + K (P ) 0 σ r |φ| n 2 (|φ| -1) 2 . Thus lim n→∞ φ -n (X 0 + Z n 1 ) n 2 -1 j=0 φ j u jP +r = 0 in L 1 (P).
As in part (i), we obtain the almost sure convergence.

(iii) It remains to study the asymptotic behaviour of (X 0 + Z n 1 )Ψ n,r n 2 where We know that X 0 + Z n 1 converges to X 0 + ζ almost surely and in quadratic mean.

Ψ n,r n 2 := φ -n n-1 j=n 2 φ j u jP +r = n-1 j=n 2 φ j-n u jP +r = n-n 2 j=1 φ -j u (n-j)P +r . (8)
(Proposition 1). Since

E |Ψ n,r n 2 | 2 1/2 ≤ n-n 2 j=1 |φ| -j E |u (n-j)P +r | 2 1/2 ≤ σ r |φ| -1 , φ -n Ψ n,r
n 2 converges to 0 in quadratic mean and also almost surely. Hence φ -n (X 0 + Z n 1 )Ψ n,r n 2 converges to 0 in L 1 (P) and almost surely. (iv) Now we establish the convergence in distribution of (X 0 + Z n 1 )Ψ n,r n 2 . Note that (X 0 +Z n 1 ) can be expressed with X 0 , u 1 , u 2 , . . . , u (n 1 +1)P while Ψ n,r n 2 can be expressed with u n 2 P , . . . , u nP . Hence, as n 1 = n 2 /2 = n/4, the mixing property entails that

P X 0 + Z n 1 ∈ A, Ψ n,r n 2 ∈ B -P X 0 + Z n 1 ∈ A P Ψ n,r n 2 ∈ B ≤ α (n/4 -1)P
for all Borel subsets A and B of R, where α(•) is the strong mixing coefficient. The mixing hypothesis entails that α (n/4 -1)P ) tends to 0 as n goes to ∞, thus lim n→∞ P X 0 + Z n 1 ∈ A, Ψ n,r n 2 ∈ B -P X 0 + Z n 1 ∈ A × P Ψ n,r n 2 ∈ B = 0. for all Borel subsets A and B. So X 0 + Z n 1 and Ψ n,r n 2 are asymptotically independent. We know that X 0 + Z n 1 converges in quadratic mean so in distribution to X 0 + ζ (Proposition 1). Now it remains to study the behaviour of Ψ n,r n 2 .

Proof of Theorem 2

Theorem 2 is a direct consequence of the following lemma about the asymptotic behaviours of B n and C n . Using the fact that φ -1 A r-1 1 = A P r -1 , we deduce limit [START_REF] Basawa | Large sample properties of parameter estimates for periodic ARMA models[END_REF].

2) The convergence almost sure and in L 1 (P) of φ -2n C n to 0, can be easily obtained following the lines of the proof of the convergence almost sure and in L 1 (P) of φ -2n C (r) n in Lemma 2. Thus the proof is left to the reader.

3) From its definition, C n can be expressed by

C n = P r=1 A r 1 n-2 j=0 φ j X 0 + Z j-1 V (r) j+1 + P r=1 n-2 j=0 U (r) j V (r) j+1 . (11)
(i) Thanks to the stationarity of the sequences U (ii) Following the same lines as in the proof of Lemma 2, and using the stationarity of V

The mixing hypothesis (M) entails that X 0 + Z n 1 and Ψ n n 2 are asymptotically independent. Besides the distribution of k } is independent with respect to X 0 and {u k }, thus the sequence {Ψ n } is also independent with respect to X 0 and {u k }. Since the sequence {u * k } is centered periodically distributed with second order moments, the sequence {Ψ * n } converges almost surely and in quadratic mean to some random variable ζ * . Thanks to the definition (12) of Ψ n n 2 and the periodicity of the distribution of the innovation {u k }, we deduce the distribution of ζ * . Then limit [START_REF] Bittanti | Periodic Systems: Filtering and Control[END_REF] is proved.

a j for 1 ≤ 1 = A r 1 φ

 111 s ≤ r, and A r s := 0 otherwise and let φ := A P 1 = P r=1 a r . Since {a k } is periodic with period P > 0, we have A nP +r n and we obtain the decomposition

  g. (Bradley 2005; Dedeker et al. 2007; Doukhan 1994 and references therein). (M) lim n→∞ α(n) = 0 where α(n) = sup P[A ∩ B] -P[A]P[B] , the supremum being taken over all k ∈ N and all sets A ∈ F k , and B ∈ F k+n . Here the σ-fields F k and F k+n are defined by

  u jP +r-k .

20 Figure 1 :

 201 Figure 1: Histograms of the scaled errors : φ = 1.4256, L[ǫr] = N (0, 1), m = 0, n = 20

2 Figure 2 :

 22 Figure 2: Histograms of the scaled errors : φ = 1.0164, L[ǫr] = N (0, 1), m = 0, n = 200

4 Figure 3 :

 43 Figure 3: Histograms of the scaled errors : φ = 1.0164, L[ǫr] = N (0, 1), m = 0, n = 400

8 Figure 4 :u

 84 Figure 4: Histograms of the scaled errors : φ = 1.0164, L[ǫr] = N (0, 1), m = 2000, n = 400

Figure 5 :

 5 Figure 5: Histograms of the scaled errors : φ = 1.0164, L[ǫr] = U[-1000, 1000], m = 0, n = 400

Figure 6 :

 6 Figure 6: Histograms of the scaled errors : φ = 1, L[ǫr] = N (0, 1), m = 0, n = 400

Figure 7 :

 7 Figure 7: Histograms of the scaled errors : φ = 0.972, L[ǫr] = N (0, 1), m = 0, n = 400

- 2 ( 10 ) 2 P r=2 A r- 1 1 2 (

 2102r=212 X 0 + ζ) 2 φ 2 -1a.s. and in L 1 (P);(9)lim n→∞ φ -2n C n = 0 a.s. and in L 1 (P);and lim n→∞ L φ -n C n = L (X 0 + ζ)ζ * . (Proof 1) First note that B n can be expressed as followsB n = P r=2 B (r) n-1 + B (P ) n -(X 0 ) 2 .Then thanks to Lemma 1lim n→∞ φ -2n B n = 1 + φ -X 0 + ζ) 2 φ 2 -1 a.s. and in L 1 (P).

:

  j ∈ Z , the second term of expression (11) is of order of magnitude n in probability.

where n 1 = n 2 / 2 =

 122 0 + Z j-1 V (r) j+1 = X 0 + Z n 1 Ψ n n 2 + o P (1)

2 j=2φ

 2 -j u (n-j+1)P +r-k . coincides with the distribution of Ψ * nand the sequence {u * k } is defined in part 2(v) of the proof of Lemma 2. The sequence {u *

  ; Chaari et al. 2014; Collet and Martinez 2008; Dragan et al. 1982; Franses and Paap 2004;

  and Goodwin 1995; Aknouche and Bibi 2009; Basawa and Lund 2001; Francq et al. 2011; Pagano 1978; Tiao and Grupe 1980

Table 1 :

 1 PAR(1) coefficients

	a1	a2	a3	a4	a5	a6	φ
	family 1 0.8 1.2	1	1.5	1.1 0.9 1.4256
	family 2 0.8 1.1	1	1.5	1.1 0.7 1.0164
	family 3 0.5	1	1	2.5	1.6 0.5	1
	family 4 0.5	1	1.5 1.62 1.6 0.5	0.972

Thus we simulate the cases |φ| > 1, |φ| close to 1, φ = 1 and |φ| < 1. The innovation is defined by

Table 2 :

 2 |φ| = 1.4256 and uncorrelated Gaussian innovation : L[ǫ k ] = N (0, 1), m = 0, n = 20

	parameter	0.8	1.2	1	1.5	1.1	0.9	1.4256
	estimate	a1	a2	a3	a4	a5	a6	φ	φ
	mean	0.8001 1.1999 0.9999 1.4999 1.0999 0.9000 1.4257 1.4256
	median	0.8000 1.1999 1.0000 1.4999 1.0999 0.9000 1.4256 1.4255
	error
	mean	2e-04	-4e-05	-2e-06	-8e-05	-1e-05	7e-06	2e-04	9e-05
	sigma	2e-03	4e-04	8e-06	8e-04	9e-05	9e-05	3e-03	2e-03
	boxplot
	u. whisker	8e-04	2e-04	8e-07	4e-04	6e-05	6e-05	9e-04	8e-04
	u. hinge	3e-04	5e-05	3e-07	9e-05	2e-05	2e-05	3e-04	3e-14
	l. hinge	-2e-04	-7e-05	-4e-07	-2e-04	-2e-05	-2e-05	-2e-04	-2e-04
	l. whisker	8e-04	-2e-04	-9e-07	-5e-04	-6e-05	-5e-05	-7e-04	-8e-04
	percentile
	abs 0.95	4e-03	1e-03	7e-06	2e-03	3e-04	3e-04	4e-03	4e-03

Table 3 :

 3 |φ|

	parameter	0.8	1.1	1	1.5	1.1	0.7	1.0164
	estimate	a1	a2	a3	a4	a5	a6	φ	φ
	mean	0.7965 1.0996 0.9999 1.4986 1.0999 0.7000 1.0131 1.0107
	median	0.7994 1.0999 1.0000 1.4999 1.1000 0.6999 1.0158 1.0154
	error
	mean	-4e-03	-4e-04	-3e-05	-2e-03	-4e-05	4e-05	-4e-03	-6e-03
	sigma	1e-02	2e-03	2e-04	7e-03	5e-04	1e-03	9e-03	3e-02
	boxplot
	u. whisker	4e-03	4e-04	2e-05	2e-03	3e-04	9e-04	4e-03	3e-03
	u. hinge	2e-04	5e-05	5e-06	4e-04	8e-05	3e-04	2e-04	-5e-05
	l. hinge	-3e-03	-3e-04	-4e-06	-1e-03	-9e-05	-3e-04	-3e-03	-2e-03
	l. whisker	-5e-03	-6e-04	-2e-05	-3e-03	-4e-04	-8e-04	-5e-04	-7e-03
	percentile
	abs 0.95	3e-02	3e-03	4e-04	9e-03	7e-04	2e-03	3e-02	5e-02

= 1.0164 and uncorrelated Gaussian innovation : L[ǫ k ] = N (0, 1), m = 0, n = 200

Table 4 :

 4 |φ| = 1.0164 and uncorrelated Gaussian innovation : L[ǫ k ] = N (0, 1), m = 0, n = 400

	parameter	0.8	1.1	1	1.5	1.1	0.7	1.0164
	estimate	a1	a2	a3	a4	a5	a6	φ	φ
	mean	0.7999 1.1000 1.0000 1.5000 1.1000 0.6999 1.0163 1.0163
	median	0.8000 1.0999 1.0000 1.4999 1.0999 0.7000 1.0164 1.0164
	error
	mean	-8e-05	4e-07	4e-07	5e-06	2e-06	-8e-06	-7e-05	-1e-04
	sigma	7e-04	5e-05	3e-06	3e-04	4e-05	1e-04	7e-04	9e-04
	boxplot
	u. whisker	2e-04	2e-05	2e-08	8e-05	2e-05	3e-05	2e-04	2e-04
	u. hinge	5e-05	3e-06	5e-09	2e-05	2e-06	2e-05	5e-05	5e-05
	l. hinge	-4e-05	-8e-06	-6e-09	-4e-05	-4e-06	-6e-06	-4e-05	-5e-05
	l. whisker	-2e-04	-2e-05	-2e-08	-7e-05	-2e-05	-3e-05	-2e-04	-2e-04
	percentile
	abs 0.95	7e-04	8e-05	2e-06	4e-04	5e-05	2e-04	7e-04	8e-04

Table 5 :

 5 |φ|

	parameter	0.8	1.1	1	1.5	1.1	0.7	1.0164
	estimate	a1	a2	a3	a4	a5	a6	φ	φ
	mean	0.7999 1.1000 1.0000 1.5000 1.1000 0.6999 1.0163 1.0163
	median	0.7999 1.1000 1.0000 1.5000 1.1000 0.6999 1.0163 1.0163
	error
	mean	-8e-05	9e-06	-3e-10	5e-05	6e-06	-2e-05	-8e-05	-8e-05
	sigma	7e-04	9e-05	2e-09	4e-04	5e-05	2e-04	7e-04	7e-04
	boxplot
	u. whisker	2e-04	3e-05	5e-12	2e-04	2e-05	5e-05	2e-04	2e-04
	u. hinge	5e-05	9e-06	-2e-12	4e-05	6e-06	2e-05	5e-05	5e-05
	l. hinge	-7e-05	-7e-06	-2e-11	-3e-05	-4e-06	-2e-05	-7e-05	-7e-05
	l. whisker	-2e-04	-3e-05	-4e-11	-2e-04	-2e-05	-5e-05	-3e-04	-3e-04
	percentile
	abs 0.95	9e-04	2e-04	5e-10	5e-04	7e-05	2e-04	9e-04	9e-04

= 1.0164 and correlated Gaussian innovation : L[ǫ k ] = N (0, 1), m = 2000, n = 400

Table 6 :

 6 |φ| = 1.0164 and uncorrelated uniformly distributed innovation : L[ǫr] = U[-1000, 1000],

	m = 0, n = 400
	parameter	0.8	1.1	1	1.5	1.1	0.7	1.0164
	estimate	a1	a2	a3	a4	a5	a6	φ	φ
	mean	0.7991 1.0998 1.0000 1.4996 1.0999 0.7000 1.0156 1.0150
	median	0.7999 1.1000 1.0000 1.5000 1.1000 0.7000 1.0163 1.0163
	error
	mean	-9e-04	-2e-04	1e-06	-4e-04	-2e-05	2e-05	-8e-04	-2e-03
	sigma	6e-03	8e-04	2e-05	3e-03	1e-04	2e-04	6e-03	1e-02
	boxplot
	u. whisker	2e-04	3e-05	4e-08	2e-04	2e-05	4e-05	2e-04	2e-04
	u. hinge	4e-05	8e-06	1e-08	4e-05	5e-06	9e-06	4e-05	4e-05
	l. hinge	-8e-05	-6e-06	-4e-10	-3e-05	-4e-06	-2e-05	-8e-05	-8e-05
	l. whisker	-3e-04	-3e-05	-4e-05	-2e-04	-2e-05	-4e-05	-3e-04	-3e-04
	percentile
	abs 0.95	6e-04	1e-04	7e-06	4e-04	6e-05	2e-04	6e-04	7e-04

Table 7 :

 7 |φ|

	parameter	0.5	1	1	2.5	1.6	0.5	1
	estimate	a1	a2	a3	a4	a5	a6	φ	φ
	mean	0.4948 1.0000 1.0000 2.4372 1.5972 0.5004 0.9944 0.9644
	median	0.4973 1.0000 1.0000 2.4566 1.5978 0.5002 0.9972 0.9765
	error
	mean	-5e-03	-2e-06	1e-05	-6e-02	-2e-03	4e-03	-6e-03	4e-02
	sigma	9e-03	2e-04	4e-04	6e-02	3e-03	6e-04	9e-03	4e-02
	boxplot
	u. whisker	4e-03	8e-05	4e-04	-8e-03	-4e-04	2e-03	5e-03	2e-03
	u. hinge	-4e-04	2e-05	8e-05	-3e-02	-2e-03	8e-04	-5e-04	-2e-02
	l. hinge	-9e-03	-2e-05	-9e-05	-8e-02	-4e-03	4e-05	-1e-02	-5e-02
	l. whisker	-2e-02	-8e-05	-4e-04	-2e-01	-7e-03	-1e-03	-3e-02	-1e-01
	percentile
	abs 0.95	3e-03	5e-04	9e-04	3e-01	8e-03	2e-03	3e-02	2e-01

= 1 and uncorrelated Gaussian innovation : L[ǫr] = N (0, 1), m = 0, n = 400

Table 8 :

 8 |φ| = 0.972 and uncorrelated Gaussian innovation : L[ǫr] = N (0, 1), m = 0, n = 400

	parameter	0.5	1	1.5	1.62	1.6	0.5	0.972
	estimate	a1	a2	a3	a4	a5	a6	φ	φ
	mean	0.4938 1.0000 1.3983 1.5579 1.5765 0.5071 0.9662 0.8612
	median	0.4971 1.0000 1.4055 1.5624 1.5777 0.5072 0.9693 0.8745
	error
	mean	-7e-03	5e-06	-2e-01	-7e-02	-3e-02	8e-03	-6e-03	-2e-01
	sigma	2e-02	5e-04	3e-02	2e-02	4e-03	1e-03	2e-02	6e-02
	boxplot
	u. whisker	2e-02	5e-04	-6e-02	-4e-02	-2e-02	9e-03	2e-02	-3e-02
	u. hinge	3e-03	2e-04	-9e-02	-6e-02	-3e-02	8e-03	4e-03	-8e-02
	l. hinge	-2e-02	-2e-04	-2e-01	-8e-02	-3e-02	7e-03	-2e-02	-2e-01
	l. whisker	-4e-02	-5e-04	-2e-01	-1e-01	-4e-02	7e-03	-3e-02	-2e-01
	percentile
	abs 0.95	3e-02	2e-03	2e-01	1e-01	4e-02	9e-03	3e-02	2e-01

D. Dehay Institut de Recherche Mathématique de Rennes, CNRS umr 6625, Université de Rennes, France e-mail : dominique.dehay@uhb.fr

Appendix

Proof of Proposition 1

Let r = 1, . . . , P be fixed. We know that φ -n X nP +r = A r 1 (X 0 + Z n-1 ) + φ -n U (r)

n . Since the sequence {U r) where X 0 + ζ and ζ * (r) are independent random variables. Furthermore from definition (8), we easily deduce the distribution of the ζ * r s. Following the same lines with Cramér device we can establish the multidimensional convergence.

Proof of Theorem 1. The almost sure convergence is a direct consequence of Lemmas 1 and 2. To prove the convergence in distribution, we first apply Cramér device to prove the convergence in distribution of φ

For this purpose, let α 1 , . . . , α P , β 1 , . . . , β P ∈ R and establish the convergence in distribution of

Following the same method as in the proof of Lemma 2 we define blocks to separate the terms B n , as well as to apply the asymptotic independence given by the strong mixing condition. Denote n 1 = n 2 /2 = n/4. Then S n can be decomposed as

n 1 converges to 0 almost surely. Moreover thanks to the parts 1, 2(i) and 2(ii) of the proof of Lemma 2, it remains to study

Then from the strong mixing condition, B

n 1 , . . . , B

n 1 , X 0 + Z n 1 is asymptotically independent with respect to Ψ n,1 n 2 , . . . , Ψ n,P n 2 , and following the same lines as in the part 2(v) of the proof of Lemma 2 we deduce the convergence in distribution of S n as n → ∞.

Finally the application of the continuous mapping theorem for convergence in distribution completes the proof of the theorem.


Julien Heulot
email: jheulot@insa-rennes.fr

Maxime Pelcat
email: mpelcat@insa-rennes.fr

Jean-Franc ¸ois Nezan
email: jnezan@insa-rennes.fr

Yaset Oliva
email: yoliva@insa-rennes.fr

Slaheddine Aridhi
email: saridhi@ti.com

Shuvra S Bhattacharyya

Just-In-Time Scheduling Techniques for Multicore Signal Processing Systems

This paper introduces a novel multicore scheduling method that leverages a parameterized dataflow Model of Computation (MoC). This method, which we have named Just-In-Time Multicore Scheduling (JIT-MS), aims to efficiently schedule Parameterized and Interfaced Synchronous DataFlow (PiSDF) graphs on multicore architectures. This method exploits features of PiSDF to find locally static regions that exhibit predictable communications. This paper uses a multicore signal processing benchmark to demonstrate that the JIT-MS scheduler can exploit more parallelism than a conventional multicore task scheduler based on task creation and dispatch. Experimental results of the JIT-MS on an 8-core Texas Instruments Keystone Digital Signal Processor (DSP) are compared with those obtained from the OpenMP implementation provided by Texas Instruments. Results shows latency improvements of up to 26% for multicore signal processing systems.

I. INTRODUCTION

An important evolution in embedded processing is the integration of increasingly more Processing Elements (PEs) in the Multiprocessor Systems-on-Chip (MPSoC) devices [START_REF]Multicore Fixed and Floating-Point Digital Signal Processor -SPRS691E, Texas Instruments[END_REF], [START_REF]MPPA MANYCORE: a multicore processors family[END_REF], [START_REF]Epiphany A breakthrough in parallel processing[END_REF], [START_REF] Benini | P2012: Building an ecosystem for a scalable, modular and high-efficiency embedded computing accelerator[END_REF]. This trend is mainly due to limitations in the processing power of individual PEs as a result of power consumption considerations.

Concurrently, signal processing applications are becoming increasingly dynamic in terms of hardware resource requirements. This tendency is due to the growing complexity of algorithms allowing higher levels of performance in aspects such as data compression, transmission efficiency, and precision of data analysis. For example, the Scalable High Efficiency Video Coding (SVC) video codec provides a mechanism to temporarily reduce the resolution of a transmitted video in order to match the instantaneous bandwidth of a network [START_REF] Helle | A scalable video coding extension of HEVC[END_REF].

One of the main challenges of the design of multicore signal processing systems, is to distribute computational tasks efficiently onto the available PEs while taking into account dynamic changes. The process of assigning, ordering and timing actors on PEs in this context is referred to as multicore scheduling. Inefficient use of the PEs affects latency and energy consumption making multicore scheduling a very important problem to solve [START_REF] Marwedel | Mapping of applications to MPSoCs[END_REF].

This paper describes a novel method called JIT-MS to address this challenge. JIT-MS is a flexible scheduling method that determines scheduling decisions at run-time to optimize the mapping of an application onto multicore processing resources. In relation to the scheduling taxonomy defined by Lee and Ha [START_REF] Lee | Scheduling strategies for multiprocessor real-time DSP[END_REF], JIT-MS is a fully dynamic scheduling strategy.

Singh presents a survey on multi/manycore mapping methodologies in [START_REF] Singh | Mapping on multi/many-core systems: Survey of current and emerging trends[END_REF]. In the context of the taxonomy used in Singh's survey, our methodology can be classified as "On-the-fly" mapping, targeting This work is supported by the ANR COMPA project.

heterogeneous platforms with a centralized resource management strategy.

Applications managed by the JIT-MS scheduler are described using the PiSDF dataflow Model of Computation (MoC), which is related to the general Dataflow Process Network (DPN) MoC. DPN MoCs are widely used in design of signal processing systems [START_REF]Handbook of Signal Processing Systems[END_REF]. A distinguishing feature of PiSDF is the integration of a parameter tree to asynchronously transmit control values between actors [START_REF] Desnos | Pimm: Parameterized and interfaced dataflow meta-model for mpsocs runtime reconfiguration[END_REF].

The JIT-MS scheduling method is embedded in the Synchronous Parameterized and Interfaced Dataflow Embedded Runtime (SPIDER) [START_REF] Heulot | Spider: A synchronous parameterized and interfaced dataflow-based rtos for multicore dsps[END_REF] This paper is organized as follows: Section II and Section III present related research, providing the context of current work, Section IV details our proposed new JIT-MS scheduling method, and Section V presents our experimental results with JIT-MS scheduling.

II. RELATED WORKS

Various frameworks based on OpenMP [START_REF] Dagum | Openmp: an industry standard api for sharedmemory programming[END_REF] and OpenCL [START_REF] Stone | Opencl: A parallel programming standard for heterogeneous computing systems[END_REF] language extensions are currently proposed to address the multicore scheduling challenge. However, these extensions are based on imperative languages (e.g., C, C++, Fortran) that do not provide mechanisms to model specific signal flow graph topologies. On the contrary, signal processing oriented dataflow MoCs are widely used for specification of data-driven signal flow graphs in a wide range of application areas, including video decoding [START_REF] Lucarz | Dataflow/actor-oriented language for the design of complex signal processing systems[END_REF], telecommunication [START_REF] Pelcat | Adaptive multicore scheduling for the LTE uplink[END_REF], [START_REF] Hsu | A mixed-mode vector-based dataflow approach for modeling and simulating lte physical layer[END_REF], and computer vision [START_REF] Sen | Dataflow-based mapping of computer vision algorithms onto fpgas[END_REF]. The popularity of dataflow MoCs in design and implementation of signal processing systems is due largely to their analyzability and their natural expressivity of the concurrency in signal processing algorithms, which makes them suitable for exploiting the parallelism offered by MPSoCs.

Synchronous DataFlow (SDF) [START_REF] Lee | Synchronous data flow[END_REF] is the most commonly used DPN MoC for signal processing systems. Production and consumption rates of actors (pieces of computation) are set by firing rules. These rates are fixed scalars in an SDF graph. Data values, encapsulated by tokens, are passed along the edges (First In, First Out data queues (FIFOs)) of a dataflow graph as it executes. Initial tokens, called delays can be set on FIFOs.

The PiSDF dataflow MoC [START_REF] Desnos | Pimm: Parameterized and interfaced dataflow meta-model for mpsocs runtime reconfiguration[END_REF] results from the addition of the Parameterized and Interfaced Meta Model (PiMM) to the SDF MoC. PiMM extends the semantics of a targeted dataflow MoC by introducing specific notions of hierarchy, interfaces, and parameters. Parameters in PiMM can influence, both statically and dynamically, different properties of a DPN, such as the firing rules of actors. The meta model introduces configuration actors, i.e. specific actors that can modify parameter values.

Neuendorffer, et al. define quiescent points as points where parameters influencing an execution are allowed to change [START_REF] Neuendorffer | Hierarchical reconfiguration of dataflow models[END_REF]. Between two quiescent points, the application can be considered static. In this paper, decisions are taken Just-In-Time, immediately after the quiescent points are reached, unveiling new application parallelism.

JIT-MS is an evolution of the work in [START_REF] Pelcat | Adaptive multicore scheduling for the LTE uplink[END_REF] presenting an adaptive scheduler of parameterized dataflow MoC. However, this work did not consider application hierarchy and was focused only on 3rd Generation Partnership Project (3GPP) Long Term Evolution (LTE) base stations. Our work on JIT-MS goes beyond the methods of [START_REF] Pelcat | Adaptive multicore scheduling for the LTE uplink[END_REF] to take application hierarchy into account and address a broad class of signal processing applications through generalized scheduling techniques.

III. CONTEXT

A. Runtime Architecture

The method developed in this paper is applicable to heterogeneous platforms. In such platform, optimized local decision to start an actor computation (e.g., based on earliest availability of input data) can be inefficient in a global sense. In order to take effective decisions globally, a Master/Slave execution scheme is chosen for the system.

The JIT-MS method requires multiple (software or hardware) components (Figure 1). Processing Elements (PEs) are slave components that process actors. They can be of multiple types, such as General-Purpose Processors (GPPs), DSPs, or accelerators. The master of the JIT-MS system is called Scheduling Element (SE). This is the only component that has access to the overall algorithm topology.

Jobs are used to communicate between the SE and PEs. Each PE has a job queue from which it pops jobs out prior to their execution. Parameters influence dataflow graph topology or execution timing of actors. When a parameter value is set by a configuration actor, its value is sent to the SE via a parameter queue. Finally, Data FIFOs are used by the PEs to exchange data tokens. A data FIFO can be implemented for instance over a shared memory or a network-onchip.

B. Benchmark

We illustrate the JIT-MS scheduling algorithm by the scheduling of a benchmark application. This benchmark is an extension of the MP-sched benchmark [START_REF] Zaki | Integration of dataflow-based heterogeneous multiprocessor scheduling techniques in gnu radio[END_REF].

The MP-sched benchmark can be viewed as a two-dimensional grid involving N channels, where each branch consists of M cascaded Finite Impulse Response (FIR) filters of NbS samples. Here, we extend the MP-sched benchmark by allowing the M parameter to vary across different branches. We refer to this extended version of the MP-sched benchmark as heterogeneous-chain-length MP-sched (HCLM-sched).

C. Notations

To describe JIT-MS, the following notation is used. CA represents the set of configuration actors of the given PiSDF graph. Thus, CA represents all actors in the given PiSDF graph that are not configuration actors.

IV. JUST-IN-TIME MULTICORE SCHEDULING (JIT-MS)

A. Multicore Scheduling of Static Subgraphs

JIT-MS involves decomposing the scheduling of a given PiSDF graph into the scheduling of a sequence X1, X2, . . . of SDF graphs. Different executions (with different sets of input data) can result in different sequences of SDF graphs for the same PiSDF graph. For a given execution, we refer to each Xi as a step of the JIT-MS scheduling process for that execution.

On each step, resolved parameters enable the transformation of the PiSDF graph into an SDF graph, which can be scheduled by any of the numerous existing SDF scheduling heuristics that are relevant for multicore architectures [START_REF] Sriram | Embedded multiprocessors: Scheduling and synchronization[END_REF]. For example, see [START_REF] Kwok | High-performance algorithms for compile-time scheduling of parallel processors[END_REF] for a set of techniques that can be applied upon transforming the resulting SDF graph into an single rate SDF (srSDF) graph. An srSDF graph is an SDF graph in which the production rate on each edge is equal to the consumption rate on that edge. A consistent SDF graph can be transformed into an equivalent srSDF graph by applying techniques that were introduced by Lee and Messerschmitt [START_REF] Lee | Static scheduling of synchronous data flow programs for digital signal processing[END_REF].

The Just-In-Time Multicore Scheduling (JIT-MS) method is based on the static multicore scheduling method which is composed of the following sequence of phases:

1) Computing the Basis Repetition Vector (BRV) of the current graph (the graph that is presently being scheduled). The BRV, also known as the SDF repetition vector, is a positive-integer vector and represents the number of firings of each actor in a minimal periodic scheduling iteration for the graph. We note however, that certain technical details of PiSDF require adaptations to the conventional repetitions vector computation process from [START_REF] Lee | Synchronous data flow[END_REF]. 2) Converting the SDF graph into an equivalent srSDF graph, where each actor is instantiated a number of times equal to its corresponding BRV component.

3) Scheduling actors and communications from a derived acyclic srSDF graph onto the targeted heterogeneous platform. Any scheduling heuristic that is applicable to acyclic srSDFs graphs can be chosen here -e.g., the applied schedule can be a list scheduler, fast scheduler, flow-shop or genetic scheduler [START_REF] Singh | Mapping on multi/many-core systems: Survey of current and emerging trends[END_REF], [START_REF] Boutellier | A low-overhead scheduling methodology for fine-grained acceleration of signal processing systems[END_REF], [START_REF] Kwok | High-performance algorithms for compile-time scheduling of parallel processors[END_REF]. Upon completing the scheduling process described, the resulting schedule S is executed. A complete JIT-MS schedule of a PiSDF hierarchical graph consists of several of these phases, repeated as many times as needed (see Section IV-B).

In a PiSDF graph, some data FIFOs behave as Round Buffers (RBs) [START_REF] Desnos | Pimm: Parameterized and interfaced dataflow meta-model for mpsocs runtime reconfiguration[END_REF] -i.e., such FIFOs produce multiple copies of individual tokens as necessary to satisfy consumption demand. In particular, FIFOs at the interface of a hierarchical actor have RBs behavior to help ensure composability in hierarchical specifications. FIFOs connecting configuration actors to other actors also behave as RBs to ensure that configuration actors fire only once per subgraph. Application designers using the PiSDF model of computation need to take such RB behavior into account during the development process.

Configuration Actors and such RBs are excluded from the BRV computation as they are forced to fire only once.

B. Multicore Scheduling of Full Graphs

The JIT-MS method is based on the PiSDF runtime operational semantic. As shown in [START_REF] Desnos | Pimm: Parameterized and interfaced dataflow meta-model for mpsocs runtime reconfiguration[END_REF], the JIT-MS scheduler has to proceed in multiple steps, each one unveiling a new portion of srSDF graph for scheduling. In one step, configuration actors have to be fired first, they produce parameters needed to resolve the rest of the subgraph. When all parameters are solved at one hierarchy level, scheduling of other actors of this hierarchy level is made possible. In a multicore system, the SE has to extract the parallelism of the application to send jobs to multiple PEs. Contrary to static applications, the difficulty of this process is to schedule actors efficiently without knowing the complete graphs. The complete srSDF graph is only known when all configuration actors have been executed.

Once an srSDF graph has been generated, it can be analyzed to exploit the parallelism of the application (Section IV-A). The JIT-MS runtime schedules the actors and communications and fires their execution on the platform. Newly instantiated hierarchical actors are added to a global srSDF graph, called execution graph, and the same process can be used until the whole graph has been processed.

To keep track of actor's execution, each actor of the execution graph is tagged with a flag representing its execution state. An actor can be Run (R), Not Executable (N) or Executable (E). An actor is Executable only when all its parameters are resolved and when all its predecessors are Executable or Run.

The procedure of JIT-MS scheduling is shown in Algorithm 1.

After initialization, the algorithm enters in a main while loop which computes scheduling steps until there is no more hierarchical actor in the execution graph. A single scheduling step is made of the 3 stages: graph configuration, actor execution and graph resolution.

The first stage (line 3 to 13) replaces each executable hierarchical actor of the execution graph by its configuration actors. As they are only fired once, there is no need to compute the BRV and the graph transformation to srSDF becomes trivial. If there is no configuration actor in this hierarchical actor, all the subgraph parameters can be resolved (using the 2 first phases presented in Section IV-A) and the subgraph can replace the hierarchical actor in the execution graph. In this stage, it is also important to add RBs at the interfaces of the hierarchical actors and between CA and CA to respect PiSDF semantics.

Algorithm 1: Multi-Step Algorithm procedure to schedule a PiSDF graph. The second stage (line 14 to 15) assigns, orders and fires executable actors. It corresponds to phase 3 of Section IV-A.

The third stage (line 16 to 20) corresponds to the graph resolution. At this stage, the parameters resolved by configuration actors of the previous stages are used to solve the graph of each hierarchical step. The 2 first phases of Section IV-A can then be applied to fully replace the hierarchical actor in the execution graph with the corresponding child actors.

At the end of the algorithm (line 21 to 22), when no more hierarchical actor is present in the execution graph, a last phase of assignment, ordering and firing of executable actors has to be done to execute all non executed actors.

C. Applying JIT-MS to the Benchmark

The execution graph shape at each step of the HCLM-sched benchmark can be seen in Figure 3. In this figure, blue actors are not executable, green ones are executable and black ones are already run. Red dashed actors are hierarchical.

V. EXPERIMENTAL RESULTS

This paper describes a method called JIT-MS used to parallelize applications at runtime. In this context, experimental results will focus on the comparison between the JIT-MS approach and the OpenMP Fig. 3: single rate SDFs (srSDFs) graphs generated from the HCLM-sched benchmark.

framework. Results have been acquired by studying the latency of single and multiple iterations of the HCLM-sched benchmark on the Texas Instruments c6678 multicore DSP [START_REF]Multicore Fixed and Floating-Point Digital Signal Processor -SPRS691E, Texas Instruments[END_REF].

OpenMP is a framework designed for shared memory multiprocessing. It provides mechanisms for launching parallel teams of threads to execute efficiently an algorithm on a multicore architecture. OpenMP applications are designed with a succession of sequential code, executed by a master thread, and parallel code, distributed in a team of threads dispatched onto multiple cores [START_REF] Dagum | Openmp: an industry standard api for sharedmemory programming[END_REF].

The platform used for the current experiments is the Texas Instruments Keystone I architecture (EVM TMS320C6678). This multicore DSP platform is composed of 8 c66x DSP cores interconnected by a Network on Chip (NoC) called TeraNet with access to an internal shared memory. To perform synchronization between cores, hardware queues provided by the Multicore Navigator [START_REF]Texas Instruments[END_REF] have been used.

The OpenMP framework cannot implement the HCLM-sched as a double nested loop since FIRs are cascaded on each channels. So, OpenMP is used to parallelize channels by using a "parallel for".

For the first experiment, we fix the M value to 8 for all stages, FIR of 4000 samples and we measure latency of one graph iteration. Results on execution time are displayed in Figure 4.a. As can be seen on Figure 4.a, the OpenMP implementation latency curve displays a step shape when increasing N . This is due to channels distribution on the platform. Since each stage is implemented as a monolithic block with OpenMP, as soon as 9 channels are reached, 2 channels have to be completed on one PE making the overall latency double.

With the JIT-MS implementation, the graph transformation and scheduling phases introduce a visible overhead but the execution efficiency over varying parameters is smoother. The overhead can be observed on the figure when N equals to 7 or 8 as the resulting scheduling is the same as OpenMP. The transformation to srSDF extracts more parallelism than OpenMP from the subdivision of channels into multiple FIRs. These choices make JIT-MS suitable for unbalanced applications. In the HCLM-sched benchmark with 9 channels, the overall latency is reduced of up to 26%.

The second experiment is based on multiple iterations of the HCLM-sched benchmark. For this experiment, we fixed the number of channels to 8 and M values are linear between 1 to 8. Then, multiple iterations of the application are launched with a fixed period.

As we can see in Figure 4.b, if the latency of the OpenMP implementation is superior to the period, the latency is growing at each new iterations. This is due to the global synchronization at the end of each OpenMP parallelization blocks.

For the JIT-MS implementation, the latency remains constant over iterations. By having prior knowledge on how the application will behave, the Scheduling Element can start an execution on processing elements which have already finished the previous execution. It can then start the following iteration as soon as the next period tick occurs. With a better knowledge of the application execution, the JIT-MS can pipeline graph iterations.

VI. CONCLUSION

This paper presents a novel multicore scheduling method referred to as Just-In-Time Multicore Scheduling (JIT-MS). JIT-MS splits the scheduling of a PiSDF dataflow graph into steps to identify locally static regions. It enables efficient assignment and ordering of actors into PEs with a better knowledge of actor interactions. Experiments conducted on an 8-core Texas Instruments DSP demonstrate on a benchmark that the JIT-MS scheduler provides more parallelism to the execution than the job posting system based on pragmas, task creation and task dispatch of OpenMP. Results have shown that JIT-MS can reduce the execution latency up to 26% and can allow handling multiple executions.

Fig. 1 :

 1 Fig. 1: Runtime execution scheme.

Fig. 2 :

 2 Fig. 2: A PiSDF model of the HCLM-sched benchmark.

Figure 3 .

 3 a corresponds to the execution graph state at the end of the first phase of the first iteration of the while loop (loop I.a). At this point, N is set to 2. Then Figure 3.b corresponds to execution graph state after the third phase of the first iteration (loop I.b). The hierarchical FIR Chan actors are instanciated. Then, Figures 3.c

  and 3.d correspond to the execution, first of the internal configuration actors of FIR Chan (SM ), then of their actors with parameter M = {1, 2}.

Fig. 4 :

 4 Fig. 4: a) Latency vs N values b) Latency vs multiple iterations

  Add RBs between CA and CA ;

	1 Procedure MultiStep()
	2	while {∃ Hierarchical actor in execGraph } do
	3	while {∃ Hierarchical actor in execGraph |
		actor.flag = E } do
	4	currentPiSDF ← actor.pisdf ;
	5	if CA = {∅} then
	6	Replace actor with RBs in execGraph;
	9	push currentPiSDF → graphFifo;
	10	else
	11	computeBRV(currentPiSDF) ;
	12	Add single rate CA graph in execGraph;
	13	Update flags in execGraph;
	14	Schedule Executable actors ∈ execGraph;
	15	Fire Actors and Wait parameter values ;
	16	while graphFifo is not empty do
	17	pop graphFifo → currentPiSDF;
	18	computeBRV(currentPiSDF) ;

7 Put CA in execGraph; 8 19 Add single rate CA graph in execGraph; 20 Update flags in execGraph; 21 Schedule Executable actors ∈ execGraph; 22 Fire Actors ;