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

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

Experimental Analysis of the Tardiness of Parallel Tasks in Soft Real-time Systems

Keywords: parallelism, stretching techniques, real-time systems, soft real-time systems, scheduling simulation, global earliest deadline first

A parallel application is defined as the application that can be executed on multiple processors simultaneously. In software, parallelism is a useful programming technique to take advantage of the hardware advancement in processors manufacturing nowadays. In real-time systems, where tasks have to respect certain timing constraints during execution, a single task has a shorter response time when executed in parallel than the sequential execution. However, the same cannot be trivially applied to a set of parallel tasks (taskset) sharing the same processing platform, and there is a negative intuition regarding parallelism in realtime systems. In this work, we are interested in analyzing this statement and providing an experimental analysis regarding the effect of parallelism soft on real-time systems. By performing an extensive simulation of the scheduling process of parallel taskset on multiprocessor systems using a known scheduling algorithm called the global Earliest-Deadline First (gEDF), we aim at providing an indication about the effects (positive or negative) of parallelism in real-time scheduling.

Introduction

Uniprocessor platforms have been widely used in computer systems and applications for a long time. However, making processors smaller and faster has become more challenging for manufacturers recently due to the physical constraints such as heating and power problems. As a result, manufacturers are moving toward building multicore and multiprocessor systems so as to overcome these physical constrains. In the last few years, we have witnessed a dramatic increase in the number of cores in computational systems, such as the 72-core processor of the TILE-Gx family from Tilera, and the 192-core processor released by ClearSpeed in 2008.

Unfortunately, there is a gap between the advancement in software and hardware, and most of the currently used applications are still designed to target uniprocessor systems as execution platforms [START_REF]Mixed criticality systems[END_REF]. In order to get full advantage of multicore and multiprocessor systems, parallel programming has been employed so as to perform computations and calculations simultaneously on multiple processors. Lately, it 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. Usually, these programs are harder to be written than the sequential ones, and they consist of dependent parts. However, global scheduling, in which the scheduler can execute any job on any available processor at any time instant, is more suitable for parallel programs than partitioned scheduling (in which jobs are assigned first to individual processors and are forced to execute without processor migration).

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 [3]. Except these are not designed normally for real-time systems. In embedded systems, software usually is subjected to certain timing constraints, such as operational deadlines and the frequency of job arrivals. These constraints affect the correctness of its results along with the correctness of the calculations, and these systems are referred to as real-time systems.

Based on the criticality of the timing constraints, real-time systems are classified as either hard or soft. In hard real-time systems, the consequences of deadline misses can cause catastrophic effects, while soft real-time systems can tolerate delays in the execution of tasks, and a deadline miss only degrades the quality of service provided by the application. Avionic and transportation systems are examples of hard real-time systems, while communication and media systems (such as in video surveillance) are considered as soft real-time systems.

In real-time systems, many researches focused on the sequential task model in the case of multiprocessor systems [START_REF] Davis | A survey of hard real-time scheduling algorithms and schedulability analysis techniques for multiprocessor systems[END_REF]. In comparison, Few studies are conducted on the different models of parallel tasks, such as the multi-threaded segment and the Directed Acyclic Graph (DAG) model [START_REF] Saifullah | Real-Time Scheduling of Parallel Tasks under a General DAG Model[END_REF][START_REF] Baruah | A generalized parallel task model for recurrent real-time processes[END_REF]. Mainly, a parallel task model is divided into three categories:

-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 (this is the model we consider in this paper), -malleable if the number of processors can be changed by the scheduler during execution.

In real-time systems, it has been believed that parallelism has negative effect on the schedulability of tasksets, as it has been stated in [START_REF] Lakshmanan | Scheduling Parallel Real-Time Tasks on Multi-core Processors[END_REF]. In that paper, the authors proposed to stretch the parallel tasks of the Fork-join model 1 as a way to avoid parallelism, and their results encourage the execution of parallel tasks as sequentially as possible. The reason why this was possible is that fork-join tasks have schedulable utilization bounds slightly greater than and arbitrarily close to uniprocessors 2 .

In this work, we aim at providing a basic intuition regarding the validity of this assumption, and we will study the effect of parallelism on the scheduling of tasksets on multiprocessor soft real-time systems. We use experimental analyses through extensive simulations as an indication tool towards our purpose. By choosing soft real-time systems, we can measure the performance of parallel tasks by calculating the tardiness of their jobs (how many time units a job needs after its deadline to complete its execution) in such systems when executed in parallel and sequentially, without worrying about the catastrophic effects of not respecting the timing constraints. To the best of our knowledge, we are not aware of similar researches or studies done regarding this assumption.

The structure of this paper is denoted as follows: Section 2 describes our parallel task model which is used in this paper, and it also includes two stretching transformations we propose in order to execute parallel tasks as sequentially as possible. These transformations are necessary as comparison references to the parallel execution. Then Section 3 contains a description about soft real-time systems and some details and discussion about an upper bound of tardiness found in literature. The contributions of this paper are included in Section 4, which provides a description about the simulation process used in this work, and the analysis of the conducted results. Finally, we conclude this paper by Section 5 which includes future work as well.

2 System model and its transformations

Parallel Task Model

In this work, we consider a taskset τ that consists of n parallel sporadic implicitdeadline real-time tasks on a platform of m identical processors. Each task τ i , where 1 ≤ i ≤ n, is a parallel task that consists of a number of identical sequential threads, and it is characterized by (n i , C i , T i ), where n i is the count of the threads belong to τ i that can execute in parallel, C i is the worst-case execution time (WCET) of τ i which equals to the total WCET of its threads, and T i is the minimum inter-arrival time (or simply the period) between successive jobs of the task, which defines the sporadic task. As in an implicit-deadline task, the deadline D i of task τ i , which is defined as the time interval in which τ i has to complete its execution, is equal to the period of the task.

Let τ i,j denote the j th thread of τ i , where 1 ≤ j ≤ n i . All the threads of the same task share the same period and deadline of their task. Let C i,j be the WCET of thread τ i,j , where C i = ni j=1 C i,j . In this paper, we consider identical threads, however, the model can be generalized more by allowing non-identical threads. 2 The remark regarding the utilization of Fork-join tasks is quoted from [START_REF] Lakshmanan | Scheduling Parallel Real-Time Tasks on Multi-core Processors[END_REF] the utilization of thread τ i,j is defined as U i,j = Ci,j Ti , and the utilization of the parallel task τ i is defined as

U i = C i T i = ni j=1 U i,j .
An example of our considered parallel task is shown in Figure 1(a), in which task τ i consists of 8 threads and has a deadline and a period equal to 11. In real-time systems, a scheduling algorithm is defined as the algorithm that assigns priorities to the active jobs in the system, and it chooses which jobs can execute on the available processors at time t. If active jobs are authorized to migrate between processors, which means that a job can start its execution on one processor and then continue on another, then the scheduling algorithm is called global. In multiprocessor systems, few optimal algorithms 3 exist for global scheduling of tasksets. These algorithms suffer usually from high overhead costs consist of large number of jobs migrations and preemptions. However, there exist non-optimal algorithms that have good performance with lower costs such as the global earliest deadline first (gEDF), which we will use in this paper. The gEDF algorithm assigns the highest priority to the job with the earliest absolute deadline. It belongs to the fixed job priority family, in which the priority of the job is fixed during its execution but jobs of the same task have different priorities. Also we consider a preemptive scheduling, in which a higher priority job can interrupt the execution of a lower priority job, and the interrupted job can start its execution on a different processor.

Based on the categories of the parallel tasks in real-time systems, our considered parallel task model rigid w.r.t. the number of threads. A given task τ i consists of n i parallel threads is defined by the model. However, the execution behavior of the task depends on the number of available processors and the scheduling algorithm, and it is not obligatory to execute all the parallel threads together. So, these threads can execute either in parallel or sequentially based on the decisions of the scheduler. When a job is activated at time t, all the n i parallel threads are activated as well. But if there exist less than n i available processors at time t, then the scheduler executes partial set of the threads in parallel while the rest are executed later.

In this paper, we considered a simplified task model of parallelism, in order to better show the effect of parallelism on the scheduling of soft real-time systems. Our task model can be considered as a Fork-join task model, in which each task consists of one parallel segment, and the costs of fork and join events of the threads are included in the execution time of each thread. In the future, we aim to extend the work to include more realistic parallel task models such as the the multi-threaded task model and the Directed Acyclic Graphs (DAGs).

Stretching Parallel Tasks

In order to provide an analysis of the effect of parallelism on the scheduling of soft real-time systems, we will study the scheduling of a parallel taskset τ when executing on m identical processors using gEDF scheduling algorithm while considering some execution scenarios, that vary from parallel execution to sequential execution. As we described earlier in Section 2.1, the threads of a parallel task can execute either in parallel or sequentially based on the availability of processors and on the decisions of the chosen scheduling algorithm.

Hence, each parallel task τ i in taskset τ can execute based on the following execution scenarios:

-the Parallel Scenario: all the threads τ i execute in parallel, and they are activated at the same activation time of their parallel task τ i (please refer to Figure 1(a)), -the Fully-Stretched Scenario: all the threads of τ i execute as sequentially as possible, and τ i is transformed into a set of fully stretched threads and a thread is broken into at most two pieces which execute in parallel, while the stretched threads can be assigned dedicated processors (please refer to Figure 1(c)). A straight-froward transformation is provided in the following section in order to fully stretch the parallel threads. -the Partially-Stretched Scenario: all the threads of τ i execute as sequentially as possible, without causing interruptions and migrations due to transfor-mation (please refer to Figure 1(b)). This transformation will be explained in more details in the following section.

The example of the proposed execution scenarios in Figure 1 might seem unclear now. We invite the reader to consult the following detailed sections regarding the execution scenarios while referring to the example in Figure 1.

The Parallel Scenario:

The Parallel scenario represents the default execution behavior of our parallel task model. According to this scenario, the threads of each parallel task are activated by the activation event of the original task, and they have its deadline and minimum arrival time between the jobs. Hence, all the threads have the same priority according to gEDF, and they have the same utilization. So, the scheduling of the parallel tasks on m identical processors can be treated as the scheduling problem of a taskset of (n i , ∀τ i ∈ τ ) sequential sporadic implicitdeadline threads. An example of the parallel scenario is shown in Inset 1(a), in which each thread of task τ i has a worst-case execution time of 4 and a deadline equal to 11.

However, the maximum tardiness of a parallel task is determined by the maximum tardiness of all of its threads among all possible scenarios of jobs' activation.

