Minyu Cui
email: minyu.cui@irisa.fr

Angeliki Kritikakou
email: angeliki.kritikakou@irisa.fr

Lei Mo

Emmanuel Casseau
email: emmanuel.casseau@irisa.fr

Near-optimal Energy-Efficient Partial-Duplication Task Mapping of Real-Time Parallel Applications

Keywords: Fault tolerant, Task mapping, DVFS, Real-time execution, Reliability, Energy minimization

Minimizing energy consumption, as well as meeting real-time and reliability constraints, are major goals during system deployment. When complex platforms, such as multicore architectures with DVFS, and parallel applications are considered, these goals are significantly impacted by task mapping. To minimize energy consumption, while meeting real-time and reliability constraints, this work proposes a task mapping approach to jointly solve the problem of task allocation, task scheduling, frequency assignment, and task duplication. A novel heuristic algorithm is proposed to cope with this NP-hard problem, consisting of a pruning phase, which maintains only the task configurations that satisfy reliability constraints, and a mapping phase, which minimizes total energy consumption under real-time and precedence constraints. The obtained results show that the proposed heuristic obtains near-optimal results, with low computation time, compared to optimal solvers, while it achieves better energy consumption and finds slightly more solutions compared to other heuristic approaches.

1 Introduction

Context

The execution of embedded real-time parallel applications on multicore platforms require guarantees for real-time execution [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Huang | Energy-efficient fault-tolerant mapping and scheduling on heterogeneous multiprocessor real-time systems[END_REF][START_REF] Gou | Reliability-aware energy optimization for throughput-constrained applications on MPSoC[END_REF] and reliability [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. Due to technology size reduction, multicore platforms are susceptible to transient faults [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF]. Reliability is defined as the probability of executing a task without faults. Typical techniques to increase reliability are the execution of tasks with high frequency [START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF] and task replication [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. However, both techniques can lead to large energy consumption. Dynamic Voltage and Frequency Scaling (DVFS) is a well-known energy management technique, which optimizes energy consumption by scaling down the processor supply voltage and frequency [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. However, this has a negative impact on reliability, since more transient faults occur at a low voltage and frequency level [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. Therefore, during the task mapping not only task allocation and scheduling, but also frequency assignment and task replication should be incorporated into the optimization process to achieve energy efficiency, while meeting real-time and reliability constraints.

Related work and motivation

Table 1 summarises representative State-of-the-Art (SoA) task mapping approaches that minimize energy consumption considering DVFS, under Real-Time (RT.) and Reliability (R.) constraints. Tasks are Independent (I.) or Dependent (D.). The platform consists of Homogeneous processors(HO.), Heterogeneous processors (HE.), or Single (S.) processor. The applied fault tolerance policy can be task Recovery (Rec.) or task Replication (Rep.). A task is executed successfully, if at least one replica is executed without faults [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF]. Last, the proposed solving method can be Optimal (O.) or Heuristic-based (H.).

Approaches exist without applying a fault tolerance policy, e.g., the task mapping problem is decomposed into a sub-problem that satisfies the reliability constraint and another that minimizes resources [START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF] and a whale optimization algorithm is proposed [START_REF] Deng | Reliability-aware task scheduling for energy efciency on heterogeneous multiprocessor systems[END_REF]. In [START_REF] Roeder | Energy-aware scheduling of multi-version tasks on heterogeneous real-time systems[END_REF], the scheduling algorithm for dependent multi-version tasks is studied based on Forward List Scheduling with the goal of minimizing the total energy consumption under real-time constraint. Approaches execute a recovery task, e.g., individual [START_REF] Zhang | Joint optimization of energy efficiency and system reliability for precedence constrained tasks in heterogeneous systems[END_REF] or shared [START_REF] Huang | Energy-efficient fault-tolerant mapping and scheduling on heterogeneous multiprocessor real-time systems[END_REF][START_REF] Zhao | Shared recovery for energy efficiency and reliability enhancements in real-time applications with precedence constraints[END_REF], or both [START_REF] Guo | Reliability-aware power management for parallel realtime applications with precedence constraints[END_REF], with maximum frequency, exploring available time slack to meet the reliability constraint. Last, approaches apply task replication. Some works decide the required number of replicas per task always to meet the reliability constraint, e.g., for independent tasks on homogeneous platform [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF] and dependent tasks on heterogeneous platforms [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. In [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF], all replicas of a task are executed at the same frequency, whereas in [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF], no real-time constraints are taken into account. In [START_REF] Salehi | Two-phase low-energy n-modular redundancy for hard real-time multi-core systems[END_REF], the number of replicas per task is given. In the first phase, half-plus-one copies per task are executed. If a fault occurs, the second phase is applied to execute the remaining number of copies. Other works decide among different reliability mechanisms for each task. In [START_REF] Salehi | DRVS: Power-efficient reliability management through dynamic redundancy and voltage scaling under variations[END_REF], a heuristic explores three reliability mechanisms in sequence to decide single task execution, task duplication, and task triplication, without the requirements of always meeting the real-time and reliability constraints. In [START_REF] Gou | Reliability-aware energy optimization for throughput-constrained applications on MPSoC[END_REF], a heuristic determines which tasks to be duplicated, removing the need for a recovery task for all tasks. An optimal approach that decides which tasks to duplicate, taking into account reliability and real-time constraints is proposed in [START_REF] Cui | Energy-aware partial-duplication task mapping under real-time and reliability constraints[END_REF][START_REF] Cui | Fault-tolerant mapping of real-time parallel applications under multiple DVFS schemes[END_REF][START_REF] Cui | Energy-efficient partial-duplication task mapping under multiple dvfs schemes[END_REF]. The main difference between [START_REF] Cui | Energy-aware partial-duplication task mapping under real-time and reliability constraints[END_REF][START_REF] Cui | Energy-efficient partial-duplication task mapping under multiple dvfs schemes[END_REF] and [START_REF] Cui | Fault-tolerant mapping of real-time parallel applications under multiple DVFS schemes[END_REF] is the task model, i.e., independent tasks are considered in [START_REF] Cui | Energy-aware partial-duplication task mapping under real-time and reliability constraints[END_REF][START_REF] Cui | Energy-efficient partial-duplication task mapping under multiple dvfs schemes[END_REF] while tasks with dependencies are considered in [START_REF] Cui | Fault-tolerant mapping of real-time parallel applications under multiple DVFS schemes[END_REF].

Our work (Prop.) studies the same problem as in [START_REF] Cui | Fault-tolerant mapping of real-time parallel applications under multiple DVFS schemes[END_REF], i.e., partial duplication task mapping of tasks with dependencies and task-level DVFS. However, an optimal algorithm is presented in [START_REF] Cui | Fault-tolerant mapping of real-time parallel applications under multiple DVFS schemes[END_REF], while a heuristic algorithm that provides near-optimal, but less time-consuming solutions, is proposed in this paper. The experimental section provides a comparison between the optimal and the heuristic approaches.

Overall, optimal approaches are applicable only for small problem sizes and existing heuristics, either do not fully guarantee real-time or reliability constraints, or use a high number of replicas, leading to large energy consumption with a negative impact on execution time, and thus, potentially no feasible solution.

Contributions

This work addresses the task mapping problem of parallel applications on homogeneous multicore platforms with DVFS, with the goal of minimizing total energy consumption, under real-time and reliability constraints. An effective heuristic is proposed, considering multiple non-functional properties of execution time, energy, and reliability, that combine task allocation, task scheduling, frequency assignment, and selective task duplication. Unlike the majority of SoA techniques, original and duplicated tasks can have different operating frequencies, being more suitable for real-world systems [START_REF] Zhou | Resource management for improving soft-error and lifetime reliability of real-time MPSoCs[END_REF]. A pruning phase maintains only the task configurations that satisfy reliability constraints. A mapping phase minimizes total energy consumption under real-time and precedence constraints. Last but not least, the proposed method is evaluated both with task graphs from real applications and randomly generated graphs. The experiment results show that our approach provides near-optimal energy savings, with low computation time compared to optimal solvers. At the same time, it has better energy consumption and feasibility compared to other heuristics.

The rest of the paper is organized as follows. Section 2 introduces the system model. Section 3 presents the formulation of the proposed approaches. Section 4 presents the evaluation results. Finally, Section 5 concludes this study.

System Model

Table 2 shows the main notations. For the sake of paper presentation, when original and duplicated tasks must be distinguished in mathematical formulations, the superscript k ∈ {o, d} indicates the original task ( o ) or the duplicated task ( d ). If no superscript exists, the mathematical formulation is valid for both.

Task Model

This work considers a real-time application modelled as a Directed Acyclic Graph (DAG) G(V, E), where V denotes the set of N frame-based, nonpreemptive, dependent tasks N = {τ o 0 , . . . , τ o N -1 }, while E represents the edges, corresponding to the tasks' precedence constraints. Tasks are released at time 0 and have a global deadline D, given by the application frame. The release period of the task set is assumed to be longer than its global deadline. We focus on a single frame, which implies only one job of the same task can be active simultaneously. If a task has no predecessors (successors), it is an entry task τ entry (exit task τ exit ). If a graph has multiple entry or/and exit tasks, then a dummy entry or/and exit task can be added into the graph to meet our model. A task is ready for execution when all its predecessors have been completed. Each task τ i is described by a tuple {W i , R th i }, where W i is the Worst Case Execution Cycles (WCEC) and R th i is its reliability threshold which is given as input and depicts the reliability requirement of the task. Each task has its own reliability constraint, since functions of an application exhibit distinct vulnerabilities, due to variations in the spatial and temporal vulnerabilities of different instructions [START_REF] Salehi | DRVS: Power-efficient reliability management through dynamic redundancy and voltage scaling under variations[END_REF]. The target platform has a shared-memory multicore architecture with M homogeneous processors M = {θ 0 , . . . , θ M -1 }. Each processor supports DVFS and has L pairs of frequency/voltage level {(f 0 , v 0 ), . . . , (f L-1 , v L-1 )}. As the relationship of voltage and frequency is almost linear [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF][START_REF] Zhao | Shared recovery for energy efficiency and reliability enhancements in real-time applications with precedence constraints[END_REF][START_REF] Salehi | Two-phase low-energy n-modular redundancy for hard real-time multi-core systems[END_REF], we use the term frequency scaling to express the simultaneous change of voltage and frequency. We consider intra-task DVFS. When task τ i is executed at frequency f l , its execution time is Wi f l . The power consumption is modeled as the sum of static power P sta l and dynamic power P dyn l considering a voltage/frequency level (v l , f l ) [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. Specifically,

P l = P sta l + P dyn l = P sta l + C ef f v 2 l f l , (1)
where C ef f is the effective switching capacitance.

Fault Model and Reliability

This work addresses transient faults, having a higher occurrence than permanent faults during the useful lifetime of the system [START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF]. During this period, the fault model, where the fault occurrence is given by a Poisson distribution with an average fault rate λ(f l ) at frequency f l , is typically used [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF][START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF][START_REF] Zhao | Shared recovery for energy efficiency and reliability enhancements in real-time applications with precedence constraints[END_REF][START_REF] Salehi | Two-phase low-energy n-modular redundancy for hard real-time multi-core systems[END_REF][START_REF] Zhu | The effects of energy management on reliability in real-time embedded systems[END_REF]. The failure rate per time unit of a processor at frequency f l is given by

λ(f l ) = λ 0 × 10 d0 fmax-f l fmax-f min , (2)
where f max = max ∀l {f l }, f min = min ∀l {f l }, λ 0 is the average failure rate of the processor corresponding to f max , and d 0 is a positive constant, indicating the sensitivity of failure rates to voltage scaling [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. The reliability of task τ i is defined as the probability of executing τ i without any fault. Based on the exponential model in [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Zhao | Shared recovery for energy efficiency and reliability enhancements in real-time applications with precedence constraints[END_REF], the reliability of a task executed at f l is calculated as

R i (f l ) = e -φi(f l ) , (3)
where φ i (f l ) = λ(f l ) × et i,l , and et i,l is the execution time of task τ i at frequency f l . If the reliability of original task τ o i is larger than its reliability threshold R th i , the execution is considered as reliable [START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF] and the task reliability is given by R i = R o i . Otherwise, the task τ o i is duplicated and executed on a different processor, since it is unlikely that the execution of both original and duplicated tasks on different processors fails [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Gou | Reliability-aware energy optimization for throughput-constrained applications on MPSoC[END_REF][START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. The duplicated task τ d i has the same characteristics with the original task τ o i . When the duplicated task τ d i is executed, its reliability is R d i and depends on the frequency it is executed. Then, the task reliability, after duplication, is

R i = 1 -(1 -R o i )(1 -R d i ). ( 4
)
As our approach finds an offline heuristic-based task mapping solution, with the goal of minimizing energy consumption, we consider only task duplication, i.e., a single replica per task, in order not to unnecessarily increase the number of replicas, in case no faults occur. An online mechanism can be applied to further improve the energy consumption of our solution (by not executing the duplicated task, when the first execution is correct), and to deal with the low probability cases, where both original and duplicated tasks are faulty. In this work, cores are assumed to operate below a temperature threshold, where temperature impact on reliability is low [START_REF] Skadron | Temperature-aware microarchitecture: Modeling and implementation[END_REF].

Problem under study

Given a DAG task graph G and M processors, the goal is to minimize the total energy consumption by deciding the: 1) task duplication, 2) assignment of frequencies to tasks, 3) allocation of tasks to processors, 4) start time of tasks, subject to reliability, real-time and task precedence constraints.

Proposed Approach

To solve the problem under study, we propose a Heuristic for Reliability-aware Fault-tolerant Task Mapping (H RAFTM), described in Algorithm 1. The algorithm consists of two phases:

1. Phase A obtains, per task, the set of possible configurations that meet the reliability constraint, ordered in decreasing energy consumption.

2. Phase B obtains the application mapping, by allocating tasks to processors using the least total energy consumption, under task precedence and realtime constraints.

H RAFTM is based on the following definitions:

Definition 1 (Configuration). A configuration j of a task τ i is denoted as

C j i = {f o i , f d i , et o i , et d i , E o i , E d i , R i }, where f o i (f d i ) is the assigned frequency, et o i (et d i ) is the required execution time, E o i (E d i )
is the energy consumption of the original (duplicated) task, and R i is the reliability of the task (taking into account task duplication). If the task is not duplicated, we have

f d i = et d i = E d i = 0
which is considered as a dummy execution. Definition 2 (Task Mapping). A mapping of a task τ i , under the task configuration C j i , is denoted as T M

C j i i = {θ o i , θ d i , st o i , st d i }, where θ o i (θ d i )
is the allocated processor, and st o i (st d i ) is the start time of the original (duplicated) task. If a task is not duplicated, then f d i = 0, and the duplicated task takes no execution time, i.e., its start time is equal with its finish time, st d i = f t d i . Definition 3 (Application Mapping). The mapping of the application (AM) is given by the set of mappings of N original tasks and S ⊆ N duplicated tasks. The mapping is valid if task precedence and real-time constraints are satisfied.

The following paragraphs describe in detail the two phases of the proposed approach and illustrate them using the application DAG example of Fig. 1.

Part of RT E 5 * with W 5 = 1.4728 × 10 8 and R th 5 = 0.9994 *Processor model based on Table 3 C j 5 f o 5 f d 5 et o 5 et d 5 E o 5 E d 5 R 5 (GHz) (GHz) (msec) (msec) (mJ) (mJ) C 0 5 0.
RT E i = {C j i : C j i is a configuration of τ i } ;
3:

F C i = RT E i -{C j i : R i < R th i };
4:

BC i = {F C i : f d i = 0}; 5:
for each configuration bc in BC i do 6:

P C i = F C i -{F C i : f d i ̸ = 0 ∧ min{et o i , et d i } ≥ et bc ∧ {E o i , E d i } > E bc }; 7:
end for 8:

rP C i = {P C i : P C i decreasing energy consumption}; 9: end for // Phase B 10: for each task τ i in N do 11:

Compute rank i (Eq. 9); 12: end for 13: P L = {N : ordered in decreasing rank i }; 14: for each task τ i in P L do 15:

SC i = rP C i [0]; 16:
Select the processor and set st i = EST i (Eq. 6 and 8), compute T M SCi i in Definition 2; 17: end for

18: AM 0 = {T M SCi i , i ∈ N }; 19: Compute SL AM0 (Eq. 7); 20: if SL AM0 > D then 21:
Infeasible problem, algorithm stops. 22: else

23:

AM relaxation (Algorithm 2); 24: end if configurations (Line 2). For instance, part of the RTE of task τ 5 is depicted in Fig 1 . A pruning step removes the task configurations that do not satisfy the reliability constraint (Line 3).

Algorithm 2: Mapping Relaxation Algorithm.

1:

AM = AM 0 , SL = SL 0 ; 2: while |rP C i |> 1(∃τ i ) do 3: f lag = 0 4:
for each task τ i in N do 5:

N C A i = rP C i [0]; 6: N C B i = rP C i [j] with max k∈{o,d} (ES j τ k i /T I j τ k i ) ; 7: if E N C A i ≤ E N C B i then 8: N C i = N C A i ; 9:
else 10:

N C i = N C B i ; 11: end if 12:
for each task τ j in P L do 13:

if τ j ̸ = τ i then 14:
Compute T M

Compute AM i = {T M N Ci(/SCi) i , i ∈ N }; 20:
Compute SL AMi (Eq. 7) and SLI i = SL AMi -SL;

21:

if SLI i ̸ = 0 then 22: Compute Gain i = k∈{o,d} (ES N C i τ k i /T I N C i τ k i )) SLIi ; 23:
else 24:

Mark task τ i as with "highest" gain; end if 46: end while i) Reliability Constraint: A task must be executed meeting its reliability requirement, i.e., R i ≥ R th i . For instance, assuming that the reliability of τ 5 is R th 5 = 0.9994, the configurations C 0 5 , C 1 5 and C 2 5 are pruned in this step. The result is the Feasible Configurations (F C) of the task. F C i considering only the original task τ o i (when f d i = 0 no duplicated task exists) serve as Baseline Configurations (BC) (Line 4). In our illustration example, the BC of τ 5 are C 3 5 , C 4 5 and C 5 5 . The next step prunes any feasible configuration with duplicated tasks, if both the energy consumption and the execution time are larger than any defined BC i (Lines 5-7), e.g., C 10 5 and C 26 5 in our illustration example of Fig 1, because they are less efficient than the BC. The result is the Possible Configurations (P C). The P C are ranked based on decreasing energy consumption (rP C i ) (Line 8) where higher energy consumption generally implies that a higher frequency is assigned, and thus, it takes a shorter execution time to execute the task.

3.2 Phase B: Application mapping, under precedence and real-time constraints.

Phase B uses Phase A task configurations and performs the application mapping, subject to the following constraints: ii) Precedence constraints: Based on the dependencies defined by the task graph, a task τ i can start execution only when all its predecessors are completed. Task predecessors also include the duplicated tasks, since our approach is applied offline, and thus, strict scheduling is considered where a task can be executed after all its predecessors are finished. Then, the Earliest Start Time (EST) of τ i on a processor is given by

EST i = 0, if τ i = τ entry max τj ∈P red{τi} {EF T j }, else (5)
where P red{τ i } is the set of τ i 's predecessors, and EF T j = EST j + et j is the Earliest Finish Time (EFT) of task τ j .

iii) Deadline constraint: Due to precedence constraints, the actual start time of a task is st i ≥ EST i . Our goal is to exploit the available time slack to save energy, thus, we initially consider that tasks start execution as soon as possible,

st i = EST i , ∀τ i (6)
Therefore, the actual finish time of task τ i is f t i = st i + et i . The application must be finished before the deadline D. The Schedule Length of task graph G, under a given application mapping AM , denoted as SL AM , is determined by the actual finish time of exit task τ exit . The deadline constraint is as follows:

SL AM = f t τexit ≤ D. (7)
iv) Non-overlapping constraint: Only a single task should be executed on a processor at a given time instance. Taking into account the task dependency and non-overlapping constraints, the EST i on each processor in Equation 5 is modified as follows:

EST i =        0, if τ i = τ entry max    max τj ∈P red{τi} {EF T j }, max τp∈Bf {τi} {EF T p },    , else (8)
where Bf {τ i } is the set of tasks that is executed before task τ i on the same processor as task τ i . Bf {τ i } is subject to the task priority assignment explained in detail later in this section.

The method to choose a processor to execute a task is the following. From Eq. 8, except for the entry task, the earliest start time is the maximum of two components. For convenience, we define EST A i = max τj ∈P red{τi} {EF T j }, due to the task dependency constraint, and EST B i = max τp∈Bf {τi} {EF T p } which corresponds to the earliest available time of each processor when it is ready to execute a task, due to non-overlapping constraint. For the currently scheduled task τ i , EST A i has only one value, while EST B i may have different values on different processors. Because we target real-time applications, the processor that has the smallest EST i for task τ i is chosen to execute this task, i.e., {θ m : arg min m∈M {EST i }} for task τ i . If there are more than one processors that have the same smallest EST i for task τ i , the first processor in the list of available processors (the one with smallest index) is chosen to execute this task.

Fig. 2 illustrates this selection process through an example, where the horizontal axis is related to time. We assume that the currently scheduled task is τ i (and thus, not the entry task) and the mapping of tasks before τ i in the Priority List (PL) is done. There are two possible cases: 1) in Fig. 2a, processors θ 1 , θ 2 and θ 3 are available later than EST A i . The value for EST B i can be obtained as

