Luis Gustavo

Giacon Villani

Samuel Da Silva

Americo Cunha

Identification of a nonlinear beam through a stochastic model based on a Duffing oscillator

à la diffusion de documents scientifiques 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.

The system behavior can be approximated by a Duffing oscillator, considering the presence of uncertainties:

𝑥 𝜃, 𝑡 + 2𝜉 𝜃 𝜔 𝑛 𝜃 𝑥 𝜃, 𝑡 + 𝜔 𝑛 𝜃 2 𝑥 𝜃, 𝑡 + 𝐹 𝑛𝑙 𝜃, 𝑥 𝜃, 𝑡 = 𝑢(𝜃, 𝑡)

The nonlinear restoring force can be approximated by: 𝐹 𝑛𝑙 𝜃, 𝑥 𝜃, 𝑡 ≈ 𝛽 𝜃 𝑥 𝜃, 𝑡 3

Identification of the Nonlinear Beam Final Remarks

• The results have showed that the studied system can be well approximated by a Duffing oscillator; • The stochastic approach allows the model to represent the system behavior in different days and situations with statistical confidence. • The test was also repeated 320 times with sampling frequency of 1024 Hz and 4096 samples.

6thFigure 3 :

 3 Figure 1: Photo.

Figure 4 :

 4 Figure 4: PDF of linear parameters. (a): PDF of 𝜉 mean = 0.0175 . (b): PDF of 𝜔 𝑛 mean = 23 Hz .

Figure 5 :

 5 Figure 5: Nonlinear coeficient identification. (a): 𝐹 𝑛𝑙 𝜃, 𝑥 𝜃, 𝑡 . (b): PDF of 𝛽(mean = 1.35x108 N/m 3 kg).

Figure 7 :

 7 Figure 7: Confidence bands of stepped sine test.

Figure 2 :

 2 Figure 2: Scheme.


Aymen Gammoudi
email: aymen.gammoudi@irisa.fr

Daniel Chillet
email: daniel.chillet@irisa.fr

Mohamed Khalgui
email: khalgui.mohamed@gmail.com

Adel Benzina
email: adel.benzina@isd.rnu.tn

Mapping of Periodic Tasks in Reconfigurable Heterogeneous Multi-Core Platforms

Keywords: Heterogeneous multi-core platform, Reconfiguration, Task mapping and scheduling

Multi-core Real-time Systems (MRS) powered by a battery have been adopted for a wide range of high performance applications, such as mobile communication and automotive systems. A system is composed of N dependent and periodic Operating System (OS) tasks to be assigned to p heterogeneous cores linked by a network-on-chip (NoC). This paper deals with the problem of task allocation in MRS in such a way that the cost of communication between cores is minimized by trying to place the dependent tasks as close as possible to each other. The main objective is to develop a new strategy for allocating N tasks to p cores of a given distributed system using task clustering by considering both the cost of inter task communication and that of communication between cores. The proposed strategy guarantees that, when a task is mapped into the system and accepted, then it is correctly executed prior to the task deadline. A novel periodic task model based on elastic coefficients is proposed to compute useful temporal parameters allowing to assign all tasks to p cores, by minimizing the traffic between cores. Experimental results reveal the effectiveness of the proposed strategy by comparing the derived solutions with the optimal ones, obtained by solving an Integer Linear Program (ILP).

INTRODUCTION

Multi-core real-time platforms typically are composed of multiple processors (processing units), memories, and a communication infrastructure. Heterogeneous multi-core platforms contain different types of processing units. Therefore, the system designers can take advantage of their properties when mapping tasks to specific processor types and optimize criteria such as computational performance, cost and energy consumption [START_REF] Schranzhofer | Dynamic power-aware mapping of applications onto heterogeneous mpsoc platforms[END_REF]. Several academic and industrial studies reported in [START_REF] Wang | Dynamic multiple-period reconfiguration of real-time scheduling based on timed des supervisory control[END_REF], [START_REF] Cecilio | Architecture for uniform (re) configuration and processing over embedded sensor and actuator networks[END_REF], [START_REF] Li | Qos-aware scheduling of services-oriented internet of things[END_REF] have addressed the dynamic reconfiguration of real-time systems. These approaches can be divided into two categories: manual applied by users [START_REF] Rooker | Zero downtime reconfiguration of distributed automation systems: The εcedac approach[END_REF]; and automatic applied by intelligent control agents [START_REF] Vrba | Capabilities of dynamic reconfiguration of multiagent-based industrial control systems[END_REF]. The most promising approach is the elastic scheduling reported in [START_REF] Wang | Dynamic multiple-period reconfiguration of real-time scheduling based on timed des supervisory control[END_REF], [START_REF] Wang | Dynamic low-power reconfiguration of real-time systems with periodic and probabilistic tasks[END_REF], [START_REF] Marinoni | Elastic dvs management in processors with discrete voltage/frequency modes[END_REF], [START_REF] Buttazzo | Elastic task model for adaptive rate control[END_REF].

