Manar Qamhieh
email: manar.qamhieh@univ-paris-est.fr

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

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

Performance Analysis for Segment Stretch Transformation of Parallel Real-time Tasks

The Segment Stretch Transformation (SST) is an algorithm that transforms parallel Fork-Join (FJ) tasks into sequential tasks on multiprocessor systems when possible, in order to increase the schedulability of the tasksets of this model. SST is based on Task Stretch Transformation (TST) which is a transformation for the same model of tasks, but it uses segment migrations while SST eliminates their use.

In this paper, we prove that SST transformation has the same performance of TST transformation by providing a detailed analysis based on Demand Bound Function (DBF) and by showing that SST has a resource augmentation bound of 3.42, same as TST, which means that if a taskset is feasible on m speed processors, then it is schedulable using the transformation on m processors that are 3.42 times faster.

I. INTRODUCTION

Parallelism in normal systems is widely used for a long time, and it is created specially to cope with the tendency of chip manufacturers to build multiprocessor systems. But in real-time systems, the integration of parallelism is more complicated when it is to be compared with ordinary sequential tasks even if they are executed on multiprocessor systems. Parallelism in real-time systems can be defined as the execution of the same task at the same time on multiple processors while respecting certain time constraints like period or deadline.

Parallelism has many models and theories that are applied in actual programming languages, like the MapReduce model which is designed by Google in order to speed up the execution of massive data on multiple processors. Another model is the fork-join model "FJ", which is a common parallel computing model and it is the base of OpenMP parallel programming C library [START_REF]Openmp[END_REF].

The remainder of this paper is organized as follows: in Section II, we present our task model. Section III describes the transformations TST and SST. Section IV contains the analysis of the demand bound function and resource augmentation bound done on the SST, and we finish with the conclusion in section V.

II. FORK-JOIN MODEL

The parallel real-time task of fork-join model is a task in which certain parts are executed simultaneously on multiple processors. As shown in Figure 1, FJ task consists of segments, both sequential and parallel. The task always starts by a sequential segment which is executed on one processor, and then it forks into a specific number of parallel segments, which they join together into a sequential segment, and so on. The number of segments are defined by the model, as well as the number of parallel processors, which means that all the parallel regions in the task share the same number of processors.

An implicit-deadline FJ task is described as the following:

τ 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 segments in each parallel region fixed by the model. m i > 1 for parallel segments, and equal to 1 for sequential segments. • C k i is the Worst Case Execution Time (WCET) of the k th sequential segment, and k is an odd number and 1 ≤ k ≤ s i , • P k i is the WCET of the parallel segments in the k th parallel region, where k is an even number and 1 ≤ k ≤ s i , and Definition II.1 (Master string). The master string of a parallel FJ task is a collection of segments that executes within the master thread of the task, starting by the first sequential segment and then the intermediate parallel and sequential segments, and ending by the last sequential segment. In numerical notations, master string can be represented as:

P k i = P k,1 i = P k,2 i = . . . = P k,mi
τ 1 i , τ
P i = s i -1 2 k=1 P 2k i (1)
Definition II.3 (Minimum execution length). The minimum execution length η i represents the minimum time a FJ task τ i needs to execute when all parallel segments are executed in parallel. It is equal to the sum of WCET of all segments in the master string of task τ i :

η i = ( s i -1 2 k=0 (C 2k+1 i )) + P i (2)
Definition II.4 (Maximum execution length). The maximum execution length C i , which is the sum of WCET of all sequential and parallel segments in task τ i :

C i = ( s i -1 2 k=0 (C 2k+1 i )) + m i * P i (3)
Definition II.5 (Slack time). The slack time L i is the temporal difference between the deadline and the minimum execution time.

L i = D i -η i (4)
Definition II.6 (Capacity). The capacity f i is defined as the capacity of the master string to execute parallel segments from all parallel regions within itself without missing its deadline.

f i = L i P i (5)

III. RELATED WORK A. Task Stretch Transformation

