Nguyen Van Trinh
email: van-trinh.nguyen@insa-rennes.fr

Jean-François Dupuy
email: jean-francois.dupuy@insa-rennes.fr

Zero-inated Poisson regression with right-censored data

Keywords: Count data, excess of zeros, health-care utilization, large-sample properties, simulations

The zero-inated Poisson regression model is often used to analyse count data with an excess of zeros. This paper extends the model to randomly right-censored count data. Rightcensoring occurs when one only knows that the true count value is higher than the observed one. In this setting, maximum likelihood estimators (MLE) are constructed and their properties are investigated. In particular, MLE are shown to be consistent and asymptotically normal. A simulation study is conducted to assess nite-sample behaviour of the MLE. Finally, an application in health economics is described.

Introduction

Statistical modeling of count data is an important issue in various elds, including agriculture, econometrics, epidemiology, industrial applications, public health. . . Generalized linear models [START_REF] Mccullagh | Generalized linear models[END_REF]) provide a powerful framework for analysing such data.

In many applications however, count data show an excess of zeros, that is, a number of zeros that cannot be explained by models based on standard distributional assumptions. A large number of statistical tools have been developed to tackle this issue, such as zero-inated regression models which mix a degenerate distribution with point mass of one at zero with a standard count regression model.

For example, zero-inated Poisson (ZIP) regression model was proposed by [START_REF] Lambert | Zero-inated Poisson regression, with an application to defects in manufacturing[END_REF] and further developed by [START_REF] Dietz | On estimation of the Poisson parameter in zero-modied Poisson models[END_REF], Lim et al. (2014) and [START_REF] Monod | Random eects modeling and the zero-inated Poisson distribution[END_REF], among many others. Recent variants of ZIP regression include random-eects ZIP models [START_REF] Hall | Zero-inated Poisson and binomial regression with random eects: a case study[END_REF][START_REF] Min | Random eect models for repeated measures of zero-inated count data[END_REF] and semiparametric ZIP models [START_REF] Lam | Semiparametric analysis of zero-inated count data[END_REF][START_REF] Feng | Semiparametric analysis of longitudinal zero-inated count data[END_REF]. Zero-inated negative binomial (ZINB) regression model was proposed by [START_REF] Ridout | A score test for testing a zero-inated Poisson regression model against zero-inated negative binomial alternatives[END_REF], see also [START_REF] Moghimbeigi | Multilevel zeroinated negative binomial regression modeling for over-dispersed count data with extra zeros[END_REF] and [START_REF] Mwalili | The zero-inated negative binomial regression model with correction for misclassication: an example in caries research[END_REF]. When counts have an upper bound, ZIP and ZINB regression models are no longer appropriate. [START_REF] Hall | Zero-inated Poisson and binomial regression with random eects: a case study[END_REF] thus introduced the zero-inated binomial (ZIB) model, see also [START_REF] Hall | Score tests for heterogeneity and overdispersion in zero-inated Poisson and binomial regression models[END_REF], [START_REF] Diop | Maximum likelihood estimation in the logistic regression model with a cure fraction[END_REF], [START_REF] Diop | Simulation-based inference in a zero-inated Bernoulli regression model[END_REF] and [START_REF] Diallo | Asymptotic properties of the maximum likelihood estimator in zero-inated binomial regression[END_REF]. Statistical modeling of bounded count data containing both extra zeros and extra right-endpoints has recently where P(λ i ) denotes Poisson distribution with parameter λ i > 0. Obviously, the ZIP model reduces to a standard Poisson distribution if ω i = 0. In ZIP regression, the mixing probability ω i and parameter λ i are usually modeled by logistic and log-linear models respectively, that is:

logit(ω i (γ)) = γ W i ,
(2.2) and

log(λ i (β)) = β X i , (2.3)
where X i = (1, X i2 , . . . , X ip ) and W i = (1, W i2 , . . . , W iq ) are random vectors of predictors or covariates (both categorical and continuous covariates are allowed), β ∈ R p and γ ∈ R q are unknown parameters and denotes the transpose operator.