A multi-core real-time system, denoted MRS, can be implemented by N reconfigurable real-time dependent and periodic tasks to be assigned to p heterogeneous cores linked by a network-on-chip (NoC) [START_REF] Hu | Energy-and performance-aware mapping for regular noc architectures[END_REF] in order to ensure the communication between dependent tasks. Since we consider a heterogeneous platform, each task cannot be executed by all cores, it can be supported only by one or more specific cores according to system specification. Similarly to the research works reported in [START_REF] Wang | Dynamic multiple-period reconfiguration of real-time scheduling based on timed des supervisory control[END_REF], [START_REF] Marinoni | Elastic dvs management in processors with discrete voltage/frequency modes[END_REF], we consider a more flexible task model, in which the tasks can operate within a given range of periods with different performances. A reconfiguration scenario is defined in this paper as any internal or external event that leads to the addition and/or removal of periodic tasks as well as their exchanged messages to adapt the system's behavior to its environment [START_REF] Quadri | Expressing embedded systems configurations at high abstraction levels with uml marte profile: Advantages, limitations and alternatives[END_REF]. In this paper, we are interested basically in reconfiguration scenarios that add new software tasks. New tasks must be assigned to their appropriate cores by trying to place the depen-dent tasks as close as possible to each other in order to reduce the traffic on the NoC. Therefore the energy consumption, proportional to the data communication volume, will be decreased. As partitioned scheduling converts the problem of scheduling realtime tasks into a set of uniprocessor scheduling problems [START_REF] Baruah | Scheduling realtime tasks: Algorithms and complexity[END_REF], we decided to select earliest deadline first (EDF) scheduler to schedule the local tasks for each core.

For two new added dependent tasks assigned to different cores, a new periodic message is added automatically to the NoC. Consequently, the real-time constraints can be not satisfied when a task misses the related deadline and a message can take a long time to arrive to its destination. Therefore, the system MRS will be unfeasible. An MRS is feasible if and only if it satisfies two constraints: (i) the deadlines of the tasks, and (ii) the messages' deadlines on the communication medium. Moreover, the provided solutions must be optimal real-time ones that minimize the power consumption of system.

The general goal of this paper is to propose a new mapping strategy based on grouping heavily communicating tasks into the same cluster. The tasks that are grouped into the same cluster are assigned to the same core while keeping its processor utilization coefficient less than or equal to 1 and the communication bus is feasible. Whenever these constraints are not satisfied, the proposed strategy offers two solutions (A and B) based on the modification of temporal parameters of the processed tasks to meet the real-time and communication constraints. If after assigning the new task to core C j , the real-time constraint is violated, then the proposed strategy starts by modifying the periods of tasks and the exchanged messages until reaching their specific maximal periods (Solution A) in order to decrease the processor utilization of C j . If the second constraint is also violated after assigning one or more new tasks, then the proposed strategy applies the second solution (Solution B) that modifies the message's period and the associated tasks to slow down the communicating tasks to satisfy the communication constraint. To evaluate this strategy, we formalize the problem as an optimization problem by using integer linear programming (ILP) and compare the proposed solutions with the optimal results provided by the CPLEX solver (CPLEX, 2013). The originality of this paper is to propose a new strategy of mapping and scheduling tasks in reconfigurable architectures. The proposed strategy looks for the near optimal placement of tasks on cores after any reconfiguration scenario in order to minimize the traffic on the NoC. The proposed strategy is deterministic since it is able to find the suitable solutions for each situation.

The rest of this paper is organized as follows: Section 2 reviews some related works. Section 3 presents the system model and the used terminologies. We formalize the considered problem in Section 4. The proposed strategy is presented in Section 5 that deals with the modification of temporal parameters of the processed tasks to guarantee the related real-time and communication constraints after any reconfiguration scenario. The strategy is implemented, simulated and analyzed in Section 6. Finally, Section 7 concludes this work.

RELATED WORK

Reducing the cost of communication between cores becomes a major concern for the highperformance and reliability of such systems. Several academic studies reported in [START_REF] Carle | From dataflow specification to multiprocessor partitioned time-triggered real-time implementation[END_REF], [START_REF] Bhardwaj | An effective load balancing task allocation algorithm using task clustering[END_REF], [START_REF] Tosun | An ilp formulation for application mapping onto network-on-chips[END_REF] have addressed the mapping algorithms using task clustering by taking both inter task communication and execution costs. The basic idea of clustering based algorithm in [START_REF] Bhardwaj | An effective load balancing task allocation algorithm using task clustering[END_REF], [START_REF] Tosun | An ilp formulation for application mapping onto network-on-chips[END_REF] is to group heavily communicating tasks into the same cluster. The tasks that are grouped into the same cluster are assigned to the same processor in an effort to avoid communication costs. These algorithms are interesting since the communication cost is reduced, but the authors are not interested in the verification of the processor utilization after assigning the tasks. In certain cases, the processor utilization exceeds 100%. In addition, they are not interested to check the overflow on the communication medium. To resolve these two problems, effective solutions based on the modification of WCETs, deadlines, and periods of tasks in order to verify the processor utilization after any assignment of tasks are reported in [START_REF] Gammoudi | New pack oriented solutions for energyaware feasible adaptive real-time systems[END_REF], [START_REF] Wang | Dynamic multiple-period reconfiguration of real-time scheduling based on timed des supervisory control[END_REF], [START_REF] Wang | Dynamic low-power reconfiguration of real-time systems with periodic and probabilistic tasks[END_REF], [START_REF] Gharsellaoui | Reconfiguration of synchronous real-time operating system[END_REF], [START_REF] Marinoni | Elastic dvs management in processors with discrete voltage/frequency modes[END_REF].

