Minyu Cui
email: minyu.cui@irisa.fr

Angeliki Kritikakou
email: angeliki.kritikakou@irisa.fr

Lei Mo

Emmanuel Casseau
email: emmanuel.casseau@irisa.fr

Fault-Tolerant Mapping of Real-Time Parallel Applications under multiple DVFS schemes

On multicore platforms, reliable task execution, as well as low energy consumption, are essential. Dynamic Voltage/Frequency Scaling (DVFS) is typically used for energy saving, but with a negative impact on reliability, especially when the frequency is low. Using high frequencies to meet reliability constraints is not always feasible, while multiple replicas increase energy consumption. To minimize energy consumption, enhancing reliability, without violating real-time constraints, we propose an approach that combines distinct reliability enhancement techniques, under task-level, processor-level and system-level DVFS. Our task mapping problem jointly optimizes task allocation, task frequency assignment, and task duplication, under multiple constraints. This is achieved by formulating the task mapping problem as a mixed integer non-linear programming problem and equivalently transforming it into a mixed integer linear programming, that is optimally solved. From the obtained results, the proposed approach achieves better energy consumption and finds solutions, when other approaches fail.

1 Introduction

Context

Hard real-time applications require both timing guarantees and reliable execution, i.e., tasks must finish correctly and before their deadlines. To ensure timing guarantees, a safe estimation of the Worst-Case Execution Time (WCET) of tasks is typically used. Nevertheless, the correct execution of tasks is threatened by sources that affect hardware platforms, such as radiation and electromagnetic interference, causing non-persistent transient faults (also known as soft errors). As technology size reduces, platforms become more susceptible to soft errors. Meanwhile, the energy consumption of embedded systems has become a crucial factor, especially for systems with a limited energy budget. As a result, adaptive management techniques have been established to maximize energy efficiency [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. DVFS is a technique that optimizes energy consumption by simultaneously scaling down the processor supply voltage and frequency, during execution. However, DVFS has a significant, negative impact on system reliability, mainly because of the increased transient fault rates at low supply voltage and frequency levels [START_REF] Zhao | On maximizing reliability of real-time embedded applications under hard energy constraint[END_REF]. Therefore, task mapping techniques must take into account the reliability degradation, energy consumption and execution time in order to make provisions accordingly, especially for real-time applications [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF].

Related work and motivation

Although both fault tolerance and energy management have been extensively (but often independently) studied, the co-management of system reliability and energy efficiency has been addressed only recently [START_REF] Zhao | Shared recovery for energy efficiency and reliability enhancements in real-time applications with precedence constraints[END_REF]. Table 1 depicts representative State-of-the-Art (SoA) task mapping approaches with DVFS, under Energy Budget (EB), Real-Time (RT) and Reliability (R) constraints, with maximizing system Reliability (mR) or minimizing Energy consumption (mE) goals. Fault tolerance is provided by Recovery tasks (Rec.) or task Replicas (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]. Tasks are Independent (I) or Dependent (D). The platform has a Homogeneous (HO), Heterogeneous (HE) or Single (S) processor. Based on the problem formulation and solving method, the solutions are Feasible (F) or Optimal (O).

Regarding reliability maximization, approaches without fault tolerance map only original tasks, e.g., through online heuristics [START_REF] Zhang | Maximizing reliability with energy conservation for parallel task scheduling in a heterogeneous cluster[END_REF]. Approaches with faulttolerance i) insert a recovery task, always executed with maximum frequency in case of an error [START_REF] Zhao | On maximizing reliability of real-time embedded applications under hard energy constraint[END_REF], ii) map a given number of task replicas [START_REF] Zhou | Resource management for improving soft-error and lifetime reliability of real-time MPSoCs[END_REF], and iii) decide the number of replicas during task mapping [START_REF] Wang | A reliability-aware task scheduling algorithm based on replication on heterogeneous computing systems[END_REF].

Regarding minimizing energy consumption, approaches exist without fault tolerance, e.g., by decomposing the task mapping problem into two sub-problems (satisfying reliability goal and minimizing resource consumption) [START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF]. To tackle the negative impacts of DVFS on reliability, existing techniques preserve the original system reliability for all tasks, i.e., the reliability obtained with the maximum platform frequency. Slack is reserved to execute a recovery task (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] Zhao | Shared recovery for energy efficiency and reliability enhancements in real-time applications with precedence constraints[END_REF]) with the maximum frequency. Then, DVFS scales down tasks. If an error is detected, the recovery task is evoked. A longesttask-first heuristic applies DVFS and recovery tasks only to a task subset [START_REF] Guo | Reliability-aware power management for parallel realtime applications with precedence constraints[END_REF]. However, such approaches usually require high frequencies to satisfy the original reliability, increasing energy consumption. It is also possible that reliability constraints cannot be satisfied, even with the maximum frequency, leading to empty solution space.

Other approaches compute the required number of replicas to always meet reliability constraints. Heuristics are typically proposed, due to high complexity, e.g., a first-fit decreasing heuristic for homogeneous platforms [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF] and a list scheduling heuristic for heterogeneous platforms [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. Hybrid approaches use a given number of replicas and apply task recovery, when an error occurs [START_REF] Salehi | Two-phase low-energy n-modular redundancy for hard real-time multi-core systems[END_REF]. However, the increased number of replicas leads to large energy consumption, combined with a negative impact on execution time. When the real-time constraints are strict, solutions may not exist. To reduce this negative impact, the number of replicas is restricted. In [START_REF] Salehi | DRVS: Power-efficient reliability management through dynamic redundancy and voltage scaling under variations[END_REF], a heuristic decides among single execution, task duplication and task triplication. However, no guarantees are provided on 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 of a recovery task, without considering any reliability constraint. An Integer Linear Programming (ILP) approach [START_REF] Tosun | Energy-and reliability-aware task scheduling onto heterogeneous MPSoC architectures[END_REF] maps independent tasks on a heterogeneous platform to satisfy a given percentage of duplicated tasks, under energy budget constraint. However, the reliability of tasks is not considered.

Contributions

This work belongs to the last category, extending the SoA by proposing an optimal task mapping approach, which decides between reliable single task execution and task duplication, under real-time and reliability constraints. The execution of a task is considered safe, when it meets its reliability constraint. Otherwise, the task requires duplication. As a result, the number of duplicated tasks is reduced, relieving the negative impact on execution time and energy consumption. We focus on the design-time phase, where task mapping and scheduling is performed offline. The goal is to minimize energy consumption, by optimally and concurrently deciding which tasks to be duplicated, the frequency per task and the task allocation, under both real-time and reliability constraints. Unlike the majority of SoA techniques, original and duplicated tasks can have different operating frequencies, being more suitable for realworld systems [START_REF] Zhou | Resource management for improving soft-error and lifetime reliability of real-time MPSoCs[END_REF]. To achieve that, the task mapping problem is formulated as a Mixed Integer Non-Linear Programming (MINLP), and safely transformed into a Mixed Integer Linear Programming (MILP) problem, in order to be solved optimally. Last, but not least, the proposed approach is extended for three DVFS schemes, typically supported by hardware platforms. To support our contribution, we performed extensive experiments, under different scenarios. From the results, the proposed approach can find feasible solutions, when existing replication approaches fail, and consumes less energy, compared to existing reliability-aware approaches. 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

Task Model

This work considers a real-time application consisting of N frame-based nonpreemptive dependent tasks {τ 1 , . . . , τ N }. The application is represented by a Directed Acyclic Graph (DAG) G(V, E), where V denotes the set of tasks and E represents the partial order, corresponding to the precedence constraints among tasks. All the tasks are released at time 0. The ready time of a task is the time instant at which all its predecessors have been completed. Each task τ i is defined by its deadline D i and Worst-Case Execution Cycles (WCEC) C i . The common period of the tasks is given by the application frame, denoted by H. Hence, the deadline D i cannot be larger than the application frame H, i.e., D i ≤ H. Different functions within an application exhibit distinct vulnerabilities to soft errors, 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]. Hence, each task τ i has its own reliability threshold R th i .

Platform Model

A shared-memory multicore platform is used with M homogeneous processors {θ 1 , . . . , θ M }. DVFS is possible at the task (TL-DVFS), processor (PL-DVFS) and system levels (SL-DVFS). Such variants correspond to DVFS-schemes in existing hardware platforms, e.g., clock frequency is controlled per core in Intel-Xeon E5620 and per 8 cores in GreenWaves GAP8. There are L pairs of frequency/voltage levels {(f 1 , v 1 ), . . . , (f L , v L )}. Similar to [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], the relationship of voltage and frequency is almost linear. Therefore, we use the term frequency scaling to express the simultaneous change of voltage and frequency. When task τ i is executed with frequency f l , its execution time is

t i = Ci f l .
The power consumption is modeled as the sum of static power P sta l and dynamic power P dyn l with the given voltage/frequency level (v l , f l ), i.e., P l = P sta l

+ P dyn l = P sta l + C ef f v 2 l f l ,
where C ef f is the effective switching capacitance [START_REF] Chen | Energy optimization for real-time multiprocessor system-on-chip with optimal DVFS and DPM combination[END_REF].

Processor Fault Model and Reliability

As transient faults have a higher occurrence than permanent faults [START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF], we focus on transient faults and fault detection is assumed to be done by the hardware. Our fault model is the one typically used by the SoA, such as [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] Wang | A reliability-aware task scheduling algorithm based on replication on heterogeneous computing systems[END_REF][START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF][START_REF] Salehi | Two-phase low-energy n-modular redundancy for hard real-time multi-core systems[END_REF], i.e., a Poisson distribution with an average fault rate λ(f ) at frequency f . Different frequency scalings yield various failure rates. The failure rate per time unit of a processor at frequency f is given by λ(f ) = λ 0 × 10 d0 fmax-f fmax-f min , 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 a task τ i is defined as the probability of executing a task without any fault, based on the exponential model of [START_REF] Zhu | The effects of energy management on reliability in real-time embedded systems[END_REF]. Therefore, the reliability of a task with WCEC C i at frequency f l is r i (f l ) = e -ϕi(f l ) , where ϕ i (f l ) = λ(f l ) × t i , and t i = Ci f l is the execution time of task τ i at frequency f l [START_REF] Zhao | On maximizing reliability of real-time embedded applications under hard energy constraint[END_REF][START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF][START_REF] Zhu | The effects of energy management on reliability in real-time embedded systems[END_REF]. If the reliability of task τ i is larger than its reliability threshold R th i , the execution is considered to be reliable [START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF] and the task reliability is not modified, i.e., R i = r i (f l ). Otherwise, the task τ i is duplicated and the duplicated task is 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]. If the duplicated task τ N +i (task index N + i is defined in Section 3) is executed with frequency f l , its reliability is r N +i (f l ). Therefore, the total reliability is

