Annabelle Lapostolle

Veronique Massari

Pierre Chauvin

Keywords: hiv testing, migrants, socioeconomic factors HIV testing, migrants, socioeconomic factors, France

HAL is

INTRODUCTION

Since the advent of effective treatments against HIV, the benefits of timely access to treatment after HIV infection have been largely documented in terms of morbidity and mortality reduction, [START_REF] Girardi | Delayed presentation and late testing for HIV: demographic and behavioral risk factors in a multicenter study in Italy[END_REF][START_REF] Hogg | Rates of disease progression by baseline CD4 cell count and viral load after initiating triple-drug therapy[END_REF][START_REF] Palella | Survival benefit of initiating antiretroviral therapy in HIV-infected persons in different CD4+ cell strata[END_REF][START_REF] Sabin | Late presenters in the era of highly active antiretroviral therapy: uptake of and responses to antiretroviral therapy[END_REF]. Timely access to treatment requires not only adequate postdiagnostic management, but timely testing as well. The current trend is to treat patients earlier and earlier, since initiating compared to initiating it when the count is between 351/µL and 450/µL [START_REF] Sterne | Timing of initiation of antiretroviral therapy in AIDS-free HIV-1-infected patients: a collaborative analysis of 18 HIV cohort studies[END_REF].

In France, HIV testing policy is based on the opt-in approach. HIV testing is widely delivered in hospitals, in public and private laboratories, in free and anonymous testing centres, and also largely provided in primary care [START_REF] Massari | Trends in voluntary HIV testing in general practices in France between 1987 and 2002[END_REF][START_REF] Mounier-Jack | HIV testing strategies across European countries[END_REF]. HIV testing is offered systematically by health professionals to some specific populations (pregnant women, new tuberculosis patients, prisoners). Mandatory screening concerns only blood, sperm and tissue donors. Despite this large offer of testing, 36% of infected individuals are tested when they already have an AIDS defining illness or are greatly immunocompromised [START_REF] Invs | Surveillance du VIH/sida en France: Données au 30 juin 2005[END_REF]. The specific risk of late testing in immigrant populations has been reported several times, in particular in people of African origin, [START_REF] Chee | Medical and social differences between French and migrant patients consulting for the first time for HIV infection[END_REF][START_REF] Delpierre | High-Risk groups for late diagnosis of HIV infection: a need for rethinking testing policy in the general population[END_REF][START_REF] Delpierre | Correlates of late HIV diagnosis: implications for testing policy[END_REF][START_REF] Dray-Spira | Social health inequalities during the course of chronic HIV disease in the era of highly active antiretroviral therapy[END_REF][START_REF] Lanoy | Frequency, determinants and consequences of delayed access to care for HIV infection in France[END_REF]. In 2003, France's public authorities initiated HIV prevention information campaigns targeted at these populations. A study conducted in 2003 revealed two categories of immigrants who have been diagnosed late: men who have been in France for a long time and for whom late testing is associated primarily with delaying their entry to the health-care system, and young women who have recently arrived and for whom late testing is due to the duration between infection and migration [START_REF] Calvez | Les personnes originaires d'Afrique subsaharienne en accès tardif aux soins pour le VIH : données de l'enquête Retard, France, novembre 2003-aout 2004[END_REF].

Recently, a new testing paradigm was proposed in France, with recommendations from the Haute Autorité de Santé (High Health Authority)(HAS, 2009) which, for the first time, proposed screening schedules on the basis of results from modelling studies among high-risk populations (multi-partner MSM, IDUs, and multi-partner individuals from sub-Saharan Africa or the Caribbean). For them, it is now recommended that HIV screening be done every year. (which is, of all the regions in mainland France, the one with the highest number and proportion of AIDS cases and immigrant people). We aimed to determine, in particular, the mean time since the last test in people of African origin and to study if the potential effect of nationality was in relation to the duration of time lived in France and the difficulties in writing/reading French.

METHOD

Data collection

The SIRS (a French acronym for health, inequalities and social ruptures) cohort is the first large, representative, population-based French cohort set up to study the social determinants of health and health-care utilization in the field of social epidemiology (Chauvin & Parizot, 2009;[START_REF] Renahy | Health information seeking on the Internet: a double divide? Results from a representative survey in the Paris metropolitan area, France, 2005-2006[END_REF].

Our study population was a multistage-random sample of the adult French-speaking population living in the Paris metropolitan area. The primary sampling units were census blocks: 50 of them were randomly selected from the 2595 eligible census blocks in Paris and its suburbs, according to their socioeconomic type. At the second level, 60 households were chosen at random in each census block. Lastly, one adult in each household was randomly selected for interviewing using the next-birthday method (the adult chosen was the person in the household who will have the next birthday).

The questionnaires were administered face-to-face at the interviewee's home. In all, 29% of the individuals contacted declined to answer the survey, 2% said that they were too sick to answer, and, lastly, 3% were excluded because they did not speak French.

Variables

Of interest here is the date of the last HIV test performed among those individuals who reported having been tested at least once in their lifetime. Of the 3023 individuals interviewed, one person did not want to answer, 30 indicated that they did not know whether or not they had ever been tested, 1286 (42.5%) had never been tested, and, lastly, 1706 (56.4%) indicated that they had been tested for HIV. Amongst these people, 1642 (96.2%)

answered the question "how many years it had been since their last test".

Based on previous analyses of the determinants of HIV testing uptake in the cohort [START_REF] Massari | Gender, socio economic status and migration are barriers to HIV testing in Paris area[END_REF][START_REF] Wynne | Factors related to HIV Testing Among Different Migrant Populations in Paris[END_REF], the following variables of interest were chosen for the analyses: age which was divided into four groups (18-29 years, 30-44 years, 45-59 years and 60 years and older); socioprofessional groups (derived from the French national bureau of statistic which distinguishes between worker, employee, craftsmen/shopkeepers, executive/management, intermediary position, and never employed and/or students -retired or unemployed people being classified according to their last job); the number of sequential steady relationships (0, 1, 2 and 3 or more); the sense of belonging to an ethnic or religious community (yes/no); the feeling of being at risk to contract HIV (yes/no), the fact of having reported difficulty reading and/or writing French (yes/no).

To study migration origin, we used 1) the nationality at the time of the survey (the foreign-born migrants which had previously obtained French citizenship were then counted as French) and 2) the number of years lived in France: for those individuals who indicated that they had spent their entire lives in France (whatever their nationality), it was their age. The fact of having a child born after 1990 (vs. before 1990 or no children) was also included in the analyses. This is because in France, in 1993, a law provided for the systematic offer of HIV testing to all pregnant women during their first prenatal visit. However, this practice had already become widespread several years before this law came into existence, hence our decision to distinguish between births before and after 1990 (rather than 1993).

Statistical analyses

All the proportions and mean values presented in this paper were weighted to account for the complex sample design and for the poststratification adjustment for age and gender according to the general population census data provided by the INSEE, the French bureau of statistics.

We first performed a univariate analysis of the factors associated with having or not having been tested at least once during one's lifetime and with the mean time since the last test. The statistical tests performed were the chi-square test for proportions and ANOVA analyses for the intergroup mean differences [START_REF] Kleinbaum | Applied Regression Analysis and Multivariable Methods[END_REF].

Multivariate linear regression and ANOVA analyses were then performed for the variables found to be significantly associated in the univariate analysis. ANOVA measures two sources of variation in the data and compares their relative sizes. The F-statistic is the ratio of the between group variation divided by the within group variation. Finally, we performed two regression models: a first one to measure the effect of the nationality, a second one to tease out whether the potential effect of nationality was in relation to the duration of time in France and the difficulties in writing and/or reading French.

All the statistical processing was performed with STATA 10 © .

F

RESULTS

In 2005, 51.32% [47.15-55.48] of the men (n=730) and 58. 94% [54.94-62.28] of the women (n=943) indicated that they had been tested for HIV during their lifetime (Table 1).

For both sexes, the proportion of tested individuals was the highest in the 30-44 age-group, in people in upper white-collar positions and higher-level intellectual occupations, individuals who had had numerous steady relationships, and those who had had a child after 1990.

