Philippe Collard
email: philippe.collard@unice.fr

Salma Mesmoudi

How to prevent intolerant agents from high segregation?

In the framework of Agent-Based Complex Systems we examine dynamics that lead individuals towards spatial segregation. Such systems are constituted of numerous entities, among which local interactions create global patterns which cannot be easily related to the properties of the constituent entities. In the 70's, Thomas C. Schelling showed that an important spatial segregation phenomenon may emerge at the global level, if it is based upon local preferences. Moreover, segregation may occur, even if it does not correspond to agent preferences. In real life preferences regarding segregation are influenced by individual contexts as well as social norms; in this paper we will propose a model which describes the dynamic evolution of individuals tolerance. We will introduce heterogeneity in agents' preferences and allow them to evolve over time. We will show that it is possible to dynamically get a distribution of tolerance over the agents with a low average and in the same time to deeply limit global aggregation. As the Schelling's model showed that individual tolerance can nevertheless induce global aggregation, this paper takes the opposite view showing that intolerant agents can avoid segregation in some extent.

Introduction

In his article [START_REF] Schelling | Dynamic models of segregation[END_REF], Thomas Schelling developed a model of segregation and analysed how a simple preference not be a part of a minority in one's neighbourhood, without necessarily favouring dominance of one's own type, can generate small micro-shocks which have drastic consequences at the macro level. Aggregation happens through a chain reaction, even though the agents do not wish such an extreme situation. Agents interact only locally with their neighbours: every one agrees to stay in a neighbourhood with individuals that have the opposite type, only if there are enough individuals with the same type in the vicinity. This proportion is fixed by a threshold, denoted by the tolerance ratio.

More generally, the 'micromotives and macrobehaviour' problematic asks the question of the compliance between local micro-motives and the resulting macro-behaviour. Today, as problems become more and more complex, this problematic is more relevant than ever. In the fields of sociology, economics, ecology, energy, ..., each one has many a priori on the global consequence of his own actions. Most often, a person thinks in good faith that his action will produce faithful results for the community. For example, one can think that:

(a) intolerant behaviour lead to high segregation (b) tolerant behaviour lead to low segregation Let i (resp. ī) stands for individual intolerance (resp. tolerance) and S for a high level of global aggregation/segregation. Hypothesis (a) and (b) can be reformulated by the micro to macro link [i → S] and [ ī → S]. The Schelling's model provides first an example for the expected case [i → S]; but, as it shows that tolerance can nonetheless induce a significant level of segregation, it provides also an example for the paradoxical link [ ī → S] where the macrooutcome is intuitively inconsistent with the preferences of the agents who generate it.

This paper shows that macro-segregation can be deeply limited despite the presence of intolerant agents; thus, it provides an example for the dual case [i → S]. In the model we propose, each agent has his own threshold of tolerance. At each time, for each agent, the tolerance is adapted using some meta-rules. As a consequence, the emergent state of the 'world' results from a spatio-temporal adaptive dynamics. The scientific question addressed in this work is an evolution of the Schelling Model, which consists in considering an adaptive micro level of tolerance and analysing its impact on the segregation phenomenon observed at the macro level.

This article is organized as follows. In section 2, we propose a generic model of satisfaction. Section 3 shows the global behaviour of models using the simple Eulogy to Fleeing rule. Section 4 examines the effects of introducing adaptive tolerance thresholds on the nature of frontier between patterns. Section 5 proposes the new model which allows to conciliate local intolerance and a low level of segregation. Finally, future works are listed and conclusions are drawn.

A generic model of satisfaction

The Schelling's checkerboard model of residential segregation has become one of the most cited and studied models in many domains as economics, sociology, complex systems science,... [START_REF] Pancs | Schelling's spatial proximity model of segregation revisited[END_REF], [START_REF] Zhang | A dynamic model of residential segregation[END_REF][START_REF] Gerhold | Computing the complexity for schelling segregation models[END_REF], [START_REF] Banos | Exploring network effects in schelling? segregation model. S4-MODUS workshop Multi-scale interactions between urban forms and processes[END_REF]. It is also one of the predecessor of agent-based computer models [START_REF] Rosser | On the complexities of complex economics dynamics[END_REF]. Taking inspiration from this model, we define a more generic model of satisfaction (GMS).

The GMS is similar to a 2-D cellular automata model: the 'world' includes numerous agents embedded on a toroidal grid. For each agent, the perception is centered on his local neighbourhood only, where the neighbourhood is constituted of the nearest cells surrounding him. We note d i (t) the social degree of the agent a i at time t, that is the number of agents in its neighbourhood. Since some locations remain empty, the size of the neighbourhood is the maximum number of neighbours an agent can have. There are two types of agents and each agent has its own type. During a run the agent's type cannot change. The satisfaction of one agent is relative to the type of the agents in its own neighbourhood. For convenience we will denote by a color, yellow and green, the two possible types. Y (resp. G) represents the set of agents in the yellow type (resp. green type). Thus, the number of agents is (#Y + #G) and at the global level, the basic hypothesis is (#Y = #G). At each time t, for each agent a i , s i (t) (resp. o i (t)) represents the number of neighbours with the same type (resp. opposite type), so

s i + o i = d i .

From Thresholding to Satisfaction

For each agent a i , we assume that there is some quantity measured by the variable Q i in the range [0, 1] which depends on s i and o i . At each time t, the value requiredQ i (t) is a number in the range [0, 1] which denotes the threshold under which the agent is satisfied according to Q i (t). We define the local boolean indicator satisf ied as:

satisf ied i (t) = (Q i (t) ≤ requiredQ i (t)) (1)
Finally, we define the global indicator satisfactionRatio in the range [0, 1] as:

satisf actionRatio(t) = #{satisf ied i (t) = true} #Y + #G (2)
This is the ratio of satisfied agents at time t; if it is equal to 1, then all the agents are satisfied at time t.

Local rule

Once the static description of the model is specified, one must add rules that govern the dynamics of agents' movement. At each time, the motives of each agent are driven by its own satisfaction: an unsatisfied agent is motivated to move away to one vacant location. The gap between micromotives and macro-behaviours is due to overlapping neighbourhoods: an agent who moves according to its own interest affects not only the neighbourhood it leaves and the one it arrives in, but also affects, in the long run, all the agents. In GMS we do not fix how an agent moves; this will be specified later when the model will be instantiated. One can only say that there are many ways for an unsatisfied agent to move to a vacant place.

An index to measure the degree of aggregation

To have some insight into the aggregation level, it is necessary to measure the global aggregate over the world. We reformulate measures proposed by Schelling, Carrington and Goffette-Nagot Schelling (1971), [START_REF] Carrington | On measuring segregation in samples with small units[END_REF], [START_REF] Goffette-Nagot | Dynamic models of residential segregation: Brief review, analytical resolution and study of the introduction of coordination[END_REF]. First, we define a global measure of similarity as:

s(t) = 1 #Y + #G i (1 -Q i (t)) (3)
Then, we define the aggregateIndex by

aggregateIndex =    s-s rand 1-s rand if s ≥ s rand s-s rand s rand else (4)
where s rand is the expected value of the measure s implied by a random allocation of the agents in the world. A null value for this index corresponds to an average random configuration. The maximum value of 1 corresponds to a configuration with two homogeneous patterns only.

The Schelling's model of segregation

The Schelling's model of segregation is a particular case for the generic model of satisfaction. In the following we are going to indicate its specificities.

How to compute satisfaction? In the Schelling model the quantity Q i (t) takes into account the proportion of neighbours of the opposite type; it is computed as the ratio between the number of neighbours having the opposite type and the social degree.

Q i (t) = oi(t) di(t) if d i (t) = 0 0 else (5)
For example, if a yellow agent a i has three yellow neighbours and two green neighbours, Q i = 2 5 . If there are no neighbours for the agent (i.e. if d i = 0), Q i = 0. If all neighbours have the same type (i.e. if o i = 0 and s i = 0), Q i = 0. If all the neighbours are in the opposite type (i.e. if s i = 0 and o i = 0), Q i = 1. As the initial spatial configuration is randomly chosen, the initial distribution of Q i is binomial.