R i = 1 -[1 -r i (f l )][1 -r N +i (f l )].
As our approach finds an offline optimal 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].

3 Reliability-aware Fault-tolerant Task Mapping Approach

The proposed Reliability-aware Fault-tolerant Task Mapping (RAFTM) approach minimizes the system energy consumption subject to a set of reliability and real-time constraints. It concurrently decides: 1) task frequency assignment (s), 2) task duplication decision (σ), 3) task allocation (q), and 4) task start time (t s ). Note that the task set is extended with N duplicated tasks, i.e., N = {1, . . . , N, N + 1, . . . , 2N }. Tasks {τ 1 , . . . , τ N } are original tasks and tasks {τ N +1 , . . . , τ 2N } are duplicated tasks. Hence, task τ N +1 is the duplicated task of τ 1 . Duplicated tasks have the same WCEC and deadline as the original ones. Although initially all tasks are considered duplicated, the approach decides whether the duplication is maintained, through variables σ i , according to the real-time and reliability constraints. A task waits for both original and duplicated tasks of its predecessors to end, before starting execution [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF]. The proposed approach's formulation is initially presented for a multicore platform supporting the TL-DVFS scheme. Then, it is adapted for PL-DVFS and SL-DVFS schemes.

C i WCEC of task τ i D i deadline of task τ i (v l , f l ) the l th voltage/frequency level R th i reliability threshold of task τ i O ij O ij = 1 if task τ j is dependent on task τ i , else, O ij = 0
Binary Variables

σ i = 1 if task τ i is executed, else 0 q im = 1
if task τ i executes on processor θm, else 0 w ij = 1 if task τ i executes before task τ j on same processor, else 0 TL-DVFS:

s il = 1, if task τ i executes with f l , else 0 PL-DVFS: s ml = 1, if processor θm executes with f l , else 0 SL-DVFS: s l = 1, if the system executes with f l , else 0 Continuous Variables t s i the start time of task τ i Table 2: Main Notations 3.1 Task-Level DVFS scheme (TL-DVFS)
The following paragraphs describe the constraints and the objective function of the task mapping TL-DVFS problem and its equivalent transformation.

Frequency assignment

Each task has a single frequency:

l∈L s il = σ i , ∀i ∈ N .
(1)

Reliability and Task duplication decision

For an original task

τ i (1 ≤ i ≤ N ), σ i = 1.
Its reliability is expressed as

r i = l∈L s il e -ϕi(f l ) , where ϕ i (f l ) = λ(f l ) × Ci f l (Section 2.3). If r i > R th i , task τ i does not need duplication (σ N +i = 0). Else, if 0 < r i ≤ R th i , the task τ i is duplicated, i.e., σ N +i = 1.
To transfer this "if-else" constraints into linear mathematical formula, we use the following Lemma: Lemma 1 Let x and y denote two discrete variables where 0 < x min ≤ x ≤ x max ≤ 1 and 0 < y min ≤ y ≤ y max ≤ 1. Let c denote a binary variable. Given the determination i) if 0 < x ≤ y, c = 1, and ii) if x > y, c = 0, then the determination can be equivalently transferred into δ -

(1 + δ)c ≤ x -y ≤ 1 -c,
where δ is a positive small value.

Proof To prove that the given determination can be equivalently transferred into the linear constraint, we first let

C 1 : δ -(1 + δ)c ≤ x -y and C 2 : x -y ≤ 1 -c. i) If x < y, then x -y < 0. For C 1 , c must be 1. For C 2 ,
c can be either 0 or 1. To satisfy both C 1 and C 2 , we have c = 1. If x = y, for C 1 , c must be 1 due to x -y = 0 and δ > 0. For C 2 , c can be either 0 or 1. Similarly, we obtain c = 1. ii) If x > y, for C 1 , c can be either 0 or 1. However, c must be 0 in C 2 due to x -y > 0. Hence, c must be 0 if x > y.

Since there are L pairs of voltage/frequency, we have r i ∈ {e -ϕi(f1) , . . . , e -ϕi(f L ) }. On this basis, the relationship between R i , r th i and σ i is linearized as:

δ i -(1 + δ i )σ N +i ≤ l∈L s il e -ϕi(f l ) -R th i ≤ 1 -σ N +i , ∀i ∈ N . (2)
Thus, the reliability of task

τ i becomes R i = (1 -σ N +i )r i + σ N +i [1 -(1 - r i )(1-r N +i )]
, where r i is the reliability of original τ i and r N +i is the reliability of duplication task τ N +i , if duplication takes place. However, if the reliability after duplication does not satisfy the reliability threshold, then the solution is not acceptable, so we have to guarantee that the reliability of a task considering duplication should not be smaller than its reliability threshold

R i ≥ R th i , ∀i ∈ N . (3)

Task allocation

A task τ i is executed on one processor:

m∈M q im = σ i , ∀i ∈ N . (4)
If task τ i is duplicated, original and duplicated tasks should be allocated on different processors. We have:

q im + q N +i,m ≤ 1, ∀i ∈ N , ∀m ∈ M. (5)

Task non-overlapping

When task τ i is executed on processor θ m with frequency f l , its execution time is l∈L s il Ci f l and, as tasks are executed in a non-preemptive manner, its end time is t e i = t s i + l∈L s il Ci f l . We need to guarantee that a task execution cannot overlap with any other task execution, when assigned to the same processor. The ordering of tasks, assigned on the same processor, is given by a matrix w = [w ij ] 2N ×2N . For any two tasks τ i and τ j , when w ij = 1, tasks τ i and τ j are allocated on the same processor, and τ i is executed before τ j . Otherwise, either τ i and τ j are allocated on different processors or τ i is executed after τ j . Therefore, when both q im = 1 and q jm = 1, only one of w ij and w ji can be equal to 1, i.e., w ij + w ji = 1. Otherwise, both w ij and w ji are equal to 0, i.e., w ij + w ji = 0. On this basis, the non-overlapping constraints are formulated as:

t e i ≤ t s j + (2 -q im -q jm )H + (1 -w ij )H, ∀i, j ∈ N , ∀m ∈ M, i = j, (6)
w ij + w ji = m∈M q im q jm , ∀i, j ∈ N , i = j, (7)
where H = max ∀i∈N {D i }.

Task dependencies

Based on the task graph, we introduce a Task Dependency 8) is always satisfied.

matrix o = [o ij ] 2N ×2N . When o ij = 1, task τ i precedes τ j and (8) becomes t s j ≥ t s i + l∈L s il Ci f l . Oth- erwise, (
t s j + (1 -o ij )H ≥ t s i + o ij l∈L s il C i f l , ∀i, j ∈ N , i = j. (8)

Real-time execution

Since all tasks should be executed before their deadline D i , for each task:

t s i + l∈L s il C i f l ≤ D i , ∀i ∈ N . (9)

Objective Function

The system energy consumption is:

E s = i∈N l∈L s il C i f l P l , (10)
Thus, the Primal Problem (PP) is formulated as an MINLP:

PP : min s,q,σ, w,t s i∈N l∈L s il C i f l P l s.t.      (1) ∼ (9) s il , q im , σ i , w ij ∈ {0, 1}, 0 ≤ t s i ≤ D i , ∀i ∈ N , ∀m ∈ M, ∀l ∈ L.
In order to find the optimal solution, we simplify the problem structure by transforming PP to an equivalent MILP, through variable replacement, which removes the nonlinear variable combinations based on the following lemma:

Lemma 2 Let b 1 , b 2 and g denote binary variables. The nonlinear item g = b 1 b 2 can be replaced by i) g ≤ b 1 , ii) g ≤ b 2 and iii) g ≥ b 1 + b 2 -1. Proof Inequalities g ≤ b 1 and g ≤ b 2 ensure that g is zero, if either g ≤ b 1 or g ≤ is zero. Equality g ≥ b 1 + b 2 -1 ensures that g becomes 1, if both variables b 1 and b 2 are 1.
Let h m ij = q im q jm (i, j ∈ N , m ∈ M, i = j) and h m ii = 0, when i = j. (7) can be equally expressed as

w ij + w ji = h m ij , ∀i, j ∈ N , i = j, (11)
-

q im + h m ij ≤ 0, -q jm + h m ij ≤ 0, q im + q jm -h m ij ≤ 1, ∀i, j ∈ N , ∀m ∈ M, i = j. (12)
Then, PP is reformulated as the following MILP problem:

RAFTM-TL : min s,q,σ, w,h,t s i∈N l∈L s il C i f l P l s.t.     
(1) ∼ ( 6), ( 8) ∼ (9), ( 11)

∼ (12), s il , q im , σ i , w ij , h m ij ∈ {0, 1}, 0 ≤ t s i ≤ D i , ∀i ∈ N , ∀m ∈ M, ∀l ∈ L.

Processor-Level DVFS scheme (PL-DVFS)

For platforms supporting PL-DVFS, each processor can have a single frequency level:

l∈L s ml = 1, ∀m ∈ M, (13)
For a task τ i , the frequency is m∈M q im l∈L s ml f l , the reliability is R i = m∈M q im l∈L s ml e -ϕi(f l ) and the execution time is m∈M q im l∈L s ml Ci f l . These equations replace the corresponding equations of RAFTM-TL, and the proposed approach with PL-DVFS is formulated as

RAFTM-PL : min s,q,σ, w,t s i∈N m∈M q im l∈L s ml C i f l P l s.t.     
(2) ∼ (9), ( 13)

s ml , q im , σ i , w ij ∈ {0, 1}, 0 ≤ t s i ≤ D i , ∀i ∈ N , ∀m ∈ M, ∀l ∈ L.

System-Level DVFS scheme (SL-DVFS)

For platforms supporting SL-DVFS, all processors are assigned with same frequency:

l∈L s l = 1. ( 14
)
For a task τ i , the frequency is l∈L s l f l , the reliability is R i = l∈L s l e -ϕi(f l ) and the execution time is l∈L s l Ci f l . Then, the proposed approach with SL-DVFS is formulated as RAFTM-SL : min s,q,σ, w,t s i∈N l∈L

s l C i f l P l s.t.     
(2) ∼ (9), ( 14)

s l , q im , σ i , w ij ∈ {0, 1}, 0 ≤ t s i ≤ D i , ∀i ∈ N , ∀m ∈ M, ∀l ∈ L.

Experimental Results

Experimental set-up