Fully-Stretched Scenario:

The purpose of the Fully-Stretched transformation is to avoid the parallelism within the tasks when possible, by executing them as sequentially as possible. So, instead of activating all the parallel threads of a certain task at the same time (as in the Parallel scenario), this transformation determines which threads are activated in parallel and which are delayed to be executed sequentially. The objective is to transform the majority of the parallel threads of each task into fully-stretched threads which have a WCET equals to the period (utilization equals to 1). As a result, we can dedicate an entire processor for each transformed thread, which will guarantee their scheduling by the use of partitioned scheduling (tasks are assigned to a processor have to execute on this processor without authorizing migrations). Hence, the rest of the threads (not fully stretched) are the ones to be scheduled using gEDF, which will reduce their tardiness.

The Fully-Stretched Transformation is straight forward due to the simplicity of the considered parallel model. Let us consider a parallel task τ i which consists of n i threads and each thread τ i,j has a WCET of C i,j . The Fully-Stretched transformation will generate the following sets of modified threads τ ′ i,j : -A set of fully-stretched threads τ ′ stretch : which consists of ⌊U i ⌋ threads each has a total WCET equals to the original period, and utilization U ′ i,j = 1, where τ ′ i,j ∈ τ ′ stretched . If the capacity of the processor cannot contain entire threads (i.e. Ti Ci,j is not an integer), then a thread will be forced to execute on 2 processors in order to fill the first one. As a result, the transformation will cause at most ⌊U i ⌋ threads to migrate between processors.

-When the utilization of the parallel task is not integer, then there exist a set of threads that cannot fill an entire processor. Let the total remaining execution time be denoted as C rem = (U i -⌊U i ⌋) * T i . The remaining threads are divided into the following two types:

• At most, one implicit-deadline thread τ ′ imp from each transformed parallel task is generated. This thread is created by merging the remaining threads that did not fit into the stretched tasks without the thread that is used to partially fill the last processor. The WCET of τ ′ imp is calculated as C imp = (⌊ Crem Ci,j ⌋ * C i,j ), and it has a deadline and period equal to the original parallel task τ i .

• At most one constrained deadline4 thread τ ′ cd is generated, which has a WCET calculated as C cd = C rem -C imp . Its period is the same as the original task τ i , and it has a deadline calculated as

D cd = (D i - (C i,j -C cd )
). This thread contains the remaining execution time of the thread that had to fill the last stretched processor. The conversion from an implicit-deadline thread into a constrained deadline one is necessary to prevent the sequential thread from executing in parallel since its execution is divided between two processors.

Back to the example in Figure 1, Inset 1(c) shows an example of the Fully-Stretched transformation when applied on task τ i shown in Inset 1(a). As shown in the figure, the original task consists of 8 threads each has a WCET equals to 4 and a deadline equals to 11. After transformation, the fully-stretched tasks τ ′ stretch contains two threads. The first consists of threads τ i,1 , τ ′ i,2 and the ending part of τ i,3 . While the second task consists of the beginning part of the τ i,3 (complementary to the part in the previous task), threads τ i,4 , τ i,5 and the ending part of thread τ i,6 . The remaining execution time of thread τ i,6 forms the constrained deadline independent thread τ ′ cd , with a deadline D i,6 = 9 as shown in the figure. Threads τ i,7 and τ i,8 are merged together, in order to form a single implicit-deadline task with a WCET equals to 8 and a deadline equals to 11.

The advantage of the Fully-Stretched Transformation is that, at most, two threads (τ ′ imp and τ ′ cd ) are scheduled using gEDF, and they are the ones that may cause a tardiness during the scheduling process. While the rest of the generated threads ({τ ′ stretch }) are scheduled using partitioned scheduling algorithms, and they are guaranteed to respect their deadline each on a single processor independently.

Partially-Stretched Scenario:

A modification to the Fully-Stretched transformation can be proposed so as to avoid the thread migrations between processors. In this transformation, we authorize the parallel threads to be stretched up to the maximum possible threadcapacity of a processor, which can be at most the deadline of the parallel task. Let x denote the thread-capacity of a particular processor (all identical processors have the same value), which is calculated as x = ⌊ Di Ci,j ⌋. This means that each processor can contain at most x complete threads executing sequentially. The result of the transformation is a set of ⌊ Ci x ⌋ implicit-deadline threads each has a WCET equals to (x * C i,j ). Also, at most on implicit-deadline thread which has a WCET equals to (C i -((x * C i,j ) * ⌊ Ci

x ⌋)). The resulted threads are scheduled using gEDF on m identical multiprocessors. As shown in the example in Figure 1, parallel task τ i from Inset 1(a) is transformed using the Partially-Stretched Transformation, and the result is shown in Inset 1(b). The processor capacity of task τ i is equal to 2, and the result of transformation is 4 sequential implicit-deadline threads characterized by [START_REF] Ha | Validating timing constraints in multiprocessor and distributed real-time systems[END_REF][START_REF] Valente | An upper bound to the lateness of soft real-time tasks scheduled by edf on multiprocessors[END_REF][START_REF] Valente | An upper bound to the lateness of soft real-time tasks scheduled by edf on multiprocessors[END_REF]. It is clear that the Partially-Stretched transformation does not force any threads to migrate prior to the scheduling process, and this is the advantage of this transformation over the Fully-Stretched Transformation.

The worst-case execution time of a task is a pessimist value, and usually the jobs do not execute up to this value. In the case of a global work-conserving scheduling algorithm, when a job finishes its execution earlier than expected by the WCET, then the scheduler will not allow to leave a processor idle while there are active jobs ready to execute, and it will allow an active job to be released earlier. In the case of partitioned scheduling, the scheduling algorithm assigns tasks to processors, and then migration between processors is not allowed. Hence, if a job finishes its execution earlier than expected and there are no active jobs waiting on this processor, the processor will stay idle even of there are active jobs waiting on the other processors. Also, it had been proved in [START_REF] Ha | Validating timing constraints in multiprocessor and distributed real-time systems[END_REF] that fixed job priority algorithms (which include gEDF) are predictable, i.e. a schedulable taskset is guaranteed to stay schedulable when one or more of its tasks execute for less than its worst-case execution time. This property is another advantage of global scheduling over partitioned scheduling. We can conclude that the Parallel and Partially-Stretched scenarios, which use gEDF to schedule all the threads of the taskset, behave better than the Fully-Stretched scenario (which uses partitioned scheduling for most of the executed tasks) in the case of lower execution time of jobs. Hence, the processors will be efficiently used.

Advantage of stretching over parallelism in real-time systems:

The scheduling of real-time tasksets on multiprocessor systems is more complicated than the uniprocessor systems. A famous problem had been shown in [START_REF] Dhall | On a Real-Time Scheduling Problem[END_REF] called the Dhall effect, in which a low utilization taskset can be non-schedulable regardless of the number of processors in the platform. Later, it had been proved in [START_REF] Phillips | Optimal time-critical scheduling via resource augmentation (extended abstract)[END_REF] that this problem happens when a low utilization taskset contains a high utilization task. We will show using an example, that this problem happens in the case of the Parallel Scenario, while the stretching scenarios solves it. The used example is inspired from [START_REF] Phillips | Optimal time-critical scheduling via resource augmentation (extended abstract)[END_REF].

Let us consider a taskset τ that consists of 2 tasks that executes on 3 unitspeed processors (m = 3). The first task τ 1 has a deadline equal to 1, and it consists of 3 threads each has a WCET equals to 2ǫ, where ǫ is slightly greater (a) Parallel Scenario: All the threads of the task τ1, which have the highest priority according to gEDF, execute on all 3 processors. While the highest utilization task τ2 is delayed and hence it misses its deadline. than zero. The second task τ 2 has a deadline equals to 1 + ǫ, and it has a single thread with WCET equals to 1. The utilization of each task is calculated as U 1 = 2mǫ and U 2 = 1 1+ǫ . Hence, the total system's utilization approaches to 1 since ǫ → 0. The taskset is shown in Figure 2.

When gEDF is used, at time t = 0, the first job of task τ 1 has a higher priority than the job of task τ 2 , because it has an earlier absolute deadline. All the threads of τ 1 have the same priority of τ 1 , and according to the Parallel Scenario, they will execute in parallel and they will occupy all the available processors in the systems. At time t = 2ǫ, the threads finish their execution, and then task τ 2 can start its own. Unfortunately, task τ 2 misses its deadline. The scenario is shown in Inset 2(a). However, when a stretching scenario is used (either fully-stretched or partiallystretched transformation has the same result), the parallel threads of the low utilization task will be forced to execute sequentially and hence they will occupy lower number of processors. As a result, the higher utilization task (τ 2 in the example) will start its execution earlier and it will respect its deadline. Inset 2(b) shows the effect of stretching on the Dhall effect problem, and how it solved it.

The effect of parallelism on the tardiness of Soft real-time systems

In soft real-time systems, a deadline miss during the scheduling process of a taskset does not have catastrophic effects on the correctness of the system as in hard real-time systems. However, a deadline miss of a task will reduce the quality of service (QoS) provided by the application. So, in order to keep the QoS at an acceptable rate and better analyze it, it is necessary to determine an upper bound of tardiness for each task in a system regarding a specific scheduling algorithm.

A tardiness of a job in real-time systems is defined as its delay time, i.e. the time difference between the deadline and the actual finish time of this job. For a real-time task that generates a number of jobs, the tardiness of one job has a cascaded effect on the successor jobs, since the next jobs have to wait for the delayed one to finish its execution before they can start their own execution, which means that they will be delayed as well. The tardiness of a task is defined as the maximum tardiness among its generated jobs. Fig. 3. An example (from [START_REF] Valente | An upper bound to the lateness of soft real-time tasks scheduled by edf on multiprocessors[END_REF]) shows the tardiness of tasks during the scheduling of a taskset consists of 4 tasks on 3 identical processors using gEDF.

Few researches have been done regarding the problem of identifying an upper bound to the tardiness of sporadic sequential implicit-deadline tasks on multiprocessors when global EDF is used, such as in [START_REF] Valente | An upper bound to the lateness of soft real-time tasks scheduled by edf on multiprocessors[END_REF] 5 . In [START_REF] Devi | Soft Real-Time Scheduling on Multiprocessors[END_REF], an upper bound of tardiness under preemptive and non-preemptive global EDF is proved. In this work, we intend to present the latter tardiness bound in the case of preemptive gEDF and discuss its usefulness in the calculations of tardiness in the case of parallel tasks. In the future, we aim at calculating an adapted upper bound for parallel tasks.

