Amit Kumar Pandey
email: akpandey@aldebaran.com

Rodolphe Gelin
email: rgelin@aldebaran.com

Rachid Alami
email: rachid.alami@laas.fr

Renaud Viry
email: renaud.viry@laas.fr

Axel Buendia
email: axel.buendia@cnam.fr

Roland Meertens
email: rolandmeertens@gmail.com

Mohamed Chetouani
email: mohamed.chetouani@upmc.fr

Laurence Devillers

Marie Tahon
email: marie.tahon@limsi.fr

David Filliat
email: david.filliat@ensta-paristech.fr

Yves Grenier
email: yves.grenier@telecom-paristech.fr

Mounira Maazaoui
email: maazaoui@telecom-paristech.fr

Abderrahmane Kheddar
email: kheddar@gmail.com

Frédéric Lerasle
email: frederic.lerasle@laas.fr

Laurent Fitte Duval

Romeo2 Project: Humanoid Robot Assistant and Companion for Everyday Life: I. Situation Assessment for Social Intelligence 1

Keywords: Situation Assessment, Socially Intelligent Robot, Human Robot Interaction, Robot Companion

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.

Introduction

As robots started to co-exist in a human-centered environment, the human awareness capabilities must be considered. With safety being a basic requirement, such robots should be able to behave in a socially accepted and expected manner. This requires robots to reason about the situation, not only from the perspective of physical locations of objects, but also from that of 'mental' and 'physical' states of the human partner. Further, such reasoning should build knowledge with the human understandable attributes, to facilitate natural human-robot interaction.

The Romeo2 project (website1 ), the focus of this paper, is unique in that it brings together different perception components in a unified framework for reallife personal assistant and companion robot in an everyday scenario. This paper outlines our perception architecture, the categorization of basic requirements, the key elements to perceive, and the innovation advantages such a system provides. Fig. 1 shows the Romeo robot and its sensors. It is a 40kg and 1.4m tall humanoid robot with 41 degrees-of-freedom, vertebral column, exoskeleton on legs, partially soft torso and mobile eyes.

An Example Scenario

Mr. Smith lives alone (with his Romeo robot companion). He is elderly and visually impaired. Romeo understands his speech, emotion and gestures, assists him in his daily life. It provides physical support by bringing the 'desired' items, and cognitive support by reminding about medicine, items to add in to-buy list, playing memory games, etc. It monitors Mr. Smith's activities and calls for assistance if abnormalities are detected in his behaviors. As a social inhabitant, it plays with Mr. Smith's grandchildren visiting him. This outlined partial target scenario of Romeo2 project (also illustrated in fig. 2), depicts that being aware about human, his/her activities, the environment and the situation are the key aspects towards practical achievement of the project's objective.

Related Works and the main Contributions

Situation awareness is the ability to perceive and abstract information from the environment [START_REF] Bolstad | Situation awareness: Does it change with age[END_REF]. It is an important aspect of day-to-day interaction, decisionmaking, and planning, so as important is the domain-based identification of the elements and attributes, constituting the state of the environment. In this paper, we will identify and present such elements from companion robot domain perspective, sec. 2.2. Further, three levels of it have been identified (Endsley et al. [START_REF] Endsley | Toward a theory of situation awareness in dynamic systems[END_REF]): Level 1 situation awareness: To perceive the state of the elements composing the surrounding environment. Level 2 situation awareness: To build a goal oriented understanding of the situation. Experience and comprehension of the meaning are important. Level 3 situation awareness: To project on the future. Sec. 2.1 will present our sense-interact perception loop and map these levels.

Further, there have been efforts to develop integrated architecture to utilize multiple components of situation assessment. However, most of them are specific for a particular task like navigating [START_REF] Pomerleau | Neural network perception for mobile robot guidance[END_REF], intention detection [START_REF] Lee | Cognitive robotic engine: Behavioral perception architecture for human-robot interaction[END_REF], robot's self-perception [START_REF] Chella | A robot architecture based on higher order perception loop[END_REF], spatial and temporal situation assessment for robot passing through a narrow passage [START_REF] Beck | Spacio-temporal situation assessment for mobile robots[END_REF], laser data based human-robot-location situation assessment, e.g. human entering, coming closer, etc. [START_REF] Jensen | Narrative situation assessment for humanrobot interaction[END_REF]. Therefore, they are either limited by the variety of perception attributes, sensors or restricted to a particular perception-action scenario loop. On the other hand, various projects on Human Robot Interaction try to overcome perception limitations by different means and focus on high-level semantic and decision-making. Such as, the detection of objects is simplified by putting tags/markers on the objects, in the detection of people no audio information is used, [START_REF]CHRIS-Project: Cooperative human robot interaction systems[END_REF], [START_REF] Lallee | Towards a platform-independent cooperative human-robot interaction system: I. perception[END_REF], etc. In [START_REF]EYESHOTS-Project: Heterogeneous 3-d perception across visual fragments[END_REF], different layers of perception have Fig. 3. A generalized perception system for sense-interact in Romeo2 project, with five layers functioning in a closed loop.

been analyzed to build representations of the 3D space, but focused on eye-hand coordination for active perception and not on high-level semantics and perception of the human.

In the Romeo2 project, we are making effort to bring a range of multi-sensor perception components within a unified framework (Naoqi, [18]), at the same time making the entire multi-modal perception system independent from a very specific scenario or task, and explicitly incorporating reasoning about human, towards realizing effective and more natural multi-modal human robot interaction. In this regard, to the best of our knowledge, Romeo2 project is the first effort of its kind for a real world companion robot. In this paper, we do not provide the details of each component. Instead, we give an overview of the entire situation assessment system in Romeo2 project (sec. 2.1). Interested readers can find the details in documentation of the system [18] and in dedicated publications for individual components, such as [START_REF] Caron | Neural network based 2d/3d fusion for robotic object recognition[END_REF], [START_REF] Filliat | Rgbd object recognition and visual texture classification for indoor semantic mapping[END_REF], [START_REF] Pandey | Towards human-level semantics understanding of humancentered object manipulation tasks for hri: Reasoning about effect, ability, effort and perspective taking[END_REF], [START_REF] Le Maitre | Self-talk discrimination in human-robot interaction situations for supporting social awareness[END_REF], [START_REF] Buendia | From informative cooperative dialogues to long-term social relation with a robot[END_REF], [START_REF] Tahon | Real-life emotion detection from speech in human-robot interaction: Experiments across diverse corpora with child and adult voices[END_REF], [START_REF] Mekonnen | People detection with heterogeneous features and explicit optimization on computation time[END_REF], [START_REF] Sehili | Attention detection in elderly people-robot spoken interaction[END_REF], etc. (see the complete list of publications 1 ). Further, the combined effort to bring different components together helps us to identify some of the innovation potentials and to develop them, as discussed in section 3.

Perceiving Situation in RomeoProject

A Generalized Sense-Interact Perception Architecture for HRI

We have adapted a simple yet meaningful, sensing-interaction oriented perception architecture, by carefully identifying various requirements and their interdependencies, as shown in fig. 3. The roles of the five identified layers are:

(i) Sense: To receive signals/data from various sensors. Depending upon the sensors and their fusion. This layer can build 3D point cloud world; sense stimuli like touch, sound; know about the robot's internal states such as joint, heat; record speech signals; etc. Therefore, it belongs to level 1 of situation assessment.