According to Lakshmanan et al. in [START_REF] Lakshmanan | Scheduling parallel real-time tasks on multi-core processors[END_REF], the parallel real-time tasks of FJ model on multiprocessor systems can have schedulable utilization bound slightly greater than and arbitrarily close to uniprocessor schedulable utilization bound. Therefore they proposed an algorithm called TST.

The main objective of TST is to convert the parallel FJ task into sequential when possible, by creating a fully stretched master string where its execution time is equal to its deadline. Part of the parallel segments execute within the master string and the remaining ones are scheduled by a specific partitioned scheduling algorithm called FBB-FFD ({Fisher,Baruah,Baker}-First-Fit Decreasing) [START_REF] Fisher | The partitioned scheduling of sporadic tasks according to static-priorities[END_REF].

TST is proved to have a resource augmentation bound of 3.42, which means any taskset that is feasible on m unit speed processors is feasible using the TST on m processors of speed 3.42.

B. Segment Stretch Transformation

Since segment migrations are used heavily in the TST which limits its implementation by using a special Linux kernel called Linux/RK which supports semi-partitioning, we proposed earlier a modification to the algorithm called SST for the same FJ model of parallelism [START_REF] Fauberteau | Partitioned scheduling of parallel real-time tasks on multiprocessor systems[END_REF].

SST also tries to convert the parallel tasks into sequential ones by creating a master string, which in this case can be either fully stretched or not, in order to provide a partitioned scheduling for the parallel FJ tasks by eliminating the segment migration. As a result the new transformation algorithm can be implemented directly on a RT Linux kernel with no specific patches.

For a parallel implicit deadline task τ i of FJ model, with maximum execution time of C i , deadline of D i , SST has 3 scenarios:

1) C i ≤ D i : the task will be fully converted from parallel task to sequential, 2) C i > D i and the master string will be fully stretched.

The slack L i of the master string will be completely filled by parallel segments and its execution time will be equal to the deadline, 3) C i > D i and the master string will not be fully stretched, some of the slack time will remain unfilled. In this paper we prove that SST have the same resource augmentation bound as TST, by providing a performance analysis on these 3 scenarios which is inspired by the analysis performed on TST algorithm in [START_REF] Lakshmanan | Scheduling parallel real-time tasks on multi-core processors[END_REF].

IV. ANALYSIS

A. Demand Bound Function "DBF" Definition IV.1 (DBF [START_REF] Baruah | Preemptively scheduling hard-real-time sporadic tasks on one processor[END_REF]). DBF is defined as the largest cumulative execution requirement of all jobs that can be generated by τ i to have both their arrival times and their deadlines within a contiguous interval of length t.

For a task τ i with a total execution time of C i , period of T i and a deadline of D i ≤ T i DBF is given by:

DBF (τ i , t) = max(0, ( t -D i T i + 1)C i ) (6)
Theorem IV.1 (DBF). DBF of a stretched task τ stretched i using SST is:

DBF (τ stretched i , t) ≤ C i T i -η i t
where 0 ≤ η i ≤ T i .

Proof: In order to generalize DBF for the stretched task, the three cases of SST (Section III-B) have to be analyzed.

1) For the first case, the parallel task is transformed totally into a sequential one which is the master string, and

D master i = T master i and C master i = C i (Equation (3)
). DBF is calculated as the following:

DBF (τ stretched i , t) = DBF (τ master i , t) DBF (τ stretched i , t) = max 0, t -D i T i + 1 C master i DBF (τ stretched i , t) = max 0, t T i C i ≤ C i T i t DBF (τ stretched i , t) ≤ C i T i -η i t where 0 ≤ η i ≤ T i . 2)
The second case is when the master string is fully stretched but there exist parallel constrained deadline segments that are not part of the master string and will be scheduled using FBB-FFD:

τ stretched = τ master + {τ cd }
DBF will be as the following:

DBF (τ stretched i , t) ≤ DBF (τ master i
, t)+DBF ({τ cd i }, t) DBF for the master string can be calculated knowing that the master string is fully stretched, and

