Matthieu Quignard
email: matthieu.quignard@univ-lyon2.fr

Michael Baker
email: michael.baker@univ-lyon2.fr

Favouring modellable computer-mediated argumentative dialogue in collaborative problem-solving situations

We describe an experimental Collaborative Problem-Solving (CPS) environment involving Computer-Mediated Communication (CMC), that is designed to favour the production of argumentative interactions and to enable the cognitive changes that they produce to be modelled. Our approach is based on defining a restricted set of psychological and logico-linguistic conditions for generation of argumentation, an original algorithm for optimising constitution of dyads for critical discussion and a computer-based environment that combines graphical and language-based problemsolving with CMC discussion. This approach enables us to study learners' solutions, justification structures and attitudes, before and after CPS activity, and thus to assess the role of argumentative interactions in students' changes in view. Corpus analysis showed that whilst the environment is successful in favouring argumentative interactions, it leads to increased awareness in students concerning the nature of their problem-solving task (in this case, modelling energy in physics) rather than an improvement in solutions or conceptual understanding.

Introduction

A central tenet of recent research on collaborative learning is that certain types of communicative interactions between learners can be associated with specific interactive learning mechanisms (e.g. [START_REF] Dillenbourg | The evolution of research on collaborative learning[END_REF]). In this paper we concentrate on the case of argumentative interactions between learners -interactions that involve the attempt to resolve expressed conflicts of opinions with respect to proposals, by verbal means (expression of justificational structures). A number of mechanisms by which these types of interactions could lead to conceptual change have been described (e.g. [START_REF] Thorley | Conflict within dyadic interactions as a stimulant for conceptual change in physics[END_REF][START_REF] Baker | Argumentation et co-construction de connaissances[END_REF]) but a major problem remains : it appears that very complex and strict conditions are required in order for argumentative interactions to be produced by learners [START_REF] Golder | Le développement des discours argumentatifs[END_REF], especially in CMC situations [START_REF] Baker | Promoting reflective interactions in a computer-supported collaborative learning environment[END_REF].

Our research addresses two related problems : [START_REF] Dillenbourg | The evolution of research on collaborative learning[END_REF] understanding the conditions for production of argumentative interactions in CPS situations involving CMC, and (2) modelling the cognitive changes produced as a result of engaging in argumentative interactions. We propose a restricted set of conditions under which argumentative interactions can be produced, based on psychological and logico-linguistic studies of argumentation, and research on computermediated interactions in cooperative learning situations. These conditions form the basis for design and implementation of a computer-based environment, involving synchronous typewritten CMC. Experimentation of the environment has enabled us to collect a corpus of argumentative interactions that is adapted to the validation of a cognitive model of argumentation in relation to cognitive change [START_REF] Quignard | Modelling Argumentation and Belief Revision in Agent Interactions[END_REF][START_REF] Quignard | Modélisation cognitive de dialogues argumentatifs entre élèves[END_REF]. Our experimental CPS sequence involves encouraging students to express justifications and attitudes, automatically translating graphical problemsolutions into a linguistic form as a preparation for debating, automatic constitution of dyads and generation of individualised texts describing the verbal conflict situation, and individual reconstruction of the agreed solution and justifications after CMC discussion. This approach enables us to study learners solutions, justification structures and attitudes, before and after CPS activity, and thus to assess the role of argumentative interactions in students' changes in view.

We describe design conditions and modelling constraints for argumentative interactions, then the computer-based environment whose design was based upon them, in the context of the experimental CPS sequence. We present and discuss results of a study where the learners' task was to elaborate simple qualitative models of energy ("energy chains", [START_REF] Tiberghien | Modelling as a basis for analysing teaching-learning situations[END_REF]). In conclusion we discuss the extent to which this experimental CMC situation has potential as a learning environment and how this tool could be applied to other types of CPS.

Design conditions and modelling constraints

Previous research on problem-solving dialogues between learners has confirmed what teachers have always known : students are not naturally likely to argue spontaneously with each other, at least with respect to the subjects taught in school. Interpersonal conflicts or individual contradictions are not sufficient to provoke the incidence of argumentation. Nonnon's work [START_REF] Nonnon | Activités argumentatives et élaboration de connaissances nouvelles : le dialogue comme espace d'exploration[END_REF] partially explain this phenomenon : students will not be able to adopt sufficiently firm and opposed argumentative positions with respect to concepts that are not yet sufficiently mastered (since they are being elaborated, and learned). So it appears that, in certain situations, there will be a trade-off between conditions for collaborative learning and for engaging in argumentative interactions.

Necessary conditions. Our study of situations that can promote spontaneous1 argumentative interactions between learners is structured by psychological conditions (C1-C4) concerning obstacles to the production of argumentative texts [START_REF] Golder | Le développement des discours argumentatifs[END_REF] and by pragma-dialectical conditions (C5-C8), derived from theoretical studies of argumentation [START_REF] Van Eemeren | Communication, Argumentation, Fallacies[END_REF] : C1. The concepts underlying the problem-solving task to be solved can be understood by participants. C2. The "debatability" of the task : participants can understand different positions with respect to the problem ; they are able to 'step-back' in order to apprehend differences of attitudes and contradictions. C3. The communication situation (CMC interface) does is not an unsurmountable obstacle to the expression of opinions. For example, a type-written interface may be an obstacle for communicating graphical solutions. C4. The conceptual distance between the two conflictual theses is sufficiently wide and evident. If it is not the case, there are many non-argumentative way to 'dissolve' the conflict [START_REF] Baker | Argumentation et co-construction de connaissances[END_REF] (e.g. by finding a compromise or even a immediate retraction of one thesis). C5. A minimal common ground is shared, with respect to the topic to be discussed. This is a minimal condition for understanding each other. C6. A conflict of opinions has been openly declared, and understood : participants know their initial positions in the conflict. C7. Participants have enough arguments at their disposal, and commit themselves to the debate (they have something to argue about). C8. Individuals' "argumentativeness" : participants want to resolve the conflict of opinions, whilst defending their own positions (they want to argue).

Modelling constraints. In order to experiment the potential of such a learning situation, attitudes and explanations have to be collected just before and just after discussion. In that case, it is possible to obtain a good representation of the participants' knowledge, of the attitudes they may have during the interaction and of the arguments they may use. This information

The correct energy chain for the 'battery-bulb' problem must be collected at the boundaries of the interaction (before it starts and after it finishes), yet this external intervention must alter neither the content nor the progression of the discussion. The emergence of a critical discussion is predicted as soon as the appropriate dialogical attitudes ("pro", "contra") have been expressed and the communication between participants' screens is established. This implies that dyads have already been constituted, i.e. which students will discuss together in pairs. Since the combinatory space that has to be investigated is very large (105 combinations for 8 students), dyad constitution that is based on analysis and comparison of individuals' problem solutions needs to be achieved by a computer.

Description of the experimental collaborative-problem solving situation

The choice of the problem-solving task involves a crucial compromise : the main topic must be both debatable (condition C2) and modellable, i.e. it allows automated analysis and dyad constitution. The task chosen was qualitative modelling of energy, using energy chains, by highschool students (16-17 years old). Energy chains are composed by the following elements : reservoirs (that store energy), transformers (that transform energy) and transfers of energy (work, heat and light). This task also contains a fundamental syntactic rule : "chains must start and finish by a reservoir ; these reservoirs must be different". The experimental situation students have to model is the case of a bulb connected to a battery by the mean of two conducting wires. The correct corresponding chain is given figure 1.

The choice of this task is grounded by the following facts. Firstly, students' problem solving strategies are now well known for this task [START_REF] Megalagaki | Learning modelling through the successive resolution of problems[END_REF][START_REF] Collet | Apports linguistiques à l'analyse des mécanismes cognitifs de modélisation en sciences physiques[END_REF][START_REF] Devi | Modelling students' construction of energy models in physics[END_REF]. Secondly, the task implies a wide knowledge space for debate, since students have to their disposal several systems of explanation for this phenomenon, and therefore several conflicting positions may be held and discussed (the electrokinetic model proposes a very different solution to this exercise). Finally, this graphical task is well structured by syntactic rules applying to a small number of types of elements, which allows automated analysis of students' solutions.

The experiment was carried out with 8 secondary school students of a same class, 3 boys and 5 girls. The successive phases of the experimental sequence are as follows (see table 1) : Phase 1 : Individual problem solving and attitudes. On the first screen (see figure 2), each individual student must draw the energy chain that models the experimental situation (it consists of a battery, a bulb, connected by two electric wires from the labwork material). On this screen, two spaces are available : one graphical window where energy chain elements can be placed (these boxes and arrows can be manipulated from the menu bar) and one text window, updated by the system, that describes chains in a few sentences, as fast as they are elaborated. Students also have a quick access on the screen (as well as on a separate sheet of paper) to a description of the model (syntax and semantics of the chain components). Our fundamental hypothesis here is that argumentation is a language-based activity : our aim is thus to facilitate the transition between "semiotic registers" [START_REF] Duval | Sémiosis et pensée humaine. Registres sémiotiques et apprentissages intellectuels[END_REF], from a graphically-based problem-solving activity, to language-based reflection and discussion. In addition, automated description of diagrams in a linguistic form provides a common way of describing the solutions, that may improve determination of the common ground prior to discussion. On the second screen (see figure 4), students are proposed sentences (up to ten) by which the system describes their own solution. Each sentence is displayed in a separate text window, in a column, on the left hand side. On the right of each sentence, students successively find a local menu, from which one of five attitudes can be selected (see figure 3), then a text window, where subjects are invited to type explanations or justifications with respect to their attitudes. A third screen (not shown here), in principle identical to the previous one, displays a more complex description of the solution. It does not describe components separately, but rather "chunks" of the energy chain diagram (two connected boxes and their interconnections), in order to collect more global attitudes and other types of explanations. Our hypothesis here is that modelling involves global as well as element-to-element matching [START_REF] Devi | Modelling students' construction of energy models in physics[END_REF], so justifications for chunks may not be equivalent to the sum of justifications of their components. of Hoppe and colleagues (e.g. [START_REF] Hoppe | The Use of Multiple student Modeling to Parameterize Group Learning[END_REF]) in that we also aim to constitute productive collaborative dyads in a CMC situation. However, our work differs from the latter in that our primary aim is to effect cognitive changes via stimulating a specific type of communicative interaction. An automated algorithm has been implemented for dyad constitution, so that discussions may start as soon as possible after attitudes have been expressed. The choice of the partners is achieved on-line, on the basis of the individual solutions, in order to put together subjects who manifested conflictual solutions, in a way that may give rise to potentially rich argumentation. Solutions are analysed, formalised and finally compared on the basis of the three following criteria in order to predict which pairs of students' solutions would lead their authors to commit themselves to argumentation.

conceptual obstacle : students should be put together who did not solve the problem the same way. There are generally several ways (correct or not) to give a solution to a problem. Research on modelling tasks [START_REF] Tiberghien | Modelling as a basis for analysing teaching-learning situations[END_REF] show that students are strongly resistant to changing their views of the problem. Therefore, from this conceptual obstacle one can expect strong positions and entrenched commitments. In the specific case of energy modelling, there are three different ways of describing the problem (modelling levels, see [START_REF] Tiberghien | Modelling as a basis for analysing teaching-learning situations[END_REF]) : a raw description of the objects involved in the situation (objects level, e.g. arrows represent wires), an electrokinetic model (arrows represent current) and energy modelling (arrows represent energy transfers). Modelling levels are estimated on the basis of the labels given to components of the chain, and the number and direction of arrows. These are weighted by the degree of commitment to the corresponding sentences (expressed in phase 1.2). normative obstacle : a chain that does not conform to rules of the model (uncircularity and completeness) is expected to give rise to wellgrounded attacks from the opponent (there is a space of possible counterarguments). solution correctness : on the basis of the principle that a good solution is more convincing than a worse one, one must avoid putting together very inequal solutions, otherwise the worse solution could not compete against the better one. On the other hand, one should also avoid putting together two solutions that obtained a similar mark : they could be so close that there would not be any conflict left, which may lead to a negotiated compromise, rather than to potentially valuable argumentation. This score is calculated by the evaluation of differences between the current solution and the correct one (given figure 1). The argumentative potential of each dyad is evaluated on the basis of the previous criteria, and an "argumentative score" is given. An optimisation algorithm investigates all possible ways of choosing n pairs in a group of 2n subjects ( 2n 2 n n combinations), and retains the best configurations : no pair must be too weak, most of them must be maximal.

Once the choice of dyads is made, one must give specific instructions to each dyad that will lead to an argumentative interaction. In accordance with the rules of pragma-dialectics and our modelling constraints, instructions consist of a natural language description of the conflict situation and the following final phrase : "Discuss together, each of you defending his/her own point of view, in order to find a common solution to the exercise" (see figure 5). Whilst this does not, of course, mean that students' will actually attain agreement, imposing this common goal motivates at least the necessity to engage in dialogue rather than to 'agree to differ'. By the presentation of this text, essential elements of the common ground relating to the conflict situation are established, and positions are declared. Participants can not visualise their opponent's diagram : they only have a partial description of it, in natural language. The students also have at their disposal their own solution diagram, on a separate sheet of paper.

Phase 3 : CMC discussion of the solutions. Once dyads have been constituted, the students sit in front of a computer, so that partners in a given dyad are back to back. Partners share the same computer screen across the network. The connection enables each student to observe all actions of the other on the shared screen, including text as it is being typed. The screen used for computer-mediated argumentation is divided in two parts (see figure 5). The upper part of the screen displays the description of the conflict situation, and the instruction phrase, described above. The lower part of the screen is dedicated to communication. Two personal spaces are displayed on both sides of a central dialogue history. Subjects communicate by the use of buttons in their personal space. Some buttons send short messages to the dialogue history : 'Yes', 'No', 'I agree'... Other buttons like the balloon, 'Because...' open a pop-up text window where free text can be typed. The students send their messages by hitting the TAB key. In this case, their message is added to the bottom of the dialogue history. The CMC part of this interface was based on previous research carried out within GRIC-COAST [START_REF] Baker | Promoting reflective interactions in a computer-supported collaborative learning environment[END_REF].

Phase 4 : Individual reconstruction of the agreed solution and attitudes. Once students decide that the debate is closed, they call the experimenter to disconnect the screen sharing. Subjects come back to the initial graphical and textual environment for energy chain construction (see figures 2 and 4). They are expected to rebuild the energy chain on which they agree at the end of their discussion. As in the first phase, their chain is analysed and descriptive propositions are proposed by the system, on which subjects must express their own attitudes and give explanations. The design rationale of this phase was to access the degree of agreement reached in the discussion, by comparing it with the chains drawn subsequently by individual students of the same dyad. This also enables access to the explanations given for new components of the chain, and the reasons why proposals were accepted or not.

Results

General results. Although students communicate using a typewritten interface, predominantly dialogal and argumentative interactions were produced. Interventions were relatively short, synchronously written and read, with free turn-taking. The average amount of time spent on argumentation attains 84mutual understanding and students entered freely into argumentation as soon as the discussion started. This shows that CMC did not prevent communication of graphical solutions (C3) and that the common ground (including the specific conflict description) was adequately established (C5-6-8). Argumentation evaluation. The two most conflictual argumentation dialogues were obtained with dyads having the greatest conceptual and normative difference. The poorest argumentation dialogue was obtained with the dyad for which intial solutions were very similar. In that case, students had some trouble in perceiving the conflict and reviewed all elements to check their agreement. This corroborates the distance condition (C4) and the criteria used in our dyad constitution algorithm for obtaining conflicts that may be solved by argumentation.

Attitudes and arguments. One can observe a good continuity of attitudes and arguments accross the activities (before, during and after discussion) : students did not adopt different attitudes with respect to a given proposition when they are in a discussion or alone in front of the screens 2a and 2b (figure 4). This indicates a perhaps surprisingly strong link between individual (private) and dialogical (public) forms of reasoning. Similarly, justifications given in phases 1.2 and 4.2 are use as arguments during the discussion. This shows that screens 2a and 2b are well designed for collecting the relevant information about students' knowledge and for argumentation modelling. The comparison of the two individual visions of the agreed solutions (phase 4) shows that students genuinely reached agreement on a common solution. The only differences that remained were relative to elements that were not debated.

Evolution of the solutions. Discussions did not necessarily lead to finding better or even newer solutions. Only one dyad agreed on a radically new solution, the three others agreed on slight modifications of one of the initial solutions. This can be explained by the systematic use of normative arguments (one refers to a rule of the model to attack and reject a solution), rather than more constructive arguments that could lead to completion of an unsatisfactory solution. However, producing better energy chain solutions is not the most important point here : this task is only a means to an end, that of enabling students to gain a better understanding of both the concept of energy and the nature of modelling in science. From analysis of the corpus, there was evidence that students had gained a more refined understanding of the nature of the modelling task in which they we engaged, rather than of the concepts underlying it.

Learning. The potential of this experimental situation as a learning environment is based on the cognitive activities carried out by learners at different stages of the experiment. In phase 1, students have to solve the problem with two very different types of knowledge representation : graphical diagrams and natural language [START_REF] Cox | Supporting the Use of External Representations in Problem-Solving : The Need for Flexible Learning Environments[END_REF][START_REF] Stenning | A Cognitive Theory of Graphical and Linguistic Reasoning : Logic and Implementation[END_REF]. Since they are expected to shift from one to another, they may reach a very stable solution, taking benefit of the reasoning induced by the representations : graphics facilitate elaboration of solution and the application of rules ; natural language, that has a more restricted focus, stimulates reflection and critical analysis, emphased by the activities of attitude expression and explanations.

During the discussion (phase 3) students are confronted with an alternative point of view : they have to represent the other's solution to themselves, in order to evaluate its validity. Students manage quite well with this task, specifically with formal arguments (the most efficient but also the easiest to find). Confrontation with a different solution does not necessarily lead them to produce solution that are based on deeper conceptual understanding.

If learning may not necessarily be achieved during discussion, on the basis of observing the group discussion and correction session with the teacher subsequent to our experimental sequence, we would make the following conjecture, to be explored in further research : argumentative discussion in the situation described here can create a state of receptive critical awareness of the problem-solving domain in students. Such a state of awareness may be important in learning, or in learning to learn, on a much longer-term basis.

Conclusions and perspectives

This paper presented an experimental CMC situation that was designed for favouring production of argumentative interactions between learners and for for modelling relations between those interactions and specific types of cognitive changes. We described an experimental study that has produced satisfactory qualitative results on a restricted group of learners : predominantly argumentative interactions were spontaneously produced in a way that led to better understanding of the nature of the modelling task, rather than better solutions and/or conceptual understanding. An experiment with a larger group of learners is planned for completing the validation of this protocol, including the dyad constitution algorithm, and for supporting our main research project : cognitive modelling of argumentation dialogue.

Success in the spontaneous production of argumentation dialogue depends essentially on the degree of commitment of students to their solutions, and on the conceptual distance between their points of view. In the corpus collected during the experiment presented in this paper, students' solutions were too similar and very much constrained by the electrical model. Further experiments will aim to constitute more argumentative dyads by giving students more information on the energy chain model, so that they can understand more precisely what type of modelling activity is expected from them.

Extending this experimental technique to other types of collaborative problem-solving tasks could also be a way of extending its field of validity. Such an extension could begin with other types of problem-solving tasks involving modelling activities or graphical representations, which would enable automated analysis to be carried out. The dyad constitution algorithm would then need a general problem solver, that could determine discriminate the values for the three criteria : conceptual opposition (i.e. the various ways of resolving the problem) ; normative opposition (i.e. evaluating which rules were applied and which were not) and a procedure for evaluating the degree of correctness of the solution. Nevertheless, it is clear that spontaneous production of argumentation dialogue does not only depend of the efficiency of the previous algorithm, but essentially on the nature of the topic that is to be debated : there must be something to be debated.

Figure 2 :

 2 Figure 2 : Computer environment for graphical construction of energy chains (left) with an automated description of its components (right).

Phase 2 :

 2 Dyad constitution. Our aims are similar to those (1) I'm sure it's the case. (2) Yes, maybe (3) I don't know. (4) Maybe not/yes. (5) I'm sure, it's not the case.

Figure 3 :

 3 Figure 3 : Five attitudes by which students express their commitment to elements of their solution.

Figure 4 :

 4 Figure 4 : Attribution of attitudes and explanations. For each sentence formulated by the system (left column) on the basis of the graphical solution, subjects are expected to express their attitude in the local menu (in the centre column) and to explain their choice in the reserved place, on the right.

Figure 5 :

 5 Figure 5 : CMC environment shared by the subjects of the same dyad. The upper part displays the conflict situation, whereas the lower part is dedicated to communication. On both side of the dialogue history (in the centre) subjects are provided a personal panel for the formulation of communicative acts. A free text typing window can be called by clicking on the balloon. The other buttons send key messages directly to the dialogue history.

Table 1 :

 1 General progression of the experiment.

		Phases	Achieved by Screens
	1.1 Individual problem-solving	Student	1
	1.2 Expression of attitudes and explanations	Student	2a, 2b
	2.1 Automated solution and attitudes analysis	System
	2.2 Dyad constitution	System
	2.3 Generation of conflict situation text, specific to each dyad	System
	3	Typed dialogue (CMC)	Dyad	3
	4.1 Individual reconstruction of the agreed solution	Student	1
	4.2 Expression of personal attitudes and explanations	Student	2a, 2b

By the term spontaneous, used in this context, we do not mean that the argumentation situation is completely 'free' or 'natural' since, precisely, we aim to constrain the situation so as to favour argumentation. Rather, we mean that the students attitudes towards conflicting proposals are genuinely their own, in contrast with cases where individuals or groups are asked (by the experimenter) to play the role of being in (dis)favour of a given view, and that no prior constraints are imposed on the nature of the students' dialogue.

Acknowledgements

We gratefully acknowledge financial support for this research from the French Ministry of Research (M. Quignard's PhD in Cognitive Science grant, under co-direction of J. Caelen and M. Baker), the CNRS and Université Lyon 2. Thanks to the students and their physics teacher for participating in the experiment, to colleagues in GRIC-COAST for their assistance, and to Andrée Tiberghien for her guidance.


Hamza Rihani

Matthieu Moy

Claire Maiza

Robert I Davis

Sebastian Altmeyer

Response Time Analysis of Synchronous Data Flow Programs on a Many-Core Processor

In this paper we introduce a response time analysis technique for Synchronous Data Flow programs mapped to multiple parallel dependent tasks running on a compute cluster of the Kalray MPPA-256 many-core processor. The analysis we derive computes a set of response times and release dates that respect the constraints in the task dependency graph. We extend the Multicore Response Time Analysis (MRTA) framework by deriving a mathematical model of the multilevel bus arbitration policy used by the MPPA. Further, we refine the analysis to account for the release dates and response times of co-runners, and the use of memory banks. Further improvements to the precision of the analysis were achieved by splitting each task into two sequential phases, with the majority of the memory accesses in the first phase, and a small number of writes in the second phase. Our experimental evaluation focused on an avionics case study. Using measurements from the Kalray MPPA-256 as a basis, we show that the new analysis leads to response times that are a factor of 4.15 smaller for this application, than the default approach of assuming worst-case interference on each memory access.

INTRODUCTION

The design, development, and verification of safety-critical real-time embedded systems are subject to specific requirements that follow from guidelines and standards such as DO-178B/C for avionics and ISO26262 for automotive systems. Both the functional and the timing behaviour of such systems is required to be correct. In order to ensure that applications meet their deadlines, predictable upper bounds are required on the execution times of software components. These enable the derivation of sound upper bounds on the worst-case response times (WCRT), from input stimulus to output response, and thus RTNS 2016 verification of compliance with timing constraints.

With the relatively simple hardware (single processor, no cache, no advanced hardware acceleration features, etc.) used in legacy systems, it was possible to ensure predictability of execution times, to tightly bound worst-case execution times (WCET) either via static analysis or via measurements of all relevant paths, and to compose tight upper bounds on overall response times. Due to an increasing demand for compute performance, combined with Size, Weight, and Power consumption (SWaP) requirements, the emphasis has shifted from ever faster single-core processors, which had reached physical limitations due to issues with heat dissipation, to more complex multi-core and many-core architectures. Ensuring predictable and tightly bounded timing behaviour in such systems is very challenging. This is due to the contention for multiple shared hardware resources between co-running applications on the different processors. Examples include contention for cache, network or memory bus, and other interference effects such as DRAM refreshes. For example, on the Freescale P4080, the latency of a read operation varies from 40 to 600 cycles depending on the total number of cores running competing tasks [START_REF] Nowotsch | Multi-core interference-sensitive WCET analysis leveraging runtime resource capacity enforcement[END_REF]. Similarly, a 14 times slowdown has been reported [START_REF] Radojković | On the evaluation of the impact of shared resources in multithreaded COTS processors in time-critical environments[END_REF] due to interference on the L2-cache for tasks running on Intel Core 2 Quad processors. Recent work [START_REF] Valsan | Taming non-blocking caches to improve isolation in multicore real-time systems[END_REF] shows that even with cache partitioning, contention for registers accessed on both cache hits and misses can cause a 21 times slow down due to contention caused by co-runners on the ARM cortex A-15 multi-core architecture.

A few modern architectures are however designed with the requirements of real-time embedded systems, in particular predictability, in mind. In this paper, we study the Kalray MPPA-256 [START_REF] De Dinechin | Time-critical computing on a single-chip massively parallel processor[END_REF] many-core processor (more precisely the second generation, called Bostan). This processor has 256 cores arranged in 16 clusters. The clusters are linked by a 2-D torus dual Network-On-Chip (NoC). Independent applications may run on different clusters. Although inter-cluster interference may be largely eliminated there is still the potential for interference among the tasks running on the same cluster due to accesses to shared resources such as the shared memory [START_REF] Nélis | The variability of application execution times on a multi-core platform[END_REF]. Hardware partitioning and replication (e.g. memory banks) are used to significantly reduce this interference, but do not remove it completely. Details of the architecture are discussed in Section 2.1.

Synchronous Data Flow (SDF) languages such as Lustre [START_REF] Halbwachs | The synchronous data flow programming language lustre[END_REF] and SCADE [START_REF] Berry | Next Generation Design and Verification Methodologies for Distributed Embedded Control Systems[END_REF] have been industrialised and are widely used for embedded systems. A certified SDF compiler can produce sequential code which facilitates deterministic behaviour. The challenge is to parallelise this sequential code without loss of determinism. An SDF application can be represented by a set of tasks with dependence relations between them. The tasks produce and consume a statically defined number of tokens. This model is deterministic in terms of communications, i.e., we know the topology and the amount of data sent and received. The parallelism in this case is trivial: tasks can be mapped to available processing elements (cores), respecting the dependence relations, and allowing independent tasks to run in parallel.

Existing work by Puffitsch et al. [START_REF] Puffitsch | Mapping a multi-rate synchronous language to a many-core processor[END_REF] and Walter and Nebel [START_REF] Walter | Energy-aware mapping and scheduling of large-scale macro data-flow applications[END_REF] tackles the challenge of porting and mapping Synchronous Data Flow programs to multi-core architectures by proposing different scheduling techniques. These approaches assume that an upper bound WCET is known for each task, and schedule the tasks accordingly. The scheduling techniques used optimise parameters such as the global execution time, CPU utilisation or energy efficiency. Using WCETs that are independent of co-runner interference can be very pessimistic (as shown in [START_REF] Nélis | The variability of application execution times on a multi-core platform[END_REF]) which may affect the efficiency of the approach. However, we note that accounting for the actual interference from co-runners also depends on the scheduling technique used.

Contributions: Our approach differs from previous work, in that we consider the influence of scheduling on timing analysis. As a consequence, the scheduling step considers a WCET bound for each task that also accounts for the interference from co-runners.

Our main contribution is an algorithm to compute a static, time-driven, periodic schedule (further detailed in Section 2.3), as commonly used in hard real time systems for maximum predictability. We assume that the mapping of tasks to cores and the execution order is given (either manually or provided by a separate tool), and compute a set of release dates (offsets) and response times for each task. This is an iterative process, with release dates dependent on the response times of preceding tasks, and response times dependent on the set of co-runners, which are in turn dependent on task release dates. The process either converges on a valid, all dependence relations respected, and schedulable configuration or deems the system unschedulable with that task mapping, in which case a different mapping could be tried. The proof of convergence is included in the long version of this paper published as a technical report [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor-full version[END_REF]. It is non-trivial since the usual monotonicity argument does not apply; the sequence of release dates computed at each iteration may not be monotonic.

We target applications running on the Kalray MPPA-256 many-core processor.

We identify all the sources of interference for an application running on a compute cluster, and provide a mathematical model for them. The model builds upon the Multi-core Response Time Analysis (MRTA) framework [START_REF] Altmeyer | A generic and compositional framework for multicore response time analysis[END_REF]; a generic approach to response time analysis for multi-and many-core systems. Unlike MRTA, we consider a static, time-driven schedule, and hence cannot use the same fixed-point algorithm. Instead, we provide a novel algorithm that uses not only the mapping but also the information about when each task is executed to model interference precisely. Finally, we evaluate our approach with a micro-benchmark and apply it to a case study obtained from a realistic avionics application.

Related Work: In 2014, Lampka et al. [START_REF] Lampka | A formal approach to the WCRT analysis of multicore systems with memory contention under phase-structured task sets[END_REF] proposed an approach based on timed automata and abstract interpretation.

The main idea is to analyse a phase-structured task model [START_REF] Pellizzoni | Worst case delay analysis for memory interference in multicore systems[END_REF][START_REF] Schranzhofer | Timing analysis for TDMA arbitration in resource sharing systems[END_REF] using Real-Time Calculus to derive the arrival curves for access requests and the availability curves for the shared resources (in this case the shared bus). The authors proposed timed automata models of several bus arbiters (FCFS, Round-Robin, TDMA). Although modelling a more complex arbiter can be feasible in timed automata, it increases the complexity of the model and may lead to an explosion of states during analysis. Architectures such as the Kalray MPPA-256 have several shared resources. This adds to the complexity of the analysis and may significantly affect its scalability.

In 2015, Dasari et al. [START_REF] Dasari | A framework for memory contention analysis in multi-core platforms[END_REF] presented an approach for response time analysis taking into account interference on the bus. The number of accesses were obtained from measurements during the task's execution (Regions of task execution were used for a more fine-grained analysis). The bus itself was modelled by considering the earliest and latest available communication slots for the task under analysis. This representation depends on the arbitration policy of the bus. The authors give mathematical models of the most widely used bus arbiters; however, it is difficult to see how to represent with this approach a less conventional arbitration policy such as that employed in the Kalray MPPA-256.

In 2015, Carle et al. [START_REF] Carle | From dataflow specification to multiprocessor partitioned time-triggered real-time implementation[END_REF] described the implementation of data flow applications on multi-core systems. The authors focus on the optimisation of an off-line schedule taking into account non-functional properties such as release dates and deadlines. This work aims to eliminate the interference on shared resources by providing temporal isolation. Our proposed approach accounts for the interference and hence may be complementary to this previous work.

In 2016, Giannopoulou et al. [START_REF] Giannopoulou | Mixed-criticality scheduling on cluster-based manycores with shared communication and storage resources[END_REF] proposed a response time analysis on the Kalray MPPA 256 considering mixedcriticality scheduling. The main difference with our approach is that [START_REF] Giannopoulou | Mixed-criticality scheduling on cluster-based manycores with shared communication and storage resources[END_REF] considers a "Flexible time-triggered scheduling" model which divides time into frames, and forces a global synchronization barrier between frames. This potentially creates core under-utilization while they wait for the barrier. Our scheduling policy does not require any global barrier. Also, we model the multi-level round-robin arbiter while [START_REF] Giannopoulou | Mixed-criticality scheduling on cluster-based manycores with shared communication and storage resources[END_REF] considers only one level.

Organization: The remainder of the paper is organised as follows. Section 2 describes the system and application models used, and outlines the MRTA framework which we build upon. Section 3 provides response time analysis for synchronous data flow programs running on a compute cluster of the Kalray MPPA-256. This analysis is evaluated in section 4 via a set of micro-benchmarks and a case study application. Section 5 concludes with a summary and discussion of future work.

SYSTEM AND APPLICATION MODEL

This section presents the system and application models considered, thus defining the context for our work. We describe the hardware architecture and its relevant

P

Kalray MPPA-256 Architecture

The Kalray MPPA-256 is a many-core processor [START_REF] De Dinechin | Time-critical computing on a single-chip massively parallel processor[END_REF]. It is composed of 16 tiles (called compute clusters) of 16 + 1 cores.

The processor is connected to the external environment through 2 I/O quad-core clusters. Inter-cluster communication is achieved via a 2D-torus dual Network-On-Chip (NoC) for data and control. In this paper, we are interested in applications running on a compute cluster and the interference due to intra-cluster communications.

Compute Cluster: Figure 1 illustrates the architecture of a single compute cluster. It has 16 cores plus 1 Resource Manager (RM). The compute cluster connects to the NoC via two DMA (Direct Memory Access) interfaces; one for receiving (Rx) and one for transmitting (Tx). The cluster also has a Debug Support Unit (DSU).

The cores have an in-order Very Long Instruction Word (VLIW) pipeline and separate 8 KByte 2-way set-associative private caches with 64 Byte lines for instructions and data. The data cache has a write buffer with 8 fully associative 64bit entries. There is no cache coherency mechanism between the cores. Each core has its own real-time clock. Clocks in the same cluster are synchronous.

Shared Memory: In order to provide spatial isolation, the memory is partitioned into 16 banks. Each memory bank is accessed via a separate bus arbiter which significantly reduces the amount of interference compared to the alternative of a single arbiter. There are two possible configurations for the memory banks: interleaved mode where sequential memory addresses move from one bank to another, and blocked mode where each block of 128 KB consecutive memory addresses are contained in a memory bank. In this paper, we assume that blocked mode is selected, since it gives more control over the bus interference. This is because with blocked mode, cores that access different memory banks go through different arbiters hence they do not interfere with each other. We use a fixed association between cores and memory banks. More precisely, in our application model, each task has a local memory buffer, and the buffers of all tasks running on the same core are mapped to the same memory bank. As a result, read accesses are private but write requests may access another core's memory bank. Bus Arbitration: Figure 2 illustrates the specific multilevel policy used to arbitrate accesses to the shared memory. We distinguish three groups which are arbitrated over three levels:

• G1 = {i ∈ [0, 15] : Pi}: access requests from the 16 cores are initially subject to round-robin arbitration. • G2 = {Tx , DSU , RM }: access requests from the Resource Manager (RM), Debug Support Unit (DSU) and Tx requests to the NoC are initially subject to round-robin arbitration. • G3 = {Rx }: Rx requests from the NoC. At level L1, requests issued by data and instruction caches local to a core are processed by a local round-robin arbiter. At level L2, there is round-robin arbitration within each of the groups G1 and G2. This is followed by round-robin arbitration between these two groups at level L3. Finally, G3 is included in the last level of the arbitration (L4), which uses a non-preemptive fixed priority (FP) arbiter and gives the highest priority to access requests coming from G3.

To summarise, an access request from a task running on a core crosses three levels of round-robin arbitration and a level of fixed priority arbitration to reach the shared memory.

Multicore Response Time Analysis

In this subsection, we outline the generic framework for Multi-core Response Time Analysis (MRTA) introduced by Altmeyer et al. [START_REF] Altmeyer | A generic and compositional framework for multicore response time analysis[END_REF], which we subsequently build upon.

Given a set of n sporadic tasks Γ = {τ1, . . . , τn}, where each task τi has a period or a minimum inter-arrival time Ti and a deadline Di and is statically assigned to a core, the MRTA framework computes the response time of each task taking into account the total interference at the different levels of the hardware that could occur during the task's response time. By convention, we use Px to mean the core that the task under analysis is mapped to, and Py to indicate some other core. The subset of tasks mapped to a core Py is denoted by Γy.

In the MRTA framework, tasks are represented by a set of traces, each of which consists of an ordered list of instructions, where each instruction carries information about the memory locations accessed (if any). A set of exhaustive traces (i.e. for different paths) can be used to give a sound over-approximation of the memory demand and the processor demand of a task by taking the maximum memory (processor) demand over all traces for the task. As a result, the framework decouples response time analysis from a reliance on context independent WCET values (in isolation). Instead, the analysis formulates response times directly from the demands on different hardware resources. Such a separation of concerns trades different sources of pessimism. The simplifications used in [START_REF] Altmeyer | A generic and compositional framework for multicore response time analysis[END_REF] to make the analysis tractable are unable to take advantage of overlaps between processing and memory demands; however, this compromise is set against substantial gains acquired by considering the worst-case behaviour of hardware resources, such as the memory bus, over long durations equating to task response times, rather than summing the worst case over short durations such as a single accesses, as is the case with the traditional approach using context-independent WCETs. With the MRTA framework, the response time Ri of task τi executing on core Px is computed using the following recurrence relation:

Ri = PDi +I PROC (i, x, Ri)+I BUS (i, x, Ri)+I DRAM (i, x, Ri)
(1) Where PDi is the processor demand, which equates to the execution time of task τi in isolation assuming a perfect bus and memory with zero latency. I PROC is the interference on the core due to higher priority tasks preempting or delaying task τi. I BUS is the interference on the bus computed using a mathematical model of the bus arbiter. Finally I DRAM is the interference due to DRAM refreshes. Equation ( 1) is solved as part of a larger fixed-point iteration which operates over the set of tasks, see Algorithm 1 in [START_REF] Altmeyer | A generic and compositional framework for multicore response time analysis[END_REF] for details.

The MRTA framework represents a generic and compositional solution for response time analysis. It allows the modelling of a wide range of different arbitration policies (and a combination of them), as well as different memory models (no cache, data and instruction cache, scratchpads, etc. and a combination of them). In this paper, we build upon the MRTA framework, instantiating it for different hardware components, bus arbitration policies, and application models.

The Synchronous Data Flow Model

Our aim is to obtain accurate bounds on the worst-case response time for data flow programs. A simple example of a data flow program is shown in Figure 3. In this work, we consider mono-rate programs, i.e. all tasks have the same period. In the case of a multi-rate program, we assume unfolded execution to the hyper-period (the least common multiple of the tasks' periods), effectively reducing the problem to a mono-rate one 1 . Also, we consider that all tasks in a cycle must complete before the end of the cycle, which is a common constraint when scheduling synchronous programs. As a consequence, scheduling can be done on one period (or hyper-period); the same schedule is then repeated indefinitely.

In terms of scheduling, the tasks in the data flow program are seen as an acyclic dependency graph. A task is released only when all its predecessors have finished their execution, i.e. when they produce tokens for the next tasks. In the example given in Figure 3, the output data of task τ1 must be available to task τ4 before it can execute. Hence, the release date of task τ4 should be greater than the finish time of task τ1. The data produced is written into a memory location where the consumer task can read it. In this case the memory bus is a shared resource and concurrent accesses may suffer from arbitration delays. In the example, tasks τ2, τ4, and τ6 write to the memory of task τ3 which creates potential interference within the response time of each task.

Our algorithm takes as input a fixed mapping of tasks to cores, and a fixed order for tasks mapped to the same core. We purposely delegate the mapping and ordering to a separate tool, dedicated to optimisation of the schedule and mapping, and focus on the analysis part. Mapping and ordering of tasks can also be done manually. We produce a completely static, time-driven schedule. There cannot be two tasks active on the same core at the same time, hence we do not use preemption and a task starts immediately when it is released. The schedule specifies the exact, fixed release date for each task. This is in a way pessimistic in the sense that each task waits for the worst-case response time of each of the tasks it is dependent on (it cannot start even if all of them have completed well before their deadline); however, our aim is to optimise the worst case, not the average case. The scheduling scheme has good properties for a hard-real time system. First, it enables the application to be executed without any operating system: we only require communication primitives, and one primitive to wait for a specified instant; they can be provided as a simple library. Also, it makes the whole execution highly predictable since the release date of a task does not depend on the execution time of previous tasks: we avoid any potential domino effects in timing.

We introduce the following additional notation used in our analysis: Each task τi has a release date reli (effectively an offset relative to the start of the data flow program) Θ = {rel1, ..., reln} is the set of release dates and R = {R1, ..., Rn} is the set of upper bound response times of tasks in Γ. Note that there is no order relation between reli and reli+1 (resp. Ri and Ri+1) in the set Θ (resp. R). Recall that each task is statically mapped to a core.

The approach we propose takes into account the interference on the bus as part of the response time analysis. Using the SDF model, we know which tasks could potentially execute at the same time and therefore be co-runners. We make use of this information to derive tight bounds on the amount of interference. Moreover, there is an implicit dependency between two successive periodic instances which allows us to limit the analysis to only one instance of the task graph. Our analysis, based on an adaptation of the MRTA framework, assumes static non-preemptive scheduling based on the task graph.

In summary, in addition to providing a model for the Kalray MPPA-256's bus arbiter, the main difference between the basic MRTA approach [START_REF] Altmeyer | A generic and compositional framework for multicore response time analysis[END_REF] and our approach is that MRTA considers sporadic tasks, but does not exploit any knowledge of dependencies or sequentiality between them. In contrast, we take into account the task dependencies (similarly to [START_REF] Choi | Conservative modeling of shared resource contention for dependent tasks in partitioned multi-core systems[END_REF]) and the precise schedule including release dates and response times. As a consequence, we have to solve another fixed-point problem since the schedule depends on the response times of each task, and vice-versa.

ANALYSIS FOR SDF APPLICATIONS ON THE MPPA-256

In this section we first quantify the different sources of interference that need to be considered in analysing synchronous data flow applications running on a compute cluster of the Kalray MPPA-256. We then describe how bus interference can be computed using the task dependency graph for a synchronous data flow program, thus avoiding pessimism in the analysis caused by lack of information about co-runners. We then derive a mathematical model of the multi-level arbiter of the Kalray MPPA-256. Finally we describe our response time analysis algorithm.

Quantification of the Interference

We now highlight the main sources of interference that need to be considered as part of (1) when determining the response time Ri of task τi, given the hardware and application models considered.

The interference on the core I PROC (i, x, Ri) typically comes from delays or preemptions due to the execution of higher priority tasks on the same core. In our application model, we assume a static non-preemptive scheduler. Task release dates are set such that only one task is active per core at any given time. This effectively eliminates all interference from higher priority tasks executing on the same core. It also simplifies the analysis by removing all cache-related preemption delays [START_REF] Altmeyer | Improved cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems[END_REF].

The interference due to the DRAM is mainly due to refresh cycles. The Kalray MPPA-256 supports a DDR memory accessed through the I/O clusters. An access from a core in a compute cluster has to cross the NoC and the I/O cluster and finally the DDR controller. All these layers add to the complexity of the analysis and the access delay. For predictable operation, such accesses are generally avoided by pre-loading all of the code and data into the shared memory of the compute cluster. The on-chip RAM of the MPPA is 32 MB, 2 MB per cluster, which is sufficient for many applications.

We therefore assume that ∀t > 0, I DRAM (i, x, t) = 0.

The interference on the bus depends on the specific arbitration policy used. Cache misses in the private data and instruction caches issue requests to the shared memory that are granted according to the multi-level arbiter. A detailed derivation of the I BUS (i, x, R, Θ) function that depends on the set of release dates of all tasks is given in the following section.

Taking the above considerations into account, the response time formula given in (1) simplifies to:

Ri = PDi + I BUS (i, x, R, Θ) (2)
Note, here R is the set of response times and Θ is the set of release dates for all tasks.

Bus Interference

In our application model, we consider a task dependency graph mapped to a set of cores. The hardware architecture allows the mapping of contiguous addresses to the same memory bank. Thus, concurrent accesses are independent as long as they are done in different memory banks, which reduces the bus interference. We exploit this by allocating the memory of each task running on the same core to the same bank. Tasks run on their locally reserved memory banks and access other locations only when writing data to the next successive task(s) in the task graph. We denote by MD b i the memory demand of task τi on memory bank b. The bus interference is given by:

I BUS (i, x, R, Θ) = b∈B i BUS b (i, x, R, Θ) × d ( 3
)
where d is the latency of a bus access without interference, Bi is the set of memory banks accessed by task τi, and BUS b (i, x, R, Θ) is a function that, accounting for the arbitration policy, gives an upper bound on the number of accesses that can delay completion of task τi (running on core Px) during a given time interval. Note that BUS b (i, x, R, Θ) includes both accesses of the task of interest and accesses performed by other tasks, since both delay the execution by the bus latency.

In order to derive BUS b (i, x, R, Θ), we need to compute an upper bound on all bus accesses during the response time of task τi. We define S x,b i (R) as an upper bound on the number of accesses by the task of interest τi running on core Px within its response time. Note that since the scheduler is non-preemptive the bus accesses from core Px come only from the memory demand of task τi on the memory bank b (MD b i ). Since we analyse one instance of task τi, we have:

S x,b i (R) = MD b i (4)
We define ∆ i,k (R, Θ) the overlap duration between tasks τi and τ k . The computation of the overlap is trivial since we already know the release dates and response times of tasks τi and τ k . Note that ∆ i,k (R, Θ) is 0 when the tasks do not overlap.

We use W i,k b (R, Θ) to denote an upper bound on the number of accesses by task τ k that may interfere with task τi at the memory bank b during its response time. In the absence of detailed information on the pattern of access requests within a task, we consider that any two tasks that overlap in time can interfere on each of their accesses. W i,k b (R, Θ) is given by:

W i,k b (R, Θ) = min(MD b k ,     ∆ i,k (R, Θ) d     ) (5)
We use A y,b i (R, Θ) to denote an upper bound on the number of accesses by all tasks running on core Py = Px during the response time of task τi. The number of accesses is bounded by the memory demand of each task on memory bank b. A y,b i (R, Θ) is therefore given by:

A y,b i (R, Θ) = k∈Γy W i,k b (R, Θ) (6)
The terms S x,b i (R) and A y,b i (R, Θ) are used to derive an upper bound on the number of accesses that contribute to the interference during the response time of task τi, which also depends on the bus arbitration policy. The multi-level arbiter of the Kalray MPPA-256 requires a combination of several policies (see Figure 2). We initially make the pessimistic assumption that the bus arbiter is work-conserving2 and that the accesses from the task of interest τi are dealt with last of all. (We note that compared to the analysis given in [START_REF] Altmeyer | A generic and compositional framework for multicore response time analysis[END_REF] there is no +1 term accounting for an access from a lower priority preempted task. Since we assume a static non-preemptive schedule, any previous task and its accesses must have completed before task τi starts). Thus we have:

BUS b (i, x, R, Θ) = S x,b i (R) + A y,b i (R, Θ) y∈G1∧y =x + A G2,b (R, Θ) + A G3,b (R, Θ) (7)
(We recall that G1, G2 and G3 are the three groups in the arbitration hierarchy defined in Section 2.1).

Model of the Multi-level Bus Arbiter

In this section, we study the multi-level arbitration policy used in the Kalray MPPA-256 architecture. We consider the bus arbiter to a memory bank b as shown in Figure 2. The policy operates over 4 levels which we label L1 to L4 where L1 is the first (left-most) level, and L4 the final level which is based on fixed priority arbitration. Our analysis is built up following the hierarchy from level L1 to level L4.

Level L1: As input to the first level, we assume that the maximum number of accesses that can be generated by each source in the response time of a task can be determined. These values are as follows:

• First group (G1): this is a core and may be treated in the same way as the analysis given for a round-robin arbiter in [START_REF] Altmeyer | A generic and compositional framework for multicore response time analysis[END_REF]. Note that we do not need to distinguish between accesses that come via the Instruction Cache (IC) and those that come via the Data Cache (DC), since all must be processed before the task of interest τi can complete. Hence we may represent the output from this group as either S x,b i (R) or A y,b i (R, Θ) depending on whether we are computing the accesses from the core that τi executes on, or from another core.

• Second group (G2): here we only need to compute the overall output from the group:

A G2,b i (R, Θ) = A T x,b i (R, Θ) + A DSU,b i (R, Θ) + A RM,b i (R, Θ
), since we are only interested in the interference it generates.

• Third group (G3): there is only one item, hence the output is the same as the input:

A G3,b i (R, Θ) = A Rx,b i (R, Θ).
Level L2: At level L2 the outputs (accesses) from all 16 processors are combined via a 16 to 1 Round-Robin (RR) arbiter. Note that each core has only one slot in the RR cycle. The number of accesses to bank b that can delay the execution of a task on core Px at the output of L2 is given by:

BUS L2 b (i, x, R, Θ) = S x,b i (R) + y∈G1∧y =x min A y,b i (R, Θ), S x,b i (R) (8)
where x is the index of the core Px that task τi executes on, and similarly y ranges over the other 15 cores. The worst-case situation occurs when each access in S x,b i is delayed by each core Py = Px for 1 slot. Given the round-robin arbiter, interference by core Py is limited to the minimum of the number of accesses from Py and from Px, i.e. min A y,b i (R, Θ), S x,b i (R) . Level L3: At level L3, the output from the level L2 arbiter, i.e. ( 8), is combined with that from the second group, i.e. A G2,b (R, Θ), again via a round-robin arbiter, hence we have:

BUS L3 b (i, x, R, Θ) = BUS L2 b (i, x, R, Θ) + min A G2,b i (R, Θ), BUS L2 b (i, x, R, Θ) (9)
Again, the worst-case situation occurs when each access in BUS L2 b (i, x, R, Θ) is delayed by the output of G2 for 1 slot. Interference by the output of G2 is limited to A G2,b i (R, Θ). Level L4: Finally, at level L4, the output from the level L3 arbiter, i.e. ( 9), is combined with the output from G3, i.e. A Rx,b i (R, Θ). As this is done via a fixed priority arbiter with higher priority given to A Rx i (R, Θ), we have:

BUS L4 b (i, x, R, Θ) = BUS L3 b (i, x, R, Θ) + A G3,b i (R, Θ) (10)
Finally, given the bus latency d, the bus interference is given by:

I BUS (i, x, R, Θ) = b∈B i BUS L4 b (i, x, R, Θ) × d (11)

Response Time Analysis

Our response time analysis algorithm (Algorithm 1) is based on the MRTA approach [START_REF] Altmeyer | A generic and compositional framework for multicore response time analysis[END_REF]. First, we augment the framework with the model of the multi-level arbiter of the Kalray MPPA-256, and modify the way computation of the potential interference is performed: the original MRTA framework uses a model with sporadic tasks with minimum inter-arrival times and without dependencies, while we analyze a single period of a single-rate application, with a static schedule. Knowing the release dates and response times, Algorithm 1 computes the number of accesses that can delay a given task in a given time interval. Since the potential interference depends on the release dates and response times, and the response times depend on the interference, this requires a fixed-point iteration (line 10).

After computing the response times, the schedule we get may not respect the dependencies and sequentiality constraints. We modify the release dates so that each task is released immediately after each of the tasks it depends on is guaranteed to have completed (Algorithm 2). Modifying the release dates may change the interference, hence we have to re-compute it using Algorithm 1, and so on, until a fixed point is reached (Algorithm 3).

Algorithm 1 solves the recursive equation ( 2) using a fixedpoint iteration, and computes the response times R of all Algorithm 1 Response Time Analysis Given a Set of Release Dates 1: function MultiCoreRTA(Θ) 2:

l = 1
3:

∀ i : R l [i] = PD i + MD i • d 4: do 5:
for all i do 6:

R l+1 [i] = PD i + I BUS (i, x, R l , Θ)

7:

I BUS is given by equation 118:

end for 9: for all i do 3:

l = l + 1 10: while R l = R l-
Θ[i] = max(Θ min [i], {Θ[k] + R[k]|k ∈ deps(i)})

4:

end for

5:

return Θ 6: end function tasks given the release dates Θ. Algorithm 2 ensures the dependency constraints between tasks are satisfied. It is parameterised by Θmin which gives the earliest release date for each task: Θmin[i] = t means that task τi cannot start before t. A task τi is released only when all the tasks it depends on (denoted by deps(i)) are guaranteed to have finished. We statically schedule every release date, hence we set the release date of each task to the maximum of the worstcase finish time of each task it depends on. Algorithm 3 uses MultiCoreRTA (Algorithm 1) to compute the response times of tasks in Γ given a set of release dates (line 5). Then, UpdateReleases (Algorithm 2) is used to verify and update the dependency constraints. Algorithm 3 starts from initial release dates (bounded by the SDF period) (InitRelease, line 3) and performs a fixed-point iteration. Algorithm 3 terminates when UpdateReleases does not change the release dates. When this happens, the response times R l+1 computed before the call to UpdateReleases remain valid afterwards, and hence are valid at the end of the loop. Termination of Algorithm 1 is guaranteed: we limit the computation to one period of the task graph; the number of bus accesses is bounded which implies that the amount of interference seen by a task is also bounded. The response time computation of task τi is a monotonically increasing and bounded function, thus Algorithm 1 converges for any values in Θ. Termination of Algorithm 3 is non-trivial to show: the intuition is that a task cannot interfere with its past. At each iteration, release dates of tasks released before some instant of time t become fixed and remain the same for all subsequent iterations, with t advancing by at least one release date at each iteration. Note this means the number of iterations of Algorithm 3 is at most (number of tasks -1). The complete proof is given in the technical report [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor-full version[END_REF].

Since Algorithm 3 is parameterised by a function InitRelease, one might think that the choice of InitRelease could impact the precision of the result. However, we prove in the technical report [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor-full version[END_REF] that the fixed point of the composition of MultiCoreRTA and UpdateReleases is unique, hence the algorithm will return the same schedule for any function InitRelease, and there 6:

Θ l+1 =UpdateReleases(Θ min ,Θ l ,R l+1 )
7:

l = l + 1 8: while Θ l = Θ l-1 9: if ∀ i : (Θ l [i] + R[i] l ) ≤ D i then 10:
return schedulable

11:

else return not schedulable

12:

end if 13: end function is no point trying to optimise it. In our implementation, we start with Θ 0 = Θmin, i.e. all release dates set to zero.

EVALUATION

In this section we evaluate our approach using different configurations. We show how the application model as well as the architecture configuration may affect the estimation of the WCRT. We analyse a didactic micro-benchmark and a case study of a flight management system controller to validate our approach. More experiments with detailed results can be found in the long version of this paper published as a technical report [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor-full version[END_REF].

Experimental Setup

Static analysis tools such as, OTAWA [START_REF] Ballabriga | OTAWA: An open toolbox for adaptive WCET analysis[END_REF] and aiT [START_REF] Wilhelm | The worst-case execution-time problemoverview of methods and survey of tools[END_REF] 3 , do not yet support the Kalray MPPA-256 Bostan. For this reason, we establish the task profiles from measurement-based techniques. Each task is executed in isolation while profiling processor cycles and the number of cache misses. Several measurements are performed for each task and the results show a variance approaching zero. This reflects the efforts made in the design of the Kalray MPPA-256 targeting real time applications.

In our experiments, we consider a bus delay d = 10 cycles obtained from internal specifications (we ignore transaction pipelining and TLB cache misses). We also consider that the context switch delay is included in the task execution. We assume that the Resource Manager (RM), which loads the application onto the cores before operation starts, does not interfere with running tasks (A RM,b i = 0, ∀i, b). Finally, the Debug Support Unit (DSU) is disabled during operation (A DSU,b i = 0, ∀i, b). Bus Model: We assume the benchmark in Section 4.2 is run in isolation on a compute cluster, i.e. accesses from the NoC do not occur during the execution of the application of interest. As a consequence, by setting A Rx,b = A T x,b = 0 in [START_REF] Halbwachs | The synchronous data flow programming language lustre[END_REF], the interference is simplified to one level of round-robin arbitration. We do consider the accesses from the NoC in the benchmark in Section 4. [START_REF] Ballabriga | OTAWA: An open toolbox for adaptive WCET analysis[END_REF] Execution Model: We first consider a single-phase execution model where we make no assumptions about the distribution of read and write accesses between the start and end of a task. In our code generation scheme for the SDF model, tasks execute computations, then write the result to a shared memory location where the next task can 3 read it. Similar to [START_REF] Melani | Memory-processor co-scheduling in fixed priority systems[END_REF], this execution model allows each task to be split into a first execution phase limited to reading the input and doing computations, and then a write phase where the output is sent to the next task. In the execution phase, the accesses are to the local memory bank of the task whereas in the write phase, requests may access a remote memory bank. We exploit this execution model in our analysis. We consider the two phases of a task as separate subtasks with a direct dependency relation. Using our analysis technique we compare the single-phase model with the two-phase model. Experiments: We explore and compare a number of setups for the experimental evaluation so as to determine the effectiveness of various techniques that form part of the schedulability analysis. In the first experiment E1, we use our approach taking into account a two-phase execution model. Experiment E2 also applies our approach, but using a single-phase execution model. In experiment E3, we use a simplified approach that discards the release dates of tasks, meaning that all tasks potentially overlap, and considers the tasks using the two-phase execution model. The same approach as E3 is used in E4, but using the single-phase execution model. Finally, we consider in experiment E5 that co-runners continuously interfere with the task of interest. This is a pessimistic analysis that assumes the worst-case interference on each memory access. Note that, this may result in unbounded interference due to the fixed priority level of the MPPA bus. In this case, we consider the upper bound on the number of accesses by all higher priority components during the analysed execution instance. Then, we assume that each task access is delayed by all the higher priority accesses. In the following, we compare the different analyses with different arbitration policies for each benchmark.

Didactic Example

We analyse the example given in Figure 3. Table 1 summarises each task profile that consists of the processor demand and the memory demand. Figure 4 gives a static schedule computed by our approach which accounts for the bus interference and the dependencies between tasks. Figure 5 compares the overall estimated response times obtained with different analyses. We note that taking into account the memory banks always yields a better estimation of the overall response time. Further, taking into account the two-phase execution model (E1), the estimation is 1.5 times smaller than the pessimistic approach (E5) while the analysis with the single-phase execution model (E2) is 1.49 times smaller. The approaches that discard the release dates (E3 and E4) are as pessimistic as E5 in the analysis that discards the memory banks, and only 1.06 times smaller while taking into account the memory banks.

ROSACE (Flight Management System)

Pagetti et al. [START_REF] Pagetti | The ROSACE case study: From simulink specification to multi/many-core execution[END_REF] provide a case study of a Flight Management System (FMS) 4 . The case study consists of a multi-rate controller and an environment simulator. In this kind of application, the input (sampled from physical sensors) is transmitted to a controller which, after computation, sends commands to the actuators. Figure 6 illustrates the set of tasks in the SDF application, their inputs, outputs, dependencies, and their rates. We established task profiles by executing each task in isolation and measuring a trace of its execution. The profiles are given in Table 2. The inputs from sensors and the commands to the actuators are sent through the NoC via the Rx and Tx components. Since there are multiple rates, we unfold the SDF program over a hyper-period in order to The smallest schedulable period obtained with different analyses make the model compatible with our approach. In this case, tasks with a frequency of 100 Hz execute twice within the hyper-period, while tasks with a frequency of 50 Hz execute only once. Further, the Rx component writes the inputs (h, az, vz, q, va) to the shared memory four times (200 Hz) within the hyper-period, while the Tx component reads and transmits the outputs (δec, δ the ) once (50 Hz).

Our experiments consider a time window with the length of the hyper-period that starts with the Tx accesses from the previous execution of the program.

There are several possible mappings for the multi-rate application. We choose the mapping described in Figure 7 and evaluate its schedulability with the previously defined analyses. We also consider a single-level round-robin bus (RR) as well as the multi-level arbiter (MPPA). This allows us to compare the performance of the MPPA against the conventional RR arbitration policy using our approach. Figure 8 gives the smallest period, in processor cycles, for which the mapping in Figure 7 is schedulable. This is equivalent to finding the slowest processor clock frequency that satisfies the scheduling requirements.

The results in Figure 8 show that accounting for the memory banks improves the estimation with a factor of 1.77 to 2.52 in E1, E2, E3, E4 (5 banks vs. 1 bank). Our refined approach that takes into account the number of memory banks and the release dates can verify schedulability with a hyper-period of 2588 cycles (E1) and 2604 cycles (E2) assuming the MPPA bus. This represents an improvement by a factor of 4.15 (E1) compared to the pessimistic approach in E5 with 10748 cycles. The gain achieved by considering release dates is a factor of 1.68 in E1 (respectively 1.29 in E2) when compared against E3 (respectively E4) which ignores release dates. Our analysis with the RR bus gives an estimation of 2388 cycles in E1 (respectively 2400 cycles in E2) which corresponds to a gain of a factor 3.3 when compared to the pessimistic approach in E5 that has 7900 cycles. Note that the two-phase model is more pessimistic than the single-phase model when comparing E3 and E4. This is due to accumulated pessimistic considerations on the write phase and the execution phase which may lead in some cases to a higher estimation than when the execution is considered as a single phase. We address this in more detail in the technical report [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor-full version[END_REF]. The analysis of the RR arbiter provides slightly better performance than that for the multi-level arbiter. Any pessimistic assumption in the analysis have a higher effect on the multi-level arbiter than the RR arbiter. This is due to the fixed priority level that pessimistically counts all highest priority accesses at each bus access.

Finally, we comment on the run-time of our approach. The analysis of the FMS controller takes 0.15 seconds (Intel 2.4 GHz CPU). The analysed hyper-period has 18 tasks. The analysis in E2 (single-phase execution model) takes 4 iterations in Algorithm 3 and at most 20 iterations at each execution of Algorithm 1. In E1, the analysed hyper-period has 31 subtasks/tasks and takes 6 iterations in Algorithm 3 and at most 31 iterations at each execution of Algorithm 1.

CONCLUSIONS AND FUTURE WORK

We presented an analysis able to compute a valid static schedule of a synchronous data flow application on the Kalray MPPA-256 multi-core architecture with shared memory and a multi-level arbiter. We start the analysis with a given mapping, set of dependencies between tasks and precedence constraints: the choice of the mapping and the order of tasks on a given core can either be defined manually or delegated to a separate allocation algorithm.

The analysis we derived was based on the Multicore Response Time Analysis (MRTA) framework [START_REF] Altmeyer | A generic and compositional framework for multicore response time analysis[END_REF]. We extended this framework by deriving a mathematical model of the multi-level bus arbitration policy used by the Kalray MPPA-256. Further, we refined the analysis to account for the release dates and response times of co-runners, and the use of memory banks. Improvements to the precision of the analysis may be achieved by splitting each task into two sequential phases, with the majority of the memory accesses in the first phase, and a small number of writes in the second phase. Our experimental evaluation focussed on the ROSACE avionics case study. Using measurements from the Kalray MPPA-256 as a basis, we showed that the new analysis introduced in this paper leads to response times that are a factor of 4.25 smaller for this application, compared to the default approach of assuming that each access is subject to the worst-case interference.

While we accurately model the 3-level bus arbiter and the set of memory banks in the Kalray MPPA-256 architecture, some work is still needed to model the end-to-end delay for a complete application. We focused on local interferences between cores when accessing the memory. We will later work on a model of the NoC traffic, i.e. A Rx,b i and A T x,b i . Any formula returning a number of accesses for a given time interval can be plugged into their computation: we can use the hardware configuration of the packet shaper (at the exit of each MPPA cluster), which limits the allowed bandwidth for each compute cluster on the NoC. Computations based on Network Calculus can also provide the worst-case number of accesses for a time window [START_REF] De Dinechin | Guaranteed services of the NoC of a manycore processor[END_REF]. We can also use knowledge of the application's architecture (e.g. compute the amount of data that is written to and from the cluster during each clock cycle of the SDF application). The resource manager will also require consideration, as in general it can access the shared memory and is itself a shared resource to consider in response time computations.

We considered that each access to the memory takes 10 cycles, and may delay other accesses by 10 cycles. This is actually a worst case as 10 cycles elapse between the start and the end of a memory transaction, but a more precise model should take transaction pipelining into account: during each of the 10 cycles above, only one stage of the pipeline is used by the transaction. In the best case, a core and memory couple can execute one transaction per cycle. Taking this into account should lead to a dramatic improvement in the precision of our analysis, but is non-trivial since interference at different levels of the arbiter happen at different stages of the pipeline. Other details of the architecture will be modeled more finely in the future: for example, write transactions are asynchronous, while read transactions block the core until completion (no speculation).

Figure 2 :

 2 Figure 2: Request arbitration to a shared memory bank (RR: Round-Robin. FP: Fixed Priority)

Figure 3 :

 3 Figure 3: Example of a data flow program

Algorithm 3 R

 3 Adapt Release Dates to Meet Real-Time Constraints 1: function ComputeRT(Θ min ) l+1 =MultiCoreRTA(Θ l )

Figure 4 :Figure 5 :Figure 6 :

 456 Figure 4: Static scheduling of the example in Figure 3 considering 3 memory banks

Figure 7 :Figure 8 :

 78 Figure 7: Task-to-core mapping and unfolding of tasks in the FMS controller 1 bank 5 banks

Table 1 :

 1 Task profiles of SDF example in Figure

	task PD (cycles) MD (accesses) dependencies
	τ 1	5	42	∅
	τ 2	8	30	{τ 1 }
	τ 3	20	18	{τ 2 , τ 4 , τ 6 }
	τ 4	5	52	{τ 1 }
	τ 5	8	30	∅
	τ 6	20	58	{τ 5 }

Table 2 :

 2 Task profiles of the FMS controller

		Task		PD (cycles) MD(accesses)
		altitude	275	22
		az filter	274	22
		h filter	326	24
		va control 303	24
		va filter	301	23
		vz control 320	25
		vz filter	334	25
	P 4	h filter	altitude	vz control	h filter
		100 Hz	50 Hz	50 Hz	100 Hz
	P 3	az filter			az filter
		100 Hz			100 Hz
	P 2	vz filter			vz filter
		100 Hz			100 Hz
	P 1	q filter			q filter
		100 Hz			100 Hz
	P 0	va filter	va control	va filter
		100 Hz	50 Hz		100 Hz

The unfolding preserves the required minimum separation between jobs, since our scheduling scheme includes fixed release dates for each task. The unfolding process thus assigns proper release dates to multiple instances of the same task. We note the potentially large size of the hyper-period which may introduce a complexity issue.

A work-conserving bus arbiter will not idle the bus as long as there are pending requests.

To the best of our knowledge, aiT supports the first generation Kalray MPPA-256 Andey only.

Open source implementation available on the svn repository https://svn.onera.fr/schedmcore/branches/ schedmcore-RTAS2014/Case Study RTAS

Acknowledgments

This work was funded in part by the grant CAPACITES (PIA-FSN2 n • P3425-146798) from the French Ministère de l'économie, des finances et de l'industrie, the EPSRC project MCC (EP/K011626/1) and the INRIA International Chair program. EPSRC Research Data Management: No new primary data was created during this study.