Minyu Cui

Lei Mo

Angeliki Kritikakou

Emmanuel Casseau

Energy-aware Partial-Duplication Task Mapping under Real-Time and Reliability Constraints

Keywords: Reliability, Task mapping, DVFS, multicores, Real-time

An efficient task execution on multicore platforms can lead to low energy consumption. To achieve that, an Integer Non-Linear Programming (INLP) formulation is proposed that performs task mapping by jointly addressing task allocation, task frequency assignment, and task duplication. The goal is to minimize energy consumption under real-time and reliability constraints. To provide an optimal solution, the original INLP problem is safely transformed to an equivalent Mixed Integer Linear Programming (MILP) problem. The comparison of the proposed approach with existing energy-aware task mapping approaches shows that the proposed approach is able to find solutions when other approaches fail, achieving an overall lower energy consumption.

Introduction

The execution of embedded applications on multicore platforms requires both intime and reliable execution of tasks. In time-critical domains, tasks must finish before a given deadline. Meanwhile, their correct execution can be threatened by several sources, such as radiation [START_REF] Baumann | Radiation-induced soft errors in advanced semiconductor technologies[END_REF] and electromagnetic interference [START_REF] Sudo | Electromagnetic Interference (EMI) of System-on-Package (SOP)[END_REF], causing non-persistent transient faults (also called soft errors). Due to the technology size reduction and the increasing scaling of CMOS technology, the system has become more susceptible to soft errors [START_REF] Mbrahimi | Comprehensive Analysis of Alpha and Neutron Particle-induced Soft errors in an embedded Processor at Nanoscales[END_REF]. To provide protection, the system reliability should be increased. To achieve that, tasks are executed with higher frequencies [START_REF] Zhu | The Effects of Energy Management on Reliability in Real-Time Embedded Systems[END_REF]. Another way is to apply fault-tolerance techniques at the system level, where tasks are replicated [START_REF] Zhao | On Maximizing Reliability of Real-Time Embedded Applications Under Hard Energy Constraint[END_REF][START_REF] Ma | An On-Line Framework for Improving Reliability of real-Time Systems on 'Big-little' Type MPSoC[END_REF]. Nonetheless, these approaches increase the system energy consumption, which has become an important concern, especially for systems with limited energy budget, such as battery-powered or energyharvesting devices [START_REF] Zhao | On Maximizing Reliability of Real-Time Embedded Applications Under Hard Energy Constraint[END_REF][START_REF] Zhou | Resource Management for Improving Soft-Error and Lifetime Reliability of Real-Time MPSoCs[END_REF][START_REF] Ma | An On-Line Framework for Improving Reliability of real-Time Systems on 'Big-little' Type MPSoC[END_REF], and green computing. To balance system performance and energy consumption, multicore platforms have been enhanced with Dynamic Voltage and Frequency Scaling (DVFS). However, by decreasing frequency and voltage, systems become more susceptible to soft errors [START_REF] Mcpherson | Reliability challenges for 45nm and beyond[END_REF]. Therefore, adequate mapping approaches are required in order to obtain a reliable, in-time and energy efficient task execution on multicore platforms.

Table 1 depicts representative task mapping approaches, which decide the frequency assignment and the processor allocation to tasks, under Energy Budget (EB), Real-Time (RT) and Reliability (R) constraints. The goal is to maximize system reliability (max R), usually under an energy supply constraint [START_REF] Zhao | On Maximizing Reliability of Real-Time Embedded Applications Under Hard Energy Constraint[END_REF][START_REF] Zhou | Resource Management for Improving Soft-Error and Lifetime Reliability of Real-Time MPSoCs[END_REF] [4], or to minimize energy consumption (min E), usually under a real-time [START_REF] Haque | On Reliability Management of Energy-Aware Real-Time Systems Through Task Replication[END_REF][START_REF] Huang | Energyefficient Fault-tolerant Mapping and Scheduling on Heterogeneous Multiprocessors Real-Time Systems[END_REF][START_REF] Gou | Reliability-aware energy optimization for throughput-constrained applications on MPSoC[END_REF] or reliability constraint [START_REF] Haque | On Reliability Management of Energy-Aware Real-Time Systems Through Task Replication[END_REF][START_REF] Xie | Resource Consumption Cost Minimization of Reliable Parallel Applications on Heterogeneous Embedded Systems[END_REF][START_REF] Xie | Energy-Efficient Fault-Tolerant Scheduling of Reliable Parallel Applications on Heterogeneous Distributed Embedded Systems[END_REF]. Existing approaches execute only original tasks or, additionally, replicas of original tasks. A task is executed successfully, if at least one replica is executed without faults [START_REF] Haque | On Reliability Management of Energy-Aware Real-Time Systems Through Task Replication[END_REF]. By executing several replicas on different processors, the probability of correct execution is increased, as it is unlikely that execution of all replicas fails [START_REF] Haque | On Reliability Management of Energy-Aware Real-Time 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][START_REF] Wang | A Reliability-aware Task Scheduling Algorithm Based on Heterogeneous Computing Systems[END_REF]. Task replication can be either full (all tasks are replicated) or partial (selected tasks are replicated). Task mapping approaches, that maximize reliability, consider i) only original tasks, through online heuristics [START_REF] Ma | An On-Line Framework for Improving Reliability of real-Time Systems on 'Big-little' Type MPSoC[END_REF] and static and dynamic algorithms [START_REF] Zhao | On Maximizing Reliability of Real-Time Embedded Applications Under Hard Energy Constraint[END_REF], and ii) original and replicated tasks, when the number of replicas is known [START_REF] Zhou | Resource Management for Improving Soft-Error and Lifetime Reliability of Real-Time MPSoCs[END_REF] and when the number of task replicas is also decided during the mapping process [START_REF] Wang | A Reliability-aware Task Scheduling Algorithm Based on Heterogeneous Computing Systems[END_REF].

One category of the approaches, that minimize energy consumption, considers only original tasks, e.g., a decomposition algorithm is proposed under reliability constraints [START_REF] Xie | Resource Consumption Cost Minimization of Reliable Parallel Applications on Heterogeneous Embedded Systems[END_REF]. Mapping of original tasks on heterogeneous multicores is extended in order to provide a solution, where enough slack exist to re-execute a task in case of a single fault [START_REF] Huang | Energyefficient Fault-tolerant Mapping and Scheduling on Heterogeneous Multiprocessors Real-Time Systems[END_REF]. However, these approaches usually require high frequencies to satisfy the reliability constraints, increasing energy consumption. On top, even with the highest platform frequency, it may be impossible to satisfy the reliability constraints, leading to empty solution space. Another category considers both original and replicated tasks. Full replication approaches decide the number of replicas (at least one replica per task), e.g., for homogeneous [START_REF] Haque | On Reliability Management of Energy-Aware Real-Time Systems Through Task Replication[END_REF] and heterogeneous [START_REF] Xie | Energy-Efficient Fault-Tolerant Scheduling of Reliable Parallel Applications on Heterogeneous Distributed Embedded Systems[END_REF] platforms. However, full replication leads to large energy consumption, combined with a negative impact on execution time; the end-times of tasks are delayed, due to the execution of task replicas. This impact may lead to empty solution space, when the real-time constraints are strict. Few approaches apply partial task replication. Usually heuristics are applied to select the tasks to be replicated, e.g., a heuristic that decides the tasks to be duplicated and their frequency [START_REF] Gou | Reliability-aware energy optimization for throughput-constrained applications on MPSoC[END_REF], without considering reliability constraints. Our work belongs to this category and extends the State-of-the-Art (SoA) by optimally solving a combined task mapping problem, under both real-time and reliability constraints.

The goal of the proposed task mapping approach is to minimize system energy consumption by optimally and concurrently deciding the tasks to be duplicated, the frequency assignment per task and task allocation, on a homogeneous multicore platform with DVFS, under both real-time and reliability constraints. The proposed approach considers the execution of a task to be safe, when it meets its reliability constraint. Otherwise the task is duplicated. As task duplication is applied only when the reliability constraint cannot be met, the number of duplicated tasks is reduced, reducing the negative impact on time and energy consumption. Our contribution is two-fold: i) the aforementioned task mapping problem is formulated as an Integer Non-Linear Programming (INLP), and ii) the INLP problem is safely transformed into a Mixed Integer Linear Programming (MILP) problem in order to be solved optimally. To support our contribution, we perform extensive experiments considering i) strict, medium and relaxed real-time constraints, and ii) strict and relaxed reliability constraints. From the obtained results, our approach is able to find more feasible solutions (on average, 31.77%) compared to approaches that always satisfy the reliability constraints without task replication, and consumes less energy (on average, 26.07%) compared to full duplication approaches. Especially for strict real-time constraints, our approach can achieve energy savings up to 51.56%.

The rest of the paper is organized as follows. Section 2 introduces the system model. Section 3 presents the proposed formulation of the duplication-based fault-tolerant mapping approach. Section 4 presents the evaluation results. Finally, Section 5 concludes this study.

System Model