Assume that we observe n independent vectors (Z 1 , X 1 , W 1 ), . . . , (Z n , X n , W n ) from the model (2.1)-(2.2)-(2.3), all dened on the probability space (Ω, C, P). The log-likelihood of (β, γ) based on these observations is (see [START_REF] Dupuy | Statistical methods for the analysis of overdispersed count data[END_REF]:

n i=1 1 {Z i =0} log e γ W i + e -exp(β X i ) + 1 {Z i >0} Z i β X i -e β X i -log(Z i !) -log 1 + e γ W i .
The maximum likelihood estimator of (β, γ) is obtained by maximizing this function. This estimator is consistent and asymptotically normally distributed (see [START_REF] Czado | Zero-inated generalized Poisson models with regression eects on the mean, dispersion and zero-ination level applied to patent outsourcing rates[END_REF]. Assume now that the count response Z i can be right-censored, that is, for some individuals, we only observe a lower bound on Z i . This can be modeled by introducing a censoring random variable C i and by dening the observation for the i-th individual as the vector

(Z * i , δ i , X i , W i ), where Z * i = min(Z i , C i ) and δ i = 1 {Z i <C i } (if Z i = C i , we let Z * i = C i and δ i = 0). Let J i = 1 {Z * i =0}
. The likelihood of ψ := (β , γ ) based on observations (Z * i , δ i , X i , W i ), i = 1, . . . , n is calculated as:

L n (ψ) = n i=1 P(Z i = Z * i |X i , W i ) δ i P(Z i ≥ Z * i |X i , W i ) 1-δ i , = n i=1 P(Z i = Z * i |X i , W i ) 1-J i P(Z i = 0|X i , W i ) J i δ i P(Z i ≥ Z * i |X i , W i ) (1-δ i )(1-J i ) , = n i=1   e -λ i λ Z * i i Z * i ! (1 -ω i ) 1-J i ω i + (1 -ω i )e -λ i J i   δ i ×   1 - Z * i -1 k=0 e -λ i λ k i k! (1 -ω i ) -ω i   (1-δ i )(1-J i )
, from which we easily obtain the loglikelihood n (ψ) = log L n (ψ). If ω i and λ i are given by 3 (2.2) and (2.3), straightforward algebra yields:

n (ψ) = n i=1 δ i J i log e γ W i + e -exp(β X i ) + (1 -J i ) Z * i β X i -e β X i -log(Z * i !) +(1 -δ i )(1 -J i ) ln   1 - Z * i -1 k=0 e -exp(β X i )+kβ X i k!   -log 1 + e γ W i    .
Note that n (ψ) reduces to the log-likelihood given above when there is no censoring (that is, when δ i = 1 for all i = 1, . . . , n).

The maximum likelihood estimator ψn := ( β n , γ n ) of ψ is solution of the k-dimensional score equation

∂ n (ψ) ∂ψ = 0,
(2.4)

where k = p + q. In the next section, we establish existence, consistency and asymptotic normality of ψn . First, we need to introduce some further notations.

Some additional notations

In what follows, we note k i (γ) = e γ W i and L i (β) = e -exp(β X i ) , i = 1, . . . , n. Let also S λ i (β) (u) = P(P(λ i (β)) ≥ u), u = 0, 1, . . . denote the survival function of P(λ i (β)) distribution. We have:

∂ n (ψ) ∂β = n i=1 X i -δ i J i λ i (β)L i (β) k i (γ) + L i (β) + δ i (1 -J i ) (Z * i -λ i (β))
(2.5)

-(1 -δ i )(1 -J i ) Z * i -1 k=0 L i (β)λ k i (β)(k -λ i (β)) k! S λ i (β) (Z * i )   , = 1, . . . , p,
and

∂ n (ψ) ∂γ = n i=1 W i δ i J i k i (γ) k i (γ) + L i (β) - k i (γ) k i (γ) + 1 , = 1
, . . . , q.

(2.6)

Let u i (ψ) = λ i (β)L i (β) (k i (γ) + L i (β)) 2 [k i (γ) + L i (β) -λ i (β)k i (γ)] , i = 1, . . . , n,
and for

Z * i ≥ 1, let v i (ψ) = Z * i -1 k=0 L i (β)λ k i (β) k! S 2 λ i (β) (Z * i ) S λ i (β) (Z * i ) (λ i (β) -k) 2 -λ i (β)
-λ i (β)(k -λ i (β))P(P(λ i (β)) = Z * i -1)} , i = 1, . . . , n.

Then, some tedious albeit not dicult algebra shows that

∂ 2 n (ψ) ∂β ∂β m = n i=1 X i X im {-δ i J i u i (ψ) -δ i (1 -J i )λ i (β) -(1 -δ i )(1 -J i )v i (ψ)} , , m = 1, . . . , p ∂ 2 n (ψ) ∂β ∂γ m = n i=1 X i W im δ i J i k i (γ)λ i (β)L i (β) (k i (γ) + L i (β)) 2 ,
= 1, . . . , p and m = 1, . . . , q

∂ 2 n (ψ) ∂γ ∂γ m = n i=1 W i W im k i (γ) δ i J i L i (β) (k i (γ) + L i (β)) 2 - 1 (k i (γ) + 1) 2 ,
, m = 1, . . . , q.

We note S n (ψ) = ∂ n (ψ)/∂ψ, H n (ψ) = -∂ 2 n (ψ)/∂ψ∂ψ , F n (ψ) = E(H n (ψ)) and I k the identity matrix of order k. H n (ψ) is assumed positive denite.

Asymptotic results

In this section, we establish consistency and asymptotic normality of ψn . In what follows, the space R k of k-dimensional vectors is provided with the Euclidean norm • 2 and the space of (k × k) real matrices is provided with the norm |||A||| 2 := sup x 2 =1 Ax 2 (for notations simplicity, we use • for both norms). Recall that for a symmetric real (k × k)-matrix A with eigenvalues λ 1 , . . . , λ k , A = max i |λ i | (from now on, λ min (A) and λ max (A) will denote the smallest and largest eigenvalues of A respectively).

We rst state some regularity conditions:

C1 Covariates are bounded, that is, there exist compact sets X ⊂ R p and W ⊂ R q such that X i ∈ X and W i ∈ W for every i = 1, 2, . . .

C2

The true parameter value ψ 0 = (β 0 , γ 0 ) lies in the interior of some known compact and convex set C = B × G ⊂ R k (where B ⊂ R p and G ⊂ R q are the parameter spaces of β and γ respectively).

C3 There exists a positive constant c 1 such that n/λ min (F n (ψ 0 )) ≤ c 1 for every n = 1, 2, . . .

C4

Censoring random variables C i , i = 1, 2, . . . are strictly positive and bounded by some constant M < ∞ (for example, M can be the end of the study period, at which every individual still under study is censored).

Conditions C1-C3 are classical in generalized linear regression and zero-inated regression models (see [START_REF] Fahrmeir | Consistency and asymptotic normality of the maximum likelihood estimator in generalized linear models[END_REF][START_REF] Czado | Zero-inated generalized Poisson models with regression eects on the mean, dispersion and zero-ination level applied to patent outsourcing rates[END_REF]. Condition C4 is required in the censored setting.

For each n = 1, 2, . . . and ε > 0, dene the neighbourhood

N n (ε) = {ψ ∈ C : (ψ - ψ 0 ) F n (ψ -ψ 0 ) ≤ ε 2 } of ψ 0 ,
where F n is a short notation for F n (ψ 0 ). Our rst result states that the solution of (2.4) exists, lies in the neighbourhood N n (ε) of ψ 0 when n is suciently large and is consistent for ψ 0 .

Theorem 3.1 (Existence and consistency). Assume conditions C1-C4 hold. Then the probability that ψn exists and lies in N n (ε) for some ε tends to 1 as n → ∞. Furthermore, ψn converges in probability to ψ 0 as n → ∞.

Proof of Theorem 3.1. Our proof follows the lines of [START_REF] Fahrmeir | Consistency and asymptotic normality of the maximum likelihood estimator in generalized linear models[END_REF] but technical details are dierent. Moreover, we rely on dierent arguments in several parts, leading to more direct proofs. A technical lemma is proved in an Appendix.

i) We rst prove asymptotic existence of ψn . We show that for every η > 0, there exists ε > 0 and n 1 ∈ N such that

P ( n (ψ) -n (ψ 0 ) < 0 for all ψ ∈ ∂N n (ε)) ≥ 1 -η, for n ≥ n 1 , (3.7)
where

∂N n (ε) is the boundary {ψ ∈ C : (ψ -ψ 0 ) F n (ψ -ψ 0 ) = ε 2 } of N n (ε).
This will imply the existence of a local maximum of n in N n (ε). Positive-deniteness of H n and convexity of C will ensure that this maximum is global and unique.

In fact, equivalently to (3.7), we show that for every η > 0, there exists ε > 0 and n 1 ∈ N such that

P ( n (ψ) -n (ψ 0 ) ≥ 0 for some ψ ∈ ∂N n (ε)) ≤ η, for n ≥ n 1 .
To see this, we use Taylor's expansion to write

n (ψ) -n (ψ 0 ) = (ψ -ψ 0 ) T S n (ψ 0 ) - 1 2 (ψ -ψ 0 ) T H n ( ψ)(ψ -ψ 0 ), := (ψ -ψ 0 ) T S n (ψ 0 ) -Q n (ψ),
where ψ = aψ + (1 -a)ψ 0 (for some 0 ≤ a ≤ 1) lies between ψ and ψ 0 . Let 0 < c < 1 2 and write f.s. for "for some". Then we have:

P ( n (ψ) -n (ψ 0 ) ≥ 0, f.s. ψ ∈ ∂N n (ε)) = P (ψ -ψ 0 ) T S n (ψ 0 ) ≥ Q n (ψ) and Q n (ψ) > cε 2 , f.s. ψ ∈ ∂N n (ε) +P (ψ -ψ 0 ) T S n (ψ 0 ) ≥ Q n (ψ) and Q n (ψ) ≤ cε 2 , f.s. ψ ∈ ∂N n (ε) , ≤ P (A) + P (B) ,
where A and B denote events

A = {(ψ -ψ 0 ) T S n (ψ 0 ) > cε 2 , f.s. ψ ∈ ∂N n (ε)} and B = {Q n (ψ) ≤ cε 2 , f.s. ψ ∈ ∂N n (ε)} respectively. Let u n (ψ) = 1 ε F 1 2 n (ψ -ψ 0 ). Then A = {u n (ψ) F -1 2 n S n (ψ 0 ) > cε, f.s. ψ ∈ ∂N n (ε)}, ⊆ { sup ψ∈∂Nn(ε) |u n (ψ) F -1 2 n S n (ψ 0 )| > cε}, ⊆ { sup un(ψ) =1 |u n (ψ) F -1 2 n S n (ψ 0 )| > cε}, = { F -1 2 n S n (ψ 0 ) > cε}.
where the second to third line comes from the fact that ψ ∈ ∂N n (ε) implies u n (ψ) = 1.

It follows that

P(A) ≤ P( F -1 2 n S n (ψ 0 ) > cε)
. By Theorem 1.5 of [START_REF] Seber | Linear Regression Analysis[END_REF],

E F -1 2 n S n (ψ 0 ) 2 = k
and Chebyshev's inequality implies

P(A) ≤ k c 2 ε 2 .
Finally, letting ε = 2k ηc 2 implies that P(A) ≤ η/2. Now,

B = 1 2 (ψ -ψ 0 ) T H n ( ψ)(ψ -ψ 0 ) ≤ cε 2 , f.s. ψ ∈ ∂N n (ε) , = 1 2 u n (ψ) F -1 2 n H n ( ψ)F -1 2 n u n (ψ) ≤ c, f.s. ψ ∈ ∂N n (ε) , ⊆ 1 2 λ min F -1 2 n H n ( ψ)F -1 2 n u n (ψ) u n (ψ) ≤ c, f.s. ψ ∈ ∂N n (ε) , = 1 2 λ min F -1 2 n H n ( ψ)F -1 2 n ≤ c, f.s. ψ ∈ ∂N n (ε) .
Thus, P(B) ≤ P(there exists ψ ∈ ∂N n (ε) such that λ min (F

-1 2 n H n ( ψ)F -1 2 n ) ≤ 2c). By Lemma 6.1 in Appendix, F -1 2 n H n (ψ)F -1 2 n converges in probability to I k uniformly in ψ ∈ N n (ε),
as n → ∞. Thus, by [START_REF] Maller | Asymptotics of regressions with stationary and nonstationary residuals[END_REF], λ min (F

-1 2 n H n (ψ)F -1 2 n ) converges in probability to 1 uniformly in ψ ∈ N n (ε), as n → ∞. If ψ = aψ + (1 -a)ψ 0 for some 0 ≤ a ≤ 1 and ψ ∈ N n (ε), then F 1 2 n ( ψ -ψ 0 ) = F 1 2 n (aψ + (1 -a)ψ 0 -ψ 0 ) , = a F 1 2 n (ψ -ψ 0 ) , ≤ F 1 2 n (ψ -ψ 0 ) , ≤ , and thus ψ ∈ N n (ε). If follows that λ min (F -1 2 n H n ( ψ)F -1 2 n ) converges in probability to 1 as n → ∞, since |λ min (F -1 2 n H n ( ψ)F -1 2 n )-1| ≤ sup ψ∈Nn(ε) |λ min (F -1 2 n H n (ψ)F -1 2 n )-1|. Therefore, for n suciently large (say, n ≥ n 1 ), P(there exists ψ ∈ ∂N n (ε) such that λ min (F -1 2 n H n ( ψ)F -1 2 n ) ≤ 2c) ≤ η/2, since 2c < 1. This implies that P(B) ≤ η/2. Finally, P ( n (ψ) -n (ψ 0 ) ≥ 0, f.s. ψ ∈ ∂N n (ε)) ≤ P (A) + P (B) ≤ η,
which proves (3.7) and in turn, the existence of a unique global maximum of n on N n (ε), which coincides with ψn .

ii) We turn to the consistency of ψn . We have:

λ min (F n ) ψn -ψ 0 2 = ( ψn -ψ 0 ) λ min (F n )I k ( ψn -ψ 0 ), ≤ ( ψn -ψ 0 ) F n ( ψn -ψ 0 ), = F 1 2 n ( ψn -ψ 0 ) 2 , ≤ ε 2 ,
with probability tending to 1 as n → ∞, by i). By condition C3, λ min (F n ) tends to ∞ as n → ∞. Therefore ψn -ψ 0 converges to 0 with probability tending to 1 as n → ∞, which concludes the proof.

Our second result is:

Theorem 3.2 (Asymptotic normality). Assume conditions C1-C4 hold. Then F 1 2
n ( ψnψ 0 ) converges in distribution to the Gaussian vector N (0, I k ), as n → ∞.

Proof of Theorem 3.2. Our proof proceeds along the same lines as the proof of asymptotic normality of MLE in uncensored zero-inated generalized Poisson regression [START_REF] Czado | Consistency and asymptotic normality of the maximum likelihood estimator in a zero-inated generalized Poisson regression[END_REF]. However, [START_REF] Czado | Consistency and asymptotic normality of the maximum likelihood estimator in a zero-inated generalized Poisson regression[END_REF] use a central limit theorem with Lyapunov condition. Here, we rely on the weaker Lindeberg condition, which yields a much shorter proof.

We rst prove asymptotic normality of the normalized score vector

F -1 2 n S n
, where S n is a short notation for S n (ψ 0 ). Let u be any vector in R k . We show that u F -1 2 n S n converges in distribution to N (0, u u) (without loss of generality, we set u = 1). From (2.5) and (2.6), we remark that S n can be written as a sum S n = n i=1 S n,i of independent k-dimensional random vectors S n,i = (S n,i,1 , . . . , S n,i,k ) . It is not dicult to see that under conditions C1, C2 and C4, components of S n,i are bounded by some nite positive constant c 2 that is,

|S n,i, | < c 2 , = 1, . . . , k. Therefore, S n,i 2 < c 3 := kc 2 2 . Let u F -1 2 n S n = u F -1 2 n n i=1 S n,i := n i=1 S * n,i .
Then E(S * n,i ) = 0 and var( n i=1 S * n,i ) = 1. We now verify Lindeberg condition, namely:

for every ε > 0, n i=1 E S * 2 n,i 1 {|S * n,i |>ε} → 0 as n → ∞.
Let ε > 0. We have:

n i=1 E S * 2 n,i 1 {|S * n,i |>ε} ≤ n i=1 E u 2 F -1 2 n 2 S n,i 2 1 {|S * n,i |>ε} , ≤ c 1 c 3 n n i=1 E(1 {|S * n,i |>ε} ), by condition C3. Now, {|S * n,i | > ε} implies that {λ min (F n ) < c 3 /ε 2 }, therefore, 1 {|S * n,i |>ε} ≤ 1 {λ min (Fn)<c 3 /ε 2 } and thus, n i=1 E S * 2 n,i 1 {|S * n,i |>ε} ≤ c 1 c 3 n n i=1 1 {λ min (Fn)<c 3 /ε 2 } = c 1 c 3 1 {λ min (Fn)<c 3 /ε 2 } . Under C3, λ min (F n ) → ∞ as n → ∞. Therefore, n i=1 E(S * 2 n,i 1 {|S * n,i |>ε} ) → 0 as n → ∞. It follows that for every u ∈ R k , u F -1 2 n S n converges in distribution to N (0, 1) and by Cramer-Wold device, F -1 2 n S n converges in distribution to N (0, I k ). Weak convergence of F 1 2
n ( ψn -ψ 0 ) is now obtained as usual, by expanding S n := S n (ψ 0 ) about ψn . The rest of the proof is similar to proof of Theorem 3 of [START_REF] Fahrmeir | Consistency and asymptotic normality of the maximum likelihood estimator in generalized linear models[END_REF] and is thus omitted.

In order to construct asymptotic condence intervals and tests of hypothesis for the components of ψ, one needs to estimate F 1/2 n (by F 1/2 n ( ψn ) for example). Asymptotic normality of F 1/2 n ( ψn )( ψn -ψ 0 ) still holds if one assumes that there exists a nite constant c 4 such that λ max (F n )/λ min (F n ) ≤ c 4 for n suciently large. This can be proved as in [START_REF] Fahrmeir | Consistency and asymptotic normality of the maximum likelihood estimator in generalized linear models[END_REF] and is omitted.