For the sake of explaining the upper bound of tardiness from [START_REF] Devi | Soft Real-Time Scheduling on Multiprocessors[END_REF], Consider that τ is a sporadic taskset that is scheduled using gEDF on m identical proces-sors. Each task τ k ∈ τ is a sequential implicit-deadline task that has a WCET C k and a deadline D k (equal to minimum arrival time or period). The upper bound of tardiness of each task in τ is given in the following theorem: Theorem 1 (from [START_REF] Devi | Soft Real-Time Scheduling on Multiprocessors[END_REF]). Global EDF (gEDF) ensures a tardiness bound of

Λ i=1 ε i -C min m - Λ-1 i=1 µ i + C k (1)
to every sequential task τ k of a sporadic implicit-deadline task system τ with U sum ≤ m, where: ε i (resp. µ i ) denotes the i th execution cost (resp. task utilization) in non-increasing order of the execution costs (resp. utilization) of all the tasks.

Λ = U sum -1, U sum is integral ⌊U sum ⌋, otherwise (2)
The detailed proof of Theorem 1 can be found in [START_REF] Devi | Soft Real-Time Scheduling on Multiprocessors[END_REF]. The used approach is based on comparing the processors allocations using gEDF with a concrete task system in a processor sharing 6 .

As we can notice from Equation 1, the tardiness is calculated as the worstcase execution time of each task plus a fixed value w.r.t. the global parameters of the taskset. By analyzing this bound, we conclude that the tardiness of a taskset is reduced if, at least, one of the following is applied:

-a decrease in the value of the highest WCET and utilization of the tasks in the set (ε and µ), -an increase in the WCET of tasks in τ (C min ), -an increase in the number of processors, -a decrease in the total utilization of the taskset (U sum ) which affects the value of Λ from Equation 2.

In our parallelism model described in Section 2, a thread in a parallel task is considered as a sequential task. Hence, we can apply theorem 1 on each thread τ i,j ∈ τ i ∈ τ individually. The tardiness of a job of a parallel task is the maximum tardiness among its threads, and then the tardiness of a parallel task is the maximum tardiness among its jobs.

It is worth noticing that the upper bound of tardiness is computed for sporadic implicit-deadline tasks, while the fully-stretched transformation generates at most two threads that scheduled using gEDF and may be delayed, which are τ ′ cd and τ ′ imp . As a solution to this problem, and in order to use the tardiness bound from Theorem 1, we propose a modification to the constrained deadline threads τ ′ cd to be be executing completely using gEDF, and it is converted to implicit-deadline threads. An example of this modification is shown in the example in Figure 1(d).

Let the tardiness of a parallel task τ k ∈ τ be denoted by x k when it executes in the parallel scenario described above (all threads are activated in parallel). If task τ k is partially stretched, then the threads of the parallel tasks will be stretched which will increase the utilization and execution time of threads. On another hand, the number of threads to be scheduled using gEDF is reduced on m processors. So, after the partially-stretched scenario, the values of C min , ε and µ will increase. Also, when task τ k is fully-stretched, the resulted fully-stretched threads (their utilization equals to 1) will be assigned dedicated processors, and at most 2 threads from each parallel task will be scheduled using gEDF only. As a result, the total utilization of the taskset τ will be reduced and also the number of processors on which gEDF algorithm is used, in addition to the effects of the partially-stretched scenario. The stretching scenarios have the advantage of reducing the number of threads that may cause a tardiness due to deadline misses when compared to the parallel scenario. Hence, the tardiness of the parallel tasks will be reduced as a result.

Based on these effects, we can conclude that the tardiness bound of parallel tasks is not comparable with the bound after stretching. Because stretching scenarios change the taskset in a way that can increase and decrease the tardiness bound at the same time. Hence, the theoretical tardiness bound of Theorem 1 cannot determine the performance of parallel and stretched tasks in the scheduling problem using gEDF, and it cannot be used as an indication to the performance of parallelism in real-time systems. As a result, we will use experimental analysis to simulate the scheduling of the different scenarios of parallel task execution and to give us an indication on the performance.

Experimental Analysis

In this section, we show the simulation results of the experiments conducted using randomly-generated tasksets to evaluate the performance of parallel execution in comparison with the stretching execution scenarios described in Section 2. The results are obtained by simulating the scheduling of a large number of parallel tasksets with different utilization on a platform of 16 identical processors when global EDF is used.

The simulation process is based on an event-triggered scheduling. This means that at each event in the interval [0, 3 * H), where H denotes the hyper period of the scheduled taskset τ and is defined as the least common multiple of periods, the scheduler is awakened and it decides which jobs have the highest priorities to execute on the available processors. According to EDF, the job with the earliest absolute deadline has the highest priority. We consider that a parallel job is blocked either by the execution of a higher priority thread or by an earlier job that has been delayed. During the simulation process, we calculate the tardiness of each job of parallel tasks, in order to calculate the average tardiness of tasks in the set, while varying three parameters: the execution behavior of parallel tasks (either Parallel "Par", Fully-Stretched "F-Str" or Partially-Stretched "P-Str"), the utilization of tasks within each taskset (either High "Hi" or Low "Lo"), this is done by varying the number of tasks of each taskset, and finally the number of parallel threads within each parallel task (maximum of 3 or 10 threads/task).

We used a simulation tool called YARTISS [START_REF]YaRTISS simulation tool[END_REF], which is a multiprocessor real-time scheduling simulator developed by our research team. It contains many scheduling algorithms and task models (including parallel tasks), and it can be used easily for both hard and soft real-time systems.

For each system utilization from 1 to 16, we generated 50, 000 tasksets randomly. The number of parallel tasks within each taskset is varied from 3 to 12 tasks/taskset. This variation affects the structure of tasks because, for a fixed utilization, increasing the number of tasks means that the taskset's utilization will be distributed on a larger number of tasks, which will lower the average utilization of tasks within the taskset. Also, we can control the percentage of parallelism within a taskset by varying the number of parallel threads of each task during task generation. This can help in analyzing the effect of parallelism on scheduling as we will see below.

Regarding the generation of parallel tasksets, our task generator is based on the Uunifast-Discard algorithm [START_REF] Davis | Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems[END_REF] for random generation of tasks. This algorithm is proposed by Davis and Burns to generate randomly a set of tasks of a certain total utilization on multiprocessor systems. The number of tasks and their utilization are inputs of this algorithm. The taskset generator is described briefly as follows:

-The algorithm takes two parameters n and U , where n is the number of parallel tasks in the set and U is the total utilization of the taskset (U > 0). -The Uunifast-Discard algorithm distributes the total utilization on the taskset.

A parallel task τ i can have a utilization U i greater than 1 which means that its threads cannot be stretched completely, and it has to execute in parallel. -The number of threads and their WCET of each parallel tasks are generated randomly based on the utilization of the tasks. The maximum number of threads is fixed to be either 3 or 10 threads per parallel task.

In order to limit the simulation interval and reduce the time needed to perform the simulation, which is based on the length of the hyper period of each taskset, we used the limitation method proposed in [START_REF] Goossens | Limitation of the Hyper-Period in Real-Time Periodic Task Set Generation[END_REF], which relays on using a considerate choice of periods of the tasks while generation so as to reduce their least common multiple. Using this method, we implemented our task generator to choose periods of tasks in the interval [START_REF]Mixed criticality systems[END_REF]25200].

Analysis of experimental results

For each taskset, the average of the maximum tardiness of all tasks is computed. The results are showed in Figure 4 Fig. 4. Simulation results of average tardiness of parallel tasks by varying their execution behavior (Parallel "Par", Full-stretch "F-Str" and Partially-stretch "P-Str"), the utilization of tasks within tasksets (high "Hi" and Low "Lo") and the maximum number of threads within each parallel task (either 3 or 10 threads/task).

the comparison of average tardiness of tasksets for the three types of execution behaviors, while Inset 4(b) focuses on the comparison betzeen the parallel and the fully-stretched execution behavior.

The average tardiness is calculated by considering the schedulable tasks (their tardiness equal to zero), so as to give us an indication on the number of deadline misses happened during simulation. Moreover, the x-axis of the insets of Figure 4 represents the utilization of the scheduled tasksets (from 1 to 16 on a system of 16 identical processors), while the y-axis represents the average tardiness of the tasksets.

The rest of this section discusses the results in details.

The effect of utilization of tasksets on tardiness.

Referring to Figure 4, most of the tasksets have negligible tardiness when tasksets have utilization less than 4. Then the tardiness increases differently (based on the used scenario) for higher utilization. These results are quite logical, since the number of processors in the simulation is always considered to be m = 16. Hence, lower utilization tasksets mean lower execution demand from processors which increases schedulability and reduces deadline misses. Starting from U taskset > 4, we can notice an increase in tardiness for the average tardiness values which varies based on the execution scenario.

However, we can conclude by looking at these results, and specially when U taskset = 16, that the partially-stretched transformation has always the highest tardiness values when it is compared with the other two execution scenarios (parallel and fully-stretched) with the same parameters. As a result, the partiallystretched scenario can be seen as the least appealing execution scenario from the schedulability point of view. This is expected since the partially-stretched transformation delays the execution of part of the parallel threads of a task so as to execute sequentially. This is done even if there are available processors for them to execute earlier than the defined activation time specified by the transformation. In Figure 4(a), the partially-stretched scenario (P-Str) has the highest tardiness in both groups (high and low utilization) when the number of threads of each parallel task has a maximum of 10 threads.

The performance of the other two scenarios (parallel and fully-stretched) is not comparable at this point, and they are affected by the utilization of parallel tasks and the number of threads in each task, and this will be discussed in the next paragraph.

The effect of the number of tasks per taskset on tardiness. The difference between the parallel and the fully-stretched execution scenarios of parallel tasks is shown in Figure 4(b). Since the Uunifast-Discard algorithm that we used for generating tasksets divides the total utilization of taskset on the number of tasks per taskset, varying the number of tasks while fixing the system's utilization will vary the utilization assigned for each task. In our parallel task generator, the maximum possible number of threads depends on the total execution time of the task (respectively, its utilization). So, lowering the task utilization means a lower execution time which increases the probability of generating tasks with low number of parallel threads. We can notice that the highest tardiness of tasksets is caused from the high-utilization tasksets executed using the parallel execution scenario (Par-Hi in Figure 4(b)), while their respective tasksets executing using the fully-stretched scenario (F-Str in Figure 4(b)) have the lowest tardiness, regardless of the number of parallel threads within each task.