Table 1: Ratio between the number of neighbours of opposite type to the social degree: In this model, all the agents have the same threshold of tolerance: it is a constant value (noted tolerance) which is fixed before the run. So, at each time t, for each agent a i , equation 1 becomes:

Q i = oi oi+si Coloured values: agent a i , will be satisfied if Q i is under the tolerance threshold 0.37 @ @ @ s o 0 1 2 3 4 5 6 7 8 0 0 1 1 1 1 1 1 1 1 1 0 .
satisf ied i (t) = (Q i (t) ≤ tolerance) (6)
The agents are said tolerant if the tolerance is greater than 0.5 (0.5 ≤ tolerance) and intolerant otherwise. We use the Moore neighbourhood commonly employed in agent-based models. So the neighbours of an agent are those living in the eight nearest cells surrounding him and the degree d i is a number between 0 and 8. For instance, if the tolerance threshold is 0.37, one particular agent a i , at time t, will be satisfied if Q i (t) is under this value; this happens in the following eighteen cases: How do unsatisfied agents move away ? In standard Schelling's models agents move only to satisfy their own interest. This requires that agents must be able to access distant information in order to determine whether or not it will be satisfied in a new vacant cell. This kind of behaviour is characteristic among economical agents that seek to maximize their gain. Nonetheless such a behaviour come out of the idea of agents acting approximately rational, rather economically rational in terms of utility and breaks down the principle of locality (see [START_REF] Brownlee | Satisficing, optimization, and adaptive systems[END_REF]). The Schelling Model with the Eulogy to Fleeing rule