C master i = D master i : DBF (τ master i , t) ≤ C master i D master i t DBF (τ master i , t) ≤ t
The group of segments {τ cd i } consists of segments from all the parallel regions in τ i , and only one parallel region is activated at time instant t. The maximum number of parallel segments in each region is (q i -1), where q i = m i -f i . Figure 2 shows an example of a stretched task of the second case, with constrained-deadline parallel segments of 3 different parallel regions. Therefore, DBF can be calculated as the following:

DBF ({τ cd i }, t) ≤ δ max i (q i -1)t (7)
The density of a constrained deadline task τ i is given by:

δ i = C i D i
As shown also in Figure 2, the SST algorithm starts by filling the slack of the master string by f iparallel segments from each parallel region, and then we add other parallel segments if their WCET fits in the remaining slack. For a k parallel region, all τ cd have the same WCET P k i , and deadline D k i where D k i = (1 + n f i )P k i , and 1 ≤ n < m i according to the number of parallel segments from region which execute within the master string. The maximum density of the parallel constrained deadline tasks τ cd can be calculated as the following:

δ max = s i -1 2 max k=1 P 2k i (1 + n f i )P 2k i δ max = s i -1 2 max k=1 1 (1 + n f i ) δ max = 1 1 + f i
Since there exist at least one parallel region where n = 1, this region is the one with the highest density. Using this result in Equation ( 7), the DBF is as the following: In order to eliminate the use of f i in our calculations, we will use the following approximation:

DBF ({τ cd i }, t) ≤ 1 1 + f i (q i -1)
δ max i = 1 1 + f i f i -f i < 1 =⇒ 1 + f i > f i δ max i < 1 f i
which will lead to the following:

DBF ({τ cd i }, t) ≤ 1 f i (q i -1)t f i = T i -η i P i DBF ({τ cd i }, t) ≤ (q i -1)P i T i -η i t (8)
DBF of the whole stretched task can be calculated as the sum of both the master string and the group of constrained deadline, as the following:

DBF (τ stretched i , t) ≤ DBF (τ master i , t) + DBF ({τ cd i }, t) DBF (τ stretched i , t) ≤ t + (q i -1)P i T i -η i t DBF (τ stretched i , t) ≤ T i -η i + (m i -f i -1) T i -η i t DBF (τ stretched i , t) ≤ m i P i T i -η i t ≤ C i T i -η i t
3) For the third case, the stretched task τ stretch i consists of a collection of constrained deadline tasks, including the master string, which will not be fully stretched. The execution time of the master string in this case will be as the following:

η i + P i f i ≤ C master i < C i ≤ T i C master i < T i =⇒ C master i T i < 1 DBF (τ master i , t) = max(0, t T i C master i ) DBF (τ master i , t) ≤ C master i T i t DBF (τ master i , t) ≤ t
For the group of constrained deadline segments τ cd , it is the same as in the second case, then we can use the previously calculated DBF (Equation ( 8)):

DBF (τ stretched i , t) ≤ DBF (τ master i , t) + DBF ({τ cd i }, t) DBF (τ stretched i , t) ≤ t + (q i -1)P i T i -η i t DBF (τ stretched i , t) ≤ C i T i -η i t
To sum up, the three cases of τ stretched by SST share the same DBF.

B. Resource Augmentation Bound

Lakshmanan et al. have analyzed the resource augmentation bound for their partitioned scheduling algorithm FJ-DMS (Fork-Join-Deadline-Monotonic Scheduling) [START_REF] Lakshmanan | Scheduling parallel real-time tasks on multi-core processors[END_REF]. The partitioning of the transformed set of tasks is carried out by FBB-FFD scheduling algorithm proposed by Fisher et al. [START_REF] Fisher | The partitioned scheduling of sporadic tasks according to static-priorities[END_REF]. The schedulability test for FBB-FFD is given by:

m ≥ δ sum + u sum -δ max 1 -δ max (9)
For a processor that is v times faster, the following can be applied:

∀1 ≤ i ≤ n, η v i ≤ T i v =⇒ (T i -η v i ) ≥ T i (1 - 1 v ) C v i = C i v u v sum = u sum v δ v max = δ max v n i=1 C i T i ≤ m δ v sum = max t>0 ( n i=1 DBF (τ stretched i , t) t ) δ v sum ≤ n i=1 C v i T i -η v i
In order to simplify the equation, the following can be applied:

u sum = n i=1 C i T i δ v sum ≤ n i=1 C v i T i -η v i ≤ n i=1 C v i T i (1 -1 v ) ≤ 1 v -1 u sum
By substituting the previous equations in Equation (9), a taskset is schedulable if:

m ≥ m v-1 + m v -δmax v 1 -δmax v This is an increasing function of δ max for m ≥ v 2 .
The density of any parallel thread with constrained deadline in SST is:

∀f i ≥ 0 =⇒ δ max i = 1 1 + f i 0 ≤ f i =⇒ 1 ≤ 1 + f i then δ max i ≤ 1 1+ fi ≤ 1.
Using this in Equation ( 9) and when m ≥ v 2 , the schedulability is ensured if:

m ≥ m v-1 + m v -1 v 1 -1 v
Applying the same calculations used on TST in [START_REF] Lakshmanan | Scheduling parallel real-time tasks on multi-core processors[END_REF], and for all m ≥ v 2 , we got the following result:

=⇒ v ≥ (2 + √ 2) ≈ 3.42
This approximated value of resource augmentation bound for SST is the same as the one in TST, and it means if a taskset is feasible on a m speed processors, then it is guaranteed that the transformation will schedule the same taskset on m processors with 3.42 times faster.

V. CONCLUSION In a previous paper [START_REF] Fauberteau | Partitioned scheduling of parallel real-time tasks on multiprocessor systems[END_REF], we presented SST, which is an algorithm design specially for parallel real-time tasks of FJ model based on another transformation called TST, which can be found in literature. Both algorithms enhance the schedulability of parallel tasks while the segment stretch has a practical implementation advantage gained by preventing the use of segment migration.

All the analysis we provided previously was an extensive simulation as a tool to measure the performance of SST in comparison with the TST, so as to see the effects of the proposed modifications. But in this paper, we provide a detailed analysis to calculate the demand bound function of the SST and to prove that it also has the same approximated resource augmentation bound 3.42, the same as TST. This analysis proved that SST does not only have the same performance as TST, but it also reduced the cost of segment migration.

In the future, we will continue working on parallel tasks of FJ model by providing a response time analysis, taking into account the specific constraints of this model of parallel tasks.

Fig. 1 .

 1 Fig. 1. Task of FJ model.

Fig. 2 .

 2 Fig. 2. SST: Parallel regions and constrained-deadline tasks {τ cd }.


PREFACE

Today's automatic control systems are of high degrees of integration, complexity, embedding and networking of heterogeneous entities. This trend is driven by the industrial needs for achieving new technical performance and meeting additional performance demands. A most critical and important issue surrounding the design and operation of complex automatic systems is the application of Fault Detection and Isolation and Fault-Tolerant Control (FDI/FTC) technology, aiming at guaranteeing high system performance over a wide operating range and meeting the requirements on system safety, reliability, availability and dependability. Although FDI/FTC has been developed in the framework of systems and control theories, it is mainly dedicated to the individual solutions for fault detection, diagnosis and fault tolerant control at the real time level. In order to cope with the industrial trends and demands, an FDI/FTC framework should be established in the context of fault management, health awareness and self-healing, and on a multi-disciplinary fundament with control, communication and computer sciences as its core. It is with these ideas in mind that the first edition of the Conference on Control and Fault-Tolerant Systems, SysTol'10, held in Nice, France, on 6-8 October 2010, was organized. The focus of the Conference was on new developments and applications of FDI/FTC and gathered the best international specialists. This special issue of AMCS is built around 14 selected contributions from this Conference, for which the authors were required to propose extended and enhanced versions of their work, and 3 complementary regular papers whose topics lie in this research area.