EST B i = avail[1], if τ i is executed on processor θ 1 , EST B i = avail[2]
, if τ i is executed on processor θ 2 , and EST B i = avail [START_REF] Gou | Reliability-aware energy optimization for throughput-constrained applications on MPSoC[END_REF], if τ i is executed on processor θ 3 . According to Eq. 8, the earliest start times EST i for task τ i on the three processors are avail [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF] (on θ 1 ), avail [START_REF] Huang | Energy-efficient fault-tolerant mapping and scheduling on heterogeneous multiprocessor real-time systems[END_REF] (on θ 2 ) and avail [START_REF] Gou | Reliability-aware energy optimization for throughput-constrained applications on MPSoC[END_REF] (on θ 3 ), respectively. The smallest Earliest Start Time is EST i = avail [START_REF] Gou | Reliability-aware energy optimization for throughput-constrained applications on MPSoC[END_REF]. Therefore, processor θ 3 is finally chosen to execute task τ i and sets st i = EST i = avail [START_REF] Gou | Reliability-aware energy optimization for throughput-constrained applications on MPSoC[END_REF]; and 2) in Fig. 2b processors θ 1 and θ 2 are available before EST A i , and processor θ 3 is available later than EST A i . According to Eq. 8, the Earliest Start Time for task τ i on three processors are

