This is an extended version of the paper accepted to be published in IEEE
(TCAD) 2021 which includes Appendices A-E-0.8cm,-9.0cm1.090.01.3

# Toward the Design of Fault-Tolerance- and Peak- Power-Aware Multi-Core
Mixed-Criticality Systems

Behnaz Ranjbar, Ali Hosseinghorban, Mohammad Salehi, Alireza Ejlali, and Akash
Kumar Manuscript received September 30, 2020; revised December 28, 2020 and
April 8, 2021, accepted in May 13, 2021. This article was recommended by
Associate Editor Subhasish Mitra. (Corresponding author: Akash Kumar)Behnaz
Ranjbar and Ali Hosseinghorban are with the Chair for Processor Design, CFAED,
Technische Universität Dresden, 01062 Dresden, Germany, and also with the
Department of Computer Engineering, Sharif University of Technology, Tehran
11365-11155, Iran. e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>Salehi is with the Department
of Computer Engineering, University of Guilan, Rasht, Iran. e-mail:
<EMAIL_ADDRESS>Ejlali is with the Department of Computer
Engineering, Sharif University of Technology, Tehran 11365-11155, Iran.
e-mail<EMAIL_ADDRESS>Kumar is with the Chair for Processor Design,
CFAED, Technische Universität Dresden, 01062 Dresden, Germany. e-mail:
<EMAIL_ADDRESS>Object Identifier: 10.1109/TCAD.2021.3082495

###### Abstract

Mixed-Criticality (MC) systems have recently been devised to address the
requirements of real-time systems in industrial applications, where the system
runs tasks with different criticality levels on a single platform. In some
workloads, a high-critically task might overrun and overload the system, or a
fault can occur during the execution. However, these systems must be fault-
tolerant and guarantee the correct execution of all high-criticality tasks by
their deadlines to avoid catastrophic consequences, in any situation.
Furthermore, in these MC systems, the peak power consumption of the system may
increase, especially in an overload situation and exceed the processor Thermal
Design Power (TDP) constraint. This may cause generating heat beyond the
cooling capacity, resulting the system stop to avoid excessive heat and
halting the processor. In this paper, we propose a technique for dependent
dual-criticality tasks in fault-tolerant multi-core MC systems to manage peak
power consumption and temperature. The technique develops a tree of possible
task mapping and scheduling at design-time to cover all possible scenarios and
reduce the low-criticality task drop rate in the high-criticality mode. At
run-time, the system exploits the tree to select a proper schedule according
to fault occurrences and criticality mode changes. Experimental results show
that the average task schedulability is 74.14% on average for the proposed
method, while the peak power consumption and maximum temperature are improved
by 16.65% and 14.9∘C on average, respectively, compared to a recent work. In
addition, for a real-life application, our method reduces the peak power and
maximum temperature by up to 20.06% and 5∘C, respectively, compared to a
state-of-the-art approach.

###### Index Terms:

Mixed-Criticality, Multi-Core Platforms, Peak Power Management, Scheduling,
Fault-Tolerance.

##  I Introduction

Recently, multi-core real-time embedded systems where industrial applications
with real-time constraints are executed, becomes significant. These systems
are responsible for executing an application with a set of High-Criticality
(HC) and Low-Criticality (LC) tasks on a single platform [1, 2, 3]. For
instance, aerospace applications have flight-critical tasks that must be
executed before the deadline and mission-oriented tasks that are important,
but they could be dropped in critical situations [2]. These systems are called
Mixed-Criticality (MC) systems.

In order to map and schedule these MC tasks on multi-core platforms, the
Worst-Case Execution Time (WCET) of each task is exploited to guarantee the
correct execution of all tasks, especially HC tasks, in any situation.
However, the WCET of a task is pessimistic, and the probability that the
execution time of the task will be as large as WCET is very low [4].
Therefore, most of the time, the system processing capacity is wasted because
the execution time of tasks is less than the pessimistic WCETs. To this end,
MC systems consider two or multiple WCETs for HC tasks [1, 5, 4], which are
calculated using different WCET-determination methodologies and tools (e.g.,
calculating pessimistic or optimistic WCET values). In this paper, we consider
a dual-criticality system where each task has a low WCET and a high WCET.

In MC systems, if an HC task overruns (the task’s execution time exceeds the
low WCET), the system switches to a high-criticality mode (HI mode). In this
mode, the system considers the high WCET for all the remaining tasks to
guarantee the safety of the system, and it stays in this mode until there is
no HC task in the ready queue of each core [1, 2, 3]. In this situation, the
execution of all LC and HC tasks requires higher computational demands, which
may exceed the processor’s capacity, and the system becomes overloaded [6].
Thus, all cores may execute tasks simultaneously to meet deadlines of tasks,
which increase the instantaneous processor power beyond its Thermal Design
Power (TDP) constraint [7, 8, 9].

TDP is the maximum sustainable power that a chip can dissipate safely. The
chip’s power consumption is the sum of power consumption of all cores
regardless of which kind of tasks (LC or HC) they are executing. So, even
underestimating the power consumption of an LC task might violate the TDP
constraint which generates a large amount of heat that is higher than the
cooling capacity of the chip. Thus, it may stop or restart the system by an
integrated Dynamic Thermal Management (DTM) unit [8]. Consequently, the
deadlines of HC tasks are missed, which leads to catastrophic damages.
Therefore, it is necessary to consider pessimistic power consumption value for
all tasks with any criticality level. Note that, minimizing only the average
power consumption is not sufficient. Although it may decrease the
instantaneous power, there is no guarantee that the TDP is not violated [8].

In addition to meeting deadlines in case of tasks overrun, MC systems must use
fault-tolerance techniques like task re-execution or duplication [10] to
guarantee correct functionality when tasks are affected by transient faults
[2, 11]. It should be mentioned that it is possible that the system faces both
task overrun and one or multiple transient faults in one run. So, the system
must be designed carefully to execute all HC tasks correctly before their
deadlines, even in worst-case situations.

Previous works have proposed methods to schedule MC tasks in both low-
criticality mode (LO mode) and HI mode; however, most of them have considered
independent periodic MC tasks. These methods are not suitable for MC tasks
with precedence constraints. Besides, some research works have proposed
methods to reduce average power consumption in MC systems [12, 13, 14, 15, 16,
17]. These works use the Dynamic Voltage and Frequency Scaling (DVFS)
technique [18] along with dropping LC tasks in the HI mode to manage average
power consumption; however, none of them has considered managing peak power
consumption. It is noteworthy to mention that some low-power techniques like
DVFS, cannot be easily used in the HI mode, specially in the overload
situations [12, 13, 14], because changing the voltage and frequency levels of
cores imposes high switching time overhead [7] that may cause deadline
violation of HC tasks and also degrade the reliability level of tasks. On the
other hand, some studies addressed peak power management in hard real-time
systems with only one criticality level; therefore, they are not suitable for
MC systems [7, 8, 9]. Table I presents a comparison between the state-of-the-
art approaches which we discuss in detail in Section II.

In this paper, we consider fault-tolerant MC multi-core embedded systems with
low and high criticality tasks. The proposed method manages peak power and
temperature to prevent hot spots in homogeneous multi-core platforms. The task
set is characterized by a directed acyclic graph (DAG) [19], and faults are
tolerated through task re-execution. Since tasks can overrun and a fault can
occur at any time but occasionally, using a single task’s mapping and
scheduling to guarantee the correct and on-time execution of all HC tasks
without TDP violation leads to inefficient utilization of resources.

To this end, we propose a method that exploits a tree of schedules for
dependent dual-criticality tasks. The proposed technique generates a tree of
schedules off-line (at design-time) considering all possibility of fault
occurrence scenarios in different tasks (including both LC and HC tasks) and
HC task overrun. At run-time, when an HC task overruns or a fault occurs in an
LC or HC task, the scheduler chooses the proper schedule from the tree to
tolerate the faults or manage the system mode switches with low overheads.
Moreover, typical MC systems drop or degrade most of the LC tasks in the HI
mode to guarantee the execution of all HC tasks. Therefore, another goal of
our technique is to improve the LC tasks’ QoS (Quality of Service, the
percentage of executed LC tasks to all LC tasks [20, 2]) in the HI mode while
all HC tasks meet their deadlines. As a result, by generating the schedule
tree and exploiting it at run-time, the LC tasks’ QoS is maximized, while the
peak power consumption of the system is managed and also the occurrence of
possible faults is tolerated.

Contributions: To the best of our knowledge, this paper is the first work to
study the scheduling problem for fault-tolerant MC systems with peak power and
thermal consideration. The main contributions of this paper are:

  * •

Proposing a tree generation approach for mixed-criticality systems, based on
the all possibility of fault occurrence scenarios and criticality mode
changes.

  * •

Peak power-aware task mapping and scheduling in multi-core mixed-criticality
systems for both LO and HI modes.

  * •

Offline QoS-Aware task mapping and scheduling to guarantee the correct
execution of most LC tasks in the HI mode.

  * •

Reducing the run-time timing overheads by generating all schedules at design
time and exploiting them at run-time.

To evaluate our proposed method, we obtain the peak power consumption of tasks
by running the benchmarks on the ARM Cortex-A7 core of the ODROID XU3
platform. Then, with the help of the platform’s extracted information, we
evaluate our method and state-of-the-art methods using HOTSPOT [21] simulator.
The experiments show that our scheme can schedule 74.14% of task sets on
average (43.04% more, compared to [22]), in which the TDP constraint and all
deadlines are met, while the system can tolerate occurrence of up to a certain
number of faults (four in our experiments). For a real task graph, our method
reduces the peak power and maximum temperature by up to 20.06% and 5∘C
respectively, compared to the approach of [22], while the QoS is improved
9.09%. On the other hand, although our method increases the maximum
temperature by 9.61%, compared to [23], we reduce the peak power by 6.31% and
improve the QoS by 81.82%.

The rest of the paper is organized as follows. In Section II, we review
related works. In Section III, we introduce models, assumptions and define the
problem. The motivational example is presented in Section IV and then we
describe our method in detail. Finally, we analyze the experiments and
conclude the paper in Sections V and VI, respectively.

##  II Related Work

Table I: Summary of state-of-the-art approaches

# TDP Manag. Avg. Power Temp. Fault-Tolerance MC Tasks DAG Model LC tasks’ QoS
1 Socci’15[23], Socci’19[24], Baruah’16[19], Medina’17[25] $\times$ $\times$
$\times$ $\times$ $\checkmark$ $\checkmark$ $\times$ 2 Li’16[26],
Pathan’18[27] $\times$ $\times$ $\times$ $\times$ $\checkmark$ $\checkmark$
$\checkmark$ 3 Medina’18[22, 28], Choi’18[29], Bolchini’13[30] $\times$
$\times$ $\times$ $\checkmark$ $\checkmark$ $\checkmark$ $\checkmark$ 4
Huang’14[12], Li’14[13], Ali’15[14], Narayana’16[15], Taherin’18 [16],
Awan’16[17] $\times$ $\checkmark$ $\times$ $\times$ $\checkmark$ $\times$
$\times$ 5 Lee’14[7], Munawar’14 [8] $\checkmark$ $\times$ $\times$ $\times$
$\times$ $\times$ - 6 Lee’10 [9] $\checkmark$ $\times$ $\times$ $\times$
$\times$ $\checkmark$ - 7 Ansari’19 [31] $\checkmark$ $\checkmark$ $\times$
$\times$ $\times$ $\checkmark$ - 8 Li’19 [32] $\times$ $\checkmark$
$\checkmark$ $\times$ $\checkmark$ $\times$ $\times$ 9 Ranjbar’19 [33],
Ranjbar’20 [5] $\times$ $\checkmark$ $\checkmark$ $\times$ $\checkmark$
$\checkmark$ $\checkmark$ 10 Our Work $\checkmark$ $\times$ $\checkmark$
$\checkmark$ $\checkmark$ $\checkmark$ $\checkmark$