Regarding the low-utilization tasks, we can notice that the tardiness of the tasksets depends on the number of parallel threads within each task. As shown in Figure 4(b), the fully-stretched tasksets whose tasks consist of 3 threads (F-Str-Lo-3) have lower but relatively close tardiness than the parallel scenario (Par-Lo-3). However, the parallel executing tasksets whose tasks consist of 10 threads (Par-Lo-10) are behaving better than the fully-stretched scenario (F-Str-Lo-10).

In this case, the scheduling of the parallel scenario is clearly better than the fully-stretched scenario as shown in Figure 4(b). This can be explained by noticing that in this case the number of parallel threads in a task is high while its utilization is low. Since the threads inherit the deadline and period of their original task, then the threads have low utilization as well. The parallel scenario gives the scheduling algorithm more freedom in scheduling the parallel threads, by activating them all at the same time, and choosing their execution order based on the availability of processors. While the fully-stretched scenario forces the parallel tasks to execute sequentially even if this approach is not workconserving and it might cause delays in the scheduling process.

From the results conducted by simulation, we have now an experimental indication on the effect of parallelism on the scheduling of real-time systems. It is possible now to overrule the typical assumption that parallelism has always negative effects on scheduling. As we have shown above, the parallel scheduling is better than its sequential alternatives when tasks have low number of parallel threads. According to this, the scheduler can get better scheduling decisions while parallelizing the execution of certain tasks on multiple processors than the sequential execution. This result matches the motivation of parallelism and its practical uses in non-real time systems.

Conclusion

In this paper, we were interested in studying the effect of parallelism in real-time systems. The problem is summarized as the scheduling of sporadic implicitdeadline parallel tasks on multiprocessors using global earliest deadline first (gEDF) as scheduling algorithm. The parallel tasks are either executed in a parallel scenario in which all the threads of the parallel tasks execute in parallel as soon as possible, or in a stretching scenario, in which the threads are executed as sequentially as possible. We proposed two stretching scenarios based on the number of thread migrations and preemptions required by the transformation: partially and fully stretched. In the latter, threads are stretched to form transformed threads with utilization equal to 1, but it requires higher number of migrations and preemptions between processors and jobs.

Using extensive simulation, we showed that parallelism did not cause major negative effects on the scheduling of real-time systems. Admitting that sequential execution of tasks has better results in general than parallelism, There are certain cases where parallelism behaves better and has lower tardiness values than stretching. Based on these remarks and results, we can overrule the common assumption in real-time systems against parallelism, and that tries to avoid parallel structure in order to get better scheduling results.

In the future, we aim at extending our work, and provide theoretical analyses to support our experimental results, by providing an upper bound of tardiness adapted to parallel real-time tasks on multiprocessor systems. Also, we are looking forward to analyze scheduling algorithms other than gEDF algorithm that we used in this paper. Based on this, we can classify the common scheduling algorithms in real-time systems based on their ability to schedule parallel tasks with low tardiness bounds.

Finally, we at generalizing our task model of parallel tasks, so as to include more complicated structures of parallel threads, such as the multi-threaded segment model and the Directed Acyclic Graphs. Such task models are used to represent practical parallel programming APIs.

  (a) All the threads of task τi execute in parallel.(b) The threads of task τi execute as sequentially as possible without any migrations or preemptions due to transformation.(c) All the threads of task τi execute as sequentially as possible. At most one constrained-deadline thread results.(d) The transformation in Subfigure 1(c) is modified so as to get rid of the constrained-deadline thread.

Fig. 1 .

 1 Fig. 1. An example of a parallel task τi that consists of 8 threads and it has a deadline and period equal to 11. The rectangles represent the threads of the task, and the numbers within them indicate their indexes.

  (b) Stretched Scenario: Parallel threads of task τ1 are executed as sequentially as possible. Then, task τ2 have the chance to execute at time 0.

Fig. 2 .

 2 Fig. 2. An example shows how stretching a parallel task helps in solving the Dhall effect problem.

  , which consists of 2 insets. Inset 4(a) shows -Hi-10 F-Str-Hi-10 (a) Comparison of the average tardiness of taskset when executing on m = 16 using all execution scenarios for parallel tasks. -Hi-10 (b) Comparison of the average tardiness of taskset when executing on m = 16 focusing on the parallel and the Full-stretch execution scenarios.

A fork-join model is parallel task model in which the incoming jobs are split on arrival for service by numerous processors and joined before departure. It is the base of the OpenMP parallel programming API.

An optimal algorithm is the one that can schedule successfully any feasible taskset. If the optimal algorithm fails in scheduling a taskset, then no other algorithm can schedule it.

A constrained deadline real-time task has a deadline no more than its period.

In[START_REF]An upper bound to the lateness of soft real-time tasks scheduled by EDF on multiprocessors[END_REF], the authors mentioned that a proof published in[START_REF] Valente | An upper bound to the lateness of soft real-time tasks scheduled by edf on multiprocessors[END_REF] contains an error. Until now, we are not aware of the availability of a correction for this error.

A processor sharing is an idle fluid schedule in which each task executes at a precisely uniform rate given by its utilization (from[START_REF] Devi | Soft Real-Time Scheduling on Multiprocessors[END_REF]).


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

Laurent George
email: laurent.george@univ-mlv.fr

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

A Stretching Algorithm for Parallel Real-time DAG Tasks on Multiprocessor Systems

Keywords: Real-time scheduling, parallel tasks, Directed Acyclic Graphs, global EDF scheduling, speedup factor

Parallelism is becoming more important nowadays due to the increasing use of multiprocessor systems. In this paper, we study the problem of scheduling periodic parallel real-time Directed Acyclic graph (DAG) tasks on m homogeneous multiprocessor systems. A DAG task is an example of inter-subtask parallelism. It consists of a collection of dependent subtasks under precedence constraints. The dependencies between subtasks make scheduling process more challenging. We propose a stretching algorithm applied on each DAG tasks to transform them into a set of independent sequential threads with intermediate offsets and deadlines. The threads obtained with the transformation are two types, (i) fully-stretched master threads with utilization equal to 1 and (ii) constrained-deadline independent threads. The fully-stretched master threads are assigned to dedicated processors and the remaining processors m ′ ≤ m, are scheduled using global EDF scheduling algorithm. Then, we prove that preemptive global EDF scheduling of stretched threads has a resource augmentation bound equal to 3+ √ 5 2 for all tasksets with n < ϕ • m ′ , where n is the number of tasks in the taskset and ϕ is the golden ratio 1 .

INTRODUCTION

Increasing the performance of execution platforms has been done by increasing the speed of uniprocessor systems associated to the reduction of the size of chips leading to heating problems. Multiprocessor systems have been seen as one solution to overcome these physical limitations, by increasing execution capabilities with processor parallelism.

Many practical examples of shifting towards multiprocessors 1 The value of the golden ratio is 1+ √ 5 2 can be found, such as the Intel Xeon, ARM and Cavium processor families.

However, current real-time software APIs are not able to efficiently take advantage of multiprocessor platforms especially when parallelism is considered. In the industry, the majority of designed applications are targeting uniprocessor systems. But this is expected to change in the coming few years which will focus on parallel programming to take advantage of multiprocessor architectures. There are many models of parallel application, but in this work, we are interested in a particular family of parallelism called intersubtask parallelism, in which a parallel task consists of a collection of subtasks under precedence constraints and dependencies between subtasks. There are many parallel task models based on this family, such as the Fork-join model which is the base of the famous parallel programming API OpenMP, and the multi-threaded Segment model. But the most general model is the Directed Acyclic Graph (DAG) model, which we consider as our task model in this paper.

Real-time scheduling of DAG tasks in particular and parallel tasks in general is a challenging problem. In hard realtime systems, the correctness of a system does not only depend on the correctness of the results, but on the respect of tasks timing parameters. Real-time systems on both uniprocessor and multiprocessor systems have been studied in the last decade, and many researches and scheduling algorithms have been proposed for such platforms [START_REF] Davis | A survey of hard real-time scheduling algorithms and schedulability analysis techniques for multiprocessor systems[END_REF]. However, the extension of real-time scheduling w.r.t. parallel tasks with dependencies is not trivial. The scheduling analysis of such systems can be divided into two main categories: either by transforming task precedence constraints into independent sequential tasks that execute on multiprocessor systems, or by scheduling parallel tasks directly using adapted scheduling algorithms. The first method simplifies scheduling at the price of losing some of the characteristics of parallel tasks, as it removes subtasks dependencies such that classical scheduling algorithms can then be used. In this work, we study the scheduling of DAG tasks using DAG transformation with a stretching approach.

It is worth mentioning here that this work is a generalization of the stretching algorithm proposed by Lakshmanan et. al. in [START_REF] Lakshmanan | Scheduling Parallel Real-Time Tasks on Multi-core Processors[END_REF]. Their work targeted Fork-join parallel tasks and it aims at scheduling tasks as sequentially as possible by stretching their master threads 2 up to their deadline. They proposed to schedule stretched tasks using partitioned FBB-FFD DM-decreasing scheduling algorithm 3 . In our work, we consider a more general task model which is the DAG task and we provide a resource augmentation bound for global Earliest Deadline First (EDF) scheduling of stretched tasks.

The remainder of this paper is organized as follows. Section 2 presents related works w.r.t. the problem of scheduling real-time tasks on multiprocessor systems especially for parallel DAG model. Then we present in Section 3 the considered task model. In Sections 4 and 5, we explain the DAG stretching algorithm in detail and we provide a resource augmentation bound 4 (speedup factor) analysis. Simulation results are provided in Section 6 to study the performance of our stretching algorithm. Finally, Section 7 concludes this work.

RELATED WORK

The scheduling of parallel real-time tasks of different models has been studied on both uniprocessor and multiprocessor systems. In the case of uniprocessor systems, a classical approach in the state-of-the-art is to transform a parallel task into a chain and to assign each subtask of the chain extra timing parameters used for their scheduling. For example, in [START_REF] Chetto | Dynamic scheduling of real-time tasks under precedence constraints[END_REF], the authors considered a hybrid taskset of periodic independent tasks and sporadic dependent graph tasks with a DAG model. They proposed an algorithm aiming at modifying the DAG timing parameters (by adding intermediate offsets and deadlines) in order to remove the dependencies between the tasks in the analysis.