EST i = EST A i (on θ 1 ), EST i = EST A i (on θ 2 )
and EST i = avail [START_REF] Gou | Reliability-aware energy optimization for throughput-constrained applications on MPSoC[END_REF] (on θ 3 ). Both processors θ 1 and θ 2 achieve the smallest EST i for task τ i , which is EST A i . In this case, the first processor in the list of available processors, i.e., θ 1 , is finally chosen to execute task τ i and sets st i = EST i = EST A i . The text paragraphs describe the three steps of Phase B (Lines 10-26):

(a) case A (b) case B
Fig. 2: Illustration example of how to select the processor to execute a task.

Step 1 (Lines 10-13): Priorities are given to tasks for task allocation based on the upward rank value [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF], rank i , which is common for original and duplicated tasks (Lines 10-12):

rank i = et i , if τ i = τ exit et i + max τj ∈Succ{τi} {rank j }, else (9)
where

et i = ( L l=1 W i /f l )/L
is the average computation time of τ i and Succ{τ i } the immediate successors of τ i . Then, the Priority List (PL) is ordered in decreasing rank value (Line 13).

Step 2 (Lines 14-21): The initial application mapping AM 0 is generated to check if the problem is feasible and whether time slack exists. For all tasks, AM 0 uses the first configuration in rP C as the Scheduled Configuration SC i (Line 15). When allocating a task, a processor is chosen as explained previously and sets st i = EST i according to Eq. 6 and 8 to execute the current task. We remind that Bf in equation 8 is constructed according to the allocation performed in Line 16 of Algorithm 2. We thus obtain the task mapping (T M SCi i ) per task (Line 16). The set of all task mappings provides the AM 0 (Line 18). Then, its schedule length SL AM0 is obtained (Line 19). If it is higher than the deadline, the problem is infeasible (Lines 20-21), and the algorithm stops.