MC systems are the subject of recent research due to the emergence of the
Cyber Physical System (CPS). Table I summarizes the recent studies with
different target optimization objectives. Since our focus is on power
management and fault-tolerance for dependent MC tasks, we only consider the
works presented for MC or non-MC systems with a similar scope. There are some
algorithms presented for independent tasks such as Earliest Deadline First
with Virtual Deadline (EDF-VD) used in [2], or using different scheduling
policies for different criticality levels [6]. Hence, these algorithms are
presented for independent periodic tasks and cannot be applied to the tasks
with precedence constraints.Besides, as can be seen, some papers, such as [19,
23, 24, 25, 26, 27, 33], have considered periodic MC tasks with data
dependency but none of them have considered fault occurrence possibilities and
power management. Rows 1 and 2 show that the papers in this area have focused
on the feasibility of schedules and meeting the timing constraints without
considering power consumption or fault-tolerance. From the perspective of
guaranteeing LC tasks’ minimum service level, most existing MC scheduling
algorithms (row 1) discard or degrade LC tasks when the system switches to the
HI mode. It causes serious service interruption for LC tasks. Therefore, in
addition to power management and fault-tolerance in MC systems, improving the
QoS of LC tasks would be significant. In addition, the used MC task model in
[26] is different from the popular dependent MC task model by defining a
criticality level for each task graph, not for each task in a graph. On the
other hand, there are a few works (row 3) that proposed a method to schedule
dependent MC tasks in multi-core systems [22, 28]. These papers have
considered fault occurrence possibilities, while they have not considered
power or hotspot management. In terms of fault tolerance, researchers in [34]
have proposed a design-time task re-mapping approach to tolerate faults,
however, these techniques have not considered power management.

Research works have recently been presented on energy and power management in
multi-core MC systems by considering periodic independent tasks (row 4). Most
of these papers use DVFS technique to manage power consumption in the LO mode,
and when the system enters into the HI mode, all HC tasks are executed with
the high frequency, and also all of the LC tasks are dropped. Indeed, they
interrupt the minimum service level of LC tasks in the HI mode. In addition,
due to the high frequency in the HI mode, the system’s peak power consumption
may violate the TDP constraint. None of these papers that studied MC systems
managed instantaneous power, especially when the system switches to the HI
mode. Besides, researchers in [35, 36] have proposed a design-time task
remapping approach to minimize the average power and tolerate faults; however,
in addition to not managing the peak power in this method, it is not suitable
for MC systems. On the other hand, some papers focused on peak power
management of multi-core real-time systems (5-7). These works have proposed
hard real-time tasks with one criticality level which is not practical for MC
tasks. Although the authors in [31] manage the peak power for the dependent
task model, they use DVFS to manage the peak power consumption. Hence, it is
not suitable for MC tasks, especially in the HI mode.

From the MC systems’ thermal management perspective, researchers in [32] have
considered thermal management for independent MC tasks in single-core
processors (row 8). Besides, researchers in [33, 5] reduce the peak power and
manage the temperature in MC systems with the dependent task model (row 9).
these papers use the DVFS technique, which is not acceptable, especially in
the HI mode, and also, they have not considered fault occurrence. There is
also no guarantee to manage peak power under TDP in their methods.

In this work, we study peak power and thermal management for MC multi-core
systems by considering fault-tolerance techniques, which is not considered in
existing MC works.

##  III System Models and Problem Definition

###  III-A Mixed-Criticality Task Model

The MC system is responsible for executing application A consisting of
multiple dependent periodic tasks. Analogous to [19, 22, 28, 5], the
application is modeled as a directed acyclic graph $\textit{G}_{A}$
($\textit{V}_{A},\textit{E}_{A}$) in which each task in the application is
either a HC or a LC task. Each node $\textit{T}_{i}\in\textit{V}_{A}$
represents a task and an edge $\textit{e}_{ij}\in\textit{E}_{A}$ from
$\textit{T}_{i}$ to $\textit{T}_{j}$ indicates a dependency between
$\textit{T}_{i}$ and $\textit{T}_{j}$. A task is released and ready to be
executed if all its predecessor tasks have finished their execution. We assume
preemptive execution for tasks, which means the tasks are interrupted during
their execution on a core that mapped on it. Each task $\textit{T}_{i}$ is
defined as:

$\displaystyle\textit{T}_{i}$
$\displaystyle=(\zeta_{i},\textit{C}_{i}^{LO},\textit{C}_{i}^{HI},\textit{d}_{i},\textit{P}_{i})$
(1)

Parameter $\zeta_{i}$ denotes levels of criticality for each task (HC or LC).
Each task has a deadline ($\textit{d}_{i}$), low WCET ($\textit{C}_{i}^{LO}$),
and high WCET ($\textit{C}_{i}^{HI}$). For each LC task, $\textit{C}_{i}^{LO}$
is equal to $\textit{C}_{i}^{HI}$, and for each HC task, $\textit{C}_{i}^{LO}$
is less than $\textit{C}_{i}^{HI}$. The communication time between tasks is
considered as a part of the predecessor task’s execution time. All tasks in
application A have an identical period ($\textit{P}_{i}$), which is equal to
the period of the application ($\textit{P}_{A}$) [37, 33]. Also, we assumed
the deadline and period of the task graph are equal for an application
($\textit{d}_{A}=\textit{P}_{A}$). A deadline $d_{i}$ is determined for each
task in order that all its successors can be scheduled before their deadlines.
Hence, the deadlines of tasks that have no successors are equal to the task
graph’s deadline.

MC system’s operational model: MC systems first start the operation in the LO
mode; if the execution time of at least one HC task exceeds its low WCET
($\textit{C}_{i}^{LO}$), the system switches to the HI mode. It stays in this
mode until there is no ready HC task in each core’s queue [19, 22, 28, 33]. In
the LO mode, the mapping and scheduling algorithms consider the low WCET of
tasks while in the HI mode, the algorithm schedules tasks by their high WCETs.

The task graph model is popular for image processing in automotive systems and
pedestrian detection [38]. System designers assign the criticality level of
tasks based on their functionalities. However, similar to previous studies in
the literature [19, 22], if an LC task is a predecessor of an HC task, then it
is considered as an HC task. Fig. 1 shows the task graph of Unmanned Air
Vehicle (UAV), which is a real-life MC application task graph [22]. This
application is composed of eight tasks. Tasks $\textit{T}_{1}$ to
$\textit{T}_{3}$ are HC tasks that are responsible for the avoidance,
navigation, and stability of the system. Failure in the execution of these
tasks before their deadline may lead to a system failure, and irreparable
damage to the system. The roles of LC tasks ($\textit{T}_{4}$ to
$\textit{T}_{8}$), are recording sensors data, GPS coordination, and video
transmissions [22]. The system should execute these tasks to improve its QoS;
however, the system can skip executing them in harsh situations. Note that,
the QoS is defined as the percentage of executed LC tasks in the HI mode to
all LC tasks [20, 2] ($QoS=n_{L}^{succ}/n_{L}$, where $n_{L}$ is the number of
all LC tasks in a graph and $n_{L}^{succ}$ is the number of executed LC tasks
that, when the system switches to the HI mode and $Finish-time_{i}\leq
d_{i}\And\zeta_{i}=LC$). Dropping some LC tasks in the HI mode can be used for
real-time applications characterized by hard and firm deadlines. The tasks
with a hard deadline can be HC tasks, and with firm deadlines can be LC tasks.
The multimedia tasks are an example of firm deadlines, where skipping a video
frame once in a while is better than processing it with a long delay or not
processing it completely [39].

Figure 1: An example of real-life application task graph (Unmanned Air
Vehicle)

###  III-B Fault-Tolerance Model

Transient faults are the most common faults in embedded systems [13, 2, 11].
To tolerate transient faults, fault detection and correction mechanisms need
to be applied. The detail of these mechanisms is discussed in Appendix A.

For embedded safety-critical real-time systems, low-cost, low power, and high
accuracy checker should be employed in each core. To check whether a fault
occurs during the execution of a task, analogous to [37, 31, 2], an error
detection mechanism, is conducted to check the correctness of the task’s
output at the end of the task’s execution. ARGUS [40] is one of the
significant checker tools to detect errors, that has all the features and has
been used in many recent works [41]. It can be applied to any embedded systems
with less than 11% chip area overhead and also check control flow, dataflow,
computation, and memory access separately, at run-time. Here, the error
detection time overhead is considered in the WCET of tasks. Besides, the task
re-execution technique is one of the most popular ways to correct transient
faults in embedded systems [2, 10], which we employed in this article. We
assume that up to k transient faults may occur in one period of the
application [42, 38, 43]. If the system detects a faulty task, it spends some
time ($\mu$) to discard the results of the faulty task before re-executing the
task.

###  III-C Power Model

The total power consumption of a core in an embedded system consists of three
major components, Dynamic power ($P_{d}$), static power ($P_{s}$), and
frequency-independent power ($P_{ind}$) [16, 33]. We consider a pessimistic
approach to obtain the dynamic power consumption of HC tasks as well as LC
tasks. $P_{d}$ is a frequency and workload dependent power which is consumed
when a task is run. $P_{s}$ is consumed in a core even when the core is in
idle mode and no task is run. The frequency-independent power is the power
used for memory and I/O operations [16, 13]. The total power is:

$\begin{split}P(V_{i},f_{i})&=P_{d}+P_{s}+P_{ind}=\alpha
C_{eff}V_{i}^{2}f_{i}+I_{sub}V_{i}+P_{ind}\end{split}$ (2)

where $\alpha$, $I_{sub}$, $C_{eff}$, $f_{i}$, and $V_{i}$ are transition
rate, sub-threshold leakage current, effective capacitance, core $i$
processing frequency, and core $i$ supply voltage, respectively.

###  III-D Problem Definition

Deadline Constraint: Each HC task $\tau_{i}$, must finish its execution
($ft_{i}$) correctly before its deadline ($d_{i}$) in both LO and HI modes. In
addition, all LC tasks should finish their execution before their deadlines in
the LO mode.

$\displaystyle\forall\tau_{i},$ $\displaystyle\leavevmode\nobreak\
\zeta_{i}=HC:ft_{i}\leq d_{i}$ $\displaystyle\forall\tau_{i},$
$\displaystyle\leavevmode\nobreak\ \zeta_{i}=LC\textbf{ and
}Cr_{L}=LO:ft_{i}\leq d_{i}$ (3)

Task Dependability Constraint: Due to the precedence correlations between
tasks, the start time of task $\tau_{i}$ ($st_{i}$) must be greater than the
finish time of all its predecessor tasks ($Pred(\tau_{i})$).

$\displaystyle\forall\tau_{i},\forall j\in Pred(\tau_{i})\implies st_{i}\geq
ft_{j}$ (4)

Mapping Constraint: A task ($\tau_{i}$) can only be executed on a single core
in each time slot. If $X_{ij}$ denotes the mapping of task $\tau_{i}$ on core
$j$, then:

$\displaystyle\forall\tau_{i},\sum_{j\in Cores}{X_{ij}}=1$ (5)

Table II: All possible scenarios of executing the task graph presented in Fig.
2 on a single core chip

| $S_{1}$ | $S_{2}$ | $S_{3}$ | $S_{4}$ | $S_{5}$ | $S_{6}$ | $S_{7}$ | $S_{8}$ | $S_{9}$ | $S_{10}$ | $S_{11}$ | $S_{12}$ | $S_{13}$ | $S_{14}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Overrun | - | - | - | - | $T_{1}$ | $T_{2}$ |  $T_{1}$* \raisebox{-.9pt} {1}⃝ |  $T_{1}$\raisebox{-.9pt} {1}⃝ |  $T_{1}$\raisebox{-.9pt} {1}⃝ |  $T_{2}$\raisebox{-.9pt} {1}⃝ |  $T_{2}$\raisebox{-.9pt} {1}⃝ |  $T_{1}$\raisebox{-.9pt} {2}⃝ |  $T_{2}$\raisebox{-.9pt} {2}⃝ |  $T_{2}$\raisebox{-.9pt} {2}⃝
Fault | - | $T_{1}$ | $T_{2}$ | $T_{3}$ | - | - |  $T_{1}$\raisebox{-.9pt} {2}⃝ |  $T_{2}$\raisebox{-.9pt} {2}⃝ |  $T_{3}$\raisebox{-.9pt} {2}⃝ |  $T_{2}$\raisebox{-.9pt} {2}⃝ |  $T_{3}$\raisebox{-.9pt} {2}⃝ |  $T_{1}$\raisebox{-.9pt} {1}⃝ |  $T_{1}$\raisebox{-.9pt} {1}⃝ |  $T_{2}$\raisebox{-.9pt} {1}⃝
Finish time | 9 | 14 | 13 | 12 | 13 | 11 | 20*** | 19*** | 16 | 17 | 12 | 18 | 16 | 15
Exe time (drop $T_{3}$) | 7 | 12 | 11 | 10** | 11 | 9 | 18 | 17 | 14** | 15 | 10** | 16 | 14 | 13

  * *