Simulation study

In this section, we investigate nite-samples properties of the MLE under various scenarios obtained by varying the censoring and zero-ination proportions and the sample size.

Simulation design

We simulate the data according to the ZIP model (2.1)-(2.2)-(2.3) dened by:

log(λ i (β)) = β 1 X i1 + β 2 X i2 + β 3 X i3 + β 4 X i4 + β 5 X i5 + β 6 X i6 , and logit(ω i (γ)) = γ 1 W i1 + γ 2 W i2 + γ 3 W i3 + γ 4 W i4 , +γ 5 W i5 ,
where X i1 = W i1 = 1 and the X i2 , . . . , X i6 , W i4 , W i5 are independently drawn from normal N (0, 1), Bernoulli B(0.3), normal N (1, 2.25), exponential E(1), uniform U(2, 5), normal N (-1, 1) and Bernoulli B(0.5) distributions respectively. Linear predictors in log(λ i (β)) and logit(ω i (γ)) are allowed to share common terms by letting W i2 = X i2 and W i3 = X i3 . We consider the following sample sizes: n = 500, 1000, 2500. The regression parameter β is chosen as β = (0.7, 0.1, 0.4, 0.85, -0.5, 0) . The regression parameter γ is chosen as: case 1: γ = (-0.9, -0.65, -0.2, 0.65, 0) , case 2: γ = (0.25, -0.7, -0.2, 0.65, 0) . Using these values, in case 1 (respectively case 2), the average percentage of zero-ination in the simulated data sets is 20% (respectively 40%). Censoring values are simulated from a zero-truncated Poisson model with parameter µ, where µ is chosen to yield various average censoring proportions c in the simulated samples, namely c = 0.1, 0.2, 0.4. For purpose of comparison, we also provide results that would be obtained if there were no censoring (that is, when c = 0) since these results will constitute a benchmark for assessing performance of the MLE when censoring is present.

For each combination of the simulation design parameters (sample size, proportions of censoring and zero-ination), we simulate N = 1000 samples and we calculate the MLE ψn . Simulations are carried out using the statistical software R. To solve the likelihood equation, we use the package maxLik [START_REF] Henningsen | maxLik: A package for maximum likelihood estimation in R[END_REF] which implements various Newton-Raphson-like algorithms. We obtain starting values by estimating a ZIP model without taking censoring into account (this step is carried out using the function zeroinfl of the R package pscl, see [START_REF] Zeileis | Regression models for count data in R[END_REF] and Jackman (2017)).

Results

For each conguration [sample size × censoring proportion × zero-inflation proportion] of the simulation parameters, we calculate the average bias and average relative bias (expressed as a percentage) of the estimates βj,n and γk,n over the N simulated samples. For example, the relative bias of βj,n is obtained as

1 N N t=1 β(t) j,n -β j β j × 100,
where β(t) j,n denotes the MLE of β j in the t-th simulated sample. We also obtain the average standard error (SE), empirical standard deviation (SD) and root mean square error (RMSE) for each βj,n (j = 1, . . . , 6) and γk,n (k = 1, . . . , 5). Finally, we provide the empirical coverage probability (CP) and average length of 95%-level condence intervals for the β j and γ k . Results are given in Table 1 (case 1, n = 500), Table 2 (case 2, n = 500), Table 3 (case 1, n = 1000), Table 4 (case 2, n = 1000), Table 5 (case 1, n = 2500) and Table 6 (case 2, n = 2500).

From these results, we observe, as expected, that accuracy of MLEs of both β j and γ k decreases as sample size decreases. Accuracy of β j s estimates also decreases as censoring increases (note that the relative bias stays moderate though, even when censoring is high). On the contrary, estimates of the γ k are rather insensitive to censoring, which can be explained by the fact that censoring does not aect zero counts. For both β j and γ k , empirical coverage probabilities are close to the nominal condence level in every case. As may also be expected, for a given censoring proportion, we observe that MLEs of the β j (respectively γ k ) perform better when the zero-ination proportion decreases (respectively increases).

Finally, in order to assess quality of the Gaussian approximation stated in Theorem 3.2, we obtain normal Q-Q plots of the estimates and histograms of the normalized estimates ( β j,n -β j )/standard error( β j,n ), j = 1, . . . , 6 and ( γ k,n -γ k )/standard error( γ k,n ), j = 1, . . . , 5.

We provide these graphs for n = 500 with a proportion of zero-ination equal to 0.4 and 40% of censoring (see gures 1 to 4). Plots for the other (and more favorable) simulated scenarios yield similar observations and are thus not given. From these gures, it appears that the Gaussian approximation of the distribution of the MLE is reasonably satised, even when the sample size is moderate and the proportions of zero-ination and censoring are as high as 0.4. q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q -3 -2 -1 0 1 2 3 -0.5 0.5

1.5 Normal Q-Q plot for β 1,n
Theoretical Quantiles Sample Quantiles q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q -3 -2 -1 0 1 2 3 -0.3 0.0 0.2 0.4

Normal Q-Q plot for β 2,n Theoretical Quantiles Sample Quantiles q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q -3 -

2 -1 0 1 2 3 0.0 0.4 0.8 Normal Q-Q plot for β 3,n
Theoretical Quantiles Sample Quantiles q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q -3 -2 -1 0 1 2 3 0.7 0.9

1.1 Normal Q-Q plot for β 4,n
Theoretical Quantiles Sample Quantiles q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q -3 -2 -1 0 1 2 3 -0.9

-0.6 -0.3 Normal Q-Q plot for β 5,n
Theoretical Quantiles Sample Quantiles q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q qq q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q -3 -

2 -1 0 1 2 3 -0.3 0.0 0.2 Normal Q-Q plot for β 6,n
Theoretical Quantiles

Sample Quantiles

Figure 1: Normal Q-Q plots for β1,n , . . . , β6,n with n = 500, c = 0.4 and a proportion of zero-ination equal to 0.4.

5. An application in health economics: demand for physician service