Step 3: (Lines 22-24) If the initial schedule length is equal or less than the deadline (Line 22), time slack exists. Overall, different task configurations and different tasks can be relaxed to obtain energy savings (Line 23). Algorithm 2 decides the task to be relaxed and its configuration. Initially, the current mapping (schedule length) is initialized with the initial mapping (schedule length). Algorithm 2 is applied iteratively due to the while loop (Lines 2-46), until all tasks reach their last configuration |rP C i |= 1(∀τ i ) (Line 2) with the least energy consumption, or the flag, which depicts whether no valid relaxation exists, is met. As explained later, when none of the tasks can be selected for relaxation, f lag = N and algorithm 2 stops. Firstly, the flag is initialised to zero (Line 3). In each round of relaxation of the while loop, the algorithm initially enters into a for loop (Lines 4-31), which traverses all tasks for potential relaxation. In each iteration, one task is selected to do a "virtual" relaxation with a New Configuration N C, while the remaining tasks keep the Scheduled Configuration SC (Lines 12-18). Note that, this is not the final decision for relaxation. To decide which New Configuration should be selected for a task (N C i ), we combine two criteria. Let assume the currently selected task to do such a "virtual" relaxation is task τ i . First, a local search decides a New Configuration N C A i (Line 5) by exploring rP C i sequentially, i.e., selecting always the first configuration. Second, N C B i (Line 6) selects the j configuration in rP C i with the highest value (ES j

τ o i /T I j τ o i ) + (ES j τ d i /T I j τ d i ), where ES j τ o i (ES j τ d i )
is the energy savings and T I j

τ o i (T I j τ d i
) is the time increase of task τ i in configuration j, compared to the current Scheduled Configuration SC i . The final new configuration N C i for τ i is the one with the minimum energy consumption (Lines 7-11). After selecting this new configuration, the relaxation information is updated accordingly, which includes the new application mapping AM i (Line 19) and its schedule length SL AMi (Line 20) are obtained. The difference of SL AMi with the schedule length of the current mapping SL provides the Schedule Length Increase (SLI i ), when task τ i changes its current configuration SC i to N C i (Line 20). With this, the overall gain (Gain i ), considering both energy and time, that this configuration modification will bring to the overall mapping, is computed (Lines 21-25). It is possible that in some relaxations the new application schedule length is equal to the schedule length of the current mapping, i.e., SL AMi = SL. In this case SLI i = 0, i.e. relaxation does not increase schedule length. The task is thus marked as with "highest" gain since the Gain i should be infinite according to equation Line 22 (in this case Gain i is denoted as Inf in Fig 4 .) and this task is selected for relaxation. The time slack slack i is computed (Line 26). In Line 27 when task τ i is selected to do relaxation, it is required to compare whether the new SL AMi exceeds the global deadline. As all the EST values of task τ i 's successors will be accordingly changed due to the additional execution time consumed by task τ i selecting a new configuration, we then also check whether the time increase T I i exceeds the available time slack slack i in order to generate a valid relaxation. In case the new SL AMi exceeds the global deadline or the T I i exceeds the available time slack, the flag is incremented (Line 28), and this "virtual" relaxation is considered as invalid, thus, it is discarded (Line 29). This task will not be selected for relaxation in this relaxation round. After we obtain the relaxation information for all tasks iteratively, we check if f lag = N , which means no valid relaxation exists and none of the tasks can be selected for relaxation, then the algorithm 2 stops (Lines 32-33). This typically happens when the time slack is not enough to enable a relaxation for any task.

The time slack of each task in the current mapping (slack i ) is based on task mobility through Eqs. 8, 10, 11 :

slack i = LF T i -EST i -et i . (10)
The Latest Finish Time (LFT) of τ i is:

LF T i =        D, if τ i = τ exit min    min τp∈Af {τi} {LST p }, min τj ∈Succ{τi} {LST j },    , else (11)
where

LST i = LF T i -et i is the Latest Start Time (LST) of task τ i .
Af {τ i } is the set of tasks executed after task τ i on the same processor as task τ i . Af {τ i } is subject to the task priority in P L. If f lag = N does not hold, there exists a valid relaxation, and thus, the global decision takes place (Lines 35-44). First if there exist "highest" tasks, the task with higher energy saving is selected to do relaxation, since it does not increase the schedule length while saves energy consumption (Line 36). Otherwise, the task (and its corresponding configuration) to be relaxed (τ rel ) is the task with the maximum overall gain (Line 38), whose time increase in this New Configuration is not larger than its available slack in the current mapping checked in Line 27. Last, the Scheduled Configuration (SC) for the relaxed task, the application mapping and its schedule length are updated (Lines 40-41), and all the configurations that have a higher energy consumption than the selected one are removed from rP C τ rel (Lines 42-44). on the left the initial application mapping AM 0 (according to Lines 14-19 in Algorithm 1) and on the right the initial Scheduled Configuration for each task. The total energy consumption of AM 0 is E AM0 = 48.12 mJ and schedule length is SL AM0 = 1.3515 sec (Line 19 in Algorithm 1). Since the schedule length is lower than the deadline (Line 22 in Algorithm 1), there exists some time slack, so the relaxation algorithm is applied to save energy consumption (Line 23 in Algorithm 1). During relaxation, task τ 1 is firstly selected, along with the New Configuration where both original and duplication copies are executed with frequency f 1 (Lines 35-40 in Algorithm 2), since this task and its New Configuration provide valid relaxation with the highest gain (Lines 5-30 in Algorithm 2). The energy consumption is reduced without increasing the schedule length (Inf means positive infinity in Fig. 4 and the one with most energy saving is selected if there are multiple Inf cases). The updated application mapping is depicted in Fig. 4. The algorithm continues to apply the relaxation, by selecting the next valid task and the corresponding New Configuration with the highest gain, until the end conditions are met. The final application mapping is depicted in Fig 5, with an energy consumption equal to E = 41.67 mJ and a schedule length of SL = 1.3971 sec. Fig. 5: Illustration example (Fig. 1): Final application mapping.

*Scheduled configuration C j i f o i f d i SLI i Gain i (GHz) (GHz) (sec) C 0 0 1.0 - - - C 0 1 1.0 - - - C 0 2 1.0 1.0 - - C 0 3 1.0 - - - C 0 4 1.0 - - - C 0 5 1.0 - - -

Time complexity

In this section, we compute on the dominating time complexity. In the proposed heuristic approach, the maximum number of possible configurations for each task is L + 2 L (denoted as K). Phase A takes O(N K) time to obtain the possible configuration space for all tasks. Phase B firstly requires O(N logN ) time to create the priority list (PL). Then, it takes O(N ) time to calculate the EST of all tasks in the worst case. For each single task mapping, considering the worst case when selecting a processor to execute the task, all processors needs to be traversed. Therefore, it requires O(M N ) time to proceed the task. The application mapping, including N task mappings, takes O(M N 2 ) time.