The processor model is a RISC-V Instruction Set Architecture (ISA), i.e., the open-source Comet processor, which is a high-level C++ model 32-bit RISC-V ISA and standard 5-stage pipeline [START_REF] Rokicki | What you simulate is what you synthesize: Designing a processor core from c++ specifications[END_REF]. Regarding the DVFS, L = 6 voltage/frequency levels are used [START_REF] Quan | Feasibility analysis for temperature-constraint hard realtime periodic tasks[END_REF] considering 64 nm technology, as depicted in Table 3. To obtain realistic inputs for our experiments, we count the execution cycles and Memory Accesses (MA) of common benchmarks from MiBench suite [START_REF] Guthaus | Mibench: A free, commercially representative embedded benchmark suite[END_REF], using Comet simulator. The sources of timing variability are eliminated to obtain safe and context-independent measurement [START_REF] Deverge | Safe measurement-based wcet estimation[END_REF] without interferences (WCEC iso ). Then, the WCEC inf , considering worst case interferences from the other cores, is computed. As the contribution of this paper is not WCET estimation, a trivial pessimistic approach is applied: all cores may conflict during a memory access. Thus, the interference cost is given by (M-1)*MA*Main Memory Access Delay (Table 3).

The proposed Reliability-Aware Fault-Tolerant Mapping (RAFTM) approach is compared to two SoA approaches: i) a Reliability-Aware Mapping (RAM) approach, which chooses the frequency to satisfy the reliability constraint for each task without task replication, similar to [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], and ii) a Task Duplication Mapping (TDM) approach, which always duplicates every task, similar to [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF] and [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF] (when the replica number of each task is equal to two) and to [START_REF] Tosun | Energy-and reliability-aware task scheduling onto heterogeneous MPSoC architectures[END_REF] (when the percentage of duplicated task is set to 100%). RAM is the common way to meet the expected reliability without taking replication into account. Considering task replication, TDM is the least energy consuming approach, compared to other methods that use more than two replicas per task. A large and diverse set of experiments is performed, by tuning the: -WCEC: Based on WCEC inf (Table 3), the WCEC of each task is selected within the range [1 × 10 8 , 4 × 10 8 ], incorporating the time overhead for frequency (and supply voltage) changes (e.g., 10-150 µs [START_REF] Zhang | Joint optimization of energy efficiency and system reliability for precedence constrained tasks in heterogeneous systems[END_REF][START_REF] Guo | Reliability-aware power management for parallel realtime applications with precedence constraints[END_REF]) and the sanity checks at the end of a task [START_REF] Haque | On reliability management of energy-aware realtime systems through task replication[END_REF].

-Reliability threshold R th i : Selected within the range [0.9990, 0.9999], 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]. Such a reliability target for a task is inline with safety standards, such as ISO26,262 for automotive systems, DO-178B for avionics systems and IEC 61,508 for industrial software systems [START_REF] Xie | Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems[END_REF] To evaluate the approaches, the following metrics are used:

1. Feasibility, i.e., percentage of experiments that found the optimal solution in these 10 experiments. 2. Energy consumption of RAM and TDM, compared to the energy consumption of the proposed RAFTM approach. 3. Reliability Improvement (RI = R i -R th i ), i.e., the task reliability above the reliability threshold. 4. Task duplication, i.e., the percentage of tasks that RAFTM decided to duplicate. 5. Time, i.e., the time required for each approach to find a solution.

To better explain the performance, we organize our experiments in two set-ups of reliability threshold:

1. Set-up 1: The task reliability threshold can always be met by executing only the original task using a high processor frequency. To achieve that, the reliability threshold is selected within [0.9990, 0.9995] and the average failure rate λ 0 equal to 5 × 10 -5 faults/sec. In this set-up, the feasibility of RAFTM and RAM are the same. 2. Set-up 2: The task reliability threshold cannot always be met by executing only the original task, even at maximum frequency. To achieve that, the range of reliability constraint is increased, i.e., [0.9990, 0.9999]. We explore the behavior of the proposed RAFTM and RAM approaches with the average failure rate λ 0 is equal to 5 × 10 -5 , 4 × 10 -4 , and 5 × 10 -4 faults/sec.

Feasibility

The feasibility of RAFTM, RAM and TDM is depicted in Fig. 1, for N = 10 and N = 20 with M = 4, and for N = 20 with M = 6.

Regarding the comparison with TDM, RAFTM is able to find solutions in significantly more experiments than TDM, since RAFTM is not obliged to duplicate reliable tasks, compared to TDM. When feasibility is not 100% for both approaches, RAFTM can find a solution, on average, in 30%, 33% and 10% more experiments, than TDM (Fig. 1). When k = 1, 1.1, 1.2 (N = 20 and M = 4), TDM cannot find any solution. As the number of processors is increased, e.g., from M = 4 to M = 6, the capability of TDM to find solutions improves, as more cores are available to schedule the duplicated tasks. Note that RAFTM achieves 100% feasibility in earlier deadlines than TDM, i.e., k = 0.8 (N = 10 and M = 4) and k = 1.5 (N = 20 and M = 4, N = 20 and M = 6). When the deadline becomes relaxed (and TDM can always find solutions), i.e., k = 0.9 (N = 10 and M = 4), k = 1.9 (N = 20 and M = 4), Regarding the comparison with RAM, in this experimental set-up, RAFTM and RAM have the same feasibility, since the reliability constraints can always be met by executing only the original task with a high processor frequency. Note that, we explore the difference of feasibility between RAFTM and RAM, in the experimental set-up 2, where high frequencies cannot always satisfy reliability thresholds. We observe that the feasibility of RAFTM and RAM is not modified as the number of cores is increased, due to the dependencies of the task graph. However, since TDM requires to duplicate all tasks, its feasibility is increased with more processors, approaching the RAFMT and RAM feasibility with 6 processors.

Energy consumption

The energy consumption of RAM and TDM, compared to the proposed approach, is depicted in Fig. 3. The minimum, average and maximum gains are depicted in Table 4. Note that, the minimum gain is 0 between TDM and RAFTM, when the deadlines are less strict. When deadline is relaxed, RAFTM performs duplication for all tasks, as TDM. For RAM, we observe a minimum gain of 0, only in very few strict deadlines, either with a high number of tasks or due to SL-DVFS, where the frequency assignment is very restricted. In the strict deadlines, RAFTM and RAM have a similar behavior: applying a high frequency to meet the timing constraint, thus no duplication is possible. From the obtained results, we can make the following general observations:

-When the number of tasks is increased from N = 10 to N = 20 with the same number of cores (from Fig. 3a to Fig. 3d, from Fig. 3b to Fig. 3e, and from Fig. 3c to Fig. 3f), the energy savings remain high for the proposed RAFTM approach, compared to RAM and TDM. We observe a slight decrease in average savings regarding RAM in TL-DVFS and PL-DVFS schemes, due to the fact that RAFTM behaves as RAM in very strict deadlines. On the one hand, RAM consumes more energy compared to RAFTM, as Table 4 shows. On the other hand, RAFTM is able to find solutions in more cases, compared to TDM, especially for strict deadlines, as Fig. 1 shows.

-When the number of cores increases from M = 4 to M = 6, with the same number of tasks N = 20, (from Fig. 3d to Fig. 3g, from Fig. 3e to Fig. 3h, and from Fig. 3f to Fig. 3i), the energy savings of RAFTM compared to RAM are enlarged, on average, to 38.9% (TL-DVFS), 36.72% (PL-DVFS), and 64.29% (SL-DVFS). This is supported by the fact that when more resources like processors are available, our proposed approach has more freedom to use the available processors when performing the task mapping, minimizing the total energy consumption. -Among different DVFS schemes, we observed that SL-DVFS has a higher impact on the observed gains of RAFTM vs RAM, compared to the impact it has on the observed gains of RAFTM vs TDM, as the number of tasks and cores increases. When the supported DVFS scheme is flexible, RAM performs a more fine-grained assignment, achieving a lower energy consumption. However, when SL-DVFS is supported, RAM is obliged to select a high frequency in order to meet the highest reliability threshold of the tasks and executes all tasks with this high frequency, causing large energy consumption. On the other hand, the proposed RAFTM can exploit task duplication, applying a lower frequency, and thus, reducing the energy consumption, when time slack is available for relaxed deadline cases.

With a more detailed observation, when both RAFTM and TDM approaches can find solutions, RAFTM provides a solution that consumes significantly less energy. More precisely, when N = 20 and M = 4, for TL-DVFS we observe a maximum gain of 123.05%, with an average gain of 49.67%, for PL-DVFS, we observe a maximum gain of 148.21% with an average gain of 67.3%, and, for SL-DVFS, there is a maximum gain 132.08%, with an average gain of 63.94%. Furthermore, RAFTM finds a solution, that consumes less energy than RAM, since RAFTM can duplicate some tasks in order to use lower frequencies, reducing energy consumption. When the deadline is not so strict (part of graph with almost flat average gain in the box-plot of Fig. 3), the highest energy gains are observed. More precisely, when M = 4, we observe an average gain of 54.01% (TL-DVFS), 50.5% (PL-DVFS), and 73.48% (SL-DVFS) for N = 10 and an average gain of 54.27% (TL-DVFS), 48.88% (PL-DVFS), and 92.19% (SL-DVFS) for N = 20. When M = 6 and N = 20, the observed average gain is 57.98% (TL-DVFS), 57.06% (PL-DVFS), and 102.11% (SL-DVFS). For very strict deadlines, the energy gains of RAFTM and RAM are similar; RAFTM behaves as RAM, since there is no available time slack, and thus, RAFTM assigns high frequencies, without task duplication. We observe minimum gains when k = 0.5 (N = 10) and k = 1 (N = 20). When SL-DVFS and less cores are used (M = 4), RAFTM cannot exploit duplication and use different frequencies to reduce energy consumption, and thus, it behaves as RAM. When time slack exists, RAFTM can take advantage of it and duplicate some tasks, if energy gains can be achieved.

Reliability Improvement

We also compare the reliability improvement with regard to the reliability threshold in Fig. 4, for the three DVFS schemes and for N = 10 and N = 20, with M =4, and N = 20, with M =6. Generally:

-Regarding RAM, when TL-DVFS is considered, it has the lowest reliability improvement. This is because RAM only requires to meet the reliability threshold in order to find a solution. However, when PL-DVFS and SL-DVFS are considered, RAM is obliged to select a higher frequency, even for tasks with lower reliability threshold, due to the restrictions in the DVFS schemes. As a result, the reliability improvement of RAM is increased, when the DVFS schemes are more restricted. Note that, when the number of tasks is increased in SL-DVFS, RAM is obliged to always select high frequencies to meet the highest reliability threshold, among all tasks, and then, use this frequency for task execution, even if time slack exists. -Regarding RAFTM, it provides higher reliability improvements than RAM, for all deadlines. For tight deadlines, it provides lower reliability improvements than TDM, as it partially duplicates the task set. However, as discussed in the previous section, RAFTM is more capable of finding solutions compared to TDM, and with significantly reduced energy consumption. When the deadline is not so strict, it provides the same reliability improvements as TDM, since they behave in a similar way. -Regarding TDM, since it always duplicates the tasks, it provides a high reliability improvement, if it can find a solution. Therefore, going from TL-DVFS to PL-DVFS and SL-DVFS, does not have a high impact on the reliability improvement. Moreover, when a solution is found in strict deadlines, it has typically significant reliability improvement, at the price of high energy consumption, since high frequencies are required to meet the strict timing constraints.

