Marie Cottrell

Patrice Gaubert

Patrick Letremy

Patrick Rousset

Analyzing and representing multidimensional quantitative and qualitative data: Demographic study of the Rhône valley. The domestic consumption of the Canadian families

Keywords:

1999.09

INTRODUCTION

The SOM algorithm is now extensively used for data mining, representation of multidimensional data and analysis of relations between variables( [START_REF] Blayo | Data analysis : How to compare Kohonen neural networks to other techniques ?[END_REF], [START_REF] Blayo | Algorithme de Kohonen: application à l'analyse de données économiques[END_REF], [START_REF] Cottrell | Daily Electrical Power Curves : Classification and Forecasting Using a Kohonen Map, From Natural to Artificial Neural Computation[END_REF], [START_REF] Cottrell | Theoretical aspects of the SOM Algorithm, WSOM'97[END_REF], [START_REF] Deboeck | Visal Explorations in Finance with Self-Organization Maps[END_REF], [START_REF] Demartines | Organization measures and representations of Kohonen maps[END_REF], [START_REF] Demartines | Curvilinear component analysis: a self-organizing neural network for non linear mapping of data sets[END_REF], [START_REF] Kaski | Data Exploration Using Self-Organizing Maps[END_REF], [START_REF] Kohonen | Self-Organization and Associative Memory[END_REF], [START_REF] Kohonen | Self-Organizing Maps[END_REF]). With respect to any other classification method, the main characteristic of the SOM classification is the conservation of the topology: after learning, « close » observations are associated to the same class or to « close » classes according to the definition of the neighborhood in the SOM network. This feature allows to consider the resulting classification as a good starting point for further developments as shown in what follows.

But in fact its capabilities have not been fully exploited so far. In this chapter, we present some of the techniques that can be derived from the SOM algorithm: the representation of the classes contents, the visualization of the distances between classes, a rapid and robust twolevel classification based on the quantitative variables, the computation of clustering indicators, the crossing of the classification with some qualitative variables to interpret the classification and give prominence to the most important explanatory variables. See in [START_REF] Cottrell | Analyzing a contingency table with Kohonen maps : a Factorial Correspondence Analysis[END_REF], [START_REF] Cottrell | Multiple correspondence analysis of a crosstabulation matrix using the Kohonen algorithm[END_REF], [START_REF] Cottrell | The Kohonen algorithm: A Powerful Tool for Analysing and Representing Multidimensional Quantitative and Qualitative Data[END_REF], [START_REF] Cottrell | Theoretical aspects of the SOM Algorithm, WSOM'97[END_REF] precise definitions of all these techniques. We also define two original algorithms (KORRESP and KACM) to analyze the relations between qualitative variables.

The paper is organized as follows : in sections 2 and 3, we present the main tools, in section 4 and 5, we show real applications in socio-economic fields.

THE MAIN TECHNIQUES

Let us give some notations : we consider a set of N observations, where each individual is described by P quantitative real valued variables and K qualitative variables. The main tool is a Kohonen network, generally a two-dimensional grid with n units, but the method can be used with any topological organization of the network. After learning, each unit i is represented in the R P space by its weight vector C i (or code vector). We do not examine here the delicate problem of the learning of the code vectors ( [START_REF] Cottrell | Theoretical aspects of the SOM Algorithm, WSOM'97[END_REF], [START_REF] Kohonen | Self-Organization and Associative Memory[END_REF], [START_REF] Kohonen | Self-Organizing Maps[END_REF]) which is supposed to be successfully realized from the N observations restricted to their P quantitative variables. code vectors. The distance in R P is the Euclidean distance in general, but it can be chosen in another way according to the application.

Representation of the contents:

The classes are represented according to the chosen topology of the network, along a chain, or on a grid, and all the elements can be drawn inside their classes. So it is possible to see how the observations are modified from a class to its neighbors and to appreciate the homogeneity of the classes.

Distances between classes

To highlight the true inter-classes distances, following the method proposed in [START_REF] Cottrell | A Kohonen Map Representation to Avoid Misleading Interpretations[END_REF], we represent each unit by an octagon inside the cell of the SOM map. The bigger it is, the closer it is to the border, the nearer the code vector is of its neighbors. This avoids misleading interpretations and gives an idea of the discrimination of the classes.

Two-level classification:

A hierarchical clustering of the n code vectors puts together the most similar SOM classes and provides a second classification into a smaller number of classes. These macro-classes create connected areas in the initial map, so the neighborhood relations between them are kept. This grouping together facilitates the interpretation of the contents of the classes.

Crossing with qualitative variable:

To interpret the classes according to an explicative qualitative variable, it is valuable to study the discrete distribution of its modalities in each class. We propose to draw inside each cell a frequency pie for example. So we make clear the continuity of the classes as well as the cutoffs. We also can associate to a SOM class the more frequent modalities of a qualitative variable and in this manner give a better description of the classes.

ANALYSIS OF RELATIONS BETWEEN QUALITATIVE VARIABLES

Let us define here two original algorithms to analyze the relations between qualitative variables. The first one is defined only for two qualitative variables. It is called KORRESP and is analogous to the classical Correspondence Analysis. The second one is devoted to the analysis of any finite number of qualitative variables. It is called KACM and is similar to the Multiple Correspondence Analysis. See [START_REF] Cottrell | Analyzing a contingency table with Kohonen maps : a Factorial Correspondence Analysis[END_REF], [START_REF] Cottrell | Multiple correspondence analysis of a crosstabulation matrix using the Kohonen algorithm[END_REF] for previous related papers.

For both algorithms, we consider a sample of individuals and a number K of qualitative variables. Each variable k = 1,2, ..., K has m k possible modalities. For each individual, there is one and only one modality. If M is the total number of modalities, each individual is represented by a row M-vector with values in {0, 1}. There is only one 1 between the 1st component and the m 1 -th one, only one 1 between the m 1 +1-th component and the (m 1 +m 2) -th one and so on.

In the general case, where M > 2, the data are summarized into a Burt Table which is a cross tabulation table. It is a M × M symmetric matrix and is composed of K × K blocks, such that the (k,l)-block B kl (for k ≤ l) is the (m k × m ll ) contingency table which crosses the variable k and the variable l. The block B kk is a diagonal matrix, whose diagonal entries are the numbers of individuals who have respectively chosen the modalities 1, 2, ..., m k , for modality k. From now on, the Burt Table is denoted by B.

In the case M=2, we only need the contingency table T which crosses the two variables. In that case, we set p (resp. q) for m 1 (resp. m 2 ).

The KORRESP algorithm

Let M = 2. In the contingency table T, the first qualitative variable has p levels and corresponds to the rows. The second one has q levels and corresponds to the columns. The entry n ij is the number of individuals categorized by the row i and the column j. From the contingency table, the matrix of relative frequencies (

f ij = n ij /(Σ ij n ij )) is computed.
Then the rows and the columns are normalized in order to have a sum equal to 1. The row profile r(i), 1 ≤ i ≤ p is the discrete probability distribution of the second variable when the first variable has modality i and the column profile c(j), 1 ≤ j ≤ q is the discrete probability distribution of the first variable when the second variable has modality j. The classical Correspondence Analysis is a simultaneous weighted Principal Component Analysis on the row profiles and on the column profiles. The distance is chosen to be the χ 2 distance. In the simultaneous representation, related modalities are projected into neighboring points.

To define the algorithm KORRESP, we build a new data matrix D: to each row profile r(i), we associate the column profile c(j(i)) which maximizes the probability of j given i, and conversely, we associate to each column profile c(j) the row profile r(i(j)) the most probable given j. The data matrix D is the ((p+q) × (q+p))-matrix whose first p rows are the vectors (r(i),c(j(i))) and last q rows are the vectors (r(i(j)),c(j)). The SOM algorithm is processed on the rows of this data matrix D. Note that we randomly pick the inputs among alternatively the p first rows and the q last ones and that the winning unit is computed only on the q first components in the first case, on the p last ones in the second case according to the χ 2 distance. After convergence, each modality of both variables is classified into a Voronoï class. Related modalities are classified into the same class or into neighboring classes. This method give a very quick, efficient way to analyze the relations between two qualitative variables. See [START_REF] Cottrell | Analyzing a contingency table with Kohonen maps : a Factorial Correspondence Analysis[END_REF] for real-world applications.

The KACM Algorithm

When there are more than two qualitative variables, the above method no longer works. In that case, the data matrix is the Burt Table B. The rows are normalized, in order to have a sum equal to 1. At each step, we pick a normalized row at random according to the frequency of the corresponding modality. We define the winning unit according to the χ 2 distance and update the weight vectors as usual. After convergence, we get an organized classification of all the modalities, where related modalities belong to the same class or to neighboring classes. In that case also, the KACM method provides a very interesting alternative to classical Multiple Correspondence Analysis.

The main advantages of both KORRESP and KACM methods are their rapidity and their small computing time. While the classical methods have to use several representations with decreasing information in each, ours provide only one map, that is rough but unique and permits a rapid and complete interpretation. See [START_REF] Cottrell | Analyzing a contingency table with Kohonen maps : a Factorial Correspondence Analysis[END_REF], [START_REF] Cottrell | Multiple correspondence analysis of a crosstabulation matrix using the Kohonen algorithm[END_REF] and [START_REF] Cottrell | Understanding the Leasing Decision with the Help of a Kohonen Map. An Empirical Study of the Belgian Market[END_REF] for the details and financial applications.

DEMOGRAPHIC STUDY OF THE RHÔNE VALLEY

The data come from the project ARCHEOMEDES, supported by the EU, in collaboration with the laboratory P.A.R.I.S (University Paris 1).

We consider 1783 communes in the Rhône valley, in the south of France. This valley is situated on the two banks of the river Rhône. It includes some big cities (Marseille, Avignon, Arles, ...), some small towns, many rural villages. A large part is situated in medium mountains, in very depopulated areas since the so-called drift from the land. At the same time, in the vicinity of the large or small towns, the communes have attracted a lot of people who are working in urban employment. The goal of this study is to understand the relations between the evolution of the population and the professional composition in each communes.

The data include two tables. The first one gives the numbers of seven population census (1936,1954,1962,1968,1975,1982,1990). These numbers are normalized by dividing by their sum, to keep the evolution and not the absolute values. The second one contains the current numbers of working population, distributed among six professional categories (farmers, craftsmen, managers, intermediate occupations, clerks, workers). In this second table, the data are transformed into percentages and will be compared with the χ 2 distance.

The first step consists in defining two classifications of the communes from the two types of data. We use a Kohonen one-dimensional network (a chain) to transform the quantitative variables into qualitative ordered characters. First we classify the communes into 5 classes from the census data, and then into 6 classes from the professional composition data.

The first classification into 5 classes is easily interpretable. The classes are arranged according to an evident order : there are the communes with strong increase (aug_for), with medium increase (aug_moy), with relative stability (stable), with medium decrease (dim_moy), with strong decrease (dim_for). See in fig. 4

From these two classifications, we compute the contingency table, see table 4.1. A quick glance shows a strong dependence between the row variables (census classes) and the column variables (professional classes).

E F dim_for

The conclusions are simple. The rural communes where the agriculture is dominant are depopulated, while the urban ones have an increasing population. The relations are very precise : we can note the pairs of modalities ((dim_for), F), ((dim_moy), D), ((stable), C), ((aug_moy), B), ((aug_for), A).

Actually, the SOM-inspired method is very quick and efficient, and gives the basic points of the information with only one representation. As to the classical correspondence method, it is also useful but its computation time is longer and it is usually necessary to examine several projections to have a complete analysis, since each axis represents only a percent of the total information. See in Fig. 5.1 the mean consumption structure for the 1992 survey.

The classes

We want to compare two clustering methods : 1) a SOM algorithm using a two-dimensional (8 × 8) grid, that defines 64 classes, whose number is then reduced to 10 macro-classes, by using a hierarchical clustering with the 64 code vectors, in order to get an easier interpretation of their contents. 2) a hierarchical classification into 10 classes with the Ward method.

