MD Soulef Guendouz

Stéphane Rappeneau

MD Julien Nahum

MD, PhD Jean-Luc Dubois-Randé

MD Pascal Gueret

MD, PhD Jean-Luc Monin

MD, PhD Pascal Lim

MD, PhD Serge Adnot

MD, PhD Luc Hittinger

MD, PhD Thibaud Damy
email: thibaud.damy@hmn.aphp.fr

Prognostic Significance and Normal Values of 2D Strain to Assess Right Ventricular Systolic Function in Chronic Heart Failure Short Title: RV dysfunction and prognosis in CHF

Keywords: ACE: angiotensin-converting enzyme, AR inhibitors: angiotensin receptor inhibitors brain natriuretic peptide, CHF: chronic heart failure, LV: left ventricle NYHA: New York Heart Association, RV: right ventricle

Aims: Chronic heart failure (CHF) has a poor prognosis. Our aims were to determine the normal values and prognostic significance in CHF patients of right ventricle (RV)-2D strain, a new echocardiographic parameter.

Methods and Results:

Between 2005 and 2010, we prospectively enrolled 43 controls and 118 stable CHF patients seen at our CHF clinic. All patients underwent a physical examination, laboratory tests, and echocardiography. Standard echocardiographic variables, tricuspid annular plane systolic excursion, peak systolic velocity of tricuspid annular motion using tissue Doppler imaging, and RV and left ventricle 2D-strain were measured. The primary outcome was death or emergent transplantation or emergent ventricular assist-device implantation or acute heart failure. RV-2D strain was measurable in 39 controls (58±17 years, 50% men), whose median value was -30% (95% confidence interval [95%CI], -39%;-20%); and in 104 CHF patients (80% men, mean age 57±11 years, and mean left ventricular ejection fraction 29%±8%), whose median value was -19% (95%CI, (-34%;-9%). During the mean follow-up of 3714 months, 44 patients experienced the primary outcome. By Cox proportional hazards multivariate analysis, only RV-2D strain and log-transformed brain natriuretic peptide independently predicted experiencing the primary outcome within the first year. The best RV-2D strain cut-off by ROC analysis was -21%, and patients with values >-21% were at greatest risk ( 2 -log-Rank test=14.1, p<0.0001).

Conclusion:

RV-2D strain is a strong independent predictor of severe adverse events in patients with CHF and may be superior over other systolic RV or LV echocardiographic variables.

INTRODUCTION

Chronic heart failure (CHF) is an inexorably progressive condition that is ultimately fatal in the absence of cardiac transplantation. The identification of predictors of cardiac events in patients with CHF would help to optimise treatment decisions. Given the increasing prevalence of CHF, a method capable of accurately predicting cardiac events and suitable for use in everyday clinical practice is urgently needed.

The right ventricle (RV) is pivotal in maintaining hemodynamic stability and an adequate cardiac output. Thus, recent studies point to a crucial role for RV systolic function in the course of several cardiovascular diseases. [START_REF] Haddad | Right ventricular function in cardiovascular disease, part I: Anatomy, physiology, aging, and functional assessment of the right ventricle[END_REF][START_REF] Haddad | Right ventricular function in cardiovascular disease, part II: pathophysiology, clinical importance, and management of right ventricular failure[END_REF] Over the last few years, RV systolic function has been proven in many studies to influence the prognosis of patients with CHF. [START_REF] De Groote | Right ventricular ejection fraction is an independent predictor of survival in patients with moderate heart failure[END_REF][START_REF] Ghio | Prognostic usefulness of the tricuspid annular plane systolic excursion in patients with congestive heart failure secondary to idiopathic or ischemic dilated cardiomyopathy[END_REF][START_REF] Salvo | Preserved right ventricular ejection fraction predicts exercise capacity and survival in advanced heart failure[END_REF] Imaging studies that can be used to assess RV systolic function include echocardiography, angiography, radionuclide ventriculography, and magnetic resonance imaging. [START_REF] Haddad | Right ventricular function in cardiovascular disease, part I: Anatomy, physiology, aging, and functional assessment of the right ventricle[END_REF][START_REF] Haddad | Right ventricular function in cardiovascular disease, part II: pathophysiology, clinical importance, and management of right ventricular failure[END_REF] Among these tools, echocardiography is the most readily available and the most widely used in everyday clinical practice. Consequently, the identification of a simple echocardiographic parameter that reliably predicts outcomes in CHF would be of considerable interest. In several studies, selective systolic motion or contractility of the tricuspid annulus measured by M-mode echocardiography 4,6 ,7 or tissue Doppler imaging (TDI) were found to hold prognostic significance. [START_REF] Meluzin | Pulsed Doppler tissue imaging of the velocity of tricuspid annular systolic motion; a new, rapid, and non-invasive method of evaluating right ventricular systolic function[END_REF][START_REF] Damy | Comparison of four right ventricular systolic echocardiographic parameters to predict adverse outcomes in chronic heart failure[END_REF] Recently, 2D imaging of myocardial deformation, or strain, was found useful for assessing left ventricle (LV) function. [START_REF] Nahum | Impact of longitudinal myocardial deformation on the prognosis of chronic heart failure patients[END_REF] Angle-independent 2D strain imaging is now available on echocardiography systems and has been shown to reliably reflect RV function. Whether myocardial deformation parameters derived from the RV supply additional information over standard echocardiography parameters in everyday clinical practice remains unknown. Furthermore, the normal 2D strain values for the RV have not yet been reported. [START_REF] Giusca | The right ventricle: anatomy, physiology and functional assessment[END_REF][START_REF] Jurcut | The echocardiographic assessment of the right ventricle: what to do in 2010?[END_REF] Here, our objectives were to determine the normal values of RV-2D strain in healthy controls, the prognostic significance of RV-2D strain in patients with CHF, and the best RV-2D strain cut-off for identifying high-risk patients with CHF.

METHODS

Study population

Between 2005 and 2010, we enrolled 118 patients receiving follow-up at our CHF clinics (CHU Henri Mondor, Créteil, France). Inclusion criteria were the use of appropriate medications, a clinically stable condition for at least the past month, and sinus rhythm. We also recruited, through advertising, 43 individuals free of cardiovascular disease and matching on age with the group of the patients, who served as the controls.

The study complied with the Declaration of Helsinki. The local ethics committee approved the research protocol. Informed consent was obtained from each study participant prior to inclusion.

Study assessments

The following were performed in all study participants: medical history, physical examination, blood tests (brain natriuretic peptide [BNP], creatinine, and haemoglobin), and a functional test (6-minute walk test and/or cardiopulmonary testing).

All study participants underwent an echocardiographic examination at rest. The participants were in the left lateral decubitus position. An experienced sonographer performed the examination using a Vivid 7 system (GE Vingmed, Horten, Norway). Standard parasternal views (long and short axis) and four-chamber apical views were obtained. Four-chamber apical 2D grey-scale images were recorded with a frame rate ≥50 Frames per second (fps). All data were stored digitally for off-line analysis using Echo-PAC software (V7.0.0, GE Vingmed Ultrasound). Standard RV and LV function parameters were determined as recommended by the American Society of Echocardiography, [START_REF] Lang | Recommendations for chamber quantification: a report from the American Society of Echocardiography's Guidelines and Standards Committee and the Chamber Quantification Writing Group, developed in conjunction with the European Association of Echocardiography, a branch of the European Society of Cardiology[END_REF] and for each parameter the mean of three consecutive cardiac cycles was recorded. These parameters included the transcuspid annular plane systolic excursion (TAPSE) on the M-mode apical four-chamber view, the tricuspid annular peak velocities using TDI (Sa t , Ea t , and Aa t waves), LV ejection fraction (LVEF), and LV enddiastolic diameter index to body surface area (LVEDD ind ). Early (Em) and late (Am) transmitral diastolic peak flow velocities and filling deceleration time (DT) were measured using pulsedwave Doppler imaging of the mitral valve inflow. Peak accelerations of mitral annular velocity (Sa, Ea, and Aa waves) were also measured in the lateral and septal positions using TDI.

Maximal tricuspid regurgitation velocity was determined.

RV and LV peak systolic longitudinal strain and strain rate were assessed on the apical four-chamber view using speckle tracking analysis. Patients whose RV-2D strain was not measurable were excluded from the analysis. Speckle tracking analyses motion by real-time tracking of the frame-to-frame movements of naturally occurring echo-dense speckles, using Echo-PAC software. The 2D strain and strain rate values can be derived by comparing the displacement of the speckles relative to one another throughout the cardiac cycle. For our study, the endocardial border was drawn manually and the region of interest (ROI) was generated automatically to include the entire myocardium. ROI position and width were adjusted manually when necessary. Segments with poor-quality tracking were discarded. The software automatically tracked the myocardial movements, dividing the myocardium into six segments.

QRS onset is detected from the simultaneous ECG recording to define the time point when strain equals zero. The lateral RV wall and the septal and lateral LV walls were divided into basal, middle, and apical segments for computation of regional strain and strain rate values by the software as means per segment. Global longitudinal strain and global strain rate for the entire traced ventricular contour were computed and expressed as mean±SD. The standard echocardiographic measurements, TDI, and offline 2D strain and strain rate measurements were performed by a single sonographer, who was blind to the clinical data and outcome. Interobserver reproducibility was assessed in a random sample of 30 patients.

Outcome measures

The primary end-point was the occurrence of any of the following: death, emergent cardiac transplantation, emergent implantation of a ventricular assist device, and admission for acute heart failure. In each patient, only the event that occurred first was considered for the analysis, except when acute heart failure resulted during the same hospitalisation in death or emergent surgery for cardiac transplantation or LV assist device implantation, in which case only the death or surgery was recorded. Follow-up information was obtained either from the medical chart or by interviewing the patient. Patients who underwent elective cardiac transplantation or implantation of a ventricular assist device were censored at the time of surgery.

Statistical analysis

Continuous variables were described as mean±SD, except BNP, which was described as median±SD (and logarithmically transformed for the other statistical analyses). The two-tailed unpaired Student's test was used to compare means of continuous variables and the chi-square test (or Fisher's test where appropriate) to compare categorical variables. We divided the patients with CHF into two groups based on whether they experienced the primary end-point within 1 year of study inclusion. Patients without the primary end-point who had less than 1 year of follow-up were excluded from the analysis.