RAFTM duplication

Fig. 5 depicts the task duplication obtained by the proposed approach. RAM approach does not apply duplication for any task (0%) and TDM duplicates all tasks (100%). Generally observed for all DVFS schemes, when the deadline is more relaxed, RAFTM can duplicate more tasks using lower frequency, thus achieving less energy consumption, due to the available time slack. Furthermore, as all processors have the same frequency in SL-DVFS, this DVFS scheme has less flexibility in task duplication and scheduling, when deadlines are strict. In Fig. 5, there are two interesting observations: i) for some points, the duplication percentage decreases, when deadline is relaxed (Fig. 5b, when k = 1.2 for TL-DVFS, and Fig. 5c, when k = 1.2 for both TL/PL-DVFS), and ii) the duplication percentage does not reach 100% for TL/PL-DVFS, as SL-DVFS does. The reason is the flexibility to decide the task frequency for different DVFS schemes, and the reliability threshold's value. When the task's reliability threshold can be satisfied without duplication and with a low frequency, and energy consumption is less than the energy consumption when duplicating with the lowest frequency, then TL-DVFS and PL-DVFS schemes do not duplicate the task. However, with SL-DVFS, the same frequency must be assigned to all processors. Hence, a task with a high reliability constraint forces other tasks with low reliability constraints to execute with a higher frequency than the required one. As a result, duplication does not provide benefits, even if time slack exists. Due to these reasons, the duplication percentage is usually smaller for SL-DVFS, compared to TL/PL-DVFS, except for relaxed enough deadlines.

Time

Tables 5 to 7 provide the time required to find a solution, when N = 10 and N = 20 with M = 4, and N = 20 with M = 6. Comparing Table 6 and Table 5, with more tasks, more time is required to find a solution, as expected. For RAFTM, when deadline is very strict or very relaxed, less time is needed to obtain the solutions. However, with intermediate deadlines, more time is required as RAFTM needs to explore the available time slack to decide which, and how many, tasks to be duplicated, without violating constraints, while consuming the least energy. TDM is the most running time expensive approach, because all tasks need to be duplicated, increasing the number of tasks to be scheduled, and thus, the time to find the solutions. Although RAM is the least running time expensive approach, it provides less energy savings.

Experimental set-up 2

In this experimental set-up, we explore the behavior of RAFTM and RAM at different failure rates λ 0 under TL-DVFS scheme. First, we extend the range of the task reliability threshold, in order to have few tasks with higher reliability requirements. Then, we tune the parameter λ 0 in order to change the failure rate. This experimental set-up shows how the fault model influences the ability of obtaining feasible solutions, through a slight increase of λ 0 . The results show that the proposed approach provides better results than RAM, with the fault rate changing. These modifications will affect only the proposed RAFTM and RAM approaches, since they use the reliability constraint to decide the task mapping. The results of TDM remain similar to the previous section.

Feasibility

The first column of Fig. 6 depicts the ability of RAM, compared to RAFTM, to obtain feasible solution, for λ 0 = 4×10 -4 (Fig. 6a and Fig. 6c) and λ 0 = 5×10 -4 (Fig. 6b and Fig. 6d), with N = 10 and N = 20, M = 4. Generally:

-As the λ 0 increases, the reliability of a task, due to the processor fault rate, is decreased. Therefore, with λ 0 increasing, the capability of RAM to always find a frequency, that meets the reliability threshold of all tasks, decreases, especially for tasks with high reliability requirements. Furthermore, even with λ 0 increasing, RAFTM is able to still meet these high reliability requirements, by duplicating tasks and assigning a high frequency. This can be observed by comparing Fig. 6a to Fig. 6d, where the feasibility of RAM is reduced by 20%, and Fig. 6g to Fig. 6j, where the feasibility of RAM is reduced by 30%. However, RAFTM feasibility remains the same, always finding a solution at relaxed deadlines. -As the number of tasks increases, the feasibility is affected. As we observe by comparing Fig. 6a to Fig. 6g and Fig. 6d to Fig. 6j, the curves of RAM and RAFTM separate at stricter deadlines, when N = 20, compared to the ones when N = 10. Comparing the feasibility between set-up 1 and set-up 2, we observe that the feasibility of set-up1 can be 100% for both RAFTM and RAM, with a smaller average fault rate λ 0 at relaxed deadlines. However, with the average fault rate increasing, it is not possible for RAM to find a solution satisfying the reliability requirements, even with maximum frequency and relaxed deadline. This observation worsens with λ 0 increasing. Thus, with a different fault model, executing only the original task may not be able to provide reliable execution. Therefore, replication is needed in order to guarantee the reliability threshold of the tasks.

Energy consumption

The second column of Fig. 6 depicts the energy consumption of RAM, compared to the proposed approach, when RAM found a solution.

-As the λ 0 increases, the processor sensibility to faults is increased. Then, the energy gains are slightly reduced, from 12.05% to 8.87% (N = 10, Fig. 6b to Fig. 6e) and from 12.60% to 10.75% (N = 20), Fig. 6h to Fig. 6k, since RAFTM also selects a high frequency, in order to meet the high reliability thresholds of tasks. -As the number of tasks increases, the gains in energy consumption remain similar. As we observe by comparing Fig. 6b to Fig. 6h and Fig. 6e to Fig. 6k, the energy savings are decreased, compared to set-up 1. For instance, from 36.65% (set-up 1) to 12.05% and 8.87%, when N = 10 and M = 4. This is due to the fact that, based on λ(f ) (see Section 2.3), the reliability with same frequency decreases, when λ 0 increases. In order to guarantee a reliable execution, a high frequency must be assigned to meet the reliability requirement, leading to higher energy consumption for the proposed approach.

Reliability improvement

The third column of Fig. 6 depicts the reliability improvement of RAFTM and RAM, for the cases where RAM was able to find a solution. On the basis of satisfying the reliability requirements, RAM achieves a slightly better reliability improvement than our approach, while it sacrifices the ability of obtaining feasible solutions.

RAFTM Duplication

The percentage of duplicated task is depicted in Fig. 7. As Based on the fault model in Section 2.3, the reliability decreases with higher λ 0 . When the timing constraints are always satisfied, a higher λ 0 with the same frequency, leads to lower reliability. To meet reliability constraints, either a very high frequency is assigned to original tasks, or a relative high frequency is required for both original and duplicated tasks. The first option consumes less energy.

As observed in Fig. 7a and Fig. 7b, with relaxed deadlines, RAFTM duplicates more tasks when λ 0 = 4 × 10 -4 .

Time

Table 8 and 9 give the time needed to obtain a solution for our proposed RAFTM and RAM after the extension of fault rate λ 0 . Similar to the time analysis in set-up 1, RAM needs less running time than our proposed approach when finding a feasible solution, at the price of more energy consumption and less ability to obtain feasible solutions.

Conclusion

This work proposes a RAFTM approach for dependent tasks and homogeneous platforms, under several DVFS schemes. It jointly decides the frequency assignment to tasks, task allocation to processors and tasks to be duplicated, minimizing energy consumption, under real-time and reliability constraints. RAFTM approach is compared with a reliability-aware task mapping approach and a fault-tolerant task mapping approach, under several scenarios. The results show that RAFTM finds solutions, when other approaches fail. TL-DVFS achieves less energy consumption, due to flexibility in task frequency assignment, compared to SL-DVFS. RAFTM provides more energy savings, and, at the same time, higher feasibility, without violating timing and reliability constraints, under the possible DVFS schemes. In future, we will extend RAFTM for heterogeneous platforms and controlled heuristics.

1 .

 1 Number of processors (M = 2, 4, 6). 2. Platform DVFS scheme (TL-DVFS, PL-DVFS and SL-DVFS). 3. Average failure rate (λ 0 = 5 × 10 -5 , 4 × 10 -4 , 5 × 10 -4 faults/sec) with a failure rate constant (d 0 = 3) of processor fault model [17]. 4. Size of task set (N = 10, 20, 30). 5. For a task set size, 10 experiments are performed. For each experiment, the characteristics of a task are:

  [START_REF] Xie | Resource consumption cost minimization of reliable parallel applications on heterogeneous embedded systems[END_REF].-Deadline: Tuned from strict deadlines to relaxed ones, by changing k inD i = ts i + k * d i ,where ts i is the relative start time of task τ i equal to max ∀j∈P re{i} {D j } (with P re{i} the predecessors of task τ i ) and the relative deadline given by d i ∈ Ci fmax , Ci fmin . Note that the above numbers provide only specific values to problem parameters, without affecting the problem structure. The approaches are implemented and solved with Gurobi 9.0.1 (MILP solver) on several servers, as hundreds of experiments took place. Due to page limitations, we present a subset of the experiments (TL-DVFS, PL-DVFS and SL-DVFS for N = 10, M = 4, N = 20, M = 4, and N = 20, M = 6) and we comment on the rest of the experiments.

6 Fig. 1 :

 61 Fig. 1: Feasibility for a) N = 10, M = 4, b) N = 20, M = 4, and c) N = 20, M = 6 for all DVFS schemes.

4. 2 6 Fig. 2 :

 262 Fig. 2: RAFTM duplication percentage: a) N = 10, M = 4, b) N = 20, M = 4, and c) N = 20, M = 6 (all DVFS schemes).

Fig. 3 :

 3 Fig. 3: Energy Consumption (EC) gain: N = 10, M = 4 (a, b, c), N = 20, M = 4 (d, e, f), and N = 20, M = 6 (g, h, i).

Fig. 4 :

 4 Fig. 4: Reliability improvement: N = 10, M = 4 (a,b,c), N = 20, M = 4 (d,e,f), and N = 20, M = 6 (g,h,i).

6 Fig. 5 :

 65 Fig. 5: RAFTM duplication percentage: a) N = 10, M = 4, b) N = 20, M = 4, and c) N = 20, M = 6 (all DVFS schemes).

(a) λ 0 = 4 ×Fig. 6 :

 46 Fig. 6: TL-DVFS: Feasibility (first column), Energy Consumption (EC) gain (second column) and Reliability Improvement (RI) (third column) for λ 0 = 4 × 10 -4 and λ 0 = 5 × 10 -4 , with N = 10 and N = 20 (M = 4).