In relaxation algorithm 2, we consider the worst case when the deadline is very relaxed and each configuration (K configurations per task) is searched, for all N tasks. The for loop (Lines 4-23) in Algorithm 2 traverses all N tasks and selects one to do a "virtual" relaxation for the application. It thus takes O(M N 3 ) time. The step to remove configurations for the selected task in Lines 29-31 in Algorithm 2 takes O(K) time considering the worst case, which is not the dominated part of the algorithm. Hence, the total complexity of the relaxation algorithm is O(M KN 3 ). Finally, overall, the dominating time complexity of the proposed heuristic is O(M KN 3 ).

Experimental Results

This section evaluates the proposed heuristic (H RAFTM) with i) the optimal solver using Gurobi 9.0.2 (O RAFTM) as in [START_REF] Cui | Fault-tolerant mapping of real-time parallel applications under multiple DVFS schemes[END_REF], and ii) two SoA heuristics a) the Reliability-Aware Mapping (H RAM), that meets the reliability constraint without task duplication, similar to [START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF] and ESRG algorithm in [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF], and b) the Task Duplication Mapping (H TDM), applying task duplication for all tasks, similar to [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF], when the number of replicas is two, or to [START_REF] Tosun | Energy-and reliability-aware task scheduling onto heterogeneous MPSoC architectures[END_REF], with 100% task duplication. To evaluate the approaches, the following metrics are used:

1. Feasibility, i.e., the number of experiments where a solution is found out of the total number of experiments (NE). 2. Energy Consumption (EC) of proposed heuristic approach, compared to the energy consumption of the optimal approach O RAFTM and two SoA heuristic approaches H RAM and H TDM. 3. Reliability Improvement (RI) (RI = R i -R th i ), i.e., the task reliability above the task reliability threshold. 4. Computation time (CT), i.e., the time required for each approach to find a solution.

Note that an approach may fail to find a solution, especially under strict deadlines. To fairly compare the energy consumption, reliability improvement, and computation time, we present the average values of the experiments where both compared approaches (i.e., O RAFTM vs H RAFTM, H RAFTM vs H RAM, or H RAFTM vs H TDM) were able to find a solution.

The model of the processor is based on a 32-bit RISC-V Instruction Set Architecture (ISA) with a 5-stage pipeline [START_REF] Rokicki | What you simulate is what you synthesize: Designing a processor core from c++ specifications[END_REF]. Regarding DVFS, L = 6 voltage/frequency levels are used [START_REF] Quan | Feasibility analysis for temperature-constraint hard realtime periodic tasks[END_REF] (Table 3), considering 64 nm technology. The number of processors in the experiments is M = 2, 4, 6. The task graphs are Random generation is used to compare the optimal approach (N = 10) and evaluate the scalability of the heuristics (N = 100). To obtain realistic values for the W i of a task, common benchmarks from the MiBench suite were executed on the processor. The execution cycles and memory accesses are counted and WCEC is computed, assuming that all cores may conflict during memory access. The obtained range is [1 × 10 8 , 4 × 10 8 ], and it is used to randomly select the W i of a task. The reliability threshold R th i of a task is selected within the range [0.9990, 0.9995], considering a typical magnitude 10 -3 for reliability target [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF]. For each application task graph, several experiments (denoted as N E) are performed, each time with different task characteristics (W i and R th i ). For each experiment, D is tuned from strict to relaxed deadlines, starting from SL AM0 of the initial application mapping and increased with a step of 0.1 seconds for small randomly generated DAGs and real-world DAGs and 0.5 seconds for large randomly generated DAG. Regarding feasibility, when M = 2, the H RAFTM feasibility is very close to the optimal feasibility, as shown in Fig. 7a, except for a few cases when the ) more energy than the optimal solutions. With the processor number increasing, the energy consumption of both the proposed heuristic and optimal solution flattens at earlier deadlines, since there are more processors resource available to perform the task mapping, and thus, more options to start the tasks earlier.

Comparison with optimal approach

Regarding reliability improvement, H RAFTM provides more reliability improvement than optimal solutions at the price of consuming slightly more energy under the same deadlines, as depicted in Fig. 8a The average computation time of O RAFTM and H RAFTM is computed over the number of experiments to find a feasible solution. Table 4, Table 5 and Table 6 show the results in seconds per deadline D. It can be observed that although few tasks and processors are used, the time to obtain the optimal solution is very long, on average 10 4 more than the proposed H RAFTM.

Overall, the obtained results show that i) H RAFTM provides near-optimal solutions, and the solutions tend to converge to the optimal ones with the number of processors increasing, ii) as expected, H RAFTM takes significantly less time to obtain the results compared to the optimal approaches.

Comparison with other heuristics

This section evaluates the behavior of the proposed H RAFTM heuristic to H RAM and H TDM heuristics, considering real-world application DAGs and large random generated DAGs.

Real-word DAG

The quality of solutions obtained by H RAFTM, H RAM and H TDM heuristics for the FFT (N = 15) are compared in Fig. 9 and Fig. 11, and for the GE (N = 14) in Fig. 10 and Fig. 12, considering M = 2, M = 4 and M = 6 processors, and N E = 20 experiments.

The feasibility of the three heuristics for FFT and GE benchmarks is depicted in the left column of Fig. 9 and Fig. 10. Compared to H TDM, the proposed H RAFTM can find solutions in significantly more experiments than H TDM, especially when the deadline is not fully relaxed or the number of cores is reduced. When tasks meet their reliability constraint, H RAFTM does not need to duplicate these tasks. However, H TDM duplicates all the tasks, and thus, it can find solutions only when the deadline is relatively relaxed, or several processors exist to run the tasks in parallel. Before obtaining 100% feasibility for both approaches, on average, H RAFTM finds a solution in more experiments than H TDM, i.e., 70.2% for FFT and 59.4% for GE (M = 2), 47.5% for FFT and 14.5% for GE (M = 4) and 47.5% for FFT and 2.2% for GE (M = 6). Note that, H RAFTM and H RAM have the same feasibility. This behavior is explained as follows: when H RAM finds a solution, the reliability constraint of all tasks can be met by executing only the original task with a high frequency. In this case, H RAFTM is also able to find this solution.

The energy consumption obtained by the solutions of the three heuristics for FFT and GE is depicted in the right column of Fig. 9 and Fig. 10. Comparing H RAFTM and H RAM, we observe that they consume similar energy with only the original task, meeting the reliability constraint and consuming less energy than configurations with duplicated tasks. Since H TDM duplicates all the tasks, its energy consumption can be significant, when it finds a solution. In relaxed deadlines, H RAFTM behaves similar to H TDM, i.e., duplicates the tasks when less energy is consumed. The average reliability improvement obtained by the solutions of the three heuristics is depicted in the left column of Fig. 11 and Fig. 12. H RAFTM achieves higher reliability than H RAM, except for very strict deadlines. As explained above, when there is no available time slack to perform duplication, H RAFTM behaves similarly to H RAM as most of the tasks are executed with only their original copy. Compared to H TDM, H RAFTM provides lower reliability for tight deadlines, as it duplicates only a part of the task set. The same reliability improvement can be achieved in relaxed deadlines, since both H RAFTM and H TDM duplicate tasks similarly.

The computation time of H RAFTM, H RAM and H TDM heuristics is depicted in the right column of Fig. 11 and Fig. 12. Overall, when the deadline increases, the trend of computation time for H RAM is to remain stable, for H RAFTM to slightly increase and for H TDM to increase with a higher factor. The computation time to obtain a feasible solution increases with deadline relaxation because the proposed heuristic explores the P C space for each task, based on the deadline constraints. Therefore, the more relaxed the deadline is, the larger the P C space to be explored per task, and thus, more time is needed. Note that, H TDM is the most expensive approach in terms of computation time. This behavior is because all tasks are duplicated, which increases the total number of tasks to be scheduled and the number of P Cs in each task P C space, and thus, the time to find a solution. For H RAM, it only executes original tasks. Therefore, it has a reduced number of P Cs in the P C space, taking the least time to obtain a solution. However, it provides less energy savings as explained above, especially at relaxed deadlines. Previous observations regarding feasibility, energy consumption, reliability im-provement, and computation time for the three heuristics are also verified by the experiments with the large randomly generated DAG. For instance, as the deadline is not fully relaxed or the number of cores is reduced, H RAFTM has increased feasibility compared to H TDM, i.e., 84.8% for M = 2, 85.7% for M = 4 and 83.8% for M = 6. Moreover, as the number of processors increases, energy consumption is reduced as lower frequencies can be selected, and partial task duplication can be applied by H RAFTM, as long as the reliability constraint is met.