We performed a time-to-event analysis using a univariate Cox proportional hazard model.

Variables for which p values in the univariate analysis were smaller than 0.05 were entered in a multivariate Cox proportional hazard model. Factors independently associated with the primary end-point were identified using backward stepwise selection. We tested three models. The first model included the significant variables measuring RV systolic function and compared the strength of their associations with the primary end-point. The second model included all significant echocardiographic variables and the third model all significant clinical, laboratory, and echocardiographic variables.

The accuracy of RV-2D strain for predicting the occurrence of the primary end-point was assessed by computing the areas under the receiver-operating characteristic (ROC) curves (ROC-AUCs). The Youden test was performed to determine the best RV-2D strain cut-off.

Finally, a Kaplan-Meier curve of event-free survival over time was constructed using the RV-2D strain cut-off. Values of p smaller than 0.05 were considered significant. Analyses were performed using SPSS 15.0 (SPSS Inc., Chicago, IL, USA).

RESULTS

Figure 1 shows the study participant flow chart. We included 161 individuals, of whom 118 had CHF and 43 were controls. RV-2D strain was measurable in 39 (91%) controls and 104 (88%) CHF patients; only these 143 participants were included in the analysis. RV-2D strain was measurable in most of the lateral wall segments (Figure 1); measurement failures were most common at the basal segment of the RV lateral wall of the controls (Figure 1).

Comparison of baseline characteristics between controls and patients

Table 1 reports the main baseline clinical, laboratory, and treatment characteristics of the controls and CHF patients in whom RV-2D strain was measurable. Table 2 shows the M-mode, transmitral Doppler, and TDI of the LV and RV. The results in the CHF patients indicated severe impairment of RV and LV systolic function and of LV diastolic function.

Table 3 reports the RV and LV 2D strain and strain rate data. For all variables, values were significantly lower in the control group than in the CHF group. Figure 2 shows the distribution of RV-2D strain values. The median RV-2D strain value was -30% (95% confidence interval [95%CI],-39%; -20%) in the controls and -19% (95%CI, -34%; -9%) in the patients with CHF. RV-2D strain correlated strongly with TAPSE and S at , two echocardiographic variables known to reflect RV systolic function (Figure 3). 2D strain and strain rate values were higher for the RV than for the LV (Table 3).

Comparison of patients with CHF who did and did not experience the primary end-point

At last follow-up, 60 patients, with a mean follow-up of 3313 months, had not experienced the primary end-point and 44 patients had experienced the primary endpoint (acute heart failure episode, n=32; and other, n=12). Of the 60 patients without the primary end-point, 5 underwent elective heart transplantation and 2 elective implantation of an LV assist device.