The proportion of men who had been tested was significantly lower among those who indicated that they had a sense of belonging to an ethnic or religious community.

We observed, for both sexes, significant differences according to the country group.

The highest proportion of individuals who indicated that they had been tested for HIV during their lifetime was found to be among those of sub-Saharan African nationality: 75-64.16]. Among women, we also observed significant differences based on the number of years lived in France. Among women, we also noted significant differences in the mean time since the last test according to age, occupational activity, having or not having had a child after 1990, nationality (F=8.95, df=3, p<0.0001) and the amount of time lived in France (F=10.67, df=3, p<0.0001). In By contrast to the results observed for men, the shortest mean time since the last test was found in women who had had a child after 1990 and in those of sub-Saharan nationality (1.66 years [0.95-2.37]).

In the first model of multivariate anova analysis among men (Table 3), the duration in years since the last HIV test was statistically different among age-groups (F=6.34, df=3, p<0.01) and according to birth after 1990 (F=8.52, df=1, p<0.01) and nationality (F=4.59, df=3, p<0.01). Coefficients issued from the multivariate linear regression showed that being aged of 30 years or more, and having had a baby after 1990 were associated with a longer duration since last test whereas being a foreigner from Sub-Saharan Africa or Northwest Africa was associated with having an HIV test more recently compared with French men.

In the second model, differences between age-groups and having had a birth after 1990

or not remained statistically significant and linear regression coefficients stayed very stable.

The intergroup difference in nationality was no longer significant with a F-value decreasing from 4.59 (in the first model) to 2.02. The linear regression coefficient increased for every foreigner nationality groups and remained statistically significant for Sub-Saharan Africans In women, in both models, only age, socio-occupational category and nationality showed significant mean time intergroup differences after adjusting for the other variables (Table 4). Unlike for men, the differences between nationality groups remained significant after introducing the amount of time lived in France and the difficulties reading and/or writing French (F=2.77, df=3, p=0.04). As observed in men, for women also, linear regression coefficients increased for Sub-Saharan Africans and Northwest Africans in the second model, compared to the first one.

DISCUSSION

The data available for the SIRS cohort in 2005 show a high level of testing uptake among people from sub-Saharan Africa in Paris metropolitan area compared to those from other countries. Thus, in our survey, the proportion of sub-Saharan Africans who indicated that they had been tested during their lifetime was 78.5% versus 56.2% for native-born French. This finding is consistent with another study of African populations on the Île-de-France carried out in 2005 (Lydié, 2007). In that survey, the lifetime testing rate in this population was 64.9% versus 53.9% for native-born French (population aged 18-49 years).

Our results also show strong differences according to gender, in particular, and once again, among African populations (93.22% in African women vs. 58.71% in men). As well, regardless of their nationality, women stated more often than men that they had had an HIV test during their lifetime. This difference can be explained, at least in part, by the strong acceptance of the screening tests (free of charge) systematically offered in France to all women during their first prenatal visit [START_REF] Moatti | Social acceptability of HIV screening among pregnant women[END_REF].

This can also explain the high proportion of Sub-Saharan African women who had ever been tested as they were more often to declare a birth after 1990 (76.06%[64.13-84.95] vs.

31.7%[28. 14-35.49] for French women). One of the main limitations of our study lies in the cohort inclusion criteria. For instance, this survey was conducted among people living in "ordinary households", with the result that people living in collective dwellings (e.g., senior citizens' homes, homeless shelters and military barracks) were not included. Also, only French-speaking people were

interviewed. Yet, we observed that the individuals (of both sexes and regardless of their nationality, even if the sample became too small for differences to be significant) who indicated that they had difficulty reading and/or writing French were less likely to have been tested once during their lifetime, which suggests that non-French-speaking people are more likely not to avail themselves of the HIV test.

In addition, for some of the individuals surveyed, particularly those who had difficulty understanding French, it is possible that there was some confusion between certain laboratory tests and the HIV test that could have led to overreporting of HIV testing uptake and an underestimate of the mean time since the last test. Nonetheless, to the best of our knowledge, this type of bias has never been described in other studies, and this bias cannot be measured with the data at our disposal. Furthermore, the mean differences between nationalities are very large, and if there is a bias that minimises these differences, it is unlikely that it would erase them completely. Finally, the retrospective questioning of the time since the last test may be skewed by memory biases but, because these times are longer for French-born people and for established immigrants, such bias leads instead to an underestimation of the differences observed between them and more recent immigrants.

In this study, no data were gathered on risk-taking (which may motivate the need for a test). Another possible cofactor, the self-perceived risk for HIV infection, was collected in our study but we did not take it into account in our regression models since no information was available on the circumstances of the last test performed. Because this last test could have been voluntary, systematic or mandatory as well, it did not seem meaningful to further explore such an association. Actually, even if people from sub-Saharan Africa interviewed in our study stated more often that they felt at risk for contracting HIV (24% vs. 16% of those of French nationality), its introduction in our models led to a non significant association and did not change our estimates. Moreover, to feel at risk for HIV infection may be ambiguously linked with individuals' testing attitudes and practices. A European review showed that, in Africans with high perception of risk, fear of death and disease may constitute a barrier for HIV testing, especially for those unable to access HIV care, either in their country of origin or in Europe (Fakoya, Reynolds, Caswell, & Shiripinda, 2008).

For both men and women, the longer the individual had lived in France, the longer, on average, the amount of time since the last test. These different elements can be explained in two different manners. On the one hand, over time, an acculturation phenomenon might lead immigrant populations to adopt health behaviors that are closer to those of the population of the host country [START_REF] Jusot | Inégalités de santé liées à l'immigration en France. Effets des conditions de vie ou sélection à la migration ?[END_REF]. On the other hand, it is possible that new immigrants are frequently tested when they settle in France and sometimes very quickly after their arrival. Indeed, a study on late HIV diagnosis in France found that the risk of late testing among immigrants increases during the first year in France (aOR: 2.15; 95% CI: 1.04-4.47). Among HIV-infected immigrants, the frequency of the combination of arriving in France and a diagnosis indicates an infection in the country of origin and a screening test (proposed by a physician or on the individual's initiative) upon arriving in France [START_REF] Delpierre | Correlates of late HIV diagnosis: implications for testing policy[END_REF].

For men, the duration of residence and difficulty mastering French no longer appeared to be significant after the different individual variables were taken into account. Nonetheless, it seems that these two variables explain, in large part, the differences in the mean time since the last HIV test between the nationality groups, since the regression coefficients for nationality changed strongly after introducing these variables into the final model. Mastery of the language (Cuellar Scale, Deyo Scale) and the duration of residence in a country have been used in different studies to measure immigrant populations' degree of acculturation─in relation to their culture of origin─and integration into the culture of the host country [START_REF] Cuellar | An acculturation scale for Mexican American normal and clinical populations[END_REF][START_REF] Deyo | A simple language-based Acculturation scale for Mexican Americans: Validation and application to health care research[END_REF][START_REF] Van Der Stuyft | Migration, acculturation and utilization of primary health care[END_REF]. The phenomenon of acculturation and its links with health and health-behaviors has been described a number of times [START_REF] Clark | Acculturation[END_REF][START_REF] Jusot | Inégalités de santé liées à l'immigration en France. Effets des conditions de vie ou sélection à la migration ?[END_REF]. Two studies that examined the link between acculturation and HIV testing uptake found that a high degree of acculturation (in relation to the culture of origin) was associated with a greater likelihood of being tested [START_REF] Do | HIV testing patterns and unrecognized HIV infection among young Asian and Pacific Islander men who have sex with men in San Francisco[END_REF][START_REF] Kinsler | The impact of acculturation on utilization of HIV prevention services and access to care among an at-risk Hispanic population[END_REF]. This observation is consistent with our results concerning men, as the proportion of individuals tested increased with the amount of time lived in France and with the fact of not having difficulty reading/writing French.