Regarding computation time, it is increased when the number of tasks increases as expected, but still remains low compared to the prohibited computation time required for the optimal approach. For a small randomly generated task with N = 10 (Table 5 when M = 4 and Table 6 when M = 6), the proposed heuristic takes less than 1 sec to find a solution for all experiments whereas for a large randomly generated task with N = 100, the average computation time (considering all experiments and deadlines) is 144 sec (M = 2), 159 sec (M = 4) and 212 sec (M = 6). Comparing the computation time of the three heuristics for large DAGs N = 100, the average computation time for H RAM is 52 sec (M = 2), 66 sec (M = 4) and 75 sec (M = 6). For H TDM, the average computation time is 488 (M = 2), 501 sec (M = 4) and 718 sec (M = 6). Overall, we observe that H TDM is the more time-consuming approach, and H RAM is the least time-consuming approach. However, H TDM cannot always find solutions, whereas H RAFTM finds solutions with the same or less energy consumption than H RAM and H TDM.

Conclusion

A heuristic algorithm is proposed to obtain the task mapping of parallel applications, under real-time, reliability, and task dependency constraints. The goal is to minimize total energy consumption by deciding frequency assignment, task allocation, task scheduling, and task duplication. Based on the experimental results from real-world applications and randomly generated task graphs, the proposed heuristic achieves near-optimal solutions, with low computation time. Compared to similar heuristics, it achieves better energy consumption and is able to find solutions even when the other approaches fail. In future work, we will propose similar heuristics for other DVFS schemes provided by platforms, such as assigning a common frequency at cluster, processor, and platform levels.

Fig. 3 ,

 3 Fig. 3, Fig. 4 and Fig. 5 illustrate the application mapping process for the DAG in Fig 1, when M = 3 processors and D = 1.4 sec. After obtaining the priority list of the tasks in step 1 (Lines 10-13) in Algorithm 1, Fig 3 showson the left the initial application mapping AM 0 (according to Lines 14-19 in Algorithm 1) and on the right the initial Scheduled Configuration for each task. The total energy consumption of AM 0 is E AM0 = 48.12 mJ and schedule length is SL AM0 = 1.3515 sec (Line 19 in Algorithm 1). Since the schedule length is lower than the deadline (Line 22 in Algorithm 1), there exists some time slack, so the relaxation algorithm is applied to save energy consumption (Line 23 in Algorithm 1). During relaxation, task τ 1 is firstly selected, along with the New Configuration where both original and duplication copies are executed with frequency f 1 (Lines 35-40 in Algorithm 2), since this task and its New Configuration provide valid relaxation with the highest gain (Lines 5-30 in Algorithm 2). The energy consumption is reduced without increasing the schedule length (Inf means positive infinity in Fig.4and the one with most energy saving is selected if there are multiple Inf cases). The updated application mapping is depicted in Fig.4. The algorithm continues to apply the relaxation, by selecting the next valid task and the corresponding New Configuration with the highest gain, until the end conditions are met. The final application mapping is depicted in Fig5, with an energy consumption equal to E = 41.67 mJ and a schedule length of SL = 1.3971 sec.

Fig. 3 :Fig. 4 :

 34 Fig.3: Illustration example (Fig.1): Initial application mapping AM 0 .

Fig. 6 :

 6 Fig. 6: Real-world application DAG.

Fig. 7

 7 Fig. 7 and 8 compare the quality of solutions obtained by O RAFTM and H RAFTM approaches. We present the results of N E = 10 considering random graphs with N = 10 tasks, M = 2, M = 4 and M = 6 processors.Regarding feasibility, when M = 2, the H RAFTM feasibility is very close to the optimal feasibility, as shown in Fig.7a, except for a few cases when the

= 6 Fig. 7 : 4 (c) M = 6 Fig. 8 :

 67468 Fig. 7: Feasibility and Energy Consumption (EC in mJ) of optimal and heuristic approached for M = 2, M = 4 and M = 6 (N = 10)

  , Fig 8b, and Fig 8c.

= 6 Fig. 9 :

 69 Fig. 9: Feasibility and energy consumption (EC in mJ) of FFT (N = 15) for M = 2, M = 4 and M = 6.

= 6 Fig. 10 :

 610 Fig. 10: Feasibility and Energy Consumption (EC in mJ) of GE (N = 14) for M = 2, M = 4 and M = 6.

= 6 Fig. 11 :

 611 Fig. 11: Reliability improvement (RI) and Computation Time (CT in seconds) of FFT (N = 15) for M = 2, M = 4 and M = 6.

= 6 Fig. 12 :

 612 Fig. 12: Reliability improvement (RI) and Computation Time (CT in seconds) of GE (N = 14) for M = 2, M = 4 and M = 6.

= 6 Fig. 13 :

 613 Fig. 13: Feasibility and Energy Consumption (EC in mJ) of large randomly generated DAG (N = 100) for M = 2, M = 4 and M = 6.

= 6 Fig. 14 :

 614 Fig. 14: Reliability Improvement (RI) and Computation Time (CT in seconds) of large randomly generated DAG (N = 100) for M = 2, M = 4 and M = 6.

Table 1 :

 1 Comparison with representative SoA approaches

	Ref.	Task model I. D.	Fault tol. Rec. Rep. HO. HE. S. RT. Platform Constraints Solution

  P red{τ i } all immediate predecessors of task τ i Succ{τ i } all immediate successors of task τ i Bf {τ i } task set that is executed before task τ i on the same processor Af {τ i } task set that is executed after task τ i on the same processor avail[m] earliest available time of processor θm when it is ready to execute a task SC i Scheduled Configuration of task τ i in current task mapping N C i New (checked) Configuration of task τ i to do relaxation

	Notations	Definitions
	τ o i /τ d i (v l , f l )	the original/duplicated copy of task τ i the l th voltage/frequency level
	W i	WCEC of task τ i
	D	the global deadline
	R th i	reliability threshold of task τ i
	P L	priority list of task set
	SL	schedule length of DAG G
	EST i	earliest start time of task τ i
	LF T i	latest finish time of task τ i
	st i	actual start time of task τ i
	f t i	actual finish time of task τ i
	et i	execution time of task τ i
	slack i	time slack of task τ i

Table 2

 2

	: Main Notations and their definitions
	2.2 Platform Model

  Update SC τ rel = N C τ rel ; Update AM = AM τ rel and SL = SL AMτ rel ; rP C τ rel = rP C τ rel -{rP C τ rel : E pc ≥ E SCτ rel };

	25:	end if
	26: 27:	Compute slack i (Eqs. 8, 10, 11); if SL AMi > D or T I N Ci i > slack i then
	28:	f lag+ = 1;
	30:	end if
	31:	end for
	32:	if f lag = N then
	33:	break
	34:	else
	35:
	39:	end if
	40:
	41:
	42:	for each configuration pc in rP C τ rel do
	43:
	44:	end for
	45:

29:

Discard current task/application mapping when τ i is considered; if tasks with "highest" gain exist then 36:

Select the task with higher energy saving as τ rel to do relaxation; 37: else 38:

Select τ rel = τ i to do relaxation, with i corresponding to task τ i with max(Gain i ), i ∈ N ;

Table 3 :

 3 Processor characteristics

	v l (V)	0.85	0.90	0.95	1.00	1.05	1.1
	f l (GHz)	0.801	0.8291	0.8553	0.8797	0.9027	1.0
	C ef f	7.3249	8.6126	10.238	12.315	14.998	18.497