The circles shows the order of the occurrence of fault and task overrun.

  * **

In these cases, the system executes $T_{3}$ and detects a fault occurs, but
does not re-execute the task (drops the task).

  * ***

In these cases, the system must drop task $T_{3}$ to execute all HC tasks
before their deadlines.

Power Constraint: The chip’s overall power consumption must not violate the
chip’s TDP ($TDP_{chip}$) in any time slot.

$\displaystyle\forall t\in timeslots:\sum_{j\in Cores}{Pow_{jt}}\leq
TDP_{chip},$ (6)

where $Pow_{jt}$ represents the power consumption of core $j$ in time slot
$t$.

When the system switches to the HI mode, the system drops some LC tasks to
meet the timing constraints, which degrades the QoS of the system:

$\displaystyle Cr_{L}=HI:\quad QoS=n_{L}^{succ}/n_{L}$ (7)

The problem is how to map and schedule dependent MC tasks of application A on
the system’s cores to satisfy the aforementioned constraints (timing and peak
power) and QoS of the system. In this paper, we propose a heuristic method to
solve this NP-hard problem [8].

##  IV PROPOSED METHOD

In this section, at first, a motivational example is presented in Section IV-A
for a better understanding of the problem and the proposed solution. Then, the
proposed method is explained in detail in Section IV-B and IV-C.

###  IV-A Motivational Example

Fig. 2 shows an application with three tasks, where tasks ${T}_{1}$ and
${T}_{2}$ have HC, and task ${T}_{3}$ has LC. Deadline, low WCET, and high
WCET of each task are presented in the figure, and the system takes 1ms to
discard the output of a faulty task ($\mu=1$). Hence, the period of all tasks
are the same and is equal to 18ms. For the sake of simplicity, we considered
that the application runs on a single-core processor, and up to one fault may
occur during the execution of the application ($k=1$). So, the system cannot
execute multiple tasks simultaneously on different cores to violate TDP (we
will discuss TDP challenge later). The scheduling algorithm in the LO mode,
executes tasks $T_{1}$, $T_{2}$, and $T_{3}$, respectively. The schedulability
test [19] shows that in the LO mode, all three tasks can be executed even in
the case of fault occurrence. In other words, the total CPU utilization for
application $A$ is less than one $(U_{A}\leq 1)$. If we consider the HI mode,
if a LC task $T_{3}$ is executed in addition to the two HC tasks in the case
of fault occurrence, the system becomes overloaded ($U_{A}^{HI}$>1) and the
three tasks cannot be scheduled. However, if we drop some LC tasks in the HI
mode ($T_{3}$ in this example) to guarantee the correct execution of HC tasks,
then the computation demand requested by tasks is less than one and can be
scheduled before their deadline. As a result, the utilization of this example
for both LO and HI modes with the probability of one fault occurrence is
computed as follows, in which, just LC tasks are considered to be executed in
the HI mode.

$\displaystyle\begin{split}U_{A}&=MAX(U_{A}^{LO},U_{A}^{HI})\leq 1\\\
U_{A}^{LO}&=(\sum_{i\in\\{1,2,3\\}}\frac{C_{i}^{LO}}{P_{A}})+\frac{k(\max_{i\in\\{1,2,3\\}}(C_{i}^{LO})+\mu)}{P_{A}}\\\
&=\frac{4}{18}+\frac{3}{18}+\frac{2}{18}+(\frac{4+1}{18})=\frac{14}{18}<1\\\
U_{A}^{HI}&=(\sum_{i\in\\{1,2\\}}\frac{C_{i}^{HI}}{P_{A}})+\frac{k(\max_{i\in\\{1,2\\}}(C_{i}^{HI})+\mu)}{P_{A}}\\\
&=\frac{6}{18}+\frac{5}{18}+(\frac{6+1}{18})=\frac{18}{18}\leq 1\end{split}$
(8)

However, for this example, fourteen different scenarios could happen during
the execution of the application because the time of the fault and task
overruns are unknown. Table II shows all these scenarios, and the execution
time of the system whether it drops LC task or not. In ten scenarios ($S_{5}$
to $S_{14}$), an HC task overruns, and it shows the system is in the HI mode.
However, as shown in Table II, only in two scenarios, the system fails to
execute all tasks (HC and LC tasks) before the deadline ($S_{7}$ and $S_{8}$).
The reason is that, the system has switched to the HI mode in these scenarios
and also a fault has occurred. it causes the system to be overloaded and the
computation demand for executing all tasks becomes more than one ($U_{A}>1$).
Therefore, the LC task $T_{3}$ would be dropped. Although there are some
scenarios such as $S_{12}$ to $S_{14}$, that the system is in the HI mode, we
schedule the LC task in this mode to improve the QoS. As shown in Table II,
the start time of $T_{3}$ in $S_{12}$ ($S_{14}$) is 16 (13), and since the
WCET of the LC task is 2, then it can be executed before the application
deadline ($d_{A}=18$). This example clearly shows that all situations should
be considered in an MC system. Therefore, the system is analyzed in detail at
design-time, and then, the proper schedule is exploited in the online phase to
minimize the drop ratio of LC tasks and enhance the QoS.

Figure 2: Task graph of an application with three tasks used in the example
Figure 3: The tree constructed by our method for the task graph of Fig. 2

Fig. 3 shows the tree for the application task graph presented in the
motivational example, which is constructed in the offline phase of our
proposed approach. At run-time, the system starts each period with $S_{1}$
(the scheduling in the root of the tree), which corresponds to the scenario
where no fault occurs and no HC tasks overruns. If an HC task overruns (for
instance task $T_{1}$), The system searches through the children of the
current node ($S_{1}$), finds the appropriate task mapping and scheduling, and
continues the execution based on the new schedule ($S_{6}$ in this case).
After that, if error detection unit detects a fault at the end of a task
execution (for instance task $T_{2}$), the system searches through the
children of the current node ($S_{6}$), finds the appropriate scenario, and
continues the execution based on the new task mapping and scheduling ($S_{14}$
in this case).

It is important to mention that each schedule has a different start time,
system mode, the expected number of faults, and task set. Furthermore,
scheduling of child nodes must be compatible with the scheduling of their
parent; so, the system can change the schedule of tasks without any conflicts.
For instance, assume that in $S_{1}$, the task execution order is $T_{1}$,
$T_{2}$, and $T_{3}$. When the system employed $S_{4}$, it implies that
$T_{1}$ and $T_{2}$ are completed successfully, the system is in the LO mode,
and a fault is detected at the end of the first execution of $T_{3}$. So, the
$S_{4}$ should schedule tasks based on this information.

###  IV-B Design Methodology

The fault-tolerance and peak power-aware task mapping and scheduling method
consists of two phases, design-time, and run-time. In this paper, we focus on
system design at design-time. For the sake of completeness, we provide a brief
overview of how to use the schedule tree in the run-time phase, which is
generated at design-time. Fig. 4 shows an overview of the design methodology.
In the design-time phase, there are three functions which are used to generate
the schedule tree, MakeTreeRec, Schedule, and MapSch. Section IV-C provides
details of generating the tree, these functions, and how we manage the peak
power consumption. All scenarios are stored in memory to be used in the run-
time phase. At run-time, an application follows the presented task mapping and
scheduling in the root of the tree. In the case of fault occurrence or mode
switching, the appropriate task mapping and scheduling for the remaining un-
executed tasks are fetched from memory. After fetching, mapped tasks based on
the previous scenario are re-mapped based on the new scenario, and the system
continues its operation. In the following subsection, we explain the design-
time phase of our proposed method.

###  IV-C Tree Generation and Fault-Tolerant Scheduling & Mapping

As we discussed, multiple scenarios might happen during the execution of an
instance of the application, where, in most of these scenarios, the system can
execute all or most of LC tasks without violating HC tasks’ deadline. To this
end, the proposed approach of this paper considers a different mapping and
scheduling for each scenario to handle HC tasks deadlines, faults, and peak
power violations while minimizing the number of dropped LC tasks in the HI
mode. In the run-time phase, in general, the system is unaware of tasks that
might overrun or a fault occurs; so, the system cannot select the proper
schedule in advance. Therefore, this paper employs a tree data structure in
the offline phase to organize the mapping and scheduling of tasks for all
scenarios, corresponding to each HC task overrunning, and/or up to $k$ faults
occurrence during each period. Now, we explain how the scheduling tree is
generated.

Figure 4: Design methodology

####  IV-C1 Making Scheduling Tree

The main function of creating the tree ($\Phi$) is outlined in Algorithm 1. At
first, we define a priority queue called TaskPQ (line 3), which considers
tasks’ release time as the priority. The release time of a task is the time
when all its predecessor tasks have finished their execution (presented in
Section subsec:mixedCriticalityTaskModel). Then, the algorithm enqueues all
tasks without any predecessor to the TaskPQ with key equal to 0; because they
are released at the beginning of the period (line 4). Each node of the tree
represents a particular scenario, and it has two attributes called sch and
childs. For instance, in the root scenario, the system is in the LO mode, and
no fault occurs in the entire period. sch is the proper mapping and scheduling
of tasks for that scenario, and childs is a list of children nodes of the
current node.

Algorithm 1 Creating the Tree

1:Task Graph ($G_{T}$), List of Cores ($c$), Number of Faults ($k$).

2:Scheduling Tree ($\Phi$).

3:procedure MakeTreeMain

4: $\Phi\leftarrow$ Empty Tree

5: TaskPQ $\leftarrow$ Empty Priority Queue

6: Add all tasks without predecessor node to TaskPQ with key $0$

7: $\Phi[root].sch\leftarrow MapSch(G_{T},c,0,\varnothing,TaskPQ)$

8: if $\Phi[root].sch$=un-scheduled then

9: return $\varnothing$

10: end if

11: $\Phi[root].childs\leftarrow MakeTreeRec(G_{T},c,$
$\Phi[root].sch,0,k,LO)$

12: if $\Phi[root].childs$=un-scheduled then

13: return un-scheduled

14: end if

15: return $\Phi$

16:end procedure

17:function MakeTreeRec(Task Graph ($G_{T}$), List of Cores ($c$), Parent
Schedule($Sch$), Time ($T$), Number of Faults ($k$), Mode of the System
($Mode$))

18: SchList $\leftarrow$ Empty list of nodes

19: if Mode = LO then // HChild nodes

20: Tasks $\leftarrow$ List of unfinished HC tasks in time T.

21: $G_{H}\leftarrow$ $G_{T}$ With High WCET.

22: for each $\tau$ in Tasks do

23: $T_{tmp}\leftarrow$ Finish time of $\tau$ in sch \+ $T_{sw}$.

24: S $\leftarrow$ New node

25: S.sch = Schedules ($G_{H}$, c, $T_{tmp}$, sch, TaskPQ)

26: if S.sch = un-scheduled then

27: return $\varnothing$.

28: end if

29: $S.childs\leftarrow MKTreeRec(G_{H},c,S,T_{tmp},k,HI)$

30: if $S.childs=\varnothing$ then

31: return $\varnothing$.

32: end if

33: Add $S$ to $SchList$

34: end for

35: end if

36: if k $>$ 0 then

37: Tasks $\leftarrow$ List of Unfinished Tasks in T.

38: for each $\tau$ in Tasks do

39: $T_{tmp}\leftarrow$ Finish Time of $\tau_{i}$ in sch.

40: S.sch = Schedules($G_{T}$, sch, Time)

41: if S.sch = un-scheduled then

42: return un-scheduled.

43: end if

44: $S.childs\leftarrow MKTreeRec(G_{T},c,S,T_{tmp},k-1,Mode)$

45: if $S.childs=\varnothing$ then

46: return $\varnothing$.

47: end if

48: Add $S$ to $SchList$

49: end for

50: end if

51: return $SchList$

52:end function