Fig. 7 :

 7 Fig. 7: RAFTM duplication percentage (TL-DVFS): a) N = 10, and b) N = 20, for λ 0 = 4 × 10 -4 and λ 0 = 5 × 10 -4 , with M = 4.

Table 1 :

 1 Comparison with representative State-of-the-Art

	Ref.	Goal	Fault tol. Tasks

  Table 2 summarizes the notation.

Parameters M {1, . . . , M }, with M number of processors N {1, . . . , N }, with N number of tasks N {1, . . . , 2N }, with 2N number of tasks L {1, . . . , L}, with L number of voltage/frequency levels

Table 3 :

 3 Platform and benchmark 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
	Main Memory Access Delay	200 cycles
	Benchmark MA WCEC iso	M = 2	WCEC inf M = 4	M = 6
	matmul int	371,957 3,313,958 77,705,358 226,488,158 449,662,358
	matmul int64 507,133 4,055,289 78,446,689 308,335,089 612,614,889
	qsort int	184,089 875,616 75,267,016 111,329,016 221,782,416
	qsort int64	259,553 1,219,854 75,611,254 156,951,654 312,683,454
	qsort float	185,437 1,745,122 76,136,522 113,007,322 224,269,522
	dijkstra	117,151 766,369 75,157,769 71,056,969 141,347,569
	blowfish	110,330 3,058,991 77,450,391 69,256,991 135,454,991
	stringsearch 597,608 13,093,544 87,484,944 371,658,344 730,223,144

Table 4 :

 4 Min, avg. and max energy gains (%)

				TL-DVFS		PL-DVFS		SL-DVFS
	N M Min Avg.	Max	Min Avg.	Max	Min Avg.	Max
					RAM -RAFTM
	10	4	4.8	36.65	55.1	2.11 31.46	52.64	0	42.90	78.31
	20	4	1.16 29.19	57.35	0	23.25	54.87	0	42.2	105.33
	20	6	9.76 38.97	59.14	8.63 36.72	58.84	0	64.29 105.94
					TDM -RAFTM
	10	4	0	47.34 128.52	0	56.52 177.58	0	65.86 170.68
	20	4	0	49.67 123.05	0	67.3	148.21	0	63.94 132.08
	20	6	0	30.54	91.21	0	37.15 116.08	0	53.09 115.16

Table 5 :

 5 Running time (seconds), when at least one solution is found, with N = 10, M = 4

		deadline(k) 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 1.05 1.1 1.15 1.2
		RAFTM 0.45 0.57 0.95 2.17 3.31 4.31 3.77 3.11 5.57 1.47 1.92 3.71 0.51 0.3 0.27
	TL DVFS	RAM	0.3 0.25 0.27 0.22 0.43 0.33 0.16 0.16 0.21 0.18 0.18 0.16 0.19 0.16 0.19
		TDM	2.52 0.56 0.61 0.97 1.53 2.65 2.45 2.08 1.26 1.08 0.72 0.72 0.55 0.36 0.37
		RAFTM 1.65 6.03 8.2 15.26 24.06 32.3 34.38 40.76 29.12 29.05 13.9 13.54 10.94 4.19 3.51
	PL DVFS	RAM	0.82 1.78 1.51 1.7 1.94 1.72 1.79 1.79 2.15 2.22 1.87 1.88 2.1 1.77 1.84
		TDM	2.55 2.27 1.7 4.45 5.97 9.17 5.04 4.97 4.83 3.61 3.22 2.47 2.34 1.84 1.87
		RAFTM 0.28 0.19 0.26 0.83 1.47 1.86 1.18 1.13 0.84 0.92 0.67 0.59 0.53 0.27 0.23
	SL DVFS	RAM	0.11 0.08 0.11 0.09 0.19 0.2 0.2 0.07 0.09 0.08 0.08 0.09 0.09 0.08 0.08
		TDM	0.48 0.14 1.02 1.64 1.51 2.5 1.83 1.59 1.43 1.7 0.88 0.68 0.71 0.54 0.44

Table 6 :

 6 Running time (seconds), when at least one solution is found, with N = 20, M = 4

		deadline(k) 1.0 1.1 1.2 1.3	1.4	1.5	1.6	1.7	1.8	1.9	2.0	2.1	2.2
		RAFTM 14.9 61 74.9 138.2 202.1 256.9 327.3 219 1039.3 1054.7 126.8 58.7 123.1
	TL DVFS	RAM	0.07 0.04 0.067 0.054 0.041 0.061 0.066 0.045 0.043 0.036 0.053 0.052 0.044
		TDM	-	-	-9188.3 1550.4 1015.9 1165.4 2304.7 2814.6 1350.6 700.6 549.3 237.8
		RAFTM 228.6 662.2 529.9 1092 1815 4665 15722 4676 33294 70465 24239 24054 24072
	PL DVFS	RAM	84.3 99.2 44.4 74.3 76.5 65.5 52.4	55	56.3 41.7 42.8 57.4 56.3
		TDM	-	-	-	2740 5677.5 5084.1 9641.1 14770.4 10571.4 8235.2 5517.1 3619.0 3169.6
		RAFTM 0.53 0.3 5.76 14.14 21.69 98.22 91.88 183.39 1301.28 585.03 65.29 28.56 15.08
	SL DVFS	RAM	0.08 0.06 0.038 0.069 0.045 0.066 0.059 0.036 0.027 0.026 0.025 0.037 0.025
		TDM	-	-	-238.51 230.59 230.59 230.59 230.59 230.59 230.59 230.59 230.59 230.59

Table 7 :

 7 Running time (seconds), when at least one solution is found, with N = 20, M = 6

		deadline(k) 1.0 1.1	1.2	1.3	1.4	1.5	1.6	1.7	1.8 1.9 2.0 2.1 2.2
		RAFTM 0.8 58.1 26.9 89.9 81.9 109.8 58.6 62.8 59.8 14.7 2.5 0.7 0.6
	TL DVFS	RAM	0.07 0.06 0.08 0.09 0.10 0.06 0.05 0.05 0.07 0.05 0.06 0.08 0.05
		TDM	-	70.8 333.4 124.4 298.2 227.4 70.5 160.6 203.4 39.8 2.9 1.4 0.9
		RAFTM 114.2 697.3 730.8 661.5 859.5 824.0 1090.1 503.3 569.2 188.6 95.9 82.5 75.0
	PL DVFS	RAM 566.0 397.9 533.6 671.5 546.1 820.5 954.5 562.0 687.4 693.2 799.0 1113.8 700.0
		TDM	-2861.2 2874.1 5312.8 8795.7 1477.3 1237.6 1243.7 1794.6 232.5 41.7 42.2 35.2
		RAFTM 0.4 0.3	1.4 12.1 12.6 23.5 19.2 19.7 16.1 21.3 5.9 4.7 5.6
	SL DVFS	RAM	0.09 0.07 0.06 0.12 0.08 0.06 0.04 0.04 0.04 0.04 0.04 0.05 0.04
		TDM	-	8.7 111.0 37.8 71.9 83.0 52.3 52.6 41.9 32.8 19.5 20.2 16.3

Table 8 :

 8 Running time (seconds), when at least one solution is found, with N = 10, M = 4 (TL-DVFS) deadline(k) 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 1.05 1.1 1.[START_REF] Gou | Reliability-aware energy optimization for throughput-constrained applications on MPSoC[END_REF] 1.2 λ 0 = 4 × 10 -4 RAFTM 0.77 0.93 1.01 1.49 1.48 2.00 1.28 1.31 1.21 0.74 0.68 0.66 0.62 0.64 0.62 RAM 0.07 0.04 0.06 0.07 0.13 0.19 0.12 0.05 0.06 0.05 0.06 0.06 0.05 0.04 0.04 λ 0 = 5 × 10 -4 RAFTM 0.67 0.61 0.87 1.18 0.87 1.39 0.80 0.72 0.66 0.55 0.53 0.58 0.55 0.57 0.50 RAM 0.10 0.05 0.05 0.06 0.13 0.20 0.13 0.05 0.05 0.08 0.05 0.05 0.05 0.04 0.07

Table 9 :

 9 Running time (seconds), when at least one solution is found, with N = 20, M = 4 (TL-DVFS) × 10 -4 RAFTM 26.85 194.76 98.45 208.45 224.04 315.23 167.25 326.79 278.74 99.46 216.81 31.26 4.79 RAM 0.04 0.03 0.02 0.05 0.03 0.04 0.04 0.04 0.03 0.02 0.02 0.03 0.02 λ 0 = 5 × 10 -4 RAFTM 32.08 206.57 583.86 156.99 155.10 117.55 155.63 174.00 19.15 24.26 33.65 3.52 3.06 RAM 0.05 0.03 0.03 0.05 0.04 0.05 0.05 0.04 0.04 0.02 0.03 0.04 0.02

	deadline(k) 1.0 1.1	1.2	1.3	1.4	1.5	1.6	1.7	1.8 1.9 2.0 2.1 2.2
	λ 0 = 4

√ √ √ √ √

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


Member, IEEE Thomas Chevet

Andreas Rauh

Ngoc Thach

Julien Dinh

Tarek Marzat

Senior Member, IEEE Raïssi

Robust Interval Observer for Systems Described by the Fornasini-Marchesini Second Model

Keywords: Fornasini-Marchesini second model, Interval observer, Robust observer, Two-dimensional systems, Discrete-time systems

This letter proposes a novel robust interval observer for a two-dimensional (treated as a synonym for a double-indexed system) linear time-invariant discretetime system described by the Fornasini-Marchesini second model. This system is subject to unknown but bounded state disturbances and measurement noise. Built on recent interval estimation strategies designed for one-dimensional systems, the proposed observer is based on the introduction of weighting matrices which provide additional degrees of freedom in comparison with the classical structure relying on a change of coordinates. Linear matrix inequality conditions for the exponential stability and peak-to-peak performance of a two-dimensional system described by the Fornasini-Marchesini second model are then proposed, and applied to the design of a robust interval observer. Numerical simulation results are provided to show the efficiency of the proposed estimation strategy.

I. INTRODUCTION