The design of a fault tolerant control law frequently necessitates detection, isolation and identification of faults, and this issue includes contributions in this area. The paper by H. Jamouli, M.A. El Hail and D. Sauter revisits the seminal work of Willsky and Jones about the generalized likelihood ratio test for fault detection. The proposed extension concerns the diagnosis of multiple sequential faults and is based on a reference model updated on line after the detection and isolation of each fault. The proposed strategy can be easily integrated in reconfigurable fault tolerant control systems. The paper by D. Uciński treats the problem of fault detection for processes described by partial differential equations. It is based on the maximization of the power of a parametric hypothesis test which checks whether or not system parameters have nominal values. Based on performance criteria related to the estimated parameters, a sensor network scheduling strategy consisting in selection of a subset from among a finite set of potential sensor location is proposed.

Graph theory and graphical methods have been used for a long time for highlighting structural properties of systems which can be exploited in the fault diagnosis framework. Among these tools, signed directed graphs are able to show the causal relationships between process variables. Establishing this type of model is difficult and the latter needs to be validated. The paper by F. Yang, S.L. Shah and D. Xiao proposes two validation methods based respectively on cross-correlation analysis and entropy transfer. An industrial case study illustrates the proposed methods. Graph-theoretic methods are also used in the paper by M. Ungermann, J. Lunze and D. Schwarzmann. It concerns the generation of test signals used in service diagnosis. This kind of approach can be likened to an active diagnosis method. Isolability of faults is analyzed with respect to system operating conditions.

A general multi-purpose fault tolerant control method is described in the paper by H.H. Niemann. A control architecture based on the Youla-Jabr-Bongiorno-Kucera (YJBK) parameterization is described. Based on this controller architecture the closed-loop system is analyzed by using the dual YJBK transfer function. This analysis is made with respect to closed-loop stability, fault diagnosis and system monitoring, and leads to redesign and controller reconfiguration. The paper by H. Yang, B. Jiang, V. Cocquempot and L. Lu follows the same objective. The proposed strategy relies on the assumption that the plant model belongs to a pre-specified set of models (nominal and faulty situations), and that there exists a finite family of candidate controllers such that the faulty system is stabilized when controlled by at least one of those candidate controllers. The authors then propose to sequentially switch controllers until the appropriate one is found. As a consequence, fault isolation boils down to finding the correct controller, which can be directly applied once selected.

Historically, from the point of view of practical applications, a significant amount of research on fault-tolerant control systems has been motivated by aircraft flight control system designs, with the goal of ensuring a safe landing in the event of severe faults in an aircraft. Although the fault-tolerant control problem has begun to draw more and more attention in a wider range of industrial and academic communities, aeronautic and aerospace applications continue to be in demand of this kind of research. Four papers cover fault tolerance and fault recovery in this application field. The first one, by X. Olive, presents the state of the art in fault management for autonomous satellites and describes the actual approaches implemented on an attitude and orbit control system of telecommunication satellites. The second paper, by C. Edwards, H. Alwi and C.P. Tan, explains how the sliding mode methods employing nonlinear control/injection signals to force the system trajectories to attain in finite time a motion along a surface in the state-space can be exploited for both fault detection and fault tolerant control. The proposed FTC scheme is illustrated on a motion flight simulator configured to represent a post-failure aircraft. The third work, by T. Jain, J.J. Yamé and D. Sauter, exploits the behavioral system theory. The suggested fault accommodation scheme relies on the design of an appropriate behavioral interconnection. The proposed fault tolerance mechanism is illustrated on an aircraft during the landing phase. Finally, the fourth paper, by P. Weber, B. Boussaid, A. Khelassi, D. Theilliol and C. Aubrun, develops a reconfigured control allocation strategy based on the on-line re-estimation of actuator reliability. It consists in modifying the reference according to the system constraints, which become stricter after actuator fault occurrence. The proposed approach is illustrated by a flight control application.