The work presented in [START_REF] Wang | Dynamic low-power reconfiguration of real-time systems with periodic and probabilistic tasks[END_REF] proposes a feasible low-power dynamic reconfiguration of real-time systems where addition and removal of tasks are applied at run-time. Three solutions are presented to cut-down the energy consumption after any reconfiguration scenario. The authors propose to prolong the periods (or reduce the WCETs) of tasks by assigning a single value to all the tasks in order to re-obtain the system feasibility. Recently, the work reported in [START_REF] Gammoudi | New pack oriented solutions for energyaware feasible adaptive real-time systems[END_REF] improves these solutions by proposing a new approach based on the modification of task parameters with classification in packs by assigning a unique period (or WCET) to all the tasks related to the same pack. Each pack is a group of tasks having "similar" periods (or WCETs). For each reconfiguration scenario, specific modifications are performed on the parameters of the packs and their related tasks in order to meet the real-time and energy constraints. In the research work reported in [START_REF] Gammoudi | Reconf-pack: A simulator for reconfigurable battery-powered real-time systems[END_REF], the authors develop the Recon f -Pack simulator to evaluate and compare these two approaches by generating a large number of random systems and reconfiguration scenarios for each one. The authors show that the total cost introduced by applying the solution presented in [START_REF] Wang | Dynamic low-power reconfiguration of real-time systems with periodic and probabilistic tasks[END_REF] in 88% of random cases is largely higher than that introduced by the method reported in [START_REF] Gammoudi | New pack oriented solutions for energyaware feasible adaptive real-time systems[END_REF]. To show that the pack solution, proposed in [START_REF] Gammoudi | New pack oriented solutions for energyaware feasible adaptive real-time systems[END_REF], can be implemented in a real application, the work reported in (Gammoudi et al., 2016a) proposes a new reconfigurable middleware, named Recon f -Middleware, that presents a plugin implemented in RTLinux and describes the transition from the pack theory to the implementation. An extension of the technique reported in [START_REF] Gammoudi | New pack oriented solutions for energyaware feasible adaptive real-time systems[END_REF] to homogeneous multi-core platforms is described in [START_REF] Gammoudi | Real-time scheduling of reconfigurable battery-powered multi-core platforms[END_REF]. The authors propose four solutions to schedule a real-time application composed of independent periodic tasks under energy constraints. Nevertheless, they do not consider the scheduling of dependent tasks onto heterogeneous platforms and they do not treat the influence of the task mapping on the communication and therefore on the energy consumption.

SYSTEM MODEL AND ASSUMPTIONS

In this section, we present the task model and the platform architecture that consists of a reconfigurable MRS composed of N periodic OS tasks executed by p heterogeneous cores. We also present the models of the processor architecture and the communication between cores.

Task Model

We suppose that MRS processes a task set Π containing N periodic tasks, i.e., Π = {τ 1 , τ 2 , ..., τ N }. Some tasks are considered as flexible, whose utilization can be modified by changing their periods within a specified range. According to [START_REF] Wang | Dynamic multiple-period reconfiguration of real-time scheduling based on timed des supervisory control[END_REF], [START_REF] Marinoni | Elastic dvs management in processors with discrete voltage/frequency modes[END_REF], [START_REF] Buttazzo | Elastic task model for adaptive rate control[END_REF], a periodic task τ i is characterized by: (i) a release time A i , (ii) a worst-case execution time (WCET) W i , (iii) a relative deadline D i , (iv) a period T i , and (v) a maximum tolerable period T i max . The relative deadline of a periodic task is considered as a hard deadline if its missing is unacceptable [START_REF] Baruah | Scheduling realtime tasks: Algorithms and complexity[END_REF]. According to [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF], assuming that the period is equal to the deadline for each task, the tasks are schedulable if and only if the processor utilization coefficient is less than 1. Hence, we apply in this paper the EDF policy to schedule the local tasks for each core.

Platform Model

Let the considered MRS consists of a set of p heterogeneous cores Γ={C 1 ,C 2 , ...,C p }, interconnected by communication links. Since we consider heterogeneous platforms, we suppose that each task τ i can be executed by one or more specific cores according to system specification. Hence, we define the matrix γ that represents the different possibilities to execute tasks on cores.