In the case of multiprocessor systems, most research has been done regarding scheduling hard real-time tasks on homogeneous multiprocessor systems, especially for independent sequential tasks [START_REF] Davis | A survey of hard real-time scheduling algorithms and schedulability analysis techniques for multiprocessor systems[END_REF]. As mentioned above, there are mainly two methods for scheduling parallel DAGs in hard real-time systems. The first method schedules DAG tasks by using directly common scheduling algorithms and adapting the performance analysis and the scheduling conditions to take into consideration the particular characteristics of DAGs and parallel tasks in general. This technique is introduced in [START_REF] Baruah | A Generalized Parallel Task Model for Recurrent Real-time Processes[END_REF], which considers a taskset of a single sporadic DAG. They also provided polynomial and pseudopolynomial schedulability tests for EDF scheduling algorithm.

The problem of scheduling multiple DAG tasks on multiprocessors have been more studied in [START_REF] Bonifaci | Feasibility Analysis in the Sporadic DAG Task Model[END_REF][START_REF] Li | Analysis of Global EDF for Parallel Tasks[END_REF]. The authors considered general timing parameters of DAG tasks without taking into account their internal structure. They proved that global EDF has a resource augmentation bound of 2 -1/m, where m is the number of processors in the system. In [START_REF] Qamhieh | Global edf scheduling of directed acyclic graphs on multiprocessor systems[END_REF], the internal structure and the dependencies between subtasks are considered in the analysis of global EDF scheduling of DAG tasks.

The second method for DAG scheduling is based on DAG transformation. Dependencies of inter-subtask parallelism are removed and a DAG task is transformed into a collection of independent sequential threads. A decomposition algorithm is provided in [START_REF] Saifullah | Parallel real-time scheduling of DAGs[END_REF] to distribute the slack time of 3 Partitioned scheduling algorithm FBB-FFD stands for Fisher Baruah Baker-First Fit Decreasing, then Deadline Monotonic priority assignment is used. 4 A resource augmentation bound ν for scheduling algorithm A is the processor speed up factor, such that any feasible taskset on unit-speed processor, is guaranteed to be schedulable with A on processor of speed at least ν.

the DAG task on its subtasks. The slack time is defined as the difference between the deadline of the graph and its minimum sequential execution time. The subtasks are assigned intermediate offsets and deadlines. The authors proved that preemptive global EDF scheduling algorithm has a resource augmentation bound equal to 4, and 4 plus a constant nonpreemption overhead for non-preemptive global EDF.

In [START_REF] Lakshmanan | Scheduling Parallel Real-Time Tasks on Multi-core Processors[END_REF], the authors considered fork-join model of parallel tasks and they proposed a stretching algorithm to execute them as sequentially as possible. A fork-join model is represented as an alternative sequence of sequential and parallel segment. All parallel segments of the same task have the same number of threads, and the threads of each segment have the same sequential execution length. The authors proposed to stretch a fork-join task into a master thread with utilization equal to 1, the remaining parallel threads are forced to execute in parallel with the master thread within a fixed activation interval. Hence, dependencies are no longer considered in the scheduling process. A resource augmentation bound of 3.42 for partitioned preemptive FBB-FFD using Deadline Monotonic (DM) scheduling is given.

Fork-join model is a special case of DAG task model, our paper is an extension of the stretching algorithm of fork-join tasks to DAG tasks. The concept of our stretching algorithm is the same as the one proposed in [START_REF] Lakshmanan | Scheduling Parallel Real-Time Tasks on Multi-core Processors[END_REF], but the steps and the analysis are adapted to a general DAG task model. The contributions of this paper are as follows:

• we propose a stretching algorithm adapted to DAG task model. This algorithm is a pre-step of the scheduling process of the DAGs, which transforms parallel DAGs into independent sequential threads to be scheduled on m identical processors,

• for a taskset of n DAG tasks that execute on a platform of m identical processors, we prove that global EDF scheduling of stretched tasks has a resource augmentation bound equal to 3+ √ 5 2 for all tasks if n < ϕ • m ′ , where m ′ ≤ m is the number of processors not running master threads and ϕ is the golden ratio, and equal to 4 else.

TASK MODEL

We consider a taskset τ of n periodic parallel real-time Directed Acyclic Graph (DAG) tasks run on a system of m identical processors. The taskset τ is represented by {τ1, ..., τn}. Each DAG task τi, where 1 ≤ i ≤ n, is a periodic implicit-deadline graph which consists of a set of subtasks under precedence constraints that determine their execution flow. A DAG task τi is characterized by ({τi,j|1 ≤ j ≤ ni}, Gi, Oi, Di) , where the first parameter represents the set of subtasks of τi and ni is their number, Gi is the set of directed relations between these subtasks, Oi is the offset of the DAG and Di is τi's relative deadline. Since each DAG task has an implicit deadline, its period Ti (interval time between its successive jobs) is the same as its deadline Ti = Di.

Let τi,j denotes the j th subtask of the set of subtasks forming the DAG task τi, where 1 ≤ j ≤ ni. Each subtask τi,j is a single-threaded sequential task which is characterized by a worst-case execution time (WCET) Ci,j. All subtasks of a DAG share the same deadline and period of the DAG. The total WCET Ci of DAG τi is defined as the sum of WCETs . For an implicit-deadline task, whose deadline is equal to its period, the density is the same as the utilization, while the density of a constrained-deadline task becomes δi = Ci Di .

The set of directed relations between the subtasks of DAG τi is denoted by Gi and it defines their dependencies. A directed relation Gi(j, k) between subtasks τi,j and τ i,k means that τi,j is a predecessor of τ i,k , and the latter subtask have to wait for all of its predecessors to complete their execution before it can start its own. An example of a DAG task is shown in Figure 1, in which τ1 consists of 7 subtasks. Precedence constraints are represented by directed arrows between subtasks. A source subtask is a subtask with no predecessors such as τ1,1. Respectively, an ending subtask is the one without any successors such as τ1,7.

Based on the structure of DAG tasks, the critical path of DAG τi is defined as the longest sequential execution path in the DAG when it executes on a virtual platform composed of an infinite number of processors. Its length Li is the minimum response time of the DAG. A subtask that is part of the critical path is referred to as a critical subtask, while non-critical subtasks are executed in parallel with the critical ones.

A DAG task is said to be feasible if the subtasks of all of its jobs respect its deadline. A taskset τ is deemed unfeasible when scheduled using any scheduling algorithm on m unitspeed processors if, at least, one of the following conditions is false:

∀τi ∈ τ, Li ≤ Di U (τ ) = n i=1 Ui = n i=1 Ci Ti ≤ m

DAG STRETCHING ALGORITHM

Based on our task model, subtasks of a DAG inherit the absolute deadline of the DAG task. However, only source subtasks are activated by the activation of the DAG task, while their successors are activated dynamically based on the completion time of their predecessors. During scheduling process, the subtasks of a DAG have to execute within the activation interval of the DAG (between the release time and the absolute deadline of the DAG), while the exact activation time of subtasks is unknown prior to scheduling process. As a result, multiprocessor scheduling of DAG tasks is more complicated than the scheduling of independent sequential tasks. Therefore, scheduling process of DAG tasks can be simplified by avoiding the dynamic activation of subtasks by assigning them intermediate offsets and deadlines. Hereby, we propose a stretching algorithm for parallel DAG tasks which transforms each DAG task into a set of independent periodic constrained-deadline threads, that can be scheduled using any scheduling algorithm of multiprocessors. With our DAG stretching algorithm, the scheduling of a DAG task is done based on the timing parameters of the threads, and a task is deemed feasible if all of its jobs respect their assigned intermediate deadlines. Our DAG stretching algorithm chooses intermediate offset and deadline for each subtask in a DAG task. Before explaining the concept of our algorithm, we start by analyzing the DAG model and identifying its characteristics that led to the stretching algorithm.

Assume that the critical subtasks of DAG τi are combined together in a sequential master thread τ master i whose execution time is equal to Li. Based on the task model, τi can be seen as a master thread with the longest sequential execution time among all paths in the DAG from a source to an ending subtask, while the remaining paths of the DAG execute in parallel with it. For example, DAG task τ1 from Figure 1 consists of 7 subtasks and 6 execution paths: {{τ1,1, τ1,4, τ1,6} {τ1,1, τ1,4, τ1,7} {τ1,2, τ1,4, τ1,6} {τ1,2, τ1,4, τ1,7} {τ1,3, τ1,6} {τ1,5, τ1,7}}. The master thread of τ1 is either {τ1,1, τ1,4, τ1,6} or {τ1,2, τ1,4, τ1,6} with a length L1 = 6. Since both paths are identical w.r.t. their length, we consider the former to be the master thread of the DAG arbitrarily. Thus, DAG task τ1 needs at least 6 time units in order to execute on unit-speed processors. Let Sli denote the positive slack available to DAG τi when it is scheduled exclusively without interference from other tasks. Sli is given by:

Sli = Di -Li (1)
The slack time of the DAG can be seen as a slack time of its master thread since it is the DAG's longest path. Back to the previous example, if we assume that τ1 had a deadline D1 = 10, then its slack time would be Sl1 = 4. In order to avoid dependencies between the subtasks of a DAG task, we propose to use the stretching algorithm which is summarized as follows:

DAG Stretching Algorithm.

Our stretching algorithm fills the slack time of a DAG task by adding fractions of non-critical subtasks to its master thread until it is stretched up to DAG's deadline. As a result, the remaining non-critical subtasks (if any) will be forced to execute in parallel with the stretched master thread within a fixed activation interval.

The objective of our stretching algorithm is to avoid the parallel structure of DAG tasks by executing their subtasks as sequentially as possible. Hence, for each DAG task τi ∈ τ , if τi fits completely on a single processor (Ci ≤ Di), then the stretching algorithm transforms it into a single thread which contains all of its subtasks and forces them to execute sequentially. Otherwise, the algorithm fully stretches the master thread of τi up to its deadline Di. As a result, the stretching algorithm generates a fully-stretched master thread and a collection of independent threads with intermediate offsets and deadlines that execute in parallel with the master thread. The offsets and deadlines of threads are important for the scheduling process and also to maintain the precedence constraints of DAG τi. It is worth noting that the stretching algorithm is a pre-step to the scheduling process, and any master thread with utilization equal to 1, is assigned a dedicated processor by the scheduler. Other parallel threads are scheduled on the remaining processors of the system using any multiprocessor scheduling algorithm.

In this paper, we choose global EDF scheduling algorithm.