S INCE their introduction in the second half of the nine- teen seventies, two-dimensional 1 (2D) systems have been widely studied [START_REF] Galkowski | Control systems analysis for the Fornasini-Marchesini 2D systems model -progress after four decades[END_REF]. Such systems are described by different state-space models such as the ones introduced by Roesser [START_REF] Roesser | A discrete state-space model for linear image processing[END_REF], Fornasini and Marchesini [START_REF] Fornasini | State-space realization theory for twodimensional filters[END_REF], [START_REF]Doubly-indexed dynamical systems: State-space models and structural properties[END_REF] or Kurek [START_REF] Kurek | The general state-space model for a two-dimensional linear digital system[END_REF]. 2D systems can be used to represent many physical processes [START_REF] Kaczorek | Two-Dimensional Linear Systems[END_REF] such as image processing [START_REF] Roesser | A discrete state-space model for linear image processing[END_REF], [START_REF] Du | H∞ Control and Filtering of Two-dimensional Systems[END_REF], repetitive industrial processes [START_REF] Rogers | Control Systems Theory and Applications for Linear Repetitive Processes[END_REF], spatio-temporal systems of which the behavior is governed by hyperbolic partial differential equations [START_REF] Marszalek | Two-dimensional state-space discrete models for hyperbolic partial differential equations[END_REF] or the task of iterative learning control synthesis [START_REF] Kurek | Iterative learning control synthesis based on 2-D system theory[END_REF]. Extensive studies of 2D system properties such as stability, controllability, observability, etc. have been conducted [START_REF] Galkowski | Control systems analysis for the Fornasini-Marchesini 2D systems model -progress after four decades[END_REF], [START_REF] Kaczorek | Two-Dimensional Linear Systems[END_REF]. Finally, several control [START_REF] Du | H∞ Control and Filtering of Two-dimensional Systems[END_REF], [START_REF] Rogers | Control Systems Theory and Applications for Linear Repetitive Processes[END_REF], [START_REF] Yang | Two-dimensional sliding mode control of discrete-time Fornasini-Marchesini systems[END_REF] and estimation [START_REF] Du | H∞ Control and Filtering of Two-dimensional Systems[END_REF], [START_REF] Zhao | Integrated state/disturbance observers for two-dimensional linear systems[END_REF]- [START_REF] Fu | On mixed 1 / -fault detection observer design for positive 2D Roesser systems: Necessary and sufficient conditions[END_REF] strategies have been investigated.

In the one-dimensional, i.e., single-indexed, case, set-based observers have been developed to compute sets guaranteed to T. Chevet and J. Marzat are with DTIS, ONERA, Universit é Paris-Saclay, 91123 Palaiseau, France (e-mail: {thomas.chevet, julien.marzat}@onera.fr)

A. Rauh is with Carl von Ossietzky Universit ät Oldenburg, Department of Computing Science, Group: Distributed Control in Interconnected Systems, 26111 Oldenburg, Germany (e-mail: andreas.rauh@unioldenburg.de) T.N. Dinh and T. Raïssi are with Conservatoire National des Arts et M étiers (CNAM), Cedric-Laetitia, 292 Rue St-Martin, 75141, Paris Cedex 03, France (e-mail: ngoc-thach.dinh@lecnam.net, tarek.raissi@cnam.fr) 1 Following the majority of the literature on the subject, the name "twodimensional system" is used here to refer to double-indexed systems. contain the state vector when a system is subject to bounded disturbances and measurement noise [START_REF] Gouzé | Interval observers for uncertain biological systems[END_REF]- [START_REF] Alamo | Guarateed state estimation by zonotopes[END_REF]. In this context, interval observers have been widely studied [START_REF] Mazenc | Interval observers for linear time-invariant systems with disturbances[END_REF]- [START_REF] Wang | Interval estimation based on the reduced-order observer and peak-to-peak analysis[END_REF]. They consist in the design of two sub-observers computing respectively an upper and a lower bound to the state vector. Often, the design of such observers is then based on combining a change of coordinates and gain tuning methods to ensure that the estimation error system is positive [START_REF] Kaczorek | Positive 1D and 2D Systems[END_REF] and stable. However, the change of coordinates heavily impacts the performance of interval observers [START_REF] Chambon | Overview of linear timeinvariant interval observer design: towards a non-smooth optimisationbased approach[END_REF]. To overcome this issue, the work [START_REF] Wang | Interval observer design for uncertain discrete-time linear systems[END_REF] introduces the TNL approach (named after the notation for the different matrices used) employing weighting matrices in addition to the traditional observer gain. With these additional degrees of freedom, it is easier to ensure that the error system becomes positive without requiring a change of coordinates.

To the authors' knowledge, interval observers for partial differential equations have been investigated [START_REF] Kharkovskaya | Design of interval observers and controls for PDEs using finite-element approximations[END_REF], [START_REF] Kharkovskaia | Interval observer design and control of uncertain non-homogeneous heat equations[END_REF], but no interval observers for 2D systems have been proposed. Therefore, this letter proposes to build a robust interval observer for a 2D discrete-time linear time-invariant (LTI) system described by the Fornasini-Marchesini second (FM-II) model (defined in Section II.B). The definition of such an observer, derived from [START_REF] Dinh | Optimal interval observers for discrete-time linear switched systems[END_REF] where the one-dimensional case is studied, is based on the exponential stability of the estimation error dynamics and the peak-to-peak performance of these estimation errors. In [START_REF] Ahn | Two-dimensional peak-topeak filtering for stochastic Fornasini-Marchesini systems[END_REF], a filter for stochastic FM-II systems that is asymptotically stable and peak-to-peak norm bounded is introduced. Therefore, the proposed interval observer can be based on the pointwise observer of [START_REF] Ahn | Two-dimensional peak-topeak filtering for stochastic Fornasini-Marchesini systems[END_REF]. However, it has been shown in [START_REF] Bachelier | Structural stability, asymptotic stability and exponential stability for linear multidimensional systems: the good, the bad and the ugly[END_REF] that for FM-II systems, exponential stability implies asymptotic stability while the converse is not true. It is therefore necessary to ensure that the conditions proposed in [START_REF] Ahn | Two-dimensional peak-topeak filtering for stochastic Fornasini-Marchesini systems[END_REF] also entail exponential stability. To do so, conditions for the exponential stability of a 2D nonlinear FM-II system, which requires the boundary conditions of the system to be bounded by an exponentially decreasing function, have been given in [START_REF] Pakshin | Stabilization of two-dimensional nonlinear systems described by Fornasini-Marchesini and Roesser models[END_REF]. In the meantime, [START_REF] Yeganefar | Lyapunov theory for 2D nonlinear Roesser models: application to asymptotic and exponential stability[END_REF] proposed a definition and a condition for exponential stability of a 2D system described by the Roesser model which can be adapted, as shown by [START_REF] Bachelier | Structural stability, asymptotic stability and exponential stability for linear multidimensional systems: the good, the bad and the ugly[END_REF], to 2D systems described by the FM-II model. This condition requires that the boundary conditions of the system have a finite infinity norm, thus relaxing the requirement of [START_REF] Pakshin | Stabilization of two-dimensional nonlinear systems described by Fornasini-Marchesini and Roesser models[END_REF].

Based on what precedes, the contribution of the present letter is twofold: (i) a Lyapunov function-based condition for the exponential stability and peak-to-peak performance of a 2D LTI discrete-time system described by the FM-II model with boundary conditions having finite infinity norm; (ii) the definition and construction of a novel robust interval observer for such a system.

The remainder of this letter is organized as follows. General prerequisites and assumptions on the considered model are presented in Section II. In Section III, the proposed structure and design procedure for the interval observer as well as the proposed stability and boundedness conditions are introduced. Section IV proposes numerical simulation results, which assess the efficiency of the proposed method. Finally, Section V gathers concluding remarks and perspectives.

II. PREREQUISITES AND PROBLEM FORMULATION A. Notations

The set of nonnegative integers, real numbers, and nonnegative real numbers are denoted by N, R, and R + , respectively. The matrices I n and 0 are respectively the identity matrix of size n ∈ N and the matrix of appropriate dimension filled with zeros. The matrices A and A † denote respectively the transpose and the Moore-Penrose pseudo-inverse of a matrix A ∈ R n×m . Any inequality involving vectors or matrices has to be understood elementwise. The positive or negative definiteness (resp. semi-definiteness) of a matrix A ∈ R n×n are denoted by A 0 and A ≺ 0 (resp. A 0 and A 0), respectively. If

x : N × N → R n is a 2D signal, its Euclidean norm is x(k, l) = x(k, l) x(k, l) and its L ∞ norm is the supremum over the two indices of its Euclidean norm, i.e., x ∞ = sup { x(k, l) |k, l ∈ N}. The set of all signals x : N × N → R n satisfying x ∞ < ∞ is denoted by L n ∞ .
Finally, is a placeholder denoting the transpose of a term placed symmetrically in a matrix.

B. Results on positive 2D systems

Any matrix A ∈ R n×m can be decomposed into two nonnegative matrices A + = max {0, A} ≥ 0 (where the maximum is understood elementwise) and

A -= A + -A ≥ 0. The matrix A is called nonnegative if A -= 0. Lemma 1 ([32]). Let x ∈ R m be a vector satisfying x ≤ x ≤ x, with x, x ∈ R m . Let A ∈ R n×m be a constant matrix. Then, A + x -A -x ≤ Ax ≤ A + x -A -x.
Now, consider a 2D LTI discrete-time system described by the FM-II model,

     x(k + 1, l + 1) = F 1 x(k, l + 1) + F 2 x(k + 1, l) + G 1 υ(k, l + 1) + G 2 υ(k + 1, l) y(k, l) = Hx(k, l) + Jυ(k, l), (1) where
x ∈ R n , υ ∈ R m , y ∈ R p , and F 1 , F 2 , G 1 , G 2 , H, J are constant matrices of appropriate dimensions. Definition 1 ([24]). The system (1) is called internally positive if, for all boundary conditions x(k, 0), x(0, l) ∈ R n + and sequences of inputs υ(k, l) ∈ R m + , with k, l ∈ N, x(k, l) ∈ R n + and y(k, l) ∈ R p + , ∀k, l ∈ N. Lemma 2 ([24]). The system (1) is internally positive if F 1 , F 2 ∈ R n×n + , H ∈ R p×n + , and x(k, 0), x(0, l) ∈ R n + , G 1 υ(k, l), G 2 υ(k, l) ∈ R n + , Jυ(k, l) ∈ R p + , ∀k, l ∈ N.

C. Problem formulation

Consider a 2D LTI discrete-time system described by the following FM-II model affected by disturbances and measurement noise

         x(k + 1, l + 1) = A 1 x(k, l + 1) + A 2 x(k + 1, l) + B 1 u(k, l + 1) + B 2 u(k + 1, l) + D 1 w(k, l + 1) + D 2 w(k + 1, l) y(k, l) = Cx(k, l) + Ev(k, l), (2)
where x ∈ R nx , y ∈ R ny , u ∈ R nu , w ∈ R nw , and v ∈ R nv are respectively the state, output, input, disturbance, and measurement noise vectors. The matrices

