# Optimizing Distributed Real-Time Embedded System Handling Dependence and Several Strict Periodicity Constraints

Authors: Omar Kermia
Journal: Advances in Operations Research
 (2011)

---

## Abstract

This paper focuses on real-time nonpreemptive multiprocessor scheduling with precedence and strict periodicity constraints. Since this problem is NP-hard, there exist several approaches to resolve it. In addition, because of periodicity constraints our problem stands for a decision problem which consists in determining if, a solution exists or not. Therefore, the first criterion on which the proposed heuristic is evaluated is its schedulability. Then, the second criterion on which the proposed heuristic is evaluated is its execution time. Hence, we performed a schedulability analysis which leads to a necessary and sufficient schedulability condition for determining whether a task satisfies its precedence and periodicity constraints on a processor where others tasks have already been scheduled. We also present two multiperiodic applications.


---

## Body

## 1. Introduction

Hard Real-Time problematic is to maintain temporal and functional achievement of systems execution. Hard real-time scheduling has been concerned with providing guarantees for temporal feasibility of task execution whatever the situations. A scheduling algorithm is defined as a set of rules defining the execution of tasks at system run-time. It is provided thanks to a schedulability analysis, which determines, whether a set of tasks with parameters describing their temporal behavior will meet their temporal constraints if executed at run-time according to the rules of the scheduling algorithm. The result of such a test is typically a yes or a no answer indicating whether a solution will be found or not. These schemes and tests demand precise assumptions about task properties, which hold for the entire system lifetime.In order to assist the designers, scientists at INRIA proposed a methodology called AAA (Algorithm Architecture Adequation) and its associated system-level CAD software called SynDEx. They cover the whole development cycle, from the specification of the application functions, to their implementation running in real-time on a distributed architecture composed of processors and specific integrated circuits. AAA/SynDEx provides a formal framework based on graphs and graph transformation. On the one hand, they are used to specify the functions of the applications, the distributed resources in terms of processors, and/or specific integrated circuit and communication media, the nonfunctional requirements such as temporal criteria. On the other hand, they assist the designer in implementing the functions onto the resources while satisfying timing requirements and, as much as possible, minimizing the resources. This is achieved through a graphical environment which allows the user to explore manually and/or automatically, using optimization heuristics, the design space solutions. Exploration is mainly carried out through real-time scheduling analysis and timing functional simulations. Their results predict the real-time behavior of the application functions executed onto the various resources, that is, processors, integrated circuits, and communication media. This approach conforms to the typical hardware/software codesign process. Finally, the code that is automatically generated as a dedicated real-time executive, or as a configuration file for a resident real-time operating system such as Osek and RTlinux, [1, 2], details the AAA methodology and SynDEx.In practice, periodic tasks are commonly found in applications such as avionics and process control when accurate control requires continual sampling and processing of data. Such applications based on automatic control and/or signal processing algorithms are usually specified with block-diagrams. They are composed of functions producing and consuming data, and each function can start its execution as soon as the data it consumes are available, and the cost of a task scheduling is a constant included in its worst case execution time (WCET). This periodicity constraint is the same as the one we find in the Liu and Layland model [3]. A data transfer between producer and consumer tasks leads to precedence constraints that the scheduling must satisfy. In systems we deal with, besides periodicity and precedence constraints, some tasks must be repeated according to a strict period. These tasks represent sensors and actuators by interacting with the environment surrounding the system and for which no data exchanged with this environment is lost. As data produced by the environment to the system are consumed strict periodically on the one hand and data expected by the environment from the system with a strict periodically way on the other hand, sensors and actuators must be executed at a strict periods [4]. In order to satisfy the strict periodicity of these tasks, we consider that all the system tasks have a strict period.Strict period means that if the periodic taskti has period T(ti) then for all j∈ℕ*, (S(tij+1)-S(tij))=T(ti), where tij+1 and tij are the jth and the (j+1)th instances of the task ti, and S(tij) and S(tij+1) are their start times [5]. Notice that tij is the jth instance or repetition of the periodic task ti.The multiprocessor real-time scheduling problem with precedences constraints, but without periodicity constraints, whatever the number of processors, has always a solution. The distributed schedule length, corresponding to the total execution time (Makespan), determines the solution quality. On the contrary, when periodicity constraints must be satisfied the problem may not have a solution. In other words, an application with precedence and periodicity constraints is either schedulable or not.Thus, this paper discusses three mains goals:(i)
the precedence and periodicity constraints must be satisfied. This is achieved by repeating every task according to its period onto the same processor, and receiving all the data a task needs before it executes. In comparison with the previous AAA/SynDEx, additional steps are required to assign the tasks to the processors and to add missing precedence before being distributed and scheduled;(ii)
distributed architectures involve interprocessor communications the cost of which must be taken into account accurately, as explained in [6]. These communications must be handled even when communicating tasks have different periods;(iii)
since the target architecture is embedded, it is necessary to minimize the total execution time in the one hand to insure that feedback control is correct, and in the other hand to minimize the resource allocation.As it is mentioned previously, we are interested in nonpreemptive scheduling. This choice is motivated by a variety of reasons including [7]:  (i)
in many practical real-time scheduling problems such asI/O scheduling, properties of device hardware and software either make preemption impossible or prohibitively expensive. The preemption cost is either not taken into account or still not really controlled;(ii)
nonpreemptive scheduling algorithms are easier to implement than preemptive algorithms and can exhibit dramatically lower overhead at run-time;(iii)
the overhead of preemptive algorithms is more difficult to characterize and predict than that of nonpreemptive algorithms. Since scheduling overhead is often ignored in scheduling models, an implementation of a nonpreemptive scheduler will be closer to the formal model than an implementation of a preemptive scheduler.For these reasons, designers often use nonpreemptive approaches, even though elegant theoretical results on preemptive approaches do not extend easily to them [8].


### 1.1. Related Work

According to the multiprocessor scheduling scheme (partitioned or global), the use of these algorithms changes:(i)
in partitioned multiprocessor scheduling, it is necessary to have a scheduling algorithm for every processor and an allocation (distribution) algorithm is used to allocate tasks to processors (Bin Packing) which implies heuristics utilization. Schedulability conditions for RM and EDF in multiprocessor were given;(ii)
in global multiprocessor scheduling, there is only one scheduling algorithm for all the processors. A task is put in a queue that is shared by all processors and, since migration is allowed, a preempted task can return to the queue to be allocated to another processor. Tasks are chosen in the queue according to the unique scheduling algorithm, and executed on the processor which is idle. Schedulability conditions for RM and EDF in multiprocessor were given in the case of preemptive tasks.It is well known that the Liu and Layland results, in terms of optimality and schedulability condition, break down on multiprocessor systems [9]. Dhall and Liu [10] gave examples of task sets for which global RM and EDF scheduling can fail at very low processor utilization, essentially leaving almost one processor idle nearly all of the time. Reasoning from such examples is tempting to conjecture that perhaps RM and EDF are not good or efficient scheduling policies for multiprocessor systems even if, at the moment, these conclusions have not been formally justified [11].In addition, these scheduling algorithms consider a unique independent tasks which means that tasks do not exchange data, whereas these dependences are specified in our applications by a direct graph of tasks.In [12] tasks are preemptive but dependent except that only tasks with the same period can communicate. AAA/SynDEx handles dependences between tasks with multiple periods by transforming the initial graph.


### 1.2. Model