(o i = 0), (s i = 2, o i = 1), (s i = 3, o i = 1), (s i = 4, o i = 1), (s i = 5, o i = 1), (s i = 6, o i = 1), (s i = 7, o i = 1), (s i = 4, o i = 2), (s i = 5, o i = 2) and (s i = 6, o i = 2) (

Global behaviour

In standard Schelling's models agents aspire to satisfy their interests in the new places they move in. In this section, we rather assume a reaction from agent without real cognitive abilities expressed by the simple Eulogy to Fleeing rule (EF rule).

The Eulogy to Fleeing rule

The Eulogy to Fleeing rule is agreeing with the definition of the term satisficing proposed by Herbert A. [START_REF] Simon | Rational choice and the structure of the environment[END_REF]. "Satisficing describes the selection of a good enough solution, the selection of a decision that meets a minimum threshold or aspiration level, the selection of which occurs in the context of incomplete information or limited computation" [START_REF] Brownlee | Satisficing, optimization, and adaptive systems[END_REF].

The EF rule is defined as follows: for each unsatisfied agent, a cell is randomly chosen 'all over the world' and the agent moves to this cell if and only if it is vacant. So the agents may move at random towards a new location according to their preferences by allowing utility-increasing or utility-decreasing actions. Moves do generate new satisfied or unsatisfied agents by a chain reaction until an equilibrium is reached. At a time t, if all the agents are satisfied, the EF rule has no effect and then such a configuration is a fixed point for the dynamics.

This simple rule is more in the spirit of the complex system paradigm, and, as locally there is no seeking for immediate benefits, it is interesting to know its global consequences. Although it is easy to build some particular cases where the EF rule does not converge, in the following simulations this rule leads the system towards an equilibrium. Let's note that although similar rules based on a random choice of vacant locations are already proposed [START_REF] Edmonds | Computational simulation as theoretical experiment[END_REF], Izquierdo et al. ( 2009)), they do not look completely identical to the EF rule. In particular, with the EF rule, an unsatisfied agent may stay in place for a while if the randomly chosen locations are occupied.

Simulation and results

In this paper, all the simulations are realized in the Net-Logo1 multiagent programmable modeling environment [START_REF] Pham | From Agent-Based Computational Economics towards Cognitive Economics[END_REF], [START_REF] Wilensky | Center for connected learning and computerbased modeling[END_REF]. For each simulation, the agent's features are updated in an asynchronous way and the global geographic parameters are fixed. The world is a square of locations horizontally and vertically wrapped. An agent with type 'yellow' (resp. green) is represented by a yellow (resp. green) square. A black square represents a vacant location. A simulation stops at convergence, when all the agents become satisfied.

The world is a grid-square composed of 10000 locations. This size is a good compromise between the necessity to have a large value to avoid small space effects and the convenience to have a small value to achieve short computation time. There are 1000 vacant locations, knowing that the density rate is 90% and 4500 agents in each type. We imposed a random initial configuration: in the cases studied below, the value of s rand is indistinguishable from 0.5; thus initial configuration induces an aggregateIndex closed to 0.

We conducted two types of experiment: in the first one, all the agents are intolerant and in the second they are tolerant.

Intolerant agents For this first experiment the tolerance is set to 0.37 (see table 1); so all the agents are intolerant. We can see in figure 1 the result of the agents spatio-temporal evolution at the end of a representative run: after 1150 steps all the agents are satisfied (i.e. satisf actionRatio = 1), the mean Q i over the whole population (noted Q) is 0.024 and the aggregateIndex is 0.957. From 100 independent runs we obtain, a mean of 0.952 (0.0041) 2 for the aggregateIndex and 0.024 (0.0022) respectively for Q. We can observe the emergence of large spatial homogeneous patterns. Moreover the borderland between the patterns is almost build with every vacant location (black square). So patterns are isolated by a no-man's-land of vacant cells.

Tolerant agents Here, the goal is to show that segregation occurs even if no agent strictly prefers this. We set the tolerance to 0.63 (see table 1), so all the individuals are tolerant. In particular, if an agent has exactly eight neighbours, it can bear up to five opposite agents in its vicinity. Figure 2 gives an example of the evolution of the agents' locations during a representative run. At the end, after 228 steps, all the agents are satisfied, the mean Q i over the whole population is 0.229 and the aggregateIndex is 0.548. From 100 independent runs we obtain, a mean of 0.53 (0.0119) for the aggregateIndex and 0.233 (0.0094) respectively for Q. While spatial segregation is not an attribute of the rational individuals's behaviour, we can observe the emergence of many segregationist patterns, although they have a smaller size that in the previous case (see figure 1). More, vacant locations are scarce on borderline because with a high tolerance level vacant cells are not requisite to delimit segregationist patterns.

2 standard deviation is shown in ()

Discussion

In this section, we have shown that in spite of the use of a more simple and realistic local rule, the model produces a comparable global behaviour than the classical Schelling model.

We have shown that both intolerant and tolerant local behaviours lead to the satisfaction of all the agents with the emergence of global segregationist patterns. Moreover, the gap between the tolerance and the mean Q i over the whole population is surprisingly large at the end of a run. In this way complex dynamics build much more liveable configurations than necessary. With intolerant agents, vacant places are required to form the frontiers and insulate agents in homogeneous patterns. In the next section, we propose to modify the model in order to insulate segregationist patterns without using vacant locations mainly.

From no-man's-land to mediator-land Most often, in real life some individuals are tolerant whereas others are intolerant. In a model, there are two ways to take into account this fact: either fixing a distribution for the tolerance, or dynamically evolving tolerance to 'converge' toward a particular distribution. The first solution requires not only to choose one distribution: uniform, normal, poisson,. . . but also to fix its parameters: mean and standard deviation.

Adaptive local rule

As we have no a priori on a target level of tolerance, we choose to start from an intolerant configuration and to apply a local rule to gradually increase the tolerance. For instance, when a person is immersed in an unknown world, his first attempt will be to meet people which look like him; so initially, certainly with many apriority, such a person is gregarious or intolerant. Then, if his requirement is too high relatively to the environment, it will be difficult for him to find a fitting place; therefore a natural tendency will be to gradually reduce his stress by decreasing his gregariousness and/or increasing his tolerance.

In this new instance of the GMS, each agent has its own tolerance threshold. Furthermore, each individual threshold may vary over time. So, for each agent a i , at each time t, the satisfied indicator (see equation 1) becomes:

satisf ied i (t) = (Q i (t) ≤ tolerance i (t)) (7)
Initially, the tolerance of each agent is set to a very small value, therefore an agent is at first radically intolerant and so will be unsatisfied. At each time, for each unsatisfied agent, a cell is randomly chosen 'all over the world' in order to move in if it is vacant, otherwise, i.e. if the cell is already occupied, the agent stays put and adapts its own tolerance to the context by increasing its value with a small increment.

Simulation and results

For each agent, the tolerance is initialised to 0.001 and we chose a small increment of 0.003. We can see on figure 3 the spatio-temporal evolution of the agents at the end of a representative run. After 663 steps all the agents are satisfied; the mean tolerance over the population is 0.365, the mean Q i over the population is 0.049 and the aggregateIndex is 0.892. Even if dynamics are more complex than in Schelling's model, we can observe the emergence of spatial homogeneous patterns yet. On 100 runs we obtain, a mean of 0.919 (0.0120) for the aggregateIndex and 0.360 (0.0047) respectively for the mean tolerance. So, on average, dynamics lead agents to remain intolerant and a high segregation emerges at the global level; once again this is an example for the case [i → S]. We can observe that the frontier between homogeneous patterns is constituted both by vacant cells (black square) and by the most tolerant agents (white circle), i.e. agents with tolerance ≥ 0.39; therefore, for a significant part, homogeneous regions are isolated by places for mediation where opposite agents may co-exist. We can note that there are also tolerant agents outside the mediator-land; this corresponds to scoria 3 in some areas where former conflicts have led to the local hegemony of one of the two types; thus data collected from the own tolerance of the agents allow to learn more about the past of the system.

Discussion

A first result is that dynamics leads the mean tolerance toward a relatively weak value (0.36); as a consequence, when all the agents become satisfied, they remain on average intolerant. The second result is that segregation is still high (0.919). The third result is that in a world where agents are on average intolerant there are some tolerant agents which play a crucial role in the spatial distribution. This can serve as a clue to extend the model toward more mosaic-like structure. Type-mix would be favoured by the existence of secluded agents amidst individuals having an opposite type. In the present model, this is impossible because agents are not tolerant enough to endure such a situation: we have to enhance the dynamics to allow tolerance to reach high values. On the contrary, the presence of scoria shows that one agent with high tolerance may be useful in a moment at a place then becomes superfluous later in the same location; so decrease the tolerance of satisfied agents may help to avoid such 'frozen region'. All this suggest us to manage two antagonist dynamics: increasing and decreasing the tolerance; so, we expect to significantly lower the level of segregation while maintaining a weak mean tolerance.

How to avoid high segregation ?

In this last section the goal is to respond to the question: How intolerant agents can become satisfied without the emergence of macro segregation?

In the new model we propose, there are two antagonist dynamics, the first one increases the tolerance of unsatisfied agents, whereas the second decreases the tolerance of satisfied agents. Initially, the agents have a weak tolerance and are thus radically intolerant and unsatisfied.

• An unsatisfied agent, can either move to a vacant place or else simply increase its tolerance (for details, see the previous section).

• Conversely, for a satisfied agent a i , if the difference delta between its tolerance i and the value of Q i in the place it lives in is too high, its tolerance decreases.

In real life, when a person is no longer confronted with distressing circumstance, his ability to cope later in such a situation is reduced. This phenomenon can be explained by a mechanism of forgetfulness. In the model, an agent is satisfied if it is not faced to a large enough number of opposite agents. If over time such a lack of confrontation persists, then the agent gradually reduces his threshold of tolerance.

Parameter space exploration

There are two main parameters that control the dynamics of tolerance: the amount of increment inc and decrement dec.

First we conduct a parameter space exploration in order to chose suitable values for the simulation.

In the context of complex systems, most often there are several parameters which together determine the global dynamics. In order to choose values for the parameters used in the simulations, we have first conducted an exploration of the parameter space. The objective to minimize both the mean tolerance and the global aggregateIndex is difficult because when the first one decreases, the second increases and conversely. Therefore, we conduct a tradeoff-analysis to identify compromise for which the two criteria are mutually satisfied in a Pareto-optimal sense. This is a typical multiobjective optimisation problem where the optimal solutions correspond to a set of compromises expresses by a Pareto front [START_REF] Dyer | Multiple criteria decision making, multiattribute utility theory the next ten years[END_REF], [START_REF] Belton | Multiple Criteria Decision Analysis: An Integrated Approach[END_REF]. In practice, the Pareto front is proposed to a human decision-maker who then chooses a solution according to his expertise.

For all the tests we perform, the parameter delta is set to 0.1. We focus our effort on areas that lead to interesting regions where convergence occurs with low tolerance and low segregation: each test corresponds to one couple (inc, dec) in the range [0.025, 0.040] × [0, 0.030]. There are 60 tests and, for each one, results are averaged over 100 runs. Each data point of the scatter plot (see figure 4) corresponds to a couple (inc, dec) and represents both the aggregateIndex (y-value) and the mean tolerance (x-value) obtained when all the agents are satisfied. We can observe that heightening the parameter dec (while inc remains constant) pushes the point solution to the left toward the Pareto front. Conversely, lowering the parameter inc (while dec is constant) moves up the point solution on one front. This analysis leads us to choose a particular point on the Pareto-front that represents a good compromise between both intolerance and low segregation. To conduct the following simulations, we choose the point corresponding to the parameter values inc = 0.029 and dec = 0.017 (See the arrow on figure 4).

Results

Initially, all the tolerances are set to 0.1. We can observe on figure 5 the spatial configuration at the end of a representative run when all the agents are satisfied: after 513 steps, the mean Q i over the population is 0.306, the mean tolerance over the population is 0.369 and the aggregateIndex is 0.383. On 100 runs, we obtain on average an aggregateIndex of 0.388 (0.0110) and a mean tolerance of 0.370 (0.0048). The value for the aggregateIndex (0.388) has to be compared with the ones obtained with the two previous models (0.957 and 0.919)

The frontier between homogeneous patterns is constituted by the most tolerant agents and there is no scoria inside the patterns. One observes that homogeneous areas are infiltrated by many secluded individuals: there are some niches which co-exist within a cohort of unlike agents; this is possible only because loners are very tolerant. In contrast with

Conclusion and future work

In this article, we have proposed to extend the Schelling's model considering that every individual has its own tolerance level. In a first step we have proposed a simple way to locally manage the tolerance; all that gives rise to the emergence of a new kind of border and inner scoria both made up of the most tolerant agents. In a second stage, we have introduced new dynamics that consists of combining two antagonist strengths. As a result of this confrontation, the agents are able to reach an equilibrium where they all are satisfied, rather intolerant, but where the aggregation level remains low. As, at our knowledge, there is no prior work on this topic, this result is a significant challenge to the analysis conducted by Schelling: it shows that one can avoid segregation if the tolerance level is adaptive, which is in our opinion a better assumption.

In future work, we will revisit those results by considering situations closer to reality. Beyond a simple world of agents embedded on an homogeneous toroidal-grid, we have to consider different types of network as for example neighbourhoods defined from a scale-free network. We have observed the emergence of very different type of frontiers: noman's-land, mediator-land or in some extend mixing; thus, it might be interesting to study for a border, its composition, its spatial distribution, its volume, porosity, permeability,... and so to better understand its function: place of exchange and/or medium to isolate.

Figure 1 :

 1 Figure 1: The Eulogy of Fleeing rule: tolerance = 0.37 View at convergence (ticks = 1150): Q = 0.024 aggregateIndex = 0.957

Figure 2 :

 2 Figure 2: The Eulogy of Fleeing rule: tolerance = 0.63 View at convergence (ticks = 228): Q = 0.229 aggregateIndex = 0.548

Figure 3 :

 3 Figure 3: Dynamic tolerance View at convergence (ticks = 663): aggregateIndex = 0.892 mean tolerance = 0.365

Figure 4 :

 4 Figure 4: Parameter space analysis Tolerance vs. Segregation

Figure 5 :

 5 Figure 5: Intolerant agents avoid segregation View at convergence (ticks = 513): mean tolerance = 0.369, aggregateIndex = 0.383

  stands for individual intolerance (resp. tolerance) and S stands for a high degree of global segregation. While the first case is the intuitive situation where micro-intolerance induces macrosegregation, the second case is more surprising as it shows that tolerant behaviours can nonetheless induce a global segregation.

Regarding the micro-macro problematic, the Schelling model provides examples for the two cases: [i → S] and [ ī → S] where i (resp. ī)

http://ccl.northwestern.edu/netlogo/

Scoria is the dross that remains after the smelting of metal from an ore

Acknowledgements

We thank the referees for useful comments on the manuscript and Touria Ailt Elhadj for her english correction.


Keywords: scheduling, distributed, partitioned, multi-rate ordonnancement, distribué, partitionné, multi-période

We consider deterministic functional specifications provided by means of synchronous data-flow models with multiple modes and multiple relative periods. These specifications are extended to include a real-time characterization defining task periods, release dates, and deadlines. Task deadlines can be longer than the period to allow a faithful representation of complex end-to-end flow requirements. We also extend our specifications with partitioning and allocation constraints. Then, we provide algorithms for the off-line scheduling of these specifications onto partitioned time-triggered architectures à la ARINC 653. Allocation of time slots/windows to partitions can be fully or partially provided, or synthesized by our tool. Our algorithms allow the automatic allocation and scheduling onto multi-processor (distributed) systems with a global time base, taking into account communication costs. We demonstrate our technique on a model of space flight software system with strong real-time determinism requirements.

Introduction

This paper addresses the implementation of embedded control systems with strong functional and temporal determinism requirements. The development of these systems is usually based on modeldriven approaches using high-level formalisms for the specification of functionality (Simulink, Scade[CCM + 03]) and/or real-time system architecture and non-functional requirements (AADL [AAD], UML/Marte [uml]).

The temporal determinism requirement also means that the implementation is likely to use time-triggered architectures and execution mechanisms defined in well-established standards such as TTA, FlexRay [START_REF] Rushby | Bus architectures for safety-critical embedded systems[END_REF], ARINC 653 [ARI05], or AUTOSAR [START_REF]Autosar (automotive open system architecture)[END_REF].

The time-triggered paradigm describes sampling-based systems (as opposed to event-driven ones) [START_REF] Kopetz | Event-triggered versus time-triggered real-time systems[END_REF] where sampling and execution are performed at predefined points in time. 1 The offline computation of these points under non-functional constraints of various types (real-time, temporal isolation of different criticality sub-systems, resource allocation) often complicates system development, when compared to classical event-driven systems. In return for the increased design cost, system validation and qualification are largely simplified, which explains the early adoption of time-triggered techniques in the development of safety-and mission-critical real-time systems.

Contribution. The objective and contribution of this paper is to facilitate the development of time-triggered systems by automating the allocation and scheduling steps for significant classes of functional specifications, target time-triggered architectures, and non-functional requirements. On the application side, we consider general dataflow synchronous specifications with conditional execution, multiple execution modes, and multiple relative periods. Explicitly taking into account conditional execution and execution modes during scheduling is a key point of our approach, because the offline computation of triggering dates limits flexibility at runtime. For instance, taking into account conditional execution and modes allows for better use of system resources (efficiency) and a simple modeling of reconfigurations.

On the architecture side, we consider multiprocessor distributed architectures, taking into account communication costs during automatic allocation and scheduling.

In the non-functional domain, we consider real-time, partitioning, preemptability, and allocation constraints. By partitioning we mean here the temporal partitioning specific to TTA, FlexRay (the static segment), and ARINC 653, which allows the static allocation of CPU or bus time slots, on a periodic basis, to various parts (known as partitions) of the application. Also known as static time division multiplexing (TDM) scheduling, these approaches further enhance the temporal determinism of a system.

We make an original use of classical real-time characteristics such as periods, release dates, and deadlines, which we adapt to our time-triggered target. In particular, the use of deadlines that are longer than the periods naturally arises. It allows a more natural real-time specification, improved schedulability, and less context changes between partitions (which are notoriously expensive).

The application. We apply our technique on a model of spacecraft embedded control system. Spacecrafts are subject to very strict real-time requirements. The unavailability of the avionics system (and thus of the software) of a space launcher during a few milliseconds during the atmospheric phase may indeed lead to the destruction of the launcher. From a spacecraft system point of view, the latencies are defined between acquisitions of measurement by a sensor to sending of commands by an actuator. Meanwhile, the commands are established by a set of automatism algorithms (Guidance, Navigation and Control or GNC).

Traditionally, the GNC algorithms are implemented on a dedicated processor using a classical multi-tasking approach. But today, the increase of computational power provided by space processors allows suppressing this dedicated processor and distributing the GNC algorithms on the processors controlling either the sensors or the actuators. For future spacecraft (space launchers or space tranbsportation vehicles), the navigation algorithm could for instance run on the processor controlling the gyroscope, while the control algorithm could run on the processor controlling the thruster. The suppression of the dedicated processor allows power and mass saving.

The sharing of a processor by two pieces of software (one controlling for instance a gyroscope and the other one implementing the navigation algorithm) requires the use of a hypervisor ensuring the Time and Space Partitioning (or TSP), such as ARINC 653 [ARI05]. The scheduling problem is therefore as follows: End-to-end latencies are defined at spacecraft system level, along with the offsets of sensing and actuation operations. Also provided are WCET (worst case execution time) values associated to tasks. What must be computed is the time-triggered schedule of the system, including the activation times of each partition and the bus frame.

Outline. The remainder of the paper is organized as follows. Section 2 reviews related work. Section 3 defines our architecture model, spending significant space on the careful definition of time-triggered and partitioned systems. Section 4 defines our task model, including functional and non-functional aspects. Sections 5, 6, and 7 cover the scheduling algorithms and experimental results. Section 8 concludes. [CSB90] on the scheduling of dependent task systems have been a major source of inspiration. By comparison, our paper provides a general treatment of ARINC 653-like partitioning and of conditional execution, and a novel use of deadlines longer than periods to allow faithful real-time specification. Our work is also close to that of Pop et al. [START_REF] Pop | Scheduling with optimized communication for timetriggered embedded systems[END_REF], the main differences being the handling of end-to-end delays and the use of fast heuristics.

Related work

Compared to previous work by Isovic and Fohler [START_REF] Isovic | Handling mixed sets of tasks in combined offline and online scheduled real-time systems[END_REF] on real-time scheduling for predictable, yet flexible real-time systems, our approach does not directly cover the issue of sporadic tasks. Instead, we focus on the representation of real-time characteristics and on a very general handling of execution conditions, allowing for important flexibility inside the fully predictable domain.

Compared to classical work on the on-line real-time scheduling of tasks with execution modes (cf. Baruah et al. [START_REF] Baruah | Generalized multiframe tasks[END_REF]), our off-line scheduling approach comes with precise control of timing and causalities. It is therefore more interesting for us to use a task model that directly represents execution conditions. We can then use table-based scheduling algorithms that precisely determine when the same resource can be allocated at the same time to two tasks because they are never both executed.

References on time-triggered and partitioned systems, as well as scheduling of synchronous specifications will be provided in the following sections.

Inria 3 Architecture model

In this paper, we consider both single-processor architectures and bus-based multi-processor architectures with a globally time-triggered execution model and with strong temporal partitioning mechanisms. This class of architectures covers the needs of the considered case study, but also covers platforms based on the ARINC 653, TTA, and FlexRay (the static segment) standards.

Formally, for the scope of this paper, a piece of architecture is a pair Arch = (B(Arch), Procs(Arch)) formed of a broadcast message-passing bus B(Arch) connecting a set of processors Procs(Arch) = {P 1 , . . . , P n } for some n ≥ 1. We assume that the bus does not lose, create, corrupt, duplicate or change the order of messages it transmits. Previous work by Girault et al. [START_REF] Girault | An algorithm for automatically obtaining distributed and fault-tolerant static schedules[END_REF] (among others) can be used to extend this simple model (and the algorithms of this paper) to deal with fault-tolerant architectures with multiple communication lines and more complex interconnect topologies. However, for space and clarity reasons, the remainder of the paper only focuses on extending our simple model with timing, allocation, and partitioning information specific to our time-triggered approach.

Time-triggered systems

In this section we define the notion of time-triggered system used in this paper. It roughly corresponds to the definition of Kopetz [START_REF] Kopetz | Event-triggered versus time-triggered real-time systems[END_REF], and is a sub-case of the definition of Henzinger and Kirsch [START_REF] Henzinger | The embedded machine: Predictable, portable realtime code[END_REF]. We shall introduce its elements progressively, explaining what the consequences are in practice.

General definition

By time-triggered systems we understand systems satisfying the following 3 properties: TT1 A system-wide time reference exists, with good-enough precision and accuracy. We shall refer to this time reference as the global clock. For single-processor systems the global clock can be the CPU clock itself.2

TT2 The execution duration of code driven by interrupts other than the timers is negligible.

In other words, for timing analysis purposes, code execution is only triggered by timers synchronized on the global clock.

TT3 System inputs are only read/sampled at timer triggering points.

At the same time, we place no constraint on the sequential code triggered by timers. In particular:

• Classical sequential control flow structures such as sequence or conditional execution are permitted, allowing the representation of modes and mode changes.

• Timers are allowed to preempt the execution of previously-started code.

This definition of time-triggered systems is fairly general. It covers single-processor systems that can be represented with time-triggered e-code programs, as they are defined by Henzinger and Kirsch [START_REF] Henzinger | The embedded machine: Predictable, portable realtime code[END_REF]. It also covers multiprocessor extensions of this model, as defined by Fischmeister et al. [START_REF] Fischmeister | Network-code machine: Programmable real-time communication schedules[END_REF] and used by Potop et al. [START_REF] Potop-Butucaru | Semantics-preserving implementation of synchronous specifications over dynamic TDMA distributed architectures[END_REF]. In particular, our model covers time-triggered communication infrastructures such as TTA and FlexRay (static and dynamic segments) [START_REF] Kopetz | The time-triggered architecture[END_REF][START_REF] Rushby | Bus architectures for safety-critical embedded systems[END_REF], the periodic schedule tables of AUTOSAR OS [START_REF]Autosar (automotive open system architecture)[END_REF], as well as systems following a preemptive multi-processor periodic scheduling model without jitter and drift. 3 It also covers the execution mechanisms of the avionics ARINC 653 standard [ARI05] provided that interruptdriven data acquisitions, which are confined to the ARINC 653 kernel, are presented to the application software in a time-triggered fashion satisfying property TT3. To our knowledge, this constraint is satisfied in all industrial settings.

Model restriction

The major advantage of time-triggered systems, as defined above, is that they have the property of repeatable timing [EKL + 09]: For any two input sequences that are identical in the large-grain timing scale determined by the timers of a program, the behaviors of the program, including timing aspects, are identical. 4 This property is extremely valuable in practice because it largely simplifies debugging and testing of real-time programs. A time-triggered platform also insulates the developer from most problems stemming from interrupt asynchrony and low-level timing aspects.

However, the applications we consider have even stronger timing requirements, and must satisfy a property known as timing predictability [EKL + 09]. Ideally, formal timing guarantees should be provided by means of off-line (static) analysis. The general time-triggered model defined above remains too complex to allow the analysis of real-life systems. To facilitate analysis, this model is usually restricted and used in conjunction with worst-case execution time guarantees on the sequential code fragments.

In this paper we consider a restriction of the general definition provided above where timer triggers occur following a fixed pattern which is repeated periodically in time. Following the convention of ARINC 653, we call this period the major time frame (MTF). The timer triggering pattern is provided under the form of a set of fixed offsets 0 ≤ t 1 < t 2 < . . . < t n < MTF defined with respect to the start of each MTF period. Note that the code triggered at each offset may still involve complex control, such as conditional execution or preemption.

This restriction corresponds to the classical definition of time-triggered systems by Kopetz [START_REF] Kopetz | Event-triggered versus time-triggered real-time systems[END_REF][START_REF] Kopetz | The time-triggered architecture[END_REF]. It covers our target platform, TTA, FlexRay (the static segment), and AU-TOSAR OS (the periodic schedule tables). At the same time, it does not fully cover ARINC 653. As defined by this standard, partition scheduling is time-triggered. The strict temporal partitioning also implies that all input/output is sampled, and that code execution is triggered by timers [START_REF] Mason | Device drivers in time and space partitioned operating systems[END_REF]. However, given that periodic processes can be started (in normal mode) with a release date equal to the current time (not a predefined date), intra-partition process scheduling does not fit our restricted model. To do so, an ARINC 653 system should not start periodic processes after system initialization, i.e. in normal mode.

Temporal partitioning

Our target architectures follow a strong temporal partitioning paradigm similar to that of ARINC 653. 5 In this paradigm, both system software and platform resources are statically divided among a finite set of partitions Part = {part 1 , . . . , part k }. Intuitively, a partition comprises both a software application of the system and the execution and communication resources allocated to it. 6We are mainly concerned in this paper with the execution resource represented by the processors. To eliminate timing interference between partitions, the static partitioning of processor time between the partitions running on it is done by means of a static time division multiplexing (TDM) scheme. In our case, the TDM scheme is built on top of the time-triggered model of the previous section. It is implemented by partitioning, separately for each processor P i , the MTF defined above into a finite set of non-overlapping windows W i = {w i 1 , . . . , w i ki } having each a fixed start offset tw i j and duration dw i j . Each window is then allocated to a single partition partw i j , or left unused. Unused windows are called spares and identified by partw i j = spare. Software belonging to partition part i can only be executed during windows belonging to part i . Unfinished partition code will be preempted at window end, to be resumed at the next window of the partition. There is an implicit assumption that the scheduling of operations inside the MTF will ensure that non-preemptive operations will not cross window end points.

For the scheduling algorithms of Section 6, the partitioning of the MTF into windows can be either an input or an output. More precisely, all, none, or part of the windows can be provided as input to the scheduling algorithms.

Task model

Following classical industrial design practices, the specification of our scheduling problem is formed of a functional specification and a set of non-functional properties. Represented in an abstract fashion, these two components form what is classically known as a task model used in the definition of our scheduling algorithms. In our case, the functional specification is provided under the form of a set of dependent tasks with a cyclic execution model. Non-functional properties include the real-time task characteristics, the allocation constraints, the preemptability of the tasks, and the partitioning constraints.

Functional specification

Simplifying assumptions

Our scheduling technique works on functional specifications of dataflow synchronous type. This allows the faithful representation of dependent task systems featuring multiple execution modes, conditional execution, and multiple relative periods.

However, the presentation of the scheduling results of this paper does not require a full description of all the details of this formalism. The task model we formally define abstracts away two difficult aspects of synchronous modeling and analysis. We present them here, pointing the reader to detailed papers covering the topics and explaining why the simplification does not reduce the generality of our results.

The first simplifying assumption concerns the relative periods of tasks. Assume that our scheduling problem requires tasks τ and τ ′ to have periods of 5 ms (milliseconds) and 20 ms, respectively. In this requirement, the real-time information is a non-functional property, defined later. But the ratio between the periods of τ and τ ′ belongs to the functional specification, facilitating for instance the definition of the way τ and τ ′ exchange data by means of a finite pattern which is repeated periodically.

Our simplifying assumption is that we work on single-period task systems where the period ratio is always 1. This simplification does not affect generality, because multi-period specifications can always be transformed into single-period ones by means of a hyper-period expansion. For instance, the hyperperiod of tasks τ and τ ′ is 20 ms. The hyperperiod expansion consists in replacing each tasks with as many instances of it as to cover the hyperperiod. Thus, τ is replaced by 4 tasks τ 1 , τ 2 , τ 3 , and τ 4 , all of period 20ms. Task τ ′ does not require replication because its period is 20 ms. Section 4.1.3 will provide a larger modeling example.

The compact representation of the functional part of multi-period specifications, as well as its efficient manipulation for scheduling purposes is elegantly covered by Forget et al. The second simplification concerns execution modes and conditional execution. Our model represents this information in an abstract way, by means of an exclusion relation between task instances. A full-fledged definition and analysis of the data expressions used as execution conditions has been presented elsewhere [START_REF] Potop-Butucaru | Semantics-preserving implementation of synchronous specifications over dynamic TDMA distributed architectures[END_REF] and would take precious space in paper.

Dependent task systems

The previous simplifications allow us to use the following model of dependent task system, which we define in 2 steps. The first covers systems with a single execution mode:

Definition 1 (Non-conditioned dependent task set) A non-conditioned dependent task system is a directed graph defined as a triple D = {T (D), A(D), ∆(D)}. Here, T (D) is the finite set of tasks. The finite set A(D) contains typed dependencies of the form a = (src(a), dst(a), type(a)), where src(a), dst(a) ∈ T (D) are the source, respectively the destination task of a, and type(a) is its type (identified by a name). The directed graph determined by A(D) must be acyclic. The finite set ∆(D) contains delayed dependencies of the form δ = (src(δ), dst(δ), type(δ), depth(δ)), where src(δ), dst(δ), type(δ) have the same meaning as for regular dependencies and depth(δ) is a strictly positive integer.

Non-conditioned dependent task sets have a cyclic execution model. At each execution cycle of the task set, each of the tasks is executed exactly once. We denote with t n the instance of task t ∈ T (D) for cycle n. The execution of the tasks inside a cycle is partially ordered by the dependencies of A(D). If a ∈ A(D) then the execution of src(a)

n must be finished before the start of dst(a)

n , for all n. Note that dependency types are explicitly defined, allowing us to manipulate communication mapping.

The dependencies of ∆(D) impose an order between tasks of successive execution cycles. If δ ∈ ∆(D) then the execution of src(δ) n must complete before the start of dst(δ) n+depth(δ) , for all n.

We are now ready to provide the full definition covering specifications with multiple execution modes. The introduction of the exclusion relation modifies the execution model defined above as follows: if (τ 1 , τ 2 , k) ∈ EX(D) then τ 1 n and τ 2 n+k are never both executed, for any execution of the modeled system and any cycle index n. For instance, if the activations of τ 1 and τ 2 are on the two branches of a test we will have (τ 1 , τ 2 , 0) ∈ EX(D). The relation EX(D) needs not be computed exactly (it can even be void) but the more precise it is, the better results the scheduling algorithms will give because tasks in an exclusion relation can be allocated the same resources at the same dates.

Modeling of the case study

The specification of the space flight application mentioned in the introduction was provided under the form of a set of AADL [AAD] diagrams, plus textual information defining specific Inria inter-task communication patterns, determinism requirements, and a description of the target hardware architecture. We present here its simpler version (with fewer tasks), the results on the full example being provided in Section 7.

Our first step was to derive a task model in our formalism. In doing this we discovered that the initial system was over-specified, in the sense that real-time constraints were imposed in order to ensure causal ordering of tasks instances using AADL constructs. Removing these constraints gave us more freedom for scheduling, allowing for a reduction in the number of partition changes. The resulting specification is presented in Fig. 1. Our model, named Simple represents a system with 3 tasks Fast, GNC, and Thermal. The periods of the 3 tasks are 100, 1000, and 1000 time units, respectively, meaning that Fast is executed 10 times for each execution of GNC and Thermal. The hyper-period unfolding described in Section 4.1.1 replicates task Fast 10 times, the resulting tasks being Fast i , 1 ≤ i ≤ 10. Tasks GNC and Thermal are left unchanged. The direct arcs connecting the tasks Fast i and GNC represent regular (intra-cycle) data dependencies of A(Simple). The arcs labeled with δ are delayed data dependencies of depth 1 where information is transmitted from one execution cycle of the synchronous specification to the next. In this simple model, task Thermal has no dependencies. Dashed arcs and numerical values are the real-time characterization of the model, explained in the next section.

Representing execution modes. Our first model has no execution modes. However, the input specification allows the specification of modes under the form of mode-dependent durations for the various tasks. There is also a requirement that task start dates (after scheduling) do not change with the mode. This is consistent with the practice of grouping into each task several functions that can be turned on or off individually according to the execution mode. We explain below how our task model allows the representation of such specifications. Note, however, that our algorithms could take better advantage of a specification where each function is associated an individual task, providing more degrees of freedom to the scheduler. If we assume that our system has 2 modes (1 and 2, which could correspond to the ground and

RR n°8109

flight modes), each of the tasks Fast and GNC having a different duration in each of the modes. We denote these durations respectively with WCET(Fast, P ) mode and WCET(GNC, P ) mode for mode = 1, 2 and P ranging over the processors where the two tasks can be executed. We assume that WCET(Fast, P ) 1 < WCET(Fast, P ) 2 and that WCET(GNC, P ) 1 > WCET(GNC, P ) 2 for all P (a form of monotony). Then, our modeling is based on the use of 2 tasks for the representation of each of Fast and GNC. The first task represents the part of computation of shorter duration, whereas the second task represents the remainder, which is only needed in modes where the duration is longer. Note that more than 2 tasks are needed when a task can have 3 or more different durations. The resulting model is pictured in Fig. 2. Here, Fast has been split into F1 and F2, the second one being executed only in mode 2. GNC has been split into GNC1 and GNC2, the second one being executed only in mode 1. We assume the mode change is triggered such that (GNC2, F2 i , 1) ∈ EX(Simple) for 1 ≤ i ≤ 10, which will allow GNC2 and the tasks F2 i to partially overlap if they are placed in the same partition.

Non-functional properties

Our task model considers non-functional properties of real-time, allocation, and partitioning types.

Period, release dates, and deadlines

The functional specification of the previous section is usually provided by the control engineers, which must also provide a real-time characterization in terms of periods, release dates, and deadlines.7 More constraints of the same types may be imposed by the system architecture, as explained below. Our model allows the specification of these characteristics in a specific form adapted to our functional specification model and time-triggered implementation paradigm.

Period. Recall from the previous section that after hyper-period expansion all the tasks of a dependent task system D have same period. In the functional model, each task is executed once per execution cycle, modulo conditional execution modeled by relation EX(D). Defining the period of these tasks is easily done by defining the period with which execution cycles are started. We shall call this period the major time frame of D and denote it MTF(D). We will require it to be equal to the MTF of its time-triggered implementation, as defined in Section 3.1.2. Throughout this paper, we will assume that MTF(D) is an input to our scheduling problem. Other scheduling heuristics, more directly derived from those of [START_REF] Potop-Butucaru | Semantics-preserving implementation of synchronous specifications over dynamic TDMA distributed architectures[END_REF] can be used in the case where it must be computed.

Release dates and deadlines. For each task τ ∈ T (D), we allow the definition of a release date r(τ) and a deadline d(τ). Both are positive offsets defined with respect to the start date of the current cycle. Their default values, meaning that no constraint is imposed, are respectively 0 and ∞.

This definition is consistent with our time-triggered implementation target where all inputs are sampled. The main assumption we make is that the sampling offsets are an input to our scheduling problem, specified using the release dates defined above.

End-to-end latency requirements are specified using a combination of both release dates and deadlines. Indeed, such end-to-end latencies should be defined on flows (chains of dependent task instances) starting with an input acquisition and ending with an output. Since acquisitions have fixed positions, the latency constraints can also be specified using fixed offsets, namely the deadlines.

Even though the release dates and deadlines defined above have the same meaning as in classical real-time, there is a fundamental difference: In our implementations the scheduler never uses these values directly (they are specification objects), relying instead on the start dates computed offline.

Modeling of the case study. The specification in Fig. 1 has MTF(Simple) = 1000 time units. Release dates and deadlines are respectively represented using descending and mounting dashed arcs. The release dates specify that task Fast uses an input that is sampled with a period of 100 time units, starting at date 0, which imposes a release date of n * 100 for the n th instance of task Fast. Although, by transitivity, the release dates on Fast constrain the start of GNC, we do not consider these constraints to be a part of the specification itself. Thus, we set the release dates of tasks GNC and Thermal to the default value 0 and do not represent them graphically.

Only task Fast 4 has a deadline that is different from the default ∞ (and is thus represented). In conjunction with the 0 release date on Fast 1 , this deadline represents an end-to-end constraint of 1400 time units on the flow defined by the chain of task instances Fast

1 n → Fast 2 n → . . . → Fast 10 n → GNC n → Fast 4 n+1
for n ≥ 0. The deadline on Fast 4 is of 400 time units, and not 1400, because the flow covers two successive execution cycles of our functional specification. The end of the flow belonging to the second execution cycle, we must subtract one MTF (1000 in our case) from the end-to-end constraint value (1400 time units).

The release dates and deadlines of Fig. 1 represent architecture-independent real-time requirements that must be provided by the control engineer. But architecture details may impose constraints of their own. For instance, assume that the samples used by task Fast are stored in a 3-place circular buffer. At each given time, Fast uses one place for input, while the hardware uses another to store the next sample. Then, to avoid buffer overrun, the computation of Fast n must be completed before date (n + 1) * 100, as required by the new deadlines of Fig. 3. Note that these deadlines can be both larger than the period of task Fast , and larger than the MTF (for Fast 10 ) to allow the faithful representation of our real-time constraints. By comparison, the specification of Fig. 1 corresponds to the assumption that input buffers are infinite.

Worst-case durations, allocations, preemptability

We also need to describe the processing capabilities of the various processors and the bus. More precisely:

• For each task τ ∈ T (D) and each processor P ∈ Procs(Arch) we provide the capacity, or duration of τ on P . We assume this value is obtained through a worst-case execution time (WCET) analysis, and denote it WCET(τ, P ). This value is set to ∞ when execution of τ on P is not possible.

• Similarly, for each data type type(a) used in the specification, we provide WCCT(type(a)) as an upper bound on the transmission time of a value of type type(a) over the bus. We assume this value is always finite.

Note that the WCET information may implicitly define absolute allocation constraints, as WCET(t, P ) = ∞ prevents t from being allocated on P . Such allocation constraints are meant to represent hardware platform constraints, such as the positioning of sensors and actuators, or designer-imposed placement constraints. Relative allocation constraints can also be defined, under the form of task groups which are subsets of T (D). The tasks of a task group must be allocated on the same processor. The use of task groups is necessary in the representation of mode-dependent task durations, as presented in Section 4.1.3 (to avoid task migrations). It is also needed in the transformations of Section 5.

Our task model allows the representation of both preemptive and non-preemptive tasks. The preemptability information is represented for each task τ by the flag is_preemptive(τ). We assume that bus communications are non-interruptible. Throughout this paper we make the simplifying assumption that preemption and partition context switch costs are negligible.8

Partitioning

Recall from Section 3.2 that there are two aspects to partitioning: the partitioning of the application and that of the resources (in our case, CPU time). On the application part, we assume that every task τ is associated to a partition part τ of a fixed partition set Part = {part 1 , . . . , part k }.

Also recall from Section 3.2 that CPU time partitioning, i.e the time windows on processors and their allocation to partitions can be either provided as part of the specification or computed by our algorithms. Thus, our specification may include window definitions which cover none, part, or all of CPU time of the processors. We do not specify a partitioning of the shared bus, but the algorithms can be easily extended to support a per-processor time partitioning like that of TTA [START_REF] Rushby | Bus architectures for safety-critical embedded systems[END_REF].

Removal of delayed dependencies

The first step in our scheduling approach is the transformation of the initial task model specification into one having no delayed dependency. This is done by a modification of the release dates and deadlines for the tasks related by delayed dependencies, possibly accompanied by the creation of new helper tasks that require no resources but impose scheduling constraints. Doing this will allow in the next section the use of simpler scheduling algorithms that work on acyclic task graphs.

The first part of our transformation ensures that delayed dependencies only exist between tasks that will be scheduled on the same processor. Assume that δ ∈ ∆(D) and src(δ) and dst(δ) are not forced by absolute or relative allocation constraints to execute on the same processor. Then, we add a new task τ δ to D. The source of δ is reassigned to be τ δ , and a new (nondelayed) dependency is created between src(δ) and τ δ . Relation EX(D) is augmented to place τ δ in exclusion with all tasks that are exclusive with src(δ). Task τ δ is assigned durations of 0 on all processors where dst(δ) can be executed, and ∞ elsewhere. Finally, a task group is created containing τ δ and dst(δ).

The second part of our transformation removes the delayed dependencies. It does so by imposing for each delayed dependency δ that src(δ) terminates its execution before the release Finally, task deadlines are changed following the approach of Blazewicz, as cited by Chetto et al. [START_REF] Chetto | Dynamic scheduling of real-time tasks under precedence constraints[END_REF]. More precisely, the deadline of each task is set to be the minimum of all deadlines of tasks depending transitively on it (including itself).9

The result of all these transformations for the example in Fig. 3, assuming that tasks Fast 4 and GNC are always allocated on the same processor and thus no helper task is needed, is pictured in Fig. 4. Note that this transformation is another source of deadlines larger than the periods. Also note that all the transformations described above are linear in the size of the number of arcs (delayed or not), and thus very fast.

Offline real-time scheduling

On the transformed task models we apply an offline scheduling algorithm whose output is a system-wide scheduling table defining the allocation of processor and bus time to the various computations and communications. The length of this table is equal to the MTF of the task model.

Our offline scheduling algorithm is a significant extension of those described by Potop et al. [START_REF] Potop-Butucaru | Clock-driven distributed real-time implementation of endochronous synchronous programs[END_REF]. New features are the handling of preemptive tasks, release dates and deadlines, the MTF, and the partitioning constraints. Other major features remain largely unchanged. This is the case for the handling of conditional execution and bus communications. We do not present these features in detail, instead pointing the interested reader to reference [START_REF] Potop-Butucaru | Clock-driven distributed real-time implementation of endochronous synchronous programs[END_REF]. Instead, we insist on the novelty points, like the deadline-driven scheduler inspired by existing work by Blazewicz (cited by Chetto et al. [START_REF] Chetto | Dynamic scheduling of real-time tasks under precedence constraints[END_REF]).

Basic principles

As earlier explained, our algorithm computes a scheduling table. This is done by associating to each task a target processor on which it will execute, a set of time intervals that will be reserved for its execution, and a date of first start. The conditional execution paradigm of our task model implies the use of conditional reservations: The same time interval can be reserved to two or more tasks if they are mutually exclusive, as defined by relation EX(D). A similar reservation model is used for the bus [START_REF] Potop-Butucaru | Clock-driven distributed real-time implementation of endochronous synchronous programs[END_REF].

Given a scheduling table S of task system D, and τ ∈ T (D), we shall denote with S.proc(τ) the target processor of τ, with S.start(τ) the date of first start, and with S.intervals(τ) the set of time intervals reserved for τ. A time interval i is defined by its start date start(i) and end date end(i). It is required that the intervals of S.intervals(τ) are disjoint, and that the start date of one of them is S.start(τ) mod MTF(D).

The execution model is as follows: The n th instance of task τ will start (modulo conditional execution) at date S.start(τ) + n * MTF(D). If its execution terminates before consuming all reserved intervals, unused space can be used by any of the suspended tasks belonging to the same partition as τ (arbitrating between multiple such tasks can be done using a priority-driven scheme not covered here). A task is suspended between intervals reserved for itself, unless using free space from another task.

The choice of processor, start date, and intervals by the scheduling algorithm must ensure that:

• The intervals reserved for a task allow the complete execution of a task instance before the next instance is started.

• Intervals of two tasks can only overlap if the two tasks are exclusive.

• The task and communication execution order imposed by the direct and delayed dependencies is respected.

• The release date of a task precedes its start date, and deadline constraints are respected.

• Intervals reserved for two tasks of different partitions cannot overlap. Moreover, an interval allocated to task τ of a partition part cannot overlap with windows allocated to other partitions.

Scheduling algorithms

The scheduling algorithm, whose top-level routine is Procedure 1, follows a classical list scheduling approach. It works by iteratively choosing a new task to schedule and then scheduling it and the necessary communications. Among the not-yet-scheduled tasks of whom all predecessors have been executed, function choose_task_to_schedule, not provided here, returns the one of minimal deadline. If several tasks satisfy this criterion, it returns one of greatest release date.

The body of the while loop allocates and schedules a single task τ, along with the communications needed to gather the input data of τ. It works by attempting to schedule τ on each of the processors that can execute it. Function group_ok determines if the relative allocation constraints and the current scheduling state allow τ to be allocated on P . Among all the possible allocations of τ, Procedure 1 chooses the one resulting in a schedule of minimal cost. In our case, cost_function chooses the schedule ensuring the earliest termination of τ. If scheduling is not possible on any of the processors Procedure 1 returns invalid_ schedule to identify the failure.

Procedure 2 does the actual scheduling of a task τ on a processor P , following a classical ASAP (as soon as possible) scheduling strategy. The scheduling is done as follows. First, the transmission of data needed by τ and not yet present on P is scheduled for communication on the bus using function schedule_bus_communications. This function schedules the transmission of both input data of τ and state variables needed to compute the execution condition of τ. We do not provide the function here, interested readers being directed to [START_REF] Potop-Butucaru | Clock-driven distributed real-time implementation of endochronous synchronous programs[END_REF].

Once communications are scheduled, we attempt to schedule the task at the earliest date after the date where all needed data is available. If this is not possible without missing the deadline, invalid_scheduling is returned to identify the failure. To allow an efficient search for free time intervals, the data structure storing the partial schedules also stores the set of free intervals of end of Fast 10 ).