A 1 , A 2 , B 1 , B 2 , C, D 1 , D 2
, and E have appropriate dimensions. The system (2) admits for boundary conditions

x(k, 0) = ψ 1 (k), k ∈ N, x(0, l) = ψ 2 (l), l ∈ N. (3)
Assumption 1. The boundary conditions ψ 1 and ψ 2 , the disturbance w, and the measurement noise v are unknown but bounded and satisfy

ψ 1 (k) ≤ ψ 1 (k) ≤ ψ 1 (k), ψ 2 (l) ≤ ψ 2 (l) ≤ ψ 2 (l), w(k, l) ≤ w(k, l) ≤ w(k, l), and v(k, l) ≤ v(k, l) ≤ v(k, l), ∀k, l ∈ N, with ψ 1 , ψ 1 , ψ 2 , ψ 2 ∈ L nx ∞ , w, w ∈ L nw
∞ , and v, v ∈ L nv ∞ . This letter's purpose is to define a new interval observer based on the TNL approach of [START_REF] Wang | Interval observer design for uncertain discrete-time linear systems[END_REF]. This interval observer provides two signals x, x :

N × N → R nx satisfying x(k, l) ≤ x(k, l) ≤ x(k, l), ∀k, l ∈ N.
In addition, the proposed observer is designed so that the ratio of the norm of the estimation error to the norm of the disturbances and measurement noise is lower than a prescribed value γ > 0.

III. MAIN RESULTS

This section introduces the proposed framer enclosing the state of a 2D system described by the FM-II model subject to disturbances and measurement noise. To compute the observer's gains and to guarantee that the framer is a robust interval observer for the system (2), a linear matrix inequalitybased design strategy is provided.

A. Stability and robustness for 2D systems described by the Fornasini-Marchesini second model

In the one-dimensional case, the work [START_REF] Dinh | Optimal interval observers for discrete-time linear switched systems[END_REF] defines an interval observer as two signals x : N → R nx and x : N → R nx satisfying x ≤ x ≤ x at all time so that the upper and lower estimation errors e = x -x and e = x -x are input-tostate stable. These conditions can be adapted to the 2D case. (i) (x, x) is a framer for system (2), i.e., x(k, l) ≤ x(k, l) ≤ x(k, l), ∀k, l ∈ N; (ii) the upper and lower estimation errors e = x -x and e = x -x are exponentially stable for zero input, having the peak-to-peak norm bound γ > 0, under zero boundary conditions, i.e., e ∞ ≤ γ φ ∞ + φ ∞ and e ∞ ≤ γ φ ∞ + φ ∞ where φ is the total disturbance acting on (2), satisfying φ(k, l) ≤ φ(k, l) ≤ φ(k, l), ∀k, l ∈ N.

As stated in the introduction, in most works dealing with control or estimation for 2D systems described by the FM-II model [START_REF] Ahn | Two-dimensional peak-topeak filtering for stochastic Fornasini-Marchesini systems[END_REF], only asymptotic stability requirements are made. However, as shown in [START_REF] Bachelier | Structural stability, asymptotic stability and exponential stability for linear multidimensional systems: the good, the bad and the ugly[END_REF], for the FM-II model with boundary conditions given as in (3), exponential stability implies asymptotic stability while the converse is not true. In addition, ensuring exponential stability gives some control over the convergence speed of the interval observer. Therefore, it is necessary to obtain conditions guaranteeing exponential stability of a 2D system described by the FM-II model to propose an interval observer for such a system.

A condition for exponential stability of systems described by the Roesser model is proposed in [START_REF] Yeganefar | Lyapunov theory for 2D nonlinear Roesser models: application to asymptotic and exponential stability[END_REF]. Then, [START_REF] Bachelier | Structural stability, asymptotic stability and exponential stability for linear multidimensional systems: the good, the bad and the ugly[END_REF] shows that the definition of exponential stability given in [START_REF] Yeganefar | Lyapunov theory for 2D nonlinear Roesser models: application to asymptotic and exponential stability[END_REF] can be adapted to systems described by the FM-II model. Therefore, based on the asymptotically stable peak-to-peak norm bounded filter introduced in [START_REF] Ahn | Two-dimensional peak-topeak filtering for stochastic Fornasini-Marchesini systems[END_REF], the following theorem gives conditions for exponential stability and peak-to-peak performance of 2D systems described by the FM-II model. Theorem 1. If there exist scalars α ∈ (0, 1), γ ≥ 0, and µ ≥ 0, with γ -µ ≥ 0, and two matrices P ∈ R n×n and Q ∈ R n×n , with P = P 0, Q = Q 0, and P -Q 0, such that

V 0 (k + 1, l + 1) ≤ (1 -α)(V 1 (k, l + 1) + V 2 (k + 1, l)) + 1 2 µ υ(k, l + 1) 2 + υ(k + 1, l) 2 , ( 4
)
where

V 0 (k, l) = x(k, l) P x(k, l), V 1 (k, l) = x(k, l) (P - Q)x(k, l
), and V 2 (k, l) = x(k, l) Qx(k, l), then system (1) with boundary conditions (3) is exponentially stable for zero input, i.e., for υ ≡ 0. In addition to condition (4), if

1 2 x(k, l + 1) 2 + 1 2 x(k + 1, l) 2 ≤ γ α 2 V 1 (k, l + 1) + V 2 (k + 1, l) + 1 2 (γ -µ) υ(k, l + 1) 2 + υ(k + 1, l) 2 , (5)
system (1) satisfies x ∞ ≤ γ υ ∞ under zero boundary conditions. Proof. Since V 0 (k, l) = V 1 (k, l) + V 2 (k, l), inequality (4)
can be rewritten, when υ ≡ 0, as

V 1 (k + 1, l + 1) ≤ (1 -α)V 1 (k, l + 1) + (1 -α)V 2 (k + 1, l) -V 2 (k + 1, l + 1), (6)
which implies, as in [START_REF] Yeganefar | Lyapunov theory for 2D nonlinear Roesser models: application to asymptotic and exponential stability[END_REF], by recursively bounding V 1 (i, l +1), with 0 < i ≤ k, on the right hand side of ( 6)

V 1 (k + 1, l + 1) ≤ (1 -α) k+1 V 1 (0, l + 1) + (1 -α)W 2 (k, l) -W 2 (k, l + 1), (7)
where

W 2 (k, l) = k i=0 (1 -α) k-i V 2 (i + 1, l).
The function W 2 (k, j), with 0 < j ≤ l, can also be recursively bounded in the same way as V 1 so that

W 1 (k + 1, l) + W 2 (k, l + 1) ≤ (1 -α) k+1 W 1 (0, l) + (1 -α) l+1 W 2 (k, 0), where W 1 (k, l) = l j=0 (1 -α) l-j V 1 (k, j + 1). The term W 1 (k + 1, l) + W 2 (k, l + 1
) is a finite sum of nonnegative terms, implying that it is greater than or equal to V 1 (k + 1, l + 1) + V 2 (k + 1, l + 1) = V 0 (k + 1, l + 1). Therefore, factoring on the right hand side by (1 -α) 2 and (1 -α) k+l+1 , x(k + 1, l + 1) P x(k + 1, l + 1)

≤ (1 -α) k+l+3 k i=0 V 2 (i + 1, 0) (1 -α) i+2 + l j=0 V 1 (0, j + 1) (1 -α) j+2 .
Let β be the largest eigenvalue of diag(P -Q, Q) and δ be the smallest eigenvalue of P . Remembering that 0 < 1 -α < 1, the above inequality then implies

x(k + 1, l + 1) 2 ≤ β δ (1 -α) k+l k+1 i=1 ψ 1 (i) 2 (1 -α) i+1 + l+1 j=1 ψ 2 (j) 2 (1 -α) j+1 ≤ β δ (1 -α) k+l k+1 i=1 ψ 1 (i) √ 1 -α i+1 + l+1 j=1 ψ 2 (j) √ 1 -α j+1 2 so that x(k, l) ≤ M q k+l k i=1 ψ 1 (i) q i+1 + l j=1 ψ 2 (j) q j+1
, where M = β/δ and q = √ 1 -α, which is the definition of exponential stability for a 2D FM-II system [START_REF] Bachelier | Structural stability, asymptotic stability and exponential stability for linear multidimensional systems: the good, the bad and the ugly[END_REF].

Applying the previous recursive bounding procedure with non-zero input and remembering that υ(k, l + 1)

2 + υ(k + 1, l) 2 ≤ 2 υ 2 ∞ , W 1 (k + 1, l) + W 2 (k, l + 1) ≤ (1 -α) k+1 W 1 (0, l) + (1 -α) l+1 W 2 (k, 0) + µ k i=0 l j=0 (1 -α) k-i (1 -α) l-j υ 2 ∞ , or, since 0 < 1 -α < 1, V 1 (k + 1, l + 1) + V 2 (k + 1, l + 1) ≤ µ α 2 υ 2 ∞ + (1 -α) k+1 W 1 (0, l) + (1 -α) l+1 W 2 (k, 0). ( 8
)
Using [START_REF] Rogers | Control Systems Theory and Applications for Linear Repetitive Processes[END_REF] to bound the right hand side of (5),

x(k + 1, l + 1) 2 ≤ γµ υ 2 ∞ + γ(γ -µ) υ 2 ∞ + γα 2 ((1 -α) k+1 W 1 (0, l) + (1 -α) l+1 W 2 (k, 0)). ( 9
)
With zero boundary conditions, inequality ( 9) is equivalent to

x(k, l) ≤ γ υ ∞ .
Remark 1. With non-zero boundary condition, the state vector's norm is bounded over time by γ υ ∞ plus a vanishing term depending on the boundary conditions. Therefore, the set {x ∈ R n | x ≤ γ υ ∞ } is an attractor for system (1).

B. Robust interval observer design

Inspired by the work of [START_REF] Wang | Interval observer design for uncertain discrete-time linear systems[END_REF], the proposed structure for the framer of system ( 2) is

                                       x(k + 1, l + 1) = (T A 1 -L 1 C)x(k, l + 1) + (T A 2 -L 2 C)x(k + 1, l) + T B 1 u(k, l + 1) + T B 2 u(k + 1, l) + L 1 y(k, l + 1) + L 2 y(k + 1, l) + N y(k + 1, l + 1) + φ(k, l) x(k + 1, l + 1) = (T A 1 -L 1 C)x(k, l + 1) + (T A 2 -L 2 C)x(k + 1, l) + T B 1 u(k, l + 1) + T B 2 u(k + 1, l) + L 1 y(k, l + 1) + L 2 y(k + 1, l) + N y(k + 1, l + 1) + φ(k, l), (10)