Finally, as we mentioned in the methods section, using the nationality at the time of the survey may have introduced some classification biases in term of migration origin. Indeed, some French people may be immigrants who acquired the French citizenship (in 2004, 9.6% of the adult population in France are foreign-born abroad and 41% of them has then get the French citizenship) and, inversely, some French-born people may have been born and lived abroad before migration in France [START_REF] Borrel | Enquêtes annuelles de recensement : premiers résultats de la collecte 2004 -Principales caractéristiques de la population et des logements[END_REF]. Such biases lead to an underestimation of differences between migration groups, especially among migrant women because they are more numerous to get French citizenship than migrant men [START_REF] Fougère | L'acquisition de la nationalité française : quels effets sur l'accès à l'emploi des immigrés[END_REF].

Our study tends to show good testing uptake in people of sub [START_REF] Invs | Situation du VIH/sida en France: Données du 30 juin 2007 Retrieved 2010-03-11[END_REF]. Concurrently, these data suggest that the French policies -which have focused on high risk groups (Sub-Saharan migrants as mentioned above, but also men who have sex with men and intravenous drug users) -might have missed opportunities to raise the awareness of French heterosexuals and other lower-risk groups. As a result, when infected with HIV, these populations are then at higher risk of being tested late [START_REF] Delpierre | High-Risk groups for late diagnosis of HIV infection: a need for rethinking testing policy in the general population[END_REF].

France has recently adopted a new national strategy for the prevention and control of Aids for the years 2010-2014 (Ministère de la Santé, 2010). It recommends the universal screening of the general population with specific targets to the most vulnerable populations, which are not only the ones at higher risk of infection, but also those who may stay away from the existing screening services. It would be meaningful to repeat our analysis in the future in order to evaluate the consequences of this new screening policy.

F

  Time since the last HIV test and migration origin in theParis metropolitan area, France.

  CD4 count is ≤350/µL increases the risk of AIDS or death by 28%

  , the purpose of this study was to compare the amount of time since the last HIV test according to the migration origin of the residents of Paris metropolitan area

  into large geographic groups: France, Sub-Saharan Africa, Maghreb (Northwest Africa), and others.

  men with a coefficient of -1.88(-3.68,-0.07).

Table 2

 2 Among men, the shortest mean times were observed among those aged 18-29 years, those who were occupationally inactive, those who had not been in a steady relationship, those who did not have a child born after 1990, those of Maghreb nationality (2.28 years [1.03-3.53]), those who had lived in France for less than five years (1.80 years [0.00-3.97]), and those who indicated that they had difficulty reading and/or writing). No significant difference in the mean time since the last test was observed based on belonging or not to an ethnic or religious community.

	presents, for the individuals for whom a duration was available (n=1642), the
	mean time (in years) since the last HIV test by gender, and the univariate ANOVA analyses

for each category of variables. We did not observe any differences in mean time since the last HIV test between men and women.

Table 1 : Proportion of people tested by sex (weighted data). Table 2: Mean time since the last HIV test (in years) and univariate ANOVA analysis by sex.Table 3 : Factors associated with the duration since last HIV testing (in years) among men as determined by multilevel linear regression and multivariate anova analysis, taken into account the time lived in France and the difficulties mastering French (model 2) or not (model 1).

 13

	o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

Table 4 : Factors associated with the duration since last HIV testing (in years) among women as determined by multilevel linear regression and multivariate anova analysis, taken into account the time lived in France and the difficulties mastering French 2) or not (model 1).

 4

	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

Table 1 : Proportion of people tested by sex (weighted data).

 1

	People tested			Men				Women
		n	%	95% CI	p	n	%	95% CI	P
	Total (n=1673)	730 51.32 [47.15,55.48]		943 58.94 [54.94,62.82]

Table 2 : Mean time since the last HIV test (in years) and univariate ANOVA analysis by sex.

 2

		Men (n=584)			Women (n=1058)
			ANOVA			ANOVA
			(univariate)		(univariate)
		Mean			Prob.	Mean			Prob.
		(years) 95% CI	F	df	>F	(years) 95% CI	F	df	>F
	Total (n=1642)	4.59

Table 3 : Factors associated with the duration since last HIV testing (in years) among men as determined by multilevel linear regression and multivariate anova analysis, taken into account the time lived in France and the difficulties mastering French (model 2) or not (model 1).

 3

	MEN	Model 1			Model 2
			Mean			Mean
		coef.(95CI)	Square	F	p coef.(95CI)	Square	F	p
	Model		88.62 4.46 <0.01	74.43 3.75 <0.01
	Age
	18-29 years	Ref.	126.04 6.34 <0.01 Ref.	116.05 5.84 <0.01
	30-44 years	2.10(0.88,3.33)**			2.07(0.84,3.30)**
	45-59 years	2.48(1.24,3.72)**			2.35(1.10,3.60)**
	60 and over	2.75(1.30,4.19)**			2.69(1.23,4.14)**
	Number of steady relationships
	0	Ref.	5.93 0.30 0.83	5.47 0.28 0.84
	1	0.35(-0.70,1.40)			0.35(-0.70,1.40)
	2	-0.06(-1.29,1.18)			-0.05(-1.28,1.19)
	3 or more	0.08(-1.35,1.50)			0.16(-1.27,1.60)
	Birth after 1990
	No	Ref.	169.49 8.52 <0.01	191.24 9.62 <0.01
	Yes	1.30(0.43,2.18)**			1.39(0.51,2.27)**
	Socio-occupational categories
	Never employed	Ref.	22.39 1.13 0.35	20.19 1.02 0.41
	Worker	0.27(-1.72-2.26)			0.31(-1.72,2.33)
	Employee	-0.64(-2.69-1.41)			-0.64(-2.70,1.43)
	Intermediary position	0.22(-1.78-2.23)			0.14(-1.88,2.17)
	Executive/management 0.66(-1.29-2.62)			0.6(-1.37,2.58)
	Craftsmen/shopkeepers 1.01(-1.41-3.44)			0.91(-1.53,3.34)
	Nationality
	French		91.24 4.59 <0.01	40.18 2.02 0.11
	Sub-Saharan African	-2.48(-4.15,-0.82)**			-1.88(-3.68,-0.07)*
	Northwest African	-2.13(-3.93,-0.33)*			-1.66(-3.54,0.22)
	Other	-1.15(-2.73,0.44)			-0.57(-2.29,1.14)
	Time lived in France
	0-4 years					21.64 1.09 0.35
	5-9 years				-0.87(-4.13,2.40)
	10-14 years				-0.89(-3.85,2.07)
	15 or more years				0.55(-1.97,3.06)
	Difficulty reading/writing French
	Yes					16.91 0.85 0.36
	No				-0.66(-2.05,0.74)
	Residual		19.88			19.87
	Total		21.65			21.65
	* p<0.05, ** p<0.01

http://mc.manuscriptcentral.com/ac-phm-vcy Health Sciences

ACKNOWLEDGMENT

The SIRS cohort study has been supported by the Institute for Public Health Research (IRESP), the Directorate-General of Health (DGS), the Interministerial Delegation for Urban Affairs (DIV), the European Social Fund, the Regional Council of Ile-de-France and the City of Paris. This study was part of a research project supported by a grant from the French National Agency for Research on Aids (ANRS).


Souad Bezzaoucha

Benoît Marx

Didier Maquin

José Ragot

Linear Feedback Control Input under Actuator Saturation: a Takagi-Sugeno Approach

Keywords: Takagi-Sugeno models, actuator saturation, linear matrix inequality

In this paper, the Takagi-Sugeno representation is used to represent the nonlinear behaviour of a saturated actuator. The control design is based on a state feedback controller function of the saturation levels. Stabilization conditions in the sense of Lyapunov method are derived and expressed as a linear matrix inequality problem. An academic example is presented with a comparaison between the proposed approach and a conventional anti-windup controller.

I. INTRODUCTION