Table 4 :

 4 Computation time (seconds) for N = 10, M = 2

	D	1.3	1.4	1.5	1.6	1.7	1.8	1.9	2.0	2.1
	O RAFTM 424.8	523.4	537.1	275.5	432.2	739.7	832.7 1,645.6 2,349.0
	H RAFTM 0.15	0.13	0.14	0.17	0.17	0.20	0.22	0.23	0.29
	D	2.2	2.3	2.4	2.5	2.6	2.7	2.8	2.9	3.0
	O RAFTM 3,358.1 5,368.3 4,543.9 9,335.6 11,974.2 13,038.4 19,364.5 27,312.9 19,378.6
	H RAFTM 0.32	0.31	0.36	0.33	0.36	0.35	0.41	0.42	0.42
	D	3.1	3.2	3.3	3.4	3.5	3.6	3.7	3.8-4
	O RAFTM 13,155.9 21,493.1 24,228.4 77,477.5 5,472.0 4,868.6 4,096.3	2.5
	H RAFTM 0.49	0.52	0.47	0.52	0.56	0.58	0.59	0.63

Table 5 :

 5 Computation time (seconds) for N = 10, M = 4

	D	1.0	1.1	1.2	1.3	1.4	1.5	1.6	1.7	1.8	1.9	2.0
	O RAFTM 14.9 61.0 74.9 138.2 202.1 256.9 327.3 219.0 1039.3 1054.7 126.8
	H RAFTM 0.19 0.26 0.27 0.30 0.35 0.27 0.33 0.43	0.47	0.50	0.57
	D	2.1	2.2	2.3	2.4	2.5	2.6	2.7	2.8	2.9	3.0	-
	O RAFTM 58.7 123.1 4.9	1.9	1.4	0.6	1.8	1.0	1.8	2.3	-
	H RAFTM 0.59 0.66 0.64 0.70 0.68 0.67 0.68 0.69	0.66	0.78	-

Table 6 :

 6 Computation time (seconds) for N = 10, M = 6 at very strict deadlines, when the number of processors is small. In this case, H RAFTM behaves similarly to H RAM, i.e., mainly executing the original tasks with the frequency required to achieve the reliability constraint. With the deadline relaxing, H RAFTM starts to consume less energy than H RAM. H RAFTM achieves this gain by exploring the available time slack to duplicate tasks to save energy, e.g., up to ∼50.9% for FFT at relaxed deadlines. Similarly, when more processors are available, H RAFTM can take advantage of these resources and execute duplicated tasks in parallel. Comparing H RAFTM and H TDM, as H TDM applies task duplication for every task, it cannot find solutions under very strict deadlines. H RAFTM consumes significantly less energy than H TDM. H RAFTM selects the task configuration, if it exists,

	D	1.0	1.1	1.2	1.3	1.4	1.5	1.6	1.7	1.8	1.9	2.0
	O RAFTM 0.83 58.10 26.95 89.89 81.87 109.82 58.60 62.77 59.77 14.69 2.49
	H RAFTM 0.32 0.27 0.33 0.48 0.54	0.50	0.58 0.68 0.69 0.70 0.67
	D	2.1	2.2	2.3	2.4	2.5	2.6	2.7	2.8	2.9	3.0	-
	O RAFTM 0.74 0.65 0.63 0.66 0.66	0.64	0.64 0.63 0.60 0.60	-
	H RAFTM 0.76 0.74 0.76 0.80 0.84	0.77	0.76 0.76 0.71 0.72	-

√ √ √ √ √

This work is funded by China Scholarship Council (CSC).

Emmmanuel Casseau is a Professor at ENSSAT Graduate Engineering School, University of Rennes 1, Lannion, France. He is a member of the IRISA Lab./INRIA (French Institute for Research in Computer Science and Automation), France. His research interests are in the broader area of computer architecture, where he investigates the design of high-performance and costeffective embedded systems and reconfigurable-based architecture design. Within this context, he has performed research in high-level synthesis, mapping/scheduling techniques, custom and application-specific hardware architectures targeting multimedia and signal processing applications, reconfigurable architectures and FPGA-based accelerators.


Mohamed Younes

AIP: Adversarial Interaction Priors for Multi-Agent Physics-based Character Control

We address the problem of controlling and simulating interactions between multiple physics-based characters, using short unlabeled motion clips. We propose Adversarial Interaction Priors (AIP), a multi-agents generative adversarial imitation learning (MAGAIL) approach, which extends recent deep reinforcement learning (RL) works aiming at imitating single character example motions. The main contribution of this work is to extend the idea of motion imitation of a single character to interaction imitation between multiple characters. Our method uses a control policy for each character to imitate interactive behaviors provided by short example motion clips, and associates a discriminator for each character, which is trained on actor-specific interactive motion clips. The discriminator returns interaction rewards that measure the similarity between generated behaviors and demonstrated ones in the reference motion clips. The policies and discriminators are trained in a multi-agent adversarial reinforcement learning procedure, to improve the quality of the behaviors generated by each agent. The initial results show the effectiveness of our method on the interactive task of shadowboxing between two fighters. CCS Concepts: • Computing methodologies → Procedural animation; Adversarial learning; Multi-agent reinforcement learning.

Additional Key Words and Phrases: Character Animation, Multi-Agent Reinforcement Learning, Adversarial Imitation learning, Physics-based Simulation, Motion Capture

INTRODUCTION

Physics-based character control is a very active field of research, as it enables to generate physically valid animation in complex interactive environments. In applications where a simulated character/agent has to interact with an environment that may involve other agents (simulated or real users), it has to react realistically to a large variety of unexpected situations. Here, "realistic" means that the motions should preserve a natural style, and the actions performed by the agent could have been performed by a real person in the same situation.

Previous works demonstrated the promising use of data-driven approaches based on deep RL in order to improve the quality of a character motions for a wide range of behaviors. Recent techniques include Generative Adversarial Imitation Learning (GAIL), which enables a character to have realistic behavior learned from large datasets of multiple motion clips [START_REF] Peng | AMP: Adversarial Motion Priors for Stylized Physics-Based Character Control[END_REF]]. This approach mainly uses an adversarial discriminator output as a reward instead of manually designing imitation rewards, such as measuring pose errors between a simulated and a synchronized reference motion. However, most of these works aim at controlling a single character, while behaviors involving interactions between multiple characters have not been widely explored.

We propose adversarial interaction priors (AIP), a method for imitating interactions of multiple characters from non-annotated motion clips, based on the Multi-Agent GAIL framework (MAG-AIL) [START_REF] Song | Multi-Agent Generative Adversarial Imitation Learning[END_REF], an extension of GAIL to the multi-agent setting. As input to the system, we use two non-annotated datasets: 1) a single-actor dataset containing motions of single actors performing a set of motions linked to a specific application, and 2) an interaction dataset containing a few examples of interactions between several actors for this application. Based on these datasets, our system trains control policies allowing each character to imitate the interactive skills associated with each actor. Similarly to AMP [START_REF] Peng | AMP: Adversarial Motion Priors for Stylized Physics-Based Character Control[END_REF]], the single-actor dataset is used by all agents to provide them with the ability to imitate realistic motions, as well as a way to add user control through some defined objective. These individual motion capabilities provide each agent with a repertoire of behaviors that can be used to interact with other agents. The interaction dataset is used to train each agent on how to behave in different interactive situations that involve multiple agents. The interaction prior is therefore acting as a measure of similarity between the motions generated by the policies when the agents are interacting with each other, while the motion prior is measuring similarity between the motions produced by a character and the motions in the same dataset, independently of the other characters.

OUR APPROACH