where φ(k, l) and φ(k, l) are

                                       φ(k, l) = (T D 1 ) + w(k, l + 1) -(T D 1 ) -w(k, l + 1) + (T D 2 ) + w(k + 1, l) -(T D 2 ) -w(k + 1, l) -(L 1 E) + v(k, l + 1) + (L 1 E) -v(k, l + 1) -(L 2 E) + v(k + 1, l) + (L 2 E) -v(k + 1, l) -(N E) + v(k + 1, l + 1) + (N E) -v(k + 1, l + 1) φ(k, l) = (T D 1 ) + w(k, l + 1) -(T D 1 ) -w(k, l + 1) + (T D 2 ) + w(k + 1, l) -(T D 2 ) -w(k + 1, l) -(L 1 E) + v(k, l + 1) + (L 1 E) -v(k, l + 1) -(L 2 E) + v(k + 1, l) + (L 2 E) -v(k + 1, l) -(N E) + v(k + 1, l + 1) + (N E) -v(k + 1, l + 1), (11)
T ∈ R nx×nx , N ∈ R nx×ny , L 1 ∈ R nx×ny
Theorem 2. Let Assumption 1 hold. If there exist

T ∈ R nx×nx and L 1 , L 2 ∈ R nx×ny such that T A 1 -L 1 C and T A 2 -L 2 C are nonnegative matrices, then x(k, l) ≤ x(k, l) ≤ x(k, l), ∀k, l ∈ N. (13)
Proof. Let e(k, l) = x(k, l) -x(k, l) and e(k, l) = x(k, l)x(k, l) be the upper and lower estimation errors. Let also

φ(k, l) = T D 1 w(k, l + 1) + T D 2 w(k + 1, l) -L 1 Ev(k, l+1)-L 2 Ev(k+1, l)-N Ev(k+1, l+1)
be the total disturbance. Then,

e(k + 1, l + 1) = (T A 1 -L 1 C)e(k, l + 1) + (T A 2 -L 2 C)e(k + 1, l) + φ(k, l) -φ(k, l)
and, by Lemma 1, φ(k, l) ≥ φ(k, l). Therefore, by Lemma 2,

e(k, l) ≥ 0, ∀k, l ∈ N, if T A 1 -L 1 C and T A 2 -L 2 C are nonnegative matrices. With the same reasoning, e(k, l) ≥ 0, ∀k, l ∈ N, if T A 1 -L 1 C and T A 2 -L 2 C are nonnegative matrices.
As noted in [START_REF] Wang | Interval observer design for uncertain discrete-time linear systems[END_REF], the matrices T and N provide additional degrees of freedom in the interval observer's tuning. Indeed, it might be difficult to obtain matrices L i , with i ∈ {1, 2}, such that the matrices A i -L i C are both nonnegative and stable [START_REF] Raïssi | Interval state estimation for a class of nonlinear systems[END_REF]. The matrix T relaxes this difficulty while allowing, in conjuction with the matrix N , a better performance tuning.

Then, from the results of Theorem 1 and Theorem 2, it is possible to derive linear matrix inequality conditions to ensure that ( 10) is an interval observer according to Definition 2. First, the following lemma recalls the structure of the matrices T and N .

Lemma 3 ([33]

). Given three matrices X ∈ R n×m , Y ∈ R m×p , and Z ∈ R n×p , with rank Y = p, the general solution X of the equation XY = Z is

X = ZY † + Ξ I m -Y Y †
where Ξ ∈ R n×m is an arbitrary matrix.

With Lemma 3, T and N satisfying ( 12) are

T = Θ † λ 1 + ΞΥλ 1 , N = Θ † λ 2 + ΞΥλ 2 , (14)
where Ξ ∈ R nx×(nx+ny) is an arbitrary matrix, Θ =

I nx C , Υ = I nx+ny -ΘΘ † , λ 1 = I nx 0 , λ 2 = 0 I ny .
Theorem 3. Let Assumption 1 hold. If there exist scalars α ∈ (0, 1), γ ≥ 0, and µ ≥ 0 and matrices nx+ny) , with P, Q, P -Q 0, such that

P ∈ R nx×nx diagonal, Q ∈ R nx×nx diagonal, X 1 ∈ R nx×ny , X 2 ∈ R nx×ny , and Y ∈ R nx×(
S ≥ 0, (15) 
 (α -1)∆ 0 -µI n φ /2 S Φ -P   0, (16)
  α 2 ∆ 0 (γ -µ)I n φ /2 I 2nx 0 2γI 2nx   0, (17)
where

S = S 1 S 2 , S 1 = Πλ 1 A 1 -X 1 C, S 2 = Πλ 1 A 2 - X 2 C, with Π = P Θ † + Y Υ, ∆ = diag(P -Q, Q), n φ = 2n w + 3n v + n x , and
Φ = Πλ 1 D 1 Πλ 1 D 2 -X 1 E -X 2 E -Πλ 2 E -P , then (10
) is a robust interval observer for system (1) with L 1 = P -1 X 1 , L 2 = P -1 X 2 , and Ξ = P -1 Y .

Proof. Since P 0 and is diagonal, all its diagonal elements are strictly positive. Defining X 1 = P L 1 , X 2 = P L 2 , and Y = P Ξ, condition ( 15) is equivalent to the positivity of

T A 1 -L 1 C and T A 2 -L 2 C.
Moreover, applying the Schur complement to ( 16) and ( 17), pre-multiplying by z(k, l) and post-multiplying by z(k, l), where z(k, l) = e(k, l + 1) e(k + 1, l) w(k, l + 1)

w(k + 1, l) v(k, l + 1) v(k + 1, l) v(k + 1, l + 1) φ(k, l) ,
yields conditions (4) and ( 5) for the upper estimation error, where the terms x and G 1 υ(k, l +1)+G 2 υ(k +1, l) appearing in [START_REF] Galkowski | Control systems analysis for the Fornasini-Marchesini 2D systems model -progress after four decades[END_REF] are replaced by e and φ(k, l) -φ(k, l), respectively. Then, applying the Schur complement to ( 16) and ( 17), premultiplying by z(k, l) and post-multiplying by z(k, l), where z(k, l) = e(k, l + 1) e(k + 1, l) w(k, l + 1)

w(k + 1, l) v(k, l + 1) v(k + 1, l) v(k + 1, l + 1) φ(k, l) ,
yields conditions (4) and ( 5) for the lower estimation error, where the terms x and G 1 υ(k, l +1)+G 2 υ(k +1, l) appearing in [START_REF] Galkowski | Control systems analysis for the Fornasini-Marchesini 2D systems model -progress after four decades[END_REF] are replaced by e and φ(k, l) -φ(k, l), respectively.

Therefore, with conditions ( 15)-( 17), the upper and lower estimation errors satisfy the conditions of Definition 2.

IV. NUMERICAL SIMULATION

Consider a numerical example of system (2) adapted from [START_REF] Singh | Stability analysis of 2-D linear discrete systems based on the Fornasini-Marchesini second model: Stability with asymmetric Lyapunov matrix[END_REF], with

A 1 = 1 -2.5 0.1 0 , A 2 = 0 0.1 0 0.1 , B 1 = 0.6 0.3 , D 1 = 0.1 -0.4 0.8 -0.2 , D 2 = 0.2 0.6 -0.1 -0.5 , B 2 = 1.2 0 , C = -0.5 0.2 , E = 0.8,
with the boundary conditions

ψ 1 (k) = cos(k) sin(0.3k) sin(0.5k) , ψ 2 (l) = cos(0.5l) sin(l) cos(0.3l) .
For simulation, the input signal is u(k, l) = 0.5 sin(0.01k) cos(0.01l).

Moreover, the disturbance is a uniformly distributed random vector satisfying w ≤ w(k, l) ≤ w, with w = -w = 0.05 • 1 1 . Finally, the measurement noise is a uniformly distributed random scalar satisfying

v ≤ v(k, l) ≤ v, with v = -v = 0.1.
The observer is initialized with

ψ 1 = ψ 2 = -ψ 1 = -ψ 2 = 3 • 1 1 .
In addition, α = 0.9 is chosen. To obtain γ, T, N, L 1 , and L 2 , an optimization problem minimizing γ under the constraints ( 15)-( 17) is solved using CVX [START_REF] Grant | CVX: Matlab software for disciplined convex programming, version 2.1[END_REF], yielding γ = µ = 3.1689 and T = 0.0076 0.3970 0.0189 0.9924

, N = -1.9849 0.0378 , L 1 = -0.0945 -0.2363 , L 2 = 0.0272 0.0604 .
For readability, Fig. 1 and 2 only present the evolution of the state variables for selected values of l and k, respectively. These figures show the efficiency of the proposed interval observer. Indeed, the interval defined by x and x tightens in a small number of steps, whether it be along the direction k or the direction l. In addition, the state remains contained between the bounds x and x.

This can also be seen in Fig. 3, showing the surface plots of e 1 and e 1 , respectively. Both the lower estimation error e 1 (k, l) and the upper estimation error e 1 (k, l) remain positive for all values of k and l, which is the desired behavior. In addition, in less than five steps along both directions, the estimation errors converge to bounded values.

V. CONCLUSIONS AND FUTURE WORK

This letter proposes a novel interval observer for twodimensional systems described by the Fornasini-Marchesini second model. Building on existing interval observers for onedimensional systems, the observer includes weighting matri-ces, in addition to the gains, in its design. These additional degrees of freedom are tuned along with the gain matrices to enforce the positivity and stability of the estimation errors and to attenuate the effect of the disturbances by considering a peak-to-peak norm criterion. The design parameters of the interval observer are then obtained by solving an optimization problem under linear matrix inequality constraints. The efficiency of the proposed estimation method is assessed by numerical simulation results. In future work, this interval observer can be adapted to other types of two-dimensional systems, such as the ones described by the Roesser model or the Fornasini-Marchesini first model. In addition, the proposed observer can be employed to evaluate the robustness of given control strategies against parameter uncertainties. Finally, interval-based (and more generally set-based) fault detection strategies for two-dimensional systems based on such an interval observer will be studied.

Definition 2 .

 2 Let x : N × N → R nx and x : N × N → R nx be two 2D signals. The pair (x, x) is a robust interval observer for system (2) with boundary conditions (3) if:

  , and L 2 ∈ R nx×ny are design parameters of the framer, with T and N satisfying T + N C = I nx .

1 State 𝑥 1 ( 1 State 𝑥 1 (Fig. 1 . 2 State 2 StateFig. 2 .

 11111222 Fig. 1. First state variable and guaranteed bounds along the direction k for the two values l = 1 and l = 250.

Fig. 3 .

 3 Fig. 3. Lower (a) and upper (b) estimation errors for the first state variable.