Task Model: We consider a set of N independent tasks, i.e., {τ 1 , . . . , τ N }. For each task τ i , C i is the Worst Case Execution Cycles (WCEC). All tasks must be executed before a common deadline D, and no preemption occurs between different tasks executed on the same processor. Without loss of generality, in the rest of the paper, we assume that the release times of all tasks are at the start of the scheduling period. Platform and Power Model: A multicore platform is considered with M homogeneous processors, i.e., {θ 1 , . . . , θ M }. The multicore platform supports individual DVFS in task level and there are L different voltage/frequency (V/F) pairs {(v 1 , f 1 ), . . . , (v L , f L )}. When task τ i is assigned with frequency f l , its execution time is given by t i = Ci f l . For each processor θ m , the power consumption is modeled as the sum of static P sta l power and dynamic P dyn l power with frequency f l [START_REF] Chen | Energy Optimization for Real-Time Multiprocessor System-on-Chip with Optimal DVFS and DPM Combination[END_REF], i.e., P l = P sta l + P dyn l . The dynamic power consumption with voltage/frequency level (v l , f l ) is given by P dyn l = C ef f v 2 l f l , where C ef f is the effective switching capacitance. Fault Model and Reliability: We focus on soft errors that follow a Poisson Distribution with an average fault rate λ(f ) at frequency f , which can be modeled as λ(f ) = λ 0 ×10 d fmax-f fmax-f min , where λ 0 is the average fault rate corresponding to the maximum frequency f max , d 0 is a positive constant, indicating the sensitivity of failure rate related to frequency scaling [START_REF] Zhu | The Effects of Energy Management on Reliability in Real-Time Embedded Systems[END_REF]. The reliability of a task τ i , i.e., the probability of executing the task without any fault, follows the exponential model [START_REF] Zhu | The Effects of Energy Management on Reliability in Real-Time Embedded Systems[END_REF]. Hence, the task's reliability at frequency f l is r i (f l ) = e -ϕi(f l ) , where ϕ i (f l ) = λ(f l ) × t i , with t i 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] Zhu | The Effects of Energy Management on Reliability in Real-Time Embedded Systems[END_REF][START_REF] Huang | Energyefficient Fault-tolerant Mapping and Scheduling on Heterogeneous Multiprocessors Real-Time Systems[END_REF]. If the reliability of task τ i is larger than its reliability constraint, the execution is considered as reliable and the task reliability is not modified, R i = r i (f l ). Otherwise, the task τ i is duplicated and executed on different processors. The duplicated task is executed with same frequency as the original task, similar to [START_REF] Haque | On Reliability Management of Energy-Aware Real-Time Systems Through Task Replication[END_REF][START_REF] Gou | Reliability-aware energy optimization for throughput-constrained applications on MPSoC[END_REF][START_REF] Haque | Energy-Aware Task Replication to manage reliability for periodic real-time applications on multicore platforms[END_REF], since using the same frequency in original and duplicated tasks yields similar energy consumption [START_REF] Haque | Energy-Aware Task Replication to manage reliability for periodic real-time applications on multicore platforms[END_REF]. When the task is duplicated, its reliability is given by

R i = 1 -(1 -r i (f l )) 2 .
As our approach is applied offline, 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 platform workload, in case no faults occur. An mechanism can be applied, during execution, to further improve the energy consumption of our solution (by not executing the replica, when the first execution is correct), such as [START_REF] Zheng | On the Design of Fault-Tolerant Scheduling Strategies Using Primary-Backup Approach for Computational Grids with Low Replication Costs[END_REF], and to deal with the low probability cases, where non-replicated tasks and both original and duplicated tasks are faulty, such as [START_REF] Dubrova | Fault Tolerant Design[END_REF].

3 Duplication-based Fault-Tolerant Mapping Approach (DFTMA)

Motivational example: Before providing the mathematical formulation of the proposed Duplication-based Fault-Tolerant Mapping Approach (DFTMA), we provide a simple example to motivate our approach. Let us assume a single task with C=4 * 10 8 , a reliability threshold equal to 0.999 and the voltage/frequency levels of the platform from Table 4 in section 4. Table 2 depicts the execution time (t), energy consumption (E = P l × t) and reliability R, when only the original task is executed (columns f 1 -f 6 ) and when both original and its replica are executed (columns 2f 1 -2f 6 ). Table 2.a) enumerates all feasible solutions under only the reliability constraint for the approaches that i) apply full task

DFTMA -A1 A1,A2 A1,A2 A1,A2 A1,A2,A3 A1,A2,A3,A4 A1-A4,A5 A1-A5,A6 FTM -B1 B1, B2 B1, B2 B1, B2 B1, B2 B1, B2 B1, B2 B1, B2 FDM -- - C1 C1, C2 C1, C2, C3 C1-C3, C4 C1-C4, C5 C1-C5, C6
duplication (FDM), such as [START_REF] Xie | Resource Consumption Cost Minimization of Reliable Parallel Applications on Heterogeneous Embedded Systems[END_REF], ii) must always satisfy the reliability constraint without duplication (FTM), such as [START_REF] Haque | On Reliability Management of Energy-Aware Real-Time 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], and iii) apply task duplication only when the reliability constraint cannot be satisfied (DFTMA), such as the proposed method. Table 2.b) explores how the deadline constraint (D) affects the feasible and optimal (highlighted in bold) solutions. Compared to DFTMA approach, existing approaches cannot find optimal solutions, due to strict reliability constraint (as FTM) or deadline constraint (as FDM), even for only a single task.

Mathematical formulation:

The goal is to minimize the total energy consumption of the system, subject to a set of reliability and real-time constraints.

To achieve that we decide the: 1) frequency of original tasks (s); 2) duplication of original tasks (σ); 3) allocation of original tasks (q) and duplicated tasks (d).

Table 3 summarizes the parameters and the variables of our formulation.

i) Frequency Assignment: Let N = {1, . . . , N }, M = {1, . . . , M } and L = {1, . . . , L}. Since the platform provides individual DVFS, that can be applied per task, each task can only be assigned with one frequency level:

l∈L s il = 1, ∀i ∈ N . (1)
ii) Task Duplication Decision: The reliability of task τ i is expressed as r i = l∈L s il e -ϕi(f l ) , where ϕ i (f l ) = λ(f l ) × t i and t i = l∈L s il Ci f l (the execution time of task τ i when executed with frequency f l ). Let R th i denote the reliability threshold of task τ i . If 0 < r i ≤ R th i , the task needs to be duplicated, σ i = 1, else (i.e., r i > R th i ), only the original task is executed, thus, σ i = 0. In order to describe this behaviour, the following Lemma is introduced. 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 δ -

(1 + δ)c ≤ x -y ≤ 1 -c, where δ is positive small value. Proof. 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 C 1 and C 2 at the same time, then 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.

Parameters M number of processors N number of tasks L number of discrete V/F levels Ci WCEC of task τi D global deadline (v l , f l ) the l th V/
Hence, c must be 0 if x > y.

Since there are L pairs of voltage/frequency, for the values of r i , then r i ∈ {e -ϕi(f1) , . . . , e -ϕi(f L ) }. According to Lemma 1, the relationship between R i (f l ), R th i and σ i is linearized as follows:

δ -(1 + δ)σ i ≤ l∈L s il e -ϕi(f l ) -R th i ≤ 1 -σ i , ∀i ∈ N . (2)
iii) Original task allocation: The original task τ i is executed on one processor:

m∈M q im = 1, ∀i ∈ N . (3)
iv) Duplicated task allocation: If a task τ i is duplicated, the original and duplicated tasks should be allocated on different processors. The duplicated task is allocated only on one processor:

m∈M d im = σ i , ∀i ∈ N , (4a)
q im + d im ≤ 1, ∀i ∈ N , ∀m ∈ M . (4b)
v) Real-time Constraints: All (original and duplicated) tasks assigned on processor θ m should be executed within a common deadline D:

i∈N q im t i + i∈N d im t i ≤ D, ∀m ∈ M , (5)
where t i = l∈L s il Ci f l is the execution time of task τ i .

vi) Objective Function: As the duplicated task is executed with the frequency of the original task, their execution consumes the same energy. Therefore, the energy consumption of original task τ i and its potential duplicated task is:

E i = l∈L (1 + σ i )s il P l C i f l . (6)
Based on Equation ( 6), the total energy consumed by the system until the deadline is E s = i∈N E i . Based on the objective function and the aforementioned constraints, the Primal Problem (PP) is formulated as

PP : min s,q,σ,d E s (7)
s.t.

(1), ( 2), ( 3), (4a), (4b), [START_REF] Mbrahimi | Comprehensive Analysis of Alpha and Neutron Particle-induced Soft errors in an embedded Processor at Nanoscales[END_REF],

s il , q im , σ i , d im ∈ {0, 1}, ∀i ∈ N , ∀m ∈ M , ∀l ∈ L.
Since Equation ( 5) and Equation ( 6) include the nonlinear items q im t i , d im t i and σ i s il , PP is an INLP problem, which is difficult to solve optimally. In order to find the optimal solution, and simplify the structure of problem, we equivalently transform PP to an MILP problem. By applying variable replacement, the nonlinear variable combinations are replaced and an equal to the original MILP formulation is obtained. To this end, we introduce the following Lemma: According to Lemma 2, we introduce the auxiliary binary variable h il and let h il = σ i s il . Then, Equation ( 6) can be replaced by:

E i = l∈L s il P l C i f l + h il P l C i f l , ∀i ∈ N , (8a)
-s il + h il ≤ 0, -σ i + h il ≤ 0, s il + σ i -h il ≤ 1, ∀i ∈ N , ∀l ∈ L. (8b)
As a next step, q im t i and d im t i are linearized. Since s il ∈ {0, 1} and C i is large enough, one cycle has a negligible impact on the solution. Thus, t i are relaxed to continuous variables: 0 ≤ t i = l∈L s il Ci f l ≤ T i , where T i = Ci fmin . The following lemma is introduced: Lemma 3. Given two positive constants s 1 and s 2 , there are two constraint spaces

P 1 = {[t, b, x]|t = bx, -s 1 ≤ x ≤ s 2 , b ∈ {0, 1}} and P 2 = {[t, b, x]| -bs 1 ≤ t ≤ bs 2 , t + bs 1 -x -s 1 ≤ 0, t -bs 2 -x + s 2 ≥ 0, b ∈ {0, 1}}, then P 1 P 2 .
Proof. i) P 1 P 2 : According to t = bx and -s 1 ≤ x ≤ s 2 , then -bs 1 ≤ t ≤ bs 2 . Based on -s 1 ≤ x ≤ s 2 and b ∈ {0, 1}, then (b -1)(x -s 2 ) ≥ 0 and (b -1)(x + s 1 ) ≤ 0. Therefore, t -bs 2 -x + s 2 ≥ 0 and t + bs 1 -x -s 1 ≤ 0 hold. ii) P 1 P 2 : When b = 0, t = 0 and -s 1 ≤ x ≤ s 2 according to P 2 space definition. When b = 1, then -s 1 ≤ t = x ≤ s 2 from P 2 . Thus, P 1 P 2 .

Based on Lemma 3, the continuous variables χ im = q im t i and ξ im = d im t i are introduced, replacing Equation ( 5) by:

i∈N χ im + i∈N ξ im ≤ D, ∀m ∈ M , (9a)
-T i q im +χ im ≤ 0, -t i +χ im ≤ 0, T i q im +t i -χ im ≤ T i , ∀i ∈ N , ∀m ∈ M , (9b)
-T i d im +ξ im ≤ 0, -t i +ξ im ≤ 0, T i d im +t i -ξ im ≤ T i , ∀i ∈ N , ∀m ∈ M . (9c)
Therefore, the primal problem ( 7) is equally reformulated as follows:

PP1 : min s,q,σ,d,h, t,χ,ξ i∈N l∈L P l C i f l (s il + h il ) (10) s.t.          (1) ∼ (3), (4a), (4b), (8b), (9a) ∼ (9c), -l∈L Ci f l s il + t i = 0, ∀i ∈ N , s il , q im , σ i , d im , h il ∈ {0, 1}. 0 ≤ t i , χ im , ξ im ≤ T i , ∀i ∈ N , ∀m ∈ M , ∀l ∈ L.
Since all the variables (binary and continuous) are coupled linearly with each other, PP1 is an MILP problem.

Experimental Results

Experimental set-up: The processor model is based on RISC-V Instruction Set Architecture (ISA). We have used a high-level C++ model with 32-bit RISC-V ISA and standard 5-stage pipeline, i.e., the open-source Comet processor [START_REF] Rokicki | What You Simulate Is What You Synthesize: Designing a Processor Core from C++ Specifications[END_REF]. To obtain realistic bounds for the WCEC, we analyse typical benchmarks, such as stringsearch, qsort, blowfish, and dikstra (MiBench suite [START_REF] Guthaus | A Free, Commercially Representative Embedded Benchmark Suite[END_REF]) and integer matrix multiplication (matmul). Through a measurement-based approach using Comet simulator, we count the number of execution cycles and memory access (Table 4). To obtaining safe and context-independent measurement, the sources of timing variability are eliminated [START_REF] Deverge | Safe measurement-based WCET estimation[END_REF], i.e., data-caches are considered disabled, the task is executed without interferences on a single core (WCEC iso ). Taking into account the number of cores, the number of memory accesses, and the delay of accessing the main memory, we compute WCEC inf considering interferences. Regarding the DVFS, L = 6 voltage/frequency levels are used, based on the work of [START_REF] Quan | Feasibility Analysis for Temperature-Constraint Hard Real-Time Periodic Tasks[END_REF] considering 64 nm technology, as depicted Table 4.

To explore the ability to find optimal solutions and the solution quality, we performed a large and diverse set of experiments. More precisely, we tune the i) number of tasks, ii) WCEC, iii) reliability constraints and iv) deadline, considering 4 processors (M = 4). The failure rate constant has been set to d 0 = 3 and the initial failure rate λ 0 = 5 × 10 -6 faults per second [START_REF] Zhu | The Effects of Energy Management on Reliability in Real-Time Embedded Systems[END_REF]. Three task sets are considered with N =10, 20 and 30 tasks. We generate the tasks WCEC randomly based on the measured WCEC values of Table 4, i.e., within the range [1 × 10 8 , 4 × 10 8 ], incorporating the cost of the DVFS switching mechanism. The deadline is given by D

= k × N M × 1 2 ( Cmax fmin + Cmax fmax ),
where k controls the range of the deadline, from tight deadlines up to more relaxed ones. The reliability constraint is randomly selected using Low Reliability Threshold (LRT) range [0.9990, 0.9995] or a High Reliability Threshold (HRT) range [0.9995, 1] based on the magnitude 10 -3 of reliability target in [START_REF] Haque | On Reliability Management of Energy-Aware Real-Time Systems Through Task Replication[END_REF]. Notice that, these numbers change only the values of the problem parameters, and not the problem structure. The evaluation is performed following the Once Tuning One Parameter (OTOP) approach, where only one parameter is modified at each experiment. Each experiment is repeated 20 times, modifying the WCEC and the reliability constraints. Each figure point presents the average result. In total, we have performed at least 12 (different deadline values) × 3 (number of tasks) × 20 (with different WCEC and reliability constraint) = 720 experiments, per approach. The first set of experiments explores how the proposed approach behaves (energy consumption, percentage of duplicated tasks) with respect to i) real-time constraints and ii) reliability constraints. The second set of experiments compares the energy consumption, the feasibility (the percentage of the experiments where we obtained the optimal solution), the reliability improvement, and the estimation time, under reliability and real-time constraints for: i) the proposed Duplication-based Fault-Tolerant Mapping Approach (DFTMA), ii) a task mapping approach always satisfying the reliability constraint, without applying task duplication (formulated as FTM), similar to [START_REF] Xie | Resource Consumption Cost Minimization of Reliable Parallel Applications on Heterogeneous Embedded Systems[END_REF], and iii) a task mapping approach (formulated as FDM) always applying task duplication, similar to [START_REF] Haque | On Reliability Management of Energy-Aware Real-Time 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 set to two. We present results using LRT range, in order not to penalise the FTM approach. FTM under HRT constraint leads to many infeasible solutions. Since FTM and FDM are INLP problems, we apply the proposed transformation to convert them into an MILP problems, in order to be able to compare their optimal solutions. We have used Matlab 2018a to implement and solve (MILP solver) the problem formulation of DFTMA, FTM and FDM formulation. The simulations are performed on a quad-core 2.11 GHz Intel i7 processor and 16 GB RAM.

s il P l Ci f l s.t.              (1), (3)
,

l∈L s il e -ϕ i (f l ) ≥ R th i , ∀i ∈ N , i∈N qimti ≤ D, ∀m ∈ M , s il , qim ∈ {0, 1}, ∀i ∈ N , ∀m ∈ M , ∀l ∈ L. FDM : min s,q,d i∈N l∈L 2s il P l Ci f l s.t.         
(1), ( 3), (4b), [START_REF] Mbrahimi | Comprehensive Analysis of Alpha and Neutron Particle-induced Soft errors in an embedded Processor at Nanoscales[END_REF],