To mitigate this issue, we perform a heuristic post-scheduling schedule transformation aimed at reducing partition changes. The transformation we apply is the following: The scheduling table is traversed from end to the beginning. Whenever two intervals i 1 and i 2 allocated to tasks of the same partition are separated by intervals of another partition, we attempt to group i 1 and i 2 together. Assuming i 1 starts before i 2 , our technique attempts to move i 1 just before i 2 while moving all operations between i 1 and i 2 to earlier dates. The transformation step is only performed when the resulting schedule respects the correctes properties of Section 6.1.

The result of the transformation on our example is provided in Fig. 5(b) (only 3 partition changes). Fig. 5(c) provides the schedule obtained for the more constrained example in Fig. 3.

We also provide in Fig. 5(d) an example of bi-processor scheduling (there are no bus communications to represent), and the scheduling of the two-mode specification of Fig. 2, in Fig. 5(e)). In this last case, we assume that tasks F2 and GNC belong to the same partition. Notice that the second instance of F2 and GNC share a reservation.

A larger example We have implemented our scheduling algorithms into a tool, which allowed us to schedule the proof-of-concept versions of the target application, as presented above. More important, we have been able to build and schedule a large-scale model of the application, involving 4 processors, 13 tasks, and 8 end-to-end flow constraints. We do not present it here for space reasons.