After 1 year, 29 CHF patients had experienced the primary outcome and 69 had not. The baseline characteristics of these 97 CHF patients are shown in Tables 1,2, and 3. The only significant clinical or treatment difference at baseline was a higher prevalence of hypertension in the subgroup with the primary outcome. This subgroup also had worse RV and LV systolic function with higher values for BNP and Em/Am and lower values for LVEF. The subgroup with the primary outcome had higher mean values for LV-2D strain of lateral segments and basal segments and for the mean of these two variables, compared to the CHF subgroup without the primary outcome. Segment-by-segment comparisons showed no significant differences between the two subgroups. The subgroup with the primary outcome within 1 year had significantly higher values for mean septal LV-2D strain rate and mean of the septal-and lateral-segment strain rates. RV-2D strain values for the three RV wall segments were significantly higher in the subgroup with the primary outcome than in the subgroup without the primary outcome after 1 year. In contrast, the two subgroups were not significantly different regarding the RV-2D strain rate values.

Prognostic significance of strain and strain rate values

Tables 4 and5 show the results of the univariate and multivariate Cox proportional hazard model analyses. RV-2D strain was a better predictor of the primary outcome compared to the other echocardiographic variables measuring RV systolic function (TAPSE and S) or LV function (LVEF and E/Ea). RV-2D strain remained significantly associated with the primary outcome when all the clinical, laboratory, and echocardiographic variables were added to the model. The best RV-2D strain cut-off for separating CHF patients with and without the primary outcome within 1 year was -21%. Interestingly, 96% of the controls and 56% of the CHF patients had RV strain values below this cut-off.

Reproducibility

Intra-observer reproducibility was 8% for RV global longitudinal strain and 10% for strain rate. Corresponding values for inter-observer reproducibility were 10% and 14%, respectively.

DISCUSSION

We showed that RV-2D strain correlated with standard echocardiographic parameters (TAPSE and peak velocity of tricuspid annular systolic motion by pulsed TDI) used to measure RV contractility. Among our controls, 96% had RV-2D strain values lower than -21%. RV-2D strain was independently associated with the occurrence within 1 year of a composite end-point (death, admission for acute heart failure, emergent cardiac transplantation, or emergent ventricular assist-device implantation). RV-2D strain values greater than -21% (-21% to 0%) were at highest risk for experiencing the primary outcome within the first year.

Echocardiographic evaluation of RV systolic function

The complex shape and marked load dependency of the RV create challenges when assessing RV function. [START_REF] Haddad | Right ventricular function in cardiovascular disease, part II: pathophysiology, clinical importance, and management of right ventricular failure[END_REF] Various echocardiographic surrogates for RV contractility have been described. [START_REF] Ghio | Prognostic usefulness of the tricuspid annular plane systolic excursion in patients with congestive heart failure secondary to idiopathic or ischemic dilated cardiomyopathy[END_REF][START_REF] Damy | Comparison of four right ventricular systolic echocardiographic parameters to predict adverse outcomes in chronic heart failure[END_REF] RV ejection fraction measurement using 2D echocardiography was the first echocardiographic method used to assess RV systolic function [START_REF] Watanabe | Estimation of right ventricular volume with two dimensional echocardiography[END_REF][START_REF] Bommer | Determination of right atrial and right ventricular size by two-dimensional echocardiography[END_REF] but required numerous geometric assumptions that diminished the accuracy of the results. Two other parameters were therefore developed, TAPSE [START_REF] Ghio | Prognostic usefulness of the tricuspid annular plane systolic excursion in patients with congestive heart failure secondary to idiopathic or ischemic dilated cardiomyopathy[END_REF] and the peak velocity of tricuspid annular systolic motion measured using TDI. [START_REF] Damy | Comparison of four right ventricular systolic echocardiographic parameters to predict adverse outcomes in chronic heart failure[END_REF] These two parameters merely estimate the annular longitudinal function of the RV free wall, based on displacement of the tricuspid ring relative to the transducer. More recently, TDI-based parameters reflecting myocardial deformation, such as strain and strain rate, were shown to be closely related to the intrinsic functional capacity of the RV myocardium and to be more sensitive than previous parameters to subtle changes in contractility. [START_REF] Donal | Echocardiographic right ventricular strain analysis in chronic heart failure[END_REF][START_REF] Giusca | Deformation imaging describes right ventricular function better than longitudinal displacement of the tricuspid ring[END_REF] However, the angle dependency and absence of automatic measurement methods were major obstacles to the use of RV strain and strain rate. Since then, speckle tracking has been developed to image myocardial deformation imaging as a means of assessing RV systolic function. Speckle tracking provides rapid and simultaneous quantification of both regional and global lateral RV systolic function, as longitudinal lateral (free wall) RV function generates 80% of the RV stroke volume. [START_REF] Carlsson | The quantitative relationship between longitudinal and radial function in left, right, and total heart pumping in humans[END_REF] TDI and 2D strain-derived parameters have been found superior over conventional echocardiographic parameters in identifying patients with regional RV dysfunction. [START_REF] Teske | Echocardiographic tissue deformation imaging quantifies abnormal regional right ventricular function in arrhythmogenic right ventricular dysplasia/cardiomyopathy[END_REF] Furthermore, 2D strain is relatively angle-independent and independent of cardiac motion, in contrast to TAPSE. 17 2D strain is also easily measurable using automatic software.

Prognostic significance of RV systolic function in CHF and RV-2D strain

RV systolic function strongly predicts the occurrence of cardiac events in patients with CHF. [START_REF] De Groote | Right ventricular ejection fraction is an independent predictor of survival in patients with moderate heart failure[END_REF][START_REF] Ghio | Prognostic usefulness of the tricuspid annular plane systolic excursion in patients with congestive heart failure secondary to idiopathic or ischemic dilated cardiomyopathy[END_REF][START_REF] Salvo | Preserved right ventricular ejection fraction predicts exercise capacity and survival in advanced heart failure[END_REF] In keeping with an earlier study in patients with acute myocardial infarction, [START_REF] Antoni | Prognostic value of right ventricular function in patients after acute myocardial infarction treated with primary percutaneous coronary intervention[END_REF] RV-2D strain was a strong predictor of our composite primary outcome in CHF patients. A cut-off of -21% was optimal for separating patients with and without the primary outcome after 1 year of follow-up. Similar cut-offs were found using speckle tracking in patients with myocardial infarction (-22.1%) [START_REF] Antoni | Prognostic value of right ventricular function in patients after acute myocardial infarction treated with primary percutaneous coronary intervention[END_REF] or TDI-derived strain measurement in patients with arrhythmogenic RV cardiopathy (-18.2%). [START_REF] Teske | Echocardiographic tissue deformation imaging quantifies abnormal regional right ventricular function in arrhythmogenic right ventricular dysplasia/cardiomyopathy[END_REF] It is worth noting that reported RV cut-offs are higher than the previously reported LV cut-off (-9%). [START_REF] Nahum | Impact of longitudinal myocardial deformation on the prognosis of chronic heart failure patients[END_REF] Longitudinal motion can be quantified using either strain or strain rate. Strain rate is assumed to be load independent and superior over strain in assessing myocardial contractility and prognosis. In our study, however, RV-2D strain performed better than strain rate in predicting the primary outcome. We previously obtained a similar result when assessing the prognostic significance of LV systolic function in patients with unstable CHF. [START_REF] Nahum | Impact of longitudinal myocardial deformation on the prognosis of chronic heart failure patients[END_REF] The superiority of 2D strain over strain rate may be related to the smaller amount of noise in the strain data, which facilitates identification of the peak.