The SOM classes and the macro classes

Fig. 5.2 represents the 64 SOM classes with their code vectors and the macro-classes which differ by their texture. First we note that, due to the topological conservation property of the SOM algorithm that the macro-classes group only neighboring SOM classes. In Fig 5 .3, the distances between the SOM classes are drawn, following the method suggested in [START_REF] Cottrell | A Kohonen Map Representation to Avoid Misleading Interpretations[END_REF]. Observe that the grouping into 10 macro-classes respects the distance : the changes of macroclasses generally occur where the distances are larger. Cahiers de la MSE -1999.09 The SOM classes could be analyzed, but it is difficult to keep and characterize 64 types of classes. Conversely, the 10 macro classes have well separated features. One can observe that :

1. the sizes of the macro-classes are about 600 to 700 households, or about 1200, except one with a little more than 400. This macro-class gathers only 4 SOM classes which have a very special profile (as it will be seen below). 2. in all the macro-classes, there are as many 1986 data as 1992 ones. So there is no significant effect of the year of the survey. 3. the mean profiles of the 10 macro-classes are well identified, and are different from the mean profile of the whole population.

Nine types of consumption items are at the origin of the differentiation of the macroclasses.

1. macro-class 5 is dominated by the Housing item (with a 38 %).

2. macro-class 9 is characterized by the importance of the Housing item (26 %) and the Collective Transport. 3. for two macro-classes (1 and 2), the Vehicle purchase makes the difference. While the general mean value for this item is about 5 %, the value is 17 % in macro-class 1, and the other items are reduced in an homothetic way. In macro-class 2, the value is 36 %, and the housing expenditure is small, what corresponds to a large representation of the house-owners (71 % instead of 60 % in general). 4. the Food Home (20 %) and the Others items define the macro-class 7. 5. in macro-class 3, the Security (insurance) expenditure is the double mean value. 6. macro-class 10 corresponds to a large value of the Gifts item (25 %). 7. leisure item defines macro-class 8 (with 13 %), while tobacco defines macro-class 4 (with 12 %) and education is dominant in macro-class 6 (10 %).

The grouping into 10 macro-classes increases the contrast with respect to the mean consumption profile. All the SOM classes inside a macro-class have more or less the same features, with some specific characteristics.

Hierarchical clustering

If we consider the 10 classes defined by a hierarchical Ward clustering on the consumption profiles, the results are disappointing. The groups have unequal sizes, the differentiation between groups are more quantitative than qualitative, and poorer in information. For example, 4 groups have more than 1000 or 2000 elements, while the others have about 200 or 400. Among the 4 more important groups, 3 (the 1, 4, 6) have a mean profile similar to the general mean one, with only one component a little larger. Groups 2 and 7 correspond to a high housing expenditure, and cannot be clearly set apart, and so on.

Actually the correctly spotted groups are the small ones, while the others are not very different from one to another, and are similar to the general population. Furthermore, some specific behaviors, in particular those which are distinguished by a relatively large importance of the Security or Education expenditures, do not emerge in this clustering. For example, the partitioning of the population according to the poverty-wealthy criterion (Wealthy), indicates that the classes having a strong proportion of rich or quasi-rich people are rather situated at the extremities of the diagonal right top -left bottom, the poor and quasipoor being at the central area. At the same time, the opposition owner-tenant is distributed according to a simple opposition on this diagonal. The first ones are at the left bottom, the second ones at the opposite. We rediscover a well-known situation of poor people, who can be as well owner as tenant of their lodgings. It is possible to analyze in this way the four graphic representations. Actually, it is the combination of these characteristics that we have to examine to interpret the zones of the grid, as gathered by the classification into 10 classes.

Conclusion

The SOM algorithm is therefore a powerful tool to analyze multidimensional data and to help to understand the underlying structure. We are now working about local representation of the contents of a class in relation with the neighboring classes, in order to give an interpretation to the significant and discriminate variables. There is no doubt that the related data mining techniques will have a large development in many scientific fields, where one deals with numerous, large dimensioned data.

Cahiers de la MSE -1999.09

  .1 the code vectors and in fig. 4.2 the contents of the 5 classes.

1 :

 1 The code vectors of the 5 classes (first classification). The curves represent the population evolution along the seven census.

Fig. 4 . 2 :

 42 Fig. 4.2 : The contents of the 5 classes (first classification). In each class, all the communes vectors are drawn in a superposed way.

3 :

 3 The code vectors of the 6 classes (second classification). The curves correspond to the (corrected) proportion of farmers, craftsmen, managers, intermediate occupations, clerks, workers.

Fig. 4 . 4 :

 44 Fig. 4.4 : The contents of the 6 classes (second classification). Note that in class A, some communes are very specific, they do not have any farmer, but all their inhabitants belong to one or two categories.

Fig. 4 . 5 :

 45 Fig.4.5 : The first projection of the modalities using a Factorial Correspondence Analysis Table 4.3 : The two-dimensional Kohonen map with the results of KORRESP.

Fig. 5 . 1

 51 Fig. 5.1 Mean Consumption Profile in 1992.

Fig. 5 . 2 :

 52 Fig. 5.2 : The 64 SOM classes, their code vectors and the macro-classes.

Fig 5 . 5 :

 55 Fig 5.5 : The distribution of the variable Age

Fig. 5 . 6 :

 56 Fig. 5.6 : The distribution of the variable Education.

Fig 5 . 7 :

 57 Fig 5.7 : The distribution of the variable Tenure Status

Table 4 .

 4 1 : Contingency Table which crosses the two classifications. To analyze this dependence, we use a classical Correspondence Analysis and the KORRESP algorithm See in fig. 4.5 and table 4.3, the results.

		A	B	C	D	E	F
	aug_for	223	53	26	9	0	0
	aug_moy	85	112	86	34	7	1
	stable	80	100	112	113	54	22
	dim_moy	29	50	55	80	56	57
	dim_for	34	18	35	57	69	126
			Cahiers de la MSE -1999.09

Cahiers de la MSE -1999.09

The domestic consumption of the Canadian families

The data have been provided by Prof. Simon Langlois from the Université of Laval.

The purpose of the study is to define homogenous groups from the point of view of their consumption choices. The interest of such clustering is at least double. On the one hand, when one has successive surveys that include distinct individuals stemming from a same population, we can build a pseudo-panel, composed of synthetic individuals representative of the groups, which will be comparable from one survey to another.

On the other hand, it facilitates the matching of distinct surveys when each one provides different information about samples extracted from the same population. The constitution of groups which are homogenous for these data allows the linking of all the surveys. For example, it is possible to apply this method to match consumption surveys done for the same period with different samples (each sample is answered about the consumption of half-nomenclature). The matching is necessary to build complete consumption profiles. One has to notice that this method does not exactly correspond to the methodology proposed by Deaton, 1985, (13), who follows the same cohort from one survey to another by considering only individuals born at the same time.

When pseudo-panels are considered, one uses to build the clusters by crossing some significant variables. For example, to study the households consumption modes, the significant variables are the age cohort, the education level and the income distribution. Here, we use the Kohonen algorithm to define the clusters and apply it to the data of two consumption surveys. We also compare the results to those that we obtain from a standard classification.

The data

We consider two consumption surveys, performed by Statistiques Canada, in 1986 and 1990, with about 10 000 households which were not the same ones from one survey to the other. The consumption structure is known through a 20 functions nomenclature, described in Table 5.1. Each household is represented by its consumption structure, expressed as percentages of the total expenditure. The two surveys have been gathered in order to define classes including individuals which belong to one or the other year. So it will be possible to observe the dynamic evolution of the households groups which have similar consumption structures.