γ i, j = 1 τ i can be executed by C j . 0 otherwise.

In order to ensure that all the tasks are mapped on the cores, we define the mapping matrix H where

H i, j = 1 if task τ i is running on core C j . 0 otherwise.

Communication Model

Each core runs periodic OS tasks which can exchange messages on the NoC [START_REF] Khemaissia | New methodology for feasible reconfigurable real-time network-on-chip noc[END_REF], [START_REF] Hu | Energy-and performance-aware mapping for regular noc architectures[END_REF]. We denote in the following by M i, j , the message to be exchanged between a pair of tasks τ i and τ j . According to [START_REF] Bui | Realtime scheduling of concurrent transactions in multidomain ring buses[END_REF] the communication model is based on: (i) a regular interarrival time T M i, j , (ii) a spent time to transmit a message W M i, j , (iii) an absolute deadline DM i, j , and (iv) an amount of exchanged data SM i, j (in bits). We consider that the period T M i, j of message M i, j is equal to the period T i of the related sending task τ i (T M i, j =T i ).

If the task's period is changed, then the periods of the related messages will be changed implicitly.

The NoC architecture implies a communication cost between each pair of cores depending on the distance between them. We model each NoC architecture by a specific cost matrix called Cost such as

Cost C k ,C l = X C k ,C l if k = l, ∀ k, l ∈ [1..p]. 0 otherwise.
where X C k ,C l is the cost (e.g. energy) of sending one bit from core C k to core C l .

To calculate the cost of communication between each pair of cores C k and C l , it is necessary to multiply the volume of exchanged data by Cost C k ,C l . Then, the total cost of communications (in units of cost) is given by

TotalCost = p ∑ k=1 p ∑ l=1 N ∑ i=1 N ∑ j=1 SM i, j * Cost C k ,C l * H i,k * H j,l
(1) We suppose, in this paper, that the energy consumed by the communication is proportional to the distance between cores.

Processor Utilization Model

According to [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] the processor utilization U C j of core C j is given by

U C j = N ∑ i=1 W i T i * H i, j ; ∀ j ∈ [1..p] (2)
The core C j is feasible, if and only if

U C j ≤ 1; ∀ j ∈ [1..p] (3)
Eq. 3 is the real-time constraint.

According to the works reported in [START_REF] Bui | Realtime scheduling of concurrent transactions in multidomain ring buses[END_REF], [START_REF] Khemaissia | Reconfigurable can in real-time embedded platforms[END_REF], [START_REF] Khemaissia | New methodology for feasible reconfigurable real-time network-on-chip noc[END_REF], to evaluate the communication feasibility between two cores, the related medium is considered as a virtual processor. Based on this hypothesis, the utilization of the communication medium between two cores C k and C l , denoted U Com (C k ,C l ), is given by

U Com (C k ,C l ) = N ∑ i=1 N ∑ j=1 W M i, j T M i, j * H i,k * H j,l ; ∀k, l ∈ [1..p]
(4) According to the work reported in [START_REF] Khemaissia | New methodology for feasible reconfigurable real-time network-on-chip noc[END_REF], to ensure that the communication between cores that are physically close is feasible, it is necessary to check

U Com (C k ,C l ) ≤ 1; ∀k, l ∈ [1..p] | Cost C k ,C l = 1 (5)
Eq. 5 is the communication constraint.

PROBLEM FORMULATION

The problem, being addressed in this paper, is concerned with an optimal allocation of the tasks to the cores after any reconfiguration scenario. An optimal allocation is considered as one that minimizes the cost of communication between cores such that the realtime and communication constraints are satisfied. We present, in this section, the formulation of the mapping problem and formalize each constraint as an optimization problem by using ILP.

Mapping Problem

We suppose that at time

t i MRS is composed of Γ(t i ) = {C 1 ,C 2 , ...,C p } and Π(t i ) = {τ 1 , τ 2 , ..., τ n 1 }.
An MRS is feasible if and only if it satisfies the two constraints (real-time and communication constraints). We assume in the following that MRS is dynamically reconfigured at time t k (t k > t i ) by adding n 2 tasks. Therefore, the new implementation of tasks is Π(t k ) = {τ 1 , τ 2 , ..., τ n 1 , τ n 1 +1 , ..., τ N }, with N = n 1 + n 2 . The new tasks provided by this reconfiguration must be mapped to their appropriate cores. We consider, in this paper, that the initial mapping at time t 1 is also a reconfiguration scenario such that Π(t 0 ) = {∅} and Π(t 1 ) ={∅}.

To guarantee that each task is executed at most by one of its appropriate cores, it is necessary to satisfy

p ∑ j=1 H i, j * γ i, j = 1; ∀i ∈ [1..N] (6)
We need to assign all the old/new tasks to their appropriate cores by minimizing the cost of communication between them. This idea is formalized by