Limitations of RV-2D strain measurement

RV-2D strain was not measurable in 18 (11%) of our 161 study participants. The RV basal segment was less often measurable than the apical or middle segment. In the controls, the basal RV segment was difficult to track when motion of this segment was substantial and directed not only anteriorly but also towards the septum. A similar difficulty occurred in CHF patients with major anterior systolic motion of the tricuspid annulus, usually related to elevated pulmonary artery pressure. [START_REF] Giusca | The right ventricle: anatomy, physiology and functional assessment[END_REF] In our study, we assessed longitudinal RV deformation and not radial RV deformation. When measured accurately, longitudinal deformation reflects global RV contractile function under baseline conditions and during acute load modulation, whereas circumferential motion is influenced by changes in afterload. [START_REF] Leather | Longitudinal but not circumferential deformation reflects global contractile function in the right ventricle with open pericardium[END_REF]

Conclusion

In this study, RV-2D strain reliably reflected RV systolic function. An RV-2D strain cutoff of -21% was best for separating patients with and without the composite primary outcome after 1 year. These results suggest that the use of 2D-strain to assess RV contractility should be encouraged in everyday clinical practice to better evaluate the prognosis of patients with CHF.

Funding

No specific funding was received for this study. The authors of the study are full-time salaried employees of their respective institutions.

Conflict of interest

None of the authors has any conflicts of interest to declare.


Frédéric Fauberteau
email: frederic.fauberteau@univ-paris-est.fr

Manar Qamhieh
email: qamhieh@ece.fr

Serge Midonnet
email: serge.midonnet@univ-paris-est.fr

Partitioned Scheduling of Parallel Real-time Tasks on Multiprocessor Systems

In this paper, we focus on the scheduling of periodic fork-join real-time tasks on multiprocessor systems. Parallel real-time tasks of fork-join model have strict parallel segments with no laxity. We propose a partitioned scheduling algorithm which increases the laxity of the parallel segments and therefore the schedulability of tasksets of this model. A similar algorithm has been proposed in the literature but it produces job migrations. Ours avoid the use of job migrations in order to create a portable algorithm that can be implemented on a standard Linux kernel. Results of extensive simulations are provided in order to analyze the schedulability of the proposed algorithm compared to the previous one.

Introduction

Chip manufacturers are tending to build multiprocessors and multi-core processors as a solution to overcome the physical constrains of the manufacturing process, such as chip's size and heating. Because of that, parallel programming has gained a higher importance although it has been used for many years.

The concept of parallel programming is to write a code that can be executed simultaneously on different processors, and usually these programs are harder to be written than sequential ones, since it is necessary to keep the parallel partitions independent in order to execute them correctly on different processors at the same time. This condition might not be affected by reasons like shortage in processors, which requires the use of partitioning. In real-time systems and as we found in literature [START_REF] Goossens | Gang ftp scheduling of periodic and parallel rigid real-time tasks[END_REF], [START_REF] Kato | Gang edf scheduling of parallel task systems[END_REF], a parallel task can be:

• rigid if the number of processors is assigned externally to the scheduler and can't be changed during execution,

• moldable if the number of processors is assigned by the scheduler and can't be changed during execution, • malleable if the number of processors can be changed by the scheduler during execution. From practical implementation's point of view, there exist certain libraries, APIs and models created specially for parallel programming like POSIX threads [START_REF]Posix threads programming[END_REF] and OpenMP [START_REF]Openmp[END_REF], except those are not designed for real-time systems normally, but in this paper we will work on periodic real-time tasks of fork-join structure, the same structure OpenMP is based on, and which can be seen as a rigid type of real-time parallelism.

The remainder of this paper is organized as follows: in Section 2, we present our task model. Section 3 describes a related work on the same model. Section 4 explains the proposed algorithm followed by the analysis in section 5. and we finish with perspective and the conclusion in sections 6 and 7.

Fork-Join Model

As shown in Figure 1, the fork-join model defines a task as a collection of several segments, both sequential and parallel, and this task always starts by a sequential segment, then it forks into several parallel independent threads (parallel segment) to be joined finally in another sequential segment. It is important to note that all parallel segments in a task shares the same number of processors, and it should be mentioned that tasks of this model have implicit deadline (deadline of a task equals its period ).

Here is an example of the fork-join model:

τ i = ((C 1 i , P 2 i , C 3 i , ..., P si-1 i
, C si i ), m i , T i ) where: • s i is the total number of segments (sequential and parallel) and it is an odd number according to definition of the model,

• m i is the number of parallel threads on which parallel segments will be executed. m i > 1 for parallel segments, and equals to 1 for sequential segments. • C s i is the Worst-Case Execution Time (WCET) of sequential segment, where s is an odd number and 1 ≤ s ≤ s i , • P s i is the WCET of parallel segment, where s is an even number and 1 ≤ s ≤ s i , • T i is the period of the task. What we can notice about this model is the fact that by default all parallel segments have to finish their execution before the following sequential segment starts. Therefore these segments have strict laxity and their execution times equal to their deadlines.

Deadline Di Ci 1 Pi 2,1 Ci 3 Ci 5 Ci k Pi 2,2 Pi 2,n Pi 4,1 Pi 4,2 Pi 4,n
Figure 2 shows a fork-join task, which can be represented as well according to the previous definition: (1, 2, 2, 3, 1), 3, 17).

Related work

Due to the strict laxity of the parallel segments in the fork-join task model, Lakshmanan et al. in [START_REF] Lakshmanan | Scheduling parallel real-time tasks on multi-core processors[END_REF] propose an algorithm to increase the laxity of the parallel segments by reducing the parallelism in the fork-join model when possible. Their algorithm stretches the main thread to its deadline, as shown in Figure 3. It aims to execute as much parallel segments as possible in the master string thread (the thread that contains the sequential segments and it is also considered as the entry and end point of the program), this master string will be stretched to its deadline so as to be executed on an exclusive processor with 100% processor's utilization. What remains of the parallel segments will be distributed on the available processors using partitioning algorithm called FBB-FFD (stands for Fisher Baruah Baker -First Fit Decreasing) [START_REF] Fisher | The partitioned scheduling of sporadic tasks according to staticpriorities[END_REF].