Actuator saturation or control input saturation is probably the most usual nonlinearity encountered in control engineering because of the physical impossibility of applying unlimited control signals and/or safety constraints. Classical examples of such limits are the deflection limits in aircraft actuators, the voltage limits in electrical actuators and the limits on flow volume or rate in hydraulic actuators [START_REF] Tarbouriech | Stability and Stabilization of Linear Systems with Saturating Actuators[END_REF]. Motivated by these practical issues, many approaches have been developed to deal with actuator saturations in the existing literature (see, for example, [START_REF] Kapila | Actuator Saturation Control[END_REF], [START_REF] Ma | Performance analysis for linear discretetime systems subject to actuator saturation[END_REF], [START_REF] Zaccarian | A common framework for anti-windup, bumpless transfer and reliable design[END_REF], [START_REF] Kapoor | An anti-windup design for linear systems with input saturation[END_REF] and the references therein). In general, there are three main design strategies to deal with actuator saturation for linear plants. First, by taking into account the effect of saturation throughout the design procedure, a controller that may be linear or nonlinear is constructed such that the stability of the closed loop system is guaranteed and a certain performance is achieved. In ( [START_REF] Anderson | Linear Optimal Control[END_REF], an optimal control approach with bounded control leads to a bang-bang type controller that is rarelly used in application due to implementation difficulty of the resulting switching surfaces. A more practical solution is developed in [START_REF] Tyan | Anti-windup compensators synthesis for systems with saturation actuator[END_REF] where a linear and non-linear output feedback dynamic compensators are synthesized. It is applicable to unstable but controllable and observable systems. The second strategy is model predictive control (MPC), also known as receding or moving horizon control, which has been a popular control design for discrete time systems recently both in theory and application [START_REF] Syaichu-Rohman | Optimisation Based Feedback Control of Input Constrained Linear Systems[END_REF]. In MPC, an optimisation -often a quadratic programming (QP)-is performed at every time instant k by considering both current and future actuator constraints over a certain horizon of length N. The third strategy is a two-step approach in which a nominal linear controller is first constructed by ignoring actuator

The authors are with Centre de Recherche en Automatique de Nancy (CRAN), Université de Lorraine, CNRS, 2 avenue de la Forêt de Haye F-54516 Vandoeuvre-les-Nancy, France. firstname.name@univ-lorraine.fr saturation. Once this controller has been designed, usually by using standard linear design tools (it may be noticed that some anti-windup schemes are designed for a state feedback nominal controller (e.g. [START_REF] Zaccarian | A common framework for anti-windup, bumpless transfer and reliable design[END_REF]) and some others are for an output feedback dynamic controller (e.g. [START_REF] Mulder | Multivariable antiwindup controller synthesis using linear matrix inequalities[END_REF], [START_REF] Grimm | Antiwindup for stable linear systems with input saturation: an LMI-based synthesis[END_REF])) a so called anti-windup compensator is designed to handle the saturation constraints [START_REF] Syaichu-Rohman | Anti-windup schemes for discrete time systems: An LMI-based design[END_REF]. A typical anti-windup scheme consists in augmenting a nominal pre-designed linear controller with a compensator based on the discrepancy between unsaturated and saturated control signals fed to the plant [START_REF] Syaichu-Rohman | Optimisation Based Feedback Control of Input Constrained Linear Systems[END_REF]. In this paper, we propose a state feedback controller such that the control gain depends on the saturation levels. The advantage of this approach is to synthetize only one controller (instead of two for the anti-windup case) such that the input saturation is straightly taken into account in the controller design process. For that, the Takagi-Sugeno (T-S) formalism is used to represent the nonlinear behaviour of the saturated actuator and a state feedback control law is synthetized. The stability conditions of the controlled system are derived from the Lyapunov theory and expressed as matrix inequality (LMI) problem. A numerical example with a comparison between conventional anti-windup controller is given to illustrate the effectiveness of the proposed method. The rest of this paper is organized as follows. Section 2 introduces the Takagi-Sugeno structure for modeling, some preliminary results, mathematical notations and a brief description of the saturation and anti-windup configuration. It is followed by the representation of the nonlinear saturation by a T-S structure in section 3. In section 4 is designed a state feedback control law depending on the saturation bounds. A numerical example and some simulation results are given to show the effectiveness of the proposed methods in section 5. Conclusions and future works are detailed in section 6.

II. PRELIMINARIES

A. Takagi-Sugeno structure for modeling

The T-S modeling allows to represent the behavior of nonlinear systems by the interpolation of a set of linear submodels. Each sub-model contributes to the global behavior of the nonlinear system through a weighting function µ i (ξ (t)) [START_REF] Tanaka | Fuzzy Control Systems Design and Analysis: A Linear Matrix Inequality Approach[END_REF]. The T-S structure is given by

   ẋ(t) = ∑ n i=1 µ i (ξ (t))(A i x(t) + B i u(t)) y(t) = ∑ n i=1 µ i (ξ (t))(C i x(t) + D i u(t)) (1)
where x(t) ∈ R n x is the system state variable, u(t) ∈ R n u is the control input and y(t) ∈ R m is the system output. ξ (t) ∈ R q is the decision variable vector assumed to be measurable (as the system output) or known (as the system input). The weighting functions µ i (ξ (t)) of the r submodels satisfy the convex sum property

   ∑ n i=1 µ i (ξ (t)) = 1 0 ≤ µ i (ξ (t)) ≤ 1, i = 1, . . . , n (2)
In the remaining of the paper, the two following lemmas are used.

Lemma 1: Consider two matrices X and Y with appropriate dimensions and G a symmetric positive definite matrix. The following property is verified

X T Y +Y T X ≤ X T GX +Y T G -1 Y
(3) Lemma 2: (Congruence) Consider two matrices X and Y , if X is positive (resp. negative) definite and if Y is a full column rank matrix, then the matrix Y XY T is positive (resp. negative) definite.

B. Mathematical notation

The following notations are used throughout the paper.

• A bloc diagonal matrix A denoted diag(A 1 , . . . , A n ) is defined as diag(A 1 , . . . , A n ) :=      A 1 0 . . . 0 0 A 2 . . . 0 . . . . . . . . . . . . 0 0 . . . A n      (4)
where A k are square matrices.

• The integer part of a number x is denoted:

int(x) := ⌊x⌋ (5)
• The smallest and largest eigenvalues of the matrix M are respectively denoted λ min (M) and λ max (M).

• The saturation function for a signal ν(t) is defined as

sat(ν(t)) :=    ν(t) if ν min ≤ ν(t) ≤ ν max ν max if ν(t) ≥ ν max ν min if ν(t) ≤ ν min ( 6
)
where ν max and ν min denote the saturation levels.

C. Anti-windup configuration

Classical anti-windup designs were mostly based on an adjustment on the controller input [START_REF] Syaichu-Rohman | Optimisation Based Feedback Control of Input Constrained Linear Systems[END_REF]. Consider the block diagrams in Figure 1 with nominal control input ν and anti-windup compensator Ψ. The conventional anti-windup controller uses the difference νν sat as an input for a large gain matrix Ψ = αI where α >> 1 is a scalar [START_REF] Malloci | Contrôle anti-windup pour systèmes à commutation[END_REF].

A. Takagi-Sugeno saturation control

The main idea of this work is to model the nonlinear actuator saturation using the Takagi-Sugeno representation (section II-A). For that, it is proposed to re-write the saturation equation ( 6) for each component of the control input vector under a particular form. Let us consider a control input vector u(t) ∈ R n u , such that

u(t) =    u 1 (t)
. . .

u n u (t)    (7)
The contol input under actuator saturation constraint is given by

u sat (t) =    u 1 sat (t) . . . u n u sat (t)    (8)
Each component of this vector is written as

u j sat (t) = 3 ∑ i=1 µ j i (u j (t)) (λ j i u j (t) + γ j i ), j = 1, . . . , n u (9) with      λ j 1 = 0 λ j 2 = 1 λ j 3 = 0 (10)      γ j 1 = u j min γ j 2 = 0 γ j 3 = u j max ( 11
)
and the activation functions

       µ 1 (u j (t)) = 1-sign(u j (t)-u j min ) 2 µ 2 (u j (t)) = sign(u j (t)-u j min )-sign(u j (t)-u j max ) 2 µ 3 (u j (t)) = 1+sign(u j (t)-u j max ) 2 (12)
Then, the control input vector u(t) ∈ R n u subject to actuator saturation is modeled by

u sat (t) =         ∑ 3 i=1 µ 1 i (u 1 (t))(λ 1 i u 1 + γ 1 i ) . . . ∑ 3 i=1 µ ℓ i (u ℓ (t))(λ ℓ i u ℓ + γ ℓ i ) . . . ∑ 3 i=1 µ n u i (u n u (t))(λ n u i u n u + γ n u i )         (13)
In order to simplify the notations, the weighting functions µ(u(t)) are now noted µ(t).

Based on the convex sum property of the weighting functions (2), equation ( 13) can be written in order to have the same activation functions for all the input vector components.

u sat (t) =            ∑ 3 i=1 µ 1 i (t)(λ 1 i u 1 + γ 1 i ) × ∏ n u k=2 ∑ 3 j=1 µ k j . . . ∑ 3 i=1 µ ℓ i (u ℓ (t))(λ ℓ i u ℓ + γ ℓ i ) × ∏ n u k=1k =ℓ ∑ 3 j=1 µ k j . . . ∑ 3 i=1 µ n u i (t)(λ n u i u n u + γ n u i ) × ∏ n u -1 k=1 ∑ 3 j=1 µ k j            (14)
For n u inputs, 3 n u submodels are obtained. Thus, it is important to note that we have an analytical expression of the actuators saturation µ sat (t) directly expressed in term of the control variable u(t). Equation ( 14) is equivalent to

u sat (t) = 3 nu ∑ i=1 µ i (t)(Λ i u(t) + Γ i ) (15)
The global weighting functions µ i (t), the matrices Λ i ∈ R n u ×n u and vectors Γ i ∈ R n u ×1 are defined as follow

               µ i (t) = ∏ n u j=1 µ j σ j i (u j (t)), Λ i = diag(λ 1 σ 1 i , . . . , λ n u σ nu i ) Γ i = vect(γ j σ j i
).

(16) where the indexes σ j i (i = 1, . . . , 3 n u and j = 1, . . . , n u ), equal to 1, 2 or 3, indicate which partition of the j th input (µ j 1 , µ j 2 or µ j 3 ) is involved in the i th submodel. The relations between the i th submodel and the σ j i indices are given by the following equation

i = 3 n u -1 σ 1 i +3 n u -2 σ 2 i +. . .+3 0 σ n u i -(3 1 +3 2 +. . .+3 n u -1 )
The σ j i are such that ((σ 1 i -1), . . . , (σ n u i -1)) corresponds to (i-1) in base 3. An illustrative example is given for two inputs (n u = 2), such that

u sat (t) =   u 1 sat (t) u 2 sat (t)   (17)
Since we have three partitions for each input µ j (t), the Takagi-Sugeno model for u sat (t) is then composed with 3 2 submodels

u sat (t) = 9 ∑ i=1 µ i (t)(Λ i u(t) + Γ i ) (18)
with the parameters µ i , Λ i and Γ i given by the following table

submodel i (σ 1 i , σ 2 i ) µ i (t) Λ i Γ i 1 (1, 1) µ 1 1 µ 2 1 diag(λ 1 1 , λ 2 1 )    γ 1 1 γ 2 1    2 (1, 2) µ 1 1 µ 2 2 diag(λ 1 1 , λ 2 2 )    γ 1 1 γ 2 2    3 (1, 3) µ 1 1 µ 2 3 diag(λ 1 1 , λ 2 3 )    γ 1 1 γ 2 3    4 (2, 1) µ 1 2 µ 2 1 diag(λ 1 2 , λ 2 1 )    γ 1 2 γ 2 1    5 (2, 2) µ 1 2 µ 2 2 diag(λ 1 2 , λ 2 2 )    γ 1 2 γ 2 2    6 (2, 3) µ 1 2 µ 2 3 diag(λ 1 2 , λ 2 3 )    γ 1 2 γ 2 3    7 (3, 1) µ 1 3 µ 2 1 diag(λ 1 3 , λ 2 1 )    γ 1 3 γ 2 1    8 (3, 2) µ 1 3 µ 2 2 diag(λ 1 3 , λ 2 2 )    γ 1 3 γ 2 2    9 (3, 3) µ 1 3 µ 2 3 diag(λ 1 3 , λ 2 3 )    γ 1 3 γ 2 3   

B. Problem statement

Let us now consider a linear system represented by the following state equation

ẋ(t) = Ax(t) + Bu(t) (19)
The control input u(t) is subject to actuator saturation, then the system described by (19) becomes

ẋ(t) = Ax(t) + Bu sat (t) (20)
From (15), equation (20) can be written as

ẋ(t) = 3 nu ∑ i=1 µ i (t)(Ax(t) + B(Λ i u(t) + Γ i )) (21)

IV. SATURATED STATE FEEDBACK CONTROL INPUT

The objective is to design a stabilizing static state feedback control ensuring the stability of the system, even in the presence of control input saturation. The solution is obtained by representing the saturation as a T-S system and by solving an optimization problem under LMI constraints. Let us consider a linear feedback control input given by ( 22)

u(t) = -Kx(t) (22)
Our objective is to design the state feedback controller (22) to guarantee the stability of the system (21) such that the control gain K takes into account the saturation limits.

Replacing the control law (22) in the T-S system equation, the obtained system is the following

ẋ(t) = 3 nu ∑ i=1 µ i (t)((A -BΛ i K)x(t) + BΓ i ) (23)
The computation of the static feedback K is detailed in the next theorem. Theorem 1: There exists a static state feedback controller (22) for a saturated input system (21) such that the system state converges toward an origin-centred ball of radius bounded by β if there exists matrices P 1 = P T 1 > 0, R, Σ = Σ T > 0 solutions of the following optimization problem min

P 1 ,R,Σ,β β (24) s.t. Q i I I -β I < 0, i = 1, . . . , 3 n u ( 25
)
with

Q i = P 1 A T + AP 1 -R T Λ T i B T -BΛ i R I I -Σ (26)
and

Γ i B T ΣBΓ i < β (27)
for i = 1, . . . , 3 n u . The gain of the controller is given by

K = RP -1 1 (28) Proof:
Let us define the following quadratic Lyapunov function

V (x(t)) = x T (t)Px(t) (29)
where P ∈ R n×n is a symmetric positive definite matrix. According to equations ( 23) and ( 29), the time derivative of V (t) is given by

V (x(t)) = 3 nu ∑ i=1 µ i (t)(x T (t)((A -BΛ i K) T P + P(A -BΛ i K))x(t) + Γ T i B T Px(t) + x T (t)PBΓ i ) (30) Using Lemma 1, it follows that Γ T i B T Px(t) + x T (t)PBΓ i ≤ Γ T i B T ΣBΓ i + x T (t)PΣ -1 Px(t)
(31) and thus, the time derivative of the Lyapunov function (30) is bounded as follows

V (x(t)) ≤ 3 nu ∑ i=1 µ i (t)(x T (t)((A -BΛ i K) T P + P(A -BΛ i K) + PΣ -1 P)x(t) + Γ T i B T ΣBΓ i ) (32)
Let us define

Q i = (A -BΛ i K) T P + P(A -BΛ i K) + PΣ -1 P (33) ε = min i=1:3 nu λ min (-Q i ) (34) δ = max i=1:3 nu Γ T i B T ΣBΓ i (35)
Since Σ > 0 and from equation (32), according to Lyapunov stability theory [START_REF] Zhang | A new approach to observer-based fault-tolerant controller design for Takagi-Sugeno fuzzy systems with state delay[END_REF],

V (t) < -ε x 2 +δ . It follows that V (t) < 0 for    Q i < 0 and x 2 > δ ε (36)
Which means that x(t) is uniformly bounded and converges to a small origin-centred ball of radius δ ε . Since Q i < 0 is expressed by

(A T -K T Λ T i B T )P + P(A -BΛ i K) + PΣ -1 P < 0 (37)
Applying Lemma 2, the inequality (37) becomes

P -1 A T + AP -1 -P -1 K T Λ T i B T -BΛ i KP -1 + Σ -1 < 0 (38)
Using the changes of variables

P 1 = P -1 R = KP 1 (39)
condition ( 38) is linearized as

P 1 A T + AP 1 -R T Λ T i B T -BΛ i R + Σ -1 < 0 (40)
Applying Schur's complement to equation (40), we finally find the stabilization condition Q i < 0.

P 1 A T + AP 1 -R T Λ T i B T -BΛ i R I I -Σ < 0 (41)
As the weighting functions satisfy (2) and Σ > 0, if (41) is satisfied for i = 1, . . . , 3 n u and x 2 > δ ε , then V (x(t)) < 0, which implies that x(t) converges to an origin centred ball of radius δ ε .

The objective is now to minimize the radius δ ε . Firstly δ is bounded by δ < β from the definition (35) and the LMIs (27). Secondly 1/ε is bounded by β or equivalently ε > 1/β . From the definition (34) it is equivalent to

-Q i > (1/β ) I, i = 1, . . . , 3 n u (42) Applying Schur's complement, (42) is equivalent to (25).
Finally, the radius is bounded by β .

V. NUMERICAL EXAMPLE

The proposed static state feedback controller design for systems with saturated control input is illustrated by an academic example. Let consider the linear system (19) defined by

A =   -2 0.1 0 0 -0.5 0 0.2 0.1 -3   , B =   0.1 1 0.5 1 0.8 0.6   (43) with two control inputs u = u 1 u 2
. The inputs are subject to the following actuator saturations.

       u 1max = 1 u 1min = -1 u 2max = 1.5 u 2min = -1.5 (44)
In order to illustrate the effectiveness of the proposed approach, three different control laws are synthesized for the same system. A so-called nominal controller is computed by a conventional pole placement, without taking into account the input saturation, although the saturation acts on the controller. Then in the first part of this section, a comparison is provided between the nominal closed loop system without saturation, the nominal closed loop system with saturated actuators and the closed loop system with the controller proposed in this paper where the saturation bounds are taken into account in the controller design. In a second case, a conventional anti-windup controller is synthetized (as shown in section II). The obtained performances of this controller and of the proposed T-S control are compared.

A. Comparison with nominal control

Let us consider the nominal controller K n such that the gain does not take into consideration the actuator saturations. For the considered example, with a convergence to an origin-centred ball of radius r = 3.04.

K n = 0.
The following figures (2 and 3) depict the system states and control of the nominal closed loop system without saturation (respectively denoted x 1 , x 2 ,x 3 , u 1 and u 2 ), those of the nominal closed loop system with saturation (respectively denoted x 1sat , x 2sat , x 3sat , u 1sat and u 2sat ) and those of the proposed approach (respectively denoted x 1T S , x 2T S , x 3T S , u 1T S and u 2T S ).

B. Comparison with anti-windup controller

In this subsection, a second simulation is performed in order to compare a conventional anti-windup controller with the proposed one. For the conventional anti-windup, the main idea is to synthetize a nominal feedback control and to add a compensator to handle the saturated input. The anti-windup compensator is taken as a large gain matrix Ξ = αI with α = 50. Figures 4 represents the system states for the two controllers, where x 1T S , x 2T S and x 3T S correspond to the proposed approach whereas x 1AW , x 2AW and x 3AW correspond to the anti-windup controller.

C. Comments

In the present work, a new representation of the actuator saturation problem was introduced. Thus, it is important to note as first that with the proposed approach, the actuator saturation is directly expressed in terms of the control variable and the saturation limits. The proposed approach allows us to describe and study a nonlinear behavior using linear tools. As an illustrative example, a linear feedback controller was applied to an academic system. Three cases were presented: nominal controller, T-S controller and anti-windup controller. For the nominal case, the control gain is computed without considering the saturation limits. For the anti-windup case, the control input is adjusted using the difference (u satu), but the controller gain is computed without taking into account the saturation on the input control.. On the other hand, for the proposed approach the control gain is computed depending on the saturation limits by solving the LMIs given in theorem 1. The obtained results illustrates the effectiveness of the proposed approach for the studied example.

VI. CONCLUSIONS AND FUTURE WORKS

Considering the saturation nonlinearity, a linear system can be represented in a T-S form. The main advantage of the proposed approach is to synthetize the control by taking into consideration the saturation limits, since they are added in the new system representation. Then, the stabilizing state feedback gain can be computed by solving an optimization problem under LMI constraint, as usually done in the T-S framework. A numerical example was presented in order to illustrate the proposed approach with a comparaison with a conventional anti-windup controller. It was shown that the obtained results are slightly better for the T-S saturated controller. As future works, the proposed approach may be generalized to nonlinear systems represented by a T-S model with measurable and unmeasurable decision variable. It is also noted that the saturation may also affect not only the actuators, but also the sensors, this is why our approach may also be applied to sensors saturations.

Fig. 1 .

 1 Fig. 1. Conventional anti-windup controller

Fig. 2 .Fig. 3 .Fig. 4 .

 234 Fig. 2. System states for nominal, nominal saturated and T-S saturated controllers


Hervé Yviquel

Emmanuel Casseau

Matthieu Wipliez

Mickaël Raulet

EFFICIENT MULTICORE SCHEDULING OF DATAFLOW PROCESS NETWORKS

Keywords: Dataflow computing, Multicore processing, Scheduling algorithm, Distributed algorithm, Lock-free multithreading

Although multi-core processors are now available everywhere, few applications are able to truly exploit their multiprocessing capabilities. Dataflow programming attempts to solve this problem by expressing explicit parallelism within an application. In this paper, we describe two scheduling strategies for executing a dataflow program on a single-core processor. We also describe an extension of these strategies on multi-core architectures using distributed schedulers and lock-free communications. We show the efficiency of these scheduling strategies on MPEG-4 Simple Profile and MPEG-4 Advanced Video Coding decoders.

INTRODUCTION

Since processor frequency is bounded due to physics constraints like power dissipation, multi-core architectures have become the solution to allow performance to keep growing as described by Moore's law. These architectures present an interesting challenge: produce applications which fully exploit the parallelism provided by these processors. Several programming languages, extensions and models allow parallelism to be expressed in applications like Occam [START_REF] May | OCCAM[END_REF], Message Passing Interface [START_REF] Pacheco | Parallel programming with MPI[END_REF] or Algorithmic Skeletons [START_REF] Cole | Algorithmic skeletons: structured management of parallel computation[END_REF]. Most of them assume a specific underlying hardware architecture and are generally inefficient on other platforms.

Dataflow programming is an attractive candidate to design parallel applications in an architecture-agnostic way. A dataflow program is composed of atomic processing blocks that communicate with each other with communication channels. Such a representation explicitly describes task-level parallelism within the application. The behavior of this kind of program is governed by a Model of Computation (MoC) which specifies a set of rules regarding the execution of the program. Several dataflow MoCs exist with different purposes and expressivenesses such as Synchronous Dataflow (SDF), Kahn Process Network (KPN) [START_REF] Kahn | The Semantics of a Simple Language for Parallel Programming[END_REF] and Dataflow Process Network (DPN) [START_REF] Lee | Dataflow Process Networks[END_REF].

Dynamic dataflow models like KPN and DPN are very useful to describe the behavior of streaming applications. Contrary to SDF and similar models that consume and produce data in a static way, KPN and DPN models may have a data-dependent behavior i.e. the quantity of data consumed and produced by the processes may depend on the value of these data.

This paper proposes several scheduling techniques to efficiently execute dynamic dataflow programs on single-core and multi-core processors. Indeed, determining a schedule of a dynamic dataflow program is not possible at compile-time (equivalent to the halting problem, see [START_REF] Buck | Scheduling dynamic dataflow graphs with bounded memory using the token flow model[END_REF]). This paper makes the following contributions:

• We give a formal definition of a round-robin policy for scheduling dataflow process networks on single-core architectures that has been successfully used in practice, see [START_REF] Amer | Reconfigurable video coding on multicore[END_REF] and [START_REF] Von Platen | Project report: CAL ARM Compiler[END_REF] (Section 3.1).

• We present an efficient strategy to dynamically schedule actors of dataflow process networks on single-core architectures (Section 3.2). A clever scheduling strategy is key to ensure that a complex application with many processing blocks can be executed efficiently.

• We propose a distributed and lock-free extension of these two dynamic scheduling strategies on multi-core architecture (Section 4) based on Lamport's work [START_REF] Lamport | Specifying Concurrent Program Modules[END_REF] concerning lock-free communication channels of distributed processes.

This paper presents results obtained with our scheduling strategies for the execution of two video decoders (MPEG-4 Simple Profile and MPEG-4 Advanced Video Coding) on a multi-core processor.

BACKGROUND

This section presents the dynamic dataflow model called dataflow process network and how applications described by this model are scheduled.

Dataflow Process Networks

A Dataflow Process Network (DPN) is a model of computation [START_REF] Lee | Dataflow Process Networks[END_REF] which can be described as follow: a set of processes called actors that communicate with unidirectional and unbounded FIFO channels called data-fifos and connected to ports of actors. A data-fifo has only one source port but may have several target ports. In the dataflow approach, the communication between actors corresponds to a stream of data composed of a list of tokens. Figure 1 presents a network of five actors linked by data-fifos. DPNs can be considered as a generalization of the wellknown Kahn Process Networks (KPNs) [START_REF] Kahn | The Semantics of a Simple Language for Parallel Programming[END_REF]. The execution of an actor corresponds to the mapping of input tokens to output tokens applied repeatedly and sequentially on one or more data streams. This mapping is composed of three ordered steps: data reading, then computational procedure, and finally data writing. These repeated mappings are called actor firings and are guarded by a set of firing rules which specifies when an actor can be fired. These firing rules specifies precisely the number and the values of tokens that must be available on the input ports to fire the actor. This is why DPNs can describe nondeterministic algorithms which is not possible with the KPN model.

Scheduling of Dataflow Process Networks

DPNs are more suitable than KPNs to be scheduled on processors when there are more processes than processor cores because no context has to be saved between each actor execution. Indeed, the execution of an actor is described by a sequence of actor firings and actor switching can only happen between two firings, so only state variables need to be saved; in particular, it is not necessary to save the execution stack and other contextual information like registers, etc.

Consequently, it is possible to reduce the overhead of scheduling a dynamic dataflow program by using a user-level scheduler rather than relying on threads scheduled by the operating system kernel. Von Platen shows an impressive acceleration of 3.4 to 105 frame per second (FPS) with a video decoder after using a user-level scheduler that uses a single thread to schedule actors in [START_REF] Von Platen | Project report: CAL ARM Compiler[END_REF]. Scheduling an actor with this method is a lot more efficient than using threads because there is no need for the kernel to perform a context switch each time an actor is scheduled but only a function call.

The data-fifos used throughout this paper are statically bounded to be implemented on finite memory and avoiding additional overhead due to dynamic memory allocation.

SINGLE-CORE SCHEDULING STRATEGIES

A dynamic dataflow program cannot be fully scheduled by static methods so some dedicated strategies need to be developed in order to schedule actors during the execution. The following strategies are designed to execute a DPN-based application on a single-core architecture which handles the execution of only one actor at a given time.

Round-robin scheduling strategy

Round-robin is a simple scheduling strategy that continuously goes over the list of actors: The scheduler evaluates the firing rules of each actor, executes the actor if a rule is met and continues to execute the same actor until no firing rules are met. This scheduling policy guarantees to each actor an equal chance of being executed, and avoids deadlock and starvation. Contrary to classical round-robin scheduling, there is no notion of time slice: an actor is executed until it cannot fire anymore in order to minimize the number of actor switching and consequently the scheduling overhead. The reason of this unfireability is that data-fifos will be finally full or empty because of their bounded sizes.

Blocking A1 A2 A3 A4 A5 B lo c k in g B lo c k in g Bl oc ki ng Bl oc ki ng

Fig. 2: Example of round-robin scheduling with five actors

Figure 2 shows an application of this round-robin scheduling on the example presented in Fig. 1. The scheduler executes the actors in a circular order i.e. the five actors A1, A2, A3, A4 and A5 are successively executed then the scheduler starts again from A1 and so on.

Data-driven / demand-driven scheduling strategy

Data-driven / demand-driven strategy is a more advanced scheduling strategy of dynamic dataflow programs. Indeed, the round-robin strategy schedules actors unconditionally i.e. the firing rules of an actor could be checked even if they are all invalid. The firing rules of the actor will be checked, but no computation will be performed. As a result, the roundrobin strategy becomes inefficient with complex applications containing many actors and a lot of control communications.

Data-driven / demand-driven scheduling strategy is based on the well-known data driven and demand driven principles [START_REF] Parks | Bounded Scheduling of Process Networks[END_REF]. On the one hand, data-driven policy executes an actor when its input data have to be consumed to unblock the execution of the precedent actor. On the other hand, demand-driven executes an actor when its output is needed by another actor.

Two types of events can cause the blocking of an actor execution, each one is implying a different scheduling decision:

• When an actor is blocked because an input data-fifo is empty, demand-driven policy is applied and the scheduler executes the predecessor of this data-fifo.

• When an actor is blocked because an output data-fifo is full, data-driven policy is applied and the scheduler executes the successors of this data-fifo. Indeed a datafifo can be connected to several target ports (see Section 2.1).

Contrary to the round-robin algorithm, a dynamic list of next schedulable actors is needed. The behavior of this schedulable list is illustrated with Fig. 3. When an actor is blocked during its execution, the empty or full data-fifos are identified and their associate predecessors or successors are added to the schedulable list. The actor to be executed next corresponds to the next entry in the schedulable list.

Waiting list of schedulable actors

Predecessors or Successors

Next schedulable actor

Current executed actor

Fig. 3: Example of data-driven / demand-driven scheduling

DISTRIBUTED AND LOCK-FREE MULTI-CORE SCHEDULING

This section describes a distributed and lock-free multi-core scheduling technique to execute dynamic dataflow programs using round-robin and data-driven / demand-driven strategies.

Distributed scheduler

A distributed scheduler is designed to execute applications on a multi-core architecture. Several local schedulers are executed concurrently on each processor core. This specific design avoids the use of a specific thread to manage the scheduling of the application.

A static partitioning of the actors on the processor cores is needed to run our multi-core scheduler. On the one hand, the round-robin strategy goes over a static list of actors so its multi-core extension needs this static mapping of the actors on the cores to be implemented. On the other hand, the datadriven / demand-driven strategy could work with a mapping computed dynamically, but (1) a static mapping allowed us to develop the multi-core extension by tackling each problem one at a time, and ( 2) is considered as future work. Figure 4 presents a possible mapping of five actors on a dual-core processor. To form the distributed scheduler, one thread for each available processor core is created and forced to be run only on its associated core. The round-robin algorithm executes a subset of the actors that are mapped on the associated core in each thread. Figure 5 shows an example of the distributed scheduler with the round-robin strategy. The multi-core version of the data-driven / demand-driven strategy is realized in the same way as the round-robin strategy. The difference is that with our static mapping, the predecessors and successors of a given actor can possibly be mapped to a different core than the one of this actor. This requires communications between the different threads to schedule all the actors. Figure 4 illustrates this: If A1 is blocked during its execution because the data-fifo called f2 is full then the scheduler has to add A3 to the list of schedulable actors. However A3 is managed by another scheduler so an inter-scheduler communication is needed.

In a multi-core context, we use a combined version of the round-robin and data-driven / demand-driven strategies to avoid starvation of our distributed algorithm. Indeed, contrary to the single-core version, data-driven / demand-driven strategy cannot guarantee all the time that each local schedulable list is not empty. The scheduler applies the data-driven / demand-driven policy until its schedulable list is empty and then the round-robin policy is used until the schedulable list contains at least one actor. The algorithm is presented in Fig. 6.

CombinedScheduling

Lock-free inter-core communications

Lock-free communications between distributed schedulers are used to avoid the synchronization of threads. Indeed, the fine granularity of the actors makes actor scheduler a critical part of the execution so the smallest overhead can have disastrous consequences on the performance. Moreover informing a remote scheduler to add a schedulable actor to its schedulable list is essential otherwise a deadlock could occur during the execution. In fact, if this scheduling information is not communicated, a self-contained cycle can appear and cause a deadlock of the application. For example in Fig. 4, if the data-fifos f4-7 are full, the actors A3, A4 and A5 form a self-contained cycle that never stops until A2 consumes the tokens contained in f4 but this could never happen if the other scheduler loops on a self-contained cycle, too.

Another kind of FIFO channels called scheduling-fifos is used to communicate between schedulers without synchronization. Lamport proved that locks are not necessary in the case of single producer, single consumer FIFOs [START_REF] Lamport | Specifying Concurrent Program Modules[END_REF]. However it is important not to confuse the two types of FIFOs which work with the same mechanism but have two distinct uses: the data-fifo channels used to carry on the application stream and the scheduling-fifo channels used to share scheduling informations (in our case a set of next schedulable actors). Figure 7 shows the inter-core communications mechanism. When an actor execution is blocked, the scheduler adds the predecessor or the successors of the blocking data-fifo to its schedulable list. In some cases this actor is not executed by the current scheduler so this actor is sent to its associated scheduler by a scheduling-fifo channel.

We propose two kinds of communication network topology (Fig. 8): mesh and ring. The mesh topology uses a bidirectional communication channel between each couple of actors. The distributed schedulers communicate directly but the number of scheduling-fifos increases exponentially with the number of cores. The ring topology offers the possibility to use the distributed scheduler with a limited number of scheduling-fifos: on a N-core processors N scheduling-fifos are needed. However the communication could cross N-2 schedulers in the worst case before the targeted scheduler receives it. For example (see Fig. 8(b)), if the scheduler on core 1 wants to communicate with the other one mapped on core 4, the schedulers on cores 2 and 3 are used as intermediaries.

RESULTS

In this section, we present several experimental results to demonstrate the efficiency of our multi-core scheduler on real-world video applications. We also compare our approach with another runtime included in the OpenDF framework on the same applications [START_REF] Von Platen | Project report: CAL ARM Compiler[END_REF] [START_REF] Bhattacharyya | OpenDF: a dataflow toolset for reconfigurable hardware and multicore systems[END_REF].

Benchmarks

The Reconfigurable Video Coding (RVC) framework was created by MPEG to increase the reusability and portability of the code in video decoders [START_REF] Amer | Reconfigurable video coding on multicore[END_REF]. The description language of RVC, called RVC-CAL and based on the Dataflow Process Networks model, was used to implement the applications used in our experiments.

We have implemented the round-robin and combined strategies in the C runtime library of the Open RVC-CAL Compiler (Orcc) 1 . These two scheduling strategies have been tested on dataflow descriptions of MPEG-4 Simple Profile and MPEG-4 Advanced Video Coding with different sized video sequences. We benchmarked these decoders on a Intel Xeon with four cores at 2.33GHz. During all the experiments, the data-fifos are bounded to 4096 elements and the scheduling-fifos to 200 elements.

The testing video sequences are: For MPEG-4 SP, hit001 (CIF) from ISO/IEC 14496-4:2004 and old_town_cross (720p) encoded at 6Mbps with the Xvid encoder from an YUV file available on [START_REF]YUV Sequences[END_REF] and for MPEG-4 AVC LS_SVA_D (QCIF) and HCBP2_HHI_A (CIF) available on [START_REF]H264 Sequences[END_REF].

The results for various configurations are presented in Table 1 for the MPEG-4 SP decoder and in Table 2 for the MPEG-4 AVC decoder. We benchmarked too the MPEG-4 SP decoder on the 720 sequence using the other runtime library included in OpenDF framework: We obtain 10.1 fps on one core and 15.6 fps on two cores i.e. the speedup is about 1.54.

Strategy

Core CIF 720p Speedup

Mapping validation using genetic algorithm

A genetic algorithm was developed to find efficient static mapping of actors on the processor cores and used during these experiments. Most of the time, dynamic dataflow programs can be easily partitioned on dual-core processor with manual methods thanks to the explicit parallelism of dataflow representations. However this is increasingly complex to do when the number of cores and actors grows. For example, the dataflow description of MPEG-4 SP is composed of 42 actors and MPEG-4 AVC one is composed of 131 actors. More than one thousand possible mappings of a dataflow program into a multi-core processor is quickly reached.

Discussion

The data-driven / demand-driven strategy shows its efficiency with the MPEG-4 AVC decoder which contains many actors and many control flows. Moreover the data-driven / demanddriven strategy, and consequently the combined strategy, is slightly more efficient than the round-robin strategy even on small applications like MPEG-4 SP.

Our multi-core extension of these single-core scheduling strategies is validated by the high speedups we obtained compared to the maximal theoretical speedups.

Results show that the round-robin strategy is better on MPEG-4 Simple Profile than the data-driven / demand-driven strategy on four cores. Indeed, most of the time the roundrobin executes a fireable actor because this application is described with few actors. When MPEG-4 SP is partitioned on multiple cores, more scheduling operations are required using the data-driven / demand-driven strategy, which leads to a slightly increased overhead.

Finally, the speedup obtained with the OpenDF framework is lower than the ones obtained with our two scheduling strategies with the same mapping of actors on the processor cores.

RELATED WORK

In [START_REF] Parks | Bounded Scheduling of Process Networks[END_REF] and [START_REF] Haid | Efficient Execution of Kahn Process Networks on Multi-Processor Systems Using Protothreads and Windowed FIFOs[END_REF], Parks and Haid et al. deal with implementation and scheduling of Kahn Process Networks. Contrary to Dataflow Process Networks, the context switches of process suspension and resumption cannot be avoided and it leads to an inevitable overhead. On the one hand, Haid et al. have chosen to use lightweight and stackless threads implementation to minimize this overhead. On the other hand, Parks presents a combined demand-driven and data-driven strategy. Unfortunately he gives no result we can use for comparison.

Aldinucci et al. presents a low-level programming framework based on lock-free queues dedicated to multiprocessors streaming applications in [START_REF] Aldinucci | Efficient Smith-Waterman on Multi-core with FastFlow[END_REF]. Like us, they try to use lockfree communication channels to avoid synchronization between threads. In their model, all channels with multiple writers or/and readers are built by assembling a set of single reader and single writer channels with an external thread which manages the data copies between these channels. This approach avoids cache invalidation but a lot of data transfers is needed to hide the overhead of switching between threads.

In [START_REF] Boutellier | Multiprocessor scheduling of dataflow models within the Reconfigurable Video Coding framework[END_REF], Boutellier et al. present a methodology to map and schedule actors on multiprocessors. They begin to transform the RVC-CAL network in a set of homogeneous synchronous dataflow graphs. Unfortunately these graphs cannot be generated when an actor execution depends of the input token value. Moreover, the small MPEG-4 SP decoder was their only test-case and the complexity of such static techniques increases exponentially according to the application size.

CONCLUSION

This paper proposes a new approach to efficiently schedule dynamic dataflow programs with a lock-free and distributed algorithm on multi-core architectures based on two presented single-core scheduling strategies. The results of the experiments shows that our multi-core scheduler scales up well to four cores.

In future work we will focus on stream communications between cores to improve the application speedup and we will extend our multi-core scheduling algorithm to dynamically map the actors on processor cores.

Fig. 1 :

 1 Fig. 1: An example of Dataflow Process Network

Fig. 4 :

 4 Fig. 4: Mapping example of a network on processor cores

Fig. 5 :

 5 Fig.5: Distributed multi-core scheduler using round-robin

Fig. 7 :

 7 Fig. 7: Example of data-driven / demand-driven scheduling

Fig. 8 :

 8 Fig. 8: Possible topologies of communications

Table 1 :

 1 Results of MPEG-4 SP for various configurations in frames per second

			1	144 15.6	1
	Round-robin	2	265 26.6	1.78
			4	494 51.4	3.36
			1	154 16.1	1
	Combined		2	288 27.3	1.75
	strategy	Ring	4	443 49.8	2.98
		Mesh	4	516 51.9	3.28

Table 2 :

 2 Results of MPEG-4 AVC for various configurations in frames per second

Orcc is available at http://orcc.sf.net