One can see that for any classification method, the classes contain in almost equal proportion data of the two surveys. It seems that there is no temporal effect on the groups, which simplifies the further analyses.

So from now on, we continue the analysis by using the SOM classification, followed by the grouping into 10 macro-classes.

Crossing with qualitative variables

To understand better the factors which determine the macro-classes, and to allow their identification, we use a graphic representation of some qualitative variables, that were not present in the classification.

For that, we use 4 qualitative variables, that give a socio-demographic description of the households :

1. the first one (Wealth) is a variable with 5 modalities (poor, quasi-poor, middle, quasi-rich, rich). This variable is defined by combining three simple criteria, the income distribution, the total expenditure, the food expenses, according to the age, the education level and the regional origin. 2. the second one (Age) is the age of the head of household, with 6 modalities (less than 30, 30-39, 40-49, 50-59, 60-69, more than 69). 3. the educational level (Education), with 5 levels (primary, secondary, post-secondary without diploma, post-secondary with diploma, university diploma). 4. the tenure status (Tenure Status) (owner or tenant).

For each SOM class, we compute the distribution of the four qualitative variables (which did not participate to the classification), and we represent it as a sector diagram (a pie) inside the cell. We observe that there is also a continuity for the variations of the socio-demographic variables distributions among the SOM classes. But they provide other information, different from the previous one.


Marie-Philippine Séba

Pauline Maillot

Sylvain Hanneton

Gilles Dietrich

Age related postural responses during repeated virtual stimulation: traditional analysis and analysis of the complexity

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

BACKGROUND

The aging of the sensorimotor system alters the perception of our environment and reduces our ability to react quickly to stimuli. This phenomenon contributes to increase the risk of falling in older adults. One way to artificially induce sensory conflicts is to expose individuals to virtual environments, causing conflicts between visual and sensory signals. Postural control reflects the central nervous system's processing of sensory conflicts. A traditional analysis uses the postural parameters resulting from the center of pressures such as the length of the trajectory of the center of pressures or even the mean velocity.

It allows to observe the repercussions of sensory conflicts. On the other hand, a complexity analysis uses postural parameters such as fractal dimension or entropy. Complexity is a marker of sensory state. A decrease in complexity and variability may be due to a pathological condition. Complexity is an estimator of fall risk in older adults [START_REF] Seigle | Dynamical structure of center of pressure fluctuations in elderly people[END_REF][START_REF] Zhou | The complexity of standing postural sway associates with future falls in community-dwelling older adults: the MOBILIZE Boston Study[END_REF]. On the other hand, repetitive patterns are adaptation markers [START_REF] Riley | Recurrence quantification analysis of postural fluctuations[END_REF]. This is why this study addresses the following question: are age, repetition and translations influencing traditional and complexity-based postural parameters when exposed to repeated virtual stimulation?

PURPOSE Investigate the effects of age on postural responses during virtual reality stimulation using traditional analysis and complexity analysis Quantifying exploratory postural strategies. Identifying repeating patterns.

Wii Balance Board Oculus Rift (CV1)

According to the mean velocity, the visual disturbance have indeed caused a sensory conflict. Before the visual disturbance, aging led to an increase in mean velocity, but after the disturbance, all participants appeared to be equally affected. Complexity analysis (Sample Entropy and Percent Recurrence) showed that after the disturbance, participants restricted their postural oscillations. It is by looking at the complexity of the signal according to the age of the participants that differences emerged after visual disturbance. There was an increase in fractal dimension with age, an increase in sample entropy, and a decrease in percent recurrence. But with repetition, the age of the participants no longer correlated with the complexity of the signal. Five repetitions allowed adaptation to the visual disturbance (translations) with aging [START_REF] Fransson | Postural instability in an immersive Virtual Reality adapts with repetition and includes directional and gender specific effects[END_REF].

  analyzes here focuse only on the sequences before and after the forward and backward translations.

  the complexity of the center of pressure allow to observe the impact of a sensory conflict on posture and quality of adaptation. With age, visual disturbances cause a restriction of postural oscillations, but repetition allows adaptation to the stimulus through a relaxation of postural oscillations. KEY POINTS Traditional analysis and analysis of the complexity of CoP data Increase of mean velocity after visual disturbance The fractal dimension, the entropy and the percentage of recurrence reveal the influence of age on postural adaptation to visual disturbances Studying aging and sensory conflicts with Virtual Reality identical exposures to forward and backward translations Age as a continuous variable (21 to 86 y.o.)


Wolfram Kloppmann

Jean-Yves Le Pogam

Lise Leroux

du XIVe au XVIe siècle : enjeux, méthodes et résultats d'un programme de recherche

archive ouverte pluridisciplinaire HAL, est destinée au dépôt

L'


Rémi Meunier

Thomas Carle

Thierry Monteil

Correctness and Efficiency Criteria for the Multi-Phase Task Model

Keywords: 2012 ACM Subject Classification Computer systems organization → Real-time systems, Computer systems organization → Multicore architectures, Computer systems organization → Embedded software Keywords and phrases Task model, Interference, Multicore architectures Digital Object Identifier 10.4230/LIPIcs.ECRTS.2022.9

This paper investigates how the multi-phase representation of real-time tasks impacts their implementation and the precision of the interference analysis in a multi-core context. In classical scheduling and interference analyses, tasks are represented as a single phase with a duration equal to their Worst-Case Execution Time (WCET) in isolation, annotated with their worst-case number of accesses. We propose a general formal definition of a task model in which tasks are represented as a sequence of such phases: the multi-phase model. We then provide a set of general correction criteria for the implementation of tasks represented in the multi-phase model, which is agnostic of the analysis method applied on the tasks. We also use the multi-phase model on an avionics case-study and study its impact on the interference analysis. Finally, we define a set of efficiency criteria using a statistical study of the most efficient multi-phase shapes.

Introduction

The growing adoption of multi-core processors in industrial real-time systems [START_REF] Sander | The promised future of multi-core processors in avionics systems[END_REF][START_REF] Schneider | Migration of automotive real-time software to multicore systems: First steps towards an automated solution[END_REF] raises the challenge of providing safe and tight Worst-Case Execution Time (WCET) bounds for tasks running in parallel on separate cores. Indeed, in multi-core architectures, the cores execute their processes/threads independently from one another, but they share some hardware components such as caches, buses and memories. Interference may happen in these shared components: when a task requires to access a component which is already in use by another task running on another core, it has to wait until the component is free again. This phenomenon incurs execution delays which depend on the context of the task execution (which other tasks are running in parallel, and are they accessing the shared resources ?).

In traditional single-core WCET analysis [1, 3], each task is analysed in isolation i.e. as if no other task was running in parallel. Then a schedulability or Worst-Case Response Time (WCRT) analysis is performed using a model in which each task is represented by its WCET, in order to guarantee that each individual task meets its deadline or that the system as a whole meets an end-to-end timing constraint. A direct consequence of the delays incurred by interference is that traditional WCETs no longer represent a safe upper-bound on the execution time of the tasks when they are run on multi-core processors. It becomes necessary to model tasks using at least their WCET in isolation and their worst-case number of accesses to shared components, and to perform an additional interference analysis in order to obtain a safe over-estimation of their execution time. However, this classical model, which maps one task to one temporal phase was not designed with interference analysis in mind, and may not be the best-suited to analyse tasks running in parallel. More recent models represent each task as a sequence of phases, each characterized by a WCET and a number of accesses, either as an attempt to increase the precision of the interference analysis [START_REF] Arora | Buscontention aware schedulability analysis for the 3-phase task model with partitioned scheduling[END_REF][START_REF] Carle | Reducing timing interferences in real-time applications running on multicore architectures[END_REF][START_REF] Pellizzoni | Worst case delay analysis for memory interference in multicore systems[END_REF], or in order to build schedules in which there is no interference [START_REF] Durrieu | Predictable flight management system implementation on a multicore processor[END_REF][START_REF] Rouxel | Hiding communication delays in contention-free execution for spm-based multi-core architectures[END_REF]. This multi-phase abstraction maps temporal phases to actual sections of code which are separated by synchronizations. The shape of the phases may be dictated by a programming model in which the programmers insert synchronizations at particular points (e.g. [START_REF] Durrieu | Predictable flight management system implementation on a multicore processor[END_REF]), or may be designed during the analysis and enforced by synchronizations that are injected in the code afterwards (e.g. [START_REF] Carle | Static extraction of memory access profiles for multi-core interference analysis of real-time tasks[END_REF]).

In the remainder of the paper, we focus on memory accesses as the sole source for interference in the system. However, the abstractions that we describe naturally support any other kind of interference source: the only thing that changes is the analyses that must be performed on the code in order to obtain the abstract models of the tasks, which are not considered in the scope of the paper. In particular, we consider non-preemptive static (or fixed-priority time-triggered) scheduling, but limited preemptions could be supported by adapting classic cache-related preemption delay (CRPD) computation techniques.

In this paper we make the following contributions: we give a general, formal description of the multi-phase model that is agnostic of the method used to analyze the tasks. As such it can be seen as a generalization of the 2-phase [START_REF] Pellizzoni | A predictable execution model for cots-based embedded systems[END_REF] and 3-phase [START_REF] Durrieu | Predictable flight management system implementation on a multicore processor[END_REF] models, and as an extension of the model of [START_REF] Carle | Static extraction of memory access profiles for multi-core interference analysis of real-time tasks[END_REF] to the notion of synchronizations. we investigate the relationship between the phases and the synchronizations that enforce them, that is to say between the multi-phase analysis model of tasks and their actual implementation. We show that synchronizations are not mandatory at the boundaries between two consecutive phases, and provide criteria to validate the implementation of a task w.r.t. the assumptions that were made during the analysis. Once again the criterion is agnostic about the way the analysis is actually performed. we apply the multi-phase model on an avionics case-study, and show that correlating the shape of the model to the actual behavior of the tasks may not lead to the best results.