The quality of model-based FDI/FTC heavily relies on the ability of the model considered to describe the actual behavior of the system to be monitored. The use of linear models being limited, research has been directed towards the use of nonlinear models. Although they are generally more difficult to handle, certain classes of nonlinear models are suitable for the implementation of methods developed in the context of linear models. It is particularly the case for Linear Parameter Varying (LPV) and Takagi-Sugeno (T-S) models. The paper by R.J. Patton, L. Chen and S. Klinkhieo proposes to combine a robust fault estimator based on an LPV model within an adaptive FTC fault compensation system. This approach is particularly suitable for mechanical/mechatronic systems with friction phenomena. In that case, the friction forces, regarded as actuator faults, are estimated and their effect is compensated within a polytope controller system, yielding a robust form of active FTC that is easy to apply. The proposed design strategy is illustrated using a nonlinear two-link manipulator system with friction forces acting simultaneously at each joint. The paper by S. Montes de Oca, V. Puig, M. Witczak and Ł. Dziekan also uses polytopic LPV techniques to design an actuator fault tolerant controller. The proposed approach implements an unknown input observer and a state feedback controller. Its performance is assessed on a laboratory model experiment with a two degree of freedom helicopter. Fault diagnosis and fault tolerant control methods can also play an important role in improving the performances of road vehicles. The paper by P. Gáspár, Z. Szabó and J. Bokor presents a supervisory decentralized architecture for the design and development of reconfigurable and fault-tolerant control systems in road vehicles. The proposed design is based on an LPV method that uses monitored scheduling variables during the operation of the vehicle.

Two papers of this issue describe systems with nonlinear behavior using Takagi-Sugeno models. The first one, by D. Xu, B. Jiang and P. Shi, deals with the problem of actuator fault estimation. A robust sliding mode observer is designed based on a T-S model, and an inverse system method is used to estimate the actuator fault. In the same context, the second paper, by D. Ichalal, B. Marx, J. Ragot and D. Maquin, proposes actuator fault tolerant control. The suggested methods require simultaneous estimation of the system state and actuator fault. To this end, two methods are proposed: the first one extends to the nonlinear case a previously developed adaptive fast state and fault observer, while the second implements a proportional integral observer. Academic simulation examples illustrate these approaches.

The model predictive control method, which consists in solving on-line a finite horizon open-loop optimal control problem subject to system dynamics and constraints involving states and controls, has demonstrated its efficiency in a very wide range of applications. Naturally, this approach has been investigated in the FDI/FTC framework. The paper by A. Yetendje, M.M. Seron and J.A. De Doná exploits this method to design a fault tolerant output feedback controller that ensures robust closed-loop exponential stability and good performance in the fault-free case and under the occurrence of abrupt sensor faults. Similarly, K. Patan and J. Korbicz propose the implementation of a predictive controller by means of a recurrent neural network which acts as a one-step ahead predictor. Based on the knowledge of a priori faulty scenarios, a fault detection and compensation module is designed using that predictor. The proposed strategy is applied to a boiler unit.

We believe that this special issue gives a valuable overview of actual results in the fault diagnosis and fault tolerance field and will encourage the development of enhanced theories and applications. Finally, we would like to thank all the authors and reviewers who contributed to this issue. March 2012 Józef Korbicz Institute of Control and Computation Engineering University of Zielona Góra, Poland Didier Maquin Didier Theilliol Research Center for Automatic Control of Nancy (CRAN) University of Lorraine, France

Józef Korbicz has been a full-rank professor of automatic control at the University of Zielona Góra, Poland, since 1994, and a corresponding member of the Polish Academy of Sciences since 2007. He currently heads the Institute of Control and Computation Engineering of his home university. His research interests include computational intelligence, fault detection and isolation, and control theory. The primary aim of his research group is to contribute to the diagnosis of dynamical systems. He has published more than 360 technical papers, 58 of which in international journals. He is a co-author of eight monographs and textbooks and a co-editor of four books, e.g., Fault Diagnosis. Models, Artificial Intelligence, Applications (Springer-Verlag, 2004) andModeling, Diagnostics andProcess Control