This algorithm enhances the schedulability of parallel tasks of fork-join structure, by increasing the parallel segments deadline and getting rid of their strict execution time, as shown in the example of Figure 2 and 3, parallel segment P 1,3 ′ has a deadline of 4 time units instead of 2 which was exactly the worst case execution time of that parallel segment, then it has to migrate to the master string so as to fill the master thread. This laxity in the deadline will increase the chances of the parallel segments to be scheduled using FBB-FFD as it will be clarified later in the analysis.

The number of job migrations in this algorithm could be either 0, if the algorithm succeeded in scheduling all the parallel segments into the master string, creating a sequential task that will be executed on one processor. The other possibility for the number of job migrations will be the number of parallel segments in the task, as shown in Figure 3 , both P 1,3 and P 2,3 are used to fill the slack time in the master string, and they both will migrate. Task Stretch Transformation (TST) has a constraint when it comes to practical implementation, that in order to achieve a fully stretched master string, then job migration is inevitable. As shown in the Figure 3, segments P 1,3 and P 2,3 have to start execution on a certain processor then they will migrate to the master string's processor in order to fill it. According to the paper, this can be easily implemented on a specific Linux system called Linux/RK [START_REF] Oikawa | Portable rk: A portable resource kernel for guaranteed and enforced timing behavior[END_REF] (stands for Linux Resource Kernel), which is a real-time extension to the Linux kernel to support the abstractions of a resource kernel. But our idea is to implement this algorithm directly on a standard Linux enhanced with PREEMPT_RT kernel patch.

Segment Stretch Transformation

In order to eliminate the use of job migration, some modifications have to be done on the original pseudocode, which we called Segment Stretch Transformation (SST), the basic idea of TST stayed the same, we will keep trying to avoid the fork-join model by stretching the master string, but now it will be filled only with complete parallel segments with no migration, the following example will better explain the modifications.

We have a task τ 1 = ((1, 2, 2, 3, 1), 3, 17) as shown in Figure 2, which is a typical fork-join task. In Figure 2 we show the result of applying TST on τ 1 . We can notice that segment P 1,3 and P 2,3 have to be executed on 2 processors. But in SST and as shown in Figure 4, the master string is only filled by complete parallel segments. Even though the master string is not fully stretched (there still a 1 unit of time not used before the deadline), the parallel segment P 2,3 will not be used. In TST, the master string has to be filled with all the parallel segments with equal partitions, which will increase the laxity of all the segments equally. But at the same time, it will increase the number of job migrations as well. However, in SST, the master string will be filled initially with the pre-calculated number of parallel strings, then we check if we can add other single parallel strings to the master string (like P 1,3 in Figure 4). The remaining parallel segments of the task with the master string will be scheduled using FBB-FFD partitioning algorithm. The laxity of the master string will increase since we did not fill it completely with parallel segments.

So, from a practical implementation point of view, the SST can be fully implemented on a standard Linux RT kernel with no special extensions or batches added, and by only using an ordinary function like sched_set_affinity(), each segment of the parallel task can be assigned to a specific processor, according the scheduling results of any partitioning algorithm (e.g. FBB-FFD).

Analysis

In order to provide a practical analysis for these algorithms, we are going to use rtmsim (stands for Real-Time Multiprocessor SIMulator). It is a free simulation software developed at Université Paris-Est Marnela-Vallée, France [START_REF]rtmsim[END_REF]. This simulation software helps analyzing the performance of real-time scheduling algorithms by choosing one of the pre-coded approaches and run in through extensive simulation.

For our extensive simulation analysis, we considered 4 identical processors with taskset utilization varies from 0.025 to 0.975 times the number of processors in steps of 0.025, and for each utilization value we run 10,000 tasksets each of 16 parallel tasks with implicit deadline, which will be scheduled using FBB-FFD partitioning algorithm.

We started the analysis by creating a dataset of parallel tasks of the fork-join model, and by using FBB-FFD directly to schedule this dataset, we got the results shown in Figure 5(a) (the curve with the rectangle points). And as we can see from this result, FBB-FFD failed to schedule the dataset after processors' utilization of 0.1. This can be explained by knowing that FBB-FFD is using the following condition. For each task τ i to be placed on processor k, the following condition has to be true:

d i - τj ∈τ (π k ) RBF * (τ j , d i ) ≥ e i
where τ i is the task to be scheduled on processor k, π k is the set of tasks already placed on processor k and