For clarity reasons, the reader is advised to refer to the example in Figures 2 and3 so as to have a better understanding of our DAG stretching algorithm. More details about the example are provided at the end this section.

In order to perform our stretching algorithm, we propose to transform a DAG task into Multi-Threaded Segment (MTS) representation. This is a basic transformation for DAGs that maintains precedence constraints between their subtasks and leads to an easier scheduling analysis.

The Multi-Threaded Segment (MTS) Representation

A multi-threaded Segment (MTS) task τ ′ i consists of a sequence of segments. Each segment is composed of a number of parallel threads with the same WCET. Let Si denote the set of parallel segments of τ ′ i , and si denote the total number of segments in Si. Each segment Si,j, 1 ≤ j ≤ si, consists of mi,j parallel threads. All threads of segment Si,j have the same WCET is denoted by ei,j. The number of threads and their WCETs vary from one segment to another, and each segment contains at least one thread.

In this work, MTS task τ ′ i is not a new task but a representation of DAG task τi ∈ τ . This is done by considering that all subtasks of τi are executed as soon as possible on a virtual platform having an infinite number of processors. As a result, each subtask executes under precedence constraints and it does not suffer from interference of other subtasks in the system. For a DAG task τi, its source subtasks are activated at the activation time of DAG τi. Then, successor subtasks are activated as soon as their predecessors have completed their execution. A segment in the MTS task is defined whenever a subtask completes its execution. Thus, threads of the same segment have the same WCET. It is worth noticing that a subtask in DAG τi may be divided into two or more threads executing in successive segments from its MTS representation τ ′ i . Figure 2 shows the MTS representation τ ′ 1 of DAG τ1 from Figure 1. Knowing that DAG τ1 is released at time t = 0 and has a deadline D1 = 10, source subtasks {τ1,1, τ1,2, τ1,3, τ1,5} are activated at t = 0. At t = 2, both subtasks τ1,3 and τ1,5 complete their execution and the first segment S1,1 is defined. Their successors (subtasks τ1,6 & τ1,7) have to wait for all of their predecessors to complete their execution before they can start theirs. At time t = 3, subtasks τ1,1 and τ1,2 complete their execution, subtask τ1,4 starts its own Finally, the MTS task τ ′ i shares the same deadline Di and period Ti of DAG task τi. Hence, Equation 1 regarding the slack Sli of τi remains correct for the MTS task τ ′ i . Also, the critical path length Li and the total WCET Ci of the original DAG task τi is the same for τ ′ i , but they are calculated differently based on the parameters of the MTS task τ ′ i :

Li = s i j=1 ei,j Ci = s i j=1 mi,j * ei,j
For a given DAG set τ , the stretching algorithm is applied to τ ′ i for each DAG task τi ∈ τ . The algorithm is explained in detail in the remainder of this section.

The DAG Stretching Algorithm

As stated earlier, the DAG stretching technique executes the DAGs as sequentially as possible. By doing so, parallel structure of DAGs is removed and dependencies between the subtasks are replaced by intermediate offsets and deadlines. The stretching algorithm is done based on the MTS representation τ ′ i rather than the DAG structure τi. Hence, threads of parallel segments of τ ′ i are used to fill its slack Sli and intermediate offsets and deadlines are assigned to the segments. As a result, a subtask τi,j of DAG τi is said to be feasible if all of its threads in its respective τ ′ i have respected their intermediate deadlines.

The stretching algorithm is divided into two main cases, based on the timing parameters of the parallel DAG τi and the relation between its total WCET Ci and its deadline Di:

• if Ui ≤ 1, then DAG τi is considered as a sequential task because its total WCET Ci can be contained entirely within its deadline Di. As a result, the stretching algorithm transforms its subtasks into a single master thread τ master i in which all of the subtasks execute sequentially. If Ui is equal to 1, then the master thread (a) The MTS representation of task τ1 from Figure 1 showing the slack factors (fi&fi,j) derived using the stretching algorithm. ) and the scheduler dedicates an entire processor for it. Otherwise, the master thread is scheduled as a sequential implicit-deadline periodic task using any multiprocessor scheduling algorithm. In this work, we use global EDF scheduling algorithm.

In this case, the stretching is done directly on the original DAG task τi and it is not necessary to use its MTS representation τ ′ i . • if Ui > 1, then it is impossible for DAG τi to be transformed completely into a single master thread, since its total WCET Ci is larger than its deadline Di. Hence, the stretching algorithm cannot avoid parallelism in τi. Applying the stretching algorithm on τ ′ i generates a fully-stretched master thread τ master i as a result of stretching the critical path of τ ′ i up to its deadline, in addition to a set of constrained-deadline threads {τ cd i } with intermediate offsets, deadlines and period equal to the original Ti. The importance of intermediate offsets and deadlines of each thread is to keep the dependencies between the subtasks of the original task, and prevent threads of the same subtask from executing in parallel. As in the previous case, the master thread, which has a utilization U master i = 1, will be assigned its own processor, while threads of the latter set will be scheduled independently on the remaining processors of the system.

As stated earlier, the stretching algorithm aims at stretching the critical path of task τ ′ i up to its deadline and create a fully-stretched master thread. In order to do so, parallel non-critical threads of τ ′ i are used to fill the slack Sli of the task uniformly, and all segments of τ ′ i with more than one thread participate. To achieve a uniform filling of the slack, equal fractions from these threads are added to the master thread. In this case, where the stretching algorithm targets only parallel tasks with Ci > Di, the total WCET Ci of τ ′ i without its critical path length Li definitely exceeds its deadline Di. We define a distribution factor fi of each execution unit in (Ci -Li) that has to be added to the slack Sli as follows:

fi = Sli Ci -Li = Di -Li Ci -Li (2)
≤ Di Ci < 1
In order to clarify the meaning of fi, let us suppose that each non-critical execution unit in task τ ′ i is divided into two parts, first part of length equal to fi is added to the master thread and (1 -fi) execute in parallel as a constraineddeadline thread. The total execution time added from noncritical threads to the master thread is equal to Sli. However, it is unpractical to use fi in this way, and force each execution unit to be divided into two parts. So, the filling of the slack is based on the execution requirement of each segment in the task and not on the threads directly. We fill the slack with the maximum number of entire threads from each segment. Thus, at most one thread from each segment will be used to fill the slack partially. From the MTS representation τ ′ i , each segment Si,j ∈ Si ∈ τ ′ i has mi,j parallel threads, among them there is a critical thread. Hence, the total non-critical worst-case execution time of segment is equal to (ei,j * (mi,j -1)). Based on the definition of fi, we conclude that a total of (fi * ei,j(mi,j -1)) time units from segment Si,j will be added to the master thread. Now, we want to identify how many threads of each segment Si,j are added to the master thread based on the total execution time of the segment. Knowing that the threads of segment Si,j have equal WCETs denoted by ei,j, which is equivalent to the shortest sequential execution length of the segment, we can identify how many entire threads are added to the master thread. Let fi,j denote the number of threads from segment Si,j to be added to the master thread: fi,j = fi * ei,j(mi,j -1) ei,j

= fi * (mi,j -1) (3)
According to this, each segment Si,j adds ⌊fi,j⌋ entire threads and a fraction of a thread of length (fi,j -⌊fi,j⌋)ei,j to the master thread. As a result, the slack Sli of task τ ′ i is filled completely and a fully-stretch master thread τ ′ i with U master i equal to 1 is generated. We conclude that each segment Si,j adds in total (1+fi,j) threads to the master thread (including the critical thread), while the remaining threads of the segment execute in parallel with the master thread. Hence, each segment Si,j has an intermediate deadline Di,j calculated as follows:

Di,j = (1 + fi,j) * ei,j (4)
From the definition of the MTS model, segments of a task τ ′ i execute sequentially and when one segment completes its execution, its successor starts its own. Hence, at any time t ≥ 0, there is only one active segment from each task τ ′ i . According to this, we can define an intermediate offset Oi,j for each segment Si,j ∈ τ ′ i based on the intermediate deadlines of the segments, where:

∀Si,j : j > 1 → Oi,j = j-1 k=1 D i,k
and Oi,1 = 0 (since τi has no offset).

After applying the stretching algorithm, a segment Si,j of τ ′ i comprises of:

• a thread τ master i,j
which is part of the master thread τ master i of τ ′ i . It has a WCET of Di,j and a deadline of Di,j.

• (mi,j -⌊fi,j⌋-2) parallel constrained-deadline threads with a WCET of ei,j and a deadline Di,j.

• one remaining thread with WCET of (1 + ⌊fi,j⌋fi,j)ei,j and a constrained-deadline (1+⌊fi,j⌋)ei,j. The remaining WCET is added to the master thread so as to fill its slack. We can notice here that the remaining thread has a shorter deadline than the other entire remaining threads from the same segment. This is done so as to force the first fraction of the thread to finish its execution before the second fraction in the master thread starts its own. As a result, both fractions of the same threads are forced to execute sequentially.

For each segment Si,j, the total number of threads in a segment (including the partial thread), which are not added to the master thread, is given by: qi,j = mi,j -⌊fi,j⌋ -1 [START_REF] Davis | Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems[END_REF] According to this, qi,j independent threads from segments of each task τ ′ i ∈ τ are scheduled using any multiprocessor scheduling algorithm, while the fully-stretched master threads are assigned their own processors. After applying the stretching algorithm on each task τ ′ i ∈ τ , each task generates at most one fully-stretched master thread. Hence, the total number of these master threads, respectively the number of their dedicated processors, cannot exceed n, which is the total number of tasks in the original DAG set τ . As a result, the constrained-deadline tasks are scheduled on the remaining processors of the system which are referred to as m ′ . The relation between the remaining processors m ′ and the total number of processors in the system m is given as follows:

m ′ ≥ m -n (6)
Algorithm 1 shows the DAG stretching algorithm. It shows its steps and the generated threads after the stretching. Now, we present an example of the stretching algorithm applied on the DAG task τ1 from Figure 1.

Example: Stretching Algorithm

We present in this section an example of the stretching algorithm applied to the DAG task of Figure 1. The algorithm is summarized in three main steps which are shown in Figures 2 &3. We assume that task τ1 is a periodic implicit-deadline DAG with C1 = 14 and a deadline D1 = 10. Since its utilization U1 = 1.4 > 1, then τ1 has to be represented by τ ′ 1 which is shown in Figure 2. The subtasks of τ1 execute as