Conclusion and future work

We have proposed a technique for the distributed partitioned time-triggered implementation of synchronous dataflow specifications featuring multiple periods and conditional execution (and modes). Implementation can be done under end-to-end latency and partitioning constraints. We have successfully applied our technique on a realistic spacecraft case study.

Future work will focus on 2 main directions. On the scheduling side, we will focus on the fine tuning of the scheduling and the promising slot minimization heuristics. On the modeling side, we will take inspiration from Forget et al. to allow the compact representation and efficient manipulation of multi-period task models. It is important here to preserve a faithful representation of timing requirements, without over-constraining, and to allow a smooth integration of conditional execution.

  Previous work by Forget et al. [PFB + 11] and Marouf et al. [MGS12] on the implementation of multi-periodic synchronous programs, as well as previous work by Blazewicz and Chetto et al.

  [PFB + 11], drawing influences from Chetto et al. [CSB90] and Pouzet et al. [CDE + 06], among others.

Definition 2 (

 2 Dependent task set) A dependent task set is a tuple D = {T (D), A(D), ∆(D), EX(D)} where {T (D), A(D), ∆(D)} is an unconditioned dependent task set and EX(D) is an exclusion relation EX(D) ⊆ T (D) × T (D) × N.

Fast 3 Figure 1 :

 31 Figure 1: The Simple example (MTF=1000 time units)