(ii) Cognize: Corresponds to the 'meaningful' (human-understandable level) and relevant information extraction, e.g. learning shapes of objects; learning to extract the semantics from 3D point cloud, the meaningful words from speech, the meaningful parameters in demonstration, etc. In most of the perception-action systems, this cognize part is provided a priori to the system. However, in Romeo2 projects we are taking steps to make cognize layer more visible by bringing together different learning modules, such as to learn objects, learn faces, learn the meaning of instructions, learn to categorize emotions, etc. This layer lies across level 1 and level 2 of situation assessment, as it is building knowledge in terms of attributes and their values and also extracting some meaning for future use and interaction.

(iii) Recognize: Dedicated to recognizing what has been 'cognized' earlier by the system, e.g. a place, face, word, meaning, emotion, etc. This mostly belongs to level 2 of situation assessment, as it is more on utilizing the knowledge either learned or provided a priori, hence 'experience' becomes the dominating factor. (iv) Track: This layer corresponds to the requirement to track something (sound, object, person, etc.) during the course of interaction. From this layer, level 3 of situation assessment begins, as tracking allows to update in time the state of the beforehand entity (person, object, etc.), hence involves a kind of 'projection'.

(v) Interact: This corresponds to the high-level perception requirements for interaction with the human and the environment. E.g. activity, action and intention prediction, perspective taking, social signal and gaze analyses, semantic and affordance prediction (e.g. pushable objects, sitable objects, etc.). It mainly belongs to level 3 of situation assessment, as involves 'predicting' side of perception.

Sometimes, practically there are some intermediate loops and bridges among these layers, for example a kind of loop between tracking and recognition. Those are not shown for the sake of making main idea of the architecture better visible.

Note the closed loop aspect of the architecture from interaction to sense. As shown in some preliminary examples in section 3, such as Ex1, we are able to practically achieve this, which is important to facilitate natural human-robot interaction process, which can be viewed as:

Sense → Build knowledge for interaction → Interact → Decide what to sense → Sense →...

Basic Requirements, Key Attributes and Developments

In Romeo2 project, we have identified the key attributes and elements of situation assessment, to be perceived from companion robotics domain perspective, and categorized along five basic requirements as summarized in table 1. In this section, we describe some of those modules. See Naoqi [18] for details of all the modules.

I. Perception of Human

People presence: Perceives presence of people, assign unique ID to each detected person. Face characteristics: To predict age, gender and degree of smile on a detected face. Posture characterization (human): To find position and orientation of different body parts of the human, shoulder, hand, etc. Perspective taking: To perceive reachable and visible places and objects from the human's perspective, with the level of effort required to see and reach. Emotion recognition: For basic emotions of anxiety, anger, sadness, joy, etc. based on multi-modal audio-video signal analysis. Speaker localization: Localizes spatially the speaking person. Speech rhythm analysis: Analyzing the characterization of speech rhythm by using acoustic or prosodic anchoring, to extract social signals such as engagement, etc. User profile: To generate emotional and interactional profile of the interacting user. Used to dynamically interpret the emotional behavior as well as to build behavioral model of the individual over a longer period of time. Intention analysis: To interpret the intention and desire of the user through conversation in order to provide context, and switch among different topics to talk. The context also helps other perception components about what to perceive and where to focus. Thus, facilitates closing the interaction-sense loop of fig. 3.

II. Perception of Robot Itself

Fall detection: To detect if the robot is falling and to take some human user and self-protection measures with its arms before touching the ground. Other modules in this category are self-descriptive. However it is worth to mention that, such modules also provide symbolic level information, such as battery nearly empty, getting charged, foot touching ground, symbolic posture sitting, standing, standing in init pose, etc. All these help in achieving one of the aims of Romeo2 project: sensing for natural interaction with human.

III. Perception of Object

Object Tracker: It consists of different aspects of tracking, such as moving to track, tracking a moving object and tracking while the robot is moving. Semantic perception (object): Extracts high-level meaningful information, such as object type (chair, table, etc.), categories and affordances (sitable, pushable, etc.)

IV. Perception of Environment

Darkness detection: Estimates based on the lighting conditions of the environment around the robot. Semantic perception (place): Extracts meaningful information from the environment about places and landmarks (a kitchen, corridor, etc.), and builds topological maps.

V. Perception of Stimuli

Contact observer: To be aware of desired or non-desired contacts when they occur, by interpreting information from various embedded sensors, such as accelerometers, gyro, inclinometers, joints, IMU and motor torques'.

Results and Discussion on Innovation Potentials

We will not go in detail of the individual modules and the results, as those can be found online [18]. Instead, we will discuss some of the advantages and innovation potentials, which such modules functioning on a unified platform could bring. Ex1: The capability of multi-modal perception, combining input from the interacting user, the events triggered by other perception components, and the centralized memorization mechanism of robot, help to achieve the goal of closing the interactsense loop and dynamically shaping the interaction. To demonstrate, we programmed an extensive dialogue with 26 topics that shows the capabilities of the Romeo robot. During this dialogue the user often interrupts Romeo to quickly ask a question, this leads to several 'conflicting' topics in the dialogue manager. The activation of different topics during an interaction over a period is shown in fig. 4. The plot shows that around 136th second the user has to take his medicine, but the situation assessment based memory indicates that the user has ignored and not yet taken the medicine. Eventually, the system results the robot urging the user to take his medication (pointed by blue arrow), making it more important than the activity indicated by the user during the conversation (to engage in reading a book, pointed by dotted arrow in dark green). Hence, a close loop between the perception and interaction is getting achieved in a real time, dynamic and interactive manner.

Ex2: Fig. 5(a) shows situation assessment of the environment and objects at the level of semantics and affordances, such as there is a 'table' recognized at position X, and this belongs to an affordance category on which something can be put. Fig. 5(b) shows situation assessment by perspective taking, in terms of abilities and effort of the human. This enables the robot to infer that the sitting human (as shown in fig. 5(c)) will be required to stand up and lean forward to see and take the object behind the box. Thanks to the combined reasoning of (a) and (b), the robot will be able to make the object accessible to the human by placing it on the table (knowing that something can be put on it), at a place reachable and visible by the human with least effort (through the perspective taking mechanism), as shown in fig. 5(c).

In Romeo2 we also aim to use this combined reasoning about abilities and efforts of agents, and affordances of the environment, for autonomous humanlevel understanding of task semantics through interactive demonstration, for the development of robot's proactive behaviors, etc. as suggested the feasibility and advantages in some of our complementary studies in those directions, [START_REF] Pandey | Towards human-level semantics understanding of humancentered object manipulation tasks for hri: Reasoning about effect, ability, effort and perspective taking[END_REF], [START_REF] Pandey | Towards a task-aware proactive sociable robot based on multi-state perspective-taking[END_REF]. Ex3: Analyzing verbal and non-verbal behaviors such as head direction (e.g. on-view or offview detection) [START_REF] Le Maitre | Self-talk discrimination in human-robot interaction situations for supporting social awareness[END_REF], speech rhythm (e.g. on-talk or self-talk) [START_REF] Ringeval | Novel metrics of speech rhythm for the assessment of emotion[END_REF], laugh detection [START_REF] Devillers | A social interaction system for studying humor with the robot nao[END_REF], emotion detection [START_REF] Tahon | Real-life emotion detection from speech in human-robot interaction: Experiments across diverse corpora with child and adult voices[END_REF], attention detection [START_REF] Sehili | Attention detection in elderly people-robot spoken interaction[END_REF], and their dynamics (e.g. synchrony [START_REF] Delaherche | Interpersonal synchrony: A survey of evaluation methods across disciplines[END_REF]), combined with acoustic analysis (e.g. spectrum) and prosodic analysis altogether greatly allows to improve social engagement characterization of the human during interaction. To demonstrate, we collected a database of human-robot interaction during sessions of cognitive stimulation. The preliminary result with 14 users shows that on a 7 level evaluation scheme, the average scores for questions, "Did robot show any empathy?", "Was it nice to you?" and "Was it polite?" were 6.3, 6.2 and 6.4 respectively. In addition, the multi-modality combination of the rhythmic, energy and pitch characteristics seems to be elevating the detection of self-talk (known to reflect the cognitive load of the user, especially for elderly) as shown in table of fig. 6. Ex4: Inferring face gaze (as illustrated in fig. 7), combined with sound localization and object detection, altogether provides enhanced knowledge about who might be speaking in a multipeople human-robot interaction, and further facilitates analyzing the attention and intention. To demonstrate this, we conducted an experiment with two speakers, initially speaking at the different sides of the robot and then slowly moving towards each other and eventually separate away. Fig. 8 shows the preliminary result for the sound source separation by the system based on beamforming. The left part (BF-SS) shows when only the audio signal is used. When the system uses the visual information combined with the audio signals, the performance is better (AVBF-SS) in all the three types of analyses: signal-to-interference ratio (SIR), signal-to-distortion ratio(SDR) and signal-to-artifact (SAR) ratio.

Ex5: The fusion of rich information about visual clues, audio speech rhythm, lexical content and the user profile is also opening doors for automated context extraction, helping for better interaction and emotion grounding and making the interaction interesting, like doing humor [START_REF]JOKER-Project: Joke and empathy of a robot/eca: Towards social and affective relations with a robot[END_REF].

Conclusion and Future Work

In this paper, we have provided an overview of the rich multi-modal perception and situation assessment system within the scope of Romeo2 project. We have presented our sensing-interaction perception architecture and identified the key perception components requirements for companion robot. The main novelty lies in the provision for rich reasoning about the human and practically closing the sensing-interaction loop. We have pointed towards some of the work in progress innovation potentials, achievable when different situation assessment components are working on a unified theoretical and functional framework. It would be interesting to see how it could serve as guideline in different context than companion robot, such as robot co-worker.

Fig. 1 .

 1 Fig. 1. Romeo robot and sensors.

Fig. 2 .

 2 Fig. 2. Romeo2 Project scenario: A Humanoid Robot Assistant and Companion for Everyday Life.

Fig. 4 .

 4 Fig. 4. Subset of interaction topics (right), and their dynamic activation levels based on multi-modal perception and events.

Fig. 5 .

 5 High-level situation assessment. (a) The semantics map of the environment. (b) Effort and Perspective taking based situation assessment. (c) Combining (a) and (b), the robot will be able to make the object accessible to the human.

Fig. 6 .

 6 Fig. 6. Self-talk detection

Fig. 7 .

 7 Fig. 7. Face, shoulder and face orientation detection of two interacting people.

Fig. 8 .

 8 Fig. 8. Sound source separation, only audio based (BF-SS) and audio-video based (AVBF-SS).

Table 1 .

 1 Identification and Classification of the key situation assessment components

This work is funded by Romeo2 project, (http://www.projetromeo.com/), BPIFrance in the framework of the Structuring Projects of Competitiveness Clusters (PSPC)


Angeliki Kritikakou
email: angeliki.kritikakou@onera.fr

Claire Pagetti
email: claire.pagetti@onera.fr

Matthieu Roy

Christine Rochange
email: christine.rochange@irit.fr

Madeleine Faugère

Sylvain Girbal

Daniel Gracia Pérez

Distributed run-time WCET controller for concurrent critical tasks in mixed-critical systems

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

INTRODUCTION

Mixed-critical systems [START_REF] Vestal | Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[END_REF] consist in integrating applications with different properties and requirements into a common platform. The platform should provide the required level of dependability, in particular of safety, for each application. The safety level is given by the criticality level of an application, which depends on the consequences on the system if the application doesn't meet its timing constraints. For instance, the criticality level of an avionic application is given by the Design Assurance Level (DAL) model [START_REF]Aerospace recommended practices 4754adevelopment of civil aircraft and systems[END_REF].

A high criticality application, e.g. an application of A, B or C level of DAL, requires predictability to be provided by the platform, i.e. the ability to compute a safe estimation of the Worst-Case Execution Time (WCET) [START_REF] Wilhelm | The worst-case execution-time problem -overview of methods and survey of tools[END_REF]. The current platforms consist of multi/many-core COTS systems, which are hard, if not impossible, to be predictable [START_REF] Wilhelm | Embedded systems: Many cores -many problems[END_REF].

The reason is the complexity of the system architecture, the enhanced mechanisms used to improve the system performance and the lack of the systems' documentation. WCET estimations exist which upper bound the effects of the possible interferences on the system shared resources by assuming full congestion. In this way they are able to provide safe estimations which are required to guarantee real-time response. However, with these techniques a dramatic difference occurs in WCETs of an application estimated 1) when it is executed alone on one core (isolated execution, no interferences) and 2) when other applications are concurrently executed on the remaining cores (maximum load, interferences). This difference may lead to the system unschedulability in case:

WCET iso < DC < WCETmax
where WCET iso is the WCET of a high criticality application τC in isolated execution, DC is its deadline and WCETmax is its WCET in maximum load.

Run-time control for a unique critical task

We have addressed this problem by proposing a safe approach which increases the utilization of the system resources in [START_REF] Kritikakou | Run-time control to increase task parallelism in mixed-critical systems[END_REF]. The model of our system consisted of n + 1 independent synchronous tasks T = {τC, τ1, . . . , τn} where τC is a periodic task of high criticality level (DAL A, B or C) with period TC and deadline DC ; τi are tasks of low criticality level (DAL D or E); one task corresponds to one application.

Our system initially executes all tasks regardless their criticality level. The critical task is modeled by a set of Extended Control Flow Graphs (ECFGs), i.e. control flow graphs with observation points where the run-time control is executed. The run-time control regularly checks if the interferences of the low criticality tasks can be tolerated by verifying our safety condition (Eq. 1). When the condition does not hold, the low criticality tasks are immediately suspended to eliminate congestion over the shared resources and to guarantee the critical task's timing constraints. When the task terminates, the low criticality tasks are resumed.

RWCET iso (x) + Wmax + tSW ≤ DC -ET(x) [START_REF] Anderson | Multicore operating-system support for mixed criticality[END_REF] where RWCET iso (x) is the remaining WCET of τC in isolated execution from the observation point x until the end, Wmax is the maximum WCET until the next point, tSW is the overhead of suspending the low criticality tasks and ET(x) is the monitored execution time of τC until point x.

Run-time control for several critical tasks

The contribution of this work is twofold. Firstly, we have extended our approach to several high criticality tasks concurrently executed on different cores with different deadlines, periods and offsets. Secondly, we have implemented our approach as a software controller in a real multi-core COTS system, i.e. the Texas Instrument TMS320C6678 (or TMS in short) [START_REF] Instruments | TMS320c6678 Multicore fixed and floating-point digital signal processor[END_REF]. Our objective is the improvement of the system resource utilization by increasing the concurrent execution of the low criticality tasks.

The system model now consists of p+n independent tasks T = {τC 1 , . . . , τC p , τ1, . . . , τn} where τC j are periodic tasks of high criticality level with period TC j , deadline DC j , offset OC j ; τi are tasks of low criticality level. A static partitioned scheduling has been applied in which each critical task (which can consists of smaller critical tasks with precedence constraints) is executed on one core and the remaining cores execute the low criticality tasks. In this extension, WCET iso is the WCET of τC where all the high criticality applications may execute in parallel.

Our methodology applies a design-time part and a runtime part, as shown in Fig. 1. The design-time analysis inserts the proposed run-time controller to the critical tasks. As we focus on implementing our approach on TMS as a software controller, our methodology instruments the critical tasks by refining the observation points of the initial ECFGs in [START_REF] Kritikakou | Run-time control to increase task parallelism in mixed-critical systems[END_REF] with the proposed software control mechanism. The set of critical tasks is now modeled by a set of Instrumented Control Flow Graphs (ICFGs), i.e. control flow graphs enhanced with the software control mechanism. The result is the instrumented source codes of the critical tasks. For the low criticality tasks, no instrumentation is required. Then, at design-time a Timing and Structure Information (TSI) analysis takes place which pre-computes the structure and the timing information required by the run-time control mechanism using the ICFGs per critical task.

At run-time, each critical task executes its own run-time control mechanism, which monitors the ongoing execution time, dynamically computes the remaining WCET of the task in isolated execution and checks its safety condition to locally decide if the low criticality tasks should be suspended to guarantee that its deadline is met. However, the critical tasks are not responsible for the execution of the low criticality tasks suspension. They send a request to a new entity, the master, which has a global view. The master is in charge of collecting the requests of the critical tasks, suspending and restarting the low criticality tasks. The master suspends the low criticality tasks when at least one critical task sends the request for isolated execution, when the safety condition is not satisfied. During execution, the master updates the number of active requests and it restarts the low criticality tasks when all requesters have been executed. Fig. 2 describes the run-time behavior of our control mechanism through an example with two critical tasks running in parallel. In the first scenario, the safety condition of the critical task τC 2 is violated and thus it sends a request for isolated execution to the master. The master upon receiving this request sets the number of active requests to 1 and suspends the low criticality tasks. Then, the requester (task τC 2 ) informs the master that its execution is finished. As the critical task τC 1 has not yet requested isolated execution, no risk exists for the deadline of τC 1 . The master resumes the low criticality tasks (active requests=0). In a later scenario, the critical task τC 1 has also requested isolated execution after the request of τC 2 . The master restarts the low criticality tasks when both tasks have finished. The master is not assigned on the same core with a critical task, as this option will increase the WCET of the critical task due to the received requests. Hence, the master is assigned at a core that executes low criticality tasks.

The remaining of the paper is organized as follows: Section 2 presents the design-time analysis and Section 3 describes the software run-time control mechanism and the master entity. Section 4 presents the software implementation on TMS and several experimental results to evaluate our approach. Section 5 presents the related work on mixedcritical systems. Section 6 concludes this study.

DESIGN-TIME ANALYSIS

This section describes the design-time analysis which consists of the instrumentation of the critical tasks described at Section 2.1 and the timing and structure analysis to extract the pre-computed information described at Section 2.2.1. The proposed methodology considers two scenarios for the tasks that are executed on the platform. Definition 1 (Execution scenarios). The execution scenarios are 1. Isolated execution (iso), where p critical tasks are executed on the platform, 2. Maximum load (max), where p critical and n low criticality tasks are concurrently executed on the platform.

Critical tasks instrumentation

For the instrumentation of the critical tasks, we use as basis the graph grammar presented in [START_REF] Kritikakou | Run-time control to increase task parallelism in mixed-critical systems[END_REF] and we extended it to describe the proposed software instrumentation of the critical tasks. The Instrumented Control Flow Graph (ICFG) is derived by replacing the theoretical observation points in the Extended control Flow Graph (ECFGs) [START_REF] Kritikakou | Run-time control to increase task parallelism in mixed-critical systems[END_REF] by the software run-time control mechanism. Definition 4 (Software run-time control). The software run-time control mechanism (Fig. 3) for the critical tasks consists of: 1. a condition CRT which semantics is:

• CRT = true ⇐⇒ maximum load scenario,

• CRT = true ⇐⇒ isolated execution, • CRT = true at observation point start. 2. if CRT is true at vi ∈ V \ {OUT , IN }, a function call
occurs to the decision, FD, which consists of the:

• node NC to monitor the current execution time of the critical task and compute the remaining WCET in isolated execution, RWCET iso (x), • safety condition CD to decide if the low criticality tasks should be suspended. If no suspension occurs, the runtime control returns to the critical task execution, • node NS to send a request for isolated execution and to turn off the run-time control mechanism by setting CRT = false, if decided.

C RT F D FD IND N C C D N S OU TD (a) C RT N E (b)
F0 IN0 N 0,a n 0,a F 1 f 0,1 N 0,b n 0,b OU T0 F1 IN1 N 1,a n 1,a C c N 1,b n 1,b OU T1 (a)

Timing and Structure Analysis

Structure information

During the execution of any critical task, an observation point may be visited several times due to the loops and the function calls. Hence, we need the structure information of ICFG in order to distinguish between different visits of the same point during run-time execution, i.e. the nested level, the head point and the type of an observation point as defined in [START_REF] Kritikakou | Run-time control to increase task parallelism in mixed-critical systems[END_REF]. In summary:

• The nested level is: a) 0 for the start point, b) 1 for the sequential points between the IN and the OU T of an ICFG and c) increased by 1 when we are entering a loop.

• The head points show when a function has been called

and where a loop exists in each ICFG. The head points To support the run-time control mechanism, we store the structure information in memory. Table 1 provides the structure information for the observation points of Fig. 4(b). The information about the head points is propagated to the timing analysis to compute the partial remaining WCETs.

Table 1: Structure & timing information of Fig. 4(b) . Observation point x level (x) type (x) head (x) d(x) w(x) Initialization start 0 - - - - F0 n0,a 1 - start dstart-n 0,a - f0,1 1 F ENTRY start d start-f 0,1 - n 0,b 1 F EXIT start dstart-n 0,b - F1 Fig. 4(a) n1,a 1 - f0,1 d f 0,1 -n 1,a - c 1 - f0,1 d f 0,1 -c wc n 1,b 2 - c dc-n 1

Timing information

As the computation of the remaining WCET at each observation point at run-time would generate prohibitive overhead to the critical task, we pre-compute at design-time partial WCETs by processing the ICFGs. This timing information is used at run-time to reduce the computation overhead. Compared to the theoretical results of [START_REF] Kritikakou | Run-time control to increase task parallelism in mixed-critical systems[END_REF], the computation of the timing information is extended and adapted to take into account the cost of the instrumentation of the critical tasks and the fact that more than one core runs critical tasks. Our WCET analysis is based on computing the remaining WCET from one observation point x until the end of a critical task τC , RWCETy(x), where y ∈ {iso,max}.

Isolated execution.

When a critical task has requested for isolated execution, p critical tasks are executed on the platform. The run-time control mechanism of the requester is not executed, as it has already requested isolated execution. Hence, the FD is not called, whereas the FE is called at the end of the critical task (Def. 3). For computing RWCET iso (x), we only consider the feasible paths for the run-time control, that is when CRT = false and CRT = true. Using the remaining WCET analysis of an observation point x, we can compute remaining WCETs between an observation point x and its head point head(x) for each critical task.

Definition 5. d head(x)-x is the maximum time from head(x) to x. d head(x)-x = RWCET iso (head(x)) -RWCET iso (x)
Definition 6. w head(x) is the time between any two consecutive iterations j and j + 1 of the head(x), when head(x) is the condition of a loop. wc = RWCET iso (c, j) -RWCET iso (c, j + 1), ∀j ≤ n To support the run-time RWCET iso (x) computation, we store in memory d head(x)-x and the wx for each point x, as depicted in Table 1.

Maximum load.

To guarantee that the critical tasks deadlines are always met, we must ensure that for each critical task, enough time is available to decide the suspension of the low criticality tasks at the next observation point. Hence, we apply our remaining WCET analysis to compute the Wmax between any two consecutive observation points x, x ′ in each critical task in the maximum load scenario. Hence, the FD is called at each observation point, whereas the FE is not called (Def. 3).

Wmax = max x,x ′ (RWCETmax(x) -RWCETmax(x ′ ))

RUN-TIME

Global overview

At run-time, each critical task monitors its own execution and decides based on its local timing computation whether it requires the suspension of the low criticality tasks. In this case, it sends a request to the master. The local decisions per critical task are centralized and processed by the master which sends suspend or restart events to the low criticality tasks based on the received requests from the critical tasks.

When a critical task starts a new instance, it always assumes that the system is in maximum load, independently from the actual system status. This scheme is required for two reasons: firstly, when the critical tasks start their execution, they are not aware of the system status, which depends on the active requests made by the other critical tasks. This assumption guarantees that the overhead of our control mechanism is bounded, since a given critical task will generate at most two requests per instance. In a given time interval, the maximum number of requests depends on the periods and offsets of all critical tasks. Secondly, the remaining WCET of a critical task is computed when the run-time control is enabled, i.e. in the maximum load. Hence, when a critical task instance starts while the low critical tasks have been suspended, it still needs to execute its run-time monitoring control: in case the low criticality tasks are restarted during its execution, it must be able to compute its safety condition to guarantee a timely execution.

The master is responsible for serving requests and controls the suspension and the restart of the low criticality tasks. As our control mechanism is based on requests between 1) the cores that run the control mechanism through critical task instrumentation and the master, and 2) the master and the cores that run low criticality tasks, these requests are implemented by using the interrupts of the system and by developing the corresponding interrupt handling routines. The implementation of the the interrupts highly depends on the target platform. In this section we algorithmically describe the run-time control, whereas Section 4.1 presents the implementation of interrupts on our final platform.

Critical tasks

Monitoring ongoing execution

The monitoring of the ongoing execution highly depends on the target platform. During the implementation on the final system a set of low level functions are developed that access the timing control registers of the target platform which provide access to the clock of the core, as described in detail in Section 4.1.1.

Computation of RWCET iso (x)

The algorithm for the computation in adynamic way of the RWCET iso (x) of a critical task has been presented and its correctness has been proved in [START_REF] Kritikakou | Run-time control to increase task parallelism in mixed-critical systems[END_REF]. The code is depicted in Alg. 1. Briefly, when the ICFG is traversed in a forward direction, the remaining WCET is given by the remaining WCET of the head point c minus the time from the head point to the observation point x, d[x] = dc-x. When the ICFG is traversed in a backward direction, the remaining WCET of this level is reduced by w[x] = wc. An example of computing the RWCET iso (x) for Fig. 4(b) is given in Table 2.

ALGORITHM 1: Computation of RWCET iso (x) Pre-computed data: level, w, d, type Input: x Data: o level = 0, ll = level[x], last point[0]=start, R[0]=WCET iso , offset = 0 Output: RWCET iso (x) = R[ll] if (type[x] ==F EXIT or F ENEX) then /* condition 1 */ o level-=1 offset -= level[x] ll = offset + level[x] if o level < ll then /* condition 2 */ R[ll] = R[ll -1] -d[x] else if (last point[ll] == x) then /* condition 3 */ R[ll] = R[ll] -w[x] else R[ll] = R[ll -1] -d[x] last point[ll]= x o level=ll if (level[x] ==F ENTRY or F ENEX) then /* condition 4 */ offset += level[x]

Safety condition

Per core that runs a critical task, at each observation point the control checks whether the low criticality tasks should be suspended through the safety condition given by Eq. 1. That is, for all tasks τC i , at point x is:

RWCET iso (τC i , x) + Wmax + tSW ≤ DC i -ET(τC i , x) (2)
The suspension of the low criticality tasks occurs by the master when the safety condition of a critical task is violated. The overhead due to suspending and restarting the tasks, tSW, includes the time to send the request to the master and the time to suspend the tasks. Hence, the theorem 1 proved in [START_REF] Kritikakou | Run-time control to increase task parallelism in mixed-critical systems[END_REF] also holds for the proposed distributed approach with several critical tasks.

Table 2: RWCET iso for the ICFG of Fig. 4(b). Theorem 1. If ∀i, WCET iso (τC i ) ≤ DC i , then for any execution with the proposed run-time control, all τC i respect their deadline.

Obs. condition Offset RWCET iso (x) Last Obs. Point 1 2 3 4 point[ll] level start x x x x 0 R[0] = RWCET iso LP[0]=0 0 n0,a 0 1 x 0 0 R[1] = R[0] -0 LP[1]=n0,a 1 f0,1 0 0 0 1 0 R[1] = R[0] -d start-f 0,1 LP[1]=f0,1 1 n1,a 0 1 x 0 1 R[2] = R[1] -d f 0,1 -n 1,a LP[2]=n1,a 2 c 0 0 0 0 1 R[2] = R[1] -d f 0,1 -c LP[2]=c 2 n 1,b 0 1 x 0 1 R[3] = R[2] -dc-n 1,b LP[3]=n 1,b 3 c 0 0 1 0 1 R[2] = R[2] -wc LP[2]=c 2 n 1,b 0 1 x 0 1 R[3] = R[2] -dc-n 1,b LP[3]=n 1,b 3 c 0 0 1 0 1 R[2] = R[2] -wc LP[2]=c 2 n 0,b 1 0 0 0 0 R[1] = R[0] -dstart-n 0,b LP[1]=n 0,

Low criticality tasks suspension

The node NS of FD sends a request to the master to suspend the low criticality tasks and stops its own control mechanism by setting the CRT = false. Then, the master suspends the tasks by sending a set of interrupts to the corresponding cores. The implementation of the request is described in detail in Section 4.1.2.

End detection

The function NE consists of sending a request to the master which notifies that the execution of the requester for isolated execution has finished. Then, the master decides over the restarting or not of the low criticality tasks. Similar to the low criticality task suspension, the implementation of the request depends on the target platform.

Master

The master accepts a set of requests from the NS and the NE of a critical task and sends a set of interrupts to the cores that run the low criticality tasks. We developed the corresponding Interrupt Handling Routines (IHR) for the master and for the cores that run the low criticality tasks, which serve these requests and the interrupts.

The master consists of two interrupt handling routines to serve the requests from the critical tasks, as shown in Alg. 2: 1. IHRS is the interrupt handling routine called when the master receives a request from a critical task for the low criticality tasks' suspension. The master suspends the low criticality tasks when at least the safety condition of one critical core does not hold. Then:

• it increases the number of active requests,

• if it is the first received request, it sends the first interrupt to the cores that run low criticality tasks to suspend them. 2. IHRE is the interrupt handling routine called when the master receives a request that notifies about the termination of the requester for isolated execution. Then:

• it decreases the number of active requests,

• if it is the last requester for isolated execution, it sends the second interrupt to the cores that run low criticality tasks to restart them. Each core that runs low criticality tasks has an interrupt handling routine IHRLC to serve the master interrupt:

• if it is the first interrupt received, an active polling mechanism takes place inside the interrupt handling routine, • when the core receives a second interrupt, the polling is terminated and the IHRLC finishes. Then, the low criticality task continues its execution. We have implemented the proposed methodology in a real multi-core system, i.e. the TMS, to evaluate the behavior of our methodology. The implementation of two main mechanisms highly depends on the target platform: a) the time monitoring of the ongoing execution and b) the suspension/resuming of the low criticality tasks. These two mechanisms are described in Section 4.1. Section 4.2 presents the results under several experimental setups.

EVALUATION RESULTS

System Implementation

We are targeting a real multi-core COTS platform, i.e. the TMS320C6678 chip of Texas Instrument [START_REF] Instruments | TMS320c6678 Multicore fixed and floating-point digital signal processor[END_REF]. The platform is composed of 8 TMS320C66x DSP processors clocked at 1 GHz, which can issue up to 8 instructions in one clock cycle. Each core contains 32 KB level 1 program memory (L1P), 32 KB data memory (L1D), and 512 KB level 2 memory (L2) that may contain instructions and data, which can be configured as cache, SRAM or a hybrid. The level 3 memory (L3) of 4 MB on-chip SRAM and the external DDR3 of 512 MB memory is shared among the cores. The cores and the hardware modules are connected via the TeraNet onchip network. The overview of the system is depicted in Fig. 5. We appropriately configure the TMS and implement the low-level functions to support the timing monitoring and the suspension/restart of the low criticality tasks. The overhead of our controller is: 70 cycles for the time monitoring, 200 cycles for sending an event and 501 cycles for computing the RWCET iso (x) and the safety condition.

Time monitoring

We reuse the bare-metal library of [START_REF] Durrieu | Predictable flight management system implementation on a multicore processor[END_REF] that provides a set of timing functions to read the current clock by accessing the control registers TCSL and TCSH of the local core clock, which runs at the core's frequency. As the system should start the execution when all tasks have been loaded to the cores, this library also provides a synchronization scheme to ensure that cores start at the same time. When an observation point is reached, the run-time control uses the functions to read the real execution time of the system.

Suspension/Restart of low criticality tasks

The suspension and the resume of the low criticality tasks is implemented using the event and interrupt mechanisms of the TMS. The bare-metal library is extended with a set of functions that (1) configure the events and the interrupts of the TMS, (2) allow the use of the events by providing software setting, clearing and monitoring mechanisms for the events, (3) suspend or resume the low criticality tasks.

The TMS provides chip level events and core level events. A chip level event is created by the source core by setting the corresponding bit of the event to its Event Flag Register. Then, the Chip-level Interrupt Controller (CIC) is configured to generate host interrupts that act as core event inputs to the DSP interrupt controller of the destination core. The DSP interrupt controller allows up to 124 core events to be routed to the DSP interrupt/exception inputs. Each DSP can receive 12 maskable/configurable interrupts, 1 maskable exception, and 1 unmaskable interrupt/exception. When the DSP interrupt controller receives the core event, sets the corresponding bit to the Interrupt Flag Register of the destination core, an interrupt is generated to the core, the execution of the task is suspended and the Interrupt Handling Routine (IHR) is executed to deal with the interrupt.

In our implementation we have placed the master in the core 2, as depicted in Fig. 6, where core 0 and core 1 (gray cores) run critical tasks and the remaining cores run low criticality tasks (white cores). We have configured the TMS to map different chip level events for the synchronization between cores. Each chip level event is sent from a core to a host interrupt and then to a core level event for the corresponding DSP. The core that runs the master is configured to send a chip level event to each core that runs low criticality tasks to suspended their execution. Each core that runs a critical task sends a chip level event to the core that runs the master for the request to isolated execution and to notify that it has finished its execution. Then, we have implemented a core event configuration per DSP which maps each core event to one configurable interrupt. The master requests are handled by IHRS and IHRE and the cores with low criticality tasks by IHRLC .

In our example in Fig. 6, in case the safety condition of one of the cores does not hold (e.g. core 1), the low criticality tasks must be suspended. Core 1 sends an interrupt (black arrow 1) to core 2 through node NS to notify that suspension should immediately take place, it turns off its control mechanism and continues the execution of the critical task. When this interrupt is received at core 2, the execution of the low criticality task on core 2 is stopped and the IHRS is executed. The IHRS clears the received interrupt to be able to get the next one and increases the number of interrupts received. If it is the first interrupt received, it sends the interrupts to the remaining cores that run low criticality tasks (black arrow 2) by setting the corresponding bits to Event Flag Register of core 2. Then, it enters an active waiting mode until a new interrupt is received. The core level events are routed to the host interrupt controllers and finally to the DSP interrupt controllers through the CIC. The corresponding bit to each Interrupt Flag Register is set, the execution of the low criticality task is stopped and the IHRLC is executed to deal with the interrupt. It clears the interrupt to be able to get the next interrupt from the interrupt controller and puts itself in an active waiting mode until a new interrupt is received. In our example of Fig. 6, when the requester for isolated execution finishes (core 1), it sends an interrupt to notify core 2 (e.g. gray arrow 3). When the master in core 2 receives the interrupt, it reduces the number of active requests for isolated execution. If no other critical task has requested isolated execution, it sends the interrupts (e.g. gray arrow 4) to the cores that run low criticality tasks to notify that they can continue their execution and exits the active waiting mode. When the low criticality cores receive such an event, their IHRLC exits the waiting mode and returns to the execution.

Experiments

In our experiments we have considered two loop and data dominated critical tasks with similar execution times and deadlines, i.e gemm from Polybench suite [START_REF] Pouchet | Polybenchmarks benchmark suite[END_REF] which consists of three nested loops with main memory accesses and a set of arithmetic operations. The tasks are sharing the same main memory parts and run on core 0 and core 1. The remaining cores run a set of low criticality loop and data dominated tasks which are accessing different main memory parts. We explore the behavior of our methodology by tuning: 1. the application size of the critical task, which is given by the loop bounds and affects the arrays' size, the number of memory accesses and the execution time, 2. the number of cores that run low criticality tasks, i.e. from 1 core up to 6 cores, 3. the deadline of the critical tasks DC , i.e. from tight deadlines close to the WCET iso up to more relaxed deadlines, 4. the granularity of the software run-time control mechanism, i.e. the position of the observation points:

• coarse-grained : At the head points of level 1 (HP1),

• fine-grained : At the head points of levels 1 and 2 (HP2),

• very fine-grained : At the head points of all levels (HP3).

Design-time analysis

Although we have configured our system to be supported by static WCET analysis, no static WCET analysis tool, such as Ait or Otawa [START_REF] Wilhelm | The worst-case execution-time problem -overview of methods and survey of tools[END_REF], is available for the TMS320C6678 platform. As it is not the scope of this paper to extend the supported platforms for static analysis tools, we use a measure-based approach by using the local timer of the cores that run the critical tasks to compute the timing information of the critical tasks, i.e. the d(x), the w(x) and the Wmax for each critical task. The d(x) and the w(x) are measured when the critical tasks are the only tasks executed on the system and for each observation point of a critical task. To reduce the overhead introduced by our run-time measurements, we perform the timing measurements by considering one point per execution. For the computation of the d(x), we use the maximum time observed between the head point and the point x. For the computation of the w(x), we use the maximum time observed between any two consecutive iterations of the loop. The Wmax is measured when the critical tasks run in maximum load for each different number of low criticality tasks and for each position of observation points. The computation of the Wmax is performed by read-ing the local clock, subtracting any two subsequent observed times and using the maximum time difference.

The maximum time overhead of our run-time control for reading the local timer is 70ns, for the RWCET iso (x) computation and the safety condition is 501ns and for the request and suspension/resume of the low criticality tasks is 200ns.

Behavior of high criticality tasks

Fig. 7 compares the WCETmax in maximum load with 6 low criticality tasks (6LC) in comparison with the WCET iso depending on the application size given by the loop bounds. We observe that the difference between the WCET iso and WCETmax increases when the number of congestions to the shared resources increases.

WCET(ms)

Loop bounds

Isolated execution

Max load (6LC)

Figure 7: WCETs for several loop bounds Fig. 8 depicts the WCETmax for several numbers of low criticality tasks (2 in which case WCETmax = WCET iso up to 8 parallel tasks) for an application size equal to 32. We observe that the WCET highly depends on the number of tasks that run in parallel. The WCET difference between isolated execution and maximum load with 6 low criticality tasks has a factor of 6.28.

Number of parallel tasks WCET(ms)

Figure 8: WCET for several parallel tasks Fig. 9 illustrates the execution time of the critical tasks τC1 and τC2 for several deadlines and granularities for an application size equal to 32. We observe that the suspension of the low criticality tasks occurs:

• For the HP1 configuration: 1) relatively quickly, when the deadlines are tight (e.g. < 14.00ms). The observation points are far away one from the other, the w1 is quite large and thus the safety condition is early violated, and 2) never, when the deadline is relaxed. For instance, for deadlines > 14.00ms, the execution time of τC1 and τC2 is stable, as it has been completely executed maximum load scenario. • For the HP2 and HP3 configuration: 1) quickly but later that HP1, when the deadlines are tight, as the lower granularities allow the exploration of the task suspension in smaller steps, 2) never, when the deadline is quite large. For these smaller granularities, the deadline in which the system is always executed in maximum load has a larger value that HP1 configuration, i.e. 30.00ms for HP2 and 45.00ms for HP3, and 3) in between otherwise.

Gain on resources utilization

We explore the gains of our method by tuning (1) the deadline of the critical task and the (2) granularity of the observation points of our software controller. Fig. 10 illustrates the execution time of the low criticality task τ1 for several deadlines and granularities for an application size equal to 32. We observe that the more time the critical task spends in the maximum load, the longer are the execution times of the low criticality tasks. To explore the gain of our methodology, we consider the following notion: Definition 7 (Relative gain). Let t denote the execution time of the low criticality task with our methodology and tiso the execution time in isolation mode. The relative gain obtained by the methodology is:

(ttiso)/tiso 0 0.5 Fig. 11(a) presents the behavior of the relative gain of our approach with the HP1, HP2 and HP3 configuration with respect to the different deadlines for an application size equal to 32. From the experiments, we observe that our approach achieves significant relative gains:

• For the more relaxed deadlines (still below the RWCETmax i.e. 18.50ms), e.g. in 15.5ms, we have the highest gain of 2.9885 or 298.85 % for HP1. The HP1 configuration provides the largest gain. It calls the run-time controller in larger steps, and the slack time, i.e. the time between the critical task's end and the deadline, is quite short. • For larger deadlines, we still have a gain which is decreasing when the deadline is further relaxed. • For tight deadlines, e.g. <13.00ms we achieve a relative gain of 11.27% for the fine grained and a relative gain of 4.93% for very fine grained granularities. By increasing the application size to 128, we observe that the gains of the lower granularities are increased. Fig. 11(b) presents the behavior of the relative gain of our approach with the HP1, HP2 and HP3 configuration with respect to the different deadlines. We observe that:

• For tight deadlines (e.g. <660ms), the HP1 configuration has a small gain from 2.5%-23.89%, as the w1 is significantly increased and the critical task requests for isolated execution at the first observation point. However, the smaller granularities achieve significant gains because the observation points are placed closer. The HP2 configuration achieves a relative gain of 479% in 628.6ms, whereas for even tighter deadlines (e.g. 628.2ms), the HP3 configuration achieves a gain of 556%. • For more relaxed deadlines (e.g. >660ms and <2000ms), the gain of the HP1 configuration is increased up to 317%, as the time slack is increased and no need exists to explore the suspension of the low criticality tasks in smaller steps. The gains of the HP2 and HP3 remain stable and equal to 78.5% and 37.5%, respectively, as the gain due to the time slack increase balances the loss of the controller overhead. • For larger deadlines (e.g. >2000ms), we still have a gain which is decreasing while the deadline is further relaxed.

RELATED WORK

This section briefly presents the different approaches on the mixed-critical systems, whereas a detailed survey on the mixed-criticality research up to now is available in [START_REF] Burns | Mixed criticality systems -a review[END_REF].

Task scheduling

The majority of mixed-criticality scheduling work has been mainly addressed for uni-processor platforms (e.g. [START_REF] Vestal | Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[END_REF][START_REF] Baruah | Schedulability analysis of sporadic tasks with multiple criticality specifications[END_REF][START_REF] Baruah | Towards the design of certifiable mixed-criticality systems[END_REF][START_REF] Burns | Towards a more practical model for mixed criticality systems[END_REF]), which is not directly applicable in multicore platforms. In the latter, shared resources exist and time compositionality cannot be ensured [START_REF] Cullmann | Predictability considerations in the design of multi-core embedded systems[END_REF], as the WCET analysis cannot be applied independently per task.

In multicore platforms, several approaches exist that assume that the task set is schedulable at least at the high criticality level. For instance, in [START_REF] Brandenburg | Integrating hard/soft real-time tasks and best-effort jobs on multiprocessors[END_REF], both hard real-time and soft real-time tasks are scheduled using an Earliest Deadline First for Hard real-time, Soft real-time and Best effort tasks (EDF-HSB) approach with the assumption that the hard real-time tasks are statically schedulable. When time slack occurs at run-time, it is reallocated to non hard real-time tasks. Another example is the two level mixedcriticality scheduling for multicore platforms proposed in [START_REF] Anderson | Multicore operating-system support for mixed criticality[END_REF] and extended in [START_REF] Mollison | Mixed-criticality real-time scheduling for multicore systems[END_REF], where the tasks are scheduled based on the WCET of their criticality level and the time slack is reallocated to lower criticality levels. The tasks of different criticality levels are scheduled with different appropriate scheduling approaches. The tasks with the lowest criticality level are allowed to be executed when no higher criticality task is running, i.e. in the critical tasks are executed in isolation. In addition, several mixed-critical scheduling policies have been implemented in the LITMUS RT framework [START_REF] Herman | Rtos support for multicore mixed-criticality systems[END_REF].

Less pessimistic approaches, such as [START_REF] Li | Global mixed-criticality scheduling on multiprocessors[END_REF][START_REF] Baruah | Mixed-criticality scheduling on multiprocessors[END_REF][START_REF] Pathan | Schedulability analysis of mixed-criticality systems on multiprocessors[END_REF], use several WCETs per task during task scheduling. Initially, all tasks are assigned their low criticality WCET, which is a less pessimistic bound on WCET given by designers. This WCET derives from a set of test cases [START_REF] Burns | Timing faults and mixed criticality systems[END_REF] and is the maximum execution time observed during execution of the system. The proposed algorithms in [START_REF] Li | Global mixed-criticality scheduling on multiprocessors[END_REF][START_REF] Baruah | Mixed-criticality scheduling on multiprocessors[END_REF] describe a generalization of the preemptive uniprocessor algorithm EDF with Virtual Deadlines (EDF-VD) to multiprocessor platforms. At run-time, they observe if the tasks have signaled termination at their low criticality WCET. The check for the switching to higher criticality WCET occurs once in a pre-defined position based on the low criticality WCET. If no signal termination exists by that time, the criticality level of the tasks is increased and the tasks with lower criticality levels are dropped. This occurs because a scenario of higher criticality is now considered and the completion of jobs of lower criticality becomes irrelevant for the new scenario [START_REF] Baruah | Scheduling real-time mixed-criticality jobs[END_REF]. Further extensions of similar methods are presented in [START_REF] Fleming | Extending mixed criticality scheduling[END_REF] which avoid the abandoning of the low criticality tasks during high criticality mode and return to the low criticality mode after the high criticality mode has been terminated. In [START_REF] Pathan | Schedulability analysis of mixed-criticality systems on multiprocessors[END_REF] a Mixed-criticality Scheduling on Multiprocessor (MSM) algorithm is proposed which uses a global fixed priority based approach. When the switching of criticality level occurs, the low criticality tasks are dropped. The approach presented in [START_REF] Baruah | Certification-cognizant time-triggered scheduling of mixed-criticality systems[END_REF] considers mixed-critical systems and time-triggered paradigm where WCET estimates are allowed to overrun. A run-time monitor is in charge of detecting these overruns and switching on a schedule selected from a set of pre-computed schedules.

Our approach is orthogonal to the aforementioned approaches: we consider two different types of WCETs, which are not based on their reliability like existing methods but on how the critical task is executed on the platform, i.e. in maximum load or in isolated execution. Our WCET estimations in both scenarios are safe. Our method is applicable in cases where the system is considered as unschedulable, e.g. when the values of low and high criticality WCET are estimated above the deadline of the critical task. We also perform a switch which suspends the low criticality tasks in risk of a local overrun of the critical task. However, the time instants where the switching can occur and the guarantee of meeting the deadline of the critical task are formally defined and proved. Then, the switching is decided at run-time by exploring the ongoing execution of the critical task. A brief description of the general idea is detailed in [START_REF] Kritikakou | Monitoring on-line timing information to support mixed-critical workloads[END_REF] and the formal description and the proof in [START_REF] Kritikakou | Run-time control to increase task parallelism in mixed-critical systems[END_REF]. In this paper, we extended our approach by increasing the number of critical tasks which have now different deadlines, periods and offsets and the number of cores where the critical tasks run, by refining the observation points to insert instrumentation and by implementing our controller in a real multicore platform.

Run-time control implementation

Several approaches propose resources reallocation based on information derived from monitoring their utilization, e.g. the memory accesses. For instance, in [START_REF] Nowotsch | Multi-core interference-sensitive wcet analysis leveraging runtime resource capacity enforcement[END_REF] interferencesensitive WCETs are computed based on a preliminary analysis of the resource usage of tasks. The shared resources are off-line partitioned among tasks. A run-time monitoring device observes the resource usage of each task and suspends the task that overtakes the allocated capacity. In [START_REF] Nowotsch | Quality of service capabilities for hard real-time applications on multi-core processors[END_REF] the approach is extended by allowing safe dynamic changes in the resource partitioning, when resources are underutilized. In [START_REF] Yun | Memguard: Memory bandwidth reservation system for efficient performance isolation in multi-core platforms[END_REF] an approach has been developed to reserve memory accesses for critical tasks. A run-time controller has been implemented which regulates the accesses to the shared memory and ensures temporal isolation among tasks. An off-line profiling technique has been proposed in [START_REF] Mancuso | Real-time cache management framework for multi-core architectures[END_REF] which finds the most frequently accessed memory pages in a task. Then, this information is used to modify the variables' position in the shared caches in order to reduce the interferences. Another hardware approach is described in [START_REF] Daniel Lo | Slack-aware opportunistic monitoring for real-time systems[END_REF] where the monitoring is only performed when enough slack time exists which guarantees that the monitoring does not impact the meeting of the real-time constraints of the tasks. If the slack is insufficient, a dropping operation is executed to minimize the monitoring overhead.

In contrast, our approach is not based on monitoring the accesses to the shared resources, but on monitoring the ongoing execution time of the critical tasks. In case the time to reach an observation point is too high, this implicitly means that the low criticality tasks have generated many contentions to the shared resources. If tolerating more interferences could cause a dangerous slow down of the critical task, the switching to isolated execution is mandatory.

CONCLUSION & FUTURE WORK

In this work, we present a methodology which improves the resources utilization by increasing the task parallelism, while guaranteeing the real-time response of the critical tasks. These tasks are described by a set of ICFGs and the structure and time analysis is applied to compute the required data for the run-time part. At run-time, a low-overhead controller per critical task computes the remaining WCET and decides the switching to isolated execution, which is executed by the master entity. We have implemented our approach on a multi-core COTS and we observed gains up to 556% for our case study.

As future directions, we will apply our approach to other types of critical tasks to obtain a global view of the gains of our method. The next major challenge to solve is the development of a methodology to decide the position of the observation points over the ICFGs. We would like to explore the effect of the different scheduling techniques on our approach. We would like also to explore the case where in isolated execution we allow some low criticality tasks to run on other cores even if some active requests exist. In addition, we consider the extension to several criticality levels by adapting the computation of the partial RWCETs and the definition of the isolated execution by exploring several cases regarding the parallel execution of tasks during isolated execution. We believe that the combination of our approach with time and partitioning methods will further increase the task parallelization during isolated execution.

Figure 1 :

 1 Figure 1: Overview of the proposed approach

Figure 2 :

 2 Figure 2: Run-time behavior

Definition 2 (

 2 Critical task τC ). A critical task τC is a set of functions S = {F0, F1, ..., Fn}, with F0 the main function. Each function is represented by an Extended CFG (ECFG). Definition 3 (ECFG). An extended control flow graph (ECFG) is a control flow graph extended by adding observation points. An observation point is a position where the run-time control is executed. The ECFG of function F is a directed graph G = (V, E), consisting of: 1. A finite set of nodes V composed of 5 disjoint sub-sets V = N ∪ C ∪ F ∪ {IN } ∪ {OU T } where, • N ∈ N represents a binary instruction or a block of binary instructions, • C ∈ C represents the block of binary instructions of a condition statement, • Fi ∈ F represents the binary instructions of calling a function Fi and links the node with the ECFG of the function Fi, • IN is the input node, • OU T is the output node. • every node v ∈ V \ {OUT , IN } has one unique input observation point before the execution of the first binary instruction (the observation point is represented by a lowercase symbol); • start is the observation point before starting the execution. 2. a finite set of edges E ⊆ V × V representing the control flow between nodes.

Figure 3 :

 3 Figure 3: Software control mechanism a) decision and b) end detection

Figure 4 :

 4 Figure 4: a) ECFGs and b) ICFG for S = {F0, F1}

  ,b are: a) the start point, for the points of level 1 of the main function F0, b) the function caller, for the points of level 1 of the remaining functions and c) the condition of the loop, for the points that are inside a loop. • The type determines: a) the function entry, i.e. the function caller, and b) the function exit, i.e. the observation point just after the return from a function.

Figure 5 :

 5 Figure 5: Overview of TMS platform.

Figure 6 :

 6 Figure 6: Suspend/restart of low criticality tasks

Figure 9 :Figure 10 :

 910 Figure 9: Exec.time of τC1 & τC2 for several deadlines

Figure 11 :

 11 Figure 11: Gain for several deadlines with application size a) 32 and b) 128

 [START_REF] Anderson | Multicore operating-system support for mixed criticality[END_REF]The research leading to these results has received funding from the TORRENTS cluster supported by the RTRA STAE and the European FP7-ICT project DREAMS under reference n • 610640.