Algorithm 1 DAG Stretching Algorithm Require: τi(ni, {1 ≤ j ≤ ni|τi,j}, Gi, Di) Ensure: τ master i , {τ cd i } if Ci ≤ Ti then ⊲ Execute τ ′
i sequential as a single task for Si,j ∈ Si do for k = 1 to mi,j do τ master i ← τ master i ∪ τ k i,j : ei,j end for end for else τ ′ i ← DagT oM T S(τi) ⊲ Represent a DAG task as a multi-threaded segment task.

fi

← Sl i C i -L i
for Si,j ∈ Si do fi,j ← fi * (mi,j -1) qi,j ← ⌊fi,j⌋ + 1 for k = 1 to qi,j do ⊲ qi,j threads of segment Si,j are added to the master thread

τ master i ← τ master i ∪ τ k i,j : ei,j end for τ master i ← τ master i ∪ τ q i,j +1 i,j : (fi,j -⌊fi,j⌋) * ei,j τ tmp i,j ← τ q i,j +1 i,j : (1 + ⌊fi,j⌋ -fi,j) * ei,j D tmp i,j ← (1 + ⌊fi,j⌋) * ei,j if j == 1 then O tmp i,j ← Oi else O tmp i,j ← O i,(j-1) + D i,(j-1) end if {τ cd i } ← {τ cd i } ∪ τ tmp i,j
for k = (qi,j + 2) to mi,j do

τ tmp i,j ← τ k i,j : ei,j D tmp i,j ← (1 + fi,j) * ei,j if j == 1 then O tmp i,j ← Oi else O tmp i,j ← O i,(j-1) + D i,(j-1) end if {τ cd i } ← {τ cd i } ∪ τ tmp i,j
end for end for end if