RE                                      Minimize TotalCost s.t. U C j ≤ 1, ∀ j ∈ [1..p] (Eq.3) U Com (C k ,C l ) ≤ 1 | Cost C k ,C l = 1 (Eq.5) ∀ k, l ∈ [1..p] ∑ p j=1 H i, j * γ i, j = 1, ∀ i ∈ [1..N] (Eq.6)
where, TotalCost is calculated by Eq.1. Eq.3 satisfies the real-time scheduling under the EDF policy for each core, Eq.5 ensures that the communication between the cores C k and C l is feasible and Eq.6 ensures that each task is executed at most by one of its appropriate cores. The RE problem can be solved by integer linear programming solvers such as CPLEX (CPLEX, 2013), which is hard to be implemented in an embedded platform since it is too complex to be executed on-line. We note that this solver does not produce any solution if one or more constraints are not satisfied. To solve the problem RE, it is necessary that all the constraints are satisfied. We suppose that ILP is only used to compute the optimal solution to have a comparison reference for the heuristic we will propose later. After different reconfiguration scenarios, one or more of these constraints can be violated and ILP cannot provide a solution for that situation.

Real-time Problem

After assigning one or more tasks on C j , the processor utilization of C j will increase and it can be unfeasible

(U C j > 1). Since U C j = ∑ N i=1 W i T i * H i, j ; ∀ j ∈ [1..p],
we propose first of all to modify the periods of the local OS tasks in order to decrease the processor utilization. The idea is to extend the periods of tasks until they reach T i max . Using the ILP model, we formalize this problem by

∀ j ∈ [1..p] | U C j > 1 Pb1 =                      Minimize ∑ N i=1 ∆T i * H i, j s.t. ∑ N i=1 W i T i + ∆T i * H i, j ≤ 1 T i + ∆T i ≤ T i max , ∀ i ∈ [1..N]
where ∆T i is an integer that extends the period of the real-time tasks. This formalization exploits the possible flexibility of the periods in order to reduce the processor utilization.

Communication Problem

After the addition of a pair of dependent tasks on two cores, a periodic message will be added to the NoC and should respect a corresponding deadline related to these tasks. Then, it is necessary to verify the feasibility of the communication between each pair of cores C k and C l (k, l ∈ [1..p]). According to Eq. 5, if U Com (C k ,C l ) is greater than 1, then the communication between these two cores is not feasible. In order to solve this problem, we propose to modify the period of messages exchanged between the tasks running on cores C k and C l . The idea here is to slow down the communicating tasks to satisfy the communication constraint. We can formalize this problem by

∀ k, l ∈ [1..p] | U Com (C k ,C l ) > 1 Pb2 =                      Minimize ∑ N i=1 ∑ N j=1 ∆T M i, j * H i,k * H i,l s.t. ∑ N i=1 ∑ N j=1 W M i, j T M i, j + ∆T M i, j * H i,k * H i,l ≤ 1 T M i, j + ∆T M i, j ≤ T i max , ∀ i, j ∈ [1..N]
where ∆T M i, j is an integer value that extends the period of message M i, j (with M i, j =T i ).

Pb1 and Pb2 can be solved by CPLEX (CPLEX, 2013) that provides an optimal solution since it seeks for each task and message the suitable and exact modification with a minimal cost. Nevertheless, it is not reasonable to implement an ILP solver in an embedded system. Therefore, we present in the next Section some efficient and implementable heuristics and we compare them to the optimal solutions provided by the CPLEX solver to solve these problems.

CONTRIBUTION

When the configuration (or reconfiguration) scenario is applied, each new task must be assigned to its appropriate core by minimizing the cost of communication. We present in the next subsection a mapping strategy based on grouping heavily communicating tasks into the same cluster. The tasks that are grouped into the same cluster are assigned to the same core such that its processor utilization coefficient is less than or equal to 1 and the communication bus is feasible.

Proposed Task Allocation Algorithm

Before presenting the allocation algorithm, we introduce some definitions: SingleCore task: any task that can be executed only by one specific core. Example : τ 2 in Fig. 1. Cluster (CL): a group of communicating tasks. Example : τ 1 , τ 2 and τ 3 are grouped in CL 1 (Fig. 1). Common Processor (CP): a processor that can execute all tasks of a cluster CL such that its processor utilization is less than or equal to 1. Example : C 1 can be the CP of CL 1 . C 2 and/or C 4 can be the CP of CL 2 (Fig. 1). CPCL: we denote by CPCL each cluster CL that has a common processor CP. Data Traffic (TD): is the total volume of data exchanged between tasks in CL. Example : T D(CL 1 ) = TU * ( data1 + data2 T 1 ) and T D(CL 2 ) = 0 (Fig. 1).

The global structure of the proposed strategy is presented in Fig. 2 and is based on three main steps:

Step 1: Assign all the SingleCore tasks.

Step 2: Assigning the communicating tasks that have a common processor CP:

Step 2.1: Each group of communicating tasks are grouped in a cluster CL.