M m=1 dim = 1, ∀i ∈ N , s il , qim, dim ∈ {0, 1}, ∀i ∈ N , ∀m ∈ M , ∀l ∈ L.
Real-time constraint: Fig. 1a shows the energy consumption DFTMA, when the parameter k is tuned, from tight up to relaxed deadlines, with a reliability constraint within the LRT range. Fig. 1a shows that more energy is consumed: i) when the task number N increases, and ii) when real-time constraints become tight (k decreases), since higher frequencies are required to meet the deadline. With k increasing, more slack exists, and a lower frequency (that still meets the reliability constraints) can be assigned, minimizing energy consumption. From a point and on (k = 1.6 for N = 10, k = 1.4 for N = 20, k = 1.5 for N = 30), the energy consumption is stable; the deadline is relaxed enough, and thus, it does not influence the global optimal solution. Fig. 1b shows the percentage of duplicated tasks by DFTMA. The number of duplicated tasks is low at tight deadlines; no slack exists, thus duplication cannot be applied and the deadline met at the same time. As k increases, slack is created, tasks are duplicated and lower frequencies are assigned, reducing energy consumption. With large enough deadline, almost all tasks are duplicated and executed with low frequencies. Reliability constraint: We further explore the behavior of DFTMA, when the reliability constraints belong to LRT and HRT regions. Fig. 2 shows the obtained energy consumption, when N = 10 (Fig. 2a) and N = 20 (Fig. 2b). The energy consumption decreases with more relaxed deadlines. The HRT case consumes more energy than LRT case under same conditions. As expect, when k is low, i.e., the deadline is strict, the strict reliability constraints require higher frequency to execute the tasks, which consumes more energy. Energy consumption comparison: The energy consumption comparison of DFTMA, FTM and FDM approaches is depicted in Fig. 3a, with N = 10 and in Fig. 3b, with N = 20. A general observation is that the energy consumption obtained by DFTMA and FTM follows a similar trend. When the deadline is not strict, the energy consumption of DFTMA is less than the consumption of FTM. The FTM approach selects higher frequencies, since it requires to always satisfy the reliability constraints. On the contrary, DFTMA approach can exploit partial task duplication and use of lower frequencies in order to reduce energy consumption. The energy consumption of the FDM approach is much higher than both DFTMA and FTM approaches, especially when the real-time constraints are strict (e.g., k within the range [0.9, 1.4] in Fig. 3a). High frequencies are required when deadline is strict in order to execute both original and duplicated tasks before the deadline, leading to high energy consumption. As k increases, lower frequencies are assigned, reducing energy consumption. With a relaxed enough deadline (after k = 1.6 in Fig. 3a and k = 1.5 in Fig. 3b), all tasks can be duplicated with low frequencies. DFTMA obtains the same solution in this case. DFTMA decides task duplication for all tasks after k = 1.6 with N = 10 and after k = 1.4 with N = 20, approaching the same behavior of FDM, which always applies duplication, achieving lower energy consumption than FTM. Feasibility comparison: The percentage of solutions found by DFTMA, FTM and FDM approaches is depicted in Fig. 4a, when N = 10 and in Fig. 4b, when N = 20. A general observation is that the proposed DFTMA approach can find 0.6 0. Fig. 5: Reliability improvement the solution, even in cases where the FTM and FDM approaches are not able to find a solution, especially when the real-time constraint is strict, i.e., when k has a small value. The FDM approach has the worst behavior. In strict deadline cases (when k is small, k = 0.5 ∼ 0.9 with N = 10 and k = 0.6 ∼ 1 with N = 20), FDM cannot find any solution. This is explained since the FDM approach applies duplication for each task, thus more time is needed to execute the original and the duplicated tasks, compared to both the FTM (no duplication) and the proposed DFTMA (partial duplication of tasks). Compared with FTM, the proposed approach performs generally better: in FTM approach, the reliability is a hard constraint that must be always satisfied, whereas in DFTMA, if the reliability constraint cannot be satisfied by original task execution, then a duplication task is applied to achieve a reliable execution. In this way, the proposed approach has a higher probability of finding the solution. Both in Fig. 4a and Fig. 4b, we can observe that when deadline becomes relaxed enough, after a given point (for example when k = 1.4 in Fig. 4a and k = 1.7 in Fig. 4b), all the three approaches can almost 100% provide a solution. This is possible since the deadline constraints, after these points, become loose enough and do not impact the feasibility of obtaining a solution.

Reliability Improvement (RI): Fig. 5 shows the task reliability improvement above the reliability constraint, i.e., RI = R i -R th i . The trend is the same for N = 10 and N = 20. For strict deadline, the RI is high for both DFTMA and FTM, due to the assignment of high frequencies, while FDM cannot find solutions. With deadline relaxing, FTM achieves a low RI, as it only requires to meet the reliability constraint. However, DFTMA exploits the time slack, duplicating tasks, increasing RI. Whenever FDM finds a solution, it has higher RI, due to full duplication. As k increases, DFTMA and FDM behave similarly. Estimation time: Table 5 depicts the time required to obtain the solutions. For all approaches, the stricter is the deadline, the higher is the estimation time. Even if the proposed approach requires a few more seconds it is able to find a significantly higher number of solutions. For instance, when N = 10 and k = 0.5, DFTMA requires 5.26 sec more than FTM, but it finds solutions for 20% of the experiments, while the FTM finds very few ones. When k = 0.7, although the estimation time is similar, DFTMA is able to find optimal solutions for all experiments, while FTM found only 22% and FDM none. For the remaining cases, the estimation times are comparable. It should be stressed that as the approaches are applied offline, and thus, trading off a few more seconds in order to obtain optimal solutions is motivating.

Conclusion

In this paper, we studied the problem of task mapping by jointly solving task allocation, task frequency assignment, task duplication decision on multicore architectures enhanced with DVFS. The goal is to minimize energy consumption without violating the real-time constraint and taking into account the reliability. A safe transformation of the original INLP problem is applied to obtain an equivalent MILP problem, which is solved optimally. Through comparison of the proposed approach and two other energy-aware existing task mapping approaches, experimental results show that the proposed approach provides better trade-off between energy consumption and reliability, being able to find optimal solutions, even when existing approaches cannot. As future direction, the proposed strategy will be explored for heterogeneous architectures and for dependent task model.

Lemma 2 .

 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. The inequalities g ≤ b 1 and g ≤ b 2 ensure that g will be zero, if either b 1 or b 2 is zero. The equality g ≥ b 1 + b 2 -1 ensures that g becomes 1, if both variables b 1 and b 2 are equal to 1.

Fig. 1 :

 1 Fig. 1: Energy consumption and duplication decision for LRT.

Fig. 2 :

 2 Fig. 2: Energy consumption considering LRT and HRT.

= 20 Fig. 3 :

 203 Fig. 3: Energy consumption comparison.

Table 1 :

 1 Comparison with representative State-of-the-Art

	Ref.	Objective	Task replicas	Platform

Table 2 :

 2 Motivational Example

	f l f1	f2	f3	f4	f5	f6	2f1	2f2	2f3	2f4	2f5	2f6
	t 0.4994 0.4825 0.4677 0.4547 0.4431 0.4	0.9988 0.965 0.9444 0.9094 0.8862 0.8
	E 2.1169 2.7905 3.6959 4.926 6.6141 8.9525 4.2338 5.581 7.3918 9.852 13.2282 17.905
	R 0.9753 0.9909 0.9965 0.9985 0.9994 1	0.99939 0.99992 0.99999 0.99999 0.999999 1
	a) Feasible solutions of three approaches under reliability constraint
	DFTMA A1=f6, A2=f5, A3=2f4, A4=2f3, A5=2f2, A6=2f1
	FTM	B1=f6, B2=f5
	FDM	C1=2f6, C2=2f5, C3=2f4, C4=2f3, C5=2f2, C6=2f1
	b) Feasible and optimal solutions under reliability and deadline constraints
	≤ D	0 0.4	0.4431 0.8	0.8862 0.9094	0.9444	0.965	0.9988
	D <	0.4 0.4431 0.8	0.8862 0.9094 0.9444	0.965	0.9988	-

Table 3 :

 3 Main Notations

Table 4 :

 4 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	W CEC iso (Cyc.) Num. Accesses W CEC inf (Cyc.)
	matmul int 32x32	3,313,958	371,957	226,488,158
	matmul int64 32x32	4,055,289	507,133	308,335,089
	qsort int 1000	875,616	184,089	111,329,016
	qsort int64 1000	1,219,854	259,553	156,951,654
	qsort softfloat 1000	1,745,122	185,437	113,007,322
	dijkstra	766,369	117,151	71,056,969
	blowfish	3,058,991	110,330	69,256,991
	stringsearch	13,093,544	597,608	371,658,344

Table 5 :

 5 Estimation time (seconds) when at least one solution is found

						N=10	N=20
	k	0.5 0.6 0.7 0.8	0.9	1.0 1.1 1.2 1.3 1.4 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7
	DFTMA 8.36 0.14 0.13 0.05 0.16 0.19 0.06 0.06 0.09 0.06 114 1.23 0.16 0.13 0.13 0.2 0.05 0.06
	FTM	3.1 0.06 0.11 0.03 0.13 0.06 0.02 0.03 0.03 0.02 10.75 0.56 0.11 0.08 0.06 0.14 0.02 0.02
	FDM	-	-	-	-179.03 23.81 0.05 0.03 0.02 0.03	-	94.7 20.66 0.09 0.03 0.02 0.09 0.11

√ √ √ √ √

Acknowledgement

This work has been founded by China Scholarship Council (CSC).


Joseph Paturel

Angeliki Kritikakou

Olivier Sentieys

Fast Cross-Layer Vulnerability Analysis of Complex Hardware Designs

Keywords: Fault injection, vulnerability analysis, RISC-V