The algorithm calls MapSch function (Algorithm 3, which is discussed later in
Section IV-C2) to schedule task for the root node (line 5). The algorithm
returns un-scheduled, if MapSch function cannot find any feasible schedule
with no task dropping and violating the TDP constraint (lines 6-8). Otherwise,
the algorithm in line 9 continues to create the rest of the tree recursively
by calling MakeTreeRec function (which is presented in lines 15-50 of this
algorithm). If task scheduling is feasible in all possible scenarios,
MakeTreeRec function returns a list of child nodes, and the algorithm returns
the tree ($\Phi$); otherwise, the algorithm returns un-scheduled which means
it could not find a feasible solution (lines 10-13).

The MakeTreeRec function in Algorithm 1 recursively creates the tree. Each
node in the tree might have two types of child nodes. The first type of child
node (HChild) has a scenario similar to their parents, except that one of the
HC tasks overruns. Therefore, if the system is in the LO mode, any unfinished
HC task might overrun and change the system’s mode. To this end, first,
MakeTreeRec function collects all unfinished HC tasks and creates an HC task
graph ($G_{H}$) by changing the WCET of all tasks to high WCET (lines 18-19).
Then, for each unfinished HC task, the function considers the scenario that
the task overruns and schedules the task by calling Schedules function,
presented in Algorithm 2. If the Schedules function finds feasible scheduling,
the algorithm recursively creates a tree for this node, where the system is in
the HI mode, and up $k$ faults may occur on the remaining tasks by calling
MakeTreeRec function (lines 20-32). It is important to mention that switching
to the HI mode has non-zero timing overhead ($T_{sw}$) in realistic systems
[44], but it is insignificant in comparison with tasks’ WCETs (line 21). The
second type of child node (FChild) has a scenario similar to their parents,
except one fault occurs during the execution of one of the remaining tasks. As
we mentioned in Section III-B, the system can tolerate up to $k$ faults in a
period. If less than k faults occur in a node scenario, a faulty execution of
all remaining tasks needs to be considered. Therefore, a child node is
generated for the faulty execution of each remaining task, and also for each
child node, the algorithm recursively constructs a tree by calling MKTreeRec
with k-1 faults (line 34-48). Finally, if the algorithm finds a feasible
solution for all scenarios, it returns the list of child nodes ($SchList$).

Algorithm 2 Schedule Procedure

1:Task Graph ($G_{T}$), List of Cores ($Cores$), Time ($T$), Parent Schedule
($Sch_{par}$), Ready Task Priority Queue ($TaskPQ$).

2:Schedule ($Sch$)

3:procedure Schedules

4: $T_{r}\leftarrow$ List of Tasks from $G$ that all predecessors
has started executing before time T.

5: Add $T_{r}$ Tasks to a Priority Queue (TaskPQ).

6: $Sch\leftarrow Sch_{par}[0-T]$

7: $Sch\leftarrow MapSch(G_{1},Cores,T,Sch,TaskPQ)$

8: if $Sch$ = un-scheduled then

9: Find a LC Task with Largest execution time which has not started
in T and remove it from $G$ then goto line 2.

10: if Cannot find any LC task then

11: return un-scheduled.

12: end if

13: end if

14: return $Sch$

15:end procedure

The Schedule function, schedules tasks for each situation by calling MapSch
function (Algorithm 3). If MapSch function fails to find a feasible solution
to meet the deadlines of all tasks with respect to TDP constraint, Schedules
function drops the largest LC task (in terms of WCET) and calls MapSch
function again. The Schedules function repeats this procedure to find a
feasible schedule. If MapSch function fails to find a feasible solution, and
there is no more LC task to drop, Schedules function returns un-scheduled
(lines 2-12 Algorithm 2). We will discuss the MapSch function in the next
subsection. As we mentioned in this section, occurring faults and a
criticality mode change generate different scheduling scenarios that
correspond to a set of alternative schedules. These scenarios are stored in
the memory of the system as a tree in the offline phase. At run-time, the
system starts with the scheduling in the root node, which is for the scenario
that no fault or overrun happens. After that, if a fault occurs or an HC task
overruns, the system finds the appropriate scenario in the child nodes of the
current node and changes the scheduling of the system to improve the number of
executed LC tasks.

Algorithm 3 Mapping and Scheduling Pseudo Code

1:Task Graph ($G_{T}$), List of Cores ($Cores$), Time ($T$), Scedule up to the
Time ($Sch$), Ready Task Priority Queue ($TaskPQ$).

2:Complete Schedule ($Sch$)

3:procedure MapSch

4: for TS = $T$ to PERIOD do

5: $ReadyTasks\leftarrow\varnothing$

6: Extract minimum element from TaskPQ and add it to ReadyTasks while key of
each element is equal to TS and TaskPQ is not empty;

7: if TaskPQ.empty() = true and ReadyTasks $=\varnothing$ then

8: return $Sch$ // Scheduling is done;

9: end if

10: if ReadyTasks $=\varnothing$ then

11: continue // No new task is ready in this TimeSlot

12: end if

13: SortedTasks $\leftarrow$ Sort (ReadyTasks, Desc);

14: SortedCores $\leftarrow$ Sort (Cores, Asc);

15: for task in SortedTasks do

16: for core in SortedCores do

17: $\textit{Time}_{\textit{tmp}}\leftarrow\textit{task}_{\textit{wcet}}$

18: $count\leftarrow 0$

19: $Sch_{tmp}\leftarrow Sch$

20: $SysPow_{tmp}\leftarrow SysPow$

21: while $Time_{tmp}$ > $0$ do

22: if $Sch_{tmp}(TS$+$count,core)$ is empty &
$SysPow_{tmp}(TS$+$count)$ \+ $task_{pow}$ <= $TDP$ then

23: $Sch_{tmp}(TS+count,core)$ = $task$

24: $SysPow_{tmp}(TS+count)$ += $task_{pow}$

25: $Time_{tmp}$ -= $1$

26: end if

27: $count$ += $1$;

28: end while

29: if $TS$+$count\leq task_{deadline}$ then

30: $Sch\leftarrow Sch_{tmp}$

31: $SysPow\leftarrow SysPow_{tmp}$

32: SortedCores $\leftarrow$ Sort (Cores, Asc);

33: $task_{sch}\leftarrow$ true

34: break

35: end if

36: end for

37: if $task_{sch}$ == false then

38: return un-scheduled

39: end if

40: end for

41: end for

42:end procedure

####  IV-C2 Mapping and Scheduling

In this section, we explain the proposed mapping and scheduling algorithm,
which manages the peak power and hotspot distribution. It should be mentioned
that low power techniques, e.g., DVFS, cannot be easily used in the HI mode,
especially when the system is in the overload situation due to the timing
overhead. Therefore, we manage the peak power by finding the proper mapping
and scheduling of tasks on free time slots of cores. This task mapping and
scheduling are feasible if the system’s power consumption never exceeds the
TDP constraint, and all tasks finish their execution (even in the worst case)
before their deadline. So, MapSch algorithm decides the time and core where
each task should be executed.

Algorithm 3 outlines the pseudo-code of the MapSch algorithm. Tasks are mapped
and scheduled up to time T based on the current node schedule. In the case of
fault occurrence or mode switches at time T, this algorithm maps and schedules
the rest of the tasks based on the new node schedule from time T to the end of
the application period (PERIOD). The time is divided into a set of equal time
slots (TS), and the scheduler will put tasks into cores only at the beginning
of each time slot. In each time slot, at first, the algorithm sets an empty
array for ready tasks, and then it extracts all elements of TaskPQ, where
their key is equal to the current time slot. This means that all predecessor
tasks of these ready tasks have finished their execution. If TaskPQ and
ReadyTasks array are both empty, the algorithm returns the final scheduling
(Sch) because it successfully schedules all tasks. If there is no ready task
to be scheduled in the current time slot (the ReadyTask array is empty, but
the TaskPQ is not empty), the algorithm moves to the next time slot (lines
2-10).

The algorithm sorts the ready tasks in descending order of their energy
consumption (line 11). The energy consumption of each task $\tau_{i}$
($Eng_{i}$) is calculated as follow:

$\displaystyle Eng_{i}=Pow_{i}\times\leavevmode\nobreak\ WCET_{i}$ (9)

where $Pow_{i}$, and $WCET_{i}$ are the maximum power consumption, and the
worst case execution time of task $\tau_{i}$. The maximum power of each task
can be obtained by running benchmarks on a real platform. As mentioned in
Section III-C, the processor power consists of three components; when a task
is run on a processor, the dynamic power is increased significantly compared
to static and independent powers. Hence, in this paper, we don’t model the
power; we measure the processor power when task are run on the real platform.
More information about computing these values is given in Section V-A. The
system’s power consumption must never exceed the TDP constraint to overcome to
overheating problem [31, 8]. To this end, we consider a constant power
consumption for each task at design-time, which is equal to its maximum power
consumption, to guarantee the meeting of TDP constraint in the worst-case
scenario. In addition, energy increment leads to an increase in chip
temperature [12, 5]. Thus, we map a task with more energy consumption to a
core with less temperature. Then, the algorithm sorts the cores in the
ascending order of their accumulated energy (line 12). A core has a higher
priority for task assignment if it has less accumulated energy (i.e., tends to
have a less temperature degree).

(a) An example of MC application

(b) Task scheduling without our policy

(c) Task scheduling with our policy

Figure 5: Two different task scheduling scenarios

After sorting tasks and cores, the algorithm assigns tasks to the cores one by
one (lines 13-38). So, for each task, the algorithm selects a core from the
sorted list and schedules the task on the core’s free slots (lines 19-26). The
system’s instantaneous power consumption must be less than the TDP constraint;
so, we consider an array called $SysPow$, which holds the maximum power
consumption of the system in each time slot. The algorithm checks the $SysPow$
and TDP constraint before scheduling a task on a core (line 20). If the task
is completed before its deadline, the algorithm updates the schedule ($Sch$),
power array ($SysPow$), and scheduling status of the task ($task_{sch}$). It
also sorts the cores again since the energy of one core has changed, and
starts to schedule the next task (lines 27-33). If the task does not meet its
deadline on the core, the algorithm picks the next core and schedule it on
that core. However, if the deadline of one task is violated in all cores, the
algorithm fails to schedule tasks of the application in this scenario and
returns "un-schedulable" (lines 36-37).

The example in Fig. 5 shows an MC application and how our method maps and
schedules the tasks on three cores. Assume the TDP constraint is 1.6 Watt.
Fig. 5b shows that the scheduling without our policy violates the TDP
constraint, while the maximum power consumption of the task scheduling by
considering our policy is below the TDP constraint (Fig. 5c). When the system
completes task $T_{1}$, three tasks ($T_{2}$, $T_{3}$ and $T_{4}$) become
ready to be executed. So, $Eng_{T2}$ > $Eng_{T3}$ = $Eng_{T4}$ that shows
$T_{2}$ should be mapped to the core with less accumulated energy ($E_{c}$).
In addition, as can be computed, $E_{C3}$=$E_{C2}$>$E_{C1}$. Therefore,
according to the criticality level, we first map $T_{2}$ and $T_{3}$ on
$C_{3}$ and $C_{2}$ and schedule them, and thereafter, $T_{4}$ is mapped on
$C_{4}$. This procedure will be the same for mapping and scheduling $T_{5}$
and $T_{6}$.

It should be noted that the time complexity analysis and memory space analysis
of the proposed method have been discussed in Appendix B and C, respectively.

##  V Experiment

###  V-A Experimental Setup

####  V-A1 Application

For the experiments, we used both real-life and random applications to show
our proposed approach’s efficiency. To generate random task graphs, we used
the tool presented by Medina et al. [22]. We generated applications with 30,
40, 50, and 100 tasks (n), where 20% to 50% of them are LC tasks. Another
important parameter in a task graph is edge percentage (d) that shows the
probability of having edges from one task to other tasks. We considered 1% to
20 % edge percentage in the experiments. Another important parameter that will
be discussed in the experiments is the normalized system utilization $U/c$,
where $U$ is the utilization of the system considering the high WCET of each
task, and $c$ is the number of cores. We considered different values of
normalized system utilization in the range of (0,1] with the steps of 0.05. We
also evaluate the proposed approach and other approaches for comparison, with
a real-life application task graph, vehicle cruise controller (CC) [38],
composed of 32 tasks, where 34% of them are LC tasks. In addition, the value
of edge percentage for this CC application is 7%.