Step 2.2: Calculate the data traffic (TD) for each CL.

Step 2.3: Sort all the CL in a descending order according to their TD.

Step 2.4: A CL that has a CP will be denoted by CPCL. The list of all CPCLs called LCPCL.

Step 2.5: Assign the tasks of each CPCL.

Step 3: Assigning the tasks of CL as close as possible.

Step 3.1: Take the CL that has a highest TD.

Step 3.2: Place each task on the best position (in term of communication cost).

The detailed structure of the proposed strategy is presented in Fig. 3. Its objective is to find the near optimal mapping of the tasks on cores in order to optimize the energy consumption while meeting temporal and communication constraints. Communicating tasks are placed as close as possible. The proposed strategy solves the problem formalized by RE in sub-section 4.1. As shown in this figure, the proposed strategy takes the task's characteristics, the matrix γ, the matrix of architecture Cost and the size of exchanged messages as inputs and outputs the mapping of the tasks on the architecture.

After assigning the new tasks, the processor utilization of certain cores will certainly increase. If the new utilization is greater than 1, then the realtime constraint is violated as reported in [START_REF] Wang | Dynamic low-power reconfiguration of real-time systems with periodic and probabilistic tasks[END_REF], [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]. Besides, the communication constraint can be violated after the addition of tasks and consequently MRS will be unfeasible. To solve these two problems that have been formalized in 4.2 and 4.3, we present two solutions in the next subsection.

Task Scheduling for Feasible Reonfigurable Platforms

We propose two heuristics based on grouping the tasks that have "similar" periods in several packs, denoted Pack, to re-obtain the system feasibility. After a reconfiguration, we do not calculate a new period for each task, but assign a new one period to all tasks of the first pack Pack 1, j ( j ∈ [1..p]). Moreover, all the new periods affected to the tasks of pack Pack x, j are multiple of the one affected to the tasks of Pk 1, j . Hence, we have only to compute the suitable value Pk 1, j . We show in the following solutions how the tasks are grouped in packs.

Solution A: Modification of Periods under Real-Time Constraint

If C j ( j ∈ [1..p]) is not feasible after assigning some new tasks to it, then we propose to extend the periods of tasks that run on C j . In order to satisfy the real-time constraints, we assign each task to pack Pack T x, j according to its period. To construct the packs, we need to find the suitable new period Pk T 1, j that minimizes the cost of the new solution for the whole system. We formalize this problem by

               Min ∑ N i=1 (Pk T 1, j -(T i mod Pk T 1, j )) mod Pk T 1, j * H i, j s.t. Pk T 1, j ≥ Min(T i ), ∀ i ∈ [1..N] | H i, j = 1
Once Pk T 1, j is calculated, we construct the packs of the system tasks as follows: Pack T x, j , x ≥ 1, includes the tasks that have a period in the range [(x -1) * Pk T 1, j + 1 ; x * Pk T 1, j ], x ∈ N + . The first value of x is 1 and when all tasks are affected, x is no more incremented. Hence, Pack T 1, j includes the tasks that have a period in the range [1 ; Pk T 1, j ], Pack T 2, j includes the tasks that have a period in the range [Pk T 1, j + 1 ; 2 * Pk T 1, j ], etc. To satisfy the real-time constraints under the EDF policy, it is necessary that ∑ N i=1 W i T i * H i, j ≤ 1. Since the periods are now multiple of the same value Pk T 1, j , we get

∑ τ i ∈Pack T 1, j W i Pk T 1, j + ... + ∑ τ i ∈Pack T x, j W i x.Pk T 1, j ≤ 1 thus, 1 Pk T 1, j *   ∑ τ i ∈Pack T 1, j W i + ... + ∑ τ i ∈Pack T x, j W i x   ≤ 1 then, Pk T 1, j ≥ ∑ τ i ∈Pack T 1, j W i + ... + ∑ τ i ∈Pack T x, j W i x
Since the periods are integer values, then,

Pk T 1, j =     ∑ τ i ∈Pack T 1, j W i + ... + ∑ τ i ∈Pack T x, j W i x     (7)
where Pk T 1, j is the new period affected to tasks of the first pack Pack T 1, j , x * Pk T 1, j to the tasks of x th pack Pack T

x, j . After adapting the tasks' parameters running on C j , all the tasks are executed without missing their deadlines. Therefore, the real-time constraint can be satisfied. As described in subsection 3.3, if the task's period is changed implicitly, then the message's period will be changed since T M i, j =T i . For that, the periods of messages that are associated to the adapted tasks will be changed.

Solution B: Modification of Message's Period under Communication Constraint

For two added dependent tasks assigned to different processors, a message is added automatically on the NoC, we are interested in this part in the communication feasibility.

If U Com (C k ,C l ) (∀ k, l ∈ [1..p]
) is greater than 1, then the communication between the cores is not feasible. We propose to extend the periods of exchanged messages between the tasks running on cores C k and C l . In order to satisfy the communication constraint, we assign each message to Pack T M x,k,l according to its period. We formalize this problem by