RBF * (τ j , d i ) = e j + ej Pj * d i !" # !" $ !" % !" & !" ' !" ( (' (# () ($ (* (% (+ (& (, '( -.
/01234530!6768096 :;<.066<;!28=3=>48=<? @ABCD-!E@FFB@@CG @ABCD-!EH46I-8;08./J@FFB@@CG @ABCD-!E-0K90?8-8;08./J@FFB@@CG (a) Curves of comparison. According to this condition, if the task to be scheduled has both execution time and deadline of the same value, then it will be executed on an empty processor, considering the condition will fail if the processor already executes other tasks. And since parallel segments in the fork-join model have execution times equal to their deadlines always (Figure 2), then each parallel segment will need to be executed on a processor exclusively.

U i TST SST U i TST SST 0.
But by looking at the characteristics of the parallel segments, we can notice that they have offsets which means that they will not arrive all at the same time to be scheduled, and by using a suitable type of partitioning algorithm that can handle offsets we might be able to enhance the results of the simulation. FDD-RTA (First Fit Decreasing-Response Time Analysis) could be a good choice.

A second analysis is performed to compare TST and SST algorithms, by using the same model of extensive simulation described previously, the result of simulation is shown in Figure 5(a), where TST is the curve with the round points and SST is the curve with the square ones. As we can see, both curves are the same with no noticeable difference. There is a slight difference between these 2 algorithms as represented in Figure 5(b). The interesting result we can notice is the incomparability of these 2 algorithms.

Perspective

The temporal constraints of the theoretical real-time systems such as the worst case execution time, the deadline and the period, all these values can be estimated and specified. But when it comes to commercial real-time systems, some interferences and variations affect those constraints, the causes vary from the tasks to exceed their WCET, OS overheads to system interrupts [START_REF] Davis | Robust priority assignment for fixed priority real-time systems[END_REF], those variations made the constraints harder to be controlled and studied.

There exist some mechanisms to compute the variations in the temporal constraints and to analyze the interferences, among those we can mention as example the sensitivity analysis, which "provides useful information for changing the implementation by giving a measure of those computation times that must be reduced to achieve feasibility" [START_REF] Bini | Sensitivity analysis for fixed-priority real-time systems[END_REF]. And task's allowance which is defined as the maximum extra duration that can be granted to a faulty task without compromising the timeliness constraint of the task [START_REF] Bougueroua | Dealing with execution-overruns to improve the temporal robustness of real-time systems scheduled fp and edf[END_REF].

The principal idea of the algorithm TST is to design a full master string, where the processor's utilization is 100%, and there is no laxity which means the worst execution time of the task equals to its deadline. However, in our proposed algorithm SST, we stopped the migration and created a non-full master string by filling it with complete segments, which increased the laxity of the master string as well as the parallel segments, and it is a step forward to build a robust system.

In the future, we aim to provide an algorithm which computes a robust partitioning, in which we maximize the acceptable variations of the temporal constraints, taking into account the variations of possible WCET overruns. As well as maximizing the duration of a task without compromise missing its deadline [START_REF] Fauberteau | A robust partitioned scheduling for real-time multiprocessor systems[END_REF].

Conclusion

In this paper, we presented an algorithm that transforms parallel tasks of fork-join structure in order to increase the laxity of the parallel segments, and eliminate the use of job migration, which makes it possible to be implemented on standard Linux kernel. The analysis of this algorithm is performed by using extensive simulations in order to compare its performance with the original taskset model and TST algorithm. Our next step will be to study the possibility of proposing a robust partitioning algorithm so as to maximize the laxity of the segments and tolerate the execution overruns of the parallel task model.

Figure 1 .

 1 Figure 1. Fork-Join structure model.

Figure 2 .

 2 Figure 2. Example of fork-join task.

Figure 3 .

 3 Figure 3. Task Stretch Transformation.

Figure 4 .

 4 Figure 4. Segment Stretch Transformation.


Frédéric Fauberteau
email: frederic.fauberteau@univ-paris-est.fr

Serge Midonnet
email: serge.midonnet@univ-paris-est.fr

Robust Partitioning for Real-Time Multiprocessor Systems with Shared Resources

Keywords: Real-time Scheduling, Multiprocessor Systems, Robustness, Partitioning Algorithms, Shared Resources

In this paper, we focus on the temporal robustness in the hard real-time multiprocessor systems. This robustness is the capacity to tolerate faults in such a way that no deadlines are missed. A model of sporadic and dependent tasks is considered. Our contribution is to propose a partitioning algorithm which assigns the tasks to processors in order to maximize the robustness of the system to Worst Case Execution Time (WCET) overruns faults or Minimum Inter-arrival Time (MIT) violations.

INTRODUCTION

We consider that an application consists of a set of tasks where each task is recurring jobs. One of the main problems in real-time scheduling is to guarantee that no task misses its deadline. Uniprocessor scheduling attempts to solve the priority problem: when, and in what order should each job execute. In multiprocessor scheduling, to the priority problem is added the allocation problem: on which processor a job should execute. Multiprocessor scheduling algorithms can be classified according theses two problems.

We focus on the static-priority approach (for the priority problem) for which each task has a single static priority applied to all of its jobs and on the partitioned approach (for the allocation problem) for which each task is allocated on a processor and no migration is allowed. The partitioned scheduling approach consists in partitioning a taskset among processors. Each subset of task is scheduled on in own processor independently of others. The partitioning problem can be seen as bin-packing problem which is N P -hard in the strong sense. Hence no optimal algorithm exists unless P = N P . But several approaches are inspired by techniques for bin-packing and enable to solve partitioning problem.

RACS 2011 November 2-5, 2011, Miami, FL, USA.

We also consider that the tasks are dependent in the sense that they share resources. Then it is necessary to use a synchronization protocol to avoid unbounded blocking times due to priority inversion. In this context, we are interested in supplying robustness by maximizing the capacity of tasks to stand up to WCET overruns faults. The robustness is the capacity to tolerate temporal faults such as WCET overruns or MIT violations. When a temporal fault occurs (due to a high priority task), the low priority and non faulty tasks are protected against deadline missed (temporal failure). This property is called the fault isolation.

Related work

One of the most prevalant strategies to provide fault tolerance is replication. Qin and Hong has proposed an algorithm which generates distributed static schedules to handle processor failures [START_REF] Qin | A novel fault-tolerant scheduling algorithm for precedence constrained tasks in real-time heterogeneous systems[END_REF]. Emberson and Bate have proposed a task allocation algorithm which takes into account static redundancy to dispatch the tasks among the processors [START_REF] Emberson | Extending a task allocation algorithm for graceful degradation of real-time distributed embedded systems[END_REF]. Our paper is concerned by a strategy of margin on the temporal constraints of the tasks. Instead to replicate tasks to deal with faults, we give them the possibility to continue their execution beyond their WCET.

Echtle and Eusgeld used a genetic algorithm to find faulttolerant partitions [START_REF] Echtle | A genetic algorithm for fault-tolerant system design[END_REF]. However, their work does not focus on real-time systems. Tindell, Burns and Wellings have proposed a partitioning algorithm based on simulated annealing to allocate tasks on a multiprocessor distributed systems [START_REF] Tindell | Allocating hard real-time tasks: An NP-hard problem made easy[END_REF]. Di Natale and Stankovic have also used this technique to deal with systems of tasks with jitter [START_REF] Natale | Applicability of simulated annealing methods to real-time scheduling and jitter control[END_REF]. These two works are aimed at real-time systems but the fault-tolerance is not taken into account.

Oh and Son discuss the need to consider schedulability and fault-tolerance simultaneously [START_REF] Oh | Scheduling real-time tasks for dependability[END_REF]. They prove that finding a schedule to handle a single processor failure is a NP-hard problem. Their model does not include dependency constraints.

In this paper, we propose a partitioning algorithm which is fault-tolerant in such a way that it dispatches the tasks in order to maximize the margin (on WCET overruns or on frequency increasing).

Terminology

We consider a set τ = {τ1, τ2, . . . , τn} of n sporadic real-time tasks. A sporadic task is a recurring task for which only a lower bound on inter-arrival time of the jobs is known. Each task τi is characterized by a minimum inter-arrival time Ti (also denoted period), a WCET Ci and a relative deadline Di. The considered tasks are tasks with constrained deadlines (i.e. Di ≤ Ti). The processor utilization of τi is denoted Ui and is defined as Ui = Ci/Ti. This application runs on a platform Π = {π1, π2, . . . , πm} of m identical processors (homogeneous case). A job Ji is characterized by its release time ri, its execution time ei (observed at run time) and its absolute deadline di. The processor utilization of the τ is denoted U (τ ) and the total processor utilization of πj is denoted U (πj). We consider a static-priority scheduling on each processor. The priorities of the tasks are taken in an increasing order (i.e. the priority of τi+1 is higher than the priority of τi). The set of tasks with a priority lower (resp. higher) than the priority of τi is denoted lp(τi) (resp. hp(τi)). In this paper, we denote Ri the response time of a task τi and Bi the blocking factor incurred by the task τi. We also denote A C i (resp. A f i ) the value of WCET (resp. frequency) margin of τi.

Organization

The rest of this paper is organized as follows. In Section 2 we present several synchronization protocols for multiprocessor systems. In Section 3, we present the concept of robustness to WCET overruns faults and MIT violations. We describe how to compute the margin of the tasks on their WCET and their period. In Section 4, we propose a partitioning algorithm which maximize the robustness in terms of WCET overruns faults. In Section 5, we compare by simulation our approach with existing ones. Finally, we conclude and give some perspectives in Section 6.

SYNCHRONIZATION PROTOCOLS

In real-time systems, the synchronization protocols are used to avoid the unbounded priority inversions which could occur with a simple lock mechanism. In the multiprocessor context, three main protocols are often cited in the literature. We present them in the following sections.

MPCP

Multiprocessor Priority Ceiling Protocol (MPCP) is an extension to the multiprocessor case of the Priority Ceiling Protocol (PCP) proposed by Sha, Rajkumar and Lehoczky in [START_REF] Sha | Priority inheritance protocols: An approach to real-time synchronization[END_REF]. MPCP has been proposed by Rajkumar in [START_REF] Raj | Real-time synchronization protocols for shared memory multiprocessors[END_REF].

With PCP, a priority ceiling p(R k ) is associated with each shared resource R k . p(R k ) is defined as the priority of the highest priority job which can lock R k . At time t, the system priority ceiling p(t) is given by the highest priority ceiling of the locked resources at t. A job Ji can lock a resource R k at time t only if the priority of Ji is strictly greater than the system priority ceiling. Otherwise, the job which blocks Ji inherits the priority of Ji.

With MPCP, two types of resources are distinguished: local and global resources. The local resources are only shared by jobs on the same processor whilst global ones are shared by jobs which can be assigned on several processors. When a job tries to lock a local resource, the behavior of MPCP is the same as PCP. For the case of global resources, a set of priorities higher than the highest priority ceiling is used. Then, accesses to global resources are made uppermost to limit indirect blocking.

MSRP

Multiprocessor Stack Resource Protocol (MSRP) is an extension to the multiprocessor case of the Stack Resource Protocol (SRP) proposed by Baker in [START_REF] Baker | Stack-based scheduling of realtime processes[END_REF]. MSRP has been proposed by Gai et al. in [START_REF] Gai | A comparison of MPCP and MSRP when sharing resources in the Janus multiple-processor on a chip platform[END_REF].

With SRP, each job Ji is characterized by a preemption level ρ(Ji). Ji is allowed to preempt Jj only if ρ(Ji) > ρ(Jj). Each resource R k has a preemption ceiling ρ(R k ) defined as the highest preemption level of the jobs which can lock R k . At time t, the system preemption ceiling is given by the highest preemption ceiling among resources currently locked. The activ jobs are stored in a stack in decreasing order of their priority. Ji is allowed to preempt Jj if Ji is the highest active job and if its preemption level is strictly greater than the system preemption ceiling.

With MSRP at time t, a preemption ceiling ρ(t, πj) is fixed for each processor πj. For each global resource R Gk , each processor πj defines a preemption ceiling ρ(R Gk ) higher than the highest preemption ceiling on πj. For local resources, the MSRP behavior is the same as SRP. When a job attempts to lock a global resource R Gk on πj, ρ(t, πj) is raised to ρ(R Gk ) making Ji non-preemptive.

FMLP

Flexible Multiprocessor Locking Protocol (FMLP) is a synchronization protocol exclusively developed for the multiprocessor systems. It has been proposed by Block et al. in [START_REF] Block | A flexible real-time locking protocol for multiprocessors[END_REF]. Initially, FMLP has been proposed to synchronized shared resources in both partitioned and global EDF scheduling. It has been extended to deal with the partitioned Fixed-Task-Priority scheduling approach of Brandenburg and Anderson in [START_REF] Brandenburg | An implementation of the PCP, SRP, D-PCP, M-PCP, and FMLP real-time synchronization protocols in LIT M U S RT[END_REF].

FMLP takes advantage of both busy-wait and by suspension approaches. To do that, two types of resource are considered: short (R s k ) and long R l k ) resources. When a job Ji attempts to lock an already locked short resource R s k , it busy waits non-preemptively for R s k . This behavior tends to reduce response-time of jobs when they use shared resources for short time.

TASK MARGIN

We focus on temporal robustness which consists in tolerance to temporal faults in systems. The schedulability analysis of fault-tolerant systems has been studied by Burns, Davis and Punnekkat [START_REF] Burns | Feasibility anlaysis of fault-tolerant real-time task sets[END_REF]. More recently, Bougueroua, George and Midonnet has proposed an approach to compute a margin of tolerance on the WCET [START_REF] Bougueroua | Dealing with execution-overruns to improve the temporal robustness of real-time systems scheduled FP and EDF[END_REF]. We present it in Section 3.1 and we propose its extension to the domain of periods in the Section 3.2.

In this section, we use the notation C * i which is defined by

C * i = Ci + Bi.

WCET margin

The constraints in a hard real-time system are defined such that no deadlines of any task are missed. Moreover, the WCET of a task is estimated or computed in order to ensure that the task never runs for a duration longer than its WCET. If a task commits a WCET overruns fault, the system may fail unless the task has enough WCET margin.

Definition 1 (WCET margin). The WCET margin A C i of a task τi is the additional execution time which can be added to the WCET Ci of τi in such a way that no task of τ misses its deadline.

A value A C

i is a correct WCET margin value for τi on πj if it verify the inequalities:

U (πj) + A C i Ti ≤ 1 (1)
R k+1 i = C * i + A C i + τ h ∈hp(τ i ) R k i T h C h ≤ Di ( 2
)
∀τ l ∈ lp(τi), R k+1 l = C * l + τ h ∈hp(τ l ) R k l T h C h + R k l Ti A C i ≤ D l (3)
The maximum value of WCET margin for τi can be computed by binary search over the interval [0, min(Di -Ci, (1-U (πj))Ti)].

Frequency margin

The sporadic (and periodic) tasks are characterized by a minimum inter-arrival time. If a job is activated as earlier as planed (e.g. faulty external component), the system may fail unless the task has enough frequency margin.

Definition 2 (Frequency margin). The frequency margin A f i of a task τi is a period of time which can be subtracted to the period Ti of τi in such a way that no task of τ misses its deadline.

A value A f i is a correct frequency margin value for τi on πj if it verify the inequalities:

U (πj) -Ui + Ci Ti -A f i ≤ 1 (4) R k+1 i = C * i τ h ∈hp(τ i ) R k i T h C h ≤ Ti -A f i ( 5
)
∀τ l ∈ lp(τi) R k+1 l = C * l + τ h ∈hp(τ l )-τ i R k l T h C h + R k l Ti -A f i Ci ≤ D l (6)
The maximum value of frequency margin for τi can be computed by binary search over the interval [0, Ti -1].

Margin of dependent tasks

For the case of independent tasks, if a fault occurs during the execution of a job Ji, Ji can continue its execution for

Job Proc. ri ei di J1 π1 2 1 + 2(R l G1 ) + 1 12 J2 π2 3 1 + 1(R l G1 ) + 3 + 1(R l G2 ) + 1 15 J3 π1 0 1 + 5(R l G1 ) + 1(R l G2 ) + 1 16 J4 π2 0 2 + 1(R l G1 ) + 1 14
Table 1: Parameters of jobs in Figure 1.

A C i .
If the tasks share resources, the WCET margin of Ji in a critical section can be less than A C i . In Figure 1(a), we represent the schedule of 4 jobs characterized by the parameters given in Table 1. The synchronization protocol is FMLP and the resources are considered as long. We consider each job executing for its WCET (ei = Ci). If a fault occurs at the end of the execution of J3, it can continue until time 16 in such a way that no job misses its deadline. Then the value of WCET margin A C i is 5 units of time if it is used at the end of the execution of J3.

In Figure 1(b), we represent an execution overrun in the critical section associated to R l G1 . J3 can increase its budget of time by just 1 unit of time. We notice that the WCET margin of a job in a critical section is bounded by the minimum margin of all the jobs which share the resource guarded by this section.

ROBUST PARTITIONING

Simulated annealing is a generic algorithm which has been firstly proposed by Kirkpatrick, Gelatt and Vecchi [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF] for the optimization problems. The name and inspiration come from annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and to reduce their defects. In this work, we apply the simulated annealing technique to build an algorithm which finds a feasible partition of a set of tasks where the robustness to the WCET overruns faults is maximized. We describe this algorithm, Robust Simulated Annealing (RPSA) in Algorithm 1. The initialization is made as follows. At line 1, the function random_partition() build a partition P by allocating each of the n tasks on one of the m processors randomly. This partition may be unfeasible. At line 2, an initial temperature is computed such as 99% of the partitions are kept even if they do not improve the solution. By cooling the system (decreasing the temperature), the unsatisfying solutions will be eliminated. At line 3, we initialize the max_try value to an integer which depends both of the number of tasks and of the number of processors. The loop at line 4-21 performs max_try iterations of the loop at line 6-19. After each iteration, the system is cooled by dividing the temperature by 2. The main part of the algorithm is the loop at line 6-19. At line 7, the function compute_energy() computes the energy of the partition P . This function is more detailed later in Algorithm 2. At line 8, a partition Pn which is the neighbor of the partition P is computed. This partition Pn is obtained either by randomly swapping two tasks of P or by randomly moving a task of P from a processor to another. The energy of this new partition is computed at line 9. If the value En of the energy of Pn is less than the value Ep of the energy of P then P is replaced by Pn. Otherwise, a random number is drawn between 0 and 1. The more the temperature temp high is, the more the probability that the value e x (x = Ep-En temp ) is greater than the random number is. If e x > random(0, 1) then P is also replaced by Pn else Pn is discarded. This behavior avoids that the energy converge to a local minimum. We The aim of this function is to compute a value of energy for a partition such that the more the minimum value of margin for the system is great, the less the value of energy is. The value of energy is computed as follows. For each processor πj, if the processor is empty then the value of energy is increased by 1. This behavior increase the probability that the tasks are well distributed among the processor and no processors stay empty. If the set of tasks allocated on this processor is unschedulable then the value of energy is also increased by 1 to eliminate the unfeasible partitions. For each processor πj where the set of tasks is schedulable, the sum of margin on the execution duration values of each task is stored in the array margin at index j. At the end of the loop at line 3-10, the value of energy is increased by the sum of all the values stored in the array margin. Consequently the more the value of margin of each task great is, the less the value of energy is. We implemented a simulator of real-time systems which provides several partitioning algorithms. Among others, it implements both RPSA and SPA algorithms.

We also implemented a taskset generator which randomly makes sets of tasks with shared resources. The tasks generation process is based on the UUniFast-Discard algorithm proposed by Davis and Burns [START_REF] Davis | Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems[END_REF]. This algorithm is the extension to the multiprocessor case of the UUniFast algorithm proposed by Bini and Buttazzo [START_REF] Bini | Biasing effects in schedulability measures[END_REF].

For each value of processor utilization in [0.025, 0.05, . . . , 0.975], we randomly generated 1,000 tasksets with constrained deadlines. Each simulation consists in the partitioning of a taskset of 16 tasks on 4 processors. Each task has a random number of critical section in {0, 1, 2}. There are half as many resources as critical sections.

SPA has been initially proposed in order to use MPCP as synchronization protocol. In the context of our simulations, we have modified it to be based on FMLP.

Results

In Figure 2, we represent the comparison between RPSA and SPA in terms of schedulability and minimum margin.

In Figures 2(a 4), ( 5) and ( 6) (described in Section 3.2).

We show that RPSA outperforms on average SPA in terms of schedulability. Our algorithm takes advantage of the simulated annealing technique. Then it find solutions which can not be found by the BF algorithm (the one on which SPA is based).

In terms of robustness, RPSA produces partitions for which the margin of the tasks is increased compared to SPA.

CONCLUSION

We have proposed the partitioning algorithm RPSA based on the simulated annealing technique. We have considered a model of sporadic tasks with shared resources. The synchronization of data is performed by the FMLP protocol.

Our algorithm allocates the tasks on the processors in order to maximize the robustness to the WCET overruns faults and MIT violations. We have implemented our algorithm in our simulator of real-time systems and we compare it with the SPA heuristic. We have shown that our solution outperforms the heuristic approach in terms of both schedulability and robustness.

  WCET margin inside critical section.

Figure 1 :

 1 Figure 1: WCET margin of dependent tasks.

Algorithm 1 : 2 max try = n • m; 3 while temp > 10 -5 do 4 k = 0; 5 while k = max try do 6 Ep 14 P

 12345614 RPSA P = random partition(n, m); 1 temp = -m ln(0.99) ; = compute energy(P );if e x ≥ random(0, 1) then the function compute_energy().

Algorithm 2 : 1 margin[m]; 2 foreach πj ∈ P do 3 if 9 end 10 energy = energy + 1 m

 21239101 compute energy(P) energy = 0; πj is empty or πj is unschedulable then 4 energy = energy + 1; 5 margin[j] = 0; 6 else 7 margin[j] = τ i ∈τ (π j ) Ai 8 end

  ) and 2(c), RPSA has been implemented to maximize the WCET margin. The compute_energy() function of RPSA uses the Equations (1), (2) and (3) (described Minimum margin of RPSA (WCET margin) vs SPA. Minimum margin of RPSA (Frequency margin) vs SPA.

Figure 2 :

 2 Figure 2: Simulations of RPSA and SPA on 4 processors.