As a result we investigate how the shape of multi-phase representations impacts the result of static interference analysis, and deduce a promising heuristic objective to build multi-phase models of tasks. Since we discuss a general model and not a particular method, this study is based on a statistical experiment relying on synthetic artifacts.

The paper is organized as follows: we present the related work in Section 2 and we introduce formal definitions in Section 3. Then, in Section 4 we study the relationship between phases and synchronizations. In Section 5, we present our results on the ROSACE case-study. In Section 6, we detail our statistical study of the multi-phase model, and finally we conclude in Section 7.

Related Work

The problem of identifying, quantifying and possibly reducing the interference between real-time tasks running on multi-core processors is one of the most pressing issues that the real-time community is facing. Consequently, a lot of work has been done already, and various methods have been developed, although none of them seems to be entirely satisfying [START_REF] Maiza | A survey of timing verification techniques for multi-core real-time systems[END_REF].

One of the most comprehensive approaches so far, presented in [START_REF] Davis | An extensible framework for multicore response time analysis[END_REF], uses the execution traces of the tasks composing the system, and models all the hardware components shared between cores (e.g. buses, RAMs) in order to quantify the exact worst-case amount of interference in the system, given a fixed priority scheduling policy. This analysis method is thus able to provide a safe and tight interference-aware WCRT for a task system. However the authors point out that working with all the possible execution traces of all the tasks composing a system is not feasible for realistic, industrial systems. They advocate the use of a more abstract representation of the tasks execution in order to overcome this intractability issue, but do not provide such an abstraction. It thus remains open to find a suitable candidate abstraction to achieve a trade-off between tractability and precision of the analysis.

Other approaches, inspired by compilation methods and low-level code analysis, use static scheduling approaches to handle, reduce or suppress the interference in the system. These methods are inspired by the PRedictable Execution Model (PREM) introduced in [START_REF] Pellizzoni | A predictable execution model for cots-based embedded systems[END_REF]. This model, originally designed for single-core processors with Input/Output registers, abstracts the execution of tasks as a sequence of so called memory and execution phases. In a memory phase, the core executes only memory (or I/O register) operations, which require to send or receive data across an interconnect. In an execution phase however, the code is executed locally in the core, and is guaranteed not to make accesses to the interconnect. As a result, only the memory phases are subject to interference. The Acquisition Execution Restitution (AER) model [START_REF] Durrieu | Predictable flight management system implementation on a multicore processor[END_REF] can be seen as an extension of the PREM model to the context of avionics systems running on multi-core architectures. In AER, each task is divided into exactly three phases: an acquisition phase that loads to a core-local memory (cache or scratchpad) all the code and data which may be necessary to execute the task, an execution phase that executes the task code locally, and a restitution phase in which the results of the task are written back to the shared memory. A static schedule of the tasks is computed in which the acquisition and restitution phases of tasks are guaranteed not to happen simultaneously, and synchronizations are inserted to enforce this schedule. As a result, the system is completely free from interference. This line of work simplifies the analysis, by completely suppressing the interference in the system, but also introduces some limitations of its own. First, in these approaches, the tasks software has to be written with the phases in mind: this imposes constraints on the way the code is written, and makes it challenging to use legacy code. Automatic transformations of functions into the AER/PREM model have been developed as an attempt to shift the design burden from the programmer to the compiler [START_REF] Forsberg | The predictable execution model in practice: Compiling real applications for COTS hardware[END_REF][START_REF] Fort | Code generation for multi-phase tasks on a multi-core distributed memory platform[END_REF][START_REF] Mancuso | Light-prem: Automated software refactoring for predictable execution on COTS embedded systems[END_REF][START_REF] Matejka | Combining PREM compilation and ILP scheduling for high-performance and predictable mpsoc execution[END_REF][START_REF] Pagetti | Automated generation of time-predictable executables on multicore[END_REF][START_REF] Schuh | A study of predictable execution models implementation for industrial data-flow applications on a multi-core platform with shared banked memory[END_REF]. However, all these methods perform consequent modifications of the applications in order to make them comply with the AER/PREM model, and thus do not solve the limitations regarding legacy code. As a second limitation, the pre-loading of the tasks code and data increases the memory requirements of the system by forcing the load of code and data which may not be used during the execution phase (e.g. due to conditional execution). Finally, the static nature of these solutions is compatible to systems in which certification constraints are very high (e.g. avionics systems), but may be too rigid for less critical applications.

In [START_REF] Schuh | A study of predictable execution models implementation for industrial data-flow applications on a multi-core platform with shared banked memory[END_REF], the authors evaluate the PREM and AER models in different scenarios in which interference is either prohibited or can be tolerated. They conclude that for a given task system, tolerating interference is more effective in terms of WCRT than building a schedule without interference at all. In the same spirit, the Time Interest Points (TIPs) approach [START_REF] Carle | Static extraction of memory access profiles for multi-core interference analysis of real-time tasks[END_REF] has been developed to reconcile the multi-phased task model with legacy code. In this model, a multi-phase representation of the tasks is obtained through static analysis of the binary code of the tasks. As a consequence, no restriction is put on the way the source code must be written. Each phase of a task may perform a certain amount of memory accesses, E C R T S 2 0 2 2

9:4

Correctness and Efficiency Criteria for the Multi-Phase Task Model which is determined by the analysis. Using this representation, an interference analysis can be performed as part of a WCRT analysis such as the one in [START_REF] Davis | An extensible framework for multicore response time analysis[END_REF], or as part of a static scheduling/compiling approach (e.g. [START_REF] Dupont De Dinechin | Scaling up the memory interference analysis for hard real-time many-core systems[END_REF][START_REF] Didier | Correct-by-construction parallelization of hard real-time avionics applications on off-the-shelf predictable hardware[END_REF]). Moreover, the analysis can be tuned in order to produce different representations of the same task (as in [START_REF] Carle | Static extraction of memory access profiles for multi-core interference analysis of real-time tasks[END_REF]). However, to the best of our knowledge, no study has yet been performed in order to define what a "good" multi-phased representation is. In this paper we provide a first answer to this question.

Formal Models

Notation Definition We model a system of real-time tasks τ i (i ≥ 0). Each task is represented in two separate ways, as depicted in Figure 1: a "time-centric" representation called multi-phase. In this abstraction, the task is modelled by a sequence of time slots, called phases, which covers its WCET. We call this sequence of phases a profile. Each phase is associated with an upper bound on the number of memory accesses that the task can perform during the corresponding time slot. This representation is used to statically compute the schedule and perform the interference analysis of the system (in a timing-compositional approach). The mapping between tasks and multi-phase profiles is not bijective: multiple profiles can be found which represent the same task. a "code-centric" representation. In this abstraction, a task is represented by all its possible execution traces (i.e. all the possible sequences of instructions executed from the start of the task to its end). Since this set may be too large to analyze in practice, we consider memory-centric traces: only instructions which may perform memory accesses 1 are represented in the traces, and the rest of the instructions is abstracted by computing local WCETs. This representation is an intermediate step to go from the binary code of a task to its multi-phase representation, and back: it allows the number of memory accesses in each phase to be bounded correctly, and to insert synchronization code at the correct locations in the binary to enforce the scheduling choices. The scope of this paper does not include the methods required to obtain trace-based and phase-based representations of tasks. We focus instead on the relationship between these two abstraction levels. In this section, we describe these models formally and present this relationship.

τ i task i ϕ i k phase k in the representation of τ i ϕ i k .d

Task Models