∀ k, l ∈ [1..p] | U Com (C k ,C l ) > 1                        Min ∑ N i=1 ∑ N j=1 (Pk T M 1,k,l -(T M i, j mod Pk T M 1,k,l )) mod Pk T M 1,k,l * H i,k * H i,l s.t. Pk T M 1,k,l ≥ Min(T M i, j ), ∀ i, j ∈ [1..N]
Once Pk T M 1,k,l is calculated, the packs of messages are processed such that Pack T M

x,k,l includes the messages that have a period in the range [(x -1) * Pk T M

x,k,l + 1 ; x * Pk T M 1,k,l ], x ∈ N + . To satisfy the communication constraint, it is neces-

sary that ∑ N i=1 ∑ N j=1 W M i, j T M i, j * H i,k * H j,l ≤ 1. Since
the periods T M i, j are now multiple of the same value Pk T M 1,k,l , we get

∑ M i, j ∈Pack T M 1,k,l W M i, j Pk T M 1,k,l + ... + ∑ M i, j ∈Pack T M x,k,l W M i, j x.Pk T M 1,k,l ≤ 1
Since the periods are integer, then,

Pk T M 1,k,l =     ∑ M i, j ∈Pack T M 1,k,l W M i, j + ... + ∑ M i, j ∈Pack T M x,k,l W M i, j x     (8)
where Pk T M 1,k,l is the new period affected to the messages of the first pack Pack T M 1,k,l , x * Pk T M x,k,l to the messages of x th pack Pack T M

x,k,l . After adapting the parameters of messages running on the communication bus between cores C k and C l , U Com (C k ,C l ) will be smaller than 1. Therefore, the communication constraint can be satisfied. Since the periods of messages are modified, it is necessary to adapt the periods of their sending tasks.

EXPERIMENTAL STUDY

We present in the first subsection a case study in which we calculate the communication cost through the use of the proposed strategy. In the second, we evaluate the performance of the strategy by generating a large number of random tasks.

Implementation of the Proposed Strategy

Example -1 In this example, we have considered a typical program made up of 10 executable tasks The WCET W i of each task is presented in Tab. 2 WCET

Cost = C 1 C 2 C 3 ↓ ↓ ↓   0 1 1 1 0 1 1 1 0   ← C 1 ← C 2 ← C 3
C 1 C 2 C 3 W 1 1 3 0 W 2 1 0 2 W 3 2 0 0 W 4 1 2 0 W 5 2 0 0 W 6 0 2 0 W 7 0 0 3 W 8 0 2 1 W 9 0 0 2 W 10 0 2 1
The matrix γ i, j that represents the different possi-bilities to execute tasks on cores is

γ = C 1 C 2 C 3 ↓ ↓ ↓                1 1 0 1 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 1 1                ← τ 1 ← τ 2 ← τ 3 ← τ 4 ← τ 5 ← τ 6 ← τ 7 ← τ 8 ← τ 9 ← τ 10
Step 1 Assign the SingleCore tasks: τ 3 , τ 5 , τ 6 , τ 7 and τ 9 are SingleCore tasks and they must be assigned.

Step 2 Assign the tasks of CPCL to their related common processor CP: Tab. 3 shows the clusters CPCL that have common processors CP and their data traffic T D.

Clusters Tasks TD CP CPCL

1 τ 1 , τ 2 , τ 3 13 C 1 CPCL 2 τ 4 , τ 5 10 C 1 CL 1 τ 6 , τ 7 , τ 8 14 - CL 2 τ 9 0 C 3 CL 3 τ 10 0 C 2 , C 3
The proposed strategy assigns CPCL 1 and CPCL 2 on C 1 .

Step 3 Assign the tasks of the CL: We start to assign the tasks of CL 1 because it has the highest T D. Since τ 6 and τ 7 are already mapped in step 1 to C 3 , the proposed strategy assigns τ 8 to C 2 (same core of the related task τ 6 ). The output of the proposed strategy is the mapping matix

H H = C 1 C 2 C 3 ↓ ↓ ↓                1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0                ← τ 1 ← τ 2 ← τ 3 ← τ 4 ← τ 5 ← τ 6 ← τ 7 ← τ 8 ← τ 9 ← τ 10
The total cost of communication TotalCost is 40 units of cost. The processor utilization of the cores after assigning tasks is presented in Tab. 4. At a particular time, the system undergoes the first reconfiguration by adding two tasks that are presented in Tab. 5.

W i of each new task. WCET C 1 C 2 C 3 W 11 0 2 0 W 12 1 0 1 γ = C 1 C 2 C 3 ↓ ↓ ↓ 0 1 0 1 0 1 ← τ 11 ← τ 12
The new inter task communication graph is illustrated in Fig. 5.