Simulation-based fault injection is commonly used to estimate system vulnerability. Existing approaches either partially model the fault masking capabilities of the system under study, losing accuracy, or require prohibitive estimation times. This work proposes a vulnerability analysis approach that combines gate-level fault injection with microarchitecturelevel Cycle-Accurate and Bit-Accurate simulation, achieving low estimation times. Single and multi-bit faults both in sequential and combinational logic are considered and fault masking is modeled at gate-level, microarchitecture-level and application-level, maintaining accuracy. Our case-study is a RISC-V processor. Obtained results show a more than 8% reduction in masked errors, increasing more than 55% system failures compared to standard a fault injection approach.

I. INTRODUCTION

Over the past few years, the Soft Error Rate (SER) of hardware designs has significantly increased due to reduced technology node sizes and lower supply voltages [START_REF] Ibe | Impact of Scaling on Neutron-Induced Soft Error in SRAMs From a 250 nm to a 22 nm Design Rule[END_REF]. Circuits designed using modern deep-submicron technologies have become more and more sensitive to environmental sources [START_REF] Rehman | Reliable Software for Unreliable Hardware: A Cross Layer Perspective[END_REF], such as ionization, radiation, and high-energy electromagnetic interferences, leading to temporary reliability violations, called soft-errors. These sources can affect a memory cell of a design, corrupting its contents (flip the bit it contains). This type of fault is known as Single-Event-Upset (SEU). As technology node sizes have significantly reduced, several memory cells can be corrupted at the same time, leading to Multi-Bit-Upsets (MBUs) [START_REF] Ebrahimi | A layout-based approach for multiple event transient analysis[END_REF]. Moreover, when a combinational cell is affected, a logic transient, known as Single-Event-Transient (SET), is generated. The SET is propagated in the forward cone of the impacted cell, and it can eventually reach one or several flip-flops and corrupt their values. Until recently, soft errors occurring in memory circuits have been considered as the major contributors to the SER due to their large sizes and high-density, making them statistically more likely to be affected. However, soft errors occurring within logic circuits have become more and more important and combinational logic cannot be considered negligible anymore [START_REF] Mahatme | Comparison of Combinational and Sequential Error Rates for a Deep Submicron Process[END_REF], [START_REF] Psiakis | NEDA: NOP Exploitation with Dependency Awareness for Reliable VLIW Processors[END_REF].

As a result, the vulnerability of a design towards faults has to be evaluated as part of the development process. To do so, techniques that force the appearance of faults (fault injection) in different structures of the design are often employed. To obtain an accurate vulnerability analysis, the masking effects occurring at each layer of the design must be taken into account: from the logical and timing masking occurring at the gate-level, the microarchitectural masking introduced by the way computational blocks are arranged, up to the application masking resulting from the application tolerance to errors. To achieve that, fault injection has to be performed at a low layer, such as the gate-level. However, when complex designs are considered, prohibitive estimation times are required. As shown by our experimental results (Table VI-Section III), a gate-level fault injection on a RISC-V processor running an 4x4 matrix multiplication requires more than four months CPU time for a statistically representative vulnerability analysis.

To speed up the process, some approaches ignore the implementation details of the design. For instance, fault injection at the application level [START_REF] Mutlu | Characterization of the Impact of Soft Errors on Iterative Methods[END_REF] is only able to alter the data held in the variables of the application under study. However, by ignoring the underlying executing hardware, this leads to less accurate vulnerability analysis [START_REF] Laurent | Fault injection on hidden registers in a risc-v rocket processor and software countermeasures[END_REF]. The majority of approaches considering the hardware of the design focus only on single-bit faults occurring in the sequential logic [START_REF] Mao | An Automated Fault Injection Platform for Fault Tolerant FFT Implemented in SRAM-Based FPGA[END_REF]- [11]. For example, in the cross-layer vulnerability analysis flow of [11], the appearance and propagation of faults are modelled as SEUs, occurring in selected design regions. The flow uses an RTL simulator for a predefined number of cycles. Then, the state of the design is handled to a functional simulator for faster analysis. However, these approaches discard the presence of faults in combinational logic and the possibility that several bits of a design can be affected at the same time. In [START_REF] Wilkening | Calculating Architectural Vulnerability Factors for Spatial Multi-Bit Transient Faults[END_REF], several flip-flops of the design are simultaneously flipped through an almost exhaustive fault injection in the design registers, which requires high estimation time. Applying this approach to estimate the vulnerability of only the register file of the RISC-V processor for the 4x4 matrix multiplication application requires 4 hours 18 minutes. The technique presented in [START_REF] Chang | Hamartia: A fast and accurate error injection framework[END_REF] considers faults occurring both in the sequential and the combinational logic. Authors use an Instruction-Set Simulator (ISS) to execute the application. To inject a fault, the ISS invokes a gate-level simulator, that injects the fault in a cell of the design. The corruptions, induced by the fault, are obtained and given back to the ISS. As a gate-level simulation is not used for each application cycle, the estimation time is reduced. However, ISSs do not consider the hardware implementing the instruction set and are unaware of the design registers. Therefore, they cannot model the microarchitecture-level masking of the design, reducing accuracy. The obtained results show, on average, a 8.32% reduction in masked faults, which leads to an increase in the number of crashes (57.81%), hangs (24.76%), and data corruptions (5.78%) compared to standard SEU-based approaches.

The paper is organized as follows. Section II presents the proposed vulnerability analysis method. Section III analyzes the experimental analysis results on a RISC-V processor. Finally, a discussion on the accuracy of this work as well as a conclusion and future works are presented in Section V.

II. CROSS-LAYER VULNERABILITY ANALYSIS

To obtain a fast and accurate vulnerability estimation, we propose a cross-layer method based on two fault injection campaigns, at different hardware abstraction levels of the Design Under Test (DUT). Figure 1 depicts the overview of our method. The first campaign is performed at the gate level to statistically obtains error patterns independently of the application to be characterized. The error patterns describe the number of occurrences and the geometry of errors, due to SETs in the combinational logic and SEUs directly on the flipflops of the DUT, considering gate-level masking. To evaluate the impact of these patterns on an application, considering microarchitectural-level and application-level masking, the Fig. 1: Overview of proposed cross-layer vulnerability analysis second campaign is performed at the microarchitecture level, using a fast CABA simulator of the DUT microarchitecture.

A. Single-Cycle Gate-Level Analysis

The aim of the gate-level analysis is to create statistical models of the SEU and MBU occurring due to soft-errors, in both combinational logic and flip-flops of the DUT. To do so, the netlist of the DUT is enhanced with an injection block (built with a XOR gate and a multiplexer), attached to the output of each netlist cell, allowing the modification of the cell's outputs. These injection blocks allow for the appearance of an SET anywhere and at any time in the netlist. To not affect the timing characteristics of the DUT, the propagation delays of all the injection blocks are set to zero.

Once the netlist modified, it is used by the fault injection campaign described in Algorithm 1. Since the emergence of SEUs and MBUs, propagated from SETs through the combinational logic, depends on the values of the DUT inputs, we explore N input different sets of values as inputs. For instance, assuming that the DUT is the execution pipeline stage of a processor, these sets of values consist of instructions randomly selected from the processor's Instruction Set Architecture with random operands. For each new set of values (L.2), the DUT is executed without any fault (L.3) in order to obtain the golden reference (L.4), which will be used to detect errors. Then, N gl faults are forced into the netlist for this input set (L.5). The number of faults N to be injected is defined based on the required confidence level of the statistical analysis as

N = t 2 ×p×(1-p) e 2
(1), where t is the critical value related to the statistical confidence interval, e the error margin, and p the percentage of the possible fault population individuals that are assumed to lead to errors. p is usually set to 0.5 to maximize the sample size N . Eq. ( 1) is derived from [START_REF] Leveugle | Statistical fault injection: Quantified error and confidence[END_REF], where the population size is set to +∞ [START_REF] Tuzov | Accurate Robustness Assessment of HDL Models Through Iterative Statistical Fault Injection[END_REF]. Table II presents the evolution of the number of faults to inject in the DUT in order to meet certain statistical characteristics. Hence, at the gate level, the fault injection campaign performs N = N input ×N gl injections. During a fault injection cycle, the netlist cell (L.6), the time offset (L.7), and the duration of the fault to be injected (L.8), are selected. The cell that will be subject to injection is chosen function of its area -the bigger the cell, the higher its probability to be selected. The SET start time is selected randomly inside one clock cycle. The duration can be fixed, random, or provided by tools, that characterize the particles' impact over the netlist cells, e.g., MUSCA [START_REF] Hubert | A generic platform for remote accelerated tests and high altitude SEU experiments on advanced ICs: Correlation with MUSCA SEP3 calculations[END_REF]. The campaign waits until the SET start is reached (L.9) and the injection block of the selected cell is activated, flipping its output (L.10). If the selected cell is combinational (L.11), an SET has been injected and has to remain active for the selected duration (L.12). After this duration has passed, it is deactivated (L.13). Otherwise, the injected fault is an SEU affecting directly a flipflop cell (L.14). At the end of the cycle (L.15), the contents of the flip-flops provide the output, which is compared (through a XOR operation) with the golden reference (L. [START_REF] Hubert | A generic platform for remote accelerated tests and high altitude SEU experiments on advanced ICs: Correlation with MUSCA SEP3 calculations[END_REF]). The errors and the number of times they have been observed are logged (L.17). With this information, we obtain the error patterns and their frequencies. They will be used at the microarchitecturelevel injection campaign to perform an accurate vulnerability analysis. If the affected cell has several flip-flops in its forward cone, the SET propagation can lead to MBUs.