####  V-A2 Hardware Platform

To evaluate our approach, we conduct the experiments and run the applications
on a platform with 2, 4, 8, and 16 cores, which models ARM Cortex-A7 cores
(c). The maximum number of transient faults that may occur during each
application period (k) and the recovery overhead $\mu$ are considered three
and 15ms, respectively [42]. It is important to know that if $\lambda$ and
$time$ is the fault rate and application execution time, respectively, the
minimum number of fault occurrence would be $\lambda\times time$. Therefore,
$k$ would not be much smaller or larger than $\lambda\times time$ [45]. If
$\lambda=10^{-6}fault/\mu s$, and $time=10^{3}ms$, then, $\lambda\times
time=1$. As a result, since this fault rate is much higher than real fault
rates, mentioned $10^{-12}fault/\mu s$ in [43], considering $k\leq 3$ is
reasonable fault occurrence number during each application period. We use the
HOTSPOT tool [21] to obtain the cores’ temperature trace by exploiting the
specific floorplan according to a real platform, ODROID XU3 board, which has
four ARM Cortex-A7 cores, and the parameters used in [46]. In addition, we use
the reported value in [44], to consider the timing overhead of mode switching
for ARM Cortex processors. We considered the maximum reported overhead, which
is $T_{sw}=254\mu s$, in our experiments.

####  V-A3 Peak Power Consumption

To determine a realistic power consumption for tasks, we ran several embedded
benchmarks from the MiBench suite, such as automotive, network, and Telecomm.,
on ARM Cortex-A7 core of ODROID XU3 platform with maximum frequency at design-
time. We monitor the power sensors continuously, and we set the worst measured
power as the power consumption of tasks. In addition, we examined different
scenarios of activating one core to all cores by running different benchmarks.
Each benchmark is run 1000 times on a core, and we considered each task’s
power consumption between the minimum and maximum power values obtained from
the platform. The measurement reports show that the power consumption of tasks
is between 483mW to 939mW. In this paper, the TDP value has been considered
85% of the maximum power that a chip can consume, which is used conventionally
in embedded processors [47].

####  V-A4 Comparison

We analyzed our proposed method and compared our experimental results to the
results obtained by recent works that use the task graph model [23, 22, 33].
Socci et al. [23] have proposed an online scheduling algorithm for an MC
system where only HC tasks are executed in the HI mode. Medina et al. [22] has
considered a fault-tolerant MC system that generates two tables at design-time
and uses them at run-time (see Section II for more details). Based on this
work, researchers in [33] have presented an online approach to reduce the peak
power and temperature by using the DVFS technique. Hence, due to the timing
overhead of DVFS and increasing fault rate by changing the V-f levels [10], we
cannot easily use this technique especially in the HI mode.

###  V-B Experimental Results

####  V-B1 Tree Construction Time

At first, we evaluate offline tree construction time by varying the parameters
$n$ and $k$, in Fig. 6. The tree’s construction time is computed on a system
with an intel core-i5 processor with 1.3 GHz clock frequency. Construction
time depends on the number of faults and tasks. Fig. 6a shows the effects of
the number of tasks and the portion of HC tasks in each task set with $k=3$.
Besides, Fig. 6b shows the effects of the number of fault occurrence with
$n=20$. These figures depict that by increasing the number of faults or number
of tasks, the tree generation’s time is increased exponentially. Also, task
sets with higher HC tasks have higher tree construction time. Although the
offline tree construction time is relatively high for large applications, the
online overhead is small and constant for all applications. It is noticeable
that our method can generate each node of a tree in parallel to reduce the
construction time. For example, if we have a system with four cores, the
construction time is about four times faster than a single-core system.

(a) Number of tasks

(b) Number of fault occurrence

Figure 6: Tree construction time for different application sizes and number of
fault occurrence

####  V-B2 Run-Time Timing Overheads

In case of fault occurrence or mode switching, the system finds the proper
schedule by moving to the child of the current node, which is responsible for
the upcoming scenario. Each node of the tree stores two arrays with the size
of $n\times(log^{c}_{2}+log^{\frac{period}{timeslot}}_{2})$ bits, where $c$
and $n$ are the number cores and tasks, respectively. Thus, the switching time
between the schedules consists of moving one level in the tree and retrieving
the correct scheduling from memory, which is constant and negligible. We
measured the schedule changing time at run-time on the ODROID XU3 platform,
considering $c=8$, and $n=50$, it is almost 0.47$\mu$s.

####  V-B3 Peak Power Management and Thermal Distribution for a Real-Life
Application

Fig. 7 shows the system’s power traces of a real-life application, vehicle
Cruise Controller (CC) [38] by our proposed approach, the approaches proposed
by Socci et al. [23], Medina et al. [22], and Ranjbar et al. [33]. Since [33]
is the online approach to minimize the peak power, while exploiting the same
task mapping and scheduling of [22] at design-time, their power traces and
thermal distributions are the same in the worst-case scenario of tasks’
execution time and power consumption. In this part, to focus on the behavior
of systems in the HI mode, we assumed no fault occurred during the
application’s execution. Socci’s approach does not violate TDP constraint
because it drops all LC-tasks when the system switches to the HI mode, which
means it has zero-percent QoS of LC tasks in the HI mode. On the other hand,
methods of [22] and [33] guarantee 90.91% of LC tasks execution in the HI
mode, but it frequently violates the TDP constraint (Fig. 7). For the CC
application, our method endeavored to execute 81.82% of the LC tasks without
violating TDP constraint. Appendix D shows the thermal distribution of CC
application and also, the corresponding results for a random task set with
high utilization.

As a result, our method reduces the peak power and maximum temperature by up
to 20.06% and 3.71% respectively, compared to the approach of [22, 33], while
the QoS is degraded 9.09%. On the other hand, although our method increases
the maximum temperature by 9.61%, compared to [23], we reduce the peak power
consumption by 6.31% and improve the QoS by 81.82%.

Figure 7: Power trace of real-life application graph (CC) in different methods
under worst-case scenario

####  V-B4 Analyzing the QoS of LC Tasks

Figure 8: Task sets’ QoS under different scenarios

(a) Varying Utilization

(b) Varying Number of Tasks

(c) Varying Edge Percentage

(d) Varying Number of Cores

Figure 9: Peak power consumption and maximum temperature in different methods

Now, we analyze the QoS for the proposed method in comparison with methods of
[23, 22, 33] in Fig. 8. In our proposed method, there are many possible
scenarios (each node of the tree is responsible for keeping the scheduling of
system in one scenario), and for each scenario, the LC tasks’ QoS is
different. Thus, we run 100 schedulable task sets on eight cores, and for each
task set, 10 different random situations of occurring faults and mode
switching are considered. For the case when $U/c$=[0.5,0.75) or $U/c$=[0,0.5),
there is more free slack before task set deadline; therefore, in the case of
fault occurrence and mode switching, fewer LC tasks are dropped. In this
experiment, we consider the worst-case scenario of processor demands, $U/c$=
[0.75,1], $n$= 50 and $d$=10% and in the generated task sets, 20% to 50% of
tasks are LC tasks. In addition, the number of fault occurrences in each
scenario is randomly selected in the range of [0,4]. Fig. 8 shows the LC
tasks’ QoS for all these 1000 scenarios. In Section III-A, we have defined the
QoS as the successfully executed LC tasks to all LC tasks. However, we use
three different definitions of QoS to evaluate the methods of [22, 33, 23]
more accurately, as follows.

  * •

Scenario 1: The QoS refers to How many LC tasks are successfully executed
before their deadlines with no TDP violation. If TDP is going to be violated,
running LC tasks are only stopped to reduce the peak power consumption.

  * •

Scenario 2: This scenario has the same definition as Scenario 1, with the
difference that since the HC tasks are the most important, therefore without
them, QoS of LC tasks is penalized by completely being zero. Thus, if TDP is
violated and some HC tasks are running on cores, then the QoS=0.

  * •

Scenario 3: Since those methods have not been specifically designed for peak
power management while meeting the real-time constraints of all HC tasks, we
give the HC tasks higher weighted and then consider the joint QoS, including
both LC and HC tasks. Therefore, the HC tasks have a double weight in this
scenario compared to LC tasks, in the case of dropping tasks due to the TDP
violation.

As shown in Fig. 8, the QoS for methods of [22, 33] in Scenario 1 is higher
than the QoS for our proposed method in total (according to the Cumulative
Distribution Function (CDF) line). However, in this scenario, the TDP
constraint is violated several times due to the execution of HC tasks in
parallel on cores, and there is no policy to manage the peak power. Moreover,
for the second scenario in the methods of [22, 33], the figure shows that in
22.5% of task sets, the TDP constraint is violated while executing some HC
tasks on cores. Besides, the QoS in the second scenario for [23] is zero, due
to dropping all LC tasks in the HI mode. Now, if we investigate the methods of
[22, 33, 23] in the third scenario, the QoS of [22, 33] is more than the QoS
of [23] due to the executing LC tasks in the HI mode. However, they have less
QoS in this scenario compared to our proposed method. According to this
figure, we can conclude that our proposed method is more efficient in
improving QoS than other methods in different scenarios. In addition, the
minimum and maximum QoS in our proposed method are 68.33% and 100%, while the
power constraint is always met.

####  V-B5 Peak Power Consumption and Maximum Temperature Analysis

In this section, we evaluate the system’s peak power consumption and the
chip’s maximum temperature in our approach and methods of [22, 33] by varying
different parameters, such as utilization bound ($U/c$), number of tasks
($n$), edge percentage ($d$), and the number of cores ($c$). Fig. 9 shows the
average normalized peak power consumption to the TDP constraint and maximum
temperature in the worst case that the system switches to the HI mode after
executing the first HC task and all tasks execute up to their higher WCET.
Hence, in the worst-case scenario, [33] has the same power profile and thermal
distribution as [22].

First, we analyze the peak power consumption by varying different parameters.
The figure shows that our proposed approach can manage the peak power
consumption to be less than the TDP constraint in all scenarios, while
Medina’s method violates the TDP constraint almost all scenarios. In general,
the impact of our approach is increased as the probability of using
parallelism in the execution of tasks on cores is increaseed (a large number
of cores (larger c) or less dependency between tasks (lower d)). Since the
number of tasks and utilization are not changed by increasing c, the maximum
power consumption by [22] is also reduced. However, since our proposed method
endeavors to distribute the tasks on all cores to minimize hotspots and also
minimize the instantaneous power consumption, our proposed approach in
decreasing the peak power consumption is more efficient, compared to [22],
while the c is increased. Besides, by reducing the dependency between tasks
(d), although the system peak power consumption is increased and TDP is
violated in [22], our approach always guarantees that the TDP constraint is
not violated. In addition, although increasing the number of tasks or
utilization increases the system’s peak power consumption because the system
does more computation, our approach guarantees that the TDP constraint will
never be violated.

From the perspective of maximum temperature analysis, increasing the system
utilization, illustrated in Fig. 9a, while the number of tasks is fixed ($n$=
50) means that the task’s execution time tends to be longer. Thus, the
computation time of cores is increased, the managing of peak power constraint
and busy/idle times of cores would be difficult, and consequently, the maximum
temperature of the chip is increased in both methods. However, we can decrease
the maximum temperature by up to 22.4∘C in comparison with [22, 33]. Besides,
if we vary the number of tasks in Fig. 9b, since the computation time of cores
does not change, the chip’s maximum temperature is relatively constant by
increasing the number of tasks in both our proposed method and methods of [22,
33]. Additionally, by varying d, the maximum temperature reduces by increasing
the dependency between tasks because the cores’ computation time is constant,
while the idle time of cores is increased. As shown in Fig. 9c, our proposed
method can reduce the maximum temperature by 14.3∘C on average by varying edge
percentage, compared to [22, 33].

(a) Varying Utilization

(b) Varying Number of Tasks

(c) Varying Edge Percentage

(d) Varying Number of Cores

Figure 10: Normalized acceptance ratio under different scenarios in different
methods