We denote P i = {ϕ i l |0 ≤ k < Φ i } the ordered set of phases (i.e. the multi-phase profile) representing the execution of task τ i , with Φ i the number of phases. Each ϕ i l is defined by: ϕ i l .d: its start date. ϕ i l .dur: its worst-case duration in isolation (without interference). ϕ i l .m: the worst-case number of memory accesses that may be performed within [ϕ i l .d, ϕ i l .d + ϕ i l .dur[. The date of ϕ i 0 , which is also the start date of task τ i without interference, is set when the static schedule of the system is built. Then, for each ϕ i l (l > 0) the start date is defined by:

ϕ i l .d = ϕ i 0 .d + 0≤q<l ϕ i q .dur (1)
Alternatively, we can define recursively the start date of each phase (except the first one) by:

∀l > 0, ϕ i l .d = ϕ i l-1 .d + ϕ i l-1 .dur
In order to compute the worst-case number of memory accesses performed during a given phase (i.e. ϕ i l .m), the code portions of τ i that may be executed during ϕ i l must be identified and analyzed. To do so, we introduce T i = {t i j |0 ≤ j < T i } the set of execution traces of τ i , where T i is the number of traces. Each trace corresponds to a possible execution of τ i (corresponding to a particular set of inputs) and is a sequence of nodes η i j,k representing instructions with 0 ≤ k < N i j the node's index in its sequence. η i j,0 is the entry point of task τ i and each node is defined by: E C R T S 2 0 2 2

9:6

Correctness and Efficiency Criteria for the Multi-Phase Task Model η i j,k .it : the instruction represented by η i j,k . Here, an instruction is not just understood as an element of the core ISA (e.g. the ADD instruction), but as a particular instruction in the binary code of the task. Thus, nodes from different traces may reference the same instruction in the code. η i j,k .m ∈ N : the worst-case number of memory accesses performed by η i j,k .it. η i j,k .d : the worst-case execution date of η i j,k .it in trace t i j .

Synchronized Nodes

As pointed out in Section 2, working on the complete set of execution traces of all tasks composing the system is not realistic. As a consequence, we formulate our correctness criteria using memory-centric abstract traces: the nodes composing the traces that we consider only represent the instructions that may perform memory accesses. The rest of the instructions is abstracted by computing local WCETs between consecutive memory accesses and accounting for these durations in the worst-case execution date of the nodes (η i j,k .d) 2 . As a result, in this model each node is guaranteed not to execute after its worst-case date, but is a priori able to execute anytime before this date. In order to account safely for the accesses in the phases, we thus would have to account for the accesses performed by a node in all phases that start before the worst-case date of this node. This would lead to huge over-approximations. In order to limit this approximation, some selected nodes must be synchronized: synchronization code is inserted in the program to ensure that the synchronized nodes cannot be executed before their worst-case date. The synchronization code can be added by the programmer directly in the source code of the tasks, by the compiler as part of a low-level compilation pass, or during an automatic code re-engineering process to adapt legacy code to the multi-phase model. We attract the reader's attention to two particular aspects of the model described in Section 3.1: (i) the execution date for nodes that reference the same instruction in different traces and (ii) the modelling of instructions inside loops which may appear multiple times in the same trace at different dates. Both these aspects have to do with the way synchronizations are implemented in the tasks. When complex synchronization mechanisms are used (e.g. that are aware of the current execution trace or of the iteration count in the current loop), the same memory instruction in the code may be modelled as two (or more) nodes with different dates, which perfectly fits the model. If, however, the synchronization mechanism is unaware of the context, the worst-case execution date of nodes that reference the same instruction on separate traces must be the same. Since the model uses worst-case dates, the date chosen for all these nodes must be the maximum date amongst them. Additionally, without a context-aware mechanism, synchronizations inside loops become impossible to implement, so the model naturally fits this case. In this paper, we voluntarily keep the model as general as possible and make no assumption on the implementation of the synchronization mechanisms in order to formulate correctness criteria that apply in all circumstances.

To keep track of the synchronized nodes, we add the boolean attribute η i j,k .sync which is true if the node is synchronized and false otherwise.

Using these synchronizations, the accesses performed by any node must only be accounted for in the phases that: (1) finish after the last synchronization prior to the node AND (2) start before the worst-case date of the node. This is illustrated in Figure 1, which depicts 3 execution traces (t i 0 , t i 1 and t i 2 ) and 2 possible profiles for a task τ i . Synchronized nodes are depicted in black in the traces. The red (resp. green) rectangle shows the time window in which the accesses of node η i 2,3 (resp. η i 1,7 ) must be accounted for. In the first profile, the accesses of η i 1,7 must be considered in phases ϕ i 2 and ϕ i 3 , whereas in the second profile, they would only be considered in ϕ i 3 . It is important to note that since η i j,k .d is a worst-case date, if node η i j,k is synchronized, then its execution date is exactly 3 η i j,k .d. We denote s last (η i j,k ) the last synchronized node before η i j,k in trace t i j . By convention, we set s last (η i j,k ) = η i j,k when η i j,k .sync. To account for the tasks schedule, for all tasks τ i , the entry node (on any trace t i j ) is synchronized and its worst-case execution date is set to the start of the first phase of the profile:

▶ Property 1. ∀i, j : η i j,0 .sync ∧ η i j,0 .d = ϕ i 0 .d
The worst-case date of any other node η i j,k with k > 0 is defined according to the date of the last synchronized node on its trace:

▶ Property 2. η i j,k .d = η i j,s .d + s≤t<k wcet(η i j,t .it, η i j,t+1 .it)
where wcet(η i j,t .it, η i j,t+1 .it) is the WCET between instructions η i j,t .it and η i j,t+1 .it, and η i j,s

is s last (η i j,k ) if ¬η i j,k .sync and s last (η i j,k-1 ) otherwise. A node η i j,k can only be executed in the interval [s last (η i j,k ).d, η i j,k .d].
As we saw in the example of Figure 1, this interval may overlap with several phases of the task profile.

We denote t i j | ϕ i l the set of nodes in trace t i j that may be executed within [ϕ i l .d, ϕ i l .d+ϕ i l .dur[, called the restriction of trace t i j to phase ϕ i l :

t i j | ϕ i l = {η i j,k |(η i j,k .d ≥ ϕ i l .d) ∧ (s last (η i j,k ).d < ϕ i l .d + ϕ i l .dur)}
The notion of restriction of a trace to a phase is illustrated in Figure 2 on 3 traces over phase ϕ i 1 .

t

Figure 2

Restrictions of traces t i 0 , t i 1 and t i 2 to phase ϕ i 1 .

Maximum Number of Accesses in a Phase

The number of accesses that may be performed during a phase for an individual trace is equal to the sum of the accesses of the nodes from this trace that may be executed in the phase. During the execution of a task, only one trace executes (which one depends on the 3 With a precision of a few cycles depending on the implementation of the synchronization mechanism.

E C R T S 2 0 2 2

9:8

Correctness and Efficiency Criteria for the Multi-Phase Task Model execution context): as a consequence, the worst-case number of accesses performed during a phase is equal to the maximum number of accesses that may be performed by any execution trace during that phase.

▶ Property 3. The worst-case number of accesses that may be performed during phase ϕ i l , denoted ϕ i l .m, is equal to the maximum of accesses per trace during phase ϕ i l :

ϕ i l .m = max 0≤j<T i ( η i j,k ∈t i j | ϕ i l η i j,k .m)
▶ Correctness criterion 1. The formula of Property 3 provides a conservative estimation of the number of memory accesses that can occur during the phases of a multi-phase profile.

Since nodes may span over multiple phases, the number of accesses counted task-wise may be overestimated, even when some nodes are synchronized. However, nodes from a trace which span over multiple phases may be "covered" by other nodes from another trace performing more accesses on a given phase. For example, in Figure 2, if we consider that each node performs 1 access, trace t i 2 is the local worst trace on ϕ i 3 with 4 nodes performing accesses and trace t i 1 is the local worst trace on ϕ i 2 with 3 nodes performing accesses. On phase ϕ i 1 , traces t i 0 and t i 1 both have 3 nodes performing accesses. In such circumstances, although node η i 0,4 spans over ϕ i 3 , ϕ i 2 and ϕ i 1 , it does not contribute to any over-approximation. We quantify the task-wise over-approximation of memory accesses compared to the 1-phase model, by computing the difference between the sum of accesses accounted for in each phase, and the worst trace-wise number of accesses.

▶ Property 4. The memory access over-approximation in a multi-phase profile of a task τ i compared to its 1-phase representation is equal to: In this section, we consider a task system for which an analysis has provided a multi-phase model as well as a selection of synchronized nodes for each task. We assume that this task system is scheduled statically (the ϕ i 0 .d for each τ i are selected and the start dates of the other phases are computed using equation 1), and that an interference analysis (such as e.g. [START_REF] Dupont De Dinechin | Scaling up the memory interference analysis for hard real-time many-core systems[END_REF]) is applied to compute and account for the effect of potential interference between the tasks phases, assuming the timing-compositionality of the target processor [START_REF] Hahn | Enabling compositionality for multicore timing analysis[END_REF]. In practice, each phase that potentially suffers from interference is extended using a time penalty, and the next phases are postponed accordingly. This extension may violate assumptions that were made on the correspondence between phases and traces: in particular the restrictions of traces to phases that were computed prior to the interference analysis may no longer be correct, resulting in the possibility that some contentions between cores may happen in phases in which they were not accounted for.

∆ = ( 0≤l<Φ i ϕ i l .m) -max 0≤j<T i ( 0≤k<N i j η i j,k .m)

Example

Figure 3 displays trace t i

2 and the profile from Figure 2, at three stages of the analysis: (a) depicts the trace and phases before the interference analysis. We have:

t i 2 | ϕ i 0 = {η i 2,0 , η i 2,1 } ; t i 2 | ϕ i 1 = {η i 2,2 , η i 2,3 } ; t i 2 | ϕ i 2 = {η i 2,4 , η i 2,5 } ; t i 2 | ϕ i 3 = {η i 2,6 , η i 2,7 , η i 2,8 , η i 2,9 }
Additionally, we consider that for this task, ϕ i 1 .m = 2 and ϕ i 2 .m = 2. (b) shows the same trace and profile after the interference analysis (assuming other tasks in the system): the effect of interference is materialized by timing penalties on the phases (the red rectangles after each phase).

t i 2 | ϕ i 1 , t i 2 | ϕ i 2 and t i 2 | ϕ i 3
are different than in (a):

t i 2 | ϕ i 0 ={η i 2,0 , η i 2,1 }; t i 2 | ϕ i 1 ={η i 2,2 , η i 2,3 , η i 2,4 , η i 2,5 }; t i 2 | ϕ i 2 = {η i 2,5 , η i 2,6 , η i 2,7 , η i 2,8 }; t i 2 | ϕ i 3 = {η i 2,8 , η i 2,9 }
As a consequence, the worst-case amount of accesses that can happen during phases ϕ i 1 and ϕ i 2 is higher than what was assumed and therefore their interference penalty and those of the tasks scheduled in parallel are no longer conservative. (c) represents a solution to respect the model's assumptions of (a): the synchronized date of η i 2,4 (resp. η i 2,6 ) is set to the new starting date of ϕ i 2 (resp. ϕ i 3 ), which is the unique phase in which it was accounted for in (a). With this slight modification, the restrictions of t i 2 to each phase are identical to the ones in (a) and the ϕ i l .m that was computed in isolation for each phase remains correct.

Enforcing the Model's Assumptions and the Analysis Results

Since the duration and start dates of phases can be changed as a result of the interference analysis, new attributes are added to the formal model of the phases: ϕ i l .p ≥ 0 is the timing penalty added to ϕ i l due to potential interference. It is a conservative bound computed during the interference analysis. ϕ i l .d # is the post-analysis date of ϕ i l , i.e. its start date taking into account the potential interference in the system.

After the interference analysis, the start date of some tasks may be postponed due to interference that delays previous tasks. ϕ i 0 .d # is thus fixed by applying the interference analysis results to the initial schedule. The start dates of all other phases ϕ i l describing the execution of τ i are computed as: , the synchronization date is set to at least ϕ i n .d # . This way it is guaranteed that nodes after η i j,k cannot execute and thus produce accesses before the start of ϕ i n .

ϕ i l .d # = ϕ i 0 .d # + 0≤q<l (ϕ i q .dur + ϕ i q .p) (2) E C R T S
It seems straightforward that, by construction, a task set implemented using this rule is guaranteed to fulfill the assumptions made during the interference analysis: during the execution of the system, memory accesses will only occur at times that were accounted for during the analysis, and thus the amount of interference cannot be larger in practice than what was accounted for. However, although this implementation rule directly guarantees that accesses are not performed before the phases in which they are accounted for, it may be harder to convince oneself that they cannot occur later than the end of these phases. Consequently, and given the potentially critical nature of the tasks modelled in the multiphase representation, we provide in the remainder of the section a formal proof of the correctness of this implementation scheme w.r.t. the result of the interference analysis. Once again, this is completely agnostic of the analysis method, as long as it correctly provides a conservative bound on the interference level.

We denote η i j,k .d # the post-analysis worst-case date of node η i j,k . The post-analysis dates of nodes are upper bounds on the worst-case execution dates of nodes in the presence of interference. We start by characterizing those bounds in our formal model (Properties 5, 6 and 7), and then use them to prove the correctness of the implementation of a multi-phase model of tasks.

First, the post-analysis execution date of the entry point of each task τ i is the post analysis start date of its first phase ϕ i 0 .

▶ Property 5. For any task τ i : ∀j

< T i , η i j,0 .d # = ϕ i 0 .d #
Second, correctness criterion 2 has the following consequences for the post-analysis execution date of any synchronized node η i j,k (except the entry point) of any task τ i : if the phase ϕ i n in which the node was supposed to be executed is postponed due to interference penalties on previous phases, the node cannot be executed before the postanalysis start date of ϕ i n . if previous synchronized nodes see their execution dates postponed, the synchronization date of η i j,k must be postponed accordingly, and thus computed from the post-analysis date of the previous synchronized node η i j,s . In this case, we must consider the interference that can take place between η i j,s and η i j,k . If there exists one or more phases that span entirely between the two nodes, their penalties are added to the post-analysis date of η i j,k (which is conservative). Moreover, by convention we count in the post-analysis date of η i j,k the entire amount of penalty of the phase to which it belongs (which is also conservative since it accounts for the interference that can occur on each access in the phase prior to the synchronization node, and on each access that may occur until the next synchronization node).

▶ Property 6. For any synchronized node η i j,k of any trace t i j of task τ i :

(k > 0 ∧ η i j,k .sync ∧ η i j,k ∈ t i j | ϕ i n ∧ η i j,s = s last (η i j,k-1 ) ∧ η i j,s ∈ t i j | ϕ i m ) ⇒ η i j,k .d # = max(ϕ i n .d # , η i j,s .d # + s≤l<k wcet(η i j,l .it, η i j,l+1 .it) + m<b≤n ϕ i b .p)
▶ Correctness criterion 3. The synchronization dates in the final implementation of tasks must not be set to a value higher than the date computed in Property 6.

Finally, for any non-synchronized node, its post-analysis date accounts for the possible postponing of the previous synchronized node η i j,s . Note that the potential interference occurring between them has been accounted for entirely in the post-analysis date of the previous synchronized node. ▶ Property 7. For any non-synchronized node η i j,k of any trace t i j of task τ i :

(¬η i j,k .sync ∧ η i j,s = s last (η i j,k )) ⇒ η i j,k .d # = η i j,s .d # + s≤l<k wcet(η i j,l .it, η i j,l+1 .it)

Proof of Correctness

We now prove that any task system which respects the 3 correctness criteria is correct w.r.t. the results of the interference analysis i.e. cannot generate interference that was not accounted for. First, the difference between the start date of a synchronized node η i j,k before and after the interference analysis is bounded by the difference between the start date of the phase ϕ i l in which it is executed, before and after the interference analysis, added to the maximum amount of interference that can occur in ϕ i l .

▶ Lemma 1. ∀η i j,k :

(η i j,k .sync ∧ η i j,k ∈ t i j | ϕ i l ) ⇒ η i j,k .d # -η i j,k .d ≤ ϕ i l .d # -ϕ i l .d + ϕ i l .p
Proof. We will prove by induction that the property is true for all synchronized nodes. If η i j,k is the entry node of τ i , the proof is direct using Properties 1 and 5. Otherwise, using Property 6, η i j,k .d # is either equal to ϕ i l .d # or must be computed from the previous synchronized node on trace t i j . Let η i j,s = s last (η i j,k-1 ), and assume that the property is true for η i j,s . Then,

If η i j,k .d # = ϕ i l .d # : since η i j,k ∈ t i j | ϕ i l ,
η i j,s .d # -η i j,s .d ≤ ϕ i m .d # -ϕ i m .d + ϕ i m .
p, where ϕ i m is the phase in which η i j,s executes. If m = l (i.e. both nodes execute in the same phase) the property is directly proven for node η i j,k . Otherwise, m < l and then

ϕ i l .d # -ϕ i l .d = ϕ i m .d # -ϕ i m .d + m≤b<l ϕ i b .p (using
Equations 1 and 2), and thus the property is also proven. By induction, we just proved that the property holds for all synchronized nodes. ◀

We are now ready to prove the correctness property:

▶ Theorem 1. For any task system that respects correctness criteria 1, 2 and 3, for any η i j,k of any task τ i , if η i j,k spans over a phase ϕ i l after the interference analysis, then η i j,k was necessarily accounted in the restriction of trace t i j to ϕ i l before the analysis:

∀0 ≤ j < T i , ∀0 ≤ k < N i j , ∀0 ≤ l < Φ i : [s last (η i j,k ).d # , η i j,k .d # ] ∩ [ϕ i l .d # , ϕ i l .d # + ϕ i l .dur + ϕ i l .p[̸ = ∅ ⇒ η i j,k ∈ t i j | ϕ i l E C R T S 2 0 2 2

9:12

Correctness and Efficiency Criteria for the Multi-Phase Task Model Proof. The case where η i j,k is the entry node is direct. For all other nodes we consider separately the case of synchronized nodes and of non-synchronized nodes.

Case 1: η i j,k .sync is true:

By convention, s last (η i j,k ) = η i j,k . Let us assume ϕ i l such that η i j,k .d # ∈ [ϕ i l .d # , ϕ i l .d # + ϕ i l .dur + ϕ i l .p[. Let us denote ϕ i z the phase such that η i j,k ∈ t i j | ϕ i z (z is unique because η i j,k
is synchronized). We want to prove that l = z. Using Property 6, either

η i j,k .d # = ϕ i z .d # or it is greater. If it is equal, then directly ϕ i l = ϕ i z because phases of the same task do not overlap. Otherwise, if z > l then η i j,k .d # > ϕ i z .d # ≥ ϕ i l .d # + ϕ i l .dur + ϕ i l .
p which contradicts the assumption. So z would have to be less than l. Now, since

η i j,k ∈ t i j | ϕ i z , η i j,k .d -ϕ i z .d < ϕ i z .dur. At the same time, η i j,k .d # ≥ ϕ i l .d # ≥ ϕ i z .d # + ϕ i z .dur + ϕ i z .p, so η i j,k .d # -ϕ i z .d # ≥ ϕ i z .dur + ϕ i z .
p. This contradicts Lemma 1, from which we conclude that l = z. This concludes the proof for case 1.

Case 2: η

i j,k .sync is false: Let ϕ i l such that [s last (η i j,k ).d # , η i j,k .d # ] ∩ [ϕ i l .d # , ϕ i l .d # + ϕ i l .dur + ϕ i l .p[̸ = ∅.
Let us denote ϕ i m the phase to which s last (η i j,k ).d # belongs, and assume by absurd that

η i j,k ̸ ∈ t i j | ϕ i l .
Then by definition either (s last

(η i j,k ).d > ϕ i l .d + ϕ i l .dur) or (η i j,k .d < ϕ i l .d). If s last (η i j,k ).d > ϕ i l .d + ϕ i l .
dur: then m > l, and thus using Property 6:

s last (η i j,k ).d # ≥ ϕ i m .d # ≥ ϕ i l .d # + ϕ i l .dur + ϕ i l .p, which contradicts the original assumption. If η i j,k .d < ϕ i l .d, then using Property 2: s last (η i j,k ).d + s≤t<k wcet(η i j,t .it, η i j,t+1 .it) < ϕ i l .d.
Then, we can deduce:

s last (η i j,k ).d # + s≤t<k wcet(η i j,t .it, η i j,t+1 .it) < ϕ i l .d + s last (η i j,k ).d # -s last (η i j,k ).d P rop. 7 ⇒ η i j,k .d # < ϕ i l .d + s last (η i j,k ).d # -s last (η i j,k ).d ⇒ η i j,k .d # < ϕ i l .d + s last (η i j,k ).d # -s last (η i j,k ).d + l-1 b=m+1 ϕ i b .p Lemma 1 ⇒ η i j,k .d # < ϕ i l .d + ϕ i m .d # -ϕ i m .d + ϕ i m .p + l-1 b=m+1 ϕ i b .p ⇒ η i j,k .d # < ϕ i m .d # + ϕ i m .p + l-1 b=m+1 ϕ i b .p + l-1 b=m ϕ i b .dur ⇒ η i j,k .d # < ϕ i l .d #
which contradicts the initial hypothesis. We conclude that necessarily

η i j,k ∈ t i j | ϕ i l . ◀
We just proved that the correctness criteria that we enumerated in the first part of the paper guarantee that the implementation of a task system described in the multi-phase model is correct w.r.t. a chosen interference-aware static schedule. These criteria are very simple, which makes them easy to verify and offers a lot of room for optimizations in the analysis of tasks, both in order to derive a profile for tasks and to select the synchronization nodes. In the remainder of the paper, we concentrate on the efficiency of the model w.r.t. the interference analysis. We start by experimenting the multi-phase model on a case study, and then perform a statistical analysis in order to derive general efficiency criteria which can in the future serve as an objective function for analysis heuristics. Efficiency of the Multi-Phase Model on the ROSACE Case-Study ROSACE [START_REF] Pagetti | The ROSACE case study: From simulink specification to multi/many-core execution[END_REF] is a flight controller case-study composed of 15 communicating tasks running at different frequencies. We followed the Time Interest Points methodology described in [START_REF] Carle | Static extraction of memory access profiles for multi-core interference analysis of real-time tasks[END_REF] to obtain the worst-case execution traces and multi-phase profiles for the ROSACE tasks. Basically, we used the OTAWA static analysis tool to:

Detect the instructions that are not statically guaranteed to result in a cache hit. Build an "abstract" CFG in which the nodes are the instructions that were detected in the previous step. Each edge of this graph is decorated with the WCET of the code portion between its source and sink nodes, computed using OTAWA. Build the execution traces by enumerating this graph. In our experiments on ROS-ACE, the average number of traces by task was around 88, with a peak at 1280 for the aircraf t_dynamics task. The graph enumeration may lead to combinatorial explosion for arbitrarily complex applications. This issue can be mitigated by adding extra synchronizations in the traces (e.g. at the end of a if-then-else or loop construct) that factorize multiple traces for the rest of the enumeration.

For each trace, generate a multi-phase profile in which each memory access has a dedicated phase spanning the duration of the access, using the worst-case dates in the trace. Build the intersection of the profiles of all traces. This intersection is a profile that keeps all access phases from all traces. The rest of the profile is composed of phases guaranteed to feature no access. From this profile, extract the phases with a size larger than a parameter δ in which no access occurs. Parameter δ, which we varied in our experiments, specifies a minimum size threshold for the phases of the generated profiles.

For the remainder of the phases in the intersection profile, fuse them together if their duration is less than δ.

This method creates multi-phase profiles for tasks but says nothing about the selection of the synchronization nodes. We thus added a very simple method to select synchronization nodes, using the correctness criteria of Sections 3 and 4. For each phase ϕ i l , we selected as synchronized node for each trace t i j the first node η i j,k with ϕ i l .d ≤ η i j,k .d < ϕ i l .d + ϕ i l .dur (if such a node exists). None of the tasks needed context-aware synchronizations so the synchronization date was always chosen as the worst-case date of the synchronized instruction in the program. The combination of the heuristic and of our node selection pass does not perform any optimization. In our analysis, we considered a target hardware architecture composed of a multicore processor (2, 4 or 8 cores) in which each core features a L1 LRU data cache, and an instruction scratchpad which holds the totality of the code needed by the core to execute. Additionally, we considered a memory latency of 50 cycles for non-cached accesses. The tasks were compiled for ARM targets, and we considered that the cores were running at a frequency of 10MHz (otherwise the tasks WCETs were too small compared to their periods so there was no interference in the schedule).

Table 1 presents statistics on the multi-phase profiles of the ROSACE tasks for 3 values of δ. This parameter has a consequent impact on the number of phases, on the number of synchronizations and on the over-approximation (defined in Property 4) in the generated profiles. With a δ equal to 50 cycles (the memory latency of our targets), 569 phases are generated for all tasks. Our method determined 315 synchronizations nodes which corresponds to roughly 1 synchronization every 6 or 7 instructions on average. This number may be too high to be realistically used in practice, but is in part due to the small tasks of the case-study which are composed of only a few tens of instructions. As δ grows, the E C R T S 2 0 2 2 9:14 number of generated phases and of synchronization nodes get lower: 115 phases and 116 synchronizations for δ = 500, and 64 phases and 74 synchronizations for δ = 1000, with 4 tasks having only 1 phase in their representation. Our method for selecting the synchronizations and counting the accesses in each phase is basic: it respects correctness criterion 1, but does not optimize the number of synchronizations. As a result, on each trace one node is selected as synchronization for each phase, even when it is not necessary. This explains in part the high count for synchronizations. These synchronizations can be implemented by a variety of methods. One naive method is to poll a register that counts the number of cycles (e.g. a time stamp counter) until the start date of the corresponding phase is reached. This can be implemented with a simple loop composed of only a few instructions (depending on the ISA it can be as small as 3 instructions -compare, conditional jump, jump back). The precision of each synchronization depends on the depth of the pipeline (which imposes the duration of the jumps), but these small overheads can be taken into account in the analysis, and they do not accumulate as the number of phases grows, because the synchronizations are based on dates, not durations. Context-aware synchronizations (e.g. inside loops) are more complex to implement, and may impose restrictions on the analysis. Since there was no need for those in the ROSACE case-study, we leave for future work the efficient and correct implementation of context-aware synchronizations.

Correctness and Efficiency Criteria for the Multi-Phase Task Model

Figure 4 displays the generated traces and two profiles for the az_filter task. When δ = 1000, the profile is composed exclusively of phases in which the number of memory accesses is strictly positive. On the other hand, when δ = 50 most of the profile is composed of phases guaranteed to perform no memory access.

Using the generated profiles, we produced static schedules of the application for target processors featuring 2, 4 and 8 cores. The schedules represent one hyper-period of the tasks. The tasks were mapped to cores following their utilization (using a simple greedy algorithm) and scheduled using the rate monotonic policy with the frequencies specified in the original paper [START_REF] Pagetti | The ROSACE case study: From simulink specification to multi/many-core execution[END_REF]. We then performed an interference analysis: we detected the phases that overlap with each other 2 by 2 on different cores and extended them using a penalty computed as the maximum number of contentions multiplied by the cost of a memory access. Moreover, the total penalty that a phase can suffer from any other core (taken separately) is bounded by the number of accesses of the phase. This is a classical interference computation assuming e.g. a FIFO bus. We measured the total reserved time for the tasks (including the interference penalties) on the hyper-period, using the classical 1-phase model, and using our generated multi-phase profiles. We computed the gain as: gain = (time_1_phase -time_multi_phase)/time_1_phase and reported it in Table 1. The multi-phase model yields a gain of 7.83% (resp. 13.21% and 7.60%) with δ equal to 50 cycles on 2 cores (resp. 4 and 8 cores). The gain gets reduced as δ grows and the generated profiles resemble more and more the 1-phase model. However, even in the case of δ = 1000, the multi-phase model outperforms the 1-phase model by 6.01% (resp. 7.48%, 2.14%) on 2 cores (resp. 4 cores, 8 cores). One noticeable point is that the profiles with a lower δ have a higher over-approximation and still get the best gains compared to the 1-phase model: over-approximation at the profile level is not an indicator of the good performance of the model at the task-system level. Our conclusions from the case-study are the following:

the multi-phase model can yield a substantial gain compared to the 1-phase model. the over-approximation in the profile of an individual task is not correlated to the gain obtained at the task system level. Consequently, the optimal profile for a task may not be derived from its execution behavior (when do the memory accesses happen?), but from extrinsic properties. As we show in Section 6.2, particular shapes of profiles behave significantly better than others during the interference analysis. a trade-off must be found during the construction of the tasks profiles between the number of synchronizations and the efficiency (the gain) of the model. this gain is computed after the schedule is built and the interference analysis is performed and is thus not accessible when the profiles are being constructed: other criteria must be found, which can be computed directly during the construction of the profiles. In an attempt to find such criteria and to confirm these conclusions, we performed a statistical study which we describe in the next section.

Profile Shape-Based Efficiency Criteria

In this section, we investigate how the shape of multi-phase profiles impacts the result of the interference analysis. As we show in this section, we found efficiency criteria which concern the multi-phase model itself and are thus extrinsic to the analysed tasks. To do E C R T S 2 0 2 2

9:16

Correctness and Efficiency Criteria for the Multi-Phase Task Model so, we conducted a statistical study on synthetic profiles generated using multiple input parameters that are summed up in Table 2. Profiles are generated by choosing the values for the attributes of the phases, using random draws from normal distributions centered around the input parameters: for example inside a generated profile, each phase has its own duration and number of accesses, but in average the durations and number of accesses meet the input parameters. We do not consider system-level parameters such as task periodicity, data dependencies or elaborate mapping and scheduling strategies in this section because our focus is on showing how the model reacts in the presence of interference. We thus choose a setting in which a lot of tasks are executed in parallel with no slack time.

Tests Execution and Metrics

The execution of a test consists in three steps. First, we generate the set of multi-phase profiles corresponding to the input parameters. The generated tasks all share the same period, have no explicit data dependency and have a synchronous release. Then, we map the tasks into a number of cores specified for each test and schedule them as soon as possible, with no optimization in the mapping or scheduling choices. This context stresses the multi-phase model. Finally, we perform an interference analysis on the scheduled task system, as we did with the ROSACE case-study. The over-approximation level (cf. Property 4) is an input parameter to the tests. The ROSACE case-study showed that this over-approximation is not directly correlated with the gain yielded by the multi-phase model, so the study of synthetic profiles will provide us valuable insight on the performance of the model. Since we schedule the tasks as soon as possible with no slack, we redefine the notion of gain using the end dates of the schedules obtained with the 1-phase and multi-phase models: gain = (end_1_phase -end_multi_phase)/end_1_phase.

Looking for the Best Multi-Phase Profile Shapes

We started by generating shapes composed of sequences of phases of similar durations (with a standard deviation of 500 cycles), which we call Uniform Profiles (UP). The 3 UP kinds generated are depicted in Figure 5a: long (L) profiles composed only of long phases, short (S) profiles composed only of short phases or mix (M) profiles divided in 2 equal parts with respectively long and short phases. We performed 352,800 tests with different combinations of generation parameters. Each core is only assigned tasks of one UP kind (S, L or M) and has the same number of tasks, which all have the same duration and are released synchronously. With this setup, only the kind of UP assigned may differ for each core, so an easy comparison between the various combinations of UP kinds can be performed. We tested all the combinations of the profiles on 2, 4 and 8 cores. Our results showed that the best profiles hosted the 3 categories S, M and L with a majority of S profiles. This is coherent because the multi-phase model increases its gain whenever, for a given phase, the number of accesses it may perform is higher than the number of possible concurrent accesses from phases running in parallel (and it does not exceed the total accesses of the tasks in parallel). In this experiment each task has strictly the same size, so the probability to fall into this case is higher with S profiles which are composed of more phases.

As the combination of short and long phases, with more short phases than long ones, performed better in our first experiment, we then tested a different profile shape that allows an alternation between short and long phases in the tasks as depicted in the bottom of Figure 5a. We name this profile shape Alternation Profile (AP). We compared the results of AP with the other profile shapes using the same test parameters. The results, given in Figure 5b, indicate that AP systematically outperforms UP regardless of the over-approximation value and of the other parameters. Therefore, we focus on AP as the best multi-phase profile for the rest of the experiments.

▶ Efficiency criterion 1. Multi-phase profiles which alternate between long phases and grapes of small phases tend to perform better than other shapes.

Comparison Between Multi-Phase AP and 1-Phase Model

In this section we assess the performance of the AP shape using a pool of 806,400 tests in which tasks lengths vary in a range of ±25% around a value that is provided as input to the test generator. We first consider task profiles in which all phases perform memory accesses. Figure 6a gives the share of experiments in which the multi-phase AP outperforms its 1-phase counterpart for different values of maximum over-approximation (blue bars). When there is no over-approximation, the multi-phase model almost always performs better. The 1-phase model does not perform as well as the AP until all experiments with over-approximations ranging from 0% to 30% are included. According to Figure 6b (dashed lines), the share of positive results significantly decreases with the number of cores in our tests when the system-wise over-approximation value is superior to 10%, in particular when more than two cores are involved. This is coherent with the fact that the over-approximation of accesses is amplified as the number of cores grows when performing the interference analysis. In our experiments on the ROSACE case-study, the over-approximation always remained under 10% system-wise, regardless of the size of the phases. As a conclusion:

▶ Efficiency criterion 2. The over-approximation plays a lesser role than the shape of the profile at the level of individual tasks, but should still be kept within acceptable levels system-wise, preferably under 10%. This can be achieved by increasing the number of synchronizations. A special effort must be put on the traces with the most accesses as the over-approximation at the phase-level is propagated to the task-level only if it concerns, for each phase, the trace having the most accesses. The over-estimation can also be reduced by fusing phases together when locally some traces perform most of their accesses in different phases. Moreover, when the over-approximation cannot be lowered, scheduling optimizations can be applied in the same spirit as the ones used in AER in order to contain the negative effect of over-approximation.

In the profiles generated for the above experiments, all phases perform accesses. Nonetheless, the presence of phases without accesses in profiles is expected in practice e.g. due to cache effects, and is likely to improve the AP results. Indeed, phases running in parallel with other phases without accesses are guaranteed not to cause contention, while they would in the 1-phase model. Therefore, we performed a new series of tests to estimate the impact of phases without accesses in AP profiles. We modified the profiles already generated for the previous experiments, by randomly selecting one third of each task's phases and setting their accesses count to 0. The results are presented in Figures 6a (orange bars) and 6b (full lines). First, the share of positive results is significantly improved and still at more than 80% when including results with 30% of over-approximation, so the model is less sensitive to over-approximation. This is linked to situations where accesses due to over-approximation are in parallel with no other accesses so they do not lead to additional penalties. Second, the gain distribution with over-approximation ranging from 0 to 10%, given by Figures 7a and7b, is also significantly improved with an average value of 20.1% while it is 5.3% for profiles without empty phases. Consequently: R. Meunier, T. Carle, and T. Monteil

9:19

▶ Efficiency criterion 3. Phases that perform no access have a significant positive effect on the interference analysis results.

As we saw with ROSACE the number of synchronizations, of phases that perform no access and the over-approximation can be adjusted as a trade-off in the analysis.

Conclusion and Future Work

We presented a formal framework for the multi-phase task model including a set of properties that guarantee the correctness of the implemented task system. These properties are agnostic about the methods that generate the profiles and select the location of the synchronizations that enforce them. We combined our criteria to a simple heuristic to obtain multi-phase representations of tasks on the ROSACE case-study, and concluded that the shape of the model impacts the efficiency of the interference analysis, regardless of the analyzed task. We thus conducted a statistical study in order to investigate which kinds of profiles perform the best. We concluded that profiles alternating long and short phases tend to perform better, and that profiles featuring phases that do not perform accesses are particularly efficient. As part of future work, we plan on defining an automatic method for the design of optimized multiphase profiles from the tasks binary code, and on defining scheduling optimizations which benefit from the multi-phase model. Moreover, we will work on the efficient implementation of context-aware synchronizations, focusing on regular synchronization patterns inside loop iterations.

Figure 1

 1 Figure1Three traces and two profiles for task τ i . Red and green rectangles show the potential span of nodes η i 2,3 and η i 1,7 respectively.

Figure 3

 3 Figure3A trace and its corresponding phases representation : (a) in isolation, (b) after the interference analysis, red rectangles are the timing penalty added for each phase, (c) after a correction on nodes dates.

Figure 4

 4 Figure 4 az_filter task: traces (top) and generated profile (bottom).

Figure 5

 5 Figure 5 AP vs UP profiles.

  Tests with positive gain by core number.

Figure 6

 6 Figure 6 Experiments with accesses in each phase (xp2 ) and with phases without accesses (xp3 ).

Figure 7

 7 Figure 7Gain distribution for AP profiles with 0 to 10% of over-approximation.

4 Consequences of the Interference Analysis

	Notation Definition
	ϕ i l .p	timing penalty added to ϕ i l due to potential interference
	ϕ i l .d #	post-analysis start date of ϕ i l
	η i j,k .d

# worst-case date of node η i j,k in the presence of interference

2 0 2 2 9:10 Correctness and Efficiency Criteria for the Multi-Phase Task Model

  The synchronization dates in the final implementation of tasks must at least be equal to the start date of the corresponding phase: for each synchronization node η i j,k ∈ t i j | ϕ i n

▶ Correctness criterion 2.

Table 1

 1 Rosace multi-phase tasks statistics for 3 multi-phase minimum duration (δ).

					δ = 50			δ = 500		δ = 1000
	Task	instr traces ov_app sync phases ov_app sync phases ov_app sync phases
		(#) (#)	(%)	(#) (#)	(%)	(#) (#)	(%)	(#) (#)
	engine	40	1	0	10	18	0	4	4	0	2	2
	elevator	47	1	0	9	15	0	3	4	0	2	2
	aircraft_dyn 1217 1280	21.18	92	167	12.94	37	38	11.76	22	23
	h_filter	77	4	0	18	34	0	7	7	0	5	4
	az_filter	77	4	0	17	32	0	7	7	0	5	4
	q_filter	106	12	14.29	32	55	0	11	9	0	8	5
	vz_filter	106	12	10.34	32	55	0	11	9	0	8	5
	va_filter	77	4	0	17	32	0	7	7	0	5	4
	h_command	18	1	0	7	13	0	2	2	0	1	1
	altitude_hold 65	3	6.25	15	26	0	7	6	0	5	3
	vz_control	70	1	0	23	44	0	7	8	0	4	4
	va_control	73	1	0	24	45	0	7	8	0	4	4
	va_command 18	1	0	7	13	0	2	2	0	1	1
	delta_th	15	1	0	6	10	0	2	2	0	1	1
	delta_e	15	1	0	6	10	0	2	2	0	1	1
	TOTAL	2021 1327	7.88	315	569	3.33	116	115	3.03	74	64
	Gain (2 cores)			7.83%			6.79%			6.01%
	Gain (4 cores)			13.21%			8.45%			7.48%
	Gain (8 cores)			7.60%			3.74%			2.14%

Table 2

 2 Tests input parameters.

	Parameter	Values section 6.2	Values section 6.3
	Over-approximation of accesses (%)	0 to 30 (step 5)	0 to 30 (step 5)
	Nb tasks per core	{1, 2, 3}	{2, 3, 4, 5}
	Interference time penalty (cycles)	{5, 10, 20}	{5, 10}
	Accesses per cycle	0.01 to 0.1 (step 0.01) 0.01 to 0.1 (step 0.01)
	Nb long phases per UP L type task	{5, 10, 15, 20}	{5, 10, 15, 20}
	Avg. number of short phases per long phase	{2, 3, 4, 5}	{2, 3, 4, 5}
	Task duration (cycles)	17,500 to 175,000	17,500 to 175,000

  Ratio of tests with positive gain.

	Full accesses (xp2)		Empty phases (xp3)
	98.9 99.9	96.4 99.7	87.8 98.5	76.5 95.8	92.1	88.0	83.8
					66.1	57.4	50.3
	(a)

In modern processors, the actual accesses may not be performed as soon as the corresponding instruction is executed e.g. if a store buffer delays store operations. However it is possible to statically bound the time window during which the access can be performed. For clarity reasons, we consider in this paper only the date when the instruction initiates the access in the pipeline, but the model can be easily extended to work with an interval of potential access dates.

Our criteria are also valid for simple tasks for which obtaining and manipulating the exact timed execution traces is possible

Funding This work was supported by a grant overseen by the French National Research Agency (ANR) as part of the MeSCAliNe (ANR-21-CE25-0012) project.