Our method is based on MAGAIL [START_REF] Song | Multi-Agent Generative Adversarial Imitation Learning[END_REF], where an individual discriminator is assigned to each agent 𝑖, and trained to recognize behaviors based on its role in the interaction dataset. A policy controlling each agent gets rewards from the associated discriminator. The original formulation of MAGAIL assumes having access to the actions of the demonstrations, which could be difficult to get when dealing with unstructured and unlabeled motion capture data. Previous works [START_REF] Peng | AMP: Adversarial Motion Priors for Stylized Physics-Based Character Control[END_REF]] tackled this problem by using transitions of observations contained in this unlabeled motion clip (𝑜, 𝑜 ′ ), where 𝑜, 𝑜 ′ are observations of an agent at time step t and t+1 respectively. However, in the setting of interaction between multiple agents, the observation of each agent contains information about itself 𝑜 𝑠 as well as about other agents 𝑜 -𝑠 : 𝑜 = {𝑜 𝑠 , 𝑜 -𝑠 }. Since other agents are controlled by their own policies that change during training, the environment from the perspective of each agent becomes non-stationary. This is crucial for training the discriminators, as the observations of an agent might differ slightly from the demonstrations, because of this non-stationary environment. Hence, the policy could get lower reward because other agents changed their actions, as the full observation's transition could be never seen in the demonstration. Therefore, we propose to change the discriminator's input to omit observations about other agents for the next time step 𝑜 ′ -𝑠 , leading to (𝑜 𝑠 , 𝑜 -𝑠 , 𝑜 ′ 𝑠 ), without 𝑜 ′ -𝑠 , as the input for the individual discriminators. The intuition behind this choice is that we want each agent to perform actions that lead to similar interactive behaviors, as depicted by the demonstrations based on the current observation of other agents, no matter what their actions for the next time step. Therefore, the loss for the individual discriminator 𝐷 𝑖 for an agent 𝑖, is given by:

𝐿 𝑖 = 𝐿 𝑖𝑛𝑡 (𝑜 𝑠 , 𝑜 -𝑠 , 𝑜 ′ 𝑠 ) + 𝐿𝑔𝑝 (1)
where 𝐿 𝑖𝑛𝑡 is the interaction loss which trains the individual discriminator to distinguish between the agent behavior and behaviors from interactive demonstrations, 𝐿𝑔𝑝 is the gradient penalty loss used in AMP which is crucial for training stability of the discriminators. Similarly to AMP, we include a common discriminator between all agents, for which the loss is given by:

𝐿 𝑐𝑜𝑚𝑚𝑜𝑛 = 𝐿 𝑠 (𝑜 𝑠 , 𝑜 ′ 𝑠 ) + 𝐿𝑔𝑝 (2)
where 𝐿 𝑠 forces the discriminator to differentiate between agents behaviors and behaviors depicted in the single actor motion dataset. This is used for data augmentation in case the interaction dataset does not cover all possible situations. This is also a mean to use different behaviors from those included in the interaction dataset, in case a control or constraint-specific reward is used for training the policies. At the current stage of this work, we do not consider such control or constraint-specific rewards, but only rewards defined by the discriminators. The policies are trained using a combination of the multi-agent proximal policy optimization algorithm [START_REF] Yu | The Surprising Effectiveness of PPO in Cooperative[END_REF], and MAG-AIL: at each time step t, each agent receives an interaction-reward from the interaction prior 𝑟 𝑡 𝑖𝑛𝑡 = 𝑟 𝑖𝑛𝑡 (𝑜 𝑠 , 𝑜 -𝑠 , 𝑜 ′ 𝑠 ) and a style reward from the motion prior 𝑟 𝑡 𝑠 = 𝑟 𝑠 (𝑜 𝑠 , 𝑜 ′ 𝑠 ), computed from the discriminators output, as described in [START_REF] Peng | AMP: Adversarial Motion Priors for Stylized Physics-Based Character Control[END_REF]]. The rewards are then used in a linear combination to optimize each policy. The overview of the approach is depicted in the supplementary material.

RESULTS AND DISCUSSION

We applied this work to shadow-boxing with two fighters. In this combat sport exercise, the fighters minimize contacts to avoid injury. As we used marker-based motion capture, shadow-boxing prevent from potentially dangerous contacts with rigid markers. A 70-second interaction clip was recorded with the two fighters, along with 6 minutes single actor clips of boxing-specific motions (see the supplementary video).

Some snapshots of the simulation results are given in figure 1. The supplementary video shows some simulated sequences, which are compared to motion capture data. The simulated agents learned various interactive behaviors. They move around each other with light steps until they find openings for attacks, get close to each other and keep their guard up, respond fast to attacks by either dodging to the back or to the side for counter-attacks. Distinct roles and motion styles for each agent are also noticed.

Our future direction involves imitating reference motions with consistent physical contact between actors, as well as defining constraint-specific rewards to control the interactions. We also plan to evaluate the ability of this system to handle a wide variety of interactions.

Fig. 1 .

 1 Fig. 1. Simulated shadowboxing interactions between two physics-based characters.

ACKNOWLEDGMENTS

With the support of ANR in the framework of the PIA EUR DIGISPORT project (ANR-18-EURE-0022)


Hal Voepel

Tristan Berchoux

Steve Darby

Craig Hutton

Chris Hill

Guy Poppy

Le Quan

Hung Nguyen

Van Tri

Paul Whitehead

Andrew Nicholas

Dan Parsons

System Dynamics of Sustainable Rice Agriculture on the Mekong River Delta

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

Large river deltas across the globe are under increasing economic and environmental pressure due to overpopulation, climate change, and rising sea levels. River catchment sediments and associated discharge feed delta systems providing nutrients that not only enable higher yields in rice production but also the potential for flooding. Indeed, rice production on the Mekong River Delta (MRD) plays a main role in achieving food security for Vietnam, and provides significant export income for the Vietnamese economy (1.16% of GDP in 2018). To sustain high levels of rice production, the Vietnamese government has invested in a system of canals, flood dykes and sluice gates to control flooding of rice paddies and thereby extend the number of growing seasons from two to three rice harvests per year. However, these flood control measures have an unintended consequence in that, rather than allowing paddies to fallow, the exclusion of water and sediments from rice compartments means that soil nutrients become depleted and thus require artificial fertilizers to maintain yields. Furthermore, maintaining high levels of rice production is increasingly difficult as a result of climate change altering flood cycles, upstream hydro dam emplacement reducing sediment supply, and salinity intrusion shrinking available crop areas. In the face of these pressures MRD policy makers are facing pressing decisions in the delta and need to navigate the complexities of deltaic systems and identify optimal and sustainable land use management practices.

In this work we present the outcome of the application of an integrated Systems Dynamic Model (SDM) which emulates the distribution of biophysical components for water, suspended sediment, and nutrients over the delta, delivering a calibrated amount to each flood compartment. Biophysical components were calibrated using water quality routing model INCA (Integrated Catchment model), and the engineering hydraulics model MIKE 11 (with the ECO lab module). Spatial elements of the delta, such as soil type and land systems, are coupled to the SDM through a geographic information system (GIS). Model outputs of recent events provide a baseline to develop and test the SDM.

Here we show the results of the use of the (SDM) to integrate floods, nutrient supply, environmental/climate change and crop yields to facilitate stakeholders in the production of plausible normative spatially explicit scenarios of the agricultural intensification of the delta, centring on how intensification will occur and who will benefit. We use the SDM to explore scenarios covering the intensification range from local cooperatives that already exist to internationally funded agro-business. The question of livelihoods and community benefits is addressed in the normative outcomes as well as in the potential alignment and deviation form stated policy aims of the Government of Vietnam on the Mekong Delta.

Keywords: system dynamics, sediment transport, nutrient cycling, sustainability, agriculture, water supply management, water policy

  System dynamics of sustainable rice agriculture on the Mekong river delta Hal Voepel, Tristan Berchoux, Steve E. Darby, Craig W Hutton, Chris Hill, Guy Poppy, Le Quan, Nguyen Hung, Van P. D. Tri, Paul G. Whitehead, et al. To cite this version: Hal Voepel, Tristan Berchoux, Steve E. Darby, Craig W Hutton, Chris Hill, et al.. System dynamics of sustainable rice agriculture on the Mekong river delta. European Geosciences Union General Assembly 2019, Apr 2017, Vienne, Austria. European Geosciences Union, 21, pp.11073, 2019, Geophysical Research Abstracts. hal-03539040