Now, we investigate the system’s maximum temperature in Fig. 9d by increasing
the number of cores (c) while other parameters are constant. Hence, the
normalized utilization (U/c is constant in this experiment, it means the
utilization (U) is increased by increasing c. We have more parallelism to
execute tasks by increasing c and add more free slack to let the cores be idle
(having better thermal distribution). However, since each core’s temperature
is a function of its neighbor cores’ temperature, it increases the chip’s
maximum temperature while the system utilization is increased. Therefore, the
results of our proposed method show that the maximum temperature is relatively
constant by increasing c and can decrease it, 10.7∘C on average, compared to
[22, 33]. Since the methods of [22, 33] do not consider the thermal
distribution, the maximum temperature is generally increased by increasing c.

####  V-B6 Effect of Varying Different Parameters on Acceptance Ratio

In this section, we illustrate the impact of different parameters, such as
utilization bound ($U/c$), number of tasks ($n$), edge percentage ($d$), and
the number of cores ($c$) on the task schedulability (acceptance ratio). Fig.
10 represents the effect of each parameter, while the others are fixed, to
analyze how the proposed method and the methods of [22, 33] react to each
parameter. We run 1000 benchmarks for each scenario, and report the average
result. A task set is schedulable if the real-time and power constraints are
met. In general, having more dependency between tasks, large system
utilization, or more cores, causes the system to have less acceptance ratio in
our proposed method. We discuss the observation in detail.

From the perspective of utilization bound, we fix other parameters to see the
effective of varying utilization in Fig. 10a. Increasing the utilization while
the number of tasks is fixed ($n$= 50), means that the tasks execution time
tends to be longer. when the utilization is getting higher, the computation
time of cores is increased. Therefore, fewer task sets can be scheduled before
their deadlines even in the case of fault occurrence, and also, the managing
of power constraint and busy/idle times of cores would be difficult. We can
conclude that fewer task sets can be scheduled before their deadline, while
the power constraint is not violated. This trend is also the same with [22,
33] with the difference that the TDP constraint is violated several times,
which causes the task sets not to be schedulable.

Besides, Fig. 10b shows that the task schedulability is increased by
increasing the number of tasks, with $d$= 10%, $U/c$= [0.5,0.75), and $c$= 8.
Since the system utilization is constant for all number of tasks, the
execution time of tasks is reduced by increasing the number of tasks.
Therefore, the tasks tend to finish their execution early and allow their
successors to be released. Furthermore, the overhead of re-executing a task
due to fault occurrence is much lower for small tasks. According to Fig. 10b,
we conclude that our method can schedule 70% of task sets, on average, when
only the number of tasks is varied. Besides, by increasing the number of tasks
in the methods of [22, 33], the parallel task execution is increased, which
causes more peak power consumption, and therefore, less task schedulability
due to the TDP violation.

For the case of varying the edge percentage, when the dependency between the
tasks is increased, while $n$, $U/c$ and $c$ are constant ($n$= 50, $U/c$=
[0.5,0.75), $c$= 8), the release time of tasks is increased, because tasks
must wait for more predecessor tasks to finish their executions. Therefore,
the idle time on cores increases, which causes more delays in the execution of
tasks, and reduce the schedulability. Fig. 10c shows that the highest
schedulability (73%) is achieved in our method when $d$=1%. Fig. 10d shows the
effect of varying the number of cores in the system on task schedulability
when other parameters are not changed ($n$= 50, $U/c$= [0.5,0.75), $d$= 10%).
By considering the fixed $U/c$, the utilization is increased by increasing the
number of cores. Consequently, the execution time of tasks is increased
because the number of tasks is fixed. As mentioned earlier, the task
schedulability is decreased by increasing the tasks’ execution time.
Therefore, as can be seen in Fig. 10d, the schedulability of applications with
our proposed method decreases by increasing the number of cores, while the
other parameters are fixed. Besides, in methods of [22, 33], the acceptance
ratio increases by increasing the dependency between tasks and having more
cores in the system. The reason is that based on their mapping and scheduling
algorithm, by increasing the edge percentage and number of cores while fixing
other parameters, tasks have less parallelism, and also fewer cores are
selected to be active to execute the tasks, which causes the system to have
less peak power consumption and therefore, a higher acceptance ratio. As a
result, by increasing the edge percentage for more than 20%, our proposed
method and method of [22, 33] have almost the same acceptance ratio. However,
the mapping and scheduling algorithm of [22, 33] increases the overheating
problem, which is not acceptable by most safety-critical systems. In addition,
since methods of [22, 33] are not peak-power aware, when the number of cores
is less, the TDP is violated in most of the task sets and therefore, these
task sets are not schedulable.

In the end, the acceptance ratio of our proposed method is 74.14% on average
for all scenarios, while it is 31.1% in the methods of [22, 33].

####  V-B7 Investigating Different Approaches at Run-Time

Now, we evaluate the system behavior at run-time in terms of peak power
consumption for our proposed approach and the method proposed in [33, 23, 22].
Researchers in [33] have presented a run-time method to reclaim the available
slacks and reduce the V-f levels of cores to decrease the system peak power.
Here, analogous to [33], the actual execution time of tasks follows the normal
distribution with the mean and standard deviation of $\frac{3\times WCET}{4}$
and $\frac{WCET}{12}$, respectively. Fig. 11 depicts the run-time power trace
of methods for a random task graph with $d=10\%$, $n=50$, $c=8$ and $U/c=0.9$.
The system switches to the HI mode by forcing a randomly selected HC task to
execute beyond its lowest WCET for both methods. As shown in this figure, the
system peak power in the proposed approach is less than the TDP constraint at
run-time, while the method of [22] has violated the TDP for a period of time.
Although the system peak power of [33] may be less than the TDP constraint for
some applications like the used task graph and their method consumes less
energy in the system, there is no guarantee for the peak power to be less than
the power constraint. Due to the using of DVFS technique in [33] and
decreasing the V-f levels at run-time, the system consumes less energy in
comparison with our proposed method. For the example of Fig. 11, the method of
[33] saves 0.74102$J$ in system compared to our proposed approach. However,
the DVFS technique degrades the reliability and increases the fault rate. The
fault rate depends on the system’s voltage level, and also, the application’s
reliability depends on the voltage level and tasks’ WCET, which is increased
by reducing the frequency level [43]. As an example, for this task graph, by
considering the fault rate $f=10^{-4}$ [37], the reliability of tasks has been
decreased $0.17\%$ and $2.08\%$, on average and worst-case in comparison with
our proposed approach. In addition, the number of nines for the system’s
reliability ($-Log_{10}^{1-Rel}$) has been degraded from 8 to 6, which may not
be desirable for most safety-critical applications [2].

Figure 11: System power trace of different methods at run-time

From the perspective of system’s reliability and fault-tolerance in our
proposed method, we run the 1000 task graph applications for different
normalized utilization bound ($U/c$= [0.5,0.75), and [0.75,1]) and compare to
the system’s reliability in [33]. In our proposed method, $-Log_{10}^{1-Rel}$
for the normalized utilization equal to [0.5,0.75), and [0.75,1], is 8.56 and
7.67 on average, respectively, while for [33], is 4.99, and 4.60,
respectively. As a result, based on the required reliability for safety-
critical systems, the method of [33], which decreases the V-f levels, has
severely damaged the system’s safety, which is not desirable. The reliability
of the proposed approach is high for different utilization. Therefore, our
method can be applied to any application with varying bounds of utilization
while satisfying the peak power management, fault-tolerance, and high
reliability in different system operational modes.

Besides, we have evaluated the proposed method and compared with the other
methods at run-time by using the real task graph in Appendix E.

##  VI Conclusion

This paper has proposed an approach to schedule MC tasks in fault-tolerant
systems in different operational modes to manage peak power by considering a
thermal management policy. At run-time, depending on the fault occurrence
possibilities and criticality mode changes, the system faces different
scenarios. We proposed an approach that develops a tree of schedules at
design-time. Each node of the tree represents a scenario and contains
scheduling where the system is able to execute all HC tasks and as many as
possible LC tasks without violating the TDP. At run-time, a low overhead
online scheduler selects the proper node to map and schedule tasks. The
results show that the proposed technique can schedule 74.14% of task sets on
average and significantly reduce peak power consumption (by guaranteeing the
TDP constraint) in the worst-case scenario compared to the existing methods.

As a future work, we would design the MC systems to generate the scheduling
tree based on tasks’ average execution times instead of WCETs to improve the
QoS in the HI mode.

## References

  * [1] A. Burns and R. I. Davis, “A survey of research into mixed criticality systems,” _ACM Computing Surveys (CSUR)_ , vol. 50, no. 6, pp. 1–37, 2017\.
  * [2] B. Ranjbar, B. Safaei, A. Ejlali, and A. Kumar, “FANTOM: Fault tolerant task-drop aware scheduling for mixed-criticality systems,” _IEEE Access_ , vol. 8, pp. 187 232–187 248, 2020.
  * [3] F. Bahrami, B. Ranjbar, N. Rohbani, and A. Ejlali, “PVMC: Task mapping and scheduling under process variation heterogeneity in mixed-criticality systems,” _IEEE Transactions on Emerging Topics in Computing (TETC)_ , pp. 1–1, 2021.
  * [4] R. Ernst and M. Di Natale, “Mixed criticality systems—a history of misconceptions?” _IEEE Design & Test_, vol. 33, no. 5, pp. 65–74, 2016\.
  * [5] B. Ranjbar, T. D. A. Nguyen, A. Ejlali, and A. Kumar, “Power-aware run-time scheduler for mixed-criticality systems on multi-core platform,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)_ , 2020.
  * [6] J. H. Anderson, S. K. Baruah, and B. B. Brandenburg, “Multicore operating-system support for mixed criticality,” in _Proc. of the Workshop on Mixed Criticality: Roadmap to Evolving UAV Certification_ , vol. 4. Citeseer, 2009, p. 7.
  * [7] J. Lee, B. Yun, and K. G. Shin, “Reducing peak power consumption inmulti-core systems without violating real-time constraints,” _IEEE Transactions on Parallel and Distributed Systems (TPDS)_ , vol. 25, no. 4, pp. 1024–1033, 2014\.
  * [8] W. Munawar, H. Khdr, S. Pagani, M. Shafique, J.-J. Chen, and J. Henkel, “Peak power management for scheduling real-time tasks on heterogeneous many-core systems,” in _Proc. of the International Conference on Parallel and Distributed Systems (ICPADS)_ , 2014, pp. 200–209.
  * [9] B. Lee, J. Kim, Y. Jeung, and J. Chong, “Peak power reduction methodology for multi-core systems,” in _Proc. of the International SoC Design Conference (ISOCC)_ , 2010, pp. 233–235.
  * [10] I. Koren and C. M. Krishna, _Fault-tolerant systems_. Morgan Kaufmann, 2020.
  * [11] S. S. Sahoo, B. Ranjbar, and A. Kumar, “Reliability-aware resource management in multi-/many-core systems: A perspective paper,” _Journal of Low Power Electronics and Applications_ , vol. 11, no. 1, p. 7, 2021.
  * [12] P. Huang, P. Kumar, G. Giannopoulou, and L. Thiele, “Energy efficient dvfs scheduling for mixed-criticality systems,” in _Proc. on Embedded Software (EMSOFT)_ , 2014, pp. 1–10.
  * [13] Z. Li, X. Hua, C. Guo, and S. Ren, “Empirical study of energy minimization issues for mixed-criticality systems with reliability constraint,” in _Proc. 1st Workshop on Low-Power Dependable Computing (LPDC)_ , 2014, pp. 3–5.
  * [14] I. Ali, J.-h. Seo, and K. H. Kim, “A dynamic power-aware scheduling of mixed-criticality real-time systems,” in _Proc. on Computer and Information Technology; Ubiquitous Computing and Communications; Dependable, Autonomic and Secure Computing; Pervasive Intelligence and Computing (CIT/IUCC/DASC/PICOM)_ , 2015, pp. 438–445.
  * [15] S. Narayana, P. Huang, G. Giannopoulou, L. Thiele, and R. V. Prasad, “Exploring energy saving for mixed-criticality systems on multi-cores,” in _Proc. on Real-Time and Embedded Technology and Applications Symposium (RTAS)_ , 2016, pp. 1–12.
  * [16] A. Taherin, M. Salehi, and A. Ejlali, “Reliability-aware energy management in mixed-criticality systems,” _IEEE Transactions on Sustainable Computing (TSUSC)_ , vol. 3, no. 3, pp. 195–208, 2018.
  * [17] M. A. Awan, D. Masson, and E. Tovar, “Energy efficient mapping of mixed criticality applications on unrelated heterogeneous multicore platforms,” in _Proc. on IEEE Symposium on Industrial Embedded Systems (SIES)_ , 2016, pp. 1–10.
  * [18] C.-H. Hsu and U. Kremer, “Compiler-directed dynamic voltage and frequency scaling for CPU power and energy reduction,” Ph.D. dissertation, Rutgers University, 2003.
  * [19] S. Baruah, “The federated scheduling of systems of mixed-criticality sporadic DAG tasks,” in _Proc. of IEEE Real-Time Systems Symposium (RTSS)_ , 2016, pp. 227–236.
  * [20] Z. Li and S. He, “Fixed-priority scheduling for two-phase mixed-criticality systems,” _ACM Transactions on Embedded Computing Systems (TECS)_ , vol. 17, no. 2, pp. 1–20, 2018.
  * [21] W. Huang, S. Ghosh, S. Velusamy, K. Sankaranarayanan, K. Skadron, and M. R. Stan, “Hotspot: A compact thermal modeling methodology for early-stage vlsi design,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , vol. 14, no. 5, pp. 501–513, 2006.
  * [22] R. Medina, E. Borde, and L. Pautet, “Availability enhancement and analysis for mixed-criticality systems on multi-core,” in _Proc. on Design, Automation & Test in Europe Conference & Exhibition (DATE)_, 2018, pp. 1271–1276.
  * [23] D. Socci, P. Poplavko, S. Bensalem, and M. Bozga, “Multiprocessor scheduling of precedence-constrained mixed-critical jobs,” in _Proc. of International Symposium on Real-Time Distributed Computing (ISORC)_ , 2015, pp. 198–207.
  * [24] D. Socci, P. Poplavko, S. Bensalem, and M. Bozga, “Priority-based scheduling of mixed-critical jobs,” _Real-Time Systems_ , vol. 55, no. 4, pp. 709–773, 2019.
  * [25] R. Medina, E. Borde, and L. Pautet, “Directed acyclic graph scheduling for mixed-criticality systems,” in _Ada-Europe International Conference on Reliable Software Technologies_. Springer, 2017, pp. 217–232.
  * [26] J. Li, D. Ferry, S. Ahuja, K. Agrawal, C. Gill, and C. Lu, “Mixed-criticality federated scheduling for parallel real-time tasks,” in _Proc. of IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)_ , 2016, pp. 1–12.
  * [27] R. M. Pathan, “Improving the schedulability and quality of service for federated scheduling of parallel mixed-criticality tasks on multiprocessors,” in _Proc. of Euromicro Conference on Real-Time Systems (ECRTS)_ , vol. 106, 2018, pp. 12:1–12:22.
  * [28] R. Medina, E. Borde, and L. Pautet, “Scheduling multi-periodic mixed-criticality DAGs on multi-core architectures,” in _Proc. of IEEE Real-Time Systems Symposium (RTSS)_ , 2018, pp. 254–264.
  * [29] J. Choi, H. Yang, and S. Ha, “Optimization of fault-tolerant mixed-criticality multi-core systems with enhanced wcrt analysis,” _ACM Trans. Des. Autom. Electron. Syst. (TODAES)_ , vol. 24, no. 1, pp. 1–26, 2018.
  * [30] C. Bolchini and A. Miele, “Reliability-driven system-level synthesis for mixed-critical embedded systems,” _IEEE Transactions on Computers (TC)_ , vol. 62, no. 12, pp. 2489–2502, 2013.
  * [31] M. Ansari, S. Safari, A. Yeganeh-Khaksar, M. Salehi, and A. Ejlali, “Peak power management to meet thermal design power in fault-tolerant embedded systems,” _IEEE Transactions on Parallel and Distributed Systems (TPDS)_ , vol. 30, no. 1, pp. 161–173, 2019.
  * [32] T. Li, T. Zhang, G. Yu, Y. Zhang, and J. Song, “Ta-mcf: Thermal-aware fluid scheduling for mixed-criticality system,” _Journal of Circuits, Systems and Computers (JCSC)_ , vol. 28, no. 02, p. 1950029, 2019.
  * [33] B. Ranjbar, T. D. A. Nguyen, A. Ejlali, and A. Kumar, “Online peak power and maximum temperature management in multi-core mixed-criticality embedded systems,” in _Proc. of Euromicro Conference on Digital System Design (DSD)_ , 2019, pp. 546–553.
  * [34] A. Das and A. Kumar, “Fault-aware task re-mapping for throughput constrained multimedia applications on noc-based mpsocs,” in _Proc. of IEEE International Symposium on Rapid System Prototyping (RSP)_ , 2012, pp. 149–155.
  * [35] A. Das, A. Kumar, and B. Veeravalli, “Communication and migration energy aware task mapping for reliable multiprocessor systems,” _Future Generation Computer Systems_ , vol. 30, pp. 216–228, 2014.
  * [36] A. Das, A. Kumar, and B. Veeravalli, “Energy-aware task mapping and scheduling for reliable embedded computing systems,” _ACM Trans. Embed. Comput. Syst. (TECS)_ , vol. 13, no. 2s, pp. 1–27, 2014.
  * [37] M. Salehi, A. Ejlali, and B. M. Al-Hashimi, “Two-phase low-energy n-modular redundancy for hard real-time multi-core systems,” _IEEE Transactions on Parallel and Distributed Systems (TPDS)_ , vol. 27, no. 5, pp. 1497–1510, 2016\.
  * [38] V. Izosimov, P. Eles, and Z. Peng, “Value-based scheduling of distributed fault-tolerant real-time systems with soft and hard timing constraints,” in _Proc. of the IEEE Workshop on Embedded systems for real-time multimedia (ESTIMedia)_ , 2010, pp. 31–40.
  * [39] G. C. Buttazzo, _Hard real-time computing systems: predictable scheduling algorithms and applications_. Springer Science & Business Media, 2011, vol. 24.
  * [40] A. Meixner, M. E. Bauer, and D. Sorin, “Argus: Low-cost, comprehensive error detection in simple cores,” in _Proc. of IEEE/ACM International Symposium on Microarchitecture (MICRO)_ , 2007, pp. 210–222.
  * [41] J. P. Cerrolaza, R. Obermaisser, J. Abella, F. J. Cazorla, K. Grüttner, I. Agirre, H. Ahmadian, and I. Allende, “Multi-core devices for safety-critical systems: A survey,” _ACM Computing Surveys (CSUR)_ , vol. 53, no. 4, pp. 1–38, 2020.
  * [42] V. Izosimov, P. Pop, P. Eles, and Z. Peng, “Scheduling of fault-tolerant embedded systems with soft and hard timing constraints,” in _Proc. on Design, Automation & Test in Europe Conference & Exhibition (DATE)_, 2008, pp. 915–920.
  * [43] M. Salehi, M. Khavari Tavana, S. Rehman, M. Shafique, A. Ejlali, and J. Henkel, “Two-state checkpointing for energy-efficient fault tolerance in hard real-time systems,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , vol. 24, no. 7, pp. 2426–2437, 2016.
  * [44] M. Chisholm, N. Kim, S. Tang, N. Otterness, J. H. Anderson, F. D. Smith, and D. E. Porter, “Supporting mode changes while providing hardware isolation in mixed-criticality multicore systems,” in _Proc. of Real-Time Networks and Systems (RTNS)_ , 2017, p. 58–67.
  * [45] Y. Zhang and K. Chakrabarty, “A unified approach for fault tolerance and dynamic power management in fixed-priority real-time embedded systems,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)_ , vol. 25, no. 1, pp. 111–125, 2006.
  * [46] Y. Gong, J. J. Yoo, and S. W. Chung, “Thermal modeling and validation of a real-world mobile ap,” _IEEE Design & Test_, vol. 35, no. 1, pp. 55–62, 2018.
  * [47] Y. Liu, H. Yang, R. P. Dick, H. Wang, and L. Shang, “Thermal vs energy optimization for dvfs-enabled processors in embedded systems,” in _Proc. of International Symposium on Quality Electronic Design (ISQED)_ , 2007, pp. 204–209.