We illustrate maximum likelihood estimation in a censored ZIP regression model on a dataset coming from the National Medical Expenditure Survey 1987-1988 (a large crosssectional study carried out to assess the demand for medical care in USA, see [START_REF] Deb | Demand for medical care by the elderly: a nite mixture approach[END_REF]. Data are available in the R package AER [START_REF] Kleiber | Applied Econometrics with R[END_REF] under the name "NMES1988". They contain observations on 4,406 individuals aged 66 and over, all of whom are covered by Medicare (a federal health insurance program). The response variable is the number of visits to a physician in an oce setting (denoted by ofp in what follows). Explanatory variables include demographics: gender (1 for female, 0 for male), age (in years, divided by 10), socio-economic variables: marital status (1 if married, 0 otherwise), educational level (number of years of education, denoted by school), family income (in ten-thousands of dollars), two binary variables indicating whether individual is covered by Medicaid (a US health insurance for individuals with low resources) and by a supplemental private insurance (both are coded as 1 if yes and 0 otherwise), various measures of health status: number of chronic conditions (cancer, arthritis, diabete. . . denoted by chronic) and a variable indicating self-perceived health level (poor, average, excellent), which we recode as health1 (1 if health is perceived as poor, 0 otherwise) and health2 (1 health is perceived as excellent, 0 otherwise).

In the inital data, the response ofp is uncensored. But since NMES1988 has become a benchmark dataset for evaluating zero-inated models, we choose to use it and to censor ofp articially. We use a zero-truncated Poisson distribution to generate censoring values. Average sample censoring proportions of ofp are successively set to 0.2 and 0.4. The tted model is:

           log(λ i (β)) = β 1 + β 2 gender i + β 3 age i + β 4 marital_status i + β 5 school i + β 6 income i +β 7 medicaid i + β 8 insurance i + β 9 chronic i + β 10 health1 i + β 11 health2 i , logit(ω i (γ)) = γ 1 + γ 2 gender i + γ 3 age i + γ 4 marital_status i + γ 5 school i + γ 6 income i +γ 7 medicaid i + γ 8 insurance i + γ 9 chronic i + γ 10 health1 i + γ 11 health2 i .
Maximum likelihood estimates and standard errors for all model parameters are obtained in both censored and non-censored cases. Results are summarized in Table 7. The no-censoring case was already investigated using various models (e.g., [START_REF] Cameron | Regression Analysis of Count Data[END_REF][START_REF] Friendly | Discrete Data Analysis with R: Visualization and Modeling Techniques for Categorical and Count Data[END_REF][START_REF] Diallo | Analysis of multinomial counts with joint zeroination, with an application to health economics[END_REF]. Consistent with these studies, we nd that both number of chronic conditions and self-perceived health are important determinants of ofp utilization. An increase in the number of chronic diseases increases both the probability of visiting a doctor and the average number of consultations. We nd that measures of self-perceived health do not aect the decision of visiting a doctor (the eect of health status on this decision is entirely captured by chronic) but aect the average number of visits (this number increases as health perception degradates). Individuals with higher educational level are less susceptible to waive ofp-type health-care. They also seek care more often. At the same time, income is non-signicant in both models for zero-ination and visits frquency (in [START_REF] Deb | Demand for medical care by the elderly: a nite mixture approach[END_REF], authors formulate the hypothesis that the overall generosity of Medicare make ofp utilization insensitive to changes in the income). Also consistent with previous analysis, in the censored case, Medicaid and supplementary private insurance coverage are signicant determinants of both decision of visiting a doctor and number of visits (as expected, covered individuals are less susceptible to waive ofp-type consultations, they also seek care more often).

As already observed in our simulations, parameters estimates and standard errors in ω i (γ) are only slightly aected by censoring. Therefore, Wald signicance tests agree whatever the censoring fraction. Parameters estimates and standard errors in the Poisson model part are more sensitive to censoring. Wald signicance tests agree for all regressors except age, gender and marital status, where both increasing bias and standard errors resulting from censoring yield misleading conclusions.

Overall, MLEs in censored ZIP regression seem to be rather robust to censoring. In particular, estimation and variable selection in the zero-ination model part are not aected by censoring (even when the censoring fraction is large).

Discussion

In this paper, we consider estimation in zero-inated Poisson regression model when the count response is randomly right-censored. We establish consistency and asymptotic normality of the MLE in this setting. Our numerical study conrms the good performance of MLE. In particular, we show that estimation and variable selection in the zero-ination model part are not aected by censoring. q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q -3 -2 -1 0 1 2 3 -0.4 0.0 0.4 0.8 Normal Q-Q plot for γ 1,n Theoretical Quantiles Sample Quantiles q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q -3 -

2 -1 0 1 2 3 -1.2 -0.8 -0.4 Normal Q-Q plot for γ 2,n
Theoretical Quantiles Sample Quantiles q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q -3 -

2 -1 0 1 2 3 -1.0 0.0 0.5 Normal Q-Q plot for γ 3,n
Theoretical Quantiles Sample Quantiles q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q -3 -2 -1 0 1 2 3 0.2 0.6 1.0

Normal Q-Q plot for γ 4,n Theoretical Quantiles Sample Quantiles q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q -3 -2 -1 0

Figure 2 :

 2 Figure 2: Normal Q-Q plots for γ1,n , . . . , γ5,n with n = 500, c = 0.4 and a proportion of zero-ination equal to 0.4.

  Now, several issues deserve attention, such as estimation in ZIP regression under various other censoring schemes (left-censoring, interval censoring). Investigating estimation in more general models (e.g., semi-parametric zero-inated Poisson model, zero-inated generalized Poisson regression model,. . . ) with censoring is also desirable. All these issues constitute topics for our future work.

		no censoring	censoring = 20%	censoring = 40%
	variable	estimate (s.e.) signif. estimate (s.e.) signif. estimate (s.e.) signif.
		Poisson model coecients
	intercept	1.7596 (0.0878) *** 1.3491 (0.2057) *** 1.1464 (0.1246) ***
	gender	0.0066 (0.0144)	0.0487 (0.0165) **	0.0377 (0.0201)	.
	age	-0.0593 (0.0107) *** -0.0148 (0.0248)	-0.0102 (0.0152)
	marital status -0.0796 (0.0148) *** -0.0269 (0.0140) .	-0.0072 (0.0209)
	school	0.0209 (0.0020) *** 0.0130 (0.0015) *** 0.0144 (0.0027) ***
	income	-0.0014 (0.0023)	-0.0008 (0.0026)	-0.0038 (0.0032)
	medicaid	0.2256 (0.0254) *** 0.1799 (0.0297) *** 0.1681 (0.0369) ***
	insurance	0.1892 (0.0200) *** 0.1387 (0.0228) *** 0.1638 (0.0274) ***
	chronic	0.1198 (0.0046) *** 0.1150 (0.0056) *** 0.1191 (0.0070) ***
	health1	0.3081 (0.0175) *** 0.2285 (0.0212) *** 0.1971 (0.0272) ***
	health2	-0.3224 (0.0312) *** -0.2532 (0.0338) *** -0.2018 (0.0383) ***
		Zero-ination model coecients
	intercept	1.9786 (0.5917) *** 1.9597 (0.6870) **	1.9709 (0.7531) **
	gender	-0.4721 (0.0974) *** -0.4716 (0.0997) *** -0.4840 (0.1020) ***
	age	-0.1829 (0.0741) *	-0.1818 (0.0862) *	-0.1876 (0.0947) *
	marital status -0.2843 (0.1033) **	-0.2862 (0.1060) **	-0.2921 (0.1087) **
	school	-0.0607 (0.0128) *** -0.0614 (0.0131) *** -0.0611 (0.0136) ***
	income	-0.0104 (0.0188)	-0.0104 (0.0193)	-0.0120 (0.0201)
	medicaid	-0.4921 (0.1713) **	-0.4928 (0.1718) **	-0.4875 (0.1767) **
	insurance	-0.8227 (0.1102) *** -0.8299 (0.1099) *** -0.8272 (0.1145) ***
	chronic	-0.5414 (0.0458) *** -0.5393 (0.0464) *** -0.5360 (0.0479) ***
	health1	0.0124 (0.1615)	0.0212 (0.1605)	0.0380 (0.1669)
	health2	0.2447 (0.1505)	0.2398 (0.1594)	0.2410 (0.1575)

Table 7 :

 7 Health-care data analysis: estimates (standard errors) and signicance codes: *** signicant at the 0.1% level, ** signicant at the 1% level, * signicant at the 5% level, . signicant at the 10% level.

Acknowledgements

Authors acknowledge nancial support from the Ministry of Education and Training of the Republic of Vietnam and the French Embassy in Vietnam and logistical support from Campus France (French national agency for the promotion of higher education, international student services, and international mobility).

Appendix

Lemma 6.1. Assume conditions C1-C4 hold. Then sup ψ∈Nn(ε) F

-I k converges in probability to 0 as n → ∞.

Proof of Lemma 6.1. We have

by C3. Thus, the lemma is proved if we can show that both terms in the right-hand side of the last inequality converge to 0 uniformly in ψ ∈ N n (ε) as n → ∞. For illustration purposes, we show that sup ψ∈Nn(ε)

We prove that sup ψ∈Nn(ε

converges in probability to 0 as n → ∞ (the other two terms can be treated similarly). For this, we prove that the class {X i X im δ i J i u i (ψ) : ψ ∈ C} is Donsker (and thus Glivenko-Cantelli, which will ensure the required uniform (over ψ) convergence). We refer to van der [START_REF] Van Der Vaart | Weak convergence and empirical processes: with applications to statistics[END_REF] for denitions and properties of this classes. The class {X i X im δ i J i } is obviously Donsker. Under C1 and C2, classes {β X i : β ∈ B} and {γ W i : γ ∈ G} are Donsker. The exponential function is Lipschitz on compact sets therefore classes {e β X i : β ∈ B}, {e -exp(β X i ) : β ∈ B} and {e γ W i : γ ∈ G} are also Donsker. Now, products and sums of bounded Donsker classes are Donsker (van der Vaart and Wellner, 1996), therefore, the class {X i X im δ i J i u i (ψ) : ψ ∈ C} is Donsker. Hence,

also converges to 0 as n → ∞, which concludes the proof.


Francesco † Poletti
email: fpoletti@deis.unibo.it

Poggiali Antonio
email: apoggiali@deis.unibo.it

Paul Marchal
email: marchal@imec.be

Flexible hardware/software support for message passing on a distributed shared memory architecture

With the advent of multi-processor systems on a chip, the interest for message passing libraries has revived. Message passing helps in mastering the design complexity of parallel systems. However, to satisfy the stringent energy-budget of embedded applications, the message passing overhead should be limited. Recently, several hardware extensions have been proposed for reducing the transfer cost on a distributed memory architecture. Unfortunately, they ignore the synchronization cost between sender/receiver and/or require many dedicated hardware blocks. To overcome the above limitations, we present in this paper light-weight support for message passing. Moreover, we have made our library as flexible as possible such that we can optimally match the application with the target architecture. We demonstrate the benefits of our approach by means of representative benchmarks from the multimedia domain..

Introduction

Many designers turn towards parallel systems to reduce energy cost. They master design complexity with high level programming models such as message passing (e.g., openMP and MPI). After specifying the program with message passing, efficient mapping on the target architecture is required. This entails reducing both the amount of communication and the transmission cost itself.

Our goal is reducing the cost for communicating messages between tasks located on different processors. In the simplest case, message passing is implemented on top of a shared memory architecture (e.g., [START_REF] Rutten | Eclipse: heterogeneous multiprocessor architecture for flexible media processing[END_REF] [START_REF]A 160mW, 80nA Standby, MPEG-4 Audiovisual LSI 16Mb Embedded DRAM and a 5 GOPS Adaptive Post Filter[END_REF]). The producer generates a message in the shared memory. When ready, it notifies the consumer that it can start reading it. At least two locks are necessary for synchronizing the producer/consumer. A first lock (set by the producer) prevents the consumer from reading a not finalized message. A second lock (set by the consumer) prevents the producer from overwriting messages still unread by the consumer. In this naive implementation, the shared memory is frequently accessed, and easily becomes a performance bottleneck.

This bottleneck can be removed by directly transmitting messages between scratchpad memories attached to the processors, but this requires architectural changes. For instance, a scratchpad memory is usually only accessible from the core to which it is attached. Now, any other core of the system may have access to it. Recently, [START_REF] Gilbert | Communication centric architectures for turbo-decoding on embedded multiprocessors[END_REF] and [START_REF] Hand | An effi cient scalable and flexible data transfer architectures for multiprocessor SoC with massive distributed memory[END_REF] have presented such hardware extensions. However, these are mostly ad-hoc solutions, which are not flexible enough for matching the application with the target architecture. E.g., they only provide DMAs to transfer data between processors. For short messages the overhead to set up the DMA is too long. Direct write/read transfers by the processor are more efficient, but in this case they are not supported.

Moreover, in view of the limited size of the scratchpad memories (particularly on a power-efficient embedded systems), only small messages can be transmitted. Consequently, the processors need to communicate and synchronize more frequently compared to a shared memory implementation. So far, limited research exists on reducing the synchronization cost; synchronization is mostly implemented with semaphores stored on a shared memory. Therefore, it often remains a performance bottleneck (see our experimental results).

In this paper, we propose a hardware/software approach for message passing on a distributed memory architecture. We provide several communication modes (from single word access to burst accesses to the remote memory nodes) and support multi-threading as an alternative technique to reduce the communication latency. Finally, we have integrated our approach on a cycle-accurate exploration environment [START_REF] Loghi | Analyzing Chip Communication in a MPSoC Environment[END_REF].

This paper is organized as follows. After describing the prior-art in section 2, we discuss the hardware extensions necessary for our approach (section 3) and explain how we support them in software (section 4). With this high-level API, we can tune the application to the target architecture as demonstrated with a small example in section 5. Finally, we quantify our approach with realistic examples (section 6).

Related work

A large body of related work exist on message passing as a programming model (e.g., OpenMP or MPI); mapping a message passing program on a multi-processor architecture for reducing communication [START_REF] Banerjee | Overview of the PARADIGM Compiler for Distributed Memory Message-Passing Multicomputers[END_REF][7] and finally, building hardware/software support for reducing the execution time/energy of transmitting a message in both software or hardware [START_REF] Culler | Parallel Computer Architecture: A Hardware/Software Approach[END_REF] [START_REF] Byrd | Producer-Consumer Communication in Distributed Shared Memory Multiprocessors[END_REF].

We focus on reducing the message passing overhead, which can be decomposed in two parts: overhead for setting up and controlling the communication and the data transfer overhead itself.

Message passing has first been applied in the high performance community, where many techniques have been developed for reducing either costs. E.g., several authors simplify OS-layers from the message passing interface to reduce the setup cost (e.g., [START_REF] Banekazemi | MP-LAPI: An effi cient implementation of MPI for IBM RS/6000 SP systems[END_REF]). Others move message passing primitives in hardware, ranging from dedicated instructions (e.g., [START_REF] Lee | An effi cient protected message interface[END_REF]) to complex co-processors for accelerating message passing (e.g., [START_REF] Ramachandran | Hardware support for interprocess communication[END_REF]). Dedicated instructions coupled to a low latency communication network support fine granularity messages, enabling massive amounts of parallelism. However, this approach requires tedious code manipulation that reduces the portability of the code and thus jeopardizes the ROI. Solutions based on co-processors, on the other hand, focus on flexibility and performance, but their area and energy overhead makes them not suitable for embedded systems.

With the advent of multi-processor systems on chip, message passing has also entered the world of embedded systems. Message passing is here usually implemented on top of a shared memory architecture (e.g. TI OMAP, Philips Eclipse [START_REF] Rutten | Eclipse: heterogeneous multiprocessor architecture for flexible media processing[END_REF], [START_REF]A 160mW, 80nA Standby, MPEG-4 Audiovisual LSI 16Mb Embedded DRAM and a 5 GOPS Adaptive Post Filter[END_REF], Philips Nexperia). The shared memory is a performance/energy bottleneck, even when DMAs are used to increase the transfer efficiency. On most architectures, the atomic memory operations necessary for semaphores require locked transactions over the communication architecture. This not only further degrades the performance, but limits the scalability of the above implementations for more advanced communication architectures.

Therefore, several authors have recently proposed support for message-passing on a distributed memory architecture. An interesting case-study is presented in [START_REF] Gilbert | Communication centric architectures for turbo-decoding on embedded multiprocessors[END_REF] where a turbo-coder is mapped on a message-passing architecture. On each processing tile an IO-device is responsible for transmitting/receiving messages from the communication architecture. Buffer underflow/overflow of the IO-device has to be avoided in software. In [START_REF] Hand | An effi cient scalable and flexible data transfer architectures for multiprocessor SoC with massive distributed memory[END_REF], is provided more generic support for message passing. An extra co-processor, called a memory server access point, is added to each processor. The access point links the processor to its own local memory, but also to the remote memories. The synchronization is left to the message passing protocol.

Above approaches lack support for synchronization and flexibility in matching the application to the communication architecture. E.g., in [START_REF] Hand | An effi cient scalable and flexible data transfer architectures for multiprocessor SoC with massive distributed memory[END_REF] remote memories are always accessed with a DMA-like engine even though this is not the most efficient strategy for small message sizes.

In the remainder of this paper, we present a more scalable and flexible message passing implementation. On most embedded multi-processors, message passing is implemented on top of shared memory (Fig. 1-left). The producer and consumer tasks communicate over a FIFO queue stored in the shared memory. The FIFO contains space for a fixed set of messages. If the producer wants to send a message to the consumer, it first looks for free space in the queue by checking the queue's control structure. After finding free space, it writes the message in the queue, from which the consumer can then read it.

Hardware support for message passing

Slave port

Shared Memory

Mutex

To prevent the queue from over(under)flowing, the consumer and producer are synchronized. Synchronization is implemented with semaphores and thus with atomic memory accesses. Atomic memory accesses are implemented by locking the bus. As long as a master locks the bus, the arbiter does not grant it to any other master. Consequently, the granted master can perform atomic memory operations. Despite locked transfers being supported by most bus-based architectures, they do not match well with scalable communication architectures where the arbiter is distributed (e.g., cross-bars or NoCs). On the latter architectures, semaphores are mostly supported with dedicated load/store instructions to the shared memory (i.e., test-and-set [START_REF] Hennessy | Computer Architecture: A Quantitative Approach[END_REF]). In the above approach, shared memory is frequently used. Even if shared memory can be implemented on-chip, it remains a performance bottleneck. To guarantee data coherency, shared data cannot be cached and this results in long access latencies. 1We remove the need for shared memory by providing message passing support on a distributed memory architecture (Fig. 1-right). To send a message on our architecture, the producer now writes in the message queue stored on its local memory. After the message is ready, the consumer can transfer it to its own scratchpad or to a private memory space. 2 Data can be transferred either by the processor itself or by a direct memory access controller, when the hardware supports this. This transfer is only possible when the consumer can read from the scratchpad memory of another processor. The scratchpad memories should therefore also be connected as a slave port to the communication architecture and their memory space should be visible by the other processors.

Obviously, the producer/consumer should still have to be synchronized. We use two integer semaphores for this purpose. E.g., when a producer generates a message, it locally checks an integer semaphore which contains the number of free messages in the queue. If a space is available, it decrements the semaphore and starts writing the message. When the message is ready, it signals this to the consumer by incrementing the consumer pointer. Instead of storing the semaphores in the shared memory, we distribute them among the processing elements. This has two advantages: the read/write traffic to the semaphores is distributed and the producer(consumer) can locally poll whether space (a message) is available, thereby reducing the traffic on the communication architecture.

The semaphore is itself a memory device on which atomic test-and-set operations can be performed. Furthermore, our semaphore may interrupt the local processor when released, providing an alternative mechanism to semaphore polling. When a task fails to acquire a semaphore, it usually starts spinning around the semaphore until it is released. This however prevents the processor from executing more useful instructions, particularly if it takes a long time for the semaphore to be released. If the semaphore is not available, the task registers itself on a list of tasks waiting for that semaphore and suspends itself. Other tasks on the processor can then execute. As soon as the semaphore is released, it generates an interrupt and the corresponding interrupt routine reactivates all tasks on the wait list. This helps us to efficiently We thus only require a limited amount of extra hardware. Since both DMAs and scratchpad memories are readily available on most cores, only the interface to the communication architecture has to be slightly modified and the semaphore needs to be added. We have integrated a cycleaccurate model of the scratchpad, DMA, semaphores and scratchpad memory in the MPARM exploration environment [START_REF] Loghi | Analyzing Chip Communication in a MPSoC Environment[END_REF]. In the next section, we describe the software support for hardware programming.

Software support

We have built a high-level API to support message passing. Our library simplifies the programming of message passing but is sufficiently flexible for exploring the design space. The most important functions are listed in Tab. 1.

To instantiate a queue, both the producer and consumer must run an initialization routine. To initialize the producer, we call sq_init_producer. It takes as arguments the address of the consumer's semaphore, the message size, the number of messages in the queue and a binary value. The last argument specifies whether the producer should poll the producer's semaphore or suspend itself until an interrupt is generated by the semaphore. The consumer is initialized with sq_init_consumer. It requires the address of the queue's control structure on the producer side to access the producer's semaphore, the queue buffer itself and the poll/suspend flag. Furthermore, it needs the address where it can store the message transferred from the producer's message queue. This address can be located either on the local memory or on the scratchpad memory.

The producer sends a message with the sq_write(_dma) function. This function copies the data from *source to a free message block inside of the queue buffer. This transfer can either be done by the core or with a dma (x_dma). Instead of copying the data from *source into a message Figure 2. Read cost analysis block, the producer has the option of directly generating data in a free message block. The sq_getToken_write returns a free block in the queue's buffer on which the producer can operate. When data is ready, the producer should mark its availability to the consumer with sq_putToken_write. The consumer transfers a message from the producer's queue to a private message buffer with void sq_read(_dma). Again, the transfer can be performed either by a local DMA or the core itself.

Our approach thus supports: (1) either processor or DMA-initiated data transfers to remote memories, (2) either polling-based or interrupt-based synchronization, and (3) flexible allocation of the consumer's message buffer, i.e. on scratchpad or in an external private memory. Thanks to the high-level API this flexibility can be effectively used to optimize message passing based applications.

Flexible communication primitives

Cost analysis

We are interested in the time required for a consumer to obtain a message available on the producer's queue (Fig. 2). Here, we do not quantify the synchronization overhead since it is highly application dependent. 3 We measure the execution time for different message sizes using either the processors or DMAs for transfers. The first curve is generated by storing the message buffer in the shared memory and using the processor for transferring the data. We can improve on this result by storing the message buffer in the scratchpad. The longer the message, the more the application's execution time is dominated by memory transfers. Hence, performance gains become larger when using a fast scratchpad memory instead of slow shared memory. The fixed setup cost for programming DMA can clearly be seen for zero-sized messages. As soon as the message size exceeds 25 words, the increased transfer efficiency compared to explicit copying outweighs the setup cost.

Finally, we store the message read by the consumer in its local scratchpad memory. This further reduces the execution time since less data has to be fetched from the con- sumer's private memory across the communication architecture. Again, the larger the message size, the larger the performance gains become. When many large message are transmitted the communication, architecture becomes congested. As a result, removing traffic from the fabric has a direct impact on the performance.

The advantage of flexibility

In this subsection we use a simple example to show that flexibility improves the results. Our example consists of a pipeline of eight matrix multiplication tasks. Each stage of this pipeline takes a matrix as input, multiplies it with a local matrix and passes the result to the next stage. We iterate the pipeline twenty times. We run the benchmark respectively on an architecture with eight and four processors, in the first case only one task is executed on each processor, while in the second we added concurrency on each core by schedule of two tasks.

First, we compare five different implementations of message passing (Tab. 2). Furthermore, we execute the pipeline on eight processors for respectively a matrix of 8x8 and 32x32 elements. In the latter case, longer messages are transmitted. The results (Fig. 3) clearly show that message passing on a distributed memory architecture improves the throughput and reduce the energy. Not only the application performs faster, but also the energy per scratchpad access is lower than that for shared memory. Analyzing the results in detail we can observe that A DMA is not always beneficial in terms of throughput. For small messages the overhead for setting up the DMA is not justified. The consumer's processor can better directly copy the data to its local scratchpad memory. In case of larger message sizes, the DMA outperforms the processor. Instead, employing A DMA always leads to an energy reduction, even if the duration of the benchmark is longer, due to a more efficient data transfer.

Furthermore the way a consumer is notified of the arrival of a message plays an important role. The consumer has to wait until the producer releases the consumer's semaphore. With a single task per processor, the overhead related to the interrupt routine slows down the system, and polling is more efficient. When we add interrupt support to the distributed approach, the throughput we obtain does not get worse, as in the case of shared memory. This is mainly due to a more efficient hardware/software support we can provide in case of distributed approach. In any case, the energy consumption increases significantly due to the instruction cache cost we pay in order to manage the suspension of a task.

Secondly, we investigate the impact of scheduling on synchronization (Fig. 3). We adopt an architecture with four processors and we execute two tasks on each processor, for a matrix of 8x8 elements. In this case the interrupt-based approach performs better for multiple tasks on a single processor. Multi-threading effectively hides the communication latency of the message both for shared and scratchpad. The scratchpad solution has always better throughput compared to the shared approach. Instead, if we compare the results of shared memory with interrupt to the scratch with active polling, we notice that they have the same throughput but the second one consume a significantly larger amount of energy. In this case, it is more convenient to suspend the task because probably the other task scheduled on the processor is in a "ready" status. This is the cost we pay for active polling, which stalls the processor instead of scheduling another task.

From this example, we thus conclude that in order to optimize the energy and the throughput, the implementation of message passing should be matched with application's load. This is only possible with a flexible message passing library. QSDPCM is an advanced inter-frame compression technique for video streams. The algorithm first applies motion estimation and then compresses the motion compensated frame-to-frame difference signal. The motion estimation of each 16x16 pixel block can be independently processed. Therefore, the original frame can be divided in n clusters on which we apply motion estimation in parallel. Each motion estimation task sends its output to a collector task that generates the compressed bit stream.

We have executed four different versions of this benchmark (see Fig. 5). In the simplest case, we leverage message passing on shared memory. The input image also resides in the non-cacheable shared memory, hampering the performance [START_REF] Banekazemi | MP-LAPI: An effi cient implementation of MPI for IBM RS/6000 SP systems[END_REF]. Secondly, we copy the block on which each task operates in the external cacheable memory, which eliminates most accesses to the shared memory [START_REF] Banerjee | Overview of the PARADIGM Compiler for Distributed Memory Message-Passing Multicomputers[END_REF]. Thirdly, we implement message passing on a distributed memory with our approach (3). The performance only slightly improves compared to (2) since in this application relatively few messages are transmitted. Finally, we use DMA for transferring the data. DMA is more efficient for transferring data from the shared memory into the local scratchpad. It can transfer the data in bursts, whereas the processor has to copy element by element and is bad in generating the addresses.

DES encryption -ECB mode

DES encrypts and decrypts data using a 64-bit key. It splits input data into 64-bit chunks and outputs a stream of 64-bit ciphered blocks. Since each input element is independently encrypted from all others, the algorithm can be easily parallelized. An initiator task dispatches 64-bit blocks together with a 64-bit key to n calculator tasks for encryption. A collector task exists, which rebuilds an output stream by concatenating the ciphered blocks of text from the calculator tasks.

We have simulated different system architectures, focusing on two main performance issues: first, the scalability Fig. 6-left illustrates the scaling of four different communication techniques with varying amounts of system processors running on a shared bus interconnect. The approach based on shared memory queuing exhibits the worst execution times and additionally has the worst scalability, due to its intrinsic performance bottleneck. Both the two techniques exploiting scratchpad and shared memory quickly saturate the interconnect and are unable to scale effectively. In particular, the scratchpad solution saturates the bus with more than 4 processor, while the shared memory approach continues to scale until 8 processors, but never reaches the performance of the distributed approach.

That's why we decided to introduce a more scalable interconnect which allows us to see whether the scalability limitations is originated by the nature of the benchmark or by an hardware limitation. Fig. 6-right illustrates the impact of a full crossbar interconnect fabric in place of the shared bus used for the previous set of benchmarks. All figures express the improvement against the shared bus baseline. As expected, the crossbar performs better in every instance, and even more so with increasing numbers of cores. However, when using the shared approach, performance results are not scaling, because, despite the extreme congestion it imposes on the fabric, traffic is mostly bound by contention for a single slave. While, on the other hand, performance of the distributed approach still scales of a by 15% when varing from 8 to 12 cores. This demonstrates the relevance of the distribute memory access for its better scalability results.

Conclusion

We have presented a complete HW-SW solution for message passing implemented on an MPSoC with a distributed shared memory architecture. By distributing semaphores across the processing nodes and connecting the scratchpad memories to the communication network with slave ports, we can efficiently and flexibly implement message passing. The flexibility arises from different transfer (DMA/processor-initiated) and synchronization modes. We exploit it to optimally match the application to the target architecture. Small messages, e.g., are better transmitted by a processor than by a DMA. The distributed semaphores enable efficient multi-threading, which allows effective hiding of the communication latency. Experimental results on several realistic examples motivate the need for this flexible approach.

Figure 1 .

 1 Figure 1. Message passing on shared memory (left) vs. on distributed memory (right)

Figure 4 .

 4 Figure 4. Task scheduling impact on synchronization

Figure 5 .

 5 Figure 5. Execution time of QSDPCM

Figure 6 .

 6 Figure 6. Performance scalability of the DES benchmark

Table 1 . Our message passing library API support

 1 multi-threading to reduce the communication latency, as we will explain below.

	return type	function	arguments
	SQ_PRODUCER*	sq_init_producer	int core_number
			void* consumer
			int message_size
			int total_messages
			bool use_suspension
	SQ_CONSUMER*	sq_init_consumer	void* producer
			char* buffer_space
			bool use_suspension
	void	sq_write(_dma)	SQ_PRODUCER *queue_p
			char *source
	char*	sq_getToken_write	SQ_PRODUCER *queue_p
	void	sq_putToken_write	SQ_PRODUCER *queue_p
	char*	sq_read(_dma)	SQ_CONSUMER *queue_c

Table 2 . Different message passing imple- mentations Figure 3. Comparison of message passing implementations from Tab. 2

 2

	solution	queue position	transfer mode	arrival notifi cation
	(1)	shared	processor	polling
	(2)	shared	processor	interrupt
	(3)	scratchpad	processor	polling
	(4)	scratchpad	processor	interrupt
	(5)	scratchpad	dma	polling

3 We refer to Section 6 for experimental results on real applications.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Unless cache coherency is guaranteed in hardware which easily impacts the design complexity and scalability.

2 We use the private memory for the consumer if insuffi cient space is available on the consumer's scratchpad memory. The private memory is still faster than the shared memory since it is cacheable.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)