(O master i ← Oi (D master i ← Di return (τ master i , {τ cd i })
soon as possible while considering an execution platform of infinite number of processors, and the only blocking effect on a subtask is due to its predecessors. In Figure 2, the MTS task τ ′ 1 is identified. It consists of 5 segments. Segment S1,1 has 4 threads with e1,1 = 2, while the remaining threads have WCET equal to 1. Segments S1,2 & S1,4 have two threads and segments S1,3 & S1,5 have a single thread. The length of the critical path is L1 = 6 and its deadline D1 = 10. Based on Equation 1, the slack Sl1 is equal to 4. The total WCET of τ1 is equal to 14 and the noncritical execution time (while excluding the critical path) is equal to 8. According to Equation 2, the distribution factor of τ ′ 1 is equal to f1 = 4 8 = 1 2 . For each segment S1,j, its distribution factor f1,j depends on the number of its parallel threads, where f1,1 = 3 2 , f1,2 = f1,4 = 1 2 and f1,3 = f1,5 = 0, as shown in Figure 3(a). It is worth noticing that segments with a single thread have a distribution factor equal to zero, because their single thread is a critical one and it is already included in the master thread.

Based on the values of the segment distribution factor of each segment, we can identify how many threads to be added to the master thread from each segment. As described earlier, (1 + fi,j) threads from segment Si,j are used to fill the master thread. Figure 3(b) shows the stretching of task τ1 and its final result. We can notice that a total of 5 2 threads from segment S1,1 are added to the master thread where each thread has a length of 2. This is equivalent to 2 entire threads and a half. Knowing that the original DAG task τ1 has no offset, then the first segment S1,1 has no offset and its execution interval length is defined as 5 2 * 2 = 5. The third thread of segment S1,1 (denoted by τ1,3 in Figure 3(b)) is divided into two halves, one is added to the master thread and the other is an independent constrained-deadline thread with a deadline D1,3 = 4. The fourth remaining thread of the segment has a deadline equal to the deadline of the segment which is 5. The difference between both threads is that thread τ1,3 has to finish earlier than the deadline of the segment so as to give its other part (the one added to the master thread) enough time to execute. Both parts have to execute sequentially and never in parallel, and the intermediate deadline of the remaining thread forces the sequential execution of the entire subtask. By applying the same calculations on all of the segments, we obtain the result in Figure 3(b). Regarding segments S1,2 & S1,4, each one adds 1 2 thread to the master thread. This means that there is only one partial thread left to execute in parallel with the master thread from each segment. As shown in the example in Figure 3(b), the stretching algorithm generates a master thread τ master 1 with WCET and deadline equal to 10, and 4 constrained-deadline threads identified as follows: {τ cd 1 } = {{τ1,3 : (0, 1, 4, 10)},{τ1,5 : (0, 2, 5, 10)},{τ1,2 : (5, 0.5, 1, 10)},{τ1,7 : (7.5, 0.5, 1, 10)}}, where each thread is identified by its intermediate offset, WCET, intermediate deadline and period. These threads are scheduled as independent constrained-deadline threads on m ′ processors. In this example , we consider that taskset τ contains a single DAG τ1 which execute on a system of 2 identical processors. Then the master thread occupies a processor for itself, and the other processor is used for the scheduling of the parallel threads, which means m ′ = 1. Lemma 1. A DAG set τ that is schedulable using algorithm A on a system of m processors, remains schedulable after stretching, i.e., the DAG stretching algorithm does not affect its schedulability.

Proof. As described above, the stretching algorithm assigns intermediate offsets and deadlines for threads of each DAG in τ , without changing their original offsets and deadlines. Intermediate offsets and deadlines maintain precedence constraints of the original DAG, which means that if a τ ′ str is schedulable while respecting the intermediate deadlines of the threads, then the original DAG taskset τ must be schedulable while respecting the DAGs' deadlines.

RESOURCE AUGMENTATION BOUND ANALYSIS

In this section, we analyze the performance of DAG stretching algorithm of parallel tasks by calculating its resource augmentation bound (speedup factor) when global EDF is used to schedule the non fully-stretched threads generated from the stretching algorithm. Speedup factor is a common performance metric for real-time scheduling algorithms, that gives indications about their performance w.r.t. the performance of an optimal algorithm. Definition 1 (from [START_REF] Kalyanasundaram | Speed is as powerful as clairvoyance [scheduling problems[END_REF]). For a given taskset τ that is feasible on m unit-speed processors using an optimal scheduler, it is schedulable using A scheduling algorithm on m processors that are ν times faster. The minimum speedup factor of processors speed is the resource augmentation bound (or simply the speedup factor) of scheduler A.

Let τ ′′ be the thread set generated after applying our stretching algorithm on every DAG task in τ . It contains all threads generated from the stretching algorithm except for the fully-stretched master threads (including the constraineddeadline parallel threads and the implicit-deadline master threads). We prove that global EDF scheduling of τ ′′ when executing on m ′ processors, has a speedup factor of 3+ √ 5 2 for all tasks with n < ϕ • m ′ , where ϕ = 1+ √ 5

2 , the remaining number of processors is denoted by m ′ ≥ m -n, where m is the original number of processors in the system and n is the number of tasks in the set τ This implies that if a taskset τ ′′ is feasible on m ′ unit-speed processors, then it is schedulable using global EDF on m ′ processors with speed of 3+ √ 5 2 as fast as the original. Otherwise, the speedup factor is equal to 4 if we use the decomposition algorithm from [START_REF] Saifullah | Parallel real-time scheduling of DAGs[END_REF]. The fully-stretched master threads are assigned their own processors, while the remaining parallel threads are scheduled using global EDF on the remaining processors.

Our speedup factor analysis is based on the following sufficient scheduling condition of global EDF scheduling algorithm.

Theorem 1 (From [START_REF] Baruah | Techniques for Multiprocessor Global Schedulability Analysis[END_REF]). Any constrained-deadline sporadic sequential task set τ with total density δ sum (τ ) and maximum density δ max (τ ) is schedulable using preemptive global EDF policy on m unit-speed processors if

δ sum (τ ) ≤ m -(m -1)δ max (τ ) Theorem 2. If constrained-deadline taskset τ ′′ of paral- lel threads, with n < ϕ • m ′ , where ϕ = 1+ √ 5 2
(the golden ratio) and n is the number of tasks in DAG taskset τ , is feasible on m ′ unit-speed processors, then τ ′′ is schedulable using global EDF on m ′ processors with speed at least 3+ √ 5

2 . Proof. Based on Theorem 1, a taskset of constraineddeadline parallel threads τ ′′ that is generated after applying the DAG stretching algorithm is schedulable on the remaining processors m ′ of the system if:

δ sum (τ ′′ ) ≤ m ′ -(m ′ -1)δ max (τ ′′ )
We start by calculating the maximum density δ max (τ ′′ ) of the threads of τ ′′ . As stated earlier, τ ′′ consists of two types of threads: implicit-deadline master threads (not fullystretched) from DAG tasks with utilization less than 1, and a collection of constrained-deadline threads {τ cd } from each DAG task with a utilization higher than 1. We will consider both cases while calculating δ max (τ ′′ ):

• case 1: for an implicit-deadline DAG task τi with Ui < 1, it is completely transformed into a single master thread τ master i with the same timing parameters of the original DAG τi. Based on the assumption that τi has implicit deadline, then its deadline D master i is equal to its period T master i , and respectively, δ master i = U master i < 1.

• case 2: for an implicit-deadline DAG task τi with Ui > 1, it is transformed into a set of constraineddeadline parallel threads with intermediate offsets and deadlines. From the structure of multi-threaded segment tasks, only one segment is active at every time instant t. Each segment Si,j ∈ Si ∈ τ ′ , with mi,j > 1, has at most two types of parallel threads, entire and partial threads. Parallel threads of segment Si,j (other than the one in the master thread) have a maximum density δ max i,j of:

δ max i,j
= max{ ei,j (1 + fi,j)ei,j , (1 + ⌊fi,j⌋ -fi,j)ei,j

(1 + ⌊fi,j⌋)ei,j } = max{ 1 1 + fi,j , 1 -(fi,j -⌊fi,j⌋) (1 + fi,j) -(fi,j -⌊fi,j⌋) } ∀ mi,j > 1 ⇒ δ max i,j = 1 1 + fi,j (7)
From the above equation, the maximum density of threads of segment Si,j in τi depends on the segment distribution factor fi,j. From Equation 3, fi,j depends on the number of threads in this segment. Hence, the segment with a small number of threads has a higher density. We can conclude that the highest density of a thread in task τi occurs when the segment has the smallest possible number of threads (mi,j ≥ 2).

δ max i = 1 1 + (fi * (2 -1)) -→ from 3 = 1 1 + fi (8)
From Equation 2, we can derive the following relation:

∀fi ≥ 0 → δ max i = 1 1 + fi and fi ≥ Di -Li Ci → 1 1 + fi ≤ 1 1 + D i -L i C i ≤ Ci Ci + Di -Li ≤ 1 (Since Li ≤ Di).
From both cases, the maximum density δ max (τ ′′ ) of all threads in τ ′′ is:

δ max (τ ′′ ) = max τ ′′ i ∈τ ′′ {δ master i , δ max i } ≤ 1 (9)
It is worth noticing here that DAG tasks with utilization equal to one are not considered in the previous cases, because the DAG stretching algorithm transforms them into fully-stretched master threads that are assigned their own executing processors. Hence, they are not included in the resource augmentation bound of global EDF scheduling.

In order to calculate the total density of thread set τ ′′ , we consider that at time t, only a single segment from each task with utilization higher than 1 can be active in addition to the master threads of tasks with utilization < 1. We calculate the density of a task τ ′′ i , with Ui > 1, by considering the threads of the segment with the highest density. Let δ sum i be the sum of densities of such threads in a certain segment in a task τi:

δ sum i ≤ 1 1 + fi,j
* (mi,j -1 -⌊fi,j⌋) -→ ⌊fi,j⌋ ≥ 0 and from Eq. ( 5)

≤ mi,j -1 fi * (mi,j -1) ≤ 1 fi ≤ Ci -Li Di -Li ≤ Ci Di -Li -→ from Eq. (2) (10)
Now, we consider the second case where task τ ′′ i has a utilization less than 1 and is transformed into an implicit-deadline non-fully stretched master thread. The total density of the task is denoted

δ master max = Ci Di ≤ δ sum i .
For taskset τ ′′ , let δ sum (τ ′′ ) be the sum of densities of every DAG task in the original taskset τ :

δ sum (τ ′′ ) ≤ τ i ∈τ Ci Di -Li (11)
In order to calculate the speedup factor, we consider that taskset τ ′′ executes on m ′ processors with a minimum speed ν, where ν > 1. Increasing the speed of processors affects the execution parameters of task τi such as Ci and Li.

The critical path length Li of any task τi has a necessary feasibility condition:

∀τi : 1 ≤ i ≤ n -→ Li ≤ Di (12)
Otherwise, task τi is not feasible on a unit-speed processors. On a processor that is ν times faster, the critical path length L ν i is given by:

∀τi : 1 ≤ i ≤ n -→ L ν i = Li ν ≤ Di ν (13)
The same notation is applied for the total execution time C ν i of task τi when it is run on processors ν times faster:

∀τi : 1 ≤ i ≤ n -→ C ν i = Ci ν (14)
The total density of taskset δ sum,ν on speed-ν processors is:

δ sum,ν (τ ′′ ) ≤ τ i ∈τ C ν i Di -L ν i (15)
From Equation 13,

∀1 ≤ i ≤ n -→ L ν i ≤ Di ν ⇒ (Di -L ν i ) ≥ Di(1 - 1 ν ) Using this result, δ sum,ν (τ ′′ ) ≤ τ i ∈τ Ci/ν Di(1 -1 ν ) ≤ 1 ν -1 τ i ∈τ Ci Di ≤ m ν -1
From Equation 9, the maximum density δ max,ν (τ ′′ ) of taskset τ ′′ on speed-ν processors is:

δ max,ν (τ ′′ ) = δ max ν ≤ 1 ν (16)
Therefore, taskset τ ′′ is schedulable under preemptive global EDF on m ′ speed-ν processors if:

m ν -1 ≤ m ′ + n ν -1 ≤ m ′ -(m ′ -1) 1 ν m ′ ν -1 + n ν -1 ≤ m ′ - m ′ ν + 1 ν 1 ν -1 + 1 ν - 1 m ′ ν ≤ 1 ν -1 + 1 ν ≤ 1 - n (ν -1)m ′ 2ν -1 ν 2 -ν ≤ 1 - n m ′ (ν -1)
In order to have a positive value for the right hand side of the inequality, we consider the following:

0 < n m ′ (ν -1) < 1 ⇒ m ′ > n ν -1 2ν -1 ν 2 -ν <1 0 <ν 2 -3ν + 1 → ν = 3 + √ 5 2 for n < ϕ • m ′ , where ϕ = 1 + √ 5 2
where ϕ is the golden ratio.

This concludes the proof of the speedup factor.

SIMULATION

In this section, we provide simulation results for global EDF scheduling with stretched tasksets. The objective of simulation experiments is to test the performance of our DAG stretching algorithm when used prior to the scheduling process of DAG tasks. Also, we aim to compare it with another existing DAG scheduling technique found in the stateof-the-art [START_REF] Saifullah | Parallel real-time scheduling of DAGs[END_REF]. To our knowledge, the decomposition algorithm proposed in [START_REF] Saifullah | Parallel real-time scheduling of DAGs[END_REF] is the only other DAG scheduling algorithm using a DAG transformation technique. Therefore, we simulated the process of DAG scheduling for both algorithms, stretching and decomposition.

In all experiments, we generated 100000 synchronous tasksets. We used a random generator of DAG tasksets which uses UUnifast-Discard method from [START_REF] Davis | Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems[END_REF]. In order to generate a taskset, the generator requires two inputs, the total utilization of the taskset and the number of tasks. Then it distributes the utilization on its tasks uniformly. Based on the assigned utilization of each task, we derive its remaining timing parameters (WCET and deadline). In order to limit the hyperperiod (least common multiple of periods) of tasksets, we used the limitation technique from [START_REF] Goossens | Limitation of the Hyper-Period in Real-Time Periodic Task Set Generation[END_REF] in which we define a matrix containing all possibilities of period values of tasks. We defined the simulation interval of tasksets to be as large as the hyperperiod. Also, the number of subtasks of each DAG task and their dependencies are generated randomly.

Comparison between DAG stretching and decomposition algorithms

The first results of simulation are provided in Figure 4. They are obtained by varying two parameters, the number of unitspeed processors m on which tasksets are executing, and the percentage of taskset utilization, where the maximum utilization of a taskset is equal to m. Figure 4 shows the comparison results between our DAG stretching algorithm (denoted 'STR' in the figure) and the DAG decomposition algorithm 5 (denoted by 'DCMP' in the figure). Similarly, The decomposition algorithm transforms each dependent DAG task into a set of independent sequential threads with intermediate offsets and deadlines by distributing the slack of the DAG on its segments. Figure 4 shows the percentage of successfully schedulable tasksets when global EDF is used for m processors (from 2 to 16). The x-axis of the figure represents the percentage of taskset utilization w.r.t. the maximum utilization which is equal to m. The percentage values are between 20% and 100%. For each taskset, the scheduling process is simulated for both cases, when the taskset is stretched (STR) or decomposed (DCMP).

From our simulations, we notice that the performances of our stretching algorithm is better than the decomposition algorithm for the scheduling of the DAG tasks. In all the experiments, the percentage of schedulable tasksets when stretched are higher than the decomposed ones. Also, we can notice that the percentage of the schedulable tasksets decreases when the number of processors increases.

Varying the speed of processors

Here, we analyze the effect of increasing the speed of processors w.r.t. the schedulability of stretched DAG tasks. Based on the speedup factor of our stretching approach, the schedulability of stretched DAG tasks increases when the speed of processors increases and feasible tasksets become schedulable using global EDF when the speed ν > 3+ √ 5

2 . In these experiments, we increased the speed of processors from ν = 1 up to 4 by steps of 1, while varying the number of processor and taskset utilization as in the above simulations.

The results shown in Figure 5 are done by varying the 5 For more details about the decomposition algorithm, please refer to the original paper in [START_REF] Saifullah | Parallel real-time scheduling of DAGs[END_REF]. speed of processors on which tasksets are executed. For each m from 2 to 8, we simulate global EDF scheduling of tasksets of maximum utilization (equal to m). The choice of taskset utilization is done because these tasksets have the smallest success ratio in the results from Figure 4. As shown in Figure 5, schedulability of stretched tasksets increases when the speed of processors increases. In the case of m = 2 and m = 4, a success ratio of almost 100% is achieved when the speed of processors ν ≥ 2, while it needs processors speed at least equal to 4 for m = 8. The simulation results provided in this section show the performances of our DAG stretching approach when compared to the decomposition scheduling algorithm of DAGs. Although simulation experiments based on random generation of tasksets cannot be used as an accurate performance metric of algorithms in real-time systems, the results are considered as an indication regarding the average behavior of studied scheduling algorithms.

CONCLUSIONS

In this paper, we presented a stretching algorithm for parallel periodic real-time DAG tasks on homogeneous multiprocessor systems. The stretching algorithm is an extension to the one in [START_REF] Lakshmanan | Scheduling Parallel Real-Time Tasks on Multi-core Processors[END_REF] which targeted Fork-join task model, a special case of DAG model. Similarly, our DAG stretching algorithm aimed at removing dependencies between subtasks of DAG tasks and stretching their critical path (master thread) up to its deadline. In addition to the master thread which is assigned its own executing processor, a set of independent threads with intermediate offsets and deadlines are generated and scheduled using global EDF scheduling algorithm.

Then, we proved a speedup factor of 3+ for global EDF scheduling algorithm for stretched threads if n < ϕ • m ′ , where n is the total number of tasks in the taskset, m ′ is the remaining number of processors after taking off the processors dedicated for the fully-stretched master threads and ϕ is the golden ratio whose value is 1+ √ 5 2 and 4 else. Finally, we compared the performance of our stretching algorithm with another scheduling technique for DAGs from the state-of-art using DAG decomposition. The simulation results show that our DAG stretching algorithm has better average performances.

Figure 1 :

 1 Figure 1: An example of a DAG task τ1 which consists of 7 subtasks. The number on the upper right corner of each subtask represents its WCET and the arrows represent their precedence constraints.

Figure 2 :

 2 Figure 2: The Multi-Threaded Segment (MTS) representation of DAG task τ1 from Figure 1.

  The Stretch algorithm is applied on the MTS task. The result of the stretching are the master thread and the constrained-deadline parallel threads.

Figure 3 :

 3 Figure 3: Example of the DAG stretching algorithm applied on DAG τ1 from Figure 1.

Figure 4 :

 4 Figure 4: Comparison results of global EDF scheduling simulation between the DAG stretching algorithm and decomposition algorithm from[START_REF] Saifullah | Parallel real-time scheduling of DAGs[END_REF]

Figure 5 :

 5 Figure 5: Simulation results show the effect of processor speed on the schedulability of the stretched tasksets.

A master thread of a parallel task is defined as the sequential path in the task with the longest execution time.