Figure 2 :

 2 Figure 2: Representing mode-dependent WCET variations

Fast 3 Figure 3 :

 33 Figure 3: Adding 3-place circular buffer constraints to our example

Figure 4 :

 4 Figure 4: Delay removal result

Figure 5 :

 5 Figure 5: Resulting schedules: For the example in Fig. 1, single-processor without slot minimization (a) and with it (b), and bi-processor (d). For the example in Fig. 3 (c), and for the two-mode example of Fig. 2 (e).

  Fast 4 Fast 5 Fast 6 Fast 7 Fast 8 Fast 9 Fast 10

	0	100	200	300	400	500	600	700	800	900	1000
		Fast 1	Fast 2	Fast 3
											1300
		Thermal								GNC

Partially supported by the FUI8 PARSEC project.1 As such, it generalizes classical periodic real-time scheduling concepts, by relaxing fixed release intervals into more complex repetitive patterns.RR n°8109

For distributed multiprocessor systems, we assume it is provided by a platform such as TTA[START_REF] Kopetz | The time-triggered architecture[END_REF] or by a clock synchronization technique such as the one of Potop et al.[START_REF] Potop-Butucaru | Semantics-preserving implementation of synchronous specifications over dynamic TDMA distributed architectures[END_REF].RR n°8109