|  Behnaz Ranjbar received the B.S. degree in computer engineering from
Amirkabir University of Technology in 2012 and the M.S. degree from Sharif
University of Technology, Tehran, Iran in 2014. She is currently a joint Ph.D.
student with the Sharif University of Technology, Tehran, Iran, and the Chair
for Processor Design, Technische Universität Dresden, Dresden, Germany. Her
research interest includes real-time, fault tolerant and low-power embedded
system design.
---|---
|  Ali Hosseinghorban received his B.Sc. in computer engineering from Shahid
Beheshti University and his M.Sc. from Sharif University of Technology in 2015
and 2017, respectively. He is currently a Ph.D. student in the Computer
Engineering department of Sharif University of Technology. He is also a
visiting researcher at the Chair for Processor Design, Technische Universität
Dresden, Dresden, Germany. His research interests include low-power real-time
embedded systems, reconfigurable computing, and management of nonvolatile
memories.
---|---
|  Mohammad Salehi received the PhD degree in computer engineering from Sharif
University of Technology, Tehran, Iran, in 2016. He is currently an assistant
professor of computer engineering at University of Guilan, Rasht, Iran. From
2014 to 2015, he was a visiting researcher in the Chair for Embedded Systems,
Karlsruhe Institute of Technology, Germany. His research interests include
design of low-power, reliable and real-time embedded systems with a focus on
dependability and energy efficiency in cyber-physical systems.
---|---
|  Alireza Ejlali received the PhD degree in computer engineering from Sharif
University of Technology (SUT), Tehran, Iran, in 2006. He is currently an
associate professor of computer engineering at SUT. From 2005 to 2006, he was
a visiting researcher in the Electronic Systems Design Group, University of
Southampton, Southampton, United Kingdom. He is currently the Director of the
Embedded Systems Research Laboratory, SUT. His research interests include low
power design, real-time systems, and fault-tolerant embedded systems.
---|---
|  Akash Kumar (SM’13) received the joint Ph.D. degree in electrical
engineering and embedded systems from the Eindhoven University of Technology,
Eindhoven, The Netherlands, and the National University of Singapore (NUS),
Singapore, in 2009. From 2009 to 2015, he was with NUS. He is currently a
Professor with Technische Universität Dresden, Dresden, Germany, where he is
directing the Chair for Processor Design. His current research interests
include the design, analysis, and resource management of low-power and fault-
tolerant embedded multiprocessor systems.
---|---

##  Appendix A A Brief Overview of Fault Detection and Correction Mechanisms

Researchers in [10, 1, 30, 41] give a comprehensive study in the field of
fault detection and correction mechanisms. A comparison of recent mechanisms
has been studied recently in [2]. In general, the key to these mechanisms is
using redundancy, which could be information, hardware, time, or analytical.
In the following, we present these mechanisms briefly, which have been used in
recent works in the field of embedded real-time systems.

  * •

Hardware Redundancy: Hardware redundancy is one of the most useful mechanisms
to detect and correct a fault in embedded real-time systems, that can be
classified as active, passive, and hybrid [1, 10]. Duplication is the most
straightforward fault detection active redundancy, where two copies of a task
are executed, and in the case of fault occurrence, the results of the two
copies are not identical. However, this technique cannot tolerate faults.
Therefore, N-modular redundancy with a voter and replication are passive
redundancy and can be used to detect and correct the faults in applications,
used recently in [31, 37]. Watchdog timer and standby sparing are the other
hardware redundancy techniques that standby sparing has been used in [3]
recently.

  * •

Timing Redundancy: Check-pointing and rollback-recovery is one of the most
common techniques to detect transient faults in embedded systems due to its
cost-effectiveness [43]. When faults are detected, the re-executed technique
can be used to tolerate it. Finding the optimum number of check-points during
the execution of tasks is one of the challenges when this technique is used.

  * •

Information Redundancy: This redundancy is a software-based technique in which
error detection codes or parity bits can detect and recover the faulty data.
Some recent works like [4, 5] have focused on mitigating the soft errors by
using the information redundancy.

  * •