We deal with systems of real-time tasks with precedence and strict periodicity constraints. A taskti (denoted in this paper as (ti:C(ti),T(ti)) is characterized by a period T(ti), a worst case execution time C(ti) with C(ti)≤T(ti), and a start time S(ti).The precedences between tasks are represented by a directed acyclic graph (DAG) denotedG such that G=(𝕍,𝔼). 𝕍 is the set of tasks characterized as above, and 𝔼⊆𝕍×𝕍 the set of edges which represents the precedence (dependence) constraints between tasks. Therefore, the directed pair of tasks (ti,tj)∈𝔼 means that tj must be scheduled, only if ti was already scheduled, and thus we have S(ti)+C(ti)≤S(tj).We assume that periods and WCETs are multiple of a unit of timeU=1 which means that they are integers representing, for example, some cycles of the processor clock. If a task ti with execution time C(ti) is said to start at time unit S(ti), it starts at the beginning of time unit S(ti) and completes before the beginning of time unit S(ti)+C(ti). Thus the time interval where task ti is executed is [S(ti),S(ti)+C(ti)[.


## 1.1. Related Work

According to the multiprocessor scheduling scheme (partitioned or global), the use of these algorithms changes:(i)
in partitioned multiprocessor scheduling, it is necessary to have a scheduling algorithm for every processor and an allocation (distribution) algorithm is used to allocate tasks to processors (Bin Packing) which implies heuristics utilization. Schedulability conditions for RM and EDF in multiprocessor were given;(ii)
in global multiprocessor scheduling, there is only one scheduling algorithm for all the processors. A task is put in a queue that is shared by all processors and, since migration is allowed, a preempted task can return to the queue to be allocated to another processor. Tasks are chosen in the queue according to the unique scheduling algorithm, and executed on the processor which is idle. Schedulability conditions for RM and EDF in multiprocessor were given in the case of preemptive tasks.It is well known that the Liu and Layland results, in terms of optimality and schedulability condition, break down on multiprocessor systems [9]. Dhall and Liu [10] gave examples of task sets for which global RM and EDF scheduling can fail at very low processor utilization, essentially leaving almost one processor idle nearly all of the time. Reasoning from such examples is tempting to conjecture that perhaps RM and EDF are not good or efficient scheduling policies for multiprocessor systems even if, at the moment, these conclusions have not been formally justified [11].In addition, these scheduling algorithms consider a unique independent tasks which means that tasks do not exchange data, whereas these dependences are specified in our applications by a direct graph of tasks.In [12] tasks are preemptive but dependent except that only tasks with the same period can communicate. AAA/SynDEx handles dependences between tasks with multiple periods by transforming the initial graph.


## 1.2. Model

We deal with systems of real-time tasks with precedence and strict periodicity constraints. A taskti (denoted in this paper as (ti:C(ti),T(ti)) is characterized by a period T(ti), a worst case execution time C(ti) with C(ti)≤T(ti), and a start time S(ti).The precedences between tasks are represented by a directed acyclic graph (DAG) denotedG such that G=(𝕍,𝔼). 𝕍 is the set of tasks characterized as above, and 𝔼⊆𝕍×𝕍 the set of edges which represents the precedence (dependence) constraints between tasks. Therefore, the directed pair of tasks (ti,tj)∈𝔼 means that tj must be scheduled, only if ti was already scheduled, and thus we have S(ti)+C(ti)≤S(tj).We assume that periods and WCETs are multiple of a unit of timeU=1 which means that they are integers representing, for example, some cycles of the processor clock. If a task ti with execution time C(ti) is said to start at time unit S(ti), it starts at the beginning of time unit S(ti) and completes before the beginning of time unit S(ti)+C(ti). Thus the time interval where task ti is executed is [S(ti),S(ti)+C(ti)[.


## 2. Real-Time Nonpreemptive Scheduling with Precedence and Strict Periodicity Constraints

In order to satisfy these constraints, the heuristic we propose is divided into three algorithms. These algorithms are called Assignment, Unrolling, and Scheduling.


### 2.1. Assignment

Among the two approaches mentioned below for solving multiprocessor scheduling problems, we chose the partitioned one. Consequently, the first algorithm of the heuristic consists in partitioning tasks over the architecture processors. This first algorithm is called Assignment referring that each task is assigned to a processor such that all tasks assigned to one processor are schedulable on this processor. If a task is schedulable on several processor, it will be assigned to every processor.This algorithm determines if the system is schedulable when all tasks were assigned to the processors, or not schedulable if at least one task was not assigned. The assignment algorithm uses the outcome of the following scheduling analysis.


#### 2.1.1. Scheduling Analysis

The schedulability analysis consists in verifying that a task could be scheduled with other tasks already proved schedulable using the same schedulability analysis. “A schedulable task” means that it exists one or several time intervals on which this task can be scheduled, that is, its period and periods of already schedulable tasks are satisfied.The following theorem gives a necessary and sufficient condition for scheduling two tasks.Theorem 2.1.
Two tasks(ti:C(ti),T(ti)) and (tj:C(tj),T(tj)) are schedulable if and only if
(2.1)C(ti)+C(tj)≤GCD(T(ti),T(tj)).Proof.
Letg=GCD(T(ti),T(tj)) (GCD denotes the greatest common divisor). We start by proving that (2.1) is a sufficient condition. Let us assume that ti and tj are schedulable and that S(ti)=0 and S(tj)=C(ti). Thus, each instance of the task ti is executed within an interval belonging to the set of intervals I1, such that I1={∀k∈ℕ,[kT(ti),kT(ti)+C(ti)[} and each instance of the task tj is executed within an interval belonging to the set of intervals I2, such that I2={∀k∈ℕ,[kT(tj)+C(ti),kT(tj)+C(ti)+C(tj)[}.
We merge the notationg in intervals I1 and I2. I1 may be rewritten in this way: I1={∀k∈ℕ,[gk(T(ti)/g),gk(T(ti)/g)+C(ti)[}, and if n (n∈ℕ) such that n=k(T(tj)/g), then we obtain I1={∀k∈ℕ,[ng,ng+C(ti)[}. Similarly, we find that (m is an integer such as m=k(T(tj)/g)) I2={∀k∈ℕ,[mg+C(ti),mg+C(ti)+C(tj)[}. The assumption made at the beginning (ti and tj are schedulable) implies that no intervals belonging to I1 and I2 overlap. We notice that the starts of the intervals of the set I1 represent multiples of g. On the other hand, the ends of the intervals of the set I2 represent a multiple of (g+C(ti)+C(tj)). Intervals of the sets I1 and I2 do not overlap which means that if (n=m+1) then mg+C(ti)+C(tj)≤ng, which is equivalent to C(ti)+C(tj)≤g. This proves the sufficiency of the condition 1.
In order to prove the necessity of 1, we show that ifC(ti)+C(tj)<g then tasks ti and tj are schedulable. This is equivalent to show that if tasks ti and tj are not schedulable then C(ti)+C(tj)≤g. Without any loss of generality, we assume that S(ti)=0.
ti and tj are not schedulable means that two integers x and y exist such that
(2.2)[xT(ti),xT(ti)+C(ti)[∩[S(tj)+yT(tj),S(tj)+yT(tj)+C(tj)[≠∅;
this is equivalent to
(2.3)[xT(ti)-yT(tj),xT(ti)-yT(tj)+C(ti)[∩[S(tj),S(tj)+C(tj)[≠∅.
According to Bezout theorem, two integersp and q exist such that pT(ti)+qT(tj)=g. By taking x=zp and y=-zq, z∈ℕ we have
(2.4)[zg,zg+C(ti)[∩[S(tj),S(tj)+C(tj)[≠∅.
This latter is true if the length of the empty intervals between the intervals[zg,zg+C(ti)[, z∈ℕ (which is equal to g-C(ti))) is less than the length of the intervals [S(tj),S(tj)+C(tj)[(which is equal to C(tj)). That is, g-C(ti)<C(tj). This condition is equivalent to g<C(ti)+C(tj). This concludes the proof of Theorem 2.1.Now we are interested in the schedulability of a set of tasks (more than two). Let us introduce the following property for a given tasks set.Definition 2.2.
If a set ofn task {∀i∈ℕ,i≤n,(ti:C(ti),T(ti))} such that for each two tasks (ta:C(ta),T(ta)) and (tb:C(tb),T(tb)), GCD(T(ta),T(tb)) is the same, then this set is said to satisfy the SGCD property (SGCD for Same Greater Common Divisor).The following theorem introduces a necessary and sufficient condition for a set of tasks satisfying the SGCD property.Theorem 2.3.
Tasks of a set{∀i∈ℕ,i≤n,(ti:C(ti),T(ti))}, which satisfies the SGCD property, are schedulable if and only if
(2.5)∑i=0nC(ti)≤g;g is the GCD of any pair of tasks from this set.Proof.
In order to prove the sufficiency, we proceed by the same way as in the proof of Theorem2.3. Let us assume that tasks of the set {i∈ℕ*,i≤n,ti} are schedulable and that S(t1)=0 and S(ti)=∑j=1i-1C(tj). Thus each instance of the task ti (i∈ℕ*,i≤n) is executed in an interval belonging to the intervals set Ii={∀k∈ℕ,[kT(ti)+S(ti),kT(ti)+S(ti)+C(ti)[}. Ii may be rewritten in Ii={∀k∈ℕ,[gk(T(ti)/g)+S(ti),k(T(ti)/g)+S(ti)+C(ti)[}. If n is an integer such that n=kT(ti)/g, then we obtain Ii={∀k∈ℕ,[ng+S(ti),ng+S(ti)+C(ti)[}. The assumption made at the beginning (tasks ti are schedulable) implies that no intervals belonging to the sets Ii (i∈ℕ*,i≤n) do not overlap. We notice that the starts of the intervals of the set Ii represent multiples of g. On one hand, the ends of the intervals of the set I2 represent a multiple of g. On the other hand, the ends of the intervals of the set I2 represent a multiple of g+∑i=1nC(ti). Intervals of the sets Ii do not overlap which means that for S(ti) maximal then ng+S(ti)+C(ti)≤(n+1)g+S(t1), which is equivalent to S(ti)+C(ti)≤g. As max(S(ti),i∈ℕ*)=S(tn) we deduce that ∑i=1nC(ti)≤g. This proves the sufficiency of the condition 2.
We prove the necessity of condition 2 by showing that if∑i=1nC(ti)≤g then tasks of the set {∀i∈ℕ*andi≤n,ti} are schedulable. This is equivalent to show that if tasks of the set {∀i∈ℕ*andi≤n,ti} are not schedulable, then g<∑i=1nC(ti). For this we use the proof by induction.
The Base Case
For a set of two tasks this condition was proved in Theorem2.1.The Inductive Step
We show that if the condition 2 is valid for the set{∀i∈ℕandi≤(n-1),ti} then it is the same for the task {∀i∈ℕandi≤n,ti}.
Tasks of the set{∀i∈ℕandi≤n,ti} are not schedulable which means that integers x1,x2,…,xn exist such that
(2.6)([S(t1)+x1T(t1),S(t1)+x1T(t1)+C(t1)[∪⋯∪[S(tn-1)+xn-1T(tn-1),S(tn-1)+xn-1T(tn-1)+C(tn-1)[)∩[S(tn)+xnT(tn),S(tn)+xnT(tn)+C(tn)[≠∅,
which is equivalent to
(2.7)([S(t1)+x1T(t1),S(t1)+x1T(t1)+C(t1)[∩[S(tn)+xnT(tn),S(tn)+xnT(tn)+C(tn)[)∪⋯∪([S(tn-1)+xn-1T(tn-1),S(tn-1)+xn-1T(tn-1)+C(tn-1)[∩[S(tn)+xnT(tn),S(tn)+xnT(tn)+C(tn)[)≠∅.
We can rewrite this latter in the following way:
(2.8)([S(t1)+x1T(t1)-xnT(tn),S(t1)+x1T(t1)-xnT(tn)+C(t1)[∩[S(tn),S(tn)+C(tn)[)∪⋯∪([S(tn-1)+xn-1T(tn-1)-xnT(tn),S(tn-1)+xn-1T(tn-1)-xnT(tn)+C(tn-1)[∩[S(tn),S(tn)+C(tn)[)≠∅.
In addition to, according to Bezout's theorem, pairs of integers(pi,qi) such that piT(ti)+qiT(tn)=g (i=1,…,n-1), with xi=lipi and xn=-liqi (li,…,ln∈ℕ), we obtain
(2.9)([S(t1)+l1g,S(t1)+l1g+C(t1)[∩[S(tn),S(tn)+C(tn)[)∪⋯∪([S(tn-1)+ln-1g,S(tn-1)+ln-1g+C(tn-1)[∩[S(tn),S(tn)+C(tn)[)≠∅.
This may be rewritten in
(2.10)([S(t1)+l1g,S(t1)+l1g+C(t1)[∪⋯∪[S(tn-1)+ln-1g,S(tn-1)+ln-1g+C(tn-1)[)∩[S(tn),S(tn)+C(tn)[≠∅.
This latter is true if the sum of the lengths of empty intervals between the intervals([S(t1)+l1g,S(t1)+l1g+C(t1)[∪⋯∪[S(tn-1)+ln-1g,S(tn-1)+ln-1g+C(tn-1)[) (which is equal to (g-∑i=1n-1C(ti))) is less than the length of intervals [S(tn),S(tn)+C(tn)[ (which is equal to C(tn)),that is, (g-∑i=1n-1C(ti))<C(tn) which is equivalent to g<∑i=1nC(ti). This concludes the proof of Theorem 2.3.Theorem2.3 gives a schedulability condition for the tasks which satisfy the SGCD property (introduced in Definition 2.2). Nevertheless, we need a condition for all tasks whatever their periods are. Unfortunately, this condition does not exist because of the complexity of the problem [13]. As an alternative, we propose the following reasoning.We choose to give a condition which allows to assign one task to a processor where a set of tasks has already been assigned to. This task is called candidate task and once it is assigned another task, among tasks which are not assigned yet, becomes the candidate task. To be assigned to a processor, the candidate task and tasks already assigned to this processor must be schedulable on the same processor.First, we grouped already assigned tasks according to the SGCD property into sets and, second, looked for a condition which takes into account the candidate and each set of already assigned tasks.Before going further we need to introduce the notion of “identical tasks”. Two tasks are said to be identical if they have the same period and the same WCET even though they do not perform the same function.The following theorem introduce an equation allowing to compute the number of the tasks which are identical to the candidate task and can be assigned to a processor. On this processor, a set of tasks satisfying the SGCD property have already been assigned.Theorem 2.4.
Let(tcdt:C(tcdt),T(tcdt)) be the candidate task and {∀i∈ℕ*andi≤n,(ti:C(ti),T(ti))} the set of already assigned tasks which satisfy the SGCD property. The number of identical tasks to the candidate task which can be assigned to this processor is given by
(2.11)Ψ(tcdt)=T(tcdt)GCD(g,T(tcdt))⌊GCD(g,T(tcdt))-∑i=1nC(ti)C(tcdt)⌋.Proof.
⌊(GCD(g,T(tcdt))-∑i=1nC(ti))/C(tcdt)⌋ that represents the number of identical tasks to the candidate task can be scheduled in one interval of length g.T(tcdt)/GCD(g,T(tcdt)) represents the number of intervals of length g in one interval of length T(tcdt).Example 2.5.
Let(ta:1,4), (tb:1,12), and (tc:1,16) be three tasks already assigned. We look for assigning a task (td:1,20). By using Theorem 2.4, we compute the number of tasks identical to td which can be assigned.
First we check that tasksta, tb, tc, and td satisfy the SGCD property.GCD(T(ta),T(tb))=GCD(T(tb),T(tc))=GCD(T(tc),T(ta))=GCD(T(tc),T(td))=GCD(T(tb),T(td))=GCD(T(ta),T(td))=4.
Then,C(ta)+C(tb)+C(tc)+C(td)=4≤4 proves that the condition of Theorem 2.3 is satisfied.
Finally,Ψ(td)=20/4*⌊(4-3)/1⌋=5, which means that 5 tasks identical to td can be scheduled on this processor.
Figure1 shows the 5 intervals where 5 identical tasks to td can be scheduled (these intervals are numbered from 1 to 5). We show also intervals where td cannot be scheduled whereas they are empty, and for each interval the tasks (among ta, tb, and tc) cause the nonschedulability, for example, if tb is mentioned then it means that td cannot be scheduled on this interval because one of the instances of tb and one of the instances of td will be scheduled on the same interval which is not allowed.
Let us check, on Figure1, the result obtained by the previous calculation. We notice that if we divide the time axe in intervals of length equal to GCD=4 and divide each interval in subintervals of length 1, then it is always the fourth subinterval, which is used to schedule td. This means that the order established in the first interval of length GCD=4 is repeated and observed.Figure 1
Several scheduling possibilities of tasktd (Example 2.5).Definition 2.6.
We denote byΩ the set of tasks which have already been assigned to a processor. We divide the set Ω into several subsets {Ω1,Ω2,…,Ωv} such that the tasks of each subset and the task tcdt satisfy the SGCD property (introduced in Definition 2.2). Each subset Ωj is characterized by a greater common divisor (noticed gΩj), and we consider that Ω1 is the subset with the smallest greater common divisor (which is denoted BG). The sum off all execution time of a tasks set Ωj is denoted by C(Ωj)=∑ti∈ΩjC(ti).Now in order to know iftcdt is schedulable or not on a processor where other tasks have already been scheduled, we apply the following algorithm:(1)
choose a processor;(2)
set up sets(∀j),Ωj;(3)
computeΨΩ1(tcdt). This represent the identical tasks to tcdt which can be scheduled by taking into account only Ω1;(4)
for each subset (j>1),  Ωj remove to the result obtained in the previous step the number of identical tasks to tcdt which cannot be scheduled because of nonschedulability with tasks belonging to Ωj (the next theorem gives a way to compute this number);(5)
following the reached result, we decide to assigntcdt to this processor or try to assign it to another processor (go to 1).LetΓΩj(tcdt) (j≠1) represent the number of identical tasks to tcdt that cannot be scheduled because of a non-schedulability with tasks belonging to Ωj (j≠1).The following theorem gives an equation to computeΓ.Theorem 2.7.
Lettcdt be the candidate task, Ω={Ω1,Ω2,…,Ωv} the set of already scheduled tasks, and gΩj the GCD of all Ωj. For (j>1), ΓΩj(tcdt) is given by
(2.12)ΓΩj(tcdt)=T(tcdt)gΩj⌈∑ti∈ΩjC(tcdt)⌉α
such that
(2.13)α={1ifT(tcdt)gΩj>1,0ifT(tcdt)gΩj=1and∑ti∈ΩC(ti)<gΩj-1-C(tcdt).Proof.
T(tcdt)/gΩj is the number of intervals of length gΩj in an interval of length T(tcdt). This number is multiplied by ⌈∑ti∈Ωj/C(tcdt)⌉ which represents the number of tasks identical to tcdt that cannot be scheduled inside an interval the length of which is equal to gΩj. And also, in order to take into account the tasks of the other sets, we introduce the value of α.Now we bring together the different results obtained previously to find out an equation which allows to compute the number of schedulable tasks identical totcdt, and hence deduce if tcdt is schedulable or not.Corollary 2.8.
Lettcdt be the candidate task and Ω={Ω1,Ω2,…,Ωv} the set of already scheduled tasks. The number of identical tasks to tcdt which can be scheduled is given by
(2.14)ΨΩ1(tcdt)-∑j=2vΓΩj(tcdt)
such that
(2.15)ΨΩ1(tcdt)=T(tcdt)BG⌊BG-C(Ω1)C(tcdt)⌋.Example 2.9.
In order to illustrate the proposed method, we propose the following example: let(tcdt:2,30) to the candidate task to the schedulability analysis. Let Ω={(ta:2,5),(tb:1,10),(tc:1,20),(td:1,30),(te:1,60)} the set of tasks already proved schedulable. In this case, BG=GCD(T(ta),T(tb),T(tc),T(td),T(te),T(tcdt))=5(i)
the three subsets that we can set up from the setΩ and the task tcdt according to the SGCD property are
(1)
Ω1={tcdt,ta} with the GCD of periods equal to 5,(2)
Ω2={tcdt,tb,tc} with the GCD of periods equal to 10,(3)
Ω3={tcdt,td,te} with the GCD of periods equal to 30.(ii)
From Corollary2.8,
(2.16)ΨΩ1=305⌊5-22⌋=6,(iii)
Γ=ΓΩ2+ΓΩ3,
(1)
ΓΩ2=((30/10)⌈3/2⌉)= 3,(2)
by the same wayΓΩ3=0, so Γ=3+0=3,(iv)
thenΨΩ1-Γ=6-3=3, from this, we deduce that tcdt is schedulable.Remark 2.10.
The previous result allows us to assign several tasks (identical tasks totcdt) at the same times, and if other identical tasks to tcdt are not assigned then it means that these tasks are not schedulable on this processor and they must be assigned to another processor.Remark 2.11.
Notice that, throughout this schedulability analysis, in the given schedulability condition nothing is mentioned about precedence constraints, whereas we allow it in the tasks model. Indeed, a system with precedence constraints but without any periodicity constraint is always schedulable. The next theorem demonstrates that for a set of proved schedulable tasks, that is, satisfying periodicity constraints, it always exists a scheduling of these tasks which satisfies precedences between them, whatever the precedences are.Theorem 2.12.
LetΩ be a set of proved schedulable tasks. Whatever precedence constraints between Ω's tasks are, it exists, at least, one scheduling which satisfies these precedence constraints.Proof.
Once a set ofn tasks is proved schedulable, these tasks can be scheduled in n! different ways or orders. From these n! orders, at least, one order satisfies the precedence constraints (we remind that tasks are not allowed to be preempted).


#### 2.1.2. Proposed Approaches

As a result of the previous study, we are able to yield an algorithm allowing the assignment of tasks to processors while satisfying precedence and periodicity constraints. Since the corollary condition is monoprocessor and it is applied for the assignment of each task (the test may be done several time until finding the right processor), the execution time of the assignment algorithm can have be long. Hence, we propose three assignment algorithms as follows:(1)
greedy algorithm: it starts by sorting tasks following a mixed sort which takes into account both the increasing order and a priority level [14]. Then tasks are assigned without any backtracking;(2)
local search algorithm: it uses the condition of the corollary. In order to have an assignment more efficient than the one of the greedy heuristic, we introduce a backtracking process. It is used once a task cannot be assigned to any processor, however, by taking off some assigned tasks from their processors until this task could be assigned and taken off tasks will be assigned to another processors. This backtracking does not change all the assignment but only a part that should not considerably increase the algorithm execution time;(3)
exact algorithm (optimal): it uses the condition of the corollary. This algorithm takes advantage of the Branch & Cut exact method [14].


### 2.2. Unrolling

The unrolling algorithm consists in repeating each task of the graph(hp/T) times, where the period of this task is T and hp is the hyper-period (Least Common Multiple of all period tasks) [15].When two tasks are dependent and have not the same period, there are two possibilities. If the period of the consumer task is equal ton times the period of the producer task, then the producer task must be executed n times compared to the consumer task, and the consumer task cannot start its execution until it has received all data from the n executions of the producer task. Notice that the produced data differ from one execution of the producer task to another execution; therefore, data are not duplicated. Reciprocally, if the period of the producer task, is equal to n times the period of the consumer task then the consumer task must be executed n times compared to the producer task. The unrolling algorithm exploits this data transfer mechanism.


### 2.3. Scheduling

This algorithm distributes and schedules each task of the unrolled graph onto the processor where it has been assigned by the assignment algorithm. In case where the task was assigned to several processors; the algorithm distributes it to the processor which minimizes the makespan. The minimization of the makespan is based on a cost function which takes into account the WCETs of tasks and the communication costs due to dependant tasks scheduled on different processors.Once a task is scheduled all its instances take start times computed in function of the task period and the number of the instance. In addition, to be scheduled, the first instance of each task must satisfy the condition of the next theorem.Theorem 2.13.
Let{(ti:C(ti),T(ti),S(ti)),i=1⋯n} be n tasks already scheduled on a processor. The task {(tj:C(tj),T(tj)} is schedulable at the date S(tj) on this processor if and only if
(2.17)∀i,S(ti)≤(S(tj)-S(ti))mod⁡gi≤(gi-C(tj))
such that gi=GCD(T(ti),T(tj)).Proof.
In order to prove Theorem2.13, it suffices to prove that two tasks {(ta:C(ta),T(ta),S(ta))} and {(tb:C(tb),T(tb),S(tb))} (and g=GCD(T(ta),T(tb))) are schedulable if and only if
(2.18)C(ta)≤(S(tb)-S(ta))mod⁡g≤(g-C(tb)).
Without any loss of generality, we assume that S(ta)=0. We start by showing the sufficiency of the Condition 5. Let us consider time intervals I={∀l∈ℕ,[0+lg,g-1+lg]. The first C(ta) time units of each of these intervals can be allocated for executions of ta once every T(ta)/g intervals, and the remaining g-C(ta) time units only or partly for executions of tb once every T(tb)/g intervals. If (2.18) is verified, then the allocated time units suffice to execute ta and tb.
In order to prove the necessity of (2.18), let us consider again time intervals {∀l∈ℕ,[0+lg,g-1+lg]. If (2.18) is not verified, then the execution of tb overlaps the first C(ta) time units once every T(tb)/g time intervals. We also note that the C(ta) time units of the intervals are used to execute ta once every T(ta)/g time intervals. As gcd(T(ta)/g,T(tb)/g)=1, there will be an interval from I where ta and tb are executed together. Hence, if (2.18) is not verified, the tasks ta and tb cannot be scheduled on the same processor. This completes the proof of the theorem.A complete example of the scheduling heuristic can be found in [14].


## 2.1. Assignment

Among the two approaches mentioned below for solving multiprocessor scheduling problems, we chose the partitioned one. Consequently, the first algorithm of the heuristic consists in partitioning tasks over the architecture processors. This first algorithm is called Assignment referring that each task is assigned to a processor such that all tasks assigned to one processor are schedulable on this processor. If a task is schedulable on several processor, it will be assigned to every processor.This algorithm determines if the system is schedulable when all tasks were assigned to the processors, or not schedulable if at least one task was not assigned. The assignment algorithm uses the outcome of the following scheduling analysis.


### 2.1.1. Scheduling Analysis

The schedulability analysis consists in verifying that a task could be scheduled with other tasks already proved schedulable using the same schedulability analysis. “A schedulable task” means that it exists one or several time intervals on which this task can be scheduled, that is, its period and periods of already schedulable tasks are satisfied.The following theorem gives a necessary and sufficient condition for scheduling two tasks.Theorem 2.1.
Two tasks(ti:C(ti),T(ti)) and (tj:C(tj),T(tj)) are schedulable if and only if
(2.1)C(ti)+C(tj)≤GCD(T(ti),T(tj)).Proof.
Letg=GCD(T(ti),T(tj)) (GCD denotes the greatest common divisor). We start by proving that (2.1) is a sufficient condition. Let us assume that ti and tj are schedulable and that S(ti)=0 and S(tj)=C(ti). Thus, each instance of the task ti is executed within an interval belonging to the set of intervals I1, such that I1={∀k∈ℕ,[kT(ti),kT(ti)+C(ti)[} and each instance of the task tj is executed within an interval belonging to the set of intervals I2, such that I2={∀k∈ℕ,[kT(tj)+C(ti),kT(tj)+C(ti)+C(tj)[}.
We merge the notationg in intervals I1 and I2. I1 may be rewritten in this way: I1={∀k∈ℕ,[gk(T(ti)/g),gk(T(ti)/g)+C(ti)[}, and if n (n∈ℕ) such that n=k(T(tj)/g), then we obtain I1={∀k∈ℕ,[ng,ng+C(ti)[}. Similarly, we find that (m is an integer such as m=k(T(tj)/g)) I2={∀k∈ℕ,[mg+C(ti),mg+C(ti)+C(tj)[}. The assumption made at the beginning (ti and tj are schedulable) implies that no intervals belonging to I1 and I2 overlap. We notice that the starts of the intervals of the set I1 represent multiples of g. On the other hand, the ends of the intervals of the set I2 represent a multiple of (g+C(ti)+C(tj)). Intervals of the sets I1 and I2 do not overlap which means that if (n=m+1) then mg+C(ti)+C(tj)≤ng, which is equivalent to C(ti)+C(tj)≤g. This proves the sufficiency of the condition 1.
In order to prove the necessity of 1, we show that ifC(ti)+C(tj)<g then tasks ti and tj are schedulable. This is equivalent to show that if tasks ti and tj are not schedulable then C(ti)+C(tj)≤g. Without any loss of generality, we assume that S(ti)=0.
ti and tj are not schedulable means that two integers x and y exist such that
(2.2)[xT(ti),xT(ti)+C(ti)[∩[S(tj)+yT(tj),S(tj)+yT(tj)+C(tj)[≠∅;
this is equivalent to
(2.3)[xT(ti)-yT(tj),xT(ti)-yT(tj)+C(ti)[∩[S(tj),S(tj)+C(tj)[≠∅.
According to Bezout theorem, two integersp and q exist such that pT(ti)+qT(tj)=g. By taking x=zp and y=-zq, z∈ℕ we have
(2.4)[zg,zg+C(ti)[∩[S(tj),S(tj)+C(tj)[≠∅.
This latter is true if the length of the empty intervals between the intervals[zg,zg+C(ti)[, z∈ℕ (which is equal to g-C(ti))) is less than the length of the intervals [S(tj),S(tj)+C(tj)[(which is equal to C(tj)). That is, g-C(ti)<C(tj). This condition is equivalent to g<C(ti)+C(tj). This concludes the proof of Theorem 2.1.Now we are interested in the schedulability of a set of tasks (more than two). Let us introduce the following property for a given tasks set.Definition 2.2.
If a set ofn task {∀i∈ℕ,i≤n,(ti:C(ti),T(ti))} such that for each two tasks (ta:C(ta),T(ta)) and (tb:C(tb),T(tb)), GCD(T(ta),T(tb)) is the same, then this set is said to satisfy the SGCD property (SGCD for Same Greater Common Divisor).The following theorem introduces a necessary and sufficient condition for a set of tasks satisfying the SGCD property.Theorem 2.3.
Tasks of a set{∀i∈ℕ,i≤n,(ti:C(ti),T(ti))}, which satisfies the SGCD property, are schedulable if and only if
(2.5)∑i=0nC(ti)≤g;g is the GCD of any pair of tasks from this set.Proof.
In order to prove the sufficiency, we proceed by the same way as in the proof of Theorem2.3. Let us assume that tasks of the set {i∈ℕ*,i≤n,ti} are schedulable and that S(t1)=0 and S(ti)=∑j=1i-1C(tj). Thus each instance of the task ti (i∈ℕ*,i≤n) is executed in an interval belonging to the intervals set Ii={∀k∈ℕ,[kT(ti)+S(ti),kT(ti)+S(ti)+C(ti)[}. Ii may be rewritten in Ii={∀k∈ℕ,[gk(T(ti)/g)+S(ti),k(T(ti)/g)+S(ti)+C(ti)[}. If n is an integer such that n=kT(ti)/g, then we obtain Ii={∀k∈ℕ,[ng+S(ti),ng+S(ti)+C(ti)[}. The assumption made at the beginning (tasks ti are schedulable) implies that no intervals belonging to the sets Ii (i∈ℕ*,i≤n) do not overlap. We notice that the starts of the intervals of the set Ii represent multiples of g. On one hand, the ends of the intervals of the set I2 represent a multiple of g. On the other hand, the ends of the intervals of the set I2 represent a multiple of g+∑i=1nC(ti). Intervals of the sets Ii do not overlap which means that for S(ti) maximal then ng+S(ti)+C(ti)≤(n+1)g+S(t1), which is equivalent to S(ti)+C(ti)≤g. As max(S(ti),i∈ℕ*)=S(tn) we deduce that ∑i=1nC(ti)≤g. This proves the sufficiency of the condition 2.
We prove the necessity of condition 2 by showing that if∑i=1nC(ti)≤g then tasks of the set {∀i∈ℕ*andi≤n,ti} are schedulable. This is equivalent to show that if tasks of the set {∀i∈ℕ*andi≤n,ti} are not schedulable, then g<∑i=1nC(ti). For this we use the proof by induction.
The Base Case
For a set of two tasks this condition was proved in Theorem2.1.The Inductive Step
We show that if the condition 2 is valid for the set{∀i∈ℕandi≤(n-1),ti} then it is the same for the task {∀i∈ℕandi≤n,ti}.
Tasks of the set{∀i∈ℕandi≤n,ti} are not schedulable which means that integers x1,x2,…,xn exist such that
(2.6)([S(t1)+x1T(t1),S(t1)+x1T(t1)+C(t1)[∪⋯∪[S(tn-1)+xn-1T(tn-1),S(tn-1)+xn-1T(tn-1)+C(tn-1)[)∩[S(tn)+xnT(tn),S(tn)+xnT(tn)+C(tn)[≠∅,
which is equivalent to
(2.7)([S(t1)+x1T(t1),S(t1)+x1T(t1)+C(t1)[∩[S(tn)+xnT(tn),S(tn)+xnT(tn)+C(tn)[)∪⋯∪([S(tn-1)+xn-1T(tn-1),S(tn-1)+xn-1T(tn-1)+C(tn-1)[∩[S(tn)+xnT(tn),S(tn)+xnT(tn)+C(tn)[)≠∅.
We can rewrite this latter in the following way:
(2.8)([S(t1)+x1T(t1)-xnT(tn),S(t1)+x1T(t1)-xnT(tn)+C(t1)[∩[S(tn),S(tn)+C(tn)[)∪⋯∪([S(tn-1)+xn-1T(tn-1)-xnT(tn),S(tn-1)+xn-1T(tn-1)-xnT(tn)+C(tn-1)[∩[S(tn),S(tn)+C(tn)[)≠∅.
In addition to, according to Bezout's theorem, pairs of integers(pi,qi) such that piT(ti)+qiT(tn)=g (i=1,…,n-1), with xi=lipi and xn=-liqi (li,…,ln∈ℕ), we obtain
(2.9)([S(t1)+l1g,S(t1)+l1g+C(t1)[∩[S(tn),S(tn)+C(tn)[)∪⋯∪([S(tn-1)+ln-1g,S(tn-1)+ln-1g+C(tn-1)[∩[S(tn),S(tn)+C(tn)[)≠∅.
This may be rewritten in
(2.10)([S(t1)+l1g,S(t1)+l1g+C(t1)[∪⋯∪[S(tn-1)+ln-1g,S(tn-1)+ln-1g+C(tn-1)[)∩[S(tn),S(tn)+C(tn)[≠∅.
This latter is true if the sum of the lengths of empty intervals between the intervals([S(t1)+l1g,S(t1)+l1g+C(t1)[∪⋯∪[S(tn-1)+ln-1g,S(tn-1)+ln-1g+C(tn-1)[) (which is equal to (g-∑i=1n-1C(ti))) is less than the length of intervals [S(tn),S(tn)+C(tn)[ (which is equal to C(tn)),that is, (g-∑i=1n-1C(ti))<C(tn) which is equivalent to g<∑i=1nC(ti). This concludes the proof of Theorem 2.3.Theorem2.3 gives a schedulability condition for the tasks which satisfy the SGCD property (introduced in Definition 2.2). Nevertheless, we need a condition for all tasks whatever their periods are. Unfortunately, this condition does not exist because of the complexity of the problem [13]. As an alternative, we propose the following reasoning.We choose to give a condition which allows to assign one task to a processor where a set of tasks has already been assigned to. This task is called candidate task and once it is assigned another task, among tasks which are not assigned yet, becomes the candidate task. To be assigned to a processor, the candidate task and tasks already assigned to this processor must be schedulable on the same processor.First, we grouped already assigned tasks according to the SGCD property into sets and, second, looked for a condition which takes into account the candidate and each set of already assigned tasks.Before going further we need to introduce the notion of “identical tasks”. Two tasks are said to be identical if they have the same period and the same WCET even though they do not perform the same function.The following theorem introduce an equation allowing to compute the number of the tasks which are identical to the candidate task and can be assigned to a processor. On this processor, a set of tasks satisfying the SGCD property have already been assigned.Theorem 2.4.
Let(tcdt:C(tcdt),T(tcdt)) be the candidate task and {∀i∈ℕ*andi≤n,(ti:C(ti),T(ti))} the set of already assigned tasks which satisfy the SGCD property. The number of identical tasks to the candidate task which can be assigned to this processor is given by
(2.11)Ψ(tcdt)=T(tcdt)GCD(g,T(tcdt))⌊GCD(g,T(tcdt))-∑i=1nC(ti)C(tcdt)⌋.Proof.
⌊(GCD(g,T(tcdt))-∑i=1nC(ti))/C(tcdt)⌋ that represents the number of identical tasks to the candidate task can be scheduled in one interval of length g.T(tcdt)/GCD(g,T(tcdt)) represents the number of intervals of length g in one interval of length T(tcdt).Example 2.5.
Let(ta:1,4), (tb:1,12), and (tc:1,16) be three tasks already assigned. We look for assigning a task (td:1,20). By using Theorem 2.4, we compute the number of tasks identical to td which can be assigned.
First we check that tasksta, tb, tc, and td satisfy the SGCD property.GCD(T(ta),T(tb))=GCD(T(tb),T(tc))=GCD(T(tc),T(ta))=GCD(T(tc),T(td))=GCD(T(tb),T(td))=GCD(T(ta),T(td))=4.
Then,C(ta)+C(tb)+C(tc)+C(td)=4≤4 proves that the condition of Theorem 2.3 is satisfied.
Finally,Ψ(td)=20/4*⌊(4-3)/1⌋=5, which means that 5 tasks identical to td can be scheduled on this processor.
Figure1 shows the 5 intervals where 5 identical tasks to td can be scheduled (these intervals are numbered from 1 to 5). We show also intervals where td cannot be scheduled whereas they are empty, and for each interval the tasks (among ta, tb, and tc) cause the nonschedulability, for example, if tb is mentioned then it means that td cannot be scheduled on this interval because one of the instances of tb and one of the instances of td will be scheduled on the same interval which is not allowed.
Let us check, on Figure1, the result obtained by the previous calculation. We notice that if we divide the time axe in intervals of length equal to GCD=4 and divide each interval in subintervals of length 1, then it is always the fourth subinterval, which is used to schedule td. This means that the order established in the first interval of length GCD=4 is repeated and observed.Figure 1
Several scheduling possibilities of tasktd (Example 2.5).Definition 2.6.
We denote byΩ the set of tasks which have already been assigned to a processor. We divide the set Ω into several subsets {Ω1,Ω2,…,Ωv} such that the tasks of each subset and the task tcdt satisfy the SGCD property (introduced in Definition 2.2). Each subset Ωj is characterized by a greater common divisor (noticed gΩj), and we consider that Ω1 is the subset with the smallest greater common divisor (which is denoted BG). The sum off all execution time of a tasks set Ωj is denoted by C(Ωj)=∑ti∈ΩjC(ti).Now in order to know iftcdt is schedulable or not on a processor where other tasks have already been scheduled, we apply the following algorithm:(1)
choose a processor;(2)
set up sets(∀j),Ωj;(3)
computeΨΩ1(tcdt). This represent the identical tasks to tcdt which can be scheduled by taking into account only Ω1;(4)
for each subset (j>1),  Ωj remove to the result obtained in the previous step the number of identical tasks to tcdt which cannot be scheduled because of nonschedulability with tasks belonging to Ωj (the next theorem gives a way to compute this number);(5)
following the reached result, we decide to assigntcdt to this processor or try to assign it to another processor (go to 1).LetΓΩj(tcdt) (j≠1) represent the number of identical tasks to tcdt that cannot be scheduled because of a non-schedulability with tasks belonging to Ωj (j≠1).The following theorem gives an equation to computeΓ.Theorem 2.7.
Lettcdt be the candidate task, Ω={Ω1,Ω2,…,Ωv} the set of already scheduled tasks, and gΩj the GCD of all Ωj. For (j>1), ΓΩj(tcdt) is given by
(2.12)ΓΩj(tcdt)=T(tcdt)gΩj⌈∑ti∈ΩjC(tcdt)⌉α
such that
(2.13)α={1ifT(tcdt)gΩj>1,0ifT(tcdt)gΩj=1and∑ti∈ΩC(ti)<gΩj-1-C(tcdt).Proof.
T(tcdt)/gΩj is the number of intervals of length gΩj in an interval of length T(tcdt). This number is multiplied by ⌈∑ti∈Ωj/C(tcdt)⌉ which represents the number of tasks identical to tcdt that cannot be scheduled inside an interval the length of which is equal to gΩj. And also, in order to take into account the tasks of the other sets, we introduce the value of α.Now we bring together the different results obtained previously to find out an equation which allows to compute the number of schedulable tasks identical totcdt, and hence deduce if tcdt is schedulable or not.Corollary 2.8.
Lettcdt be the candidate task and Ω={Ω1,Ω2,…,Ωv} the set of already scheduled tasks. The number of identical tasks to tcdt which can be scheduled is given by
(2.14)ΨΩ1(tcdt)-∑j=2vΓΩj(tcdt)
such that
(2.15)ΨΩ1(tcdt)=T(tcdt)BG⌊BG-C(Ω1)C(tcdt)⌋.Example 2.9.
In order to illustrate the proposed method, we propose the following example: let(tcdt:2,30) to the candidate task to the schedulability analysis. Let Ω={(ta:2,5),(tb:1,10),(tc:1,20),(td:1,30),(te:1,60)} the set of tasks already proved schedulable. In this case, BG=GCD(T(ta),T(tb),T(tc),T(td),T(te),T(tcdt))=5(i)
the three subsets that we can set up from the setΩ and the task tcdt according to the SGCD property are
(1)
Ω1={tcdt,ta} with the GCD of periods equal to 5,(2)
Ω2={tcdt,tb,tc} with the GCD of periods equal to 10,(3)
Ω3={tcdt,td,te} with the GCD of periods equal to 30.(ii)
From Corollary2.8,
(2.16)ΨΩ1=305⌊5-22⌋=6,(iii)
Γ=ΓΩ2+ΓΩ3,
(1)
ΓΩ2=((30/10)⌈3/2⌉)= 3,(2)
by the same wayΓΩ3=0, so Γ=3+0=3,(iv)
thenΨΩ1-Γ=6-3=3, from this, we deduce that tcdt is schedulable.Remark 2.10.
The previous result allows us to assign several tasks (identical tasks totcdt) at the same times, and if other identical tasks to tcdt are not assigned then it means that these tasks are not schedulable on this processor and they must be assigned to another processor.Remark 2.11.
Notice that, throughout this schedulability analysis, in the given schedulability condition nothing is mentioned about precedence constraints, whereas we allow it in the tasks model. Indeed, a system with precedence constraints but without any periodicity constraint is always schedulable. The next theorem demonstrates that for a set of proved schedulable tasks, that is, satisfying periodicity constraints, it always exists a scheduling of these tasks which satisfies precedences between them, whatever the precedences are.Theorem 2.12.
LetΩ be a set of proved schedulable tasks. Whatever precedence constraints between Ω's tasks are, it exists, at least, one scheduling which satisfies these precedence constraints.Proof.
Once a set ofn tasks is proved schedulable, these tasks can be scheduled in n! different ways or orders. From these n! orders, at least, one order satisfies the precedence constraints (we remind that tasks are not allowed to be preempted).


### 2.1.2. Proposed Approaches

As a result of the previous study, we are able to yield an algorithm allowing the assignment of tasks to processors while satisfying precedence and periodicity constraints. Since the corollary condition is monoprocessor and it is applied for the assignment of each task (the test may be done several time until finding the right processor), the execution time of the assignment algorithm can have be long. Hence, we propose three assignment algorithms as follows:(1)
greedy algorithm: it starts by sorting tasks following a mixed sort which takes into account both the increasing order and a priority level [14]. Then tasks are assigned without any backtracking;(2)
local search algorithm: it uses the condition of the corollary. In order to have an assignment more efficient than the one of the greedy heuristic, we introduce a backtracking process. It is used once a task cannot be assigned to any processor, however, by taking off some assigned tasks from their processors until this task could be assigned and taken off tasks will be assigned to another processors. This backtracking does not change all the assignment but only a part that should not considerably increase the algorithm execution time;(3)
exact algorithm (optimal): it uses the condition of the corollary. This algorithm takes advantage of the Branch & Cut exact method [14].


## 2.1.1. Scheduling Analysis

The schedulability analysis consists in verifying that a task could be scheduled with other tasks already proved schedulable using the same schedulability analysis. “A schedulable task” means that it exists one or several time intervals on which this task can be scheduled, that is, its period and periods of already schedulable tasks are satisfied.The following theorem gives a necessary and sufficient condition for scheduling two tasks.Theorem 2.1.
Two tasks(ti:C(ti),T(ti)) and (tj:C(tj),T(tj)) are schedulable if and only if
(2.1)C(ti)+C(tj)≤GCD(T(ti),T(tj)).Proof.
Letg=GCD(T(ti),T(tj)) (GCD denotes the greatest common divisor). We start by proving that (2.1) is a sufficient condition. Let us assume that ti and tj are schedulable and that S(ti)=0 and S(tj)=C(ti). Thus, each instance of the task ti is executed within an interval belonging to the set of intervals I1, such that I1={∀k∈ℕ,[kT(ti),kT(ti)+C(ti)[} and each instance of the task tj is executed within an interval belonging to the set of intervals I2, such that I2={∀k∈ℕ,[kT(tj)+C(ti),kT(tj)+C(ti)+C(tj)[}.
We merge the notationg in intervals I1 and I2. I1 may be rewritten in this way: I1={∀k∈ℕ,[gk(T(ti)/g),gk(T(ti)/g)+C(ti)[}, and if n (n∈ℕ) such that n=k(T(tj)/g), then we obtain I1={∀k∈ℕ,[ng,ng+C(ti)[}. Similarly, we find that (m is an integer such as m=k(T(tj)/g)) I2={∀k∈ℕ,[mg+C(ti),mg+C(ti)+C(tj)[}. The assumption made at the beginning (ti and tj are schedulable) implies that no intervals belonging to I1 and I2 overlap. We notice that the starts of the intervals of the set I1 represent multiples of g. On the other hand, the ends of the intervals of the set I2 represent a multiple of (g+C(ti)+C(tj)). Intervals of the sets I1 and I2 do not overlap which means that if (n=m+1) then mg+C(ti)+C(tj)≤ng, which is equivalent to C(ti)+C(tj)≤g. This proves the sufficiency of the condition 1.
In order to prove the necessity of 1, we show that ifC(ti)+C(tj)<g then tasks ti and tj are schedulable. This is equivalent to show that if tasks ti and tj are not schedulable then C(ti)+C(tj)≤g. Without any loss of generality, we assume that S(ti)=0.
ti and tj are not schedulable means that two integers x and y exist such that
(2.2)[xT(ti),xT(ti)+C(ti)[∩[S(tj)+yT(tj),S(tj)+yT(tj)+C(tj)[≠∅;
this is equivalent to
(2.3)[xT(ti)-yT(tj),xT(ti)-yT(tj)+C(ti)[∩[S(tj),S(tj)+C(tj)[≠∅.
According to Bezout theorem, two integersp and q exist such that pT(ti)+qT(tj)=g. By taking x=zp and y=-zq, z∈ℕ we have
(2.4)[zg,zg+C(ti)[∩[S(tj),S(tj)+C(tj)[≠∅.
This latter is true if the length of the empty intervals between the intervals[zg,zg+C(ti)[, z∈ℕ (which is equal to g-C(ti))) is less than the length of the intervals [S(tj),S(tj)+C(tj)[(which is equal to C(tj)). That is, g-C(ti)<C(tj). This condition is equivalent to g<C(ti)+C(tj). This concludes the proof of Theorem 2.1.Now we are interested in the schedulability of a set of tasks (more than two). Let us introduce the following property for a given tasks set.Definition 2.2.
If a set ofn task {∀i∈ℕ,i≤n,(ti:C(ti),T(ti))} such that for each two tasks (ta:C(ta),T(ta)) and (tb:C(tb),T(tb)), GCD(T(ta),T(tb)) is the same, then this set is said to satisfy the SGCD property (SGCD for Same Greater Common Divisor).The following theorem introduces a necessary and sufficient condition for a set of tasks satisfying the SGCD property.Theorem 2.3.
Tasks of a set{∀i∈ℕ,i≤n,(ti:C(ti),T(ti))}, which satisfies the SGCD property, are schedulable if and only if
(2.5)∑i=0nC(ti)≤g;g is the GCD of any pair of tasks from this set.Proof.
In order to prove the sufficiency, we proceed by the same way as in the proof of Theorem2.3. Let us assume that tasks of the set {i∈ℕ*,i≤n,ti} are schedulable and that S(t1)=0 and S(ti)=∑j=1i-1C(tj). Thus each instance of the task ti (i∈ℕ*,i≤n) is executed in an interval belonging to the intervals set Ii={∀k∈ℕ,[kT(ti)+S(ti),kT(ti)+S(ti)+C(ti)[}. Ii may be rewritten in Ii={∀k∈ℕ,[gk(T(ti)/g)+S(ti),k(T(ti)/g)+S(ti)+C(ti)[}. If n is an integer such that n=kT(ti)/g, then we obtain Ii={∀k∈ℕ,[ng+S(ti),ng+S(ti)+C(ti)[}. The assumption made at the beginning (tasks ti are schedulable) implies that no intervals belonging to the sets Ii (i∈ℕ*,i≤n) do not overlap. We notice that the starts of the intervals of the set Ii represent multiples of g. On one hand, the ends of the intervals of the set I2 represent a multiple of g. On the other hand, the ends of the intervals of the set I2 represent a multiple of g+∑i=1nC(ti). Intervals of the sets Ii do not overlap which means that for S(ti) maximal then ng+S(ti)+C(ti)≤(n+1)g+S(t1), which is equivalent to S(ti)+C(ti)≤g. As max(S(ti),i∈ℕ*)=S(tn) we deduce that ∑i=1nC(ti)≤g. This proves the sufficiency of the condition 2.
We prove the necessity of condition 2 by showing that if∑i=1nC(ti)≤g then tasks of the set {∀i∈ℕ*andi≤n,ti} are schedulable. This is equivalent to show that if tasks of the set {∀i∈ℕ*andi≤n,ti} are not schedulable, then g<∑i=1nC(ti). For this we use the proof by induction.
The Base Case
For a set of two tasks this condition was proved in Theorem2.1.The Inductive Step
We show that if the condition 2 is valid for the set{∀i∈ℕandi≤(n-1),ti} then it is the same for the task {∀i∈ℕandi≤n,ti}.
Tasks of the set{∀i∈ℕandi≤n,ti} are not schedulable which means that integers x1,x2,…,xn exist such that
(2.6)([S(t1)+x1T(t1),S(t1)+x1T(t1)+C(t1)[∪⋯∪[S(tn-1)+xn-1T(tn-1),S(tn-1)+xn-1T(tn-1)+C(tn-1)[)∩[S(tn)+xnT(tn),S(tn)+xnT(tn)+C(tn)[≠∅,
which is equivalent to
(2.7)([S(t1)+x1T(t1),S(t1)+x1T(t1)+C(t1)[∩[S(tn)+xnT(tn),S(tn)+xnT(tn)+C(tn)[)∪⋯∪([S(tn-1)+xn-1T(tn-1),S(tn-1)+xn-1T(tn-1)+C(tn-1)[∩[S(tn)+xnT(tn),S(tn)+xnT(tn)+C(tn)[)≠∅.
We can rewrite this latter in the following way:
(2.8)([S(t1)+x1T(t1)-xnT(tn),S(t1)+x1T(t1)-xnT(tn)+C(t1)[∩[S(tn),S(tn)+C(tn)[)∪⋯∪([S(tn-1)+xn-1T(tn-1)-xnT(tn),S(tn-1)+xn-1T(tn-1)-xnT(tn)+C(tn-1)[∩[S(tn),S(tn)+C(tn)[)≠∅.
In addition to, according to Bezout's theorem, pairs of integers(pi,qi) such that piT(ti)+qiT(tn)=g (i=1,…,n-1), with xi=lipi and xn=-liqi (li,…,ln∈ℕ), we obtain
(2.9)([S(t1)+l1g,S(t1)+l1g+C(t1)[∩[S(tn),S(tn)+C(tn)[)∪⋯∪([S(tn-1)+ln-1g,S(tn-1)+ln-1g+C(tn-1)[∩[S(tn),S(tn)+C(tn)[)≠∅.
This may be rewritten in
(2.10)([S(t1)+l1g,S(t1)+l1g+C(t1)[∪⋯∪[S(tn-1)+ln-1g,S(tn-1)+ln-1g+C(tn-1)[)∩[S(tn),S(tn)+C(tn)[≠∅.
This latter is true if the sum of the lengths of empty intervals between the intervals([S(t1)+l1g,S(t1)+l1g+C(t1)[∪⋯∪[S(tn-1)+ln-1g,S(tn-1)+ln-1g+C(tn-1)[) (which is equal to (g-∑i=1n-1C(ti))) is less than the length of intervals [S(tn),S(tn)+C(tn)[ (which is equal to C(tn)),that is, (g-∑i=1n-1C(ti))<C(tn) which is equivalent to g<∑i=1nC(ti). This concludes the proof of Theorem 2.3.Theorem2.3 gives a schedulability condition for the tasks which satisfy the SGCD property (introduced in Definition 2.2). Nevertheless, we need a condition for all tasks whatever their periods are. Unfortunately, this condition does not exist because of the complexity of the problem [13]. As an alternative, we propose the following reasoning.We choose to give a condition which allows to assign one task to a processor where a set of tasks has already been assigned to. This task is called candidate task and once it is assigned another task, among tasks which are not assigned yet, becomes the candidate task. To be assigned to a processor, the candidate task and tasks already assigned to this processor must be schedulable on the same processor.First, we grouped already assigned tasks according to the SGCD property into sets and, second, looked for a condition which takes into account the candidate and each set of already assigned tasks.Before going further we need to introduce the notion of “identical tasks”. Two tasks are said to be identical if they have the same period and the same WCET even though they do not perform the same function.The following theorem introduce an equation allowing to compute the number of the tasks which are identical to the candidate task and can be assigned to a processor. On this processor, a set of tasks satisfying the SGCD property have already been assigned.Theorem 2.4.
Let(tcdt:C(tcdt),T(tcdt)) be the candidate task and {∀i∈ℕ*andi≤n,(ti:C(ti),T(ti))} the set of already assigned tasks which satisfy the SGCD property. The number of identical tasks to the candidate task which can be assigned to this processor is given by
(2.11)Ψ(tcdt)=T(tcdt)GCD(g,T(tcdt))⌊GCD(g,T(tcdt))-∑i=1nC(ti)C(tcdt)⌋.Proof.
⌊(GCD(g,T(tcdt))-∑i=1nC(ti))/C(tcdt)⌋ that represents the number of identical tasks to the candidate task can be scheduled in one interval of length g.T(tcdt)/GCD(g,T(tcdt)) represents the number of intervals of length g in one interval of length T(tcdt).Example 2.5.
Let(ta:1,4), (tb:1,12), and (tc:1,16) be three tasks already assigned. We look for assigning a task (td:1,20). By using Theorem 2.4, we compute the number of tasks identical to td which can be assigned.
First we check that tasksta, tb, tc, and td satisfy the SGCD property.GCD(T(ta),T(tb))=GCD(T(tb),T(tc))=GCD(T(tc),T(ta))=GCD(T(tc),T(td))=GCD(T(tb),T(td))=GCD(T(ta),T(td))=4.
Then,C(ta)+C(tb)+C(tc)+C(td)=4≤4 proves that the condition of Theorem 2.3 is satisfied.
Finally,Ψ(td)=20/4*⌊(4-3)/1⌋=5, which means that 5 tasks identical to td can be scheduled on this processor.
Figure1 shows the 5 intervals where 5 identical tasks to td can be scheduled (these intervals are numbered from 1 to 5). We show also intervals where td cannot be scheduled whereas they are empty, and for each interval the tasks (among ta, tb, and tc) cause the nonschedulability, for example, if tb is mentioned then it means that td cannot be scheduled on this interval because one of the instances of tb and one of the instances of td will be scheduled on the same interval which is not allowed.
Let us check, on Figure1, the result obtained by the previous calculation. We notice that if we divide the time axe in intervals of length equal to GCD=4 and divide each interval in subintervals of length 1, then it is always the fourth subinterval, which is used to schedule td. This means that the order established in the first interval of length GCD=4 is repeated and observed.Figure 1
Several scheduling possibilities of tasktd (Example 2.5).Definition 2.6.
We denote byΩ the set of tasks which have already been assigned to a processor. We divide the set Ω into several subsets {Ω1,Ω2,…,Ωv} such that the tasks of each subset and the task tcdt satisfy the SGCD property (introduced in Definition 2.2). Each subset Ωj is characterized by a greater common divisor (noticed gΩj), and we consider that Ω1 is the subset with the smallest greater common divisor (which is denoted BG). The sum off all execution time of a tasks set Ωj is denoted by C(Ωj)=∑ti∈ΩjC(ti).Now in order to know iftcdt is schedulable or not on a processor where other tasks have already been scheduled, we apply the following algorithm:(1)
choose a processor;(2)
set up sets(∀j),Ωj;(3)
computeΨΩ1(tcdt). This represent the identical tasks to tcdt which can be scheduled by taking into account only Ω1;(4)
for each subset (j>1),  Ωj remove to the result obtained in the previous step the number of identical tasks to tcdt which cannot be scheduled because of nonschedulability with tasks belonging to Ωj (the next theorem gives a way to compute this number);(5)
following the reached result, we decide to assigntcdt to this processor or try to assign it to another processor (go to 1).LetΓΩj(tcdt) (j≠1) represent the number of identical tasks to tcdt that cannot be scheduled because of a non-schedulability with tasks belonging to Ωj (j≠1).The following theorem gives an equation to computeΓ.Theorem 2.7.
Lettcdt be the candidate task, Ω={Ω1,Ω2,…,Ωv} the set of already scheduled tasks, and gΩj the GCD of all Ωj. For (j>1), ΓΩj(tcdt) is given by
(2.12)ΓΩj(tcdt)=T(tcdt)gΩj⌈∑ti∈ΩjC(tcdt)⌉α
such that
(2.13)α={1ifT(tcdt)gΩj>1,0ifT(tcdt)gΩj=1and∑ti∈ΩC(ti)<gΩj-1-C(tcdt).Proof.
T(tcdt)/gΩj is the number of intervals of length gΩj in an interval of length T(tcdt). This number is multiplied by ⌈∑ti∈Ωj/C(tcdt)⌉ which represents the number of tasks identical to tcdt that cannot be scheduled inside an interval the length of which is equal to gΩj. And also, in order to take into account the tasks of the other sets, we introduce the value of α.Now we bring together the different results obtained previously to find out an equation which allows to compute the number of schedulable tasks identical totcdt, and hence deduce if tcdt is schedulable or not.Corollary 2.8.
Lettcdt be the candidate task and Ω={Ω1,Ω2,…,Ωv} the set of already scheduled tasks. The number of identical tasks to tcdt which can be scheduled is given by
(2.14)ΨΩ1(tcdt)-∑j=2vΓΩj(tcdt)
such that
(2.15)ΨΩ1(tcdt)=T(tcdt)BG⌊BG-C(Ω1)C(tcdt)⌋.Example 2.9.
In order to illustrate the proposed method, we propose the following example: let(tcdt:2,30) to the candidate task to the schedulability analysis. Let Ω={(ta:2,5),(tb:1,10),(tc:1,20),(td:1,30),(te:1,60)} the set of tasks already proved schedulable. In this case, BG=GCD(T(ta),T(tb),T(tc),T(td),T(te),T(tcdt))=5(i)
the three subsets that we can set up from the setΩ and the task tcdt according to the SGCD property are
(1)
Ω1={tcdt,ta} with the GCD of periods equal to 5,(2)
Ω2={tcdt,tb,tc} with the GCD of periods equal to 10,(3)
Ω3={tcdt,td,te} with the GCD of periods equal to 30.(ii)
From Corollary2.8,
(2.16)ΨΩ1=305⌊5-22⌋=6,(iii)
Γ=ΓΩ2+ΓΩ3,
(1)
ΓΩ2=((30/10)⌈3/2⌉)= 3,(2)
by the same wayΓΩ3=0, so Γ=3+0=3,(iv)
thenΨΩ1-Γ=6-3=3, from this, we deduce that tcdt is schedulable.Remark 2.10.
The previous result allows us to assign several tasks (identical tasks totcdt) at the same times, and if other identical tasks to tcdt are not assigned then it means that these tasks are not schedulable on this processor and they must be assigned to another processor.Remark 2.11.
Notice that, throughout this schedulability analysis, in the given schedulability condition nothing is mentioned about precedence constraints, whereas we allow it in the tasks model. Indeed, a system with precedence constraints but without any periodicity constraint is always schedulable. The next theorem demonstrates that for a set of proved schedulable tasks, that is, satisfying periodicity constraints, it always exists a scheduling of these tasks which satisfies precedences between them, whatever the precedences are.Theorem 2.12.
LetΩ be a set of proved schedulable tasks. Whatever precedence constraints between Ω's tasks are, it exists, at least, one scheduling which satisfies these precedence constraints.Proof.
Once a set ofn tasks is proved schedulable, these tasks can be scheduled in n! different ways or orders. From these n! orders, at least, one order satisfies the precedence constraints (we remind that tasks are not allowed to be preempted).


## 2.1.2. Proposed Approaches

As a result of the previous study, we are able to yield an algorithm allowing the assignment of tasks to processors while satisfying precedence and periodicity constraints. Since the corollary condition is monoprocessor and it is applied for the assignment of each task (the test may be done several time until finding the right processor), the execution time of the assignment algorithm can have be long. Hence, we propose three assignment algorithms as follows:(1)
greedy algorithm: it starts by sorting tasks following a mixed sort which takes into account both the increasing order and a priority level [14]. Then tasks are assigned without any backtracking;(2)
local search algorithm: it uses the condition of the corollary. In order to have an assignment more efficient than the one of the greedy heuristic, we introduce a backtracking process. It is used once a task cannot be assigned to any processor, however, by taking off some assigned tasks from their processors until this task could be assigned and taken off tasks will be assigned to another processors. This backtracking does not change all the assignment but only a part that should not considerably increase the algorithm execution time;(3)
exact algorithm (optimal): it uses the condition of the corollary. This algorithm takes advantage of the Branch & Cut exact method [14].


## 2.2. Unrolling

The unrolling algorithm consists in repeating each task of the graph(hp/T) times, where the period of this task is T and hp is the hyper-period (Least Common Multiple of all period tasks) [15].When two tasks are dependent and have not the same period, there are two possibilities. If the period of the consumer task is equal ton times the period of the producer task, then the producer task must be executed n times compared to the consumer task, and the consumer task cannot start its execution until it has received all data from the n executions of the producer task. Notice that the produced data differ from one execution of the producer task to another execution; therefore, data are not duplicated. Reciprocally, if the period of the producer task, is equal to n times the period of the consumer task then the consumer task must be executed n times compared to the producer task. The unrolling algorithm exploits this data transfer mechanism.


## 2.3. Scheduling

This algorithm distributes and schedules each task of the unrolled graph onto the processor where it has been assigned by the assignment algorithm. In case where the task was assigned to several processors; the algorithm distributes it to the processor which minimizes the makespan. The minimization of the makespan is based on a cost function which takes into account the WCETs of tasks and the communication costs due to dependant tasks scheduled on different processors.Once a task is scheduled all its instances take start times computed in function of the task period and the number of the instance. In addition, to be scheduled, the first instance of each task must satisfy the condition of the next theorem.Theorem 2.13.
Let{(ti:C(ti),T(ti),S(ti)),i=1⋯n} be n tasks already scheduled on a processor. The task {(tj:C(tj),T(tj)} is schedulable at the date S(tj) on this processor if and only if
(2.17)∀i,S(ti)≤(S(tj)-S(ti))mod⁡gi≤(gi-C(tj))
such that gi=GCD(T(ti),T(tj)).Proof.
In order to prove Theorem2.13, it suffices to prove that two tasks {(ta:C(ta),T(ta),S(ta))} and {(tb:C(tb),T(tb),S(tb))} (and g=GCD(T(ta),T(tb))) are schedulable if and only if
(2.18)C(ta)≤(S(tb)-S(ta))mod⁡g≤(g-C(tb)).
Without any loss of generality, we assume that S(ta)=0. We start by showing the sufficiency of the Condition 5. Let us consider time intervals I={∀l∈ℕ,[0+lg,g-1+lg]. The first C(ta) time units of each of these intervals can be allocated for executions of ta once every T(ta)/g intervals, and the remaining g-C(ta) time units only or partly for executions of tb once every T(tb)/g intervals. If (2.18) is verified, then the allocated time units suffice to execute ta and tb.
In order to prove the necessity of (2.18), let us consider again time intervals {∀l∈ℕ,[0+lg,g-1+lg]. If (2.18) is not verified, then the execution of tb overlaps the first C(ta) time units once every T(tb)/g time intervals. We also note that the C(ta) time units of the intervals are used to execute ta once every T(ta)/g time intervals. As gcd(T(ta)/g,T(tb)/g)=1, there will be an interval from I where ta and tb are executed together. Hence, if (2.18) is not verified, the tasks ta and tb cannot be scheduled on the same processor. This completes the proof of the theorem.A complete example of the scheduling heuristic can be found in [14].


## 3. Performance Evaluation

In order to get the best approach among the three ones proposed into the scheduling heuristic (greedy heuristic, local search, and exact algorithm), we performed two kinds of tests.The first one consisted in comparing the scheduling success ratio for the three approaches on different systems. This test has been performed as follows: we compute for each system the value ofθ which is the ratio between the number of processors and the number of different and nonmultiple periods. Then, we gather all the systems with the same θ, and we execute for them the three approaches of the proposed heuristic. Finally, we compute the scheduling success ratio for the systems of each θ by using the results of the previous step. This method allows us to underline the impact of the architecture in terms of number of processors, and of the number of periods of tasks. The diagram of Figure 2 depicts the evolution of the success ratio according to the variation of θ. Excluding the exact algorithm which finds always the solution, we notice that the local search heuristic displays an interesting results. In addition, the greedy heuristic is efficient only when θ≥1 which means that its use is relative to the targeted systems.Figure 2
Scheduling success ratio comparison.In the second test, the speed of the three approaches of the proposed heuristic isevaluated by varying the size of the systems (both number graph tasks and number of processors). The diagram of Figure3 shows that the exact algorithm explodes very quickly whereas the local search heuristic keeps a reasonable execution time. In addition the greedy heuristic, as expected, stands for the fastest one. Notice that the algorithm execution time follows a logarithmic scale.Figure 3
Execution time comparison.To perform these tests, we generated automatically tasks graphs taking into account the periodic issues with dependent and nondependent tasks. The content itself of the task has no impact on the scheduling, only its WCET and its period are relevant. Also, we generated systems such that the number of different periods is not large relatively to the number of tasks; however, we generated systems with all the possible cases (multiple and not multiple period) in order to obtain more realistic results. In addition, the architecture graphs were generated according to a star topology meaning that any two processors can communicate through the medium without using intermediate processors (no routing).


## 4. Applications

The first example is a simple version of a “Visual control of autonomous vehicles for platooning”. This application is developed by several teams at INRIA. It consists in replacing the joystick which is used to drive manually a CyCab, by an automatic controller based on a video camera which gathers the necessary information to identify the vehicle ahead and to guarantee a minimum distance between the two vehicles. In order to simplify the original version, we use two major tasks, the first one includes the camera and image processing and the second one includes the distance controller and the tasks performing moving forward, steering, and braking (Figure4 shows the window containing the algorithm graph). The architecture is also a simple version of the real one with only two processors (Figure 5 shows the window containing the architecture graph). The separate execution of these two tasks showed that the first task produces a data every 1 second, whereas the second task consumes the data every 10 milliseconds. It means that these two dependent tasks are periodic, thus, nonperiodic real-time scheduling algorithms are unable to perform a scheduling which satisfies the periods and ensures the right data transfer between them. A shared memory could be an alternative but data sizes and memory access costs represent a significant inconvenient. AAA/SynDEx distributes and schedules onto the architecture these two periodic tasks which implies that the second task is repeated ten times for each execution of the first task. Thereby, the data produced by the first task is diffused to the ten repetitions of the second task (see Figure 6). The result is standing for a timing window corresponding to the predicted real-time behavior of the algorithm running on the architecture following the proposed distribution and scheduling algorithm. It includes one column for each processor and communication medium, describing the distribution (spatial allocation) and the scheduling (temporal allocation) of operations on processors, and of interprocessor data transfers on communication media. Here time flows from top to bottom, the height of each box is proportional to the execution duration of the corresponding operation (periods and execution durations are given or measured by the user).Figure 4
Platooning application (tasks graph).Figure 5
Platooning application (architecture graph).Figure 6
Platooning application (distribution and scheduling).The second example shows another aspect of AAA/SynDEx multiperiodic utilization. It consists in the “Engine Cooling System”, and as for the first example, this application is also a simple version of the original one. This application is composed of two sensors, the first one is a temperature sensor and the second one gives parameters representing the state of the engine. These two sensors are connected to the main task which is the engine control unit, supposed to perform the cooling of the engine. The cooling reads the temperatures sent by the first sensor and combine them with the information representing the operating state of the engine (Figure7 shows the windows containing the algorithm graph). Thereby, it can predict the change of the temperature and achieve the temperature control (by operating the cooling fan, e.g.). In order to perform more accurate predictions, the main task needs several temperatures which must be taken at equal time intervals and needs also several state information. This is why the temperature sensor is executed every 10 milliseconds (period = 10), the second sensor is executed every 15 milliseconds (Period = 15), and the main task every 30 milliseconds (period = 30). The architecture is composed of two processors similarly to the architecture of the previous example.Figure 7
Cooling control (tasks graph).Figure8 shows the result of the adequation applied to the algorithm and the architecture.Figure 8
Cooling control (distribution and scheduling).On Figure8 we can observe that the temperature sensor is executed three times. These three temperatures and two data producded by the two executions of the state sensor are sent to the main task. This latter, by receiving all these data, predicts the change of the temperature and achieves the temperature control.Finally, the user can launch the generation of an optimized distributed macro-executive, which produces as much files as there are of processors. This macroexecutive, independent of the processors and of the media, is directly derived from the result of the distribution and the scheduling. It will be macroprocessed with GM4 using executive-kernels which are dependent of the processors and the media, in order to produce source codes. These codes will be compiled with the corresponding tools (several compilers or assemblers corresponding to the different types of processors and/or source languages), then they will be linked and loaded on the actual processors where the applications will ultimately run in realtime.


## 5. Load and Memory Balancing

We proposed to improve the new distributed real-time scheduling heuristic in two main directions:(i)
minimizing the makespan of distributed applications by equalizing the workloads of processors (even thought a first attempt was carried out in the proposed heuristic),(ii)
efficient utilization of the memory resource.Towards these purposes we proposed, a load and memory balancing heuristic for homogeneous distributed real-time embedded applications with dependence and strict periodicity constraints. It deals with applications involvingN tasks and M processors. Each task a has an execution time Ea, a start time Sa computed by the distributed scheduling heuristic, and a required memory amount ma. The required memory amount may be different for every task. It represents the memory space necessary to store the data managed by the task, that is, all the variables necessary for the task according to their types.For each processor, the proposed heuristic starts by building blocks from tasks distributed and scheduled onto this processor. Then, each blockA is processed according to the increasing order of their start times. This process consists in computing the cost function λ (defined in the next paragraph) for the processors whose end time of the last block scheduled on these processors is less than or equal to the start time of the block A, and in seeking the processor which maximizes λ. Moreover, a block is moved to that processor if the periodicity of the other blocs on this processor is verified, otherwise that processor is no longer considered, and the heuristic seeks again another processor which maximizes λ. If the moved block belongs to the first category and λ>0, then this block will decrease its start time. In order to keep its strict periodicity constraint satisfied, the heuristic looks through the remaining blocks and updates the start times of the blocks containing tasks whose instances are in the moved block. This heuristic is applied to the output of the scheduling heuristic already presented.The heuristic is based then on aCost FunctionλPi→Pj(A) which is computed for a block A initially scheduled on processor Pi and a processor Pj(5.1)λPi→Pj(A)={GPi→Pj(A)ifnoblockhasbeenmovedtoPj,GPi→Pj(A)+1∑i=1i=kmBiotherwise.It combines𝔾Pi→Pj(A) and the sum of required memory amounts by the k blocks B1,…,Bk already moved to this processor Pj. Notice that 𝔾 is the gain in terms of time due to the move of this block.A detailed example and a complexity and a theoretical performance studies can be found in [16].


## 6. Conclusion

We presented a new feature for AAA/SynDEx tool which allows the scheduling of multiperiodic dependent nonpreemptive tasks onto a multiprocessor. The new feature of AAA/SynDEx provides a unique scheduling algorithm since it is based on a schedulability analysis which allows for distributing and scheduling the tasks while satisfying their dependences and their strict periodicity. The analysis proposed here is composed in several stages to reach the main result which is a necessary and sufficient condition we obtain at the end through a corollary. Such schedulability analysis can be used in suboptimal heuristics to find an assignment of the tasks for each processor when partitioned multiprocessor scheduling is intended.When dependent tasks with two different periods are distributed and scheduled onto two different processors the proposed heuristic handles correctly the interprocessor communications.Since memory is limited in embedded systems, it must be efficiently used and, also, the total execution time must be minimized since the systems we are dealing with include feedback control loops. Thus, we improved the presented heuristic in order to perform load Balancing and efficient memory usage of homogeneous distributed real-time embedded systems. This is achieved by grouping the tasks into blocks, and moving them to the processor such that the block start time decreases, and this processor has enough memory capacity to execute the tasks of the block.The study of this paper stands for a first step from a more global work which targets resolving all kinds of periodicity constraints.



---

*Source: 561794-2011-09-06.xml*