After assigning τ 11 on C 2 , since it is a SingleCore task, the processor utilization U C 2 = 1.102 > 1. The proposed strategy decreases U C 2 by applying Solution A, i.e., U C 2 equals to 0.933, and the new periods of tasks running on C 2 are presented in Tab. 7. Since the task τ 12 communicates with τ 1 , then the best position to place it, is C 1 (same core to τ 1 ). Thus, the processor utilization of C 1 after assigning τ 12 will be equal to 1.233. The proposed strategy begins by applying Solution A to decrease the processor utilization. After calculating the new periods, it appears that Solution A can not increase the periods of tasks running on C 1 because their T i max are not enough. Consequently, the proposed strategy proposes to assign τ 12 to the next core C 3 and U C 3 = 0.958. Thus, the new mapping matrix H is given by

H = C 1 C 2 C 3 ↓ ↓ ↓                    1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1                    ← τ 1 ← τ 2 ← τ 3 ← τ 4 ← τ 5 ← τ 6 ← τ 7 ← τ 8 ← τ 9 ← τ 10 ← τ 11 ← τ 12
The new total cost of communication TotalCost is equal to 40+20=60 units of cost.

Evaluation of Performance

In order to generalize the performance evaluation of the proposed strategy, we generate randomly tasks by using the developed tool Task -Generator presented in [START_REF] Gammoudi | Reconf-pack: A simulator for reconfigurable battery-powered real-time systems[END_REF]. The proposed strategy tries to form clusters of tasks and then allocate these clusters to the cores. The effectiveness of the proposed algorithm is compared with the optimal solution provided by the CPLEX solver (CPLEX, 2013). For several sets of input data (N, p), the comparison is shown in a tabular form as well as in a graphical form. Tabs. 8 and 9 illustrated in the form of Figs. 6 and 7 respectively.

It can be observed from Fig. 6 that the values of total cost obtained by the proposed strategy are near to those obtained by the optimal solution, in the case, when the number of cores is kept fixed and number of tasks are taken in increasing order. The similar observation can also be made from Fig. 7 in the case when the number of tasks is fixed and that of cores is taken in an increased order. Thus, it is concluded that the proposed strategy results in a near optimal cost in both cases. Task allocation problem for reconfigurable multicore systems, using task clustering, is discussed. A novel task model based on elastic coefficients is proposed. This is to adapt task parameters allowing task allocation and reconfiguration while minimizing communication costs. The task allocation problem is known to be NP-hard. When considering communication costs, the proposed technique gives a near optimal solution while respecting real-time and communication constraints. Optimal solution is obtained by formulating the problem as an ILP problem and we compare the results of the proposed technique with the optimal solution. After some evaluations, we conclude that the proposed technique results in a near optimal ones provided by the CPLEX solver.

In a future work, we will focus on the implementation of the paper's contribution in a real-time operating system that will be evaluated by assuming real case studies.

Figure 1 :

 1 Figure 1: Example of application.

Figure 2 :

 2 Figure 2: Global MappingTasks algorithm.

Figure 3 :

 3 Figure 3: MappingTasks algorithm.

Figure 4 :

 4 Figure 4: Inter task communication graph of example 1 (in kilo bits).

Figure 5 :

 5 Figure 5: Inter task communication graph application's example after adding tasks (in kilo bits).

Figure 6 :

 6 Figure 6: Communication cost of our strategy when tasks are in increasing order and number of cores is 4.

Figure 7 :

 7 Figure 7: Communication cost of our strategy when cores are in increasing order and number of tasks is 17.

Table 1 :

 1 Tasks' characteristics.

	Task T i τ 1 5	T i max 6
	τ 2	6	8
	τ 3	10	10
	τ 4	4	6
	τ 5	12	22
	τ 6	5	16
	τ 7	8	21
	τ 8	8	32
	τ 9	6	14
	τ 10	7	12

Table 2 :

 2 WCET W i of tasks.

Table 3 :

 3 CPCL and CL clusters.

Table 4 :

 4 Processor utilization for each core.

		Core 1	Core 2	Core 3
	Processor utilization U	0.983	0.935	0.708

Table 5 :

 5 Added tasks.

	Task T i τ 11 12	T i max 20
	τ 12	4	15
	The WCET W i of each new task is presented in
	Tab. 6

Table 6 :

 6 WCET

Table 7 :

 7 Modification of period's tasks running on C 2 .

	Task T i τ 6 5	T i max 16
	τ 8	10	32
	τ 10	10	12
	τ 11	15	20

Table 8 :

 8 Communication cost when number of tasks increases.

	Tasks N Cores p Proposed algo Optimal sol
	10	4	68	66
	11	4	92	88
	12	4	131	126
	13	4	146	138
	14	4	188	177
	15	4	235	219
	16	4	292	280
	17	4	355	336

Table 9 :

 9 Communication cost when number of cores increases.

	Tasks N Cores p Proposed algo Optimal sol
	17	4	355	336
	17	5	385	358
	17	6	372	359
	17	7	385	361
	17	8	390	372
	17	9	402	386
	17	10	423	399
	17	11	430	415