Analytical Redundancy: A few recent research works [6, 7, 8] have focused on
detecting fault based on deep learning. The reason for using Machine Learning
(ML) techniques is that some faults may not be detected by existing methods,
which are applied at design-time and employed at run-time, and then a failure
in identifying the error may have serious consequences. The ML mechanisms are
classified into two categories of data driven-based, such as unsupervised
learning, and knowledge driven-based such as reinforcement learning. Since the
embedded MC systems are safety-critical, detecting faults must have low
latency to not impact the tasks’ deadlines. In addition, since these systems
are embedded, the chosen ML technique must be low-power. In general, any
learning technique has some advantages and disadvantages. Therefore, the
designer can select the proper technique based on the feature of the systems.
Additionally, researchers in [9] have studied ML-based fault detection,
prediction, and prevention and presented a survey of ML solutions.

##  Appendix B Time Complexity Analysis

In this section, we consider an m-core processor running an application with n
tasks, and k possible fault occurrences during the application’s execution. At
first, we describe the complexity of generating a tree as the main computation
part of the proposed method.

When an HC task overruns, the system switches to the HI mode, and the
scheduler considers the high WCET of remaining tasks until complete execution
of the application. So, in each execution, only one task may overrun, and the
possible scenarios for overrun situations are equal to the number of HC tasks
($n_{H}$). Furthermore, we assume that up to k faults may occur during the
execution of the application. For clarity, we first compute the number of
different fault occurrence scenarios for k = 0, 1 and 2. Then, we present a
general formula to obtain the maximum number of possible scenarios (nodes of
the tree).

  * •

k = 0: In this case, there is one scenario for a situation where none of the
tasks overruns (the root of the tree) and $n_{H}$ (number of HC tasks in the
graph) scenarios for situations where one of the HC tasks overruns (leaf nodes
of the tree). Thus, the number of all schedules is:

$\displaystyle T(k=0)=1+n_{H}$ (10)

  * •

$\textit{k}\leq 1$: In this case, the tree has $T(k=0)$ nodes to handle $k=0$
scenarios, in addition to the nodes which contain scheduling for $k=1$
scenarios. There are three possible situations for the scenarios where one
fault occurs to a task (HC or LC task). There are $n$ scenarios for situations
when no HC task overruns, $n\times n_{H}$ scenarios for situations where the
faulty task executes before an HC task overruns, and $n\times n_{H}$ scenarios
situations where the faulty task executes after an HC task overruns.
Therefore:

$\displaystyle T(k\leq 1)$ $\displaystyle=T(k=0)+n+2\times n\times n_{H}$
$\displaystyle=1+n_{H}+n_{H}\times n+n\times(1+n_{H})$
$\displaystyle=1+n_{H}+n_{H}\times n+n\times T(k=0)$ (11)

  * •

$\textit{k}\leq 2$: In this case, the tree has $T(k\leq 1)$ nodes to handle
$k\leq 1$ scenarios, in addition to the nodes which contain scheduling for
$k=2$ scenarios. There are four possible situations for the scenarios where
two faults occur to one or two task(s). There are $n^{2}$ scenarios for
situations when no HC task overruns, $n\times n\times n_{H}$ scenarios for
situations where the two faulty tasks are executed before an HC task overruns,
$n_{H}\times n\times n$ scenarios for situations where the two faulty tasks
are executed after an HC task overruns, and $n\times n_{H}\times n$ scenarios
situations where an HC task overruns in the middle of two faulty tasks. It is
noteworthy to mention that there are scenarios in which both faults and
overrun happens on a one HC task (similar to S7, S10, S12 and S14 in Table
II). Therefore:

$\displaystyle T(k\leq 2)=T(k\leq 1)+n^{2}+3\times n_{H}\times n^{2}$
$\displaystyle=1+n_{H}+n_{H}\times n+n_{H}\times n^{2}+n\times T(k\leq 1)$
(12)

Therefore, we can conclude that the maximum number of possible schedules by
considering maximum k fault occurrence is:

$\displaystyle T(k)$
$\displaystyle=1+n_{H}(\sum_{i=0}^{k}(n^{i}))+nT(k-1),T(0)=1+n_{H}$ (13)

By solving the Eq. 13, we can conclude that generating the tree is in order of
$O(n^{k+2})$.

$\displaystyle T(k)=n_{H}\times(\sum_{i=0}^{k}((i+1)\times
n^{i}))+\frac{1-n^{k+1}}{1-n}$ (14)

Please note that this value is a general upper bound for the generating tree
algorithm, and for an actual task graph, the total number of scenarios is less
than Eq. 13. The reason is that, the total number of scenarios are presented
with no awareness of the exact dependency between tasks to count the precise
number of scenarios when a fault occurs and then a task overruns, or vice
versa. For example, there are 14 different scenarios for two HC tasks, one LC
task, and k=1 for the task graph presented in Fig. 2, while $T(k)$ is equal to
18 in Eq. 13.

##  Appendix C Memory Space Analysis

In this section, we discuss the memory space needed for storing the scheduling
tree. For each scenario, we store two arrays with the size of the number of
tasks. The first array determines the core assigned to each task, and the
second array determines the start time of the tasks. In the first array, we
denote that each task is mapped to which of $c$ cores. So, each task requires
$\log_{2}^{c}$ bits. Since we have n tasks in the application, the total
memory space required for each scenario is $n\times\log_{2}^{c}$ bits.
Considering the period of the application and the size of each time slot, the
second array size is equal to $n\times\log_{2}^{period/timeslot}$. Therefore,
the total amount of needed memory (bits) is:

$\displaystyle
Mem(n,c,k)=T(k)\times(n\times(\log^{c}_{2}+\log^{\frac{period}{timeslot}}_{2})$
(15)

Assuming c and period/timeslot values are less than $2^{32}$, the memory space
needed for saving the scheduling tree for an application with 32 tasks and up
to two possible fault occurrences in the worst-case scenario is less than 13
MB. It is noteworthy to mention that the scheduling tree can be stored in the
FLASH or read-only memory of the system, and there is no need to load the
whole tree to the RAM at run-time. In the case of fault occurrence or mode
switching at run-time, the system discards the current schedule and loads the
proper child node’s schedule into the RAM. In this example, our approach
occupies less than 2 KB of the RAM.

##  Appendix D Power Trace and Thermal Distributions of the Real Application
and a Random Task Graph Example under Worst-Case Scenario

This paper focuses on peak power management and maximum temperature reduction
in fault-tolerance MC systems in multi-core platforms. We have evaluated
different methods for a real-life task graph running on three cores in Section
V-B3. In this appendix, we first show the thermal distribution of the real-
life application, and then, we show the corresponding results for a random
application with high utilization.

Fig. 12 shows the steady-state temperature distribution of Sooci [23], Medina
[22], Ranjbar [33], and our proposed method using the HOTSPOT simulator for
the CC application, corresponding to power profile of Fig. 7. Although the
maximum temperature of [23] is lower than ours, it has zero-percent LC tasks’
QoS because it does not execute any LC task in the HI mode. In addition, we
map the tasks on the cores more uniform than the Medina’s method, which
prevents hotspots in our approach. The proposed approach could reduce 5∘C in
maximum temperature compared to [22, 33]. If the system becomes larger in
terms of number of cores and tasks, the efficiency of our proposed approach in
reducing the hotspots would be higher.

(a) Proposed Method

(b) [22, 33]

(c) [23]

(d)

Figure 12: Thermal profiles of real-life application graph (CC) in different
methods under worst-case scenario

Now, we evaluate the power trace and thermal distribution of different methods
of [23, 22, 33] and our proposed method for a random task set example in the
worst-case scenario, in terms of execution times and power consumption. It
should be noted that the scale of temperature for each method is different in
Fig. 14. Since we have generated many task graphs with different values of
parameters (n, d, c and U/c), we choose one of the random task graphs with
$d=10\%$, $n=50$, $c=8$ and $U/c=0.9$, which needs a high computational demand
to show the results. Fig. 13 shows the power traces, and Fig. 14 shows the
thermal distribution of the methods. As can be seen in Fig. 13, the peak power
consumption is violated some times in the method of [22, 33], and since the
method, of [23] drops all LC tasks in the HI mode, which is not desirable, the
task set finishes its execution earlier and also has less peak power
consumption. Besides, Fig. 14 depicts that the thermal distribution has not
been managed in [22, 33], while our approach reduces the hotspots and lowers
the maximum temperature by 22.3∘C in this example. Although the maximum
temperature of [23] is lower than ours, the LC tasks’ QoS is zero since no LC
tasks are executed in the HI mode.

Figure 13: Power trace of a random task graph in different methods under
worst-case scenario

(a) Proposed Method

(b) [22, 33]

(c) [23]

Figure 14: Thermal profiles of a random task graph example in different
methods under worst-case scenario

##  Appendix E Power Trace of Real-Life Application Graph (CC) with Different
Methods at Run-Time

Section V-B7 discussed the system behavior when the tasks finish their
execution earlier than their worst-case execution time (WCET). The method of
[33] uses the same task mapping and scheduling algorithm of [22] at design-
time and reduces the peak power by reclaiming the dynamic slack times at run-
time (the difference between the WCET and actual execution time) and decreases
the operating voltage and frequency level of cores while executing the tasks.
We have analyzed our proposed method compared to different methods for an
example in Section V-B7. Since we have used a real-life task graph (Cruise
Controller (CC)) to evaluate our proposed method, here we show the run-time
system behavior for the real task graph in Fig. 15. As shown in this figure,
the approach of [22] still violates the power constraint (TDP), and since the
approach of [33] has applied the DVFS technique, the peak power consumption
has been reduced. However, the approach of [33] has degraded reliability due
to the use of DVFS technique, which is not desirable for safety-critical
applications. In addition, our proposed method could manage the peak power
consumption in this real task graph, and also, since the method of [23] has
dropped all LC tasks in the HI mode, the peak power consumption is also less
than the TDP constraint.

Figure 15: Run-time power trace of real-life task graph in different methods

## References

## References

  * [1] D. Siewiorek and R. Swarz, _Reliable computer systems: design and evaluation_. Digital Press, 2017.
  * [2] V. B. Thati, J. Vankeirsbilck, N. Penneman, D. Pissoort, and J. Boydens, “Cdfedt: Comparison of data flow error detection techniques in embedded systems: An empirical study,” in _Proc. of the International Conference on Availability, Reliability and Security_ , 2018.
  * [3] S. Safari, S. Hessabi, and G. Ershadi, “Less-mics: A low energy standby-sparing scheme for mixed-criticality systems,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)_ , vol. 39, no. 12, pp. 4601–4610, 2020.
  * [4] A. Kajmakovic, K. Diwold, N. Kajtazovic, R. Zupanc, and G. Macher, “Flexible Soft Error Mitigation Strategy for Memories in Mixed-Critical Systems,” in _IEEE International Symposium on Software Reliability Engineering Workshops (ISSREW)_ , 2019, pp. 440–445.
  * [5] S. A. Asghari, M. B. Marvasti, and M. Daneshtalab, “A software implemented comprehensive soft error detection method for embedded systems,” _Microprocessors and Microsystems_ , p. 103161, 2020.
  * [6] R. Iqbal, T. Maniak, F. Doctor, and C. Karyotis, “Fault detection and isolation in industrial processes using deep learning approaches,” _IEEE Transactions on Industrial Informatics (TII)_ , vol. 15, no. 5, pp. 3077–3084, 2019.
  * [7] J. Lee, Y. C. Lee, and J. T. Kim, “Fault detection based on one-class deep learning for manufacturing applications limited to an imbalanced database,” _Journal of Manufacturing Systems_ , vol. 57, pp. 357–366, 2020.
  * [8] D. Park, S. Kim, Y. An, and J.-Y. Jung, “Lired: A light-weight real-time fault detection system for edge computing using lstm recurrent neural networks,” _Sensors_ , vol. 18, no. 7, p. 2110, 2018.
  * [9] A. Angelopoulos, E. T. Michailidis, N. Nomikos, P. Trakadas, A. Hatziefremidis, S. Voliotis, and T. Zahariadis, “Tackling faults in the industry 4.0 era—a survey of machine-learning solutions and key aspects,” _Sensors_ , vol. 20, no. 1, p. 109, 2020.