But these two notions must be accounted for in the construction of the global clock[START_REF] Potop-Butucaru | Semantics-preserving implementation of synchronous specifications over dynamic TDMA distributed architectures[END_REF].

We assumed that programs are functionally deterministic.

Spatial partitioning aspects are not covered in this paper.

The aim of this static allocation is to limit the functional and temporal influence of one partition on another to a set of explictly-specified inter-partition communication and synchronization mechanisms.Inria

RR n°8109

This characterization is directly derived from the analysis of the control system, and does not depend on architecture details such as number of processors, speed, etc. Inria

Taking them into account is work in progress Inria

More generally, the recomputation of release dates and deadlines by means of a fixed-point computation can be useful before the removal of delayed arcs to provide for longer deadlines.RR n°8109

RR n°8109RESEARCH CENTRE PARIS -ROCQUENCOURTDomaine de Voluceau, -Rocquencourt B.P. 105 -78153 Le Chesnay Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

the processors and buses. Window allocations taken as input by our scheduler are passed to Procedure 1 through parameter initial_schedule, which contains no task allocation, but already constrains the free interval set.

Looking for individual intervals is done by function get_first_interval, not provided here. This function takes as input the preemptability flag of the task. For non-preemptive tasks, it looks for the first free interval long enough to allow the execution of the task and satisfying the execution condition and partitioning constraints. For preemptive tasks, this function may be called several times to find the first free intervals satisfying the execution condition and partitioning constraints and of sufficient cummulated length to cover the needed duration. When unable to find a valid interval, function get_first_interval returns an invalid interval identifying the failure. Depending on the task deadline, the search for free intervals may loop over the MTF.

Post-scheduling slot minimization

The algorithm of the previous section follows a classical ASAP deadline-driven scheduling policy. Such policies are good at ensuring schedulability. It is easy to prove that our algorithm is even optimal in certain cases (all-preemptive, single processor, no execution condition, no delayed dependency).

However, resulting schedules may have a lot of unneeded preemptions and, most importantly, partition changes which are notoriously expensive. Consider our example of Fig. 1 and an architecture with a single processor P such that WCET(Fast, P ) = 40, WCET(GN C, P ) = 140, and WCET(Thermal, P ) = 100. We assume a partitioning approach à la IMA, where the 3 tasks have each one partition. Then, Fig. 5(a) provides the output of the scheduling phase. This figure shows the allocation of the time intervals to the various tasks over the MTF. Time flows from left to right, and the target processor is shown on the right. This schedule features no less than 11 partition changes (note that no partition change occurs between the start of Fast 5 and the