The gate-level analysis models the propagation of SETs during a single cycle. Hence, complex designs, that behave on a multi-cycle basis (such as pipeline circuits), have to be split into sections. Each section is a part of the design, where the output of combinational logic is computed and stored to flip-flops in a single cycle. To estimate the vulnerability of the complete design, the impact of the gate-level error patterns needs to be simulated on a platform, that is aware of the microarchitecture and able to accurately execute the application. To achieve that, we perform fault injection campaign at microarchitecture level, as described in next section.

B. Microarchitecture-Level Analysis

This analysis estimates the vulnerability of the complete DUT, taking into account microarchitecture-level and application-level masking. To achieve that, we extend a CABA simulator in order to inject the error patterns, collected at the gate level per DUT section, at the microarchitecture level.

The microarchitectural fault injection campaign is summarized in Algorithm 2. Initially, the application under study is executed on the DUT without faults in order to collect a set of golden references (L.1): i) application output, ii) system state (memory and registers), and iii) number of execution cycles. The campaign is executed N ml times per application (L.2), each time injecting a fault in the DUT. In order to obtain statistically correct vulnerability estimations, the number of faults required to be injected is computed using Eq. [START_REF] Ibe | Impact of Scaling on Neutron-Induced Soft Error in SRAMs From a 250 nm to a 22 nm Design Rule[END_REF].

During the application execution, the cycle to inject the fault is chosen randomly between the first cycle and the total number of cycles considering the fault-free execution (L.3). Then, the type of logic, where the fault is injected, is selected based on the area of the logic (L.4). For instance, if 40% of the DUT area is combinational logic, then it has a 40% chance of being chosen, and thus a 60% chance for the sequential logic. If the selected logic is sequential (L.5), an SEU is injected in a random flip-flop of the complete DUT (L.6), similar to common fault injection campaigns [START_REF] Mao | An Automated Fault Injection Platform for Fault Tolerant FFT Implemented in SRAM-Based FPGA[END_REF]- [START_REF] Azambuja | A Fault Tolerant Approach to Detect Transient Faults in Microprocessors Based on a Non-Intrusive Reconfigurable Hardware[END_REF]. If the selected logic is combinational (L.7), the injected fault is a gate-level error pattern of a DUT section. The selection of the DUT section is area driven (L.8) -the larger the DUT section, the more chances it has to be selected. Then, an error pattern is selected as a function of its frequency -the more often a pattern has been observed during gate-level analysis, the higher the chances of being selected. The selected error pattern is injected (L.9) and the simulation is resumed. When simulation ends (L.10), the outcome belongs into one of the following error classes (L.11):

• Masked: The application has executed without any error or mismatch compared to the golden reference. state differ from the golden references. Usually, an AOM will also present a mismatch in the memory of the design. Note that, the AOM and ISM classes do not completely overlap. For instance, assume that the DUT is a processor executing a for loop. A fault affects the register that stores the iteration counter. As result, the execution skips an iteration. The application output will not be correct, but if the for loop has not written to the memory, the final state of the processor will be the same as the golden reference.

III. EXPERIMENTAL RESULTS

To evaluate the proposed approach, a processor is used as DUT, i.e., the Comet processor [START_REF] Rokicki | What You Simulate Is What You Synthesize: Designing a Processor Core from C++ Specifications[END_REF] that implements the 32-bit RISC-V instruction set using a standard 5-stage pipeline. The processor is designed using a high-level C++ model, enabling a fast CABA simulator to be compiled from its description. The processor is synthesized to the gate-level using Mentor Graphics CatapultHLS and Synopsys Design Compiler with a target frequency of 650 MHz. The target technology is the 28 nm FDSOI design kit from ST-Microelectronics using the nominal corner with a supply voltage of 1.0 V. The critical path of is 1.53 ns, having a maximum operating frequency of 653.6 MHz. The technology node has been selected due to its low power characteristics, making this implementation of Comet akin to a low power microcontroller. The sequential logic represents 45.85% of the total processor area (including the register file), leaving 54.15% to the combinational logic. Table III depicts the area that each pipeline stage occupies. The write-back stage has the largest area, as it includes the register file, followed by the execution stage, which has the largest combinational logic. To obtain realistic fault models, the different cells of the design kit are analyzed using MUSCA [START_REF] Hubert | A generic platform for remote accelerated tests and high altitude SEU experiments on advanced ICs: Correlation with MUSCA SEP3 calculations[END_REF]. Considering neutron injections and an LET set to 58MeV/cm, the peak of the SET pulse width distribution is 400 ps. Section III-A presents gate-level analysis and Section III-B the microarchitecturelevel analysis for an SET pulse width equal to 400 ps and an operating frequency of 500 MHz. Section III-C analyses the impact of the processor frequency and the SET width.

A. Single-Cycle Gate-Level Analysis

To apply the gate-level analysis, the processor has been divided into sections, each being a pipeline stage. Due to page limitations, this section presents the results obtained for the execution stage. The results for the other stages are similar.

1) Gate-Level Error Patterns: The output of the gate-level analysis is a set of error patterns. Figure 2.a) shows the probability of each bit of the output register, i.e., the pipeline register between the execution and memory stages, to be erroneous.

Fig. 2: Gate-level analysis results of the execution stage

The average probability for a bit to be erroneous is 0.033%. Some regions of the register exhibit higher error probabilities than others. Such a region is between bit 32 and bit 63, with an average error probability of 0.043% (30.9% above average). This region corresponds to the result field of the register, i.e., the ALU output. It is more susceptible to errors because: i) the ALU combinational cells have large forward cones, and thus, the SETs are propagated through multiple paths to the register, and ii) the ALU logic masking depends on the operation -a multiplication operation has lower masking factor compared to a logical AND operation. The second most susceptible region is between bit 94 and bit 125, which corresponds to data resulting from logical operations on values from Control and Status Registers (CSRs). The remaining register regions correspond to data forwarded from the previous pipeline stage. Fig. 2.b) shows the amount of patterns that exhibit a specific amount of corrupted bits. We observe that 5.12% of the error patterns have more than one bit concurrently erroneous, i.e., they describe MBUs. The higher number of erroneous bits observed in an error pattern is 52 faulty bits, i.e, 41.3% of the register bits is corrupted. Although these error patterns are latched in the register, they do not necessarily lead to an error on the application execution. To assess their impact, the microarchitecture-level analysis of the DUT is required.

2) Estimation time: Based on Eq. ( 1), considering a 99.8% confidence interval with 5% error margin for each input set values, N input = 10 3 different set of values are used as inputs and N gl = 10 3 faults are injected per input, leading to N = 10 6 injections in total. Questa Advanced Simulator 10.7b running on a 2 nd generation Intel Xeon CPU is used for gate-level simulation.

B. Microarchitecture-Level Analysis

The gate-level analysis of each pipeline stage of the RISC-V processor provides the error patterns for each stage. To simulate the core, a CABA simulator was compiled from the C++ description of Comet, allowing the fault injection in any core register at any time. The simulator performance is 18.2 million instructions per second on average, using an 8 th generation Intel i7 CPU running at 2.40 GHz. We built a script around the CABA simulator to drive the microarchitecturelevel campaign. Initially, the number of faults required to be injected is computed based on Eq. ( 1). Using a 99.8% confidence interval and a 1% error margin, the number of faults to inject is 23,874. Then, faults are injected in the microarchitecture and the simulation outcomes are classified, as described in Section II-B. Four applications are analyzed: stringsearch, qsort and blowfish from MiBench suite [START_REF] Guthaus | MiBench: A free, commercially representative embedded benchmark suite[END_REF] and an 4x4 integer matrix multiplication.

1) Reliability results: The microarchitecture-level output is the distribution of observed errors to the error classes. Table IV compares the following vulnerability analysis methods:

• MA(S): SEUs are injected at microarchitecture-level, with a uniform occurring probability for all registers, as in [START_REF] Mao | An Automated Fault Injection Platform for Fault Tolerant FFT Implemented in SRAM-Based FPGA[END_REF]- [START_REF] Azambuja | A Fault Tolerant Approach to Detect Transient Faults in Microprocessors Based on a Non-Intrusive Reconfigurable Hardware[END_REF]. • MA(S,A): SEUs are injected at microarchitecture-level, with a occurring probability proportional to pipeline stage area. • CL(S,M,A): the proposed cross-layer vulnerability analysis method, considering SEUs, MBUs and pipeline stage area.

Considering that the Comet processor is microarchitecturally close to the Rocket chip [START_REF] Asanović | The rocket chip generator[END_REF], the MA(S) results are coherent with those of [START_REF] Cho | Impact of Microarchitectural Differences of RISC-V Processor Cores on Soft Error Effects[END_REF], strengthening the statement that processors, sharing the same ISA, also share similar vulnerability analysis. The obtained results show, on average, that the proposed CL(S,M,A) approach leads to 8.32% less masked faults, which results in a significant increase of other classes: 57.81% more crashes, 24.76% more hangs and 5.78% more data corruptions, compared to the standard MA(S) approach. Contrary to the proposed approach, the MA(S) analysis cannot explore the combinational logic and gate-level masking. More precisely, when evaluating the blowfish application, the proposed methodology provides a more than 10% decrease in the number of masked faults (equivalent to 1,457 faults) compared to the MA(S) approach. This significantly increases by 63.4% the number of observed crashes, which can be explained by the control-dominated nature of blowfish For the matmul application, we observe the maximum increase in data corruptions (AOM and ISM&AOM classes), which is 19.23% compared to MA(S) approach. This behavior is due to the high computation and data-dominated nature of the application. Since the execution stage has the largest area, it has a high injection probability, and, thus, a high probability in corrupting the applications operations.To further evaluate our cross-layer vulnerability analysis approach, we compare it with the MA(S,A) approach. The goal is to explore the origin of the observed results, i.e., whether it is the use of error patterns to model MBUs or the use of area of the pipeline stage. Since the percentage of MA(S,A) masked faults is even higher compared to MA(S), this implies that the origin is the MBUs modelled by our gate-level error patterns.

2) Estimation time: Table VI shows the estimation times to obtain the processor vulnerability for the: i) proposed crosslayer approach, and ii) gate-level fault injection campaign applied on the complete processor (Full gate-level) running the target application. The simulator (Section III-A) simulates a gate-level model of the full Comet processor at only 10.2 cycles per second. The smallest application (qsort) requires 6,478 cycles and the largest application (blowfish) 3,058,991 cycles, which correspond to simulation times of 171.84 and 81,144.83 days, respectively. The gate-level time of the proposed approach is 1,039 seconds of CPU time, as depicted in Table V. Since the same error patterns can be used to characterize several applications, the gate-level analysis is performed only once. Therefore, the overall estimation time of the proposed approach ranges between 366 minutes for qsort and 483 minutes for blowfish.

As a conclusion, the experimental results show that the Full gate-level approach requires prohibitive estimation time. On the contrary, the proposed cross-layer method requires significantly lower estimation time, while maintaining the accuracy of the analysis. This is achieved thanks to the gatelevel analysis is applied only once per DUT, since the obtained error patterns are reusable at the microarchitecture-level, and because of the use of a fast CABA microarchitecture simulator.

C. Target operating frequency and SET pulse width impacts

In this section, we carry out a set of campaigns in order to explore the impact of the target operating frequency and VIII show both the absolute number and the corresponding percentage of observed SEUs and MBUs, when varying the target operating frequency and the SET width, respectively. When frequency is varied, a fixed SET width of 400 ps is used. We observe that the percentage of faults leading to MBUs have small fluctuations, on average 5.24% of faults are MBUs. When SET pulse width is varied, the frequency is set to 500 MHz. We observe a similar behavior, i.e., on average 4.01% of faults are MBUs. Note that, when the pulse width is 100 ps and below the SETs are not often propagated within the latching window of the register. With a pulse width below 50 ps, no SETs are latched. These results show that MBUs represent a significant part of the error population, regardless of the operating frequency or SET pulse width. This observation, coupled to the impact of MBUs at the microarchitecture-level, imply that MBUs generated bu combinational logic, should not be neglected to obtain an accurate vulnerability analysis.

IV. DISCUSSIONS

It is noteworthy that a full gate-level simulation of the design, running the application, could yield a better accuracy, but it would require prohibitive exploration time. Also note that, once an SET has been propagated to the flip-flops of its forward cone, the gate-level simulator effectively serves as a CABA simulator. Therefore, from this point and on, simulation can continue at a higher abstraction level, such as the microarchitecture level, making it faster than full gate-level simulators. The difference between the proposed approach and a complete gate-level injection campaign is that we replace the analysis of each application specific instructions, with a reusable statistically significant distribution of error patterns.

V. CONCLUSION AND FUTURE WORK

The proposed cross-layer vulnerability analysis is based on two fault injection campaigns, carried out at different hardware abstraction levels. The gate-level analysis considers realistic soft-errors, occurring both at the combinational cells and the flip-flops cells. It is performed only once to reduce the overall analysis time. The obtained error patterns drive the fault injection at the microarchitecture level. The experimental results show less masked errors, compared to standard microarchitecture-level analysis, and significant reduction in estimation time, compared to full gate-level analysis methods. On top, although the number of MBUs required to be injected is small, they have significant impact on the error populations. As future work, we will focus on improving further the accuracy and the speed of the proposed methodology. Regarding accuracy, the precision of the gate-level analysis can be improved by considering that a single high-energy particle can impact to several combinational cells (creating multiple simultaneous SETs) on scaled technology nodes [START_REF] Ebrahimi | A layout-based approach for multiple event transient analysis[END_REF].

Algorithm 1 :

 1 Gate-level fault injection campaign L1 for inputData in inputDataSets[0...Ninput-1] target cell is a flipflop, the error is latched L15 waitForClockRisingEdge(); L16 error = compareDUTOutput(); L17 log(error);

•

  Hang: The application has entered an infinite loop. A cycle counter is used to stop the current injection simulation, if the counted cycles exceed a threshold.• Crash: The execution of the application has terminated unexpectedly and an exception has been raised (out of bound memory access, misaligned PC, hardware trap, etc.) • Application Output Mismatch (AOM): Only the output of the application differs from the golden reference. • Internal State Mismatch (ISM): Only the system state (memory and registers) differs from the golden reference. • ISM & AOM: Both the application output and the system Algorithm 2: Microarchitecture-level fault injection L1 output, state, cycles = collectGoldenReference(); L2 for fault in [0...N ml -1] (); L9 injectAnErrorPattern(combSection); L10 waitForSimulationEnd(timeout); L11 classifySimulationOutcome(output, state);

  Table I summarises the aforementioned representative works. This work addresses the above limitations by proposing

	Reference	Masking type Gate-level µArch Application SEU Fault model MBU
	[6]	-	-
	[8]-[11]	-	-
	[12]	-
	[13]		-
	Proposed

TABLE I :

 I Comparison of representative state-of-the-art a fast cross-layer vulnerability analysis method, applicable to entire complex hardware designs, providing statistically representative vulnerability analysis. It considers faults both in the sequential and combinational logic, as well as masking at the gate-level, microarchitecture-level and application-level. More precisely, the contributions of this work are:

	• A vulnerability analysis method combining two fault in-
	jection campaigns at different hardware levels, i.e, gate-
	level and microarchitectural-level. The gate-level campaign
	is applied once per design. It statistically analyses re-
	alistic faults both at the combinational and sequential
	logic, providing a higher level of accuracy. It produces
	error patterns that depict the impact of gate-level mask-
	ing. The microarchitectural-level campaign is applied per
	application under study. It is based on a fast Cycle-
	Accurate and Bit-Accurate (CABA) simulator, able to eval-
	uate microarchitectural-level and application-level masking.
	The injection is driven by the gate-level error patterns.
	• The population of SEUs and MBUs occurring due to re-
	alistic SETs on the combinational and sequential logic is
	analyzed by tuning the design operating frequency and SET
	pulse width. Results highlight the notable impact of MBUs
	on vulnerability analysis.
	• A vulnerability analysis of a RISC-V processor is provided.

TABLE II :

 II Number of faults required to be injected.

TABLE III :

 III Area of each pipeline stage of the Comet processor

  Table V shows the CPU time required to perform the gate-level fault injection for all pipeline stages.

	Pipeline stage Fetch Decode Execute Memory WriteBack
	Est. Time (s)	37	392	496	82	32

TABLE V :

 V Gate-level analysis time of each pipeline stage

TABLE VI :

 VI Comparison of estimation times application.

TABLE IV :

 IV Comparison of vulnerability analysis resultsSET pulse width on MBUs population for the execution stage. TableVII and Table

TABLE VII :

 VII Occurred SEUs and MBUs w.r.t. frequency

	SET	100 ps	200 ps	400 ps	500 ps
	SEU 5,144 (97.6%) 10,529 (95.3%) 26,489 (94.9%) 33,449 (95.9%)
	MBU 127 (2.4%)	755 (4.7%)	1,429 (5.1%) 1,432 (4.1%)

TABLE VIII :

 VIII Occurred SEUs and MBUs w.r.t SET pulse width


Angeliki Kritikakou

Stefanos Skalistis

Progress-aware Dynamic Slack Exploitation in Mixed-critical Systems: Work-in-Progress

Keywords: Run-time adaptation, Remaining Response Time, Mixed-critical systems

Mixed-critical systems consist of high criticality and low criticality applications. When a high criticality task exceeds its less pessimistic Worst Case Execution Time (WCET), the system switches mode and low criticality tasks are usually dropped. To postpone mode switch, existing approaches explore the slack, created dynamically due to an actual execution of a task that is faster than its WCET. However, the slack is visible only after the task has finished. To further enable dynamic slack exploitation, we propose a fine-grained approach that exposes the slack created due to the progress of tasks, during execution, and safely uses it to postpone mode switch.

I. INTRODUCTION AND MOTIVATION

Mixed-critical systems [START_REF] Vestal | Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[END_REF] consist of high criticality and low criticality applications, with different properties and requirements. The Worst-Case Execution Time (WCET) of applications is typically used in order to provide timing guarantees. However, due to both application and hardware characteristics, pessimism is introduced during WCET estimations. As a result, safe, but over-approximated WCET estimations are obtained, that typically over-allocate resources to high criticality applications. To reduce this negative impact, mixed-critical systems use different WCET estimations for high criticality tasks: a safe, but pessimistic, upper bound (C H ), typically based on static analysis, and a less pessimistic, but less trust-worthy, bound (C L ), typically obtained by measurementbased approaches [START_REF] Papadopoulos | AdaptMC: A Control-Theoretic Approach for Achieving Resilience in Mixed-Criticality Systems[END_REF]. Low criticality tasks are bounded by a single, less pessimistic, WCET estimation. The system starts execution in low criticality mode (LO-mode). Usually, if a low criticality task exceeds its C L , it is dropped. However, as soon as a high criticality task exceeds its C L , the system switches from low to high criticality mode. Low criticality tasks are usually dropped to meet the timing constraints of the high criticality tasks [START_REF] Baruah | Response-time analysis for mixed criticality systems[END_REF], degrading system QoS.

To improve QoS, existing approaches work on two directions: i) explore other strategies than dropping low criticality tasks, and ii) explore static or dynamic ways to postpone the mode switch. This work focuses on the latter category for uniprocessor systems, which is orthogonal and can be combined with the former category. Static approaches determine task overrun values, which when added to the C L of high criticality tasks, the system remains schedulable. These values extend the mode switch further than C L . Such examples are methods inspired by sensitivity analysis [START_REF] Santy | Relaxing mixedcriticality scheduling strictness for task sets scheduled with fp[END_REF] and zero-slack [START_REF] De Niz | Partitioned scheduling of multi-modal mixedcriticality real-time systems on multiprocessor platforms[END_REF]. As static approaches are applied before execution, they explore only the existing slack due to system under-utilisation. On the contrast, dynamic approaches exploit the slack created during execution. When the actual execution time of a task is lower than its C L , slack is created that can be used by subsequent tasks. However, existing approaches are able to observe and use the slack, only after the task has terminated, e.g., single budget [START_REF] Hu | On-the-fly fast overrun budgeting for mixed-criticality systems[END_REF], bailout protocol [START_REF] Bate | A bailout protocol for mixed criticality systems[END_REF] and feedback control mechanisms [START_REF] Papadopoulos | AdaptMC: A Control-Theoretic Approach for Achieving Resilience in Mixed-Criticality Systems[END_REF].

This work extends the state-of-the-art by dynamically exploiting, not only the slack created due to the early termination of tasks, but also the slack created due to the actual progress of tasks, during execution. To achieve that, we propose a run-time controller that regularly, at instrumentation points, exposes the actual execution progress of high criticality tasks and recomputes their response times in LO-mode. The observed differences are used to compute the dynamically created slack, which is used in order to postpone, or even avoid, the system mode switch. As our run-time computation takes into account the actual progress execution, the online computed response time bounds are typically reduced, compared to the initial worst case estimations, computed offline.

II. SYSTEM MODEL

The system is defined as a finite set of tasks T executed on a single processor. For simplification reasons, and without loss of generality, a dual-criticality system is assumed, where each task has a level of criticality equal to either high (H) or low (L), with H > L. Each task, τ i , is defined by its period (minimum arrival interval) T i , deadline D i , criticality level CL i and the WCET C CL i for each criticality level, i.e., C H i and C L i . It is reasonable to assume that C CL i is monotonically non-decreasing with increasing CL i [START_REF] Baruah | Towards the design of certifiable mixed-criticality systems[END_REF]. Tasks give rise to a potentially unbounded sequence of jobs. Jobs can be either dependent, or independent, and can be periodically executed in a preemptive manner on the processor. We use the basic mixed criticality model, where the system has two modes of execution: i) LO-mode, where both high criticality tasks and low criticality tasks are executed on the processor, and ii) HImode, where only the high criticality tasks are executed on the processor.

III. PROPOSED METHODOLOGY

The proposed approach, during execution, regularly exposes the progress of high criticality tasks and reflects that information globally to the system. This allows a more accurate re-computation of the remaining response time of each high 1 criticality task in LO-mode, as the execution progresses. Having such information, it is now possible to compute in a fine-grained way the dynamic slack created during execution. To achieve that, each high criticality task is instrumented by set of points. During execution, the proposed controller is enabled at a point p of a high criticality task i, when the system is in LO-mode. It applies the following steps: 1) Remaining WCET computation (RC L i ), i.e., the run-time estimation of the WCET of the code that remains to be executed, from point p, until the end of execution in LOmode (inspired by [START_REF] Kritikakou | Runtime control to increase task parallelism in mixed-critical systems[END_REF]).

2) Remaining Response Time computation (RR L i ), i.e., runtime computation of the new response time of i in LOmode, taking into account the actual time and the remaining preemption delays of both low and high criticality, higher priority, tasks (RP L hp(i) ). 3) Dynamic slack computation in LO-mode, obtained by the difference of the newly computed response time compared to the previously computed value. 4) Safety condition: if the slack is higher or equal to the additional time required to reach the next instrumentation point, in HI-mode, high and low criticality tasks continue execution. Otherwise, the slack is depleted and mode switch must occur. 5) Remaining preemption delay computation (RP L hclp(i) ), i.e. update the preemption delay that task i may cause to other high criticality, but lower priority, tasks, according to its updated Remaining WCET.

IV. EVALUATION

In this preliminary experimental set-up, we consider the PULP RISC-V processor of GAP8 platform [START_REF] Flamand | Gap-8: A risc-v soc for ai at the edge of the iot[END_REF] as our platform model. Table I depicts the characteristics of the task set, consisting of two high criticality tasks (AES-CTR and CannyEdge) and two low criticality tasks (matmul and FFT). The C L of the benchmarks is obtained by the observed execution cycles, when the code is executed on a single PULP core [START_REF] Flamand | Gap-8: A risc-v soc for ai at the edge of the iot[END_REF]. To obtain the C H , we apply safe margins of 20%. Fig. 1 shows the schedule in the low criticality mode. We compare the proposed approach with typical existing approaches that decide to switch mode, when the actual progress reaches the C L , and the task has not finished execution (SoA), e.g. [START_REF] Baruah | Response-time analysis for mixed criticality systems[END_REF]. We explore their behavior with respect to the possible actual execution time of benchmarks by allowing any part of the benchmarks, defined by two consecutive points p, p , to executed faster or slower than C L p,p . In particular the actual execution time of each part is selected within the range [80%×C L p,p , 120%×C L p,p ], while maintaining the total actual execution time of the benchmarks within the range [C L , 105% × C L ], with a step of 0.5% × C L . Fig. 2(a) depicts the moment when each approach decides to switch modes. As long as the actual execution time is larger than C L , the SoA decides always to switch mode when the first high criticality task exceeds its C L , i.e., when AES-CTR actual progress reaches 15, 300 cycles, i.e., at 67, 300. On the contrary, the proposed approach exposes the dynamic slack created due to the actual progress of CannyEdge, before being preempted. As long as this slack is large enough, the mode switch is not required to be decided by AES-CTR, but later on, by CannyEdge. As Fig. 2(b) shows, the postponement of the mode switch had allowed the execution of all low criticality tasks, compared to SoA. Notice that, in this experimental set-up, dynamic approaches will behave as SoA, since CannyEdge has not finished execution, and thus, the potential slack is not yet observable.

TABLE I

 I Task set characteristics.

														SoA	Proposed
														Execution time (KCycles)	0 50 100 150 200
														+5% +4.5% +4% +3.5% +3% +2.5% +2% +1.5% +1% +0.5% 0%
														Actual execution time w.r.t. CL
														(a) Time when mode switch occurs (y-axis)
														Execution time (KCycles)	20 40 60 80	SoA	Proposed
														0
														+5% +4.5% +4% +3.5% +3% +2.5% +2% +1.5% +1% +0.5% 0%
														Actual Execution time w.r.t. CL
														(b) Low criticality progress (y-axis)
														Fig. 2. Comparison of proposed and SoA approaches
	Benchmark		CL	C L			C H		Priority Arrival
	CannyEdge		H	99,500 119,400	3		0
	matmul			L	41,900		-		1		50,000
	AES-CTR			H	15,300		18,360	0		52,000
	FFT				L	28,200		-		2		53,600
	CannyEdge	MatMul AES-CTR	MatMul	FFT	CannyEdge
														KCycles
	0	…	50	…	52	…	67.3	…	107.2	…	135.4	…	184.9
	Fig. 1. Execution in low criticality mode; arrows depict the arrival of each
	task.