Angeliki Kritikakou

Olivier Baldellon

Claire Pagetti

Christine Rochange

Matthieu Roy

Run-time Control to Increase Task Parallelism in Mixed-Critical Systems

come   L'archive ouverte pluridisciplinaire

Let us consider n + 1 independent synchronous tasks T = {τ C , τ 1 , . . . , τ n } where τ C is a periodic task of high criticality level (DAL A, B or C), period T C and deadline D C ; τ i are tasks of low criticality level (DAL D or E). A partitioned scheduling is applied where each task is executed on a different core. Two scenarios for the WCET computation of τ C are considered: 1) maximum load (max): all tasks run in parallel, and 2) isolation (iso): only τ C runs on the system. In max scenario, we assume that due to the resource sharing, the WCET of τ C is above the deadline, i.e. WCET max > D C , as depicted in Fig. 1(a). In this case, the hard real-time constraints cannot be met. Existing mixed-critical scheduling approaches, such as [START_REF] Anderson | Multicore operating-system support for mixed criticality[END_REF], [START_REF] Mollison | Mixed-criticality real-time scheduling for multicore systems[END_REF], [START_REF] Li | Global mixed-criticality scheduling on multiprocessors[END_REF], assume that the task set is schedulable at least in the highest criticality level, and thus are not directly applicable. Then, a safe solution is to execute τ C in isolation. When the critical task terminates and if time slack exists, the low criticality tasks are executed. In this case, no conflict occurs with the low criticality tasks. Hence, the WCET is significantly lower and the critical task respects its deadline, i.e. WCET iso ≤ D C , as shown in Fig. 1

(b).

Our goal is to increase the task parallelism and to reduce the over-provisioning of resources by combining the benefits and discarding the drawbacks of the previous cases. To achieve that, the low criticality tasks are allowed to run in parallel with the critical task, as long as it is safe. At run-time, if the interferences may lead to a deadline miss of τ C , the low criticality tasks are suspended until the termination of τ C . If time slack exists, the low criticality tasks are resumed. In this way, the critical task is guaranteed to meet its deadline, whereas the low criticality tasks run in parallel improving the resources utilization, as shown in Fig. 1(c).

C. Proposed methodology and contributions

This optimistic mixed-critical schedule can be achieved using an appropriate run-time control mechanism, as proposed by our methodology. We introduce a set of observation points to enable the run-time (online) monitoring of the timing behavior of the critical task and the control of task set scenarios. At each observation point, a safety condition is applied to check whether it is still safe to continue the execution of τ C in the maximum load scenario. The safety condition uses the remaining WCET of the critical task in isolation scenario, which is run-time computed by our low-overhead algorithm. If the safety condition evaluates that a risk exists of overloading the system and, thus, the critical task runs too slow, a backup process is applied to guarantee the real-time response of τ C : the low criticality tasks are suspended and τ C runs in isolation. When the critical task finishes its execution and if time remains until the next release of τ C , the low criticality tasks are resumed. We prove the correctness of the proposed safety condition and the low-overhead run-time algorithm for computing the remaining WCET.

As the computation of the remaining WCET is time consuming, it cannot be performed at run-time. Hence, we propose a run-time algorithm based on pre-computed data which reflect the program structure (static analysis). Then, the run-time computation involves only basic arithmetic and reflects the actual progress of the critical task execution. To achieve this goal, during the design-time (offline) analysis, the critical task is represented by a set of Extended Control Flow Graphs (ECFGs) with observation points. We propose a graph grammar to formally describe the set of ECFGs under study and to prove the correctness of our run-time computation algorithm. Based on the obtained ECFGs, a safe WCET analysis is applied for the pre-computation of several partial remaining WCETs used by the run-time control.

!"#$%&' ()*+'' ,)-%(+' ()*+' !"#$% &'&()*#+% !"#$% !"&'()$*% + , % + -% + . % + / % &$&"*0%
,-'.$-+.'/%&'0% "-'$+-(%1,2"3% 4)4$#,% 14-5$!&+#%6% 7&+0!&+#3%

./"#0' "#1)%/$.)#' 2+,"0#3./+'$#$4&,",' 5-#3./+'()#6%)4'

Fig. 2. Overall methodology

The proposed methodology consists of the design-time analysis to pre-compute the required data and the task scenario control applied at run-time, as shown in Fig. 2. A brief description of the general idea is detailed in [START_REF] Kritikakou | Monitoring on-line timing information to support mixedcritical workloads[END_REF], whereas in this paper, we focus on the design, the formal description and the proof of the proposed methodology. We also give evaluation results based on simulations. The proposed run-time control can be implemented in the target system as a software or as a hardware component, which is our future work.

The remaining of the paper is organized as follows: Section II presents the proof of our guarantee on the critical task real-time response. Section III formally presents the designtime analysis. Section IV describes and proves the run-time control. Section V demonstrates how the proposed methodology is applied in a detailed case study and presents several experimental results. Section VI presents the related work on mixed-critical systems. Section VII concludes this study.

II. GUARANTEE OF CRITICAL TASK REAL-TIME RESPONSE

The proposed methodology initially executes the maximum load scenario and at each observation point of τ C checks whether the low criticality tasks should be suspended. Hence, the following statement should be proved: "The switching from the maximum load scenario to the isolation scenario guarantees that the critical task meets the hard real-time deadline D C ."

The task set scenario switching occurs when the following safety condition does not hold:

RWCET iso (x) + RWCET max,PTP + t RT ≤ D C -ET(x) (1)
where RWCET iso (x) is the remaining WCET of τ C at an observation point x in the isolation scenario, RWCET max,PTP is the WCET until the next observation point, t RT is the total time of the proposed run-time control mechanism and ET(x) is the real execution time of τ C until point x. The t RT is the sum of: 1) t Mon (the overhead to monitor the real execution time), 2) t Cnt (the WCET of the run-time control), and 3) t SW (the WCET overhead due to scenario switching).

Theorem 1. If WCET iso ≤ D C , then for any execution with the proposed run-time control, τ C always respects its deadline.

Proof: If τ C is executed in isolation, by definition WCET iso ≤ D C . Let us assume that τ C starts its execution in the maximum load scenario until point p i+1 . For two consecutive observation points p i and p i+1 , we have:

ET(p i+1 ) -ET(p i ) ≤ RWCET max,PTP (2) 0 ≤ RWCET iso (p i ) -RWCET iso (p i+1 ) (3)
Since the execution continues in the maximum load scenario until p i+1 , it means that p i fulfilled the safety condition 1:

ET(p i ) + t RT + RWCET max,PTP + RWCET iso (p i ) ≤ D C
The remaining execution from p i+1 is safe if τ C can be switched in the isolation scenario and ends before its deadline, therefore we have to show that:

ET(p i+1 ) + t RT + RWCET iso (p i+1 ) ≤ D C

III. DESIGN-TIME ANALYSIS

This section describes the design-time analysis of the critical task and the computation of parameters used by the run-time control mechanism.

A. Extended Control Flow Graph Representation

A graph grammar is proposed to model the critical task τ C considered under study. The critical task τ C is described by the syntax of Table I, which covers a wide range of applications. From the binary code of the critical task τ C [START_REF] Cooper | Building a controlflow graph from scheduled assembly code[END_REF], we create a set of control flow graphs (CFGs), where we insert observation points. The CFGs obtained from the abstract syntax of Table I and compiled without optimizations are covered by the proposed grammar.

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 (Fig. 3(a)),

• C ∈ C represents the block of binary instructions of a condition statement (Fig. 3(b)),

• F i ∈ F represents the binary instructions of calling a function F i and links the node with the ECFG of the function F i (Fig. 3(c)),

• IN is the input node with an observation point in (Fig. 3(d)),

• OU T is the output node with an observation point out (Fig. 3(e)).

Every node v ∈ V corresponds to a terminal node of our grammar with one unique input observation point before the execution of the first binary instruction. We name the terminal nodes with upper letters and the observation point with lower letter based on the node type.

2) a finite set of edges E ⊆ V × V representing the control flow between nodes. Definition 4 (ECFG syntax). The ECFG syntax is defined by the following graph grammar, where the terminal nodes are the nodes of ECFG and the non-terminal node is B. The grammar rules are:

• A function F i has exactly one input node and one output node, with B a non-terminal node of the grammar (Fig. 4),

• A non-terminal node B is derived as (Fig. 5):

1) An empty node (Fig. 5 • During every derivation, the possibly multiple incoming links of B are "glued" to the upper block, and the outgoing link is glued to the lower block, with lower and upper referring to the graphical representation of Fig.

5

IN B OU T F i ≡ Fig. 4. Representation of function F i . B (a) ε (b) N (c) B B (d)
G i = (V i , E i ) and G j = (V j , E j ) are disjoint if V i ∩ V j = ∅ and E i ∩ E j = ∅.
The function call nodes link the disjoint ECFGs associated to the different functions. The Fig. 6 describes a task composed of two functions S = {F 0 , F 1 }. In Fig 6(a), F 1 is sequential, while in Fig. 6

(b) F 1 is recursive. F 0 in0 IN 0 N0,a n0,a F1 f0,1 N0,b n0,b out0 OU T 0 F 1 in1 IN 1 N1,a n1,a C c N1,b n1,b out1 OU T 1 (a) F 1 in1 IN 1 N1 n1 C c N2 n2 N3 n3 F1 f1,1 N4 n4 out1 OU T 1 (b) Fig. 6. Disjoints ECFGs associated to S = {F 0 , F 1 } Definition 6 (Walk). A walk W = (IN, v 1 , . . . , v n , OU T ) in an ECFG is defined as a finite list of nodes such that (v i , v i+1 ) ∈ E, (IN, v 1 ) ∈ E and (v n , OU T ) ∈ E.
A walk is defined on a unique ECFG, while at run-time a complete execution over the different ECFGs is observed.

Definition 7 (Execution of τ C ). Let us consider the task S = {F 0 , ..., F n } and the associated ECFGs G 0 ,. . . G n . An execution P is a list of nodes ∈ V 0 ∪ . . . ∪ V n obtained by inserting walks over the ECFGs. An execution is obtained inductively as follows: Following an execution, we obtain the sequence of visited nodes of the ECFGs and thus the sequence of the observation points. An observation point may be visited several times due to the loop components and the function calls. Hence, we define the nested level of an observation point to distinguish between different visits of the same point.

• Initially, P =W o , where W o is a walk over the ECFG of F 0 , W o = (IN 0 , v 1 , . . . , OUT 0 ). • Let P =(IN 0 , . . . , v i , v i+1 , . . . , OUT 0 ). If v i = F k and v i+1 = IN k , then P is rewritten as P = (IN 0 , . . . , v i , W F k , v i+1 , . . . , OUT 0 ) where W F k is a walk over G k .
Definition 8 (Nested level). The nested level level (x) of an observation point x in an ECFG is defined based on the grammar syntax as:

• Initialization point: The level of the initialization point start is 0, level(start)=0.

• Input node: The level of the input point in is 1, level(in)=1.

• Output node: The level of the output point out is 1, level(out)=1.

• As the nested levels are design-time determined per ECFG, we define the head points to deal with the real execution of the critical task. The head points show when a function has been called and where a loop exists in each ECFG.

Definition 9 (Head point). Let us consider the task S = {F 0 , ..., F n } with the associated ECFGs G 0 ,. . . G n and an execution P = (IN 0 , v 1 , . . . , OUT 0 ). The head points are defined as follows:

• head(in 0 )=start • let us assume that we computed head(v i ).

• if v i+1 = IN k , then head(v i+1 ) = v i • if v i = OUT k , then head(v i+1 ) = head(head(v i )) • if (v i , v i+1 ) ∈ E k (i.e. are in the same ECFG): if v i is the condition of a loop, head(v i+1 ) = v i otherwise head(v i+1 ) = head(v i ) For instance, in Fig. 6(a) the P =(IN 0 , N 0,a , F 1 , IN 1 , N 1,a , C, N 1,b , C, OUT 1 , N 0,b , OUT 0 )
is an execution of the task. In a similar way, an execution over a recursive function in Fig. 6(b) is

P = (IN 0 , N 0,a , F 1 , IN 1 , N 1 , C, N 3 , F 1 , IN 1 , N 1 , C, N 2 , N 4 , OUT 1 , N 4 , OUT 1 , N 0,b , OUT 0 ).
Table II provides the nested levels and the head points for the observation points of Fig. 6 for these executions.

B. Remaining WCET analysis

The remaining WCET of the critical task heavily depends on the real execution of the critical task. Hence, at design-time, we process the ECFGs and compute partial WCETs using safe static WCET analysis, similar to [START_REF] Wilhelm | The worst-case execution-time problem -overview of methods and survey of tools[END_REF], but extended and adapted to our methodology. The WCET is computed by writing an Integer Linear Programming (ILP) formulation to express the program execution time as the combination of the individual times of the grammar components weighted by their execution counts. This expression is maximized to find the WCET, with

(x) type (x) head (x) Initialization start 0 - - F 0 in 0 1 - start n 0,a 1 - start f 0,1 1 F ENTRY start n 0,b 1 F EXIT start out 0 1 - start F 1 Fig. 6(a) in 1 1 - f 0,1 n 1,a 1 - f 0,1 c 1 - f 0,1 n 1,b 2 - c out 1 1 - f 0,1 F 1 Fig. 6(b) 1 st visit 2 nd visit in 1 1 - f 0,1 f 1,1 n 1 1 - f 0,1 f 1,1 c 1 - f 0,1 f 1,1 n 3 2 - c f 1,1 2 F ENTRY c n 2 1 - f 1,1 - n 4 1 F EXIT f 1,1 f 0,1 out 1 1 - f 1,1 f 0,1
a number of constraints that reflect flow facts, e.g. loop bounds and unfeasible paths.

Our WCET analysis is based on computing the remaining WCET from one observation point x until the end of the program, RWCET y (x), where y ∈ {iso,max}. When the RWCET max (x) is computed, we consider that interferences occur from the parallel tasks, whereas when the RWCET iso (x) is computed no interferences are taken into account. When point x is the entry of the critical task, i.e. start of F 0 , RWCET y (start) is the total WCET τi,y . When point x is inside the ECFG, we compute the remaining WCET by using constraints to prohibit the execution of all the blocks which do not belong to any path from point x until the end of the ECFG.

Using the remaining WCET analysis of an observation point x, we can compute remaining WCETs between an observation point and its head point.

Definition 10 (d head(x)-x ). 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 11 (Loop component). When d head(x)-x is computed inside a loop component with conditional node c and n number of iterations, no time variation exists between iterations.

d c-x = RWCET iso (c, j) -RWCET iso (c, j), ∀j ≤ n
w c is the time between any two consecutive iterations j and j + 1 of the conditional node c. w c = RWCET iso (c, j) -RWCET iso (c, j + 1), ∀j ≤ n When a function is called from different points, the paths to the different points may result to several partial remaining WCETs. The existence of several paths may introduce time variability in the computation of d head(x)-x of the function points x with level 1. For instance, point n 1 in Fig. 6(a) may have different values d f0,1-n1 and d f1,1-n1 . A trade-off exists between storing these timevariations or a unique partial information that permits the computation of a local upper bound for these points, i.e. the minimum remaining time observed from any common function call. For instance, in Fig. 6(b), the OTAWA tool computes RWCET iso (f 0,1 ) = 50, RWCET iso (n 1 ) = 48, RWCET iso (f 1,1 ) = 45, RWCET iso (n 1 ) = 40. By using the minimum time, we store d head(n1)-n1 = 2 and at run-time we obtain RWCET iso (f 0,1 ) = 50, RWCET iso (n 1 ) = 48, RWCET iso (f 1,1 ) = 45, RWCET iso (n 1 ) = 43.

To guarantee that the critical task deadline is always met, we must ensure that enough time is available to perform the scenario switch at the next observation point. Hence, we apply our remaining WCET analysis to compute the RWCET max,PTP between any two consecutive observation points of the critical task in the maximum load scenario.

RWCET max,PTP = max x,x ′ (RWCET max (x) -RWCET max (x ′ ))
To support the run-time RWCET iso (x) computation, we store in memory the level(x) and d head(x)-x for each point x. If x is the head point of a loop component, the w x is also stored. If x is a function call entry or exit point, the type of the point is stored as well. An example of the data stored after the design-time analysis is given in Table III of Section V-A for our case study.

IV. RUN-TIME CONTROL

At each observation point x, the safety condition of Section II decides the switching between scenarios. As the RWCET iso (x) is modified at each observation point, we propose a low-overhead algorithm to run-time compute this value by efficiently reusing the RWCET iso of the head points. In Section IV-A we describe and formally prove the basic version of our algorithm applied when the critical task consists of a single function, i.e. S = {F 0 }. In Section IV-B we present and formally prove our extended version applied when the critical task consists of a finite set of functions, i.e. S = {F 0 , . . . , F n }.

A. Basic version 1) Algorithm description:

The run-time computation of RWCET iso (x) is depicted in Alg. 1. The pre-computed data are stored in the memory as constant arrays: level for the level and d and w for the partial WCETs. The algorithm maintains two local values o level (for the previous observed level) and ll for the local level. For the basic version, ll is always equal to level(x). At run-time, the algorithm stores in array last point the last observed point and in array R the computed RWCET iso per level.

o level = 0, ll = level[x], last point[0]=start, RWCET iso [0]=WCET iso Output: RWCET iso (x) = R[ll] if o level < ll then / * condition 1 * / R[ll] = R[ll -1] -d[x] else if (last point[level] == x) then / * condition 2 * / R[ll] = R[ll] -w[x] else R[ll] = R[ll -1] -d[x] last point[ll]= x o level=ll
Three cases exist during the algorithm execution:

• Case 1: The current observation level o level is less than the local level ll. In this case the ECFG is traversed in a forward direction, because the observed point x has larger level than the previously observed point. This case occurs when we enter a loop. 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 2) Algorithm proof: The termination of the algorithm is ensured, as the task execution terminates and a finite number of observed points exist. If m points have been inserted to the critical task, each executed at most l times, due to the bounded number of loop iterations, the algorithm is executed at most n times, where n is the total number of visits over the observed points, i.e. n ≤ m i=0 l i . We prove the correctness of the Alg. 1 given the graph grammar defined in Section III-A. We show that the result of the algorithm is the RWCET iso (x) of point x. The proposed algorithm is proved through a structural induction on the grammar rules. Initially, the algorithm is proved for the basic case. Then, starting from the basic case and applying m grammar rules, we reach our induction hypothesis. At that point, the induction step derives from rewriting a non-terminal block B using the grammar components depicted in Fig. 5.

Basic case (Fig. 7(a)): The function F 0 has a non-terminal block B. By definition 8, level (in 0 ) = level (out 0 ) = level (b) = 1. By definition 9, head (in 0 ) = head (out 0 ) = head (b) = start. By definition 7, there is a unique execution P = (IN 0 , B , OUT 0 ). We have moreover R[0] = RWCET iso (start) = WCET iso . We apply the algorithm on the ECFG.

Point in 0 is the input of the function. Since o level =0, the condition 1 of Alg. 1 is true:

R[1] = R[0] -dstart-in 0 = R[0] -(WCET iso -RWCET iso (in0)) = RWCET iso (in0) o level = 1 last point[1] = in0
Point b is just before the execution of the block. Since o level =1 and the previously observed point is in 0 , the condition 1 of the run-time control algorithm is false. As the last point [START_REF] Singh | Mapping on multi/many-core systems: Survey of current and emerging trends[END_REF] is the point in 0 and we observe the point b, the condition 2 is false:

R[1] = R[0] -d start-b = R[0] -(WCET iso -RWCET iso (b)) = RWCET iso (b) o level = 1 last point[1] = b
Point out 0 is the point after the execution of all instructions of the block, but for this basic case, the algorithm did not visit any other observation point. The variables are o level = 1, last point[1 ] = b. Therefore, the condition 1 and the condition 2 are false. Induction step: We first define the induction hypothesis (Fig. 7(b)). By applying m grammar rules starting from the basic case, we obtain an execution starting from IN 0 and ending at OUT 0 with at least one non-terminal block (we are somewhere in the ECFG creation process), i.e. P =(IN 0 , . . . , B , . . . , OUT 0 ). We apply the algorithm until the observation point b, with level(b) = l and head(b) = h, and we compute R[l] = RWCET iso (b). The run-time execution has already visited the point h, which is the head point of b, with level l -1. More precisely, we know that R[l -1] = RWCET iso (h), o level =l and last point[l ] = b.

R[1] = R[0] -dstart-out = R[0] -(WCET iso -RWCET iso (out0)) = RWCET iso (out0) = 0 o level = 1 last point[1] = out0
A step (Fig. 8) is done as follows: The non-terminal block of B in the execution P is rewritten by applying the grammar rules.

have R[l] = R[l -1] - (RWCET iso (h) -RWCET iso (b 1 )) = RWCET iso (b 1 ), o level =l and last point[l ]=b 1 . At point b 2 ,
the previously observed point is b 1 which has level l and thus the condition 1 and condition 2 are false. Therefore, we have:

R[l] = R[l -1] -d h-b 2 = R[l -1] -(RWCET iso (h) -RWCET iso (b2)) ≥ RWCET iso (b2) o level = l last point[l] = b2
If-then-else condition component (Fig. 8(d = RWCET iso (bi)

R[l] = R[l -1] -d h-bp = RWCET iso (h) -(RWCET iso (h) -RWCET iso (bp)) = RWCET iso (bp) o level = l last point[l] = bp
o level = l last point[l] = bi
The first time C is visited (iteration 0), the condition 1 and the condition 2 are false.

R[l] = R[l -1] -d h-c = R[l -1] -(RWCET iso (h) -RWCET iso (c)) = RWCET iso (c) o level = l last point[l] = c
The j-th time c is visited (iteration j), the previously observed point is b l , so o level =l + 1 . Therefore, the condition 1 is false and since the previously observed point of level l is c, the condition 2 is now true.

R[l] = R[l] -wc = RWCET iso (c) -j × wc = RWCET iso (c, j) o level = l last point[l] = c
When b l is visited (C was true) at the j-th iteration, the condition 1 is true.

R[l + 1] = R[l] -d c-b l = R[l] -(RWCET iso (c, j) -RWCET iso (b l , j)) = RWCET iso (c, j) -(RWCET iso (c, j) -RWCET iso (b l , j)) = RWCET iso (b l,j ) o level = l+1 last point[l+1] = b l

B. Extended version 1) Algorithm description:

The extension of the basic version of the proposed run-time algorithm for the critical task described by a set of ECFGs is depicted in Alg. 2.

ALGORITHM 2: Extended version.

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 4 * / o level-=1 offset -= level[x] ll = offset + level[x] Instructions of basic version [Alg. 1] if (level[x] ==F ENTRY or F ENEX) then / * condition 3 * / offset += level[x]
As the function calls link the ECFGs, we need to know at run-time when the execution moves to another ECFG. Therefore, we have to mark the entry and the exit points of a function call and, thus, the type(x) of the points is also stored in memory. Locally, a data offset computes the accumulated nested level up to the last observed function entry point. The local level ll depends on this offset and the nested levels of the observation point. Note that now the condition 1 of the basic version becomes also true in the case we enter in a function after the function call node. In the extended version, two additional cases exist during the algorithm execution:

• Case 1: When a function entry point is observed (condition 3 is true), we increase the offset by the level of the entry point. • Case 2: When an exit point is observed (condition 4 is true), we decrease the offset by the level of the entry point.

In that case, o level is decreased by 1 to indicate that we encountered an exit point.

From definition 8, the level of the exit point is equal to the level of the entry point. Hence, if the offset is equal to zero, we have returned in the main function F 0 .

2) Algorithm proof: The termination of the algorithm is ensured due to the finite number of loop iterations and function calls. We prove the correctness of the extended algorithm by applying a structural induction on the grammar rules in a similar way with the basic version, as depicted in Fig. 7. The basic case of the extended version remains the same (Fig. 7(a)), as no function call has occurred yet.

Induction step:

We first define the induction hypothesis (Fig. 7(b)). After applying m grammar rules, we obtain an execution that has started from IN 0 and ends at OUT 0 with at least one non-terminal node, i.e. P =(IN 0 , . . . , B , V , . . . , OUT 0 ). We know for point b that level

(b) = l, offset = m, o level = m + l , R[m + l] = RWCET iso (b). The head point of b is point h and R[m + l -1]=RWCET iso (h).
We need also the successor V of B in the execution, which can be either a terminal or non terminal block. We also know that level(v) = l and head(v) = h since B is a non-terminal block, and thus it cannot be a loop head or a function call.

Step (Fig. 9): The non-terminal block B is rewritten based on the grammar components. For the grammar rules except the function call, the proof of the basic version remains valid. The main difference occurs when the non-terminal block B becomes a function call node F i , where the F i is described by an ECFG. Let the block B become the node F i and the execution become

P =(IN 0 , . . . , F i , IN i , B i , OUT i , V , . . . , OUT 0 ). 1) Since f i replaces b, we have R[m + l] = RWCET iso (f i ).
Moreover, the condition 3 is true, thus offset = m + l and

last point[m + l] = f i . 2) For b k ∈ {in i , b i , out i }, we have level(b k ) = 1
and the condition 3 and condition 4 are false. The computation is similar in these points, we obtain

R[m + l + 1] = R[m + l] -d f i -b k = RWCET iso (fi) -(RWCET iso (fi) -RWCET iso (b k )) = RWCET iso (b k ) o level = m+l+1 last point[m+l+1] = b k
3) The successor V of B is the exit point of the function call F i . In v, the condition C4 is true, meaning that offset = m + ll = m and o level = m + l. This implies that condition 1 and condition 2 are false.

R[m + l] = R[m + l -1] -d h-v = RWCET iso (h) -(RWCET iso (h) -RWCET iso (v) = RWCET iso (v) o level = m+l last point[m+l] = v V. RESULTS

A. Demonstration case study

We use as a case study the lu from Polybench benchmark suite [START_REF] Pouchet | Polybenchmarks benchmark suite[END_REF], which is depicted in Alg. 3. begin int lu() int i, j, k; for (k = 0; k < PB N; k++) do for

(j = k + 1; j < PB N; j++) do A[k][j] = A[k][j] / A[k][k]; for (i = k + 1; i < PB N; i++) do for (j = k + 1; j < PB N; j++) do A[i][j] -= A[i][k] * A[k][j]; return EXIT SUCCESS;
1) Design-time analysis: The ECFGs corresponding to the main function F 0 and the lu function F 1 are depicted Fig. 10. Different colors are used to distinguish the nested loops: the first loop is depicted with light gray, the second with gray, the third with black, whereas the white corresponds to no loop. Fig. 11 depicts the corresponding assembly operations and the blocks. An observation point exists per block. By analyzing the ECFGs we pre-compute the data level, w, d, type, which are depicted in Table III.

The assembly instruction and the grouping into blocks is depicted in Fig. 11.

Obs.point x type (x) level (x) w(x) d(x) n 0,1 - 1 0 0 f 1 F ENTRY 1 0 d start-f 1 n 0,2 F EXIT 1 0 d start-n 0,2 n 1,1 - 1 0 0 c 1 - 1 w 1 d f 1 -c 1 n 1,2 - 2 0 d c 1 -n 1,2 c 2 - 2 w 2 d c 1 -c 2 n 1,3 - 3 0 d c 2 -n 1,3 n 1,4 - 2 0 d c 1 -n 1,4 c 3 - 2 w 3 d c 1 -c 3 n 1,5 - 3 0 d c 3 -n 1,5 c 4 - 3 w 4 d c 3 -c 4 n 1,6 - 4 0 d c 4 -n 1,6 n 1,7 - 3 0 d c 3 -n 1,7 n 1,8 - 2 0 d c 1 -n 1,8 n 1,9 - 1 0 d f 1 -n 1, 9
2) Run-time control: We apply the extended version of the proposed run-time algorithm (Alg. 2) on the execution P =

(IN 0 , N 0,1 , F 1 , IN 1 , N 1,1 , C 1 , N 1,2 , C 2 , N 1,3 , C 2 , N 1,4 , C 3 , N 1,5 , C 4 , N 1,6 , C 4 , N 1,7 , C 3 , N 1,8 , C 1 , N 1,9 , OUT 1 , N 0,2 ,
OUT 0 ). The obtained results are depicted in Table IV. The table, following the order of the execution, shows the observation points, the value of the each condition of the run-time computation algorithm, how the RWCET iso (x) is computed and which is the last point last point[ll ] that modified the RWCET iso (x).

B. Experimental results

We applied our methodology for several benchmarks from Polybenchmark suite [START_REF] Pouchet | Polybenchmarks benchmark suite[END_REF] through simulation to obtain preliminary results of our method. We explore several options in the sets of observation points, i.e. Head Points (HP) in: i ) nested level 1, ii ) nested level 1 and 2, iii ) nested level 1, 2 and 3, and iv ) nested level 1,2 and 3 and Sequential Points (SP) inside level 3, considering the same deadline per benchmark. We compute the gain of our approach, i.e. the percentage of the execution time of the critical tack in maximum load scenario, and the overhead introduced by our [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 realtime 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 mixed-criticality 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 on maximum load scenario. 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. 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 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 may be 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.

Existing approaches explore efficient ways to address mixed-criticality systems in multi/many-core systems, but under the assumption that the WCETs of at least the high criticality level remains below the deadlines. The methodology proposed in this paper improves the resources utilization while guaranteeing the critical task real-time response, when the WCET of the critical task in maximum load scenario is estimated above the deadline, whereas in isolation scenario respects its deadline.

B. Run-time control implementation

Several approaches exist that reallocate the resources 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 offline 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.

In contrast, our approach is based on monitoring the real execution time of the critical task and decides the suspension of the low criticality task by run-time computing the remaining WCET of the critical task in isolation.

VII. CONCLUSION & FUTURE WORK

In this work, we present a methodology to improve the resources utilization by increasing the task parallelism, while guaranteeing the real-time response of the critical task. At design-time analysis, the critical task is described by a set of ECFGs and partial WCET analysis is applied to compute the required data for the run-time part. At run-time, a low-overhead controller computes the remaining WCET of the critical task and decides the switching between maximum load scenario and isolation scenario.

As future directions, we plan to develop a methodology to decide the position of the observation points over the ECFGs and to implement and evaluate the proposed methodologies to a real mutlicore system. Potentially a similar profiling approach with [START_REF] Mancuso | Real-time cache management framework for multi-core architectures[END_REF] could be also used to experimentally identify the position of the observation points. In addition, we consider the extension of the proposed approach to several high criticality tasks and several criticality levels. In this context, we plan to explore several strategies on task scheduling, where the proposed methodology could be potentially combined with several approaches presented in the related work.

Fig. 1 .

 1 Fig. 1. Mixed-critical schedules scenarios

Fig. 3 .

 3 Fig. 3. Schematic representation of terminal grammar nodes.

4 )

 4 (b)), 2) A single node N (Fig. 5(c)), 3) A sequential component, i.e. the concatenation of nonterminal nodes (Fig. 5(d)), An if-then-else component, i.e. the concatenation of a C conditional node with two mutually executed paths that end to the same non-terminal node (Fig. 5(e)), 5) A loop component, i.e. the concatenation of a loop condition C with two mutually executed paths, one with the empty node and one with the repetition of the loop kernel (Fig. 5(f)), 6) A function call node F i (Fig. 5(g)).

Fig. 5 .

 5 Fig. 5. Schematic representation of rewritting grammar rules

•

  Sequential component: The levels of two sequential points b 1 and b 2 are equal, level(b 1 )=level(b 2 ). • If-then-else component: The levels of all the points c, b t , b f and b o are equal, i.e. level(c)=level(b t ) =level(b f )=level(b o ). Loop component: The level of the initial block b i is equal to the level of the conditional node c, i.e. level(b i )=level(c). The level of the loop body point b is equal to the level of the loop condition c incremented by one, level(b)=level(c)+1.

ALGORITHM 1 :

 1 Basic version.Pre-computed data: level, w, d Input: x Data:

  [x] = d c-x . • Case 2: o level ≥ ll and last point[ll] = x. The observation point x is revisited. In this case, the ECFG is traversed in a backward direction due to the head point of a loop component, i.e. the condition. The remaining time of this level is reduced by w[x] = w c . • Case 3: otherwise. The ECFG is traversed in forward direction as the observed point is placed in a sequence with the previously observed point. This case occurs in the sequential component and the if-then-else component of our grammar. The remaining time is the remaining time of the head point c minus d[x] = d c-x .

Fig. 7 .

 7 Fig. 7. a) Basic case and b) Structural induction hypothesis.

Fig. 8 .

 8 Fig. 8. Structural induction step.

  )): The block B becomes a conditional node C, two mutually executed blocks B T and B F and an output block B O . The execution becomes P =(IN 0 , . . . , C , B T , B O , . . . , OUT 0 ) when the condition C is true, or P =(IN 0 , . . . , C , B F , B O , . . . , OUT 0 ) when the condition C is false. The point b is equal to the point c. Based on definition 8, the level remains same between observation points of the condition node C, the mutually executed blocks B T and B F and the output block B. Based on definition 9, all points have the same head point. For point b f and b t the previously observed point is c and for b o is b f or b t , depending on the value of the condition C. The condition 1 is always false. For all points b p ∈ {b t , b f , b o }, we have:

  Loop component (Fig.8(e)): The block B becomes an initial block B I , a condition node C and a loop body block B L . We also know the maximal number of loop iterations p. The execution becomes P =(IN 0 , . . . , B I , (C , B L ) k , C , . . . , OUT 0 ) with k ≤ p. By definition 8, level (b i ) = level (c) = level (b) = l and level (b l )=l + 1 . By definition 9, head (b i ) = head (c) = head (b) = h and head (b l )=c. We now apply the algorithm. Since B I replaces B, at point b i we have: R[l]

Fig. 9 .

 9 Fig. 9. Structural induction step to function call node.

ALGORITHM 3 :

 3 Demonstration case study. # define PB N 100 int A[PB N][PB N]; begin int main() lu(); return EXIT SUC;

Fig. 10 .

 10 Fig.10. ECFGs of the main function F 0 and the lu function F 1 with the level, the w of loop head points and some d between the loop head point and the first observation point.

TABLE I

 I Definition 1 (Critical task τ C ). A critical task τ C is a set of functions S = {F 0 , F 1 , ..., F n }, with F 0 the main function. Each function is represented by an Extended CFG (ECFG).

		.	APPLICATION MODEL SYNTAX
			Syntax rules
	term	::= <constant> | <variable>
	expr	::= <term> | <term> <operator> <term> | <unary-expr>
	unary-expr ::= <variable> <unary-operator> | <unary-operator> <variable>
	cond-expr	::= <expr> <conditional-operator> <expr>
	assignment ::= <unary-expr> <assignment-operator> <expr>
	instruction ::= <assignment> | <unary-expr> | <>;
	stat	::= <instruction> | <stat>;<stat> | if (<cond-expr>) then <stat1>
		else <stat2> | for (expr1; cond-expr; expr2) <stat> | <function-
		call> ;
	function-call ::= <return-type> functionName( <parameter-list> ) <stat> return
		<expr-return>;
	program	::= <function-call>
	Definition 2 (Observation point). An observation point is a
	check point in an ECFG where the run-time control is executed.
	A special observation point named start is defined before the
	starting of the execution.
	Definition 3 (Extended Control Flow Graph). An ECFG is
	a CFG annotated with observation points. The ECFG of a
	function F is a directed graph

TABLE II .

 II NESTED LEVEL AND HEAD POINTS OF FIG.6

Observation point x level

TABLE III .

 III DESIGN-TIME ANALYSIS RESULTS FOR main AND lu.

TABLE V .

 V EXPERIMENTAL RESULTS OF OUR METHODOLOGY.

	Algorithm	Points Position Number of points % max scenario Tot.overhead (tu)
			Basic version
		HP L1	16	50	18
	LU , N = 16	HP L1,L2	256	69.53	358
		HP L1-3	4,096	19.33	1,586
		HP L1	32	43.75	30
	LU , N = 32	HP L1,L2	1,024	67.77	1,390
		HP L1-3	32,768	29.04	19,030
	LU , N = 128	HP L1 HP L1,L2	128 16,384	25.78 85.81	68 28,120
	bicg, NY =NX =16	HP L1 HP L1,L2 HP L1,L2 & SP	32 272 578	25.00 78.68 51.90	18 430 602
	bicg, NY =NX =32	HP L1 HP L1,L2 HP L1,L2 & SP	64 1,056 2,178	18.75 37.31 17.54	26 790 766
	bicg, NY =NX =64	HP L1 HP L1,L2 HP L1,L2 & SP	128 4,160 8,450	5.47 11.35 43.79	16 946 7,402
			Extended version
		HP L1	11	27.27	8
	trmm,	HP L1,L2	83	63.85	108
	NI = 8	HP L1-3	659	43.86	580
		HP L1-3 & SP	1,316	36.93	974
		HP L1	19	21.05	10
	trmm,	HP L1,L2	291	56.70	332
	NI = 16	HP L1-3	4,643	23.48	2,182
		HP L1-3 & SP	9,284	15.53	2,886
	gesummv , NI = 8	HP L1 HP L1,L2 HP L1,L2 & SP	11 83 164	18.18 31.33 48.78	6 54 162
	gesummv , NI = 16	HP L1 HP L1,L2 HP L1,L2 & SP	19 291 580	36.84 40.55 51.73	16 238 602
		HP: Head Points, SP: Sequential Points, tu: time units

run-time control. The results are given by the number of observation points executed before the switching to isolation scenario over the total number of observation points introduced in the benchmark. Our simulation has as input the ECFG, the partial RWCETs and the information about the observation points and the execution. We considered an ∼0.10-0.32% difference between the real execution time and the WCET in isolation. The results are depicted in Table V.

Based on the obtained results, a trade-off exists between the number of observation points introduced in the ECFGs and the gain of the proposed approach, which is affected by the shape of the ECFGs. By using few points, e.g. HP in L1, the switching of scenarios may occur too early giving lower than the possible gains, e.g. 25,00% for benchmark bicg. This behavior occurs due to large distance between two sequential observation points. It may occur in the case where inside the loops of level 1 several nested loops exists with high number of iterations. On the other hand, by using too many points, i.e. in all loop head points and in the internal loop kernel, the time between two consecutive points may be similar to the execution time of the controller. Then, a significant time is dedicated to control execution pushing further in time the task execution, resulting to an early scenario switch and to a lower gain of the proposed approach, e.g. 51,90% for benchmark bicg. When the execution time of the critical task between two sequential points is quite larger than the controller overhead, but still not too large to prohibit the exploration of the potentials of our approach, we can achieve significant gains, e.g. 78,68% for benchmark bicg.

VI. 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].

A. 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],


Alexis Aubry
email: alexis.aubry@univ-lorraine.fr

Hervé Panetto
email: herve.panetto@univ-lorraine.fr

Towards interoperability properties for tooling a software bus for energy efficiency

This paper proposes a draft architecture for a software bus that deals with the interoperability challenges when having to interconnect, in a software platform, some software components/tools/methods/approaches for optimising energy efficiency. This platform will be developed in the framework of the French ANR Plate-Form(E)3 project. After having highlighted the challenging interoperability issues that are inherent to this type of platform, we are analysing a state-of-the-art for identifying the candidate technologies. An architecture based on one technology candidate for solving the basic interoperability challenge is then proposed.

I.

INTRODUCTION

The current context of increasing scarcity of fossil fuels and the associated price volatility strongly encourage the society for energy saving. Although significant efforts have been made in the industrial sector since 1973, according to estimation from the French institute CEREN 1 , the potential energy power saving could be up to 12 Mtoe 2 (about 23% of energy consumption in the industrial sector). These savings could be made on the following basis:

 About 2/3 of the savings can be made on plants using local optimisation approaches, conventional or experimental technologies.  The remaining 1/3 of the savings can be achieved by conducting cross-cutting actions, using technology for recovery and transport of residual energy. The local optimisation approach (process/plant scale) is already extensively studied, while the global optimisation approach (territorial area) is not addressed in the literature. In fact, no tool exists that is capable to achieve a crossscale optimisation of energy and environmental efficiency. The aim of Plate-Form(E)3 3 project is to address this problem. The ANR Plate-form(E)3 (PFE3) project: Digital Platform for computation and optimisation of Energy and Environmental Efficiency at different scales for industry (component/process/plant/territory) must contribute to the optimisation of energy and environmental efficiency of industry and territories. Plate-form(E)3 will be realized by a prototype for assessing the impact of new technolo- 1 CEREN, French Centre for Studies and Economic Research on energy 2 Mtoe = Million Tonnes of Oil Equivalent 3 http://www.agence-nationale-recherche.fr/en/anrfunded-project/?tx_lwmsuivibilan_pi2[CODE]=ANR-12-SEED-0002 gies on a large scale. This framework will propose the integration of any energy sources and sinks across the territory, seeking potential interconnections between industries (territory scale), to optimise process efficiency (plant/process scale) and to facilitate the optimal design of new technologies (component level). The platform will interconnect some existing tools (open source or proprietary) implementing different specialised methods, models and algorithms. The issue of interoperability is thus important.

The goal of this paper is to present the analysis and synthesis of the state-of-the-art, relevant for resolving the different interoperability issues of the future Plateform(E)3 system -prototype.

The first part of this paper is related directly to the definition of the interoperability problems in PFE3. Hence, it presents theoretical foundations for interoperability, the motivation for that work, scenarios and use cases that form the Plate-form(E)3 system architecture and its environment. The second part analyses the state-of-the-art, namely candidate technologies, models, tools, resources and frameworks for the resolution of the identified interoperability problems. Different types of candidate technologies are presented. Each of the technology analysis will consist of two sections. The first section presents the technology in detail. The second section analyses the relevance of the technology for PFE3. Finally a discussion is proposed for presenting an architecture based on the use of a standard for process simulation software (namely CAPE-OPEN) that is considered as one of the candidates for dealing with our interoperability issues.

II. INTEROPERABILITY AND THE ASSOCIATED PROBLEMS IN PFE3

A. Theoretical foundations for interoperability IEEE defines interoperability as the ability of two or more systems or components to exchange information and to use the information that has been exchanged [ 1 ] . Hence, the diversity, heterogeneity, and autonomy of software components, application solutions and business processes, must be considered as potential sources of noninteroperability. In contrast to system integration, which basically deals with formats, protocols and processes of information exchange, the objective of interoperability is to have two systems invoking each other's functions or exchanging information with the consideration that they are not aware of each other's internal workings.

Furthermore, interoperability aims at correct and complete reasoning on the meaning of the information which [START_REF] Aubry | A cross-scale models interoperability problem: the Plate-Form(E)3 project case study. 3rd industry Applications and Standard initiatives for Cooperative Information Systems for Interoperable Infrastructures[END_REF] is exchanged between two systems. Hence, it is sometimes called "semantic interoperability". Main tools for the implementation of the semantic interoperability are ontologies, languages for ontologies' representation, inference tools (engines) and semantic applications.

Semantic interoperability of systems means that the precise meaning of the exchanged information is uniquely interpreted by any system not initially developed for the purpose of this interoperation. A formal definition of semantic interoperability has been proposed in [START_REF] Sowa | Knowledge Representation: Logical, Philosophical, and Computational Foundations[END_REF].

B. Interoperability problems in PFE3

The goal of the Plate-Form(E)3 project is to provide a first prototype of a software platform in which some existing tools/methods/approaches have to be connected to solve dedicated use cases. This platform may then be considered as a software bus where any used application can connect. These use cases concern two types of scenario at two extreme scales.

The first type considers the process scale; the objective of the future interoperability solution at this scale is to facilitate engineering of a new component in the single process, to improve the general process performance, e.g. concerning the energy costs. In this first scenario, interoperability concerns the efficient (optimised) interconnection of unit operations (i.e. basic step in a process such as separation, crystallization, evaporation, filtration…) within a single process. Beside material flows, these interconnections may also need to consider flows of information, needed to optimise the process execution, taking into account the cost of energy.

The second type is related to the territory scale; the objective at this scale is to facilitate integrated energy management with a final goal to optimise the energy consumption in the specific territory. This will be enabled by the collaboration of the different plants in one defined territory. Two plants could collaborate to exchange the resources that are considered as excessive or even as a waste in one company, but could be used as energy source in another one (e.g. hot water, steam, heat, pressurized fluid, ..). In this second scenario, interoperability may also concern both material and information flows and their sustainable reuse by different facilities, inside a territory.

Thus, the tools that must be interconnected in Plate-Form(E)3 do not operate at the same scale, with the same business knowledge and on the same models but they must always be able to share information that they produce, ensuring the overall coherency of the whole. That means that these tools must be interoperable.

The above context can thus be defined through three generic and general scenarios that must be realised within two classical interoperability levels (technical and conceptual) [START_REF]Enterprise Interoperability-Framework and knowledge corpus -Final report[END_REF]. Some scientific problems then arise when intersecting those scenarios with the interoperability levels.

So, we propose here to define these scientific problems, based on the consideration of the use cases at two levels of abstraction. First level considers the most generic interoperability scenarios. The second level takes into account the conceptual architecture of Plate-form(E)3.

1) Generic scenarios and scientific problems

In order to highlight the underlying problems in setting interoperation between the specialised tools for modelling physical systems and their optimisation, it is important to identify the generic scenarios that realize this interoperation.

We have identified the following generic scenarios [START_REF] Aubry | A cross-scale models interoperability problem: the Plate-Form(E)3 project case study. 3rd industry Applications and Standard initiatives for Cooperative Information Systems for Interoperable Infrastructures[END_REF]: cross-scale interoperation, cross-domain interoperation, cross-feature interoperation (see Figure 1). Also, some first general assumptions on the possible approaches to address the problems at this generic level are given.

 Cross-scale interoperation: the different scales concern the component (optimal design of new technologies), the process/plant (optimisation for efficient energy management) and the territory (optimisation of potential interconnections between industries). The tools that will potentially be connected with the platform will be used at these different scales, producing models that need to be exchanged compromising the overall performance.  Cross-domain interoperation: for modelling/simulating/optimising the physical systems through the platform, users use knowledge and domain-dependant tools that are specialised. Thus experts' knowledge covers broad areas of physics for modelling thermal, thermodynamics, chemistry and energetics processes. We must also add the experts' knowledge related to optimisation. Hence, to some extent, cross-domain interoperability is related to semantic interoperability.  Cross-feature interoperation: physical systems modelled in Plate-Form(E)3 will be simulated and optimised through these models. Tools for modelling, simulation and optimisation need to be interconnected. This is the problem related to so-called syntactic interoperability. However, the semantics is not a priori excluded as a possible asset to achieve the interconnection of the above tools. Namely, semantics can be used to achieve syntactic interoperability. For making the previous scenarios effective, there exist some barriers (conceptual, technological and organisational) [START_REF]Enterprise Interoperability-Framework and knowledge corpus -Final report[END_REF] that define levels of interoperability to be studied. While organisational barriers are an issue mainly from governmental and privacy perspectives, we will focus on technical and conceptual barriers as follows:

Plate-form(E)3

User interface

 Technical barriers are related to the incompatibility of information technologies (architecture & platforms, infrastructure, exchange formats syntax …).  Conceptual barriers are related to the semantic mismatches of information to be exchanged. These barriers concern the modelling at the high level of abstraction. For highlighting the scientific problems linked to the Plate-Form(E)3 project, we propose to intersect the different generic scenarios with the interoperability levels.

Technical interoperability problems appear in each scenario. Solving these technical barriers is now easier and partly achieved by standard techniques and implemented interfaces. We can cite, for instance, XML (eXtensible Mark-up Language) and linked applications: SOAP (Simple Object Access Protocol) and WSDL (Web Services Description Language). We must therefore assess whether the candidate tools for integration into Plate-Form(E)3 use existing standards (CAPE-OPEN4 , ...) or we must define such a standard. When connecting a new tool, we must be able to assess quickly its ability to interoperate with Plate-Form(E)3 at the technical level.

Conceptual interoperability problems concern:  for the cross-scale interoperation scenario, the dynamics and the granularity of the used models that are not the same. Indeed, the models have not the same time scale when considering a territory or a component. Moreover, the different models represent heterogeneous aggregates of information depending of the scale of the modelled system (from territory to component). It is therefore necessary to formalize and finally assess the correlation between models outputs at a given scale and their use as inputs at another scale (with the same tool or not).  for the cross-domain or cross-feature interoperation scenarios, the knowledge of several specific domains that are managed by the different tools to be connected through the platform. This heterogeneous knowledge produce semantically heterogeneous models that must be exchanged, stored, processed consistently with the purposes for which they have been built. Moreover, this raises the issue of the a priori evaluation of the ability to exchange ad-hoc models (related to a specific domain or a particular tool feature) without knowing in advance the tools that will be connected to the platform to process these models (and thus the business semantics of the related models that are shared through the platform).

2) General scenarios and scientific problems

General scenarios of interoperability are directly related to identified correlations between the different modules of Plate-form(E)3. When scientific problems are defined at this level, generic scenarios are taken into account, namely, definitions of corresponding scientific problems are specialized with consideration of these correlations. It is proposed to distinguish between two types of interopera-tions within Plate-form(E)3 architecture: custom and native.

Custom interoperations are related to a fact that diversity of tools, of both closed and open architecture (both, commercial and custom), exists in the environment where these interoperations need to be achieved. More important, custom interoperations are related to a possibility to introduce some new tools of unknown capability to interoperate to the environment, probably even after the Plateform(E)3 prototype is released.

Native interoperations are the ones that occur between known groups of software tools or modules, whether of open or closed architecture, with natively ensured interoperation capability; or between the tools or modules where there is possibility to natively develop this capability.

Obviously, native interoperability is more related to software integration, while custom interoperability needs approaches with increased level of flexibility.

3) A preliminary architecture for the platform A preliminary structure of the platform is represented in Figure 2. This structure is a conceptual solution to the scientific problems presented before and can be functionally defined as follows.

Coloured symbols represent different interoperability issues. While the dark colour (Process integration) indicates the problems of higher priority, the light one (GIS integration) represents problems that are of lower priority and level of detail. This decision is justified by the estimated level of complexity, which is greater when a process integration framework is considered. For each of the illustrated connections, two different perspectives are considered: models (unifying models that consider a common perspective to the interoperable modules) and technical interoperability (including technical approaches, data formats, interfaces).

The user interface module allows one user to put some information into the system and to define the optimisation problem (optimisation criteria/objectives, constraints…). Moreover through this interface, the user can access to the different services offered by the platform and the other modules. This user interface must also give to the user all the information necessary for decision aiding by calling the visualisation module that gives some relevant indicators in a dashboard.

The process integration module is able to connect to and to call some external specific tools for modelling/simulating processes defined by the user. Moreover, this module must be able -for solving the energetic integration problem for processes -to integrate also all the obtained models in a coherent way without loss and misunderstanding. We can distinguish the integration when we are in a territory scale or when we are in a process/plant scale. Territory scale problem concerns the integration in terms of considering multiple processes of the different plants. In contrast, process/plant scale problem focuses on a single process, while different components (heat exchangers…) of the different existing simulation tools and libraries may be taken into consideration for its optimisation.

The optimisation module solves the mono-objective or multi-objective problem defined by the user through the user interface. For defining criteria and constraints, this module will connect with the model obtained by the integration module.

The visualisation module gives to the user, through the user interface, an illustration of the relevant indicators for decision aiding and decision itself, based on the results of the optimisation and the models that are given by the process integration module. This module can also connect to the GIS module if geographical data are relevant considering the predefined use case.

The GIS integration module will be invoked for territory scale use cases if geographical data are relevant for solving the optimisation problem or for helping the user for taking its decision. Some examples of the relevant data are plant locations, landscape features, such as declination or natural obstacles, energy network geo-data, transport routes, etc.

All information, regarding the functionality of Plateform(E)3 is stored in a database for the persistence.

III. STATE-OF-THE-ART

This section presents an overview of the list of candidate technologies, models, tools, resources and approaches that are considered relevant for resolution of interoperability problems, as defined in the previous section. The candidate technologies are foreseen as the possible building blocks of the future interoperability solution. This overview only presents the basic features of the technologies with arguments about possible relevance for the future interoperability solution.

Figure 3 gives an integrated overview of the proposed candidate technologies with regard to the different subproblems. Indicated relationships illustrate already existing integration between technologies ("uses" relationship). It is important to highlight that this overview considers only Process Integration Framework of Plate-form(E)3 and the parts of Plate-form(E)3 architecture that are considered as core tools -related to integrated simulation and optimisation. Each analyse of technology will conclude with a discussion about the relevance of this technology for Plate-Form(E)3.

A. Candidate technologies for Process Integration Framework 1) CAPE-OPEN

: Open industry standard for process simulation software CAPE-OPEN [START_REF] Belaud | Open software architecture for process simulation: The current status of CAPE-OPEN standard[END_REF] is an open industry standard for interoperability of CAPE (Computer Aided Process Engi-neering) software tools; it is maintained by CAPE-OPEN Laboratories Network (CO-LaN). It was developed in a joint EU initiative Global CAPE-Open (1997-99), later also endorsed by IMS (which gave it a global reach). Initiative combined similar efforts of BP (EU project PRIMA) and BASF (German consortium IK-CAPE).

CAPE-OPEN defines rules and interfaces that allow CAPE applications or components to interoperate. This interoperation is achieved by combining the different socalled Process Modelling Components (PMC) in modelling the process in specific Process Modelling Environment (PME). PMC is a software component which is intended to carry out a narrow, well-defined function such as the computation of physical properties, the simulation of a particular unit operation, or the numerical solution of certain types of mathematical problems arising in process simulation or optimisation. Some examples of PMCs are heat exchanger design models, pump models, distillation models, mixer/agitator calculators, safety relief design calculators, etc. Process Modelling Environment (PME) is a software tool that supports the design of a process model either from scratch or from libraries of existing models, or both. They then allow the user to perform a variety of different tasks, such as process simulation or optimisation, using this single model of the process. Interoperation is supported by CAPE middleware, implemented by using Microsoft COM, OMG CORBA or .NET technology. CAPE-OPEN is the ultimate solution for syntactic interoperability of process modelling and simulation tools, endorsed by the industries. It is supported by the wide range of the different existing tools, such as Aspen, ProSim, SimSci, Belsim and many others. It seems like a main candidate for a resolution of interoperability problem at process scale.

2) CLiP : Conceptual Lifecycle Process Model

CLiP is a comprehensive data model for process engineering [START_REF] Bayer | Towards integrated information models for data and docum ents[END_REF]. It is developed with an objective to generalize, extend and integrate different existing models for chemical engineering [START_REF] Bayer | Integration of data models for process design -first steps and experiences[END_REF].

Both interoperability problems are related to a process paradigm. CLiP seems like a prime candidate for modelling chemical industry processes, since it generalize, extends and integrates different existing models. CLiP is also used as a basis for development of OntoCAPE ontological framework.

3) OntoCAPE : Large-scale ontology for the domain of Computer-Aided Process Engineering (CAPE)

OntoCAPE5 captures consensual knowledge of the process engineering domain in a generic way such that it can be reused and shared. Some possible applications of On-toCAPE include the systematic management and retrieval of simulation models and design documents, electronic procurement of plant equipment, mathematical modelling, as well as the integration of design data from distributed sources. OntoCAPE can be characterized as a formal, heavyweight ontology, which is represented in the OWL modelling language. OntoCAPE has been subdivided in layers, which separate general knowledge from knowledge about particular domains and applications.

OntoCAPE is exhaustive semantic information model for data integration across the chemical process design. It can be a reference for integration and management of distributed design data, namely process designs of the different plants. Thus, it is considered as relevant for territory scale interoperability problem. Also, it is used as reference ontology for automated decision making related to configuration of the processes (see COGents).

B. Candidate technologies for core Plate-form(E)3

1) Modelica: Multi-domain modeling language for component-oriented modeling of complex systems Modelica6 is an object-oriented, declarative, multi-domain modelling language for component-oriented modelling of complex systems, e.g., systems containing mechanical, electrical, electronic, hydraulic, thermal, control, electric power or process-oriented subcomponents. Modelica is a modelling language rather than a conventional programming language. Its classes are not compiled in the usual sense, but they are translated into objects which are then exercised by a simulation engine. The simulation engine is not specified by the language, although certain required capabilities are outlined.

Modelica is used to develop platforms that could be applied for integrated modelling and simulation. Hence the relevance for territory scale interoperability problem. Examples of these platforms are OpenModelica7 and JModelica8 .

2) OSMOSE :

A tool for the design and analysis of integrated energy systems OSMOSE 9 (Acronym for Multi-Objective Optimisation of integrated Energy Systems) is a Matlab platform designed for the study of energy conversion systems. The platform allows linking several software, for flowsheeting (Belsim, Vali, Aspen Plus), energy integration (Easy, GLPK), optimisation (MOO), and lifecycle impact assessment (Ecoinvent). Among other features, OSMOSE offers a complete suite of computation and results analysis tools (optimisation, sensitivity analysis, Pareto curve analysis ...).

OSMOSE is a solution for integrated energy management, which is a core of the interoperability problems at the territory level (second type).

3) CERES Platform

A CERES software platform is developed in scope of CERES-2 project10 , funded by ANR. Its objective is to optimise waste and heat recovery in industrial processes and achieve energy integration. It is developed in C++ and it is using OpenModelica, actually Modelica API as modelling and simulation environment.

CERES is already considered as one of the main candidates for integration platform, in specific for addressing process-scale interoperability. Interfaces with simulation platforms will be additionally investigated. It seems that the efficiency of these interfaces could be significantly improved if CAPE-OPEN is considered as a wrapper.

C. Other candidate technologies, approaches and tools 1) ISO15926 11 : Industrial automation systems and integration -Integration of life-cycle data for process plants including oil and gas production facilities

While the above models consider processes in process industries as focal modelling paradigms, ISO15926 aims at providing artefacts for modelling technical installations and their components. The objective of ISO15926 (developed as extension of STEP principles to long-life process plants) is to facilitate effective and efficient exchange and reuse of complex plant and project information, or in specific to mitigate the current high costs of rekeying and reformatting information to move it from one proprietary system to another. It is mostly related to providing models for equipment and their properties. ISO 15926 acts like an interpreter between two otherwise incompatible systems, by translating the descriptions of plant objects from one company's database to that of another. In doing so, the meaning of all the terms is being maintained, independently of the context.

Setup for the process industries with large projects involving many parties, and involving plant operations and maintenance could take a long time. Optimising existing processes by replacing an existing component (processscale interoperability problem) or by adding components which could facilitate energy integration (territory-scale) assumes procurement of the installation component, or at least exchange of the information which is sufficient to define the requirements for this component. Obviously, establishment of the correspondences between process and equipment models could contribute to facilitating the collaboration between the relevant systems (e.g. for process modelling and procurement). Existing formal representations of ISO15926 [START_REF] Batresa | An upper ontology based on ISO 15926[END_REF] could reduce the efforts in making these correspondences.

Plate-form(E)3

User interface

2) COGents : Semantic approach to CAPE web service choreography COGents project proposed the approach to dynamic CAPE services composition [START_REF] Braunschweig | CAPE web services: The COGents way[END_REF], where a number of software agents collaborate to configure a process model, according to the users' requirements, defined by using OntoCAPE ontology. Namely, agents are used as CAPE web services choreographers. Typical use of this approach is as following: The user defines a Modelling Task Specification (MTS) in OntoCAPE format to describe the unit he/she requires in term of functionality and parameters (of the underlying tool, e.g. HYSYS). Then, library and match maker agents find the appropriate unit operation using the generated MTS file.

COGents provide automated support for configuration/generation of process model, on demand, based on the user's requirements.

3) Jacaranda

Jacaranda 12 is a system for process synthesis, or automated process design, intended for conceptual or early stage design [START_REF] Fraga | An objectoriented framework for process synthesis and optimization[END_REF]. It aims to provide the support necessary for creative and exploratory design, helping the engineer to identify the important issues and constraints for a given design problem.

Jacaranda is a solution for automated process design. Therefore, it may be a candidate technology for generating cross-plant processes in territory scale interoperability problem. It is also used in COGents project as optimisation platform [START_REF] Braunschweig | CAPE web services: The COGents way[END_REF].

IV. DISCUSSION

Based on the previous State-of-the-art, this section shows how CAPE-Open should be used in PFE3 as one of the candidate technologies for resolution of process-scale interoperability problem of PlateForm(E)3. In fact, CAPE-OPEN interfaces between CAPE (Computer-Aided Process Engineering) tools defined the primary means for establishing the systems interoperability in this domain. They are defined in EC sponsored effort (within two consecutive projects: CAPE-O P E N a n d G l o b a l C A P E -OPEN), with participating major industries and labs, thus gaining the global reach. Today, CAPE-OPEN represents widely accepted approach, methodology and specification for making the different CAPE tools and components interoperable. Reference [START_REF] Nougues | CAPE-OPEN as a mean to achieve interoperability of Simulation Components[END_REF] provided the list of CO-compliant CAPE tools. This list is not exhaustive because of the date of the publication. More detailed and updated list is maintained at co-lan.org website. Majority of the candidate tools for process modelling and simulation in Plate-form(E)3 architecture already provide some level of support to CAPE-OPEN integration. However, the following archi-12 http://www.ucl.ac.uk/~ucecesf/jacaranda.html tecture is only a potential architecture that is not a final choice for the project. In this section, a description of CAPE objects, by CAPE-OPEN standard is provided, together with the methodology and illustrations of some interfaces. The proposed architecture is made on basis of the high-level architecture, presented in figure 2. It elaborates in more detail a Process Integration Framework component of Plateform(E)3, in context of possible use of CAPE-OPEN interfaces to exploit the external process modelling and simulation tools. This elaborated architecture is illustrated on Figure 4. Process Integration Framework (PIF) is a part of the Plate-form(E)3 architecture whose role is to connect to and invoke some services offered by the external tools, used for process modelling and simulation. In context of CAPE-OPEN integration, Process Integration Framework s h o u l d i m p l e m e n t f u n c t i o n s w h i c h a r e u s i n g C A P E -OPEN interfaces to access the above services. The functions are part of so-called Process Integration Framework Application Programme Interface (PIF API). It is assumed that this approach is possible under condition that the above tools are CAPE-OPEN compliant. This implies that before final selection of the technology used to implement Process Integration Framework, a detailed analysis of the CO-compliance of the final choice of process modelling and simulation tools (to embed to, or to use within Plate-form(E)3) must be carried out. Despite possible non-compliance situations, CAPE-OPEN must be carefully considered, since it is today's de facto industrial standard for interoperability of process applications. In this context, the PIF acts as Process Modelling Environment (PME), namely a client or a socket, as it uses the CAPE-OPEN interfaces in order to request services from the external software. The process modelling and simulation tools, namely their open components, act as Process Modelling Components (PMC), or servers or plugs, since they are applications, wrapped with the CAPE-OPEN interfaces in order to expose their functionality. The list of these functions, namely contents of PIF API should be defined based on the specific interoperability cases. At this point, it is clear that they should be grouped according to the PMC classes they are communicating with. Process modelling and simulation tools which are parts of Plate-form(E)3 landscape provide PMC classes which can be used by Process Integration Framework, namely respective API modules: Properties API module, Unit operations API module, Numerical solvers API module and Flowsheet Analysis API module. These modules are interfaces which are wrapping the native implementations of the respective relevant functions in Optimisation module. They are using CAPE-OPEN objects, such as Thermo, Unit, Numerics and Simulator Executive objects. Two other modules are foreseen to provide supportive functions to PIF API. PMC registry functions module facilitate adding, editing and deleting PMCs, available to Plate-form(E)3 platform. Logging functions module track and store all activities related to using the different PMCs of the different process modelling and simulation tools, by the platform.

V. CONCLUSIONS AND FUTURE WORKS

The work presented in this paper is a first step in dealing with interoperability issues when having to interconnect some tools/methods/approaches in a software bus for modelling/simulating/optimising processes for energy efficiency at different scales: component/plant/territory. Based on an extensive state-of-the-art, a first architecture has been proposed based on CAPE-OPEN standard. The next step is to finalise the choice of the architecture (based on CAPE-OPEN standard or not), to develop this architecture and finally to extend it for dealing with interoperability issues when connecting some tools/models related to the different scales presented above.

Aknowledgement

This work has been partially funded by the program SEED 2012 from the French National Agency for Re-search ANR in the frame of the Plate-Form(E)3 project. The authors would like also to thank Dr. Milan Zdravkovic (University of Nis and Ingline D.O.O) for his support to this work.

3 Figure 1 .

 31 Figure1. Plate-Form(E)3 interoperation framework[START_REF] Aubry | A cross-scale models interoperability problem: the Plate-Form(E)3 project case study. 3rd industry Applications and Standard initiatives for Cooperative Information Systems for Interoperable Infrastructures[END_REF]

Figure 2 .

 2 Figure 2. Preliminary structure of Plate-Form(E)3

Figure 3 .

 3 Figure 3. Overview of the proposed candidate technologies

Figure 4 .

 4 Figure 4. Process Integration Framework architecture in CAPE-OPEN context

http://www.colan.org

http://www.avt.rwthaachen.de/AVT/index.php?id=730&L=1

[START_REF] Bayer | Towards integrated information models for data and docum ents[END_REF] https://www.modelica.

org/ 7 https://www.

openmodelica.org/ 8 http:/

/www.jmodelica.org/ 9 http://leni.epfl.ch/osmose

http://www.agence-nationale-recherche.fr/en/researchprogrammes/energie-durable/systemes-energetiquesefficaces-et-decarbones/funded-projecteesi/?tx_lwmsuivibilan_pi2[CODE]=ANR-10-EESI-0001