# Contention and Reliability-Aware Energy Efficiency Task Mapping on NoC-Based MPSoCs

Lei Mo, Xinmei Li, Angeliki Kritikakou, Xiaojun Zhai

► To cite this version:

Lei Mo, Xinmei Li, Angeliki Kritikakou, Xiaojun Zhai. Contention and Reliability-Aware Energy Efficiency Task Mapping on NoC-Based MPSoCs. IEEE Transactions on Reliability, 2024, pp.1-16. 10.1109/TR.2024.3377732. hal-04528715

HAL Id: hal-04528715

https://hal.science/hal-04528715

Submitted on 2 Apr 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
<figure><img src="image_1.png" /></figure>

HAL
open science

# Contention and Reliability-Aware Energy Efficiency Task Mapping on NoC-Based MPSoCs

Lei Mo, Xinmei Li, Angeliki Kritikakou, Xiaojun Zhai

<figure><img src="image_2.png" /></figure>

## To cite this version:

Lei Mo, Xinmei Li, Angeliki Kritikakou, Xiaojun Zhai. Contention and Reliability-Aware Energy Efficiency Task Mapping on NoC-Based MPSoCs. IEEE Transactions on Reliability, 2024, pp.1-16. 10.1109/TR.2024.3377732. hal-04528715

HAL Id: hal-04528715

https://hal.science/hal-04528715v1

Submitted on 2 Apr 2024

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Contention and Reliability-Aware Energy Efficiency Task Mapping on NoC-Based MPSoCs

Lei Mo*, Member, IEEE, Xinmei Li*, Student Member, IEEE, Angeliki Kritikakou†, Member, IEEE, and Xiaojun Zhai‡, Senior Member, IEEE

**Abstract**—Recently, Network-on-Chip (NoC)-based Multi-Processor System-on-Chips (MPSoCs) have become popular computing platforms for real-time applications due to high communication performance and energy efficiency over traditional bus-based MPSoCs. Due to the nature of network structures, network congestion along with transient faults, can significantly affect communication efficiency and system reliability. Most existing works have rarely focused on the concurrent optimization of network contention, reliability, and energy consumption. Here, we study the problem of contention and reliability-aware task mapping under real-time constraints for dynamic voltage and frequency scaling-enabled NoC. The problem entails optimizing voltage/frequency on cores and links to reduce energy consumption and ensure system reliability, while task mapping and slack time are adopted to alleviate network contention and reduce latency. We aim to minimize computation and communication energy and balance workload. This problem is formulated as a mixed-integer nonlinear programming, and we present an effective linearization scheme that equivalently transforms it into a mixed-integer linear programming to find the optimal solution. To reduce computation time, we propose a three-step heuristic, including task allocation, frequency scaling and edge scheduling, and communication contention management. Finally, we perform extensive simulations to evaluate the proposed method. The results show we can achieve 31.6% and 21.7% energy savings, with 95.5% and 98.6% less contention than the existing methods.

**Index Terms**—Contention-aware, Reliability-aware, Energy Management, Task mapping, NoC.

## I. INTRODUCTION

WITH the increasing demand for high computing performances, e.g., Internet of Things (IoT) [1], big data processes [2], cloud centers [3] and blockchain systems [4], Multi-Processor System-on-Chip (MPSoC) architectures integrate multiple cores into a single platform. The increase in cores leads to many issues and challenges for traditional shared bus-based multicore platforms, such as poor scalability and low communication efficiency due to the limited bus bandwidth [5]. To address the scalability and bandwidth issues, Network-on-Chip (NoC) has been proposed as an interconnection architecture solution with much better scalability, flexibility, parallelism, and communication efficiency, compared to the traditional bus-based multicore platforms [6]. In the NoC-based MPSoCs, e.g., the Ethereal NoC [7], the Versal NoC [8], and the Arteris

NoC [9], the Operating System (OS) can run at each core, responsible for task scheduling, task loading, packet assembly/disassembly, and Direct Memory Access (DMA) management, enabling the platforms to meet multiple constraints.

Furthermore, energy consumption has become an essential issue for the NoC-based MPSoCs as the number of cores increases. To achieve an effective system, appropriate task mapping methods are needed. Most energy-aware task mapping methods in bus-based MPSoCs mainly focus on the energy consumption of computation, e.g., [10]–[12]. To reduce both computation and communication energy consumption, the NoC-based MPSoCs are enhanced with Dynamic Voltage and Frequency Scheduling (DVFS) for cores, routers, and links [13]–[16]. The energy consumption can be reduced by lowering the Voltage/Frequency (V/F) level. However, the decrease in operating V/F levels impacts the transient fault rate on cores, routers, and links, thereby decreasing the system reliability [17]. Therefore, the trade-off between energy consumption and system reliability should be considered during task mapping on NoC-based MPSoCs. Some existing works [18]–[21] have studied the joint design problem of saving energy and enhancing system reliability. For instance, transient faults are considered on links and routers [18], [19] or cores [20], [21]. As transient faults may occur during task execution and communication, it is necessary to consider that they can occur on cores, routers, and links when optimizing task mapping for energy consumption and system reliability on NoC-based platforms.

Due to the nature of the network-based structure, the task mapping strategy on NoC-based platforms may cause network contention among the task data communication over the shared communication resource, i.e., routers and links. If a link is occupied due to the transmission of a message, any other messages requiring the same link will wait until the link becomes available [6], [14]. Network congestion degrades system performance due to the increased transmission delay, thereby affecting the execution time of applications, which is of paramount importance, especially for real-time applications [6]. For the NoC-based platforms, it is necessary to consider communication contention during task mapping. However, most existing works focused on energy and (or) reliability improvement but ignored the influence of communication contention [18], [21]. Other works alleviated the network congestion by introducing fixed slack time into the task scheduling [13]. Note that load imbalance may cause overloading and local network congestion on NoC. Overloading decreases power efficiency and system reliability [22]–[24] since the cores with high computation loads

<footnote>*L. Mo and X. Li are with the School of Automation, Southeast University, 210096 Nanjing, China. E-mails: lmo@seu.edu.cn, xinmeili@seu.edu.cn.</footnote>

<footnote>†A. Kritikakou is with the University of Rennes, INRIA, IRISA, CNRS, 35042 Rennes, France, and also with the Institut Universitaire de France, 75005 Paris, France. E-mail: angeliki.kritikakou@irisa.fr.</footnote>

<footnote>‡X. Zhai is with the School of Computer Science and Electronic Engineering, University of Essex, Colchester CO4 3SQ, U.K., E-mail: xzhai@essex.ac.uk.</footnote>
# Contention and Reliability-Aware Energy Efficiency Task Mapping on NoC-Based MPSoCs

Lei Mo*, Member, IEEE, Xinmei Li*, Student Member, IEEE, Angeliki Kritikakou†, Member, IEEE, and Xiaojun Zhai‡, Senior Member, IEEE

**Abstract**—Recently, Network-on-Chip (NoC)-based Multi-Processor System-on-Chips (MPSoCs) have become popular computing platforms for real-time applications due to high communication performance and energy efficiency over traditional bus-based MPSoCs. Due to the nature of network structures, network congestion along with transient faults, can significantly affect communication efficiency and system reliability. Most existing works have rarely focused on the concurrent optimization of network contention, reliability, and energy consumption. Here, we study the problem of contention and reliability-aware task mapping under real-time constraints for dynamic voltage and frequency scaling-enabled NoC. The problem entails optimizing voltage/frequency on cores and links to reduce energy consumption and ensure system reliability, while task mapping and slack time are adopted to alleviate network contention and reduce latency. We aim to minimize computation and communication energy and balance workload. This problem is formulated as a mixed-integer nonlinear programming, and we present an effective linearization scheme that equivalently transforms it into a mixed-integer linear programming to find the optimal solution. To reduce computation time, we propose a three-step heuristic, including task allocation, frequency scaling and edge scheduling, and communication contention management. Finally, we perform extensive simulations to evaluate the proposed method. The results show we can achieve 31.6% and 21.7% energy savings, with 95.5% and 98.6% less contention than the existing methods.

**Index Terms**—Contention-aware, Reliability-aware, Energy Management, Task mapping, NoC.

## I. INTRODUCTION

WITH the increasing demand for high computing performances, e.g., Internet of Things (IoT) [1], big data processes [2], cloud centers [3] and blockchain systems [4], Multi-Processor System-on-Chip (MPSoC) architectures integrate multiple cores into a single platform. The increase in cores leads to many issues and challenges for traditional shared bus-based multicore platforms, such as poor scalability and low communication efficiency due to the limited bus bandwidth [5]. To address the scalability and bandwidth issues, Network-on-Chip (NoC) has been proposed as an interconnection architecture solution with much better scalability, flexibility, parallelism, and communication efficiency, compared to the traditional bus-based multicore platforms [6]. In the NoC-based MPSoCs, e.g., the Ethereal NoC [7], the Versal NoC [8], and the Arteris

NoC [9], the Operating System (OS) can run at each core, responsible for task scheduling, task loading, packet assembly/disassembly, and Direct Memory Access (DMA) management, enabling the platforms to meet multiple constraints.

Furthermore, energy consumption has become an essential issue for the NoC-based MPSoCs as the number of cores increases. To achieve an effective system, appropriate task mapping methods are needed. Most energy-aware task mapping methods in bus-based MPSoCs mainly focus on the energy consumption of computation, e.g., [10]–[12]. To reduce both computation and communication energy consumption, the NoC-based MPSoCs are enhanced with Dynamic Voltage and Frequency Scheduling (DVFS) for cores, routers, and links [13]–[16]. The energy consumption can be reduced by lowering the Voltage/Frequency (V/F) level. However, the decrease in operating V/F levels impacts the transient fault rate on cores, routers, and links, thereby decreasing the system reliability [17]. Therefore, the trade-off between energy consumption and system reliability should be considered during task mapping on NoC-based MPSoCs. Some existing works [18]–[21] have studied the joint design problem of saving energy and enhancing system reliability. For instance, transient faults are considered on links and routers [18], [19] or cores [20], [21]. As transient faults may occur during task execution and communication, it is necessary to consider that they can occur on cores, routers, and links when optimizing task mapping for energy consumption and system reliability on NoC-based platforms.

Due to the nature of the network-based structure, the task mapping strategy on NoC-based platforms may cause network contention among the task data communication over the shared communication resource, i.e., routers and links. If a link is occupied due to the transmission of a message, any other messages requiring the same link will wait until the link becomes available [6], [14]. Network congestion degrades system performance due to the increased transmission delay, thereby affecting the execution time of applications, which is of paramount importance, especially for real-time applications [6]. For the NoC-based platforms, it is necessary to consider communication contention during task mapping. However, most existing works focused on energy and (or) reliability improvement but ignored the influence of communication contention [18], [21]. Other works alleviated the network congestion by introducing fixed slack time into the task scheduling [13]. Note that load imbalance may cause overloading and local network congestion on NoC. Overloading decreases power efficiency and system reliability [22]–[24] since the cores with high computation loads

<footnote>*L. Mo and X. Li are with the School of Automation, Southeast University, 210096 Nanjing, China. E-mails: lmo@seu.edu.cn, xinmeili@seu.edu.cn.</footnote>

<footnote>†A. Kritikakou is with the University of Rennes, INRIA, IRISA, CNRS, 35042 Rennes, France, and also with the Institut Universitaire de France, 75005 Paris, France. E-mail: angeliki.kritikakou@irisa.fr.</footnote>

<footnote>‡X. Zhai is with the School of Computer Science and Electronic Engineering, University of Essex, Colchester CO4 3SQ, U.K., E-mail: xzhai@essex.ac.uk.</footnote>
stay active most of the time while the remaining cores are idle. To obtain an efficient system, we must simultaneously alleviate network contention, balance workload, and improve energy efficiency and reliability.

To address the above issues, we propose a novel task mapping method to jointly optimize energy efficiency through DVFS while balancing the workload and mitigating the communication contention on the NoC-based platform under real-time and reliability constraints. Therefore, our method is suitable for applications with energy efficiency, reliability, and timeliness requirements, such as autonomous drones [25], and video processing systems [26]. The main contributions of this paper are summarized as follows:

(1) We holistically model the problem of reducing energy consumption and balancing the workload for NoC-based platforms. DVFS adjusts the V/F levels of cores and links, reducing the total energy consumption under real-time and reliability constraints. Communication contention is considered, where flexible slack time alleviates communication contention, reducing latency.

(2) Based on the system model, the task mapping problem is formulated as a mixed-integer nonlinear programming (MINLP) problem, with the aim to minimize energy consumption and balance workload under multiple constraints. We apply the linearization method by introducing auxiliary variables and additional constraints and then equivalently transform the original problem into a mixed-integer linear programming (MILP) problem to find the optimal solution.

(3) Taking advantage of the structure of the task mapping problem, we propose a novel three-step heuristic to find the solutions. First, a dynamic programming-based task allocation heuristic is applied to find the task-to-core decision. Then, the improved feasibility-pump heuristic is used to determine the frequency assignment and the edge scheduling. Finally, we calculate the precise contention slack time and adjust frequencies on cores within the task deadlines to reduce energy.

(4) We perform simulations on randomly generated task sets and realistic application task sets to evaluate the performance of our method in terms of energy consumption, task reliability, and communication contention. Compared to the state-of-the-art methods [6] and [21], our method achieves 31.6% and 21.7% energy reduction and has 95.5% and 98.6% lower average contention, while balancing workload and satisfying reliability constraints. In addition, compared to the optimal solution, our method has a polynomial computation time, but with only 24.8% lower energy efficiency.

The remainder of this paper is organized as follows. Section II discusses the related work. Section III presents a contention- and reliability-aware task mapping problem. Section IV describes the proposed three-step heuristic. Section V shows the simulation results, and Section VI concludes this paper.

## II. RELATED WORK

To improve system efficiency, such as achieving energy and communication efficiency and reliability, task mapping on NoC-based MPSoCs has gained significant attention in recent years.

<table><caption>TABLE I COMPARISON OF RELATED WORKS</caption><thead><tr><th>Ref.</th><th>Optimization objectives</th><th>RA</th><th>CA</th><th>LB</th></tr></thead><tbody><tr><td>[27]</td><td>Energy</td><td>x</td><td>x</td><td>x</td></tr><tr><td>[16]</td><td>Energy</td><td>x</td><td>x</td><td>x</td></tr><tr><td>[21]</td><td>Energy</td><td>√</td><td>x</td><td>x</td></tr><tr><td>[28]</td><td>Task Replication Overhead</td><td>√</td><td>x</td><td>x</td></tr><tr><td>[20]</td><td>Energy</td><td>√</td><td>x</td><td>x</td></tr><tr><td>[29]</td><td>Energy + Temperature</td><td>√</td><td>x</td><td>x</td></tr><tr><td>[6]</td><td>Latency</td><td>x</td><td>√</td><td>x</td></tr><tr><td>[30]</td><td>Latency</td><td>x</td><td>√</td><td>x</td></tr><tr><td>[31]</td><td>Makespan</td><td>x</td><td>√</td><td>x</td></tr><tr><td>[13]</td><td>Makespan</td><td>x</td><td>√</td><td>x</td></tr><tr><td>[32]</td><td>Energy + Latency</td><td>x</td><td>√</td><td>x</td></tr><tr><td>[15]</td><td>Energy + Latency</td><td>x</td><td>√</td><td>x</td></tr><tr><td>[14]</td><td>Energy</td><td>x</td><td>√</td><td>x</td></tr><tr><td>[18]</td><td>Energy + Reliability + Latency</td><td>√</td><td>x</td><td>x</td></tr><tr><td>[19]</td><td>Energy + Reliability + Latency</td><td>√</td><td>√</td><td>x</td></tr><tr><td>[22]</td><td>Communication Efficiency + Workload</td><td>x</td><td>x</td><td>√</td></tr><tr><td>[33]</td><td>Energy + Execution Time + Workload</td><td>√</td><td>x</td><td>√</td></tr><tr><td>[34]</td><td>Energy + Makespan + Contention</td><td>x</td><td>√</td><td>√</td></tr><tr><td>Pro.</td><td>Minimize Energy + Balance Workload</td><td>√</td><td>√</td><td>√</td></tr></tbody></table>

Table I summarizes some representative works of task mapping on NoC-based MPSoCs, which include Reliability Awareness (RA), Contention Awareness (CA), and Load Balance (LB).

Energy efficiency is essential in NoC-based MPSoCs, especially for battery-powered mobile embedded systems [16]. Several works have studied energy-aware task scheduling on NoC-based MPSoCs [16], [27] to minimize the total energy of computation and communication under real-time constraints. However, using low operating frequency to execute tasks may impact task reliability, increasing the appearance of transient faults. To address this issue, some approaches introduce reliability constraints into energy-aware task mapping problem [20], [21]. For transient faults occurring on cores, a fixed fault-tolerant policy is applied [21], where tasks are duplicated, and frequencies are adjusted simultaneously. To mitigate the transient faults while improving real-time response, a fault-tolerant method selects from several policies, i.e., checkpointing, task replication, and checkpointing with task replication techniques [20]. A fault-tolerant mechanism based on the backup copy that simultaneously optimizes temperature and energy consumption is proposed in [29]. The primary task and backup copy are executed on the primary and backup cores, respectively, and the backup cores are used only when failures exist in the primary cores. However, task replication introduces replicas, which increases computation and communication costs. To minimize task replicas and latency, [28] jointly addresses transient faults of cores, links, and routers on NoCs.

Communication latency is another critical issue, as it affects the execution time of mapped applications, especially for real-time applications [6]. To minimize the communication latency, approaches focus on the link contention between data transfers over NoC [6], [30], [31]. In [6], [30], contention metrics are introduced to identify the links of NoC with high loads, which are prone to suffer congestion. The latency can be minimized by bypassing the congested links. The communications with potential contentions are prioritized, and priorities are used to reduce the makespan [31]. However, the above methods only consider optimizing communication efficiency, whereas energy
stay active most of the time while the remaining cores are idle. To obtain an efficient system, we must simultaneously alleviate network contention, balance workload, and improve energy efficiency and reliability.

To address the above issues, we propose a novel task mapping method to jointly optimize energy efficiency through DVFS while balancing the workload and mitigating the communication contention on the NoC-based platform under real-time and reliability constraints. Therefore, our method is suitable for applications with energy efficiency, reliability, and timeliness requirements, such as autonomous drones [25], and video processing systems [26]. The main contributions of this paper are summarized as follows:

(1) We holistically model the problem of reducing energy consumption and balancing the workload for NoC-based platforms. DVFS adjusts the V/F levels of cores and links, reducing the total energy consumption under real-time and reliability constraints. Communication contention is considered, where flexible slack time alleviates communication contention, reducing latency.

(2) Based on the system model, the task mapping problem is formulated as a mixed-integer nonlinear programming (MINLP) problem, with the aim to minimize energy consumption and balance workload under multiple constraints. We apply the linearization method by introducing auxiliary variables and additional constraints and then equivalently transform the original problem into a mixed-integer linear programming (MILP) problem to find the optimal solution.

(3) Taking advantage of the structure of the task mapping problem, we propose a novel three-step heuristic to find the solutions. First, a dynamic programming-based task allocation heuristic is applied to find the task-to-core decision. Then, the improved feasibility-pump heuristic is used to determine the frequency assignment and the edge scheduling. Finally, we calculate the precise contention slack time and adjust frequencies on cores within the task deadlines to reduce energy.

(4) We perform simulations on randomly generated task sets and realistic application task sets to evaluate the performance of our method in terms of energy consumption, task reliability, and communication contention. Compared to the state-of-the-art methods [6] and [21], our method achieves 31.6% and 21.7% energy reduction and has 95.5% and 98.6% lower average contention, while balancing workload and satisfying reliability constraints. In addition, compared to the optimal solution, our method has a polynomial computation time, but with only 24.8% lower energy efficiency.

The remainder of this paper is organized as follows. Section II discusses the related work. Section III presents a contention- and reliability-aware task mapping problem. Section IV describes the proposed three-step heuristic. Section V shows the simulation results, and Section VI concludes this paper.

## II. RELATED WORK

To improve system efficiency, such as achieving energy and communication efficiency and reliability, task mapping on NoC-based MPSoCs has gained significant attention in recent years.

<table><caption>TABLE I COMPARISON OF RELATED WORKS</caption><thead><tr><th>Ref.</th><th>Optimization objectives</th><th>RA</th><th>CA</th><th>LB</th></tr></thead><tbody><tr><td>[27]</td><td>Energy</td><td>x</td><td>x</td><td>x</td></tr><tr><td>[16]</td><td>Energy</td><td>x</td><td>x</td><td>x</td></tr><tr><td>[21]</td><td>Energy</td><td>√</td><td>x</td><td>x</td></tr><tr><td>[28]</td><td>Task Replication Overhead</td><td>√</td><td>x</td><td>x</td></tr><tr><td>[20]</td><td>Energy</td><td>√</td><td>x</td><td>x</td></tr><tr><td>[29]</td><td>Energy + Temperature</td><td>√</td><td>x</td><td>x</td></tr><tr><td>[6]</td><td>Latency</td><td>x</td><td>√</td><td>x</td></tr><tr><td>[30]</td><td>Latency</td><td>x</td><td>√</td><td>x</td></tr><tr><td>[31]</td><td>Makespan</td><td>x</td><td>√</td><td>x</td></tr><tr><td>[13]</td><td>Makespan</td><td>x</td><td>√</td><td>x</td></tr><tr><td>[32]</td><td>Energy + Latency</td><td>x</td><td>√</td><td>x</td></tr><tr><td>[15]</td><td>Energy + Latency</td><td>x</td><td>√</td><td>x</td></tr><tr><td>[14]</td><td>Energy</td><td>x</td><td>√</td><td>x</td></tr><tr><td>[18]</td><td>Energy + Reliability + Latency</td><td>√</td><td>x</td><td>x</td></tr><tr><td>[19]</td><td>Energy + Reliability + Latency</td><td>√</td><td>√</td><td>x</td></tr><tr><td>[22]</td><td>Communication Efficiency + Workload</td><td>x</td><td>x</td><td>√</td></tr><tr><td>[33]</td><td>Energy + Execution Time + Workload</td><td>√</td><td>x</td><td>√</td></tr><tr><td>[34]</td><td>Energy + Makespan + Contention</td><td>x</td><td>√</td><td>√</td></tr><tr><td>Pro.</td><td>Minimize Energy + Balance Workload</td><td>√</td><td>√</td><td>√</td></tr></tbody></table>

Table I summarizes some representative works of task mapping on NoC-based MPSoCs, which include Reliability Awareness (RA), Contention Awareness (CA), and Load Balance (LB).

Energy efficiency is essential in NoC-based MPSoCs, especially for battery-powered mobile embedded systems [16]. Several works have studied energy-aware task scheduling on NoC-based MPSoCs [16], [27] to minimize the total energy of computation and communication under real-time constraints. However, using low operating frequency to execute tasks may impact task reliability, increasing the appearance of transient faults. To address this issue, some approaches introduce reliability constraints into energy-aware task mapping problem [20], [21]. For transient faults occurring on cores, a fixed fault-tolerant policy is applied [21], where tasks are duplicated, and frequencies are adjusted simultaneously. To mitigate the transient faults while improving real-time response, a fault-tolerant method selects from several policies, i.e., checkpointing, task replication, and checkpointing with task replication techniques [20]. A fault-tolerant mechanism based on the backup copy that simultaneously optimizes temperature and energy consumption is proposed in [29]. The primary task and backup copy are executed on the primary and backup cores, respectively, and the backup cores are used only when failures exist in the primary cores. However, task replication introduces replicas, which increases computation and communication costs. To minimize task replicas and latency, [28] jointly addresses transient faults of cores, links, and routers on NoCs.

Communication latency is another critical issue, as it affects the execution time of mapped applications, especially for real-time applications [6]. To minimize the communication latency, approaches focus on the link contention between data transfers over NoC [6], [30], [31]. In [6], [30], contention metrics are introduced to identify the links of NoC with high loads, which are prone to suffer congestion. The latency can be minimized by bypassing the congested links. The communications with potential contentions are prioritized, and priorities are used to reduce the makespan [31]. However, the above methods only consider optimizing communication efficiency, whereas energy
efficiency and reliability are not considered.

Considering network contention, several works [13]–[15], [32], [34] jointly optimize energy and latency. Few works also take into account reliability [18], [19]. Considering energy- and contention-aware task mapping on NoCs, the communication latency is optimized in [13], [32] by adding a fixed latency time into task scheduling, where the fixed latency time is calculated by the worst congestion estimation to alleviate the impact caused by link congestion. Energy consumption can be further reduced through task mapping and DVFS. However, introducing a fixed latency time may postpone task completion time. Therefore, optimizing task assignment and operation frequency can help in meeting task deadlines. Communications with contentions are prioritized to minimize energy consumption [14], [15], [31]. Compared to [14] that only considers DVFS, [15] integrates DVFS and DPM (Dynamic Power Management) techniques together to reduce further energy consumption. The optimization of the communication energy, reliability, and latency on NoCs is proposed in [18] by assigning the tasks onto a redundant core to avoid faulty links. Remapping and wait mechanisms are applied to solve the faults on cores, links, and routers while introducing fixed waiting time due to congestion into the scheduling [19]. However, the methods mentioned above only consider communication energy, more overhead is introduced for task remapping, they require redundant NoC hardware, and they omit the workload balance.

Regarding workload balance, it is optimized to improve the system [22], [33], [34]. For instance, a trade-off task mapping method balances workload and communication efficiency to reduce task execution time in [22]. Considering faults on routers, task reliability is tackled simultaneously considering energy consumption, execution time, and load balancing [33], but without network contention. An optimization method considering energy, makespan, and contention is proposed to avoid spatial and temporal contentions in [34]. However, the frequency adjustment and real-time constraints are not taken into account. Compared to the state-of-the-art methods in Table I, our work minimizes energy consumption and balances workload under real-time and reliability constraints while alleviating the network contention on the NoC-based platform.

### III. SYSTEM MODEL AND PROBLEM FORMULATION

#### A. System Model

1) **NoC Model:** The target platform is a 2D mesh NoC-based homogeneous MPSoCs, as it is widely used in current NoC architecture [13], [14], [27]. The platform has a set $\mathcal{P} \triangleq \{P_1, \dots, P_M\}$ of $M$ cores, and a set $\mathcal{R} \triangleq \{R_1, \dots, R_M\}$ of $M$ corresponding routers. For a 2D mesh NoC topology, as shown in Fig. 1(a), each router $R_s$ has five I/O ports, where four ports are linked to the neighboring routers, while one is associated with the corresponding core $P_s$ [13]. In addition, each port has a link and a buffer to transmit and store the data, respectively. All the cores and links in the NoC platform are DVFS-enabled. Each core can operate on a set $\{(v_{p,1}, f_{p,1}), \dots, (v_{p,N_p}, f_{p,N_p})\}$ of $N_p$ discrete V/F levels, where $(v_{p,k}, f_{p,k})$ denotes the $k^{th}$ V/F level of the core ($1 \le k \le N_p$). Similarly, each link can operate at a set $\{(v_{l,1}, f_{l,1}), \dots, (v_{l,N_l}, f_{l,N_l})\}$ of $N_l$ discrete

V/F levels, and $(v_{l,g}, f_{l,g})$ denotes the $g^{th}$ V/F level of the link ($1 \le g \le N_l$). We adopt the deterministic XY routing, a popular routing method on 2D mesh NoC [13], [14], [27]. The routing set of physical links between cores $P_s$ and $P_d$ is $\mathcal{L}_{s,d} \triangleq \{l_{s,i}, \dots, l_{j,d}\}$, where $l_{s,i}$ (or $l_{j,d}$) denotes the physical link between cores $P_s$ and $P_i$ (or cores $P_j$ and $P_d$), and each link $l_{s,d}$ is full duplex with a bandwidth $b_\omega$. The distance between $P_s$ and $P_d$ represents the number of links in the set $\mathcal{L}_{s,d}$, and it can be measured by the Manhattan distance $h_{s,d} = |x_s - x_d| + |y_s - y_d|$, where $(x_s, y_s)$ and $(x_d, y_d)$ are the coordinates of cores $P_s$ and $P_d$ in a mesh-based NoC, respectively, as the example shown in Fig. 1(a).

2) **Task Model:** A real-time application with $N$ dependent tasks is modeled as a Directed Acyclic Graph (DAG) with 6-tuple elements $\{\mathcal{T}, \mathcal{E}, \mathcal{S}, \mathcal{W}, \mathcal{D}, \mathcal{H}\}$. $\mathcal{T} \triangleq \{\tau_1, \dots, \tau_N\}$ is a real-time task set with $N$ tasks. $\mathcal{E}$ denotes the set of edges, where each edge $e_{i,j}$ represents the dependency between tasks $\tau_i$ and $\tau_j$. Each edge has a weight $s_{i,j} \in \mathcal{S}$, representing the size of communication data between $\tau_i$ and $\tau_j$. Each task $\tau_i$ has $\omega_i \in \mathcal{W}$ cycles, measured by Worst-Case Execution Cycles (WCEC). Task $\tau_i$ is released at time 0 and has an individual deadline $D_i \in \mathcal{D}$. $\mathcal{H}$ is the scheduling horizon, which is also the period of task $\tau_i$. Due to the dependency, each task $\tau_i$ cannot start execution until all its predecessors' input data has arrived. At the same time, the output data is concurrently available for transmission to all its successors only when it completes execution.

We consider the transmission time over links for task data communication since the extra overheads (e.g., data copy between buffers and inter-router delay) are negligible compared with the transmission time [13]. Besides, we consider that the transmission time is increased with the routing distance. For the edge $e_{i,j}$, if the data with the size $s_{i,j}$ is transmitted from $\tau_i$ to $\tau_j$ by one unit link, the link transmission time with the V/F level $(v_{l,g}, f_{l,g})$ is calculated as

$$t_{i,j,g}^{UL} = s_{i,j}/(b_{\omega}f_{l,g}), \quad \forall e_{i,j} \in \mathcal{E}, \ 1 \le g \le N_l. \quad (1)$$

If the routing distance is more than one unit, e.g., tasks $\tau_i$ and $\tau_j$ are assigned to different cores $P_s$ and $P_d$, and the routing distance associated with the edge $e_{i,j}$ is $h_{s,d}$, the transmission time with the V/F level $(v_{l,g}, f_{l,g})$ is computed as $t_{i,j,g}^{L} = h_{s,d}t_{i,j,g}^{UL}$. If two tasks are assigned to the same core, the communication cost between them is assumed to be zero.

3) **Energy Model:** Since each core and link can operate on different V/F levels, switching brings extra overhead to energy consumption and execution time. Compared with the energy and time required for task execution and data communication, the switching overhead is very small, especially when the switching rate is low. Hence, we omit the overhead of frequency switching [14], [16], [27]. We consider the power dissipation by computation and communication in the power model. Given the V/F level $(v_{p,k}, f_{p,k})$, the computation power $P_k^{comp}$ dissipated in executing tasks is computed as follows [27]:

$$P_k^{comp} = \underbrace{C_{eff} v_{p,k}^2 f_{p,k}}_{\text{dynamic power}} + \underbrace{L_g (v_{p,k} I_{sub} + |v_{bs}| I_j)}_{\text{static power}}, \quad (2)$$

where $C_{eff}$, $L_g$, $I_{sub}$, $v_{bs}$, and $I_j$ denotes the effective switching capacitance, the number of devices in the circuit, the sub-threshold leakage current, the body bias voltage, and the reverse
efficiency and reliability are not considered.

Considering network contention, several works [13]–[15], [32], [34] jointly optimize energy and latency. Few works also take into account reliability [18], [19]. Considering energy- and contention-aware task mapping on NoCs, the communication latency is optimized in [13], [32] by adding a fixed latency time into task scheduling, where the fixed latency time is calculated by the worst congestion estimation to alleviate the impact caused by link congestion. Energy consumption can be further reduced through task mapping and DVFS. However, introducing a fixed latency time may postpone task completion time. Therefore, optimizing task assignment and operation frequency can help in meeting task deadlines. Communications with contentions are prioritized to minimize energy consumption [14], [15], [31]. Compared to [14] that only considers DVFS, [15] integrates DVFS and DPM (Dynamic Power Management) techniques together to reduce further energy consumption. The optimization of the communication energy, reliability, and latency on NoCs is proposed in [18] by assigning the tasks onto a redundant core to avoid faulty links. Remapping and wait mechanisms are applied to solve the faults on cores, links, and routers while introducing fixed waiting time due to congestion into the scheduling [19]. However, the methods mentioned above only consider communication energy, more overhead is introduced for task remapping, they require redundant NoC hardware, and they omit the workload balance.

Regarding workload balance, it is optimized to improve the system [22], [33], [34]. For instance, a trade-off task mapping method balances workload and communication efficiency to reduce task execution time in [22]. Considering faults on routers, task reliability is tackled simultaneously considering energy consumption, execution time, and load balancing [33], but without network contention. An optimization method considering energy, makespan, and contention is proposed to avoid spatial and temporal contentions in [34]. However, the frequency adjustment and real-time constraints are not taken into account. Compared to the state-of-the-art methods in Table I, our work minimizes energy consumption and balances workload under real-time and reliability constraints while alleviating the network contention on the NoC-based platform.

### III. SYSTEM MODEL AND PROBLEM FORMULATION

#### A. System Model

1) **NoC Model:** The target platform is a 2D mesh NoC-based homogeneous MPSoCs, as it is widely used in current NoC architecture [13], [14], [27]. The platform has a set $\mathcal{P} \triangleq \{P_1, \dots, P_M\}$ of $M$ cores, and a set $\mathcal{R} \triangleq \{R_1, \dots, R_M\}$ of $M$ corresponding routers. For a 2D mesh NoC topology, as shown in Fig. 1(a), each router $R_s$ has five I/O ports, where four ports are linked to the neighboring routers, while one is associated with the corresponding core $P_s$ [13]. In addition, each port has a link and a buffer to transmit and store the data, respectively. All the cores and links in the NoC platform are DVFS-enabled. Each core can operate on a set $\{(v_{p,1}, f_{p,1}), \dots, (v_{p,N_p}, f_{p,N_p})\}$ of $N_p$ discrete V/F levels, where $(v_{p,k}, f_{p,k})$ denotes the $k^{th}$ V/F level of the core ($1 \le k \le N_p$). Similarly, each link can operate at a set $\{(v_{l,1}, f_{l,1}), \dots, (v_{l,N_l}, f_{l,N_l})\}$ of $N_l$ discrete

V/F levels, and $(v_{l,g}, f_{l,g})$ denotes the $g^{th}$ V/F level of the link ($1 \le g \le N_l$). We adopt the deterministic XY routing, a popular routing method on 2D mesh NoC [13], [14], [27]. The routing set of physical links between cores $P_s$ and $P_d$ is $\mathcal{L}_{s,d} \triangleq \{l_{s,i}, \dots, l_{j,d}\}$, where $l_{s,i}$ (or $l_{j,d}$) denotes the physical link between cores $P_s$ and $P_i$ (or cores $P_j$ and $P_d$), and each link $l_{s,d}$ is full duplex with a bandwidth $b_\omega$. The distance between $P_s$ and $P_d$ represents the number of links in the set $\mathcal{L}_{s,d}$, and it can be measured by the Manhattan distance $h_{s,d} = |x_s - x_d| + |y_s - y_d|$, where $(x_s, y_s)$ and $(x_d, y_d)$ are the coordinates of cores $P_s$ and $P_d$ in a mesh-based NoC, respectively, as the example shown in Fig. 1(a).

2) **Task Model:** A real-time application with $N$ dependent tasks is modeled as a Directed Acyclic Graph (DAG) with 6-tuple elements $\{\mathcal{T}, \mathcal{E}, \mathcal{S}, \mathcal{W}, \mathcal{D}, \mathcal{H}\}$. $\mathcal{T} \triangleq \{\tau_1, \dots, \tau_N\}$ is a real-time task set with $N$ tasks. $\mathcal{E}$ denotes the set of edges, where each edge $e_{i,j}$ represents the dependency between tasks $\tau_i$ and $\tau_j$. Each edge has a weight $s_{i,j} \in \mathcal{S}$, representing the size of communication data between $\tau_i$ and $\tau_j$. Each task $\tau_i$ has $\omega_i \in \mathcal{W}$ cycles, measured by Worst-Case Execution Cycles (WCEC). Task $\tau_i$ is released at time 0 and has an individual deadline $D_i \in \mathcal{D}$. $\mathcal{H}$ is the scheduling horizon, which is also the period of task $\tau_i$. Due to the dependency, each task $\tau_i$ cannot start execution until all its predecessors' input data has arrived. At the same time, the output data is concurrently available for transmission to all its successors only when it completes execution.

We consider the transmission time over links for task data communication since the extra overheads (e.g., data copy between buffers and inter-router delay) are negligible compared with the transmission time [13]. Besides, we consider that the transmission time is increased with the routing distance. For the edge $e_{i,j}$, if the data with the size $s_{i,j}$ is transmitted from $\tau_i$ to $\tau_j$ by one unit link, the link transmission time with the V/F level $(v_{l,g}, f_{l,g})$ is calculated as

$$t_{i,j,g}^{UL} = s_{i,j}/(b_{\omega}f_{l,g}), \quad \forall e_{i,j} \in \mathcal{E}, \ 1 \le g \le N_l. \quad (1)$$

If the routing distance is more than one unit, e.g., tasks $\tau_i$ and $\tau_j$ are assigned to different cores $P_s$ and $P_d$, and the routing distance associated with the edge $e_{i,j}$ is $h_{s,d}$, the transmission time with the V/F level $(v_{l,g}, f_{l,g})$ is computed as $t_{i,j,g}^{L} = h_{s,d}t_{i,j,g}^{UL}$. If two tasks are assigned to the same core, the communication cost between them is assumed to be zero.

3) **Energy Model:** Since each core and link can operate on different V/F levels, switching brings extra overhead to energy consumption and execution time. Compared with the energy and time required for task execution and data communication, the switching overhead is very small, especially when the switching rate is low. Hence, we omit the overhead of frequency switching [14], [16], [27]. We consider the power dissipation by computation and communication in the power model. Given the V/F level $(v_{p,k}, f_{p,k})$, the computation power $P_k^{comp}$ dissipated in executing tasks is computed as follows [27]:

$$P_k^{comp} = \underbrace{C_{eff} v_{p,k}^2 f_{p,k}}_{\text{dynamic power}} + \underbrace{L_g (v_{p,k} I_{sub} + |v_{bs}| I_j)}_{\text{static power}}, \quad (2)$$

where $C_{eff}$, $L_g$, $I_{sub}$, $v_{bs}$, and $I_j$ denotes the effective switching capacitance, the number of devices in the circuit, the sub-threshold leakage current, the body bias voltage, and the reverse
<figure><img src="image_2.png" /><figcaption>Fig. 1. An example of task mapping with communication contention.</figcaption></figure>

bias junction current, respectively. Besides the V/F level, the operating temperature also influences the static power. In this paper, we did not consider temperature, as it will introduce another dimension of variables into the task mapping problem, making it more difficult to solve. Instead, we mainly focus on optimizing energy efficiency, reliability, and communication contention, similar to the existing works [16], [20], [21].

The following link power model is adopted from [27]:

$$P_g^{\text{link}} = s_a C_{\text{rep}} v_{l,g}^2 f_{l,g} + L_g (v_{l,g} K_3 e^{K_4 v_{l,g}} e^{K_5 v_{bs}} + |v_{bs}| I_j), \quad (3)$$

where $s_a$ is the average switching activity, $C_{\text{rep}}$ is capacity load of a repeater, and $K_3$, $K_4$ and $K_5$ are hardware parameters.

Note that the routers and the links on NoC mainly consume communication energy. The communication energy for edge $e_{i,j}$ with the data size $s_{i,j}$ from core $P_s$ to $P_d$, if it is operated at the V/F level ($v_{l,g}, f_{l,g}$) [14], [27], is given by:

$$E_g^{\text{comm}} = s_{i,j} [(h_{s,d} + 1)E_{Rbit} + h_{s,d}E_{Lbit,g}], \quad (4)$$

where $E_{Rbit}$ is the energy consumption of transmitting a bit data on a router, and $E_{Lbit,g} = P_g^{\text{link}}/b_\omega f_{l,g}$ is the energy consumed by transmitting a bit data over a link with the frequency $f_{l,g}$. Since $h_{s,d}$ is the number of the links that a bit data passes during the communication, $h_{s,d} + 1$ is the number of routers that a bit data passes. On this basis, $(h_{s,d} + 1)E_{Rbit}$ is the energy consumption of transmitting a bit data for routes, while $h_{s,d}E_{Lbit,g}$ is the energy consumption of transmitting a bit data with the V/F ($v_{l,g}, f_{l,g}$) on links.

4) Communication Contention Model: In NoC, any physical link can only transmit one message at the same time; otherwise, communication contention occurs, leading to data transmission blocking and system performance degradation. The existence of communication contention should satisfy the time and space constraints. For instance, we assume that tasks $\tau_i$, $\tau_j$, $\tau_m$, $\tau_n$, and $\tau_v$ are assigned to cores $P_s$, $P_d$, $P_p$, $P_q$, and $P_f$, respectively. For these dependent tasks, the routing sets of the communication for the edges $e_{i,j}$, $e_{m,n}$, and $e_{v,j}$ are $\mathcal{L}_{s,d}$, $\mathcal{L}_{p,q}$, and $\mathcal{L}_{f,d}$, as shown in Fig. 1(a).

The communication contention in time is defined as the overlap of communication time for different edges, such as edges $e_{i,j}$ and $e_{m,n}$ in Fig. 1(b). If there is a communication time overlapping among $e_{i,j}$ and $e_{m,n}$, the contention constraints in time can be expressed as $ts_{i,j} < te_{m,n}$ and $ts_{m,n} < te_{i,j}$, where $ts_{i,j}$ and $ts_{m,n}$ ($te_{i,j}$ and $te_{m,n}$) denote the start time (end time) of data transmission for edge $e_{i,j}$ and $e_{m,n}$.

To indicate the sequence between $e_{i,j}$ and $e_{m,n}$, we introduce a binary variable $\eta_{i,j,m,n}$, where $\eta_{i,j,m,n} = 1$ denotes that edge

$e_{i,j}$ begins communication before $e_{m,n}$ completes, otherwise, $\eta_{i,j,m,n} = 0$. Note that the value of $\eta_{i,j,m,n}$ is influenced by the start time and the end time of the edges $e_{i,j}$ and $e_{m,n}$, the relationship between them can be represented as

$$(te_{m,n} - ts_{i,j})/Z \le \eta_{i,j,m,n} \le (te_{m,n} - ts_{i,j})/Z + 1, \quad (5)$$

$$(te_{i,j} - ts_{m,n})/Z \le \eta_{m,n,i,j} \le (te_{i,j} - ts_{m,n})/Z + 1, \quad (6)$$

$$e_{i,j} \neq e_{m,n} \in \mathcal{E}, \eta_{i,j,m,n}, \eta_{m,n,i,j} \in \{0, 1\},$$

where Z is a large positive integer. When $ts_{i,j} < te_{m,n}$ holds, (5) is relaxed to $\eta_{i,j,m,n} = 1$. Similarly, when $ts_{m,n} < te_{i,j}$ holds, (6) can be transformed into $\eta_{m,n,i,j} = 1$. As the example shown in Fig. 1(b), since there is a time overlap between the edges $e_{i,j}$ and $e_{m,n}$, we have $\eta_{i,j,m,n} = \eta_{m,n,i,j} = 1$.

The communication contention in space is defined that the routing sets of the edges have at least one shared link, e.g., in Fig. 1(a), for the edges $e_{i,j}$ and $e_{m,n}$, we have $\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q} \neq \emptyset$, where $\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q}$ denotes the common links between the routing sets of the edges $e_{i,j}$ and $e_{m,n}$. Hence, the communication contention occurs between the edges $e_{i,j}$ and $e_{m,n}$.

To alleviate the contention, we add flexible slack time into the communication process to ensure that the congested data can be transmitted sequentially. The slack time with a fixed value will generate additional idle time on cores, increasing energy consumption [13], [32]. In this paper, we set slack time as an adaptive value, which depends on the communication cost of overlapping links.

The slack time $t_{i,j}^{\text{slack}}$ and $t_{m,n}^{\text{slack}}$ for the edges $e_{i,j}$ and $e_{m,n}$ can be given by:

$$e_{i,j} \neq e_{m,n} \in \mathcal{E}, P_s \neq P_d, P_p \neq P_q \in \mathcal{P}, t_{i,j}^{\text{slack}}, t_{m,n}^{\text{slack}} \ge 0, \\ t_{i,j}^{\text{slack}}, t_{m,n}^{\text{slack}} \ge |\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q}| \cdot \max \left\{ \overline{t_{i,j}^{\text{UL}}}, \overline{t_{m,n}^{\text{UL}}} \right\} - Z(6 - x_{i,s} - x_{j,d} - x_{m,p} - x_{n,q} - \eta_{i,j,m,n} - \eta_{m,n,i,j}), \quad (7)$$

where $|\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q}|$ denotes the number of overlapping links between the edges $e_{i,j}$ and $e_{m,n}$; binary variable $x_{i,s} = 1$ denotes task $\tau_i$ is assigned to core $P_s$, otherwise, $x_{i,s} = 0$; binary variable $c_{i,j,g}^L = 1$ denotes the message for edge $e_{i,j}$ is transmitted with ($v_{l,g}, f_{l,g}$), otherwise, $c_{i,j,g}^L = 0$; $\overline{t_{i,j}^{UL}} = \sum_{g \in \mathcal{N}_i} c_{i,j,g}^L \overline{t_{i,j,g}^{UL}}$ is the transmission time on one unit link for the edge $e_{i,j}$. Similarly, for the edge $e_{m,n}$ we have $\overline{t_{m,n}^{UL}} = \sum_{g \in \mathcal{N}_i} c_{m,n,g}^L \overline{t_{m,n,g}^{UL}}$.

As the example shown in Fig. 1, we have $x_{i,s} = x_{j,d} = x_{m,p} = x_{n,q} = x_{v,f} = 1$. When contention constraints in time and space are satisfied, i.e., $\eta_{i,j,m,n} = \eta_{m,n,i,j} = 1$
<figure><img src="image_4.png" /><figcaption>Fig. 1. An example of task mapping with communication contention.</figcaption></figure>

bias junction current, respectively. Besides the V/F level, the operating temperature also influences the static power. In this paper, we did not consider temperature, as it will introduce another dimension of variables into the task mapping problem, making it more difficult to solve. Instead, we mainly focus on optimizing energy efficiency, reliability, and communication contention, similar to the existing works [16], [20], [21].

The following link power model is adopted from [27]:

$$P_g^{\text{link}} = s_a C_{\text{rep}} v_{l,g}^2 f_{l,g} + L_g (v_{l,g} K_3 e^{K_4 v_{l,g}} e^{K_5 v_{bs}} + |v_{bs}| I_j), \quad (3)$$

where $s_a$ is the average switching activity, $C_{\text{rep}}$ is capacity load of a repeater, and $K_3$, $K_4$ and $K_5$ are hardware parameters.

Note that the routers and the links on NoC mainly consume communication energy. The communication energy for edge $e_{i,j}$ with the data size $s_{i,j}$ from core $P_s$ to $P_d$, if it is operated at the V/F level ($v_{l,g}, f_{l,g}$) [14], [27], is given by:

$$E_g^{\text{comm}} = s_{i,j} [(h_{s,d} + 1)E_{Rbit} + h_{s,d}E_{Lbit,g}], \quad (4)$$

where $E_{Rbit}$ is the energy consumption of transmitting a bit data on a router, and $E_{Lbit,g} = P_g^{\text{link}}/b_\omega f_{l,g}$ is the energy consumed by transmitting a bit data over a link with the frequency $f_{l,g}$. Since $h_{s,d}$ is the number of the links that a bit data passes during the communication, $h_{s,d} + 1$ is the number of routers that a bit data passes. On this basis, $(h_{s,d} + 1)E_{Rbit}$ is the energy consumption of transmitting a bit data for routes, while $h_{s,d}E_{Lbit,g}$ is the energy consumption of transmitting a bit data with the V/F ($v_{l,g}, f_{l,g}$) on links.

### 4) Communication Contention Model
In NoC, any physical link can only transmit one message at the same time; otherwise, communication contention occurs, leading to data transmission blocking and system performance degradation. The existence of communication contention should satisfy the time and space constraints. For instance, we assume that tasks $\tau_i$, $\tau_j$, $\tau_m$, $\tau_n$, and $\tau_v$ are assigned to cores $P_s, P_d, P_p, P_q$, and $P_f$, respectively. For these dependent tasks, the routing sets of the communication for the edges $e_{i,j}$, $e_{m,n}$, and $e_{v,j}$ are $\mathcal{L}_{s,d}$, $\mathcal{L}_{p,q}$, and $\mathcal{L}_{f,d}$, as shown in Fig. 1(a).

The communication contention in time is defined as the overlap of communication time for different edges, such as edges $e_{i,j}$ and $e_{m,n}$ in Fig. 1(b). If there is a communication time overlapping among $e_{i,j}$ and $e_{m,n}$, the contention constraints in time can be expressed as $ts_{i,j} < te_{m,n}$ and $ts_{m,n} < te_{i,j}$, where $ts_{i,j}$ and $ts_{m,n}$ ($te_{i,j}$ and $te_{m,n}$) denote the start time (end time) of data transmission for edge $e_{i,j}$ and $e_{m,n}$.

To indicate the sequence between $e_{i,j}$ and $e_{m,n}$, we introduce a binary variable $\eta_{i,j,m,n}$, where $\eta_{i,j,m,n} = 1$ denotes that edge

$e_{i,j}$ begins communication before $e_{m,n}$ completes, otherwise, $\eta_{i,j,m,n} = 0$. Note that the value of $\eta_{i,j,m,n}$ is influenced by the start time and the end time of the edges $e_{i,j}$ and $e_{m,n}$, the relationship between them can be represented as

$$(te_{m,n} - ts_{i,j})/Z \le \eta_{i,j,m,n} \le (te_{m,n} - ts_{i,j})/Z + 1, \quad (5)$$

$$(te_{i,j} - ts_{m,n})/Z \le \eta_{m,n,i,j} \le (te_{i,j} - ts_{m,n})/Z + 1, \quad (6)$$

$$e_{i,j} \neq e_{m,n} \in \mathcal{E}, \eta_{i,j,m,n}, \eta_{m,n,i,j} \in \{0, 1\},$$

where Z is a large positive integer. When $ts_{i,j} < te_{m,n}$ holds, (5) is relaxed to $\eta_{i,j,m,n} = 1$. Similarly, when $ts_{m,n} < te_{i,j}$ holds, (6) can be transformed into $\eta_{m,n,i,j} = 1$. As the example shown in Fig. 1(b), since there is a time overlap between the edges $e_{i,j}$ and $e_{m,n}$, we have $\eta_{i,j,m,n} = \eta_{m,n,i,j} = 1$.

The communication contention in space is defined that the routing sets of the edges have at least one shared link, e.g., in Fig. 1(a), for the edges $e_{i,j}$ and $e_{m,n}$, we have $\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q} \neq \emptyset$, where $\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q}$ denotes the common links between the routing sets of the edges $e_{i,j}$ and $e_{m,n}$. Hence, the communication contention occurs between the edges $e_{i,j}$ and $e_{m,n}$.

To alleviate the contention, we add flexible slack time into the communication process to ensure that the congested data can be transmitted sequentially. The slack time with a fixed value will generate additional idle time on cores, increasing energy consumption [13], [32]. In this paper, we set slack time as an adaptive value, which depends on the communication cost of overlapping links.

The slack time $t_{i,j}^{\text{slack}}$ and $t_{m,n}^{\text{slack}}$ for the edges $e_{i,j}$ and $e_{m,n}$ can be given by:

$$e_{i,j} \neq e_{m,n} \in \mathcal{E}, P_s \neq P_d, P_p \neq P_q \in \mathcal{P}, t_{i,j}^{\text{slack}}, t_{m,n}^{\text{slack}} \ge 0, \\ t_{i,j}^{\text{slack}}, t_{m,n}^{\text{slack}} \ge |\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q}| \cdot \max\left\{\overline{t_{i,j}^{\text{UL}}}, \overline{t_{m,n}^{\text{UL}}}\right\} - Z(6 - x_{i,s} - x_{j,d} - x_{m,p} - x_{n,q} - \eta_{i,j,m,n} - \eta_{m,n,i,j}), \quad (7)$$

where $|\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q}|$ denotes the number of overlapping links between the edges $e_{i,j}$ and $e_{m,n}$; binary variable $x_{i,s} = 1$ denotes task $\tau_i$ is assigned to core $P_s$, otherwise, $x_{i,s} = 0$; binary variable $c_{i,j,g}^L = 1$ denotes the message for edge $e_{i,j}$ is transmitted with ($v_{l,g}, f_{l,g}$), otherwise, $c_{i,j,g}^L = 0$; $\overline{t_{i,j}^{UL}} = \sum_{g \in \mathcal{N}_i} c_{i,j,g}^L \overline{t_{i,j,g}^{UL}}$ is the transmission time on one unit link for the edge $e_{i,j}$. Similarly, for the edge $e_{m,n}$ we have $\overline{t_{m,n}^{UL}} = \sum_{g \in \mathcal{N}_i} c_{m,n,g}^L \overline{t_{m,n,g}^{UL}}$.

As the example shown in Fig. 1, we have $x_{i,s} = x_{j,d} = x_{m,p} = x_{n,q} = x_{v,f} = 1$. When contention constraints in time and space are satisfied, i.e., $\eta_{i,j,m,n} = \eta_{m,n,i,j} = 1$
and $\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q} \neq \emptyset$, the communication contention happens between the edges $e_{i,j}$ and $e_{m,n}$. Therefore, (7) is relaxed to

$$t_{i,j}^{\text{slack}}, t_{m,n}^{\text{slack}} \ge |\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q}| \times \max \left\{ \overline{t_{i,j}^{UL}}, \overline{t_{m,n}^{UL}} \right\}. \quad (8)$$

Note that the edges can operate at different V/F levels, and communication contention could happen over multiple edges simultaneously. For edges $e_{i,j}$ and $e_{m,n}$, the maximum communication time on overlapping links is $|\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q}| \max\{\overline{t_{i,j}^{UL}}, \overline{t_{m,n}^{UL}}\}$. If there is no communication contention, i.e., contention constraints regarding time and space are not satisfied, since $\eta_{i,j,m,n} + \eta_{m,n,i,j} \le 1$ and $\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q} = \emptyset$, we have $-Z(6 - x_{i,s} - x_{j,d} - x_{m,p} - x_{m,q} - \eta_{i,j,m,n} - \eta_{m,n,i,j}) \ll 0$ and $|\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q}| = 0$, and thus, (7) is relaxed to $t_{i,j}^{\text{slack}}, t_{m,n}^{\text{slack}} \ge 0$, which can be ignored since the lower bound of continuous variables $t_{i,j}^{\text{slack}}$ and $t_{m,n}^{\text{slack}}$ is 0. Similarly, for the contention between $e_{i,j}$ and $e_{v,j}$, we can get

$$t_{i,j}^{\text{slack}}, t_{v,j}^{\text{slack}} \ge |\mathcal{L}_{s,d} \cap \mathcal{L}_{f,d}| \times \max \left\{ \overline{t_{i,j}^{UL}}, \overline{t_{v,j}^{UL}} \right\}. \quad (9)$$

When the contention happens over multiple edges concurrently, e.g., $e_{i,j}$, $e_{m,n}$, and $e_{v,j}$ in Fig. 1(b), the lower bound of slack time $t_{i,j}^{\text{slack}}$ should be updated according to (8) and (9), since $t_{i,j}^{\text{slack}}$ is influenced by $t_{m,n}^{\text{slack}}$ and $t_{v,j}^{\text{slack}}$ at the same time.

### 5) Fault-tolerant Model
During the application execution process, several faults can affect the system reliability, e.g., transient faults, intermittent faults, and permanent faults. We mainly focus on transient faults on cores, routers, and links since transient faults have higher rates than intermittent and permanent faults [29]. In addition, a fault on a router may affect the links connected to this router. In the worst case, a fault in any part of a router can be treated as a fault occurring in all the links related to the faulty router [18]. Therefore, we assume that the faults on routers are included in the faults over the links.

We consider that the average rate caused by transient faults is followed by the Poisson distribution [17], [35], [36]. Besides, the fault rate is affected by the voltage the system is run at [17]. Hence, the fault rate with a scaled frequency $f$ can be modeled as $\lambda(f) = \lambda_0 \times 10^{\frac{d(f_{\text{max}}-f)}{f_{\text{max}}-f_{\text{min}}}}$, where $\lambda_0$ is the average fault rate at $f_{\text{max}}$, and $d$ is a positive constant, representing the sensitivity of faults caused by transient faults to DVFS. Thus, the probability of success for a task on a hardware component with fault rate $\lambda(f)$ within the time interval $t$ is $e^{-\lambda(f) \times t}$.

Considering the homogeneity of the NoC platform, we set the fault rates of cores and links as $\lambda_P(f)$ and $\lambda_L(f)$, respectively. The probability of success for task $\tau_i$ with the frequency $f_{p,k}$ on core $P_s$ can be calculated as $r_{i,k}^P = e^{-\lambda_P(f_{p,k}) \times t_{i,k}^P}$, where $t_{i,k}^P = \frac{\omega_i}{f_{p,k}}$ denotes the execution time of task $\tau_i$ with V/F level ($v_{p,k}, f_{p,k}$). Similarly, the probability of successful transmission over one unit link for edge $e_{i,j}$ with the frequency $f_{l,g}$ can be given by $r_{i,j,g}^{UL} = e^{-\lambda_L(f_{l,g}) \times t_{i,j,g}^{UL}}$. In Fig. 1(a), when tasks $\tau_i$ and $\tau_j$ are assigned to cores $P_s$ and $P_d$, respectively, the probability of success for edge $e_{i,j}$ along route $\mathcal{L}_{s,d}$ with the frequency $f_{l,g}$ is $r_{i,j,g}^L = \sum_{s \in \mathcal{M}} \sum_{d \in \mathcal{M}} x_{i,s} x_{j,d} (r_{i,j,g}^{UL})^{h_{s,d}}$, where $(r_{i,j,g}^{UL})^{h_{s,d}}$ represents the reliability probability of route $\mathcal{L}_{s,d}$ containing $h_{s,d}$ links. On this basis, the joint reliability probability of task $\tau_j$ can be calculated as

$$R_j = r_{j,k}^P \times r_{i,j,g}^L \times r_{v,j,g}^L = r_{j,k}^P \prod_{e_{u,j} \in \mathcal{E}} r_{u,j,g}^L, \quad (10)$$

where $\prod_{e_{u,j} \in \mathcal{E}} r_{u,j,g}^L$ denotes the probability of successful transmission between task $\tau_j$ and its predecessors with the frequency $f_{l,g}$. If a task does not have any predecessors, e.g., task $\tau_a$ in Fig. 1(a), we consider only the faults on cores, and thus, the reliability probability of task $\tau_a$ is $R_a = r_{a,k}^P$. To maintain the desired system reliability, each task $\tau_j$ must satisfy its reliability constraints [21], which means the task reliability $R_j$ is greater than the reliability threshold $R_{th}$.

## B. Problem Formulation

This section presents the Mixed-Integer Nonlinear Programming (MINLP) formulation of the contention- and reliability-aware mapping problem. Our goal is to schedule and route each task such that real-time and reliability constraints are satisfied and the system performance (i.e., communication efficiency, energy consumption, and core utilization) is improved. Therefore, we must determine 1) task allocation, 2) frequency assignment, 3) edge scheduling, and 4) communication contention management. To formulate the task mapping problem, we introduce a set of binary and continuous variables, as summarized in Table II. For the sake of paper presentation, let $\mathcal{N} \triangleq \{1, \dots, N\}$, $\mathcal{M} \triangleq \{1, \dots, M\}$, $\mathcal{N}_p \triangleq \{1, \dots, N_p\}$, $\mathcal{N}_l \triangleq \{1, \dots, N_l\}$. The constraint descriptions are as follows:

1) **Task Allocation Constraints:** The task allocation variable $x_{i,s}$ is bounded by

$$\sum_{s \in \mathcal{M}} x_{i,s} = 1, \quad \forall i \in \mathcal{N}, \quad (11)$$

where (11) ensures that each task $\tau_i$ is assigned to a core.

2) **Frequency Assignment Constraints:** Since all cores and links in the target platform support DVFS, for each core and link, we have

$$\sum_{k \in \mathcal{N}_p} c_{i,k}^P = 1, \quad \forall i \in \mathcal{N}, \quad (12)$$

$$\sum_{g \in \mathcal{N}_l} c_{i,j,g}^L = 1, \quad \forall e_{i,j} \in \mathcal{E}, \quad (13)$$

where (12) ensures that a task $\tau_i$ is executed with one V/F core level ($v_{p,k}, f_{p,k}$), and (13) restricts that the message of edge $e_{i,j}$ is transmitted with one V/F link level ($v_{l,g}, f_{l,g}$).

3) **Communication Start Time Constraints:** The message transmission for edges should consider the precedence relations. For example, in Fig. 1(b), when the message for edge $e_{i,j}$ is transmitted from task $\tau_i$ to $\tau_j$, the communication start time $t_{s,i,j}$ is not earlier than the finish time of the predecessor $\tau_i$. Therefore, we have

$$te_i \le t_{s,i,j}, \quad \forall e_{i,j} \in \mathcal{E}. \quad (14)$$

4) **Communication End Time Constraints:** Taking task allocation and DVFS on links during task scheduling into account, the communication time of message $e_{i,j}$ is represented as

$$t_{i,j}^L = \left( \sum_{s \in \mathcal{M}} \sum_{d \in \mathcal{M}} h_{s,d} x_{i,s} x_{j,d} \right) \sum_{g \in \mathcal{N}_l} c_{i,j,g}^L t_{i,j,g}^{UL}, \quad (15)$$

where $\sum_{g \in \mathcal{N}_l} c_{i,j,g}^L t_{i,j,g}^{UL}$ represents the transmission time over one unit link with DVFS, and $\sum_{s \in \mathcal{M}} \sum_{d \in \mathcal{M}} h_{s,d} x_{i,s} x_{j,d}$ is the number of links when transmitting the message for edge $e_{i,j}$.

If the message transmits from $\tau_i$ to $\tau_j$ through $e_{i,j}$, the communication end time $te_{i,j}$ is equal to the sum of communication
and $\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q} \neq \emptyset$, the communication contention happens between the edges $e_{i,j}$ and $e_{m,n}$. Therefore, (7) is relaxed to

$$t_{i,j}^{\text{slack}}, t_{m,n}^{\text{slack}} \ge |\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q}| \times \max \left\{ \overline{t_{i,j}^{\text{UL}}}, \overline{t_{m,n}^{\text{UL}}} \right\}. \quad (8)$$

Note that the edges can operate at different V/F levels, and communication contention could happen over multiple edges simultaneously. For edges $e_{i,j}$ and $e_{m,n}$, the maximum communication time on overlapping links is $|\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q}| \max\{\overline{t_{i,j}^{\text{UL}}}, \overline{t_{m,n}^{\text{UL}}}\}$. If there is no communication contention, i.e., contention constraints regarding time and space are not satisfied, since $\eta_{i,j,m,n} + \eta_{m,n,i,j} \le 1$ and $\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q} = \emptyset$, we have $-Z(6 - x_{i,s} - x_{j,d} - x_{m,p} - x_{m,q} - \eta_{i,j,m,n} - \eta_{m,n,i,j}) \ll 0$ and $|\mathcal{L}_{s,d} \cap \mathcal{L}_{p,q}| = 0$, and thus, (7) is relaxed to $t_{i,j}^{\text{slack}}, t_{m,n}^{\text{slack}} \ge 0$, which can be ignored since the lower bound of continuous variables $t_{i,j}^{\text{slack}}$ and $t_{m,n}^{\text{slack}}$ is 0. Similarly, for the contention between $e_{i,j}$ and $e_{v,j}$, we can get

$$t_{i,j}^{\text{slack}}, t_{v,j}^{\text{slack}} \ge |\mathcal{L}_{s,d} \cap \mathcal{L}_{f,d}| \times \max \left\{ \overline{t_{i,j}^{\text{UL}}}, \overline{t_{v,j}^{\text{UL}}} \right\}. \quad (9)$$

When the contention happens over multiple edges concurrently, e.g., $e_{i,j}$, $e_{m,n}$, and $e_{v,j}$ in Fig. 1(b), the lower bound of slack time $t_{i,j}^{\text{slack}}$ should be updated according to (8) and (9), since $t_{i,j}^{\text{slack}}$ is influenced by $t_{m,n}^{\text{slack}}$ and $t_{v,j}^{\text{slack}}$ at the same time.

### 5) Fault-tolerant Model
During the application execution process, several faults can affect the system reliability, e.g., transient faults, intermittent faults, and permanent faults. We mainly focus on transient faults on cores, routers, and links since transient faults have higher rates than intermittent and permanent faults [29]. In addition, a fault on a router may affect the links connected to this router. In the worst case, a fault in any part of a router can be treated as a fault occurring in all the links related to the faulty router [18]. Therefore, we assume that the faults on routers are included in the faults over the links.

We consider that the average rate caused by transient faults is followed by the Poisson distribution [17], [35], [36]. Besides, the fault rate is affected by the voltage the system is run at [17]. Hence, the fault rate with a scaled frequency $f$ can be modeled as $\lambda(f) = \lambda_0 \times 10^{\frac{d(f_{\text{max}}-f)}{f_{\text{max}}-f_{\text{min}}}}$, where $\lambda_0$ is the average fault rate at $f_{\text{max}}$, and $d$ is a positive constant, representing the sensitivity of faults caused by transient faults to DVFS. Thus, the probability of success for a task on a hardware component with fault rate $\lambda(f)$ within the time interval $t$ is $e^{-\lambda(f) \times t}$.

Considering the homogeneity of the NoC platform, we set the fault rates of cores and links as $\lambda_P(f)$ and $\lambda_L(f)$, respectively. The probability of success for task $\tau_i$ with the frequency $f_{p,k}$ on core $P_s$ can be calculated as $r_{i,k}^P = e^{-\lambda_P(f_{p,k}) \times t_{i,k}^P}$, where $t_{i,k}^P = \frac{\omega_i}{f_{p,k}}$ denotes the execution time of task $\tau_i$ with V/F level ($v_{p,k}, f_{p,k}$). Similarly, the probability of successful transmission over one unit link for edge $e_{i,j}$ with the frequency $f_{l,g}$ can be given by $r_{i,j,g}^{UL} = e^{-\lambda_L(f_{l,g}) \times t_{i,j,g}^{UL}}$. In Fig. 1(a), when tasks $\tau_i$ and $\tau_j$ are assigned to cores $P_s$ and $P_d$, respectively, the probability of success for edge $e_{i,j}$ along route $\mathcal{L}_{s,d}$ with the frequency $f_{l,g}$ is $r_{i,j,g}^L = \sum_{s \in \mathcal{M}} \sum_{d \in \mathcal{M}} x_{i,s} x_{j,d} (r_{i,j,g}^{UL})^{h_{s,d}}$, where $(r_{i,j,g}^{UL})^{h_{s,d}}$ represents the reliability probability of route $\mathcal{L}_{s,d}$ containing $h_{s,d}$ links. On this basis, the joint reliability probability of task $\tau_j$ can be calculated as

$$R_j = r_{j,k}^P \times r_{i,j,g}^L \times r_{v,j,g}^L = r_{j,k}^P \prod_{e_{u,j} \in \mathcal{E}} r_{u,j,g}^L, \quad (10)$$

where $\prod_{e_{u,j} \in \mathcal{E}} r_{u,j,g}^L$ denotes the probability of successful transmission between task $\tau_j$ and its predecessors with the frequency $f_{l,g}$. If a task does not have any predecessors, e.g., task $\tau_a$ in Fig. 1(a), we consider only the faults on cores, and thus, the reliability probability of task $\tau_a$ is $R_a = r_{a,k}^P$. To maintain the desired system reliability, each task $\tau_j$ must satisfy its reliability constraints [21], which means the task reliability $R_j$ is greater than the reliability threshold $R_{th}$.

## B. Problem Formulation

This section presents the Mixed-Integer Nonlinear Programming (MINLP) formulation of the contention- and reliability-aware mapping problem. Our goal is to schedule and route each task such that real-time and reliability constraints are satisfied and the system performance (i.e., communication efficiency, energy consumption, and core utilization) is improved. Therefore, we must determine 1) task allocation, 2) frequency assignment, 3) edge scheduling, and 4) communication contention management. To formulate the task mapping problem, we introduce a set of binary and continuous variables, as summarized in Table II. For the sake of paper presentation, let $\mathcal{N} \triangleq \{1, \dots, N\}$, $\mathcal{M} \triangleq \{1, \dots, M\}$, $\mathcal{N}_p \triangleq \{1, \dots, N_p\}$, $\mathcal{N}_l \triangleq \{1, \dots, N_l\}$. The constraint descriptions are as follows:

1) **Task Allocation Constraints:** The task allocation variable $x_{i,s}$ is bounded by

$$\sum_{s \in \mathcal{M}} x_{i,s} = 1, \quad \forall i \in \mathcal{N}, \quad (11)$$

where (11) ensures that each task $\tau_i$ is assigned to a core.

2) **Frequency Assignment Constraints:** Since all cores and links in the target platform support DVFS, for each core and link, we have

$$\sum_{k \in \mathcal{N}_p} c_{i,k}^P = 1, \quad \forall i \in \mathcal{N}, \quad (12)$$

$$\sum_{g \in \mathcal{N}_l} c_{i,j,g}^L = 1, \quad \forall e_{i,j} \in \mathcal{E}, \quad (13)$$

where (12) ensures that a task $\tau_i$ is executed with one V/F core level ($v_{p,k}, f_{p,k}$), and (13) restricts that the message of edge $e_{i,j}$ is transmitted with one V/F link level ($v_{l,g}, f_{l,g}$).

3) **Communication Start Time Constraints:** The message transmission for edges should consider the precedence relations. For example, in Fig. 1(b), when the message for edge $e_{i,j}$ is transmitted from task $\tau_i$ to $\tau_j$, the communication start time $t_{s,i,j}$ is not earlier than the finish time of the predecessor $\tau_i$. Therefore, we have

$$te_i \le t_{s,i,j}, \quad \forall e_{i,j} \in \mathcal{E}. \quad (14)$$

4) **Communication End Time Constraints:** Taking task allocation and DVFS on links during task scheduling into account, the communication time of message $e_{i,j}$ is represented as

$$t_{i,j}^L = \left( \sum_{s \in \mathcal{M}} \sum_{d \in \mathcal{M}} h_{s,d} x_{i,s} x_{j,d} \right) \sum_{g \in \mathcal{N}_l} c_{i,j,g}^L t_{i,j,g}^{UL}, \quad (15)$$

where $\sum_{g \in \mathcal{N}_l} c_{i,j,g}^L t_{i,j,g}^{UL}$ represents the transmission time over one unit link with DVFS, and $\sum_{s \in \mathcal{M}} \sum_{d \in \mathcal{M}} h_{s,d} x_{i,s} x_{j,d}$ is the number of links when transmitting the message for edge $e_{i,j}$.

If the message transmits from $\tau_i$ to $\tau_j$ through $e_{i,j}$, the communication end time $te_{i,j}$ is equal to the sum of communication
<table><caption>TABLE II
MAIN NOTATIONS USED IN PROBLEM FORMULATIONS</caption><thead><tr><th colspan="2">Related Parameters</th></tr></thead><tbody><tr><td>N</td><td>number of tasks in set T ≜ {τ<sub>i</sub>, ..., τ<sub>N</sub>}. <br> number of cores in set P ≜ {P<sub>1</sub>, ..., P<sub>M</sub>}. <br> router sets, where R ≜ {R<sub>1</sub>, ..., R<sub>M</sub>}. <br> physical link between cores P<sub>s</sub> and P<sub>d</sub>. <br> routing set between cores P<sub>s</sub> and P<sub>d</sub>. <br> Manhattan distance between core P<sub>s</sub> and P<sub>d</sub>. <br> the k<sup>th</sup> V/F level of core. <br> the g<sup>th</sup> V/F level of link. <br> number of V/F levels in cores (links). <br> link bandwidth. <br> dependency between tasks τ<sub>i</sub> and τ<sub>j</sub>, where e<sub>i,j</sub> ∈ E. <br> size of communication data between tasks τ<sub>i</sub> and τ<sub>j</sub>. <br> execution cycles of task τ<sub>i</sub>. <br> task deadline of task τ<sub>i</sub>. <br> α<sub>i</sub> = 1 if task τ<sub>i</sub> has no predecessors, else α<sub>i</sub> = 0. <br> λ<sub>0</sub>, d = average fault rate and transient fault sensitivity. <br> R<sub>th</sub> = reliability threshold. <br> μ = weight in the objective function.</td></tr><tr><th colspan="2">Binary Variables</th></tr><tr><td>x<sub>i,s</sub></td><td>= 1 if task τ<sub>i</sub> is assigned to core P<sub>s</sub>, else x<sub>i,s</sub> = 0. <br> = 1 if task τ<sub>i</sub> is executed with V/F level (v<sub>p,k</sub>, f<sub>p,k</sub>), <br> else c<sup>P</sup><sub>i,k</sub> = 0.</td></tr><tr><td>c<sup>L</sup><sub>i,j,g</sub></td><td>= 1 if the message for edge e<sub>i,j</sub> is transmitted with <br> the level V/F (v<sub>l,g</sub>, f<sub>l,g</sub>), else c<sup>L</sup><sub>i,j,g</sub> = 0. <br> = 1 if task τ<sub>i</sub> starts execution before τ<sub>j</sub> is completed, <br> else o<sub>i,j</sub> = 0.</td></tr><tr><td>o<sub>i,j</sub></td><td>= 1 if edge e<sub>i,j</sub> starts transmitting messages <br> before e<sub>m,n</sub> completes, else η<sub>i,j,m,n</sub> = 0.</td></tr><tr><th colspan="2">Continuous Variables</th></tr><tr><td>ts<sub>i</sub> (te<sub>i</sub>)</td><td>start (end) time of executing τ<sub>i</sub>.</td></tr><tr><td>ts<sub>i,j</sub> (te<sub>i,j</sub>)</td><td>start (end) time of message transmission for edge e<sub>i,j</sub>.</td></tr><tr><td>t<sup>slack</sup><sub>i,j</sub></td><td>slack time for edge e<sub>i,j</sub>.</td></tr><tr><td>U<sub>max</sub></td><td>maximum core utilization rate.</td></tr><tr><th colspan="2">Auxiliary Variables</th></tr><tr><td>β<sub>i,s,k</sub></td><td>binary variable, and β<sub>i,s,k</sub> = x<sub>i,s</sub>c<sup>P</sup><sub>i,k</sub>.</td></tr><tr><td>γ<sub>i,j,s,d</sub></td><td>binary variable, and γ<sub>i,j,s,d</sub> = x<sub>i,s</sub>x<sub>j,d</sub>.</td></tr><tr><td>δ<sub>i,j,s,d,g</sub></td><td>binary variable, and δ<sub>i,j,s,d,g</sub> = γ<sub>i,j,s,d</sub>c<sup>L</sup><sub>i,j,g</sub>.</td></tr></tbody></table>

start time $ts_{i,j}$, communication time $t_{i,j}^L$, and slack time $t_{i,j}^{slack}$. The value of $te_{i,j}$ is not earlier than the start time of the successor $\tau_j$. Thus, we have

$$te_{i,j} = ts_{i,j} + t_{i,j}^{L} + t_{i,j}^{slack} \leq ts_j, \forall e_{i,j} \in \mathcal{E}. \quad (16)$$

5) Real-time Constraints: For the real-time tasks, since each task $\tau_j$ must be completed within the deadline $D_j$, we have

$$te_j = ts_j + \sum_{k \in \mathcal{N}_p} c_{j,k}^P t_{j,k}^P \leq D_j, \forall j \in \mathcal{N}, \quad (17)$$

where $\sum_{k \in \mathcal{N}_p} c_{j,k}^P t_{j,k}^P$ is the execution time of $\tau_j$ with DVFS.

6) Task Non-overlapping Constraints: If tasks are assigned to the same core, their execution sequence should be determined since one core cannot execute multiple tasks at the same time. Hence, we have the following constraints:

$$(te_j - ts_i)/Z \leq o_{i,j} \leq (te_j - ts_i)/Z + 1, \quad (18)$$

$$o_{i,j} + o_{j,i} + x_{i,s} + x_{j,s} \leq 3, \forall e_{i,j} \notin \mathcal{E}, \forall s \in \mathcal{M}. \quad (19)$$

If task $\tau_i$ starts the execution before the completion of task $\tau_j$, i.e., $ts_i \leq te_j$, (18) is transformed to $o_{i,j} = 1$, otherwise, we get $o_{i,j} = 0$. If the execution time of $\tau_i$ and $\tau_j$ overlaps, and there is no dependency between $\tau_i$ and $\tau_j$, $ts_j \leq te_i$ and $ts_i \leq te_j$ hold. We get $o_{i,j} = o_{j,i} = 1$ from (18). Therefore, (19) is transformed to $x_{i,s} + x_{j,s} \leq 1$, which means $\tau_i$ and $\tau_j$ cannot be assigned to the same core.

7) Reliability Constraints: Note that we consider transient faults on both cores and links. On the one hand, we consider only faults on cores for the task without predecessors, as there is no communication between this task and its predecessors. Let parameter $\alpha_j = 1$ denote task $\tau_j$ does not have predecessors, otherwise, $\alpha_j = 0$. With $\alpha_j = 1$ and DVFS, the reliability probability of task $\tau_j$ is given by

$$R_j = \sum_{k \in \mathcal{N}_p} c_{j,k}^P r_{j,k}^P, \forall j \in \mathcal{N}, \alpha_j = 1. \quad (20)$$

On the other hand, if task $\tau_j$ has predecessors, i.e., $\alpha_j = 0$, we consider the reliability on both cores and links. Since the reliability of each link is related to the V/F, the reliability probability of links transmitting $e_{i,j}$ with DVFS is $\sum_{g \in \mathcal{N}_l} c_{i,j,g}^L r_{i,j,g}^L$. Therefore, the reliability probability of task $\tau_j$ is calculated as

$$R_j = \left( \sum_{k \in \mathcal{N}_p} c_{j,k}^P r_{j,k}^P \right) \prod_{e_{i,j} \in \mathcal{E}} \left( \sum_{g \in \mathcal{N}_l} c_{i,j,g}^L r_{i,j,g}^L \right), \quad \forall j \in \mathcal{N}, \alpha_j = 0. \quad (21)$$

Combining (20) and (21), the reliability probability of task $\tau_j$, including computation and communication, is formulated as:

$$R_j = \begin{cases} \sum_{k \in \mathcal{N}_p} c_{j,k}^P r_{j,k}^P, & \forall j \in \mathcal{N}, \alpha_j = 1, \\ \left( \sum_{k \in \mathcal{N}_p} c_{j,k}^P r_{j,k}^P \right) \prod_{e_{i,j} \in \mathcal{E}} \left( \sum_{g \in \mathcal{N}_l} c_{i,j,g}^L r_{i,j,g}^L \right), & \forall j \in \mathcal{N}, \alpha_j = 0. \end{cases} \quad (22)$$

To run applications successfully, we must consider the reliability requirements of scheduling and routing for all tasks. Thus, the joint reliability probability of each task $\tau_j$ should be larger than reliability threshold $R_{th}$, and we have

$$R_j \geq R_{th}, \forall j \in \mathcal{N}. \quad (23)$$

8) Utilization Balance Constraints: Imbalanced mapping of tasks harms system reliability since the cores with heavy tasks assigned have high circuit activities, which raises the average fault rate $\lambda_0$ and decreases system reliability [22]. Moreover, load imbalance may cause local congestion in NoC, and the increased transmission delay will degrade communication efficiency. To improve system performance, we consider a load-balanced task mapping to minimize the maximum core utilization rate $U_{max}$. To restrict the maximum core utilization rate among the cores, we have the following constraints:

$$U_s = \underbrace{\left( \sum_{i \in \mathcal{N}} \sum_{k \in \mathcal{N}_p} x_{i,s} c_{i,k}^P t_{i,k}^P \right)}_{(a)} / H \leq U_{\max}, \forall s \in \mathcal{M}, \quad (24)$$

where $U_s$ denotes the core utilization rate of $P_s$, given by the ratio of the total task execution time on core $P_s$ (i.e., (24)-(a)) to the scheduling horizon $H$.
<table><caption>TABLE II
MAIN NOTATIONS USED IN PROBLEM FORMULATIONS</caption><thead><tr><th colspan="2">Related Parameters</th></tr></thead><tbody><tr><td>N</td><td>number of tasks in set T ≜ {τ<sub>i</sub>, ..., τ<sub>N</sub>}. <br> number of cores in set P ≜ {P<sub>1</sub>, ..., P<sub>M</sub>}. <br> router sets, where R ≜ {R<sub>1</sub>, ..., R<sub>M</sub>}. <br> physical link between cores P<sub>s</sub> and P<sub>d</sub>. <br> routing set between cores P<sub>s</sub> and P<sub>d</sub>. <br> Manhattan distance between core P<sub>s</sub> and P<sub>d</sub>. <br> the k<sup>th</sup> V/F level of core. <br> the g<sup>th</sup> V/F level of link. <br> number of V/F levels in cores (links). <br> link bandwidth. <br> dependency between tasks τ<sub>i</sub> and τ<sub>j</sub>, where e<sub>i,j</sub> ∈ E. <br> size of communication data between tasks τ<sub>i</sub> and τ<sub>j</sub>. <br> execution cycles of task τ<sub>i</sub>. <br> task deadline of task τ<sub>i</sub>. <br> = 1 if task τ<sub>i</sub> has no predecessors, else α<sub>i</sub> = 0. <br> average fault rate and transient fault sensitivity. <br> reliability threshold. <br> weight in the objective function.</td></tr><tr><td colspan="2"><strong>Binary Variables</strong></td></tr><tr><td>x<sub>i,s</sub></td><td>= 1 if task τ<sub>i</sub> is assigned to core P<sub>s</sub>, else x<sub>i,s</sub> = 0. <br> = 1 if task τ<sub>i</sub> is executed with V/F level (v<sub>p,k</sub>, f<sub>p,k</sub>), <br> else c<sup>P</sup><sub>i,k</sub> = 0. <br> = 1 if the message for edge e<sub>i,j</sub> is transmitted with <br> the level V/F (v<sub>l,g</sub>, f<sub>l,g</sub>), else c<sup>L</sup><sub>i,j,g</sub> = 0. <br> = 1 if task τ<sub>i</sub> starts execution before τ<sub>j</sub> is completed, <br> else o<sub>i,j</sub> = 0. <br> = 1 if edge e<sub>i,j</sub> starts transmitting messages <br> before e<sub>m,n</sub> completes, else η<sub>i,j,m,n</sub> = 0.</td></tr><tr><td colspan="2"><strong>Continuous Variables</strong></td></tr><tr><td>ts<sub>i</sub> (te<sub>i</sub>)</td><td>start (end) time of executing τ<sub>i</sub>. <br> start (end) time of message transmission for edge e<sub>i,j</sub>. <br> slack time for edge e<sub>i,j</sub>. <br> maximum core utilization rate.</td></tr><tr><td colspan="2"><strong>Auxiliary Variables</strong></td></tr><tr><td>β<sub>i,s,k</sub></td><td>binary variable, and β<sub>i,s,k</sub> = x<sub>i,s</sub>c<sup>P</sup><sub>i,k</sub>. <br> binary variable, and γ<sub>i,j,s,d</sub> = x<sub>i,s</sub>x<sub>j,d</sub>. <br> binary variable, and δ<sub>i,j,s,d,g</sub> = γ<sub>i,j,s,d</sub>c<sup>L</sup><sub>i,j,g</sub>.</td></tr></tbody></table>

start time $ts_{i,j}$, communication time $t_{i,j}^L$, and slack time $t_{i,j}^{slack}$. The value of $te_{i,j}$ is not earlier than the start time of the successor $\tau_j$. Thus, we have

$$te_{i,j} = ts_{i,j} + t_{i,j}^{L} + t_{i,j}^{slack} \leq ts_j, \forall e_{i,j} \in \mathcal{E}. \quad (16)$$

5) Real-time Constraints: For the real-time tasks, since each task $\tau_j$ must be completed within the deadline $D_j$, we have

$$te_j = ts_j + \sum_{k \in \mathcal{N}_p} c_{j,k}^P t_{j,k}^P \leq D_j, \forall j \in \mathcal{N}, \quad (17)$$

where $\sum_{k \in \mathcal{N}_p} c_{j,k}^P t_{j,k}^P$ is the execution time of $\tau_j$ with DVFS.

6) Task Non-overlapping Constraints: If tasks are assigned to the same core, their execution sequence should be determined since one core cannot execute multiple tasks at the same time. Hence, we have the following constraints:

$$(te_j - ts_i)/Z \leq o_{i,j} \leq (te_j - ts_i)/Z + 1, \quad (18)$$

$$o_{i,j} + o_{j,i} + x_{i,s} + x_{j,s} \leq 3, \forall e_{i,j} \notin \mathcal{E}, \forall s \in \mathcal{M}. \quad (19)$$

If task $\tau_i$ starts the execution before the completion of task $\tau_j$, i.e., $ts_i \leq te_j$, (18) is transformed to $o_{i,j} = 1$, otherwise, we get $o_{i,j} = 0$. If the execution time of $\tau_i$ and $\tau_j$ overlaps, and there is no dependency between $\tau_i$ and $\tau_j$, $ts_j \leq te_i$ and $ts_i \leq te_j$ hold. We get $o_{i,j} = o_{j,i} = 1$ from (18). Therefore, (19) is transformed to $x_{i,s} + x_{j,s} \leq 1$, which means $\tau_i$ and $\tau_j$ cannot be assigned to the same core.

7) Reliability Constraints: Note that we consider transient faults on both cores and links. On the one hand, we consider only faults on cores for the task without predecessors, as there is no communication between this task and its predecessors. Let parameter $\alpha_j = 1$ denote task $\tau_j$ does not have predecessors, otherwise, $\alpha_j = 0$. With $\alpha_j = 1$ and DVFS, the reliability probability of task $\tau_j$ is given by

$$R_j = \sum_{k \in \mathcal{N}_p} c_{j,k}^P r_{j,k}^P, \forall j \in \mathcal{N}, \alpha_j = 1. \quad (20)$$

On the other hand, if task $\tau_j$ has predecessors, i.e., $\alpha_j = 0$, we consider the reliability on both cores and links. Since the reliability of each link is related to the V/F, the reliability probability of links transmitting $e_{i,j}$ with DVFS is $\sum_{g \in \mathcal{N}_l} c_{i,j,g}^L r_{i,j,g}^L$. Therefore, the reliability probability of task $\tau_j$ is calculated as

$$R_j = \left( \sum_{k \in \mathcal{N}_p} c_{j,k}^P r_{j,k}^P \right) \prod_{e_{i,j} \in \mathcal{E}} \left( \sum_{g \in \mathcal{N}_l} c_{i,j,g}^L r_{i,j,g}^L \right), \quad \forall j \in \mathcal{N}, \alpha_j = 0. \quad (21)$$

Combining (20) and (21), the reliability probability of task $\tau_j$, including computation and communication, is formulated as:

$$R_j = \begin{cases} \sum_{k \in \mathcal{N}_p} c_{j,k}^P r_{j,k}^P, & \forall j \in \mathcal{N}, \alpha_j = 1, \\ \left( \sum_{k \in \mathcal{N}_p} c_{j,k}^P r_{j,k}^P \right) \prod_{e_{i,j} \in \mathcal{E}} \left( \sum_{g \in \mathcal{N}_l} c_{i,j,g}^L r_{i,j,g}^L \right), & \forall j \in \mathcal{N}, \alpha_j = 0. \end{cases} \quad (22)$$

To run applications successfully, we must consider the reliability requirements of scheduling and routing for all tasks. Thus, the joint reliability probability of each task $\tau_j$ should be larger than reliability threshold $R_{th}$, and we have

$$R_j \geq R_{th}, \forall j \in \mathcal{N}. \quad (23)$$

8) Utilization Balance Constraints: Imbalanced mapping of tasks harms system reliability since the cores with heavy tasks assigned have high circuit activities, which raises the average fault rate $\lambda_0$ and decreases system reliability [22]. Moreover, load imbalance may cause local congestion in NoC, and the increased transmission delay will degrade communication efficiency. To improve system performance, we consider a load-balanced task mapping to minimize the maximum core utilization rate $U_{max}$. To restrict the maximum core utilization rate among the cores, we have the following constraints:

$$U_s = \underbrace{\left( \sum_{i \in \mathcal{N}} \sum_{k \in \mathcal{N}_p} x_{i,s} c_{i,k}^P t_{i,k}^P \right)}_{(a)} / H \leq U_{max}, \forall s \in \mathcal{M}, \quad (24)$$

where $U_s$ denotes the core utilization rate of $P_s$, given by the ratio of the total task execution time on core $P_s$ (i.e., (24)-(a)) to the scheduling horizon $H$.
9) **Objective Function:** We aim to minimize the weighted core utilization rate and total energy consumption. The objective function can be formulated as follows:

$$ \min \mu E_{\text{total}}/E_{\text{max}} + (1 - \mu)U_{\text{max}}. \quad (25) $$

where $\mu \in [0, 1]$ is a weighted factor, $E_{\text{total}}$ is the total energy consumption, and $E_{\text{max}}$ is an upper bound of $E_{\text{total}}$.

$$ E_{\text{total}} = \sum_{e_{i,j} \in \mathcal{E}} \sum_{s \in \mathcal{M}} \sum_{d \in \mathcal{M}} x_{i,s} x_{j,d} s_{i,j} \left[ (h_{s,d} + 1) E_{\text{Rbit}} + h_{s,d} \sum_{g \in \mathcal{N}_i} c_{i,j,g}^{L} E_{\text{Lbit},g} \right] + \sum_{i \in \mathcal{N}} \sum_{k \in \mathcal{N}_p} c_{i,k}^{P} P_{\text{comp}}^{P} t_{i,k}^{P}. \quad (26) $$

10) **Primal Problem:** Based on the above constraints and objective function, the contention- and reliability-aware task mapping problem is formulated as follows:

$$ \textbf{PP}: \min_{x, e^P, c^L, o, \eta, ts^P, ts^L, t, u} \mu E_{\text{total}}/E_{\text{max}} + (1 - \mu)U_{\text{max}} \quad (27) $$

$$ \text{s.t.} \quad \begin{cases} (5) - (7), (11) - (19), (22) - (24), \\ x_{i,s}, c_{i,k}^P, c_{i,j,g}^L, o_{i,j}, \eta_{i,j,m,n} \in \{0, 1\}, 0 \le t_{s_i}, t_{s_i,j} \le H, \\ \forall i, j, m, n \in \mathcal{N}, \forall s \in \mathcal{M}, \forall k \in \mathcal{N}_p, \forall g \in \mathcal{N}_l, \end{cases} $$

where we have $x = [x_{i,s}]_{N \times M}$, $c^P = [c_{i,k}^P]_{N \times N_p}$, $c^L = [c_{i,j,g}^L]_{N \times N \times N_l}$, $o = [o_{i,j}]_{N \times N}$, $\eta = [\eta_{i,j,m,n}]_{N \times N \times N \times N}$, $ts^P = [ts_i]_{1 \times N}$, $ts^L = [ts_{i,j}]_{N \times N}$, $t = [t_{i,j}^{\text{slack}}]_{N \times N}$, and $u = U_{\text{max}}$. Note that $x$, $c^P$, $c^L$, $o$, and $\eta$ are binary variables, while $ts^P$, $ts^L$, $t$, and $u$ are continuous variables. Moreover, the nonlinear terms $e^{-\lambda t}$, $x_{i,s}c_{i,k}^P$, and $x_{i,s}x_{j,d}c_{i,j,g}^L$ are included in (15), (23), (24) and (26). Thus, (27) is an MINLIP problem.

**Remark 3.1:** DVFS switching overheads are mainly influenced by the V/F levels before and after transition [37]. The time overhead is $t^{\text{switch}}(f_s, f_e) = t_{\text{trans}} \times (f_e - f_s)/f_e$, and the energy overhead is $E^{\text{switch}}(f_s, f_e) = P_s^{\text{switch}} \times t^{\text{switch}}(f_s, f_e)$, where $t_{\text{trans}}$ is a time transition parameter, $f_s$ and $f_e$ are the frequencies before and after transition, respectively, and $P_s^{\text{switch}}$ is the power before frequency transition. Based on the parameters of the NoC platform, we can get switching overheads regarding the links and the cores, e.g., $t_{i,j}^{\text{Lswitch}}$ and $E_{i,j}^{\text{Lswitch}}$ for data transmission among the edge $e_{i,j}$, and $t_{i}^{\text{Pswitch}}$ and $E_{i}^{\text{Pswitch}}$ for execution of task $\tau_i$. Considering the DVFS switching overhead in PP, the extra time ($t_{i,j}^{\text{Lswitch}}$ and $t_{i,j}^{\text{Pswitch}}$) and energy ($E_{i,j}^{\text{Lswitch}}$ and $E_{i}^{\text{Pswitch}}$) should be added to constraints (16), (17), and (26).

**Remark 3.2:** In (2), the leakage current $I_{\text{sub}}$ is affected by temperature $T$. The relationship between them can be described by a complex nonlinear function [38]. To reduce complexity, the leakage current can be linearized with the temperature within a given acceptable accuracy [16], [20], [27]. Specifically, the static power working at the V/F level ($v_{p,k}, f_{p,k}$) can be modeled as $P_{\text{sta},k}^{\text{comp}} = (\gamma_s + \eta_s T) \times v_{p,k}$, where $\gamma_s$ and $\eta_s$ are constants depending on core $P_s$. Let $T(t)$ denote the temperature at time $t$. In (26), the energy consumed by the static power can be updated to $\sum_{s \in \mathcal{M}} \sum_{i \in \mathcal{N}} \sum_{k \in \mathcal{N}_p} x_{i,s} c_{i,k}^P t_{i,k}^P v_{p,k} (\gamma_s + \eta_s \int_0^H T(t) dt)$.

**Remark 3.3:** The above problem can be extended to heterogeneous platforms by modifying the constraints (12), (17), (22), (24), and (26). In addition, we can replace the frequency assignment variable $c_{i,k}^P$ with $c_{i,s,k}^P$, where $c_{i,s,k}^P = 1$ denotes that task

$\tau_i$ assigned to core $P_s$ is executed with V/F level ($v_{s,k}^P, f_{s,k}^P$). Similarly, the execution time of $\tau_i$ on $P_s$ with ($v_{s,k}^P, f_{s,k}^P$) is updated as $t_{i,s,k}^P = \omega_i/f_{s,k}^P$, and the reliability of executing $\tau_i$ on $P_s$ with ($v_{s,k}^P, f_{s,k}^P$) is represented as $r_{i,s,k}^P = e^{-\lambda_P} f_{s,k}^P \times t_{i,s,k}^P$.

### C. Problem Linearization

The MINLP problem has been proven to be an NP-Hard [39], which is hard to solve within polynomial time. To find the optimal solution to PP, we propose a linearization method, which can equivalently convert PP into an MILP problem.

1) **Nonlinear terms caused by exponential terms:** We introduce the following lemma to linearize the product of binary variables and exponential terms in (23).

**Lemma 3.1:** Assume that $z_i$ is a binary variable, and the constant $a_i > 0$ for each $i \in \mathcal{N}$. When $\sum_{i \in \mathcal{N}} z_i = 1$, the equation $\ln(\sum_{i \in \mathcal{N}} a_i z_i) = \sum_{i \in \mathcal{N}} z_i \ln a_i$ holds.

**Proof:** Considering the case when binary variable $z_m = 1$, while the other binary variable $z_n = 0$ ($\forall n \neq m \in \mathcal{N}$) due to $\sum_{i \in \mathcal{N}} z_i = 1$. Therefore, we have $\ln(\sum_{i \in \mathcal{N}} a_i z_i) = \ln(a_1 \times 0 + \dots + a_m z_m + \dots + a_N \times 0) = \ln a_m z_m = \ln a_m$. On the other hand, we get $\sum_{i \in \mathcal{N}} z_i \ln a_i = 0 \times \ln a_1 + \dots + z_m \ln a_m + \dots + 0 \times a_N = z_m \ln a_m = \ln a_m$. Therefore, it is proved that $\ln(\sum_{i \in \mathcal{N}} a_i z_i) = \sum_{i \in \mathcal{N}} z_i \ln a_i$ when $\sum_{i \in \mathcal{N}} z_i = 1$. ■

Since logarithm is a monotonically increasing function, the relation between left and right parts in (23) remains unchanged when logarithm operation is performed on both sides of (23). According to Lemma 3.1, (23) can be linearized as follows:

$$ \ln R_j \ge \ln R_{th}, \quad \forall j \in \mathcal{N}, \quad (28) $$

where

$$ \ln R_j = \begin{cases} \sum_{k \in \mathcal{N}_p} c_{j,k}^P \ln r_{j,k}^P, & \alpha_j = 1, \\ \sum_{e_{i,j} \in \mathcal{E}} \sum_{g \in \mathcal{N}_l} c_{i,j,g}^L \ln r_{i,j,g}^L + \sum_{k \in \mathcal{N}_p} c_{j,k}^P \ln r_{j,k}^P, & \alpha_j = 0, \end{cases} \\ \ln r_{j,k}^P = \ln e^{-\lambda_P(f_{p,k})} \times t_{j,k}^P = -\frac{\omega_j \lambda_P(f_{p,k})}{f_{p,k}}, \\ \ln r_{i,j,g}^L = \sum_{s \in \mathcal{M}} \sum_{d \in \mathcal{M}} x_{i,s} x_{j,d} h_{s,d} \ln r_{i,j,g}^{UL} \\ = -\sum_{s \in \mathcal{M}} \sum_{d \in \mathcal{M}} x_{i,s} x_{j,d} \frac{h_{s,d} s_{i,j} \lambda_L(f_{l,g})}{b_{\omega} f_{l,g}}. $$

Taking the value of $\alpha_j$ in the above equations into account, (28) can be reformulated as follows:

$$ \ln R_j = (1 - \alpha_j) \sum_{e_{i,j} \in \mathcal{E}} \sum_{g \in \mathcal{N}_l} c_{i,j,g}^L \ln r_{i,j,g}^L \\ + \sum_{k \in \mathcal{N}_p} c_{j,k}^P \ln r_{j,k}^P \ge \ln R_{th}, \quad \forall j \in \mathcal{N}. \quad (29) $$

2) **Nonlinear terms caused by the products of binary variables:** We propose the following lemma to tackle the nonlinear items $x_{i,s}c_{i,k}^P$ and $x_{i,s}x_{j,d}c_{i,j,g}^L$ in (15), (24), (26), and (29).

**Lemma 3.2:** Assume that $x_1$ and $x_2$ are binary variables. The nonlinear term $x_1x_2$ can be replaced by an auxiliary (binary) variable $y$, where $y = x_1x_2$, and the additional constraints $y \le x_1$, $y \le x_2$ and $y \ge x_1 + x_2 - 1$.

**Proof:** When binary variables $x_1 = 1$ and $x_2 = 1$, the additional constraint is transformed to $1 \le y \le 1$, i.e., $y = 1$.
9) **Objective Function:** We aim to minimize the weighted core utilization rate and total energy consumption. The objective function can be formulated as follows:

$$ \min \mu E_{\text{total}}/E_{\text{max}} + (1 - \mu)U_{\text{max}}. \quad (25) $$

where $\mu \in [0, 1]$ is a weighted factor, $E_{\text{total}}$ is the total energy consumption, and $E_{\text{max}}$ is an upper bound of $E_{\text{total}}$.

$$ E_{\text{total}} = \sum_{e_{i,j} \in \mathcal{E}} \sum_{s \in \mathcal{M}} \sum_{d \in \mathcal{M}} x_{i,s} x_{j,d} s_{i,j} [(h_{s,d} + 1)E_{\text{Rbit}} + h_{s,d} \sum_{g \in \mathcal{N}_i} c_{i,j,g}^{L} E_{\text{Lbit},g}] + \sum_{i \in \mathcal{N}} \sum_{k \in \mathcal{N}_p} c_{i,k}^{P} P_{\text{comp}}^{P} t_{i,k}^{P}. \quad (26) $$

10) **Primal Problem:** Based on the above constraints and objective function, the contention- and reliability-aware task mapping problem is formulated as follows:

$$ \textbf{PP}: \min_{x, e^P, c^L, o, \eta, ts^P, ts^L, t, u} \mu E_{\text{total}}/E_{\text{max}} + (1 - \mu)U_{\text{max}} \quad (27) $$

$$ \text{s.t.} \quad \begin{cases} (5) - (7), (11) - (19), (22) - (24), \\ x_{i,s}, c_{i,k}^{P}, c_{i,j,g}^{L}, o_{i,j}, \eta_{i,j,m,n} \in \{0, 1\}, 0 \le ts_i, ts_{i,j} \le H, \\ \forall i, j, m, n \in \mathcal{N}, \forall s \in \mathcal{M}, \forall k \in \mathcal{N}_p, \forall g \in \mathcal{N}_l, \end{cases} $$

where we have $x = [x_{i,s}]_{N \times M}$, $c^P = [c_{i,k}^P]_{N \times N_p}$, $c^L = [c_{i,j,g}^L]_{N \times N \times N_l}$, $o = [o_{i,j}]_{N \times N}$, $\eta = [\eta_{i,j,m,n}]_{N \times N \times N \times N}$, $ts^P = [ts_i]_{1 \times N}$, $ts^L = [ts_{i,j}]_{N \times N}$, $t = [t_{i,j}^{\text{slack}}]_{N \times N}$, and $u = U_{\text{max}}$. Note that $x$, $c^P$, $c^L$, $o$, and $\eta$ are binary variables, while $ts^P$, $ts^L$, $t$, and $u$ are continuous variables. Moreover, the nonlinear terms $e^{-\lambda t}$, $x_{i,s} c_{i,k}^P$, and $x_{i,s} x_{j,d} c_{i,j,g}^L$ are included in (15), (23), (24) and (26). Thus, (27) is an MINLIP problem.

**Remark 3.1:** DVFS switching overheads are mainly influenced by the V/F levels before and after transition [37]. The time overhead is $t^{\text{switch}}(f_s, f_e) = t_{\text{trans}} \times (f_e - f_s)/f_e$, and the energy overhead is $E^{\text{switch}}(f_s, f_e) = P_s^{\text{switch}} \times t^{\text{switch}}(f_s, f_e)$, where $t_{\text{trans}}$ is a time transition parameter, $f_s$ and $f_e$ are the frequencies before and after transition, respectively, and $P_s^{\text{switch}}$ is the power before frequency transition. Based on the parameters of the NoC platform, we can get switching overheads regarding the links and the cores, e.g., $t_{i,j}^{\text{Lswitch}}$ and $E_{i,j}^{\text{Lswitch}}$ for data transmission among the edge $e_{i,j}$, and $t_{i}^{\text{Pswitch}}$ and $E_{i}^{\text{Pswitch}}$ for execution of task $\tau_i$. Considering the DVFS switching overhead in PP, the extra time ($t_{i,j}^{\text{Lswitch}}$ and $t_{i,j}^{\text{Pswitch}}$) and energy ($E_{i,j}^{\text{Lswitch}}$ and $E_{i}^{\text{Pswitch}}$) should be added to constraints (16), (17), and (26).

**Remark 3.2:** In (2), the leakage current $I_{\text{sub}}$ is affected by temperature $T$. The relationship between them can be described by a complex nonlinear function [38]. To reduce complexity, the leakage current can be linearized with the temperature within a given acceptable accuracy [16], [20], [27]. Specifically, the static power working at the V/F level ($v_{p,k}, f_{p,k}$) can be modeled as $P_{\text{sta},k}^{\text{comp}} = (\gamma_s + \eta_s T) \times v_{p,k}$, where $\gamma_s$ and $\eta_s$ are constants depending on core $P_s$. Let $T(t)$ denote the temperature at time $t$. In (26), the energy consumed by the static power can be updated to $\sum_{s \in \mathcal{M}} \sum_{i \in \mathcal{N}} \sum_{k \in \mathcal{N}_p} x_{i,s} c_{i,k}^P t_{i,k}^P v_{p,k} (\gamma_s + \eta_s \int_0^H T(t) dt)$.

**Remark 3.3:** The above problem can be extended to heterogeneous platforms by modifying the constraints (12), (17), (22), (24), and (26). In addition, we can replace the frequency assignment variable $c_{i,k}^P$ with $c_{i,s,k}^P$, where $c_{i,s,k}^P = 1$ denotes that task

$\tau_i$ assigned to core $P_s$ is executed with V/F level ($v_{s,k}^P, f_{s,k}^P$). Similarly, the execution time of $\tau_i$ on $P_s$ with ($v_{s,k}^P, f_{s,k}^P$) is updated as $t_{i,s,k}^P = \omega_i/f_{s,k}^P$, and the reliability of executing $\tau_i$ on $P_s$ with ($v_{s,k}^P, f_{s,k}^P$) is represented as $r_{i,s,k}^P = e^{-\lambda_P} f_{s,k}^P \times t_{i,s,k}^P$.

### C. Problem Linearization

The MINLP problem has been proven to be an NP-Hard [39], which is hard to solve within polynomial time. To find the optimal solution to PP, we propose a linearization method, which can equivalently convert PP into an MILP problem.

1) **Nonlinear terms caused by exponential terms:** We introduce the following lemma to linearize the product of binary variables and exponential terms in (23).

**Lemma 3.1:** Assume that $z_i$ is a binary variable, and the constant $a_i > 0$ for each $i \in \mathcal{N}$. When $\sum_{i \in \mathcal{N}} z_i = 1$, the equation $\ln(\sum_{i \in \mathcal{N}} a_i z_i) = \sum_{i \in \mathcal{N}} z_i \ln a_i$ holds.

**Proof:** Considering the case when binary variable $z_m = 1$, while the other binary variable $z_n = 0$ ($\forall n \neq m \in \mathcal{N}$) due to $\sum_{i \in \mathcal{N}} z_i = 1$. Therefore, we have $\ln(\sum_{i \in \mathcal{N}} a_i z_i) = \ln(a_1 \times 0 + \dots + a_m z_m + \dots + a_N \times 0) = \ln a_m z_m = \ln a_m$. On the other hand, we get $\sum_{i \in \mathcal{N}} z_i \ln a_i = 0 \times \ln a_1 + \dots + z_m \ln a_m + \dots + 0 \times a_N = z_m \ln a_m = \ln a_m$. Therefore, it is proved that $\ln(\sum_{i \in \mathcal{N}} a_i z_i) = \sum_{i \in \mathcal{N}} z_i \ln a_i$ when $\sum_{i \in \mathcal{N}} z_i = 1$. ■

Since logarithm is a monotonically increasing function, the relation between left and right parts in (23) remains unchanged when logarithm operation is performed on both sides of (23). According to Lemma 3.1, (23) can be linearized as follows:

$$ \ln R_j \ge \ln R_{th}, \quad \forall j \in \mathcal{N}, \quad (28) $$

where

$$ \ln R_j = \begin{cases} \sum_{k \in \mathcal{N}_p} c_{j,k}^P \ln r_{j,k}^P, & \alpha_j = 1, \\ \sum_{e_{i,j} \in \mathcal{E}} \sum_{g \in \mathcal{N}_l} c_{i,j,g}^L \ln r_{i,j,g}^L + \sum_{k \in \mathcal{N}_p} c_{j,k}^P \ln r_{j,k}^P, & \alpha_j = 0, \end{cases} \\ \ln r_{j,k}^P = \ln e^{-\lambda_P(f_{p,k})} \times t_{j,k}^P = - \frac{\omega_j \lambda_P(f_{p,k})}{f_{p,k}}, \\ \ln r_{i,j,g}^L = \sum_{s \in \mathcal{M}} \sum_{d \in \mathcal{M}} x_{i,s} x_{j,d} h_{s,d} \ln r_{i,j,g}^{UL} \\ = - \sum_{s \in \mathcal{M}} \sum_{d \in \mathcal{M}} x_{i,s} x_{j,d} \frac{h_{s,d} s_{i,j} \lambda_L(f_{l,g})}{b_{\omega} f_{l,g}}. $$

Taking the value of $\alpha_j$ in the above equations into account, (28) can be reformulated as follows:

$$ \ln R_j = (1 - \alpha_j) \sum_{e_{i,j} \in \mathcal{E}} \sum_{g \in \mathcal{N}_l} c_{i,j,g}^L \ln r_{i,j,g}^L + \sum_{k \in \mathcal{N}_p} c_{j,k}^P \ln r_{j,k}^P \ge \ln R_{th}, \quad \forall j \in \mathcal{N}. \quad (29) $$

2) **Nonlinear terms caused by the products of binary variables:** We propose the following lemma to tackle the nonlinear items $x_{i,s} c_{i,k}^P$ and $x_{i,s} x_{j,d} c_{i,j,g}^L$ in (15), (24), (26), and (29).

**Lemma 3.2:** Assume that $x_1$ and $x_2$ are binary variables. The nonlinear term $x_1 x_2$ can be replaced by an auxiliary (binary) variable $y$, where $y = x_1 x_2$, and the additional constraints $y \le x_1$, $y \le x_2$ and $y \ge x_1 + x_2 - 1$.

**Proof:** When binary variables $x_1 = 1$ and $x_2 = 1$, the additional constraint is transformed to $1 \le y \le 1$, i.e., $y = 1$.
holds. Similarly, for the cases 1) $x_1 = 0$ and $x_2 = 0$; 2) $x_1 = 1$ and $x_2 = 0$; 3) $x_1 = 0$ and $x_2 = 1$, we have $y = x_1x_2 = 0$. ■

Based on Lemma 3.2, we introduce auxiliary (binary) variables $\beta_{i,s,k}$, $\gamma_{i,j,s,d}$ and $\delta_{i,j,s,d,g}$ to replace the nonlinear items, where $\beta_{i,s,k} = x_{i,s}c_{i,k}^P$, $\gamma_{i,j,s,d} = x_{i,s}x_{j,d}$, and $\delta_{i,j,s,d,g} = \gamma_{i,j,s,d}c_{i,j,g}^L$, and add the following constraints into (27).

$$ \forall i, j \in \mathcal{N}, \forall s, d \in \mathcal{M}, \forall k \in \mathcal{N}_p, \forall g \in \mathcal{N}_l, \quad \beta_{i,s,k} \le x_{i,s}, \beta_{i,s,k} \le c_{i,k}^P, \beta_{i,s,k} \ge x_{i,s} + c_{i,k}^P - 1, \quad (30) $$

$$ \gamma_{i,j,s,d} \le x_{i,s}, \gamma_{i,j,s,d} \le x_{j,d}, \gamma_{i,j,s,d} \ge x_{i,s} + x_{j,d} - 1, \quad (31) $$

$$ \begin{aligned} & \delta_{i,j,s,d,g} \le \gamma_{i,j,s,d}, \delta_{i,j,s,d,g} \le c_{i,j,g}^L, \\ & \delta_{i,j,s,d,g} \ge \gamma_{i,j,s,d} + c_{i,j,g}^L - 1. \end{aligned} \quad (32) $$

Thus, the primal problem (27) can be converted into the following MILP problem through the above linearization method.

$$ \textbf{PP1}: \quad \min_{x, c^P, c^L, o, \eta, ts^P, ts^L, t, u, \beta, \gamma, \delta} \mu E_{total} / E_{max} + (1 - \mu) U_{max} \quad (33) $$

$$ \text{s.t.} \quad \left\{ \begin{array}{l} (5) - (7), (11) - (14), (16) - (19), (29) - (32), \\ t_{i,j}^L = \sum_{s \in \mathcal{M}} \sum_{d \in \mathcal{M}} \sum_{g \in \mathcal{N}_i} h_{s,d} \delta_{i,j,s,d,g} t_{i,j,g}^{UL}, \\ U_s = \left( \sum_{i \in \mathcal{N}} \sum_{k \in \mathcal{N}_p} \beta_{i,s,k} t_{i,k}^P \right) / H \le U_{max}, \\ x_{i,s}, c_{i,k}^P, c_{i,j,g}^L, o_{i,j}, \eta_{i,j,m,n}, \beta_{i,s,k}, \gamma_{i,j,s,d}, \\ \delta_{i,j,s,d,g} \in \{0,1\}, \quad 0 \le t_{s,i} s_{t,i} \le H, \\ \forall i, j, m, n \in \mathcal{N}, \forall s, d \in \mathcal{M}, \forall k \in \mathcal{N}_p, \forall g \in \mathcal{N}_l, \end{array} \right. $$

where we set $\beta = [\beta_{i,s,k}]_{N \times M \times N_p}$, $\gamma = [\gamma_{i,j,s,d}]_{N \times N \times M \times M}$, and $\delta = [\delta_{i,j,s,d,g}]_{N \times N \times M \times M \times N_l}$, and the total energy consumption $E_{total}$ in the objective function of (33) is given by $E_{total} = \sum_{e_{i,j} \in \mathcal{E}} \sum_{s \in \mathcal{M}} \sum_{d \in \mathcal{M}} s_{i,j}[(h_{s,d} + 1)\gamma_{i,j,s,d}E_{Rbit} + h_{s,d} \sum_{g \in \mathcal{N}_i} \delta_{i,j,s,d,g}E_{Lbit,g}] + \sum_{i \in \mathcal{N}} \sum_{k \in \mathcal{N}_p} c_{i,k}^P P_k^{comp} t_{i,k}^P$.

## IV. HEURISTIC TASK MAPPING APPROACH

The proposed contention- and reliability-aware task mapping problem can be transformed into an MILP problem using the linearization methods presented in Section III-C. However, only small-scale problems can be solved efficiently by optimization solvers, such as Gurobi and CPLEX. The problem with large scale will lead to excessive time consumption and memory overflow problems. Hence, we proposed a novel three-step Contention- and Reliability-Aware Task Mapping and Scheduling (CRATMS) heuristic to perform 1) task-to-core assignment, 2) frequency scaling and edge scheduling, and 3) communication contention management, so as to provide better system performance. The structure of CRATMS is shown in Fig. 2.

### A. Task Allocation Scheme

Since the tasks are dependent, the task-to-core assignment directly affects task scheduling and communication on NoC. In addition, the task allocation variable $x$ exists in all the constraints of PP except the frequency assignment constraints (12) and (13), and thus, we consider $x$ at the first step. The optimization processes are summarized in Algorithm 1.

<figure><img src="image_3.png" /><figcaption>Fig. 2. The structure of the proposed CRATMS scheme.</figcaption></figure>

1) **Task Priority:** We introduce the concept of task level to sort the dependent tasks in DAG. The task level of task $\tau_i$ is defined as the largest number of edges from itself to the entry node: $rl(\tau_j) = \max_{\forall e_{i,j} \in \mathcal{E}} \{rl(\tau_i)\} + 1$, and we set the task level of entry nodes as zero. For example, in Fig. 1(a), we have $rl(\tau_a) = 0$, $rl(\tau_b) = 1$, $rl(\tau_v) = 1$, $rl(\tau_m) = 1$, $rl(\tau_i) = 2$, $rl(\tau_j) = 3$, $rl(\tau_n) = 3$, $rl(\tau_u) = 4$, and $rl(\tau_w) = 5$. Therefore, the tasks in the set $\mathcal{T}$ can be sorted in ascending order according to their task levels, and we can get a new task set $\hat{\mathcal{T}}$ (Line 2).

2) **Task-to-core Assignment:** To reduce the routing costs while balancing the task workloads among the cores, we consider the cost function of task $\tau_j$ assigned to core $P_d$ as follows:

$$ F(\tau_j, P_d) = \underbrace{(\mu \sum_{e_{i,j} \in \mathcal{E}} \sum_{s \in \mathcal{M}} x_{i,s} h_{s,d}) / h_{max}}_{(a)} + \underbrace{(1 - \mu) (U_d + t_{j,min}^P / H)}_{(b)} \quad (34) $$

where $h_{max}$ is the maximum Manhattan distance on NoC through the XY routing, and $t_{j,min}^P$ is the execution time of task $\tau_j$ on core $P_d$ with the minimum frequency $f_{p,min}$. Hence, (34)-(a) is the ratio of routing distances between the cores executing tasks $\tau_i$ and $\tau_j$ to the maximum distance $h_{max}$, and (34)-(b) is the core utilization of $P_d$. To reduce the cost of task assignment, for each non-entry task $\tau_j$, they are assigned to the core $P_d^*$ with the minimum cost function, i.e., $d^* = \arg\min_{d \in \mathcal{M}} F(\tau_j, P_d)$ (Line 5). However, since the entry tasks do not have predecessors, we assume that these tasks are assigned to core $P_1$, i.e., $d^* = 1$ (Line 7). After completing the assignment of task $\tau_j$, we can update the task assignment decision $x_{j,d^*} = 1$ (Line 9) and core utilization rate $U_d = U_d + t_{j,min}^P / H$ (Line 10). The decision regarding task allocation $x^*$ is determined by applying the above method for each task.

### B. Frequency Scaling and Edge Scheduling

Under the given task allocation decision, the frequencies of cores and links relate to energy consumption, task reliability, and real-time constraints, affecting the starting and ending time of task execution and edge communication. Therefore, the variables regarding core frequency assignment $c^P$, link frequency assignment $c^L$, task sequence $o$, start time of task execution
holds. Similarly, for the cases 1) $x_1 = 0$ and $x_2 = 0$; 2) $x_1 = 1$ and $x_2 = 0$; 3) $x_1 = 0$ and $x_2 = 1$, we have $y = x_1x_2 = 0$. ■

Based on Lemma 3.2, we introduce auxiliary (binary) variables $\beta_{i,s,k}$, $\gamma_{i,j,s,d}$ and $\delta_{i,j,s,d,g}$ to replace the nonlinear items, where $\beta_{i,s,k} = x_{i,s}c_{i,k}^P$, $\gamma_{i,j,s,d} = x_{i,s}x_{j,d}$, and $\delta_{i,j,s,d,g} = \gamma_{i,j,s,d}c_{i,j,g}^L$, and add the following constraints into (27).

$$ \forall i, j \in \mathcal{N}, \forall s, d \in \mathcal{M}, \forall k \in \mathcal{N}_p, \forall g \in \mathcal{N}_l, \quad \beta_{i,s,k} \le x_{i,s}, \beta_{i,s,k} \le c_{i,k}^P, \beta_{i,s,k} \ge x_{i,s} + c_{i,k}^P - 1, \quad (30) $$

$$ \gamma_{i,j,s,d} \le x_{i,s}, \gamma_{i,j,s,d} \le x_{j,d}, \gamma_{i,j,s,d} \ge x_{i,s} + x_{j,d} - 1, \quad (31) $$

$$ \begin{aligned} & \delta_{i,j,s,d,g} \le \gamma_{i,j,s,d}, \delta_{i,j,s,d,g} \le c_{i,j,g}^L, \\ & \delta_{i,j,s,d,g} \ge \gamma_{i,j,s,d} + c_{i,j,g}^L - 1. \end{aligned} \quad (32) $$

Thus, the primal problem (27) can be converted into the following MILP problem through the above linearization method.

$$ \textbf{PP1}: \quad \min_{x, c^P, c^L, o, \eta, ts^P, ts^L, t, u, \beta, \gamma, \delta} \mu E_{total} / E_{max} + (1 - \mu) U_{max} \quad (33) $$

$$ \text{s.t.} \quad \left\{ \begin{array}{l} (5) - (7), (11) - (14), (16) - (19), (29) - (32), \\ t_{i,j}^L = \sum_{s \in \mathcal{M}} \sum_{d \in \mathcal{M}} \sum_{g \in \mathcal{N}_i} h_{s,d} \delta_{i,j,s,d,g} t_{i,j,g}^{UL}, \\ U_s = \left( \sum_{i \in \mathcal{N}} \sum_{k \in \mathcal{N}_p} \beta_{i,s,k} t_{i,k}^P \right) / H \le U_{max}, \\ x_{i,s}, c_{i,k}^P, c_{i,j,g}^L, o_{i,j}, \eta_{i,j,m,n}, \beta_{i,s,k}, \gamma_{i,j,s,d}, \\ \delta_{i,j,s,d,g} \in \{0, 1\}, \quad 0 \le t_{s,i} s_{t,i} \le H, \\ \forall i, j, m, n \in \mathcal{N}, \forall s, d \in \mathcal{M}, \forall k \in \mathcal{N}_p, \forall g \in \mathcal{N}_l, \end{array} \right. $$

where we set $\beta = [\beta_{i,s,k}]_{N \times M \times N_p}$, $\gamma = [\gamma_{i,j,s,d}]_{N \times N \times M \times M}$, and $\delta = [\delta_{i,j,s,d,g}]_{N \times N \times M \times M \times N_l}$, and the total energy consumption $E_{total}$ in the objective function of (33) is given by $E_{total} = \sum_{e_{i,j} \in \mathcal{E}} \sum_{s \in \mathcal{M}} \sum_{d \in \mathcal{M}} s_{i,j}[(h_{s,d} + 1)\gamma_{i,j,s,d}E_{Rbit} + h_{s,d} \sum_{g \in \mathcal{N}_l} \delta_{i,j,s,d,g}E_{Lbit,g}] + \sum_{i \in \mathcal{N}} \sum_{k \in \mathcal{N}_p} c_{i,k}^P P_{k}^{comp} t_{i,k}^P$.

## IV. HEURISTIC TASK MAPPING APPROACH

The proposed contention- and reliability-aware task mapping problem can be transformed into an MILP problem using the linearization methods presented in Section III-C. However, only small-scale problems can be solved efficiently by optimization solvers, such as Gurobi and CPLEX. The problem with large scale will lead to excessive time consumption and memory overflow problems. Hence, we proposed a novel three-step Contention- and Reliability-Aware Task Mapping and Scheduling (CRATMS) heuristic to perform 1) task-to-core assignment, 2) frequency scaling and edge scheduling, and 3) communication contention management, so as to provide better system performance. The structure of CRATMS is shown in Fig. 2.

### A. Task Allocation Scheme

Since the tasks are dependent, the task-to-core assignment directly affects task scheduling and communication on NoC. In addition, the task allocation variable $x$ exists in all the constraints of PP except the frequency assignment constraints (12) and (13), and thus, we consider $x$ at the first step. The optimization processes are summarized in Algorithm 1.

<figure><img src="image_5.png" /><figcaption>Fig. 2. The structure of the proposed CRATMS scheme.</figcaption></figure>

1) **Task Priority:** We introduce the concept of task level to sort the dependent tasks in DAG. The task level of task $\tau_i$ is defined as the largest number of edges from itself to the entry node: $rl(\tau_j) = \max_{\forall e_{i,j} \in \mathcal{E}} \{rl(\tau_i)\} + 1$, and we set the task level of entry nodes as zero. For example, in Fig. 1(a), we have $rl(\tau_a) = 0$, $rl(\tau_b) = 1$, $rl(\tau_v) = 1$, $rl(\tau_m) = 1$, $rl(\tau_i) = 2$, $rl(\tau_j) = 3$, $rl(\tau_n) = 3$, $rl(\tau_u) = 4$, and $rl(\tau_w) = 5$. Therefore, the tasks in the set $\mathcal{T}$ can be sorted in ascending order according to their task levels, and we can get a new task set $\hat{\mathcal{T}}$ (Line 2).

2) **Task-to-core Assignment:** To reduce the routing costs while balancing the task workloads among the cores, we consider the cost function of task $\tau_j$ assigned to core $P_d$ as follows:

$$ F(\tau_j, P_d) = \underbrace{(\mu \sum_{e_{i,j} \in \mathcal{E}} \sum_{s \in \mathcal{M}} x_{i,s} h_{s,d}) / h_{max}}_{(a)} + \underbrace{(1 - \mu) (U_d + t_{j,min}^P / H)}_{(b)} \quad (34) $$

where $h_{max}$ is the maximum Manhattan distance on NoC through the XY routing, and $t_{j,min}^P$ is the execution time of task $\tau_j$ on core $P_d$ with the minimum frequency $f_{p,min}$. Hence, (34)-(a) is the ratio of routing distances between the cores executing tasks $\tau_i$ and $\tau_j$ to the maximum distance $h_{max}$, and (34)-(b) is the core utilization of $P_d$. To reduce the cost of task assignment, for each non-entry task $\tau_j$, they are assigned to the core $P_d^*$ with the minimum cost function, i.e., $d^* = \arg\min_{d \in \mathcal{M}} F(\tau_j, P_d)$ (Line 5). However, since the entry tasks do not have predecessors, we assume that these tasks are assigned to core $P_1$, i.e., $d^* = 1$ (Line 7). After completing the assignment of task $\tau_j$, we can update the task assignment decision $x_{j,d^*} = 1$ (Line 9) and core utilization rate $U_d = U_d + t_{j,min}^P/H$ (Line 10). The decision regarding task allocation $x^*$ is determined by applying the above method for each task.

### B. Frequency Scaling and Edge Scheduling

Under the given task allocation decision, the frequencies of cores and links relate to energy consumption, task reliability, and real-time constraints, affecting the starting and ending time of task execution and edge communication. Therefore, the variables regarding core frequency assignment $c^P$, link frequency assignment $c^L$, task sequence $o$, start time of task execution
**Algorithm 1: Task Allocation Scheme**

**Input**: Task graph TG and 2D-mesh NoC with M cores

**Output**: Task allocation variable $\boldsymbol{x}^*$

1. Initialize $x_{j,d} = 0$ and $U_d = 0$ ($\forall j \in \mathcal{N}, \forall d \in \mathcal{M}$);

2. Sort tasks in $\mathcal{T}$ by ascending task levels, and get $\hat{\mathcal{T}}$;

3. **for each task $\tau_j$ in $\hat{\mathcal{T}}$ do**

4. | | **if** $rl(\tau_j) \neq 0$ **then**
5. | | | | **Get** $d^* = \arg \min_{d \in \mathcal{M}} F(\tau_j, P_d)$ through (34);
6. | | **else**
7. | | | | **Set** $d^* = 1$;
8. | **end**
9. **Assign** task $\tau_j$ to core $P_{j,d^*}$, and set $x_{j,d^*} = 1$;
10. Update $U_{d^*} = U_{d^*} + t_{j,min}^P/H$;
11. **end**

$ts^P$ and start time of message transmission $ts^L$ are determined at this step concurrently. However, according to (7), the coupling between the slack time $t$ and other variables, e.g., $\boldsymbol{x}, \boldsymbol{c}^L, \boldsymbol{ts}^P$, and $\boldsymbol{ts}^L$ makes it challenging to solve the problem of frequency scaling and edge scheduling. To handle this problem, we assume that the slack time $t$ has a predetermined value $\hat{\boldsymbol{t}}$, which is calculated from (7) in the worst case. In this case, the communication contention constraints for any two edges, e.g., $e_{i,j}$ and $e_{m,n}$ in time are satisfied ($\eta_{i,j,m,n} = \eta_{m,n,i,j} = 1$), and the link frequencies are set to the minimum frequency $f_{l,min}$. Moreover, the objective function of (27) can be transformed to minimize the energy consumption on NoC since the core utilization rate has been determined in the first step. Thus, substituting $x_{i,s}^*$ and $\hat{t}_{i,j}^{slack}$ into (27), the problem of frequency scaling and edge scheduling is given by

$$ \text{SP1}: \min_{\boldsymbol{c}^P, \boldsymbol{c}^L, \boldsymbol{o}, \boldsymbol{ts}^P, \boldsymbol{ts}^L} E_{\text{total}} \quad (35) $$

$$ \text{s.t.} \quad \begin{cases} (12) - (19), (29), \\ c_{i,k}^P, c_{i,j,g}^L, o_{i,j} \in \{0, 1\}, \quad 0 \le t_{si}, t_{sj} \le H, \\ \forall i, j \in \mathcal{N}, \forall k \in \mathcal{N}_p, \forall g \in \mathcal{N}_l. \end{cases} $$

Since (35) is an MILP problem with a smaller scale than (27), based on the structure of the problem, we proposed a novel Feasibility-Pump (FP) based method to solve it. The implementation details are summarized in Algorithm 2.

1) Let $\Phi = \{\boldsymbol{c}^P, \boldsymbol{c}^L, \boldsymbol{o}, \boldsymbol{ts}^P, \boldsymbol{ts}^L\}$ denote the set of the variables in SP1, and we set $\mathcal{I} = \{j | \phi_j \in \{0, 1\}\}$, where $\phi_j$ is the $j^{th}$ element in the set $\Phi$. To make problem (35) easier to solve, we relax it into a Linear Program (LP) problem SP2 by replacing the binary variables $\{\boldsymbol{c}^P, \boldsymbol{c}^L, \boldsymbol{o}\}$ with the continuous variables within the range $[0, 1]$ (Line 1). When SP2 is solved, we get the initial solution $\Phi^{(0)*} = \{\boldsymbol{c}^P, \boldsymbol{c}^L, \boldsymbol{o}, \boldsymbol{ts}^P, \boldsymbol{ts}^L\} \in \mathcal{Z}$ (Line 1), where $\mathcal{Z}$ denotes the set of the feasible region of SP2.

2) We initialize the iteration number $n = 0$ (Line 2). Since the values of $\{\boldsymbol{c}^P, \boldsymbol{c}^L, \boldsymbol{o}\}$ in $\Phi^{(0)*}$ may not be integer, we round the values of $\{\boldsymbol{c}^P, \boldsymbol{c}^L, \boldsymbol{o}\}$ to the nearest integers (Line 3). When considering the task-level DVFS, each task $\tau_i$ is executed with only one V/F level on each core. Based on the $i^{th}$ row of $\boldsymbol{c}^P$, we can find the maximum one among the values $\{c_{i,1}^P, \dots, c_{i,N_p}^P\}$, and denote it as $k^* = \arg \max_{k \in \mathcal{N}_p} \{c_{i,k}^P\}$. For task $\tau_i$, we assign the V/F level $(v_{p,k^*}, f_{p,k^*})$ to execute this task. Therefore, we have $\hat{c}_{i,k}^P = 1$ ($k = k^*$) and $\hat{c}_{i,k}^P = 0$ ($\forall k \neq k^* \in \mathcal{N}_p$). Similarly, we can handle the $\boldsymbol{c}^L$ and $\boldsymbol{o}$.

**Algorithm 2: Frequency Scaling and Edge Scheduling**

**Input**: Task allocation $\boldsymbol{x}$ and the predetermined slack time $\hat{\boldsymbol{t}}$

**Output**: Frequency assignment $\boldsymbol{c}^P$ and $\boldsymbol{c}^L$, and the start time of execution (communication) $\boldsymbol{ts}^P$ ($\boldsymbol{ts}^L$)

1. Relax SP1 to a LP problem and get the initial solution $\Phi^{(0)*}$;

2. Initialize iteration number $n = 0$;

3. Round $\{\boldsymbol{c}^P, \boldsymbol{c}^L, \boldsymbol{o}\}$ in $\Phi^{(0)*}$ to $\{\hat{\boldsymbol{c}}^P, \hat{\boldsymbol{c}}^L, \hat{\boldsymbol{o}}\}$, and update the solution $\hat{\Phi}^{(0)} = \{\hat{\boldsymbol{c}}^P, \hat{\boldsymbol{c}}^L, \hat{\boldsymbol{o}}, \boldsymbol{ts}^P, \boldsymbol{ts}^L\}$;

4. **while** $\Delta(\Phi^{(n)}, \hat{\Phi}^{(n)}) > 0$ **and** $n < n_{\max}$ **do**

5. | | Solve $\Phi^{(n)*} = \arg \min_{\Phi^{(n)}} \{\Delta(\Phi^{(n)}, \hat{\Phi}^{(n)}) : \Phi^{(n)} \in \mathcal{Z}\}$;

6. | | **if** $\Delta(\Phi^{(n)}, \hat{\Phi}^{(n)}) = 0$ **then**

7. | | | | Find the solution to SP1 and return $\Phi^{(n)*}$;

8. | **else**

9. | | Round $\{\boldsymbol{c}^P, \boldsymbol{c}^L, \boldsymbol{o}\}$ in $\Phi^{(n)*}$ to $\{\hat{\boldsymbol{c}}^P, \hat{\boldsymbol{c}}^L, \hat{\boldsymbol{o}}\}$, and get $\hat{\Phi}^{(n)*} = \{\hat{\boldsymbol{c}}^P, \hat{\boldsymbol{c}}^L, \hat{\boldsymbol{o}}, \boldsymbol{ts}^P, \boldsymbol{ts}^L\}$;

10. | | Set $\hat{\Phi}^{(n+1)} = \hat{\Phi}^{(n)*}$ for the next iteration;

11. | | **if** $\hat{\Phi}^{(n+1)} = \hat{\Phi}^{(n)}$ **then**

12. | | | | Select $n_f$ variables $\hat{\phi}_j$ ($j \in \mathcal{I}$) in $\hat{\Phi}^{(n+1)}$ to flip their values, and update $\hat{\Phi}^{(n+1)}$;

13. | **end**

14. | Update iteration number $n \to n + 1$;

15. | **end**

16. **end**

17. **if** $n = n_{\max} + 1$ **and** $\Delta(\Phi^{(n)}, \hat{\Phi}^{(n)}) > 0$ **then**

18. | | Solve SP1 after substituting $\{\boldsymbol{c}^P, \boldsymbol{c}^L, \boldsymbol{o}\}$ with the corresponding values in $\hat{\Phi}^{(n)}$, and get $\hat{\Phi}^{(n+1)*}$;

19. | **while** $\Phi^{(n+1)*} = \emptyset$ **do**

20. | | | | Update frequency levels with $c_{i,k}^P = 1 \to c_{i,k+1}^P = 1$ and $c_{i,j,g}^L = 1 \to c_{i,j,g+1}^L = 1$;

21. | | | | Solve SP1 after substituting $\{\boldsymbol{c}^P, \boldsymbol{c}^L\}$ with the updated values, and update $\hat{\Phi}^{(n+1)*}$;

22. | **end**

23. **end**

Specially, the rounding of $o_{i,j}$ is given by $\hat{o}_{i,j} = [o_{i,j}]$, where $[\cdot]$ represents the rounding operation. Therefore, the rounding processes of $\{\boldsymbol{c}^P, \boldsymbol{c}^L, \boldsymbol{o}\}$ are as follows:

$$ \left\{ \begin{array}{l} \hat{c}_{i,k}^P = 1, \text{ if } k = \arg \max \{c_{i,k}^P\}, \text{ else, } \hat{c}_{i,k}^P = 0, \\ \hat{c}_{i,j,g}^L = 1, \text{ if } g = \arg \max \{c_{i,j,g}^L\}, \text{ else, } \hat{c}_{i,j,g}^L = 0, \\ \hat{o}_{i,j} = [o_{i,j}], \quad \forall i, j \in \mathcal{N}, \forall k \in \mathcal{N}_p, \forall g \in \mathcal{N}_l. \end{array} \right. \quad (36) $$

According to (36), the values of $\{\boldsymbol{c}^P, \boldsymbol{c}^L, \boldsymbol{o}\}$ are transformed to $\{\hat{\boldsymbol{c}}^P, \hat{\boldsymbol{c}}^L, \hat{\boldsymbol{o}}\}$, and the rounding result is $\hat{\Phi} = \{\hat{\boldsymbol{c}}^P, \hat{\boldsymbol{c}}^L, \hat{\boldsymbol{o}}, \boldsymbol{ts}^P, \boldsymbol{ts}^L\}$ (Line 3). Note that there is no need to round the values of $\boldsymbol{ts}^P$ and $\boldsymbol{ts}^L$ as they are continuous. Therefore, we obtain $\hat{\Phi}^{(0)} = \{\hat{\boldsymbol{c}}^P, \hat{\boldsymbol{c}}^L, \hat{\boldsymbol{o}}, \boldsymbol{ts}^P, \boldsymbol{ts}^L\}$.

3) Note that $\Phi^{(0)*} = \{\boldsymbol{c}^P, \boldsymbol{c}^L, \boldsymbol{o}, \boldsymbol{ts}^P, \boldsymbol{ts}^L\}$ is the solution to LP-based SP2. However, the values of $\{\boldsymbol{c}^P, \boldsymbol{c}^L, \boldsymbol{o}\}$ may not be integer. Although the values of $\{\hat{\boldsymbol{c}}^P, \hat{\boldsymbol{c}}^L, \hat{\boldsymbol{o}}\}$ in $\hat{\Phi}^{(0)}$ are integer, $\hat{\Phi}^{(0)}$ may not be the solution to SP2 as the constraints may be violated. Since SP2 is relaxed from SP1, they have the same set of constraints. If the values of $\{\boldsymbol{c}^P, \boldsymbol{c}^L, \boldsymbol{o}\}$ in $\Phi^{(0)*}$ are integer, SP1 and SP2 have the same solution. For the solution to SP1, besides the constraints in SP2 must be satisfied, the values of $\{\boldsymbol{c}^P, \boldsymbol{c}^L, \boldsymbol{o}\}$ should be the integer. To find the solution to SP1, based on the given rounding solution $\hat{\Phi}$, we construct a L1-norm distance between the solutions $\Phi^* \in \mathcal{Z}$ and $\hat{\Phi}$, and we define it as $\Delta(\Phi^*, \hat{\Phi}) = \sum_{j \in \mathcal{I}, \hat{\phi}_j=1} (1 - \phi_j^*) + \sum_{j \in \mathcal{I}, \hat{\phi}_j=0} \phi_j^*$, where $\hat{\phi}_j$ and $\phi_j^*$ are the $j^{th}$ elements in $\hat{\Phi}$ and $\Phi^*$, respectively. Since $\Delta(\Phi^*, \hat{\Phi}) \ge 0$, we have the following two cases:
**Algorithm 1: Task Allocation Scheme**

**Input**: Task graph TG and 2D-mesh NoC with M cores

**Output**: Task allocation variable $\boldsymbol{x}^*$

1. Initialize $x_{j,d} = 0$ and $U_d = 0$ ($\forall j \in \mathcal{N}, \forall d \in \mathcal{M}$);

2. Sort tasks in $\mathcal{T}$ by ascending task levels, and get $\hat{\mathcal{T}}$;

3. **for each task $\tau_j$ in $\hat{\mathcal{T}}$ do**

4. | | **if** $rl(\tau_j) \neq 0$ **then**
5. | | | | **Get** $d^* = \arg \min_{d \in \mathcal{M}} F(\tau_j, P_d)$ through (34);
6. | | **else**
7. | | | | **Set** $d^* = 1$;
8. | | **end**
9. | **Assign** task $\tau_j$ to core $P_{j,d^*}$, and set $x_{j,d^*} = 1$;
10. | | **Update** $U_{d^*} = U_{d^*} + t_{j,min}^P/H$;
11. | **end**

$ts^P$ and start time of message transmission $ts^L$ are determined at this step concurrently. However, according to (7), the coupling between the slack time $t$ and other variables, e.g., $\boldsymbol{x}, c^L, ts^P$, and $ts^L$ makes it challenging to solve the problem of frequency scaling and edge scheduling. To handle this problem, we assume that the slack time $t$ has a predetermined value $\hat{t}$, which is calculated from (7) in the worst case. In this case, the communication contention constraints for any two edges, e.g., $e_{i,j}$ and $e_{m,n}$ in time are satisfied ($\eta_{i,j,m,n} = \eta_{m,n,i,j} = 1$), and the link frequencies are set to the minimum frequency $f_{l,min}$. Moreover, the objective function of (27) can be transformed to minimize the energy consumption on NoC since the core utilization rate has been determined in the first step. Thus, substituting $x_{i,s}^*$ and $\hat{t}_{i,j}^{slack}$ into (27), the problem of frequency scaling and edge scheduling is given by

$$ \text{SP1}: \min_{c^P, c^L, o, ts^P, ts^L} E_{\text{total}} \quad (35) $$

$$ \text{s.t.} \quad \begin{cases} (12) - (19), (29), \\ c_{i,k}^P, c_{i,j,g}^L, o_{i,j} \in \{0, 1\}, \quad 0 \le t_{si}, t_{sj} \le H, \\ \forall i, j \in \mathcal{N}, \forall k \in \mathcal{N}_p, \forall g \in \mathcal{N}_l. \end{cases} $$

Since (35) is an MILP problem with a smaller scale than (27), based on the structure of the problem, we proposed a novel Feasibility-Pump (FP) based method to solve it. The implementation details are summarized in Algorithm 2.

1) Let $\Phi = \{c^P, c^L, o, ts^P, ts^L\}$ denote the set of the variables in SP1, and we set $\mathcal{I} = \{j | \phi_j \in \{0, 1\}\}$, where $\phi_j$ is the $j^{th}$ element in the set $\Phi$. To make problem (35) easier to solve, we relax it into a Linear Program (LP) problem SP2 by replacing the binary variables $\{c^P, c^L, o\}$ with the continuous variables within the range $[0, 1]$ (Line 1). When SP2 is solved, we get the initial solution $\Phi^{(0)*} = \{c^P, c^L, o, ts^P, ts^L\} \in \mathcal{Z}$ (Line 1), where $\mathcal{Z}$ denotes the set of the feasible region of SP2.

2) We initialize the iteration number $n = 0$ (Line 2). Since the values of $\{c^P, c^L, o\}$ in $\Phi^{(0)*}$ may not be integer, we round the values of $\{c^P, c^L, o\}$ to the nearest integers (Line 3). When considering the task-level DVFS, each task $\tau_i$ is executed with only one V/F level on each core. Based on the $i^{th}$ row of $c^P$, we can find the maximum one among the values $\{c_{i,1}^P, \dots, c_{i,N_p}^P\}$, and denote it as $k^* = \arg \max_{k \in \mathcal{N}_p} \{c_{i,k}^P\}$. For task $\tau_i$, we assign the V/F level $(v_{p,k^*}, f_{p,k^*})$ to execute this task. Therefore, we have $\hat{c}_{i,k}^P = 1$ ($k = k^*$) and $\hat{c}_{i,k}^P = 0$ ($\forall k \neq k^* \in \mathcal{N}_p$). Similarly, we can handle the $c^L$ and $o$.

**Algorithm 2: Frequency Scaling and Edge Scheduling**

**Input**: Task allocation $\boldsymbol{x}$ and the predetermined slack time $\hat{t}$

**Output**: Frequency assignment $c^P$ and $c^L$, and the start time of execution (communication) $ts^P$ ($ts^L$)

1. Relax SP1 to a LP problem and get the initial solution $\Phi^{(0)*}$;

2. Initialize iteration number $n = 0$;

3. Round $\{c^P, c^L, o\}$ in $\Phi^{(0)*}$ to $\{\hat{c}^P, \hat{c}^L, \hat{o}\}$, and update the solution $\hat{\Phi}^{(0)} = \{\hat{c}^P, \hat{c}^L, \hat{o}, ts^P, ts^L\}$;

4. **while** $\Delta(\Phi^{(n)}, \hat{\Phi}^{(n)}) > 0$ **and** $n < n_{\max}$ **do**

5. | | Solve $\Phi^{(n)*} = \arg \min_{\Phi^{(n)}} \{\Delta(\Phi^{(n)}, \hat{\Phi}^{(n)}) : \Phi^{(n)} \in \mathcal{Z}\}$;

6. | | **if** $\Delta(\Phi^{(n)}, \hat{\Phi}^{(n)}) = 0$ **then**

7. | | | | Find the solution to SP1 and return $\Phi^{(n)*}$;

8. | | **else**

9. | | Round $\{c^P, c^L, o\}$ in $\Phi^{(n)*}$ to $\{\hat{c}^P, \hat{c}^L, \hat{o}\}$, and get $\hat{\Phi}^{(n)*} = \{\hat{c}^P, \hat{c}^L, \hat{o}, ts^P, ts^L\}$;

10. | | Set $\hat{\Phi}^{(n+1)} = \hat{\Phi}^{(n)*}$ for the next iteration;

11. | | **if** $\hat{\Phi}^{(n+1)} = \hat{\Phi}^{(n)}$ **then**

12. | | | | Select $n_f$ variables $\hat{\phi}_j$ ($j \in \mathcal{I}$) in $\hat{\Phi}^{(n+1)}$ to flip their values, and update $\hat{\Phi}^{(n+1)}$;

13. | | **end**

14. | | Update iteration number $n \to n + 1$;

15. | **end**

16. | **end**

17. | **if** $n = n_{\max} + 1$ **and** $\Delta(\Phi^{(n)}, \hat{\Phi}^{(n)}) > 0$ **then**

18. | | Solve SP1 after substituting $\{c^P, c^L, o\}$ with the corresponding values in $\hat{\Phi}^{(n)}$, and get $\hat{\Phi}^{(n+1)*}$;

19. | | **while** $\Phi^{(n+1)*} = \emptyset$ **do**

20. | | | | Update frequency levels with $c_{i,k}^P = 1 \to c_{i,k+1}^P = 1$ and $c_{i,j,g}^L = 1 \to c_{i,j,g+1}^L = 1$;

21. | | | | Solve SP1 after substituting $\{c^P, c^L\}$ with the updated values, and update $\hat{\Phi}^{(n+1)*}$;

22. | **end**

23. | **end**

Specially, the rounding of $o_{i,j}$ is given by $\hat{o}_{i,j} = [o_{i,j}]$, where $[\cdot]$ represents the rounding operation. Therefore, the rounding processes of $\{c^P, c^L, o\}$ are as follows:

$$ \left\{ \begin{array}{l} \hat{c}_{i,k}^P = 1, \text{ if } k = \arg \max \{c_{i,k}^P\}, \text{ else, } \hat{c}_{i,k}^P = 0, \\ \hat{c}_{i,j,g}^L = 1, \text{ if } g = \arg \max \{c_{i,j,g}^L\}, \text{ else, } \hat{c}_{i,j,g}^L = 0, \\ \hat{o}_{i,j} = [o_{i,j}], \quad \forall i, j \in \mathcal{N}, \forall k \in \mathcal{N}_p, \forall g \in \mathcal{N}_l. \end{array} \right. \quad (36) $$

According to (36), the values of $\{c^P, c^L, o\}$ are transformed to $\{\hat{c}^P, \hat{c}^L, \hat{o}\}$, and the rounding result is $\hat{\Phi} = \{\hat{c}^P, \hat{c}^L, \hat{o}, ts^P, ts^L\}$ (Line 3). Note that there is no need to round the values of $ts^P$ and $ts^L$ as they are continuous. Therefore, we obtain $\hat{\Phi}^{(0)} = \{\hat{c}^P, \hat{c}^L, \hat{o}, ts^P, ts^L\}$.

3) Note that $\Phi^{(0)*} = \{c^P, c^L, o, ts^P, ts^L\}$ is the solution to LP-based SP2. However, the values of $\{c^P, c^L, o\}$ may not be integer. Although the values of $\{\hat{c}^P, \hat{c}^L, \hat{o}\}$ in $\hat{\Phi}^{(0)}$ are integer, $\hat{\Phi}^{(0)}$ may not be the solution to SP2 as the constraints may be violated. Since SP2 is relaxed from SP1, they have the same set of constraints. If the values of $\{c^P, c^L, o\}$ in $\Phi^{(0)*}$ are integer, SP1 and SP2 have the same solution. For the solution to SP1, besides the constraints in SP2 must be satisfied, the values of $\{c^P, c^L, o\}$ should be the integer. To find the solution to SP1, based on the given rounding solution $\hat{\Phi}$, we construct a L1-norm distance between the solutions $\Phi^* \in \mathcal{Z}$ and $\hat{\Phi}$, and we define it as $\Delta(\Phi^*, \hat{\Phi}) = \sum_{j \in \mathcal{I}, \hat{\phi}_j=1} (1 - \phi_j^*) + \sum_{j \in \mathcal{I}, \hat{\phi}_j=0} \phi_j^*$, where $\hat{\phi}_j$ and $\phi_j^*$ are the $j^{th}$ elements in $\hat{\Phi}$ and $\Phi^*$, respectively. Since $\Delta(\Phi^*, \hat{\Phi}) \ge 0$, we have the following two cases:
<caption>**Algorithm 3: Communication Contention Management**</caption>

**Input** : The predetermined slack time $\hat{t}$ and the outputs of Algorithms 1 and 2
**Output**: Core frequency assignment $c^{P*}$, the start time of executing tasks $ts^{P*}$, and the precise slack time $t^*$
1 &nbsp;&nbsp;&nbsp;&nbsp;Update slack time $t_{i,j}^{\text{slack}*}$ ($\forall e_{i,j} \in \mathcal{E}$) based on (5)-(7);
2 &nbsp;&nbsp;&nbsp;&nbsp;Calculate time slot $\Delta t_{i,j} = \hat{t}_{i,j}^{\text{slack}} - t_{i,j}^{\text{slack}*}$ ($\forall e_{i,j} \in \mathcal{E}$);
3 &nbsp;&nbsp;&nbsp;&nbsp;**for each edge** $e_{i,j}$ **in** $\mathcal{E}$ **do**
4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Initialize $k_j^{\text{init}} = k$ for task $\tau_j$ if $c_{j,k}^{P*} = 1$;
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Calculate feasible frequency level $\hat{k}_j = \max\{k_j^R, k_j^T\}$ through (38) and (39) for task $\tau_j$;
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $E_j^{\text{comp}}(f_{p,\hat{k}_j}) < E_j^{\text{comp}}(f_{p,k^{\text{init}}})$ **then**
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Update $c_{j,k}^{P*} = 1$ ($k = \hat{k}_j$) and $c_{j,k}^{P*} = 0$ ($k \neq \hat{k}_j \in \mathcal{N}_p$);
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end**
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Calculate task start time $ts_j^*$ by (17);
10 **end**

a). If $\Delta(\Phi^*, \hat{\Phi}) = 0$, $\phi_j^* (\forall j \in \mathcal{I})$ is integer and $\phi_j^* = \hat{\phi}_j$, and thus, $\Phi^*$ is a solution to SP1.

b). If $\Delta(\Phi^*, \hat{\Phi}) > 0$, we round $\Phi^*$ and update $\hat{\Phi}$ with the rounding result. On this basis, to reduce the distance $\Delta(\Phi^*, \hat{\Phi})$, we update the values of $\Phi^*$ and $\hat{\Phi}$ iteratively until the distance $\Delta(\Phi^*, \hat{\Phi}) = 0$.

In the $n^{th}$ iteration, to minimize $\Delta(\Phi^{(n)}, \hat{\Phi}^{(n)})$ through $\Phi^{(n)}$, we construct a new problem SP3 as follows:

$$ \text{SP3: } \min_{\hat{\Phi}^{(n)}} \Delta(\Phi^{(n)}, \hat{\Phi}^{(n)}) \quad (37) $$

$$ \text{s.t.} \quad \begin{cases} (12) - (19), (29), \\ c_{i,k}^P, c_{i,j,g}^L, o_{i,j} \in [0, 1], \quad 0 \le ts_i, ts_{i,j} \le H, \\ \forall i, j \in \mathcal{N}, \forall k \in \mathcal{N}_p, \forall g \in \mathcal{N}_l, \end{cases} $$

where $\Phi^{(n)}$ and $\hat{\Phi}^{(n)}$ denote the sets of variables and the rounding solution in the $n^{th}$ iteration, respectively. Note that SP3 has the same form as SP2 except for the objective function. In the $n^{th}$ iteration, we fix $\hat{\Phi}^{(n)}$ and solve SP3 to obtain the solution $\Phi^{(n)} \in \mathcal{Z}$, so as to reduce the current distance $\Delta(\Phi^{(n)}, \hat{\Phi}^{(n)})$ (Line 5). If $\Delta(\Phi^{(n)}, \hat{\Phi}^{(n)}) = 0$, $\Phi^{(n)*}$ is the solution to SP1, and the iteration stops (Lines 6-7). Otherwise, we round the values of $\{c^P, c^L, o\}$ in $\Phi^{(n)*}$ through (36), and get a rounding solution $\hat{\Phi}^{(n)*}$, which is the given solution $\hat{\Phi}^{(n+1)} = \hat{\Phi}^{(n)*}$ in the $(n+1)^{th}$ iteration (Lines 9-10).

Specially, if $\hat{\Phi}^{(n+1)} = \hat{\Phi}^{(n)}$, the solution to SP3 stays unchanged in the $(n+1)^{th}$ iteration, which means the distance $\Delta(\hat{\Phi}^{(n+1)}, \hat{\Phi}^{(n+1)})$ is unchanged as well. To avoid endless loop, we randomly select $n_f$ elements, e.g., $\hat{\phi}_j \in \hat{\Phi}^{(n+1)}$ ($j \in \mathcal{I}$), and flip their values (Lines 11-13), where $n_f \in [N_F/2, 3N_F/4]$, and $N_F$ is a positive integer related to flipping number. During the flipping process, the value of $\hat{\phi}_j$ is reset to 1 if $\hat{\phi}_j = 0$, otherwise, $\hat{\phi}_j$ is reset to 0. Therefore, we can update $\hat{\Phi}^{(n+1)}$ to avoid cycling issue (Line 12). Then, we update the iteration number $n \to n+1$ (Line 14), and the iteration continues if $\Delta(\hat{\Phi}^{(n)}, \hat{\Phi}^{(n)}) > 0$ or $n < n_{\text{max}}$.

After iteration stops, we have $n = n_{\text{max}} + 1$. If the distance $\Delta(\hat{\Phi}^{(n)}, \hat{\Phi}^{(n)}) > 0$, the solution to SP1 is not founded, and we only get the rounding solution $\hat{\Phi}^{(n)}$. This solution cannot satisfy all constraints in SP1, especially the real-time and reliability constraints. Note that frequency assignment variables $\{c^P, c^L\}$ have an influence on real-time constraints (17) and reliability constraints (29). We iteratively adjust variables $\{c^P, c^L\}$ based on the rounding solution $\hat{\Phi}^{(n)}$ until the constraints in SP1 are satisfied (Lines 17-23). The details are as follows.

a). Since the rounding solution $\hat{\Phi}^{(n)}$ cannot satisfy the constraints in SP1, we solve SP1 by substituting $\{c^P, c^L, o\}$ with the corresponding values in $\hat{\Phi}^{(n)}$. If this problem is feasible, we get a feasible solution $\Phi^{(n+1)*}$ (Line 18), i.e., the solution to SP1 is founded, and the algorithm stops. Otherwise, we set the solution to SP1 as $\Phi^{(n+1)*} = \emptyset$.

b). When SP1 does not have a feasible solution, we increase the V/F levels of each core and link to find a feasible solution, e.g., $c_{i,k}^P = 1 \to c_{i,k+1}^P = 1$ and $c_{i,j,g}^L = 1 \to c_{i,j,g+1}^L = 1$ (Line 20). That is because increased operation frequencies on cores and links can reduce task completion time and improve task reliability to satisfy real-time and reliability constraints.

c). We update the values of $\{c^P, c^L\}$ in SP1, and solve this problem to find the feasible solution $\Phi^{(n+1)*}$ (Line 21). Similarly, if SP1 does not have a feasible solution, the solution $\Phi^{(n+1)*}$ is set to $\emptyset$.

d). We check whether $\Phi^{(n+1)*} = \emptyset$, in which case there is no feasible solution to SP1. We repeat Step b). and c). to adjust the frequencies on cores and links until the feasible solution $\Phi^{(n+1)*}$ is found, i.e., $\Phi^{(n+1)*} \neq \emptyset$ (Lines 19-22).

By the above FP method, we get the solution to SP1, i.e., $\{c^{P*}, c^{L*}, o^*, ts^{P*}, ts^{L*}\}$, but slack time $\hat{t}$ is predetermined.

### C. Communication Contention Management

We apply Algorithm 2 to solve the problem of frequency scaling and edge scheduling and get the decisions regarding the core frequency assignment $c^{P*}$, link frequency assignment $c^{L*}$, task sequence $o^*$, task scheduling time $ts^{P*}$, and edge scheduling time $ts^{L*}$. In the worst case, they are based on the given slack time $\hat{t}$. During this process, we assume that the communication contention constraints in time are always satisfied, and the slack time $\hat{t}$ is calculated with the minimum link frequency $f_{\text{min}}$. Based on $\{x^*, c^{L*}, ts^{L*}\}$, we can update the slack time $t^*$ through (5)-(7), and get the extra time slot $\Delta t_{i,j} = \hat{t}_{i,j}^{\text{slack}} - t_{i,j}^{\text{slack}*}$, $(\hat{t}_{i,j}^{\text{slack}} \in \hat{t}, t_{i,j}^{\text{slack}*} \in t^*)$. Since $\Delta t_{i,j}$ is a non-negative value, this time slot can execute task $\tau_j$ or transmit data for the edge $e_{i,j}$. Lowering the operating frequency of the core/link, the system energy consumption can be further reduced. However, when $\Delta t_{i,j}$ is used to transmit task data for the edge $e_{i,j}$, the start and end time of communication, i.e., $ts_{i,j}$ and $te_{i,j}$ will be changed. Thus, the slack time $t_{i,j}^{\text{slack}}$ is changed as well due to (5)-(7), which makes the problem difficult to solve. For problem-solving, we use time slot $\Delta t_{i,j}$ for task execution. The details are summarized in Algorithm 3.

a). We calculate the flexible slack time $t_{i,j}^{\text{slack}*}$ according to $\{x^*, c^{L*}, ts^{L*}\}$ for each edge $e_{i,j} \in \mathcal{E}$ through (5)-(7) (Line 1). Based on the calculated slack time $t_{i,j}^{\text{slack}*}$ and the predetermined slack time $\hat{t}_{i,j}^{\text{slack}}$, we can use extra slot time $\Delta t_{i,j} = \hat{t}_{i,j}^{\text{slack}} - t_{i,j}^{\text{slack}*}$ to execute task $\tau_j$ (Line 2).

b). After completing the communication for edge $e_{i,j}$, task $\tau_j$ starts its execution. The initial frequency level used to execute $\tau_j$ is set to $k_j^{\text{init}} = k$ since $c_{j,k}^{P*} = 1$ (Line 4).
<caption>**Algorithm 3: Communication Contention Management**</caption>

**Input** : The predetermined slack time $\hat{t}$ and the outputs of Algorithms 1 and 2
**Output**: Core frequency assignment $c^{P*}$, the start time of executing tasks $ts^{P*}$, and the precise slack time $t^*$
1 &nbsp;&nbsp;&nbsp;&nbsp;Update slack time $t_{i,j}^{\text{slack}^*}$ ($\forall e_{i,j} \in \mathcal{E}$) based on (5)-(7);
2 &nbsp;&nbsp;&nbsp;&nbsp;Calculate time slot $\Delta t_{i,j} = \hat{t}_{i,j}^{\text{slack}} - t_{i,j}^{\text{slack}^*}$ ($\forall e_{i,j} \in \mathcal{E}$);
3 &nbsp;&nbsp;&nbsp;&nbsp;**for** each edge $e_{i,j}$ in $\mathcal{E}$ **do**
4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Initialize $k_j^{\text{init}} = k$ for task $\tau_j$ if $c_{j,k}^{P^*} = 1$;
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Calculate feasible frequency level $\hat{k}_j = \max\{k_j^R, k_j^T\}$ through (38) and (39) for task $\tau_j$;
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $E_j^{\text{comp}}(f_{p,\hat{k}_j}) < E_j^{\text{comp}}(f_{p,k^{\text{init}}})$ **then**
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Update $c_{j,k}^{P^*} = 1$ ($k = \hat{k}_j$) and $c_{j,k}^{P^*} = 0$ ($k \neq \hat{k}_j \in \mathcal{N}_p$);
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end**
9 &nbsp;&nbsp;&nbsp;&nbsp;Calculate task start time $ts_j^*$ by (17);
10 **end**

a). If $\Delta(\Phi^*, \hat{\Phi}) = 0$, $\phi_j^* (\forall j \in \mathcal{I})$ is integer and $\phi_j^* = \hat{\phi}_j$, and thus, $\Phi^*$ is a solution to SP1.

b). If $\Delta(\Phi^*, \hat{\Phi}) > 0$, we round $\Phi^*$ and update $\hat{\Phi}$ with the rounding result. On this basis, to reduce the distance $\Delta(\Phi^*, \hat{\Phi})$, we update the values of $\Phi^*$ and $\hat{\Phi}$ iteratively until the distance $\Delta(\Phi^*, \hat{\Phi}) = 0$.

In the $n^{th}$ iteration, to minimize $\Delta(\Phi^{(n)}, \hat{\Phi}^{(n)})$ through $\Phi^{(n)}$, we construct a new problem SP3 as follows:

$$ \text{SP3: } \min_{\hat{\Phi}^{(n)}} \Delta(\Phi^{(n)}, \hat{\Phi}^{(n)}) \quad (37) $$

$$ \text{s.t.} \quad \begin{cases} (12) - (19), (29), \\ c_{i,k}^P, c_{i,j,g}^L, o_{i,j} \in [0, 1], \quad 0 \le ts_i, ts_{i,j} \le H, \\ \forall i, j \in \mathcal{N}, \quad \forall k \in \mathcal{N}_p, \quad \forall g \in \mathcal{N}_l, \end{cases} $$

where $\Phi^{(n)}$ and $\hat{\Phi}^{(n)}$ denote the sets of variables and the rounding solution in the $n^{th}$ iteration, respectively. Note that SP3 has the same form as SP2 except for the objective function. In the $n^{th}$ iteration, we fix $\hat{\Phi}^{(n)}$ and solve SP3 to obtain the solution $\Phi^{(n)} \in \mathcal{Z}$, so as to reduce the current distance $\Delta(\Phi^{(n)}, \hat{\Phi}^{(n)})$ (Line 5). If $\Delta(\Phi^{(n)}, \hat{\Phi}^{(n)}) = 0$, $\Phi^{(n)}$ is the solution to SP1, and the iteration stops (Lines 6-7). Otherwise, we round the values of $\{c^P, c^L, o\}$ in $\Phi^{(n)}$ through (36), and get a rounding solution $\hat{\Phi}^{(n)}$, which is the given solution $\hat{\Phi}^{(n+1)} = \hat{\Phi}^{(n)}$ in the $(n+1)^{th}$ iteration (Lines 9-10).

Specially, if $\hat{\Phi}^{(n+1)} = \hat{\Phi}^{(n)}$, the solution to SP3 stays unchanged in the $(n+1)^{th}$ iteration, which means the distance $\Delta(\hat{\Phi}^{(n+1)}, \hat{\Phi}^{(n+1)})$ is unchanged as well. To avoid endless loop, we randomly select $n_f$ elements, e.g., $\hat{\phi}_j \in \hat{\Phi}^{(n+1)}$ ($j \in \mathcal{I}$), and flip their values (Lines 11-13), where $n_f \in [N_F/2, 3N_F/4]$, and $N_F$ is a positive integer related to flipping number. During the flipping process, the value of $\hat{\phi}_j$ is reset to 1 if $\hat{\phi}_j = 0$, otherwise, $\hat{\phi}_j$ is reset to 0. Therefore, we can update $\hat{\Phi}^{(n+1)}$ to avoid cycling issue (Line 12). Then, we update the iteration number $n \to n+1$ (Line 14), and the iteration continues if $\Delta(\hat{\Phi}^{(n)}, \hat{\Phi}^{(n)}) > 0$ or $n < n_{\text{max}}$.

After iteration stops, we have $n = n_{\text{max}} + 1$. If the distance $\Delta(\hat{\Phi}^{(n)}, \hat{\Phi}^{(n)}) > 0$, the solution to SP1 is not founded, and we only get the rounding solution $\hat{\Phi}^{(n)}$. This solution cannot satisfy all constraints in SP1, especially the real-time and reliability constraints. Note that frequency assignment variables $\{c^P, c^L\}$ have an influence on real-time constraints (17) and reliability constraints (29).

We iteratively adjust variables $\{c^P, c^L\}$ based on the rounding solution $\hat{\Phi}^{(n)}$ until the constraints in SP1 are satisfied (Lines 17-23). The details are as follows.

a). Since the rounding solution $\hat{\Phi}^{(n)}$ cannot satisfy the constraints in SP1, we solve SP1 by substituting $\{c^P, c^L, o\}$ with the corresponding values in $\hat{\Phi}^{(n)}$. If this problem is feasible, we get a feasible solution $\Phi^{(n+1)}$ (Line 18), i.e., the solution to SP1 is founded, and the algorithm stops. Otherwise, we set the solution to SP1 as $\Phi^{(n+1)} = \emptyset$.

b). When SP1 does not have a feasible solution, we increase the V/F levels of each core and link to find a feasible solution, e.g., $c_{i,k}^P = 1 \to c_{i,k+1}^P = 1$ and $c_{i,j,g}^L = 1 \to c_{i,j,g+1}^L = 1$ (Line 20). That is because increased operation frequencies on cores and links can reduce task completion time and improve task reliability to satisfy real-time and reliability constraints.

c). We update the values of $\{c^P, c^L\}$ in SP1, and solve this problem to find the feasible solution $\Phi^{(n+1)}$ (Line 21). Similarly, if SP1 does not have a feasible solution, the solution $\Phi^{(n+1)}$ is set to $\emptyset$.

d). We check whether $\Phi^{(n+1)} = \emptyset$, in which case there is no feasible solution to SP1. We repeat Step b). and c). to adjust the frequencies on cores and links until the feasible solution $\Phi^{(n+1)}$ is found, i.e., $\Phi^{(n+1)} \neq \emptyset$ (Lines 19-22).

By the above FP method, we get the solution to SP1, i.e., $\{c^{P*}, c^{L*}, o^*, ts^{P*}, ts^{L*}\}$, but slack time $\hat{t}$ is predetermined.

### C. Communication Contention Management

We apply Algorithm 2 to solve the problem of frequency scaling and edge scheduling and get the decisions regarding the core frequency assignment $c^{P*}$, link frequency assignment $c^{L*}$, task sequence $o^*$, task scheduling time $ts^{P*}$, and edge scheduling time $ts^{L*}$. In the worst case, they are based on the given slack time $\hat{t}$. During this process, we assume that the communication contention constraints in time are always satisfied, and the slack time $\hat{t}$ is calculated with the minimum link frequency $f_{\text{min}}$. Based on $\{x^*, c^{L*}, ts^{L*}\}$, we can update the slack time $t^*$ through (5)-(7), and get the extra time slot $\Delta t_{i,j} = \hat{t}_{i,j}^{\text{slack}} - t_{i,j}^{\text{slack}^*}$, $(\hat{t}_{i,j}^{\text{slack}} \in \hat{t}, t_{i,j}^{\text{slack}^*} \in t^*)$. Since $\Delta t_{i,j}$ is a non-negative value, this time slot can execute task $\tau_j$ or transmit data for the edge $e_{i,j}$. Lowering the operating frequency of the core/link, the system energy consumption can be further reduced. However, when $\Delta t_{i,j}$ is used to transmit task data for the edge $e_{i,j}$, the start and end time of communication, i.e., $ts_{i,j}$ and $te_{i,j}$ will be changed. Thus, the slack time $t_{i,j}^{\text{slack}}$ is changed as well due to (5)-(7), which makes the problem difficult to solve. For problem-solving, we use time slot $\Delta t_{i,j}$ for task execution. The details are summarized in Algorithm 3.

a). We calculate the flexible slack time $t_{i,j}^{\text{slack}^*}$ according to $\{x^*, c^{L*}, ts^{L*}\}$ for each edge $e_{i,j} \in \mathcal{E}$ through (5)-(7) (Line 1). Based on the calculated slack time $t_{i,j}^{\text{slack}^*}$ and the predetermined slack time $\hat{t}_{i,j}^{\text{slack}}$, we can use extra slot time $\Delta t_{i,j} = \hat{t}_{i,j}^{\text{slack}} - t_{i,j}^{\text{slack}^*}$ to execute task $\tau_j$ (Line 2).

b). After completing the communication for edge $e_{i,j}$, task $\tau_j$ starts its execution. The initial frequency level used to execute $\tau_j$ is set to $k_j^{\text{init}} = k$ since $c_{j,k}^{P^*} = 1$ (Line 4).
c). Since $\Delta t_{i,j} \ge 0$ is only used for task execution, the execution time of $\tau_j$ is extended from $t_{j,k^{init}}^P$ to $t_{j,k^{init}}^P + \Delta t_{i,j}$. To satisfy the real-time constraints, the task start time $ts_j$ can be ahead using the extra slot time $\Delta t_{i,j}$, while the task end time $te_j$ remains unchanged. Considering the constraint of execution time for task $\tau_j$, the candidate of frequency level can be given by

$$k_j^T = \arg \max_{k \in \mathcal{N}_p} \{t_{j,k}^P : t_{j,k}^P \le t_{j,k^{init}}^P + \Delta t_{i,j}\}, \quad (38)$$

where $t_{j,k^{init}}^P$ denotes the execution time of task $\tau_j$ with the frequency $f_{p,k^{init}}$. Besides task execution time, operated frequencies also influence task reliability due to (29). To satisfy the reliability constraints, the candidate frequency level can be set to

$$k_j^R = \arg \min_{k \in \mathcal{N}_p} \{\ln r_{j,k}^P : \ln r_{j,k}^P + \ln R_j^L \ge \ln R_{th}\}, \quad (39)$$

where $R_j^L = \prod_{e_{i,j} \in \mathcal{E}} (\sum_{g \in \mathcal{N}_p} c_{i,j,g}^L * r_{i,j,g}^L)$ denotes the reliability probability of communication between $\tau_j$ and its predecessors, and $r_{j,k}^P$ denotes the reliability probability of executing $\tau_j$ with the frequency $f_{p,k}$. Therefore, to concurrently satisfy the constraints of task execution time and task reliability, the feasible frequency level for task $\tau_j$ is set to $\hat{k}_j = \max\{k_j^R, k_j^T\}$ (Line 5).

d). To minimize energy consumption, we determine whether the update of execution frequency is necessary (Line 6). Under the given frequency $f_{p,k}$, the computation energy is $E_j^{comp}(f_{p,k}) = P_k^{comp} t_{j,k}^P$. For task $\tau_j$, if $E_j^{comp}(f_{p,k}) < E_j^{comp}(f_{p,k^{init}})$, we set the execution frequency level as $\hat{k}_j$. Therefore, we update $c_{j,k}^P = 1$ ($k = \hat{k}_j$) and $c_{j,k}^P = 0$ ($k \ne \hat{k}_j \in \mathcal{N}_p$) (Line 7). On this basis, we can calculate task start time $ts_j^*$ based on (17) (Line 9). However, if $E_j^{comp}(f_{p,k_j}) \ge E_j^{comp}(f_{p,k^{init}})$, the frequency of $\tau_j$ is unchanged since we aim to reduce energy consumption.

e). We apply the above method for each edge $e_{i,j} \in \mathcal{E}$ to update task execution frequency. Therefore, we can obtain the core frequency assignment $c^P$, the start time of executing tasks $ts^P$, and the flexible slack time $t^*$.

To sum up, through the above three algorithms: Task Allocation Algorithm 1, Frequency Scaling and Edge Scheduling Algorithm 2, and Communication Contention Algorithm 3, we can solve this task mapping and scheduling problem and obtain the solution $\{x^*, c^P, c^L, o^*, ts^P, ts^L, t^*\}$.

### D. Algorithm Complexity

CRATMS contains Algorithm 1-Algorithm 3, and the details of their computational complexities are as follows.

a). **Task Allocation:** A heuristic based on dynamic programming is applied in Algorithm 1 to solve the task allocation problem. Firstly, tasks are sorted according to their dependencies through the bubble method. The time complexity is $O(N^2)$ when sorting $N$ tasks [40]. Then, task-to-core assignment is conducted by the dynamic programming method. The number of sub-problems influences the time complexity. Since $N$ tasks are assigned to processors for execution, the task assignment requires $N$ iterations, and

<table><caption>TABLE III
EXPERIMENTAL SET-UP</caption><thead><tr><th colspan="2">Platform Model</th></tr><tr><th>Platform Size M: 2 × 2 → 5 × 5</th><th>V/F Levels: N<sub>p</sub> = 5, N<sub>l</sub> = 5</th></tr></thead><tbody><tr><th colspan="2">Processor Parameters</th></tr><tr><td>Voltage v<sub>p,k</sub> (V)</td><td>0.75, 1.0, 1.3, 1.6, 1.8</td></tr><tr><td>Frequency f<sub>p,k</sub> (MHz)</td><td>150, 400, 600, 800, 1000</td></tr><tr><td>Power P<sub>k</sub><sup>comp</sup> (mW)</td><td>80, 170, 400, 900, 1600</td></tr><tr><th colspan="2">Link Parameters</th></tr><tr><td>Frequency f<sub>l,k</sub> (MHz)</td><td>200, 400, 600, 800, 1000</td></tr><tr><td>Power P<sub>k</sub><sup>link</sup> (mW)</td><td>160, 180, 520, 880, 1600</td></tr><tr><td>Bandwidth b<sub>ω</sub> = 32 bps</td><td>Router Energy Consumption E<sub>Rbit</sub> = 0.01 nJ</td></tr></tbody></table>

<table><thead><tr><th colspan="2">Task Model</th></tr><tr><th>Task Set</th><th>LU, GE, FFT, LE, MW, MDC, and randomly generated task sets</th></tr></thead><tbody><tr><td>Task Number N ∈ [5, 100]</td><td>Execution Cycles ω<sub>i</sub> ∈ [4 × 10<sup>7</sup>, 6 × 10<sup>8</sup>]</td></tr><tr><td>Scheduling Horizon H</td><td>Deadline D<sub>i</sub> = δ(D<sub>max</sub> - D<sub>min,i</sub>) + D<sub>min,i</sub></td></tr><tr><td>D<sub>max</sub> = H</td><td>D<sub>min,i</sub> = <sup>ω<sub>i</sub></sup>/<sub>f<sub>p,max</sub></sub> + <sup>s<sub>j,i</sub></sup>/<sub>b<sub>ω</sub>f<sub>l,max</sub></sub></td></tr></tbody></table>

<table><thead><tr><th colspan="2">Tuned Parameters</th></tr><tr><th>Task Reliability: d = {2, 3, 4, 5, 6, 7, 8}, R<sub>th</sub> = {0.9, 0.95, 0.99, 0.9999}</th><th></th></tr><tr><th>Task Deadline Factor δ</th><th>Weight Factor μ</th></tr></thead><tbody><tr><td>Min/Max/Step</td><td>0/1.2/0.1</td><td>0/1/0.1</td></tr></tbody></table>

the time complexity is $O(N)$. Thus, the time complexity of Algorithm 1 is $O(N^2 + N)$.

b). **Frequency Scaling and Edge Scheduling:** Algorithm 2 performs rounding operations iteratively to improve SP1. The rounding operation is based on the FP method. In the worst case, it needs $n_{max}$ iterations. If no feasible solution is found within the iterations, we adjust the solution of frequency assignment to obtain a feasible solution. Considering the dimensions of variables in frequency assignment $c^P = [c_{i,k}^P]_{N \times N_p}$ and $c^L = [c_{i,j,g}^L]_{N \times N \times N_l}$, the adjustments of frequency assignment require at most $N_p N + N_l N^2$ times. Hence, the time complexity of Algorithm 2 is $O(n_{max} + N_p N + N_l N^2)$.

c). **Communication Contention Management:** Algorithm 3 is applied to calculate the precise slack time for each edge (task communication). Since the number of edges is $|\mathcal{E}|$, the slack time calculation needs to perform $|\mathcal{E}|$ times, and thus, the time complexity of Algorithm 3 is $|\mathcal{E}|$.

Therefore, the time complexity of CRATMS is $O((N_l+1)N^2 + (N_p+1)N + n_{max} + |\mathcal{E}|)$. Note that task number $N$ is usually much larger than the numbers of V/F levels for cores and links ($N_p$ and $N_l$), i.e., $N \gg N_p$ and $N \gg N_l$. The total time complexity can be simplified as $O(N^2 + N + n_{max} + |\mathcal{E}|)$.

## V. SIMULATION RESULTS

In this section, we perform extensive experiments to evaluate the performance of the proposed heuristics (CRATMS), compared to the state-of-the-art methods, such as Contention and Energy-aware Task Mapping and Edge Scheduling scheme (CA-TMES) [13], ILP-based heuristics (ILP-HEU) [27], Link Contention-aware Allocation and Scheduling (LCAS) scheme [6], and Task Duplication and Path Selection-based (TDPS) scheme [21]. Specifically, CA-TMES minimizes the makespan and considers the network contention on NoC but ignores the system reliability. ILP-HEU is an energy-aware task mapping scheme without considering system reliability and network contention. LCAS is a link-contention-aware heuristic,
c). Since $\Delta t_{i,j} \ge 0$ is only used for task execution, the execution time of $\tau_j$ is extended from $t_{j,k^{init}}^P$ to $t_{j,k^{init}}^P + \Delta t_{i,j}$. To satisfy the real-time constraints, the task start time $ts_j$ can be ahead using the extra slot time $\Delta t_{i,j}$, while the task end time $te_j$ remains unchanged. Considering the constraint of execution time for task $\tau_j$, the candidate of frequency level can be given by

$$k_j^T = \arg \max_{k \in \mathcal{N}_p} \{t_{j,k}^P : t_{j,k}^P \le t_{j,k^{init}}^P + \Delta t_{i,j}\}, \quad (38)$$

where $t_{j,k^{init}}^P$ denotes the execution time of task $\tau_j$ with the frequency $f_{p,k^{init}}$. Besides task execution time, operated frequencies also influence task reliability due to (29). To satisfy the reliability constraints, the candidate frequency level can be set to

$$k_j^R = \arg \min_{k \in \mathcal{N}_p} \{\ln r_{j,k}^P : \ln r_{j,k}^P + \ln R_j^L \ge \ln R_{th}\}, \quad (39)$$

where $R_j^L = \prod_{e_{i,j} \in \mathcal{E}} (\sum_{g \in \mathcal{N}_p} c_{i,j,g}^L * r_{i,j,g}^L)$ denotes the reliability probability of communication between $\tau_j$ and its predecessors, and $r_{j,k}^P$ denotes the reliability probability of executing $\tau_j$ with the frequency $f_{p,k}$. Therefore, to concurrently satisfy the constraints of task execution time and task reliability, the feasible frequency level for task $\tau_j$ is set to $\hat{k}_j = \max\{k_j^R, k_j^T\}$ (Line 5).

d). To minimize energy consumption, we determine whether the update of execution frequency is necessary (Line 6). Under the given frequency $f_{p,k}$, the computation energy is $E_j^{comp}(f_{p,k}) = P_k^{comp} t_{j,k}^P$. For task $\tau_j$, if $E_j^{comp}(f_{p,k}) < E_j^{comp}(f_{p,k^{init}})$, we set the execution frequency level as $\hat{k}_j$. Therefore, we update $c_{j,k}^P = 1$ ($k = \hat{k}_j$) and $c_{j,k}^P = 0$ ($k \ne \hat{k}_j \in \mathcal{N}_p$) (Line 7). On this basis, we can calculate task start time $ts_j^*$ based on (17) (Line 9). However, if $E_j^{comp}(f_{p,k_j}) \ge E_j^{comp}(f_{p,k^{init}})$, the frequency of $\tau_j$ is unchanged since we aim to reduce energy consumption.

e). We apply the above method for each edge $e_{i,j} \in \mathcal{E}$ to update task execution frequency. Therefore, we can obtain the core frequency assignment $c^P$, the start time of executing tasks $ts^P$, and the flexible slack time $t^*$. To sum up, through the above three algorithms: Task Allocation Algorithm 1, Frequency Scaling and Edge Scheduling Algorithm 2, and Communication Contention Algorithm 3, we can solve this task mapping and scheduling problem and obtain the solution $\{x^*, c^P, c^L, o^*, ts^P, ts^L, t^*\}$.

### D. Algorithm Complexity

CRATMS contains Algorithm 1-Algorithm 3, and the details of their computational complexities are as follows.

a). **Task Allocation:** A heuristic based on dynamic programming is applied in Algorithm 1 to solve the task allocation problem. Firstly, tasks are sorted according to their dependencies through the bubble method. The time complexity is $O(N^2)$ when sorting $N$ tasks [40]. Then, task-to-core assignment is conducted by the dynamic programming method. The number of sub-problems influences the time complexity. Since $N$ tasks are assigned to processors for execution, the task assignment requires $N$ iterations, and

<table><caption>TABLE III
EXPERIMENTAL SET-UP</caption><thead><tr><th colspan="2">Platform Model</th></tr><tr><th>Platform Size M: 2 × 2 → 5 × 5</th><th>V/F Levels: N<sub>p</sub> = 5, N<sub>l</sub> = 5</th></tr></thead><tbody><tr><th colspan="2">Processor Parameters</th></tr><tr><td>Voltage v<sub>p,k</sub> (V)</td><td>0.75, 1.0, 1.3, 1.6, 1.8</td></tr><tr><td>Frequency f<sub>p,k</sub> (MHz)</td><td>150, 400, 600, 800, 1000</td></tr><tr><td>Power P<sub>k</sub><sup>comp</sup> (mW)</td><td>80, 170, 400, 900, 1600</td></tr><tr><th colspan="2">Link Parameters</th></tr><tr><td>Frequency f<sub>l,k</sub> (MHz)</td><td>200, 400, 600, 800, 1000</td></tr><tr><td>Power P<sub>k</sub><sup>link</sup> (mW)</td><td>160, 180, 520, 880, 1600</td></tr><tr><td>Bandwidth b<sub>ω</sub> = 32 bps</td><td>Router Energy Consumption E<sub>Rbit</sub> = 0.01 nJ</td></tr></tbody></table>

<table><thead><tr><th colspan="2">Task Model</th></tr><tr><th>Task Set</th><th>LU, GE, FFT, LE, MW, MDC, and randomly generated task sets</th></tr></thead><tbody><tr><td>Task Number N ∈ [5, 100]</td><td>Execution Cycles ω<sub>i</sub> ∈ [4 × 10<sup>7</sup>, 6 × 10<sup>8</sup>]</td></tr><tr><td>Scheduling Horizon H</td><td>Deadline D<sub>i</sub> = δ(D<sub>max</sub> - D<sub>min,i</sub>) + D<sub>min,i</sub></td></tr><tr><td>D<sub>max</sub> = H</td><td>D<sub>min,i</sub> = <sup>ω<sub>i</sub></sup>/<sub>f<sub>p,max</sub></sub> + <sup>s<sub>j,i</sub></sup>/<sub>b<sub>ω</sub>f<sub>l,max</sub></sub></td></tr></tbody></table>

<table><thead><tr><th colspan="2">Tuned Parameters</th></tr><tr><th>Task Reliability: d = {2, 3, 4, 5, 6, 7, 8}, R<sub>th</sub> = {0.9, 0.95, 0.99, 0.9999}</th><th></th></tr><tr><th>Task Deadline Factor δ</th><th>Weight Factor μ</th></tr></thead><tbody><tr><td>Min/Max/Step</td><td>0/1.2/0.1</td><td>0/1/0.1</td></tr></tbody></table>

the time complexity is $O(N)$. Thus, the time complexity of Algorithm 1 is $O(N^2 + N)$.

b). **Frequency Scaling and Edge Scheduling:** Algorithm 2 performs rounding operations iteratively to improve SP1. The rounding operation is based on the FP method. In the worst case, it needs $n_{max}$ iterations. If no feasible solution is found within the iterations, we adjust the solution of frequency assignment to obtain a feasible solution. Considering the dimensions of variables in frequency assignment $c^P = [c_{i,k}^P]_{N \times N_p}$ and $c^L = [c_{i,j,g}^L]_{N \times N \times N_l}$, the adjustments of frequency assignment require at most $N_p N + N_l N^2$ times. Hence, the time complexity of Algorithm 2 is $O(n_{max} + N_p N + N_l N^2)$.

c). **Communication Contention Management:** Algorithm 3 is applied to calculate the precise slack time for each edge (task communication). Since the number of edges is $|\mathcal{E}|$, the slack time calculation needs to perform $|\mathcal{E}|$ times, and thus, the time complexity of Algorithm 3 is $|\mathcal{E}|$.

Therefore, the time complexity of CRATMS is $O((N_l+1)N^2 + (N_p+1)N + n_{max} + |\mathcal{E}|)$. Note that task number $N$ is usually much larger than the numbers of V/F levels for cores and links ($N_p$ and $N_l$), i.e., $N \gg N_p$ and $N \gg N_l$. The total time complexity can be simplified as $O(N^2 + N + n_{max} + |\mathcal{E}|)$.

## V. SIMULATION RESULTS

In this section, we perform extensive experiments to evaluate the performance of the proposed heuristics (CRATMS), compared to the state-of-the-art methods, such as Contention and Energy-aware Task Mapping and Edge Scheduling scheme (CA-TMES) [13], ILP-based heuristics (ILP-HEU) [27], Link Contention-aware Allocation and Scheduling (LCAS) scheme [6], and Task Duplication and Path Selection-based (TDPS) scheme [21]. Specifically, CA-TMES minimizes the makespan and considers the network contention on NoC but ignores the system reliability. ILP-HEU is an energy-aware task mapping scheme without considering system reliability and network contention. LCAS is a link-contention-aware heuristic,
<figure><img src="image_4.png" /><figcaption>Fig. 3. Task allocation and scheduling of LU application when using CRATMS, LCAS, and TDPS in a 3 × 3 NoC.</figcaption></figure>

which minimizes the contention metrics to reduce commu-
nication latency through task mapping, and TDPS is a task
duplication-based reliability-aware task deployment scheme.

1) Simulation set-up: We deploy the proposed CRATMS and the other aforementioned methods on a 2D mesh NoC platform with DVFS technology. The NoC parameters are adopted from [14]. We conduct simulations on both randomly generated DAGs (the number of tasks *N* is changed within the range [5, 100]) and realistic application DAGs, such as LU Decomposition (LU) [41], Gaussian Elimination (GE) [41], Fast Fourier Transform (FFT) [41], Laplace Equation (LE) [42], Montage Workflows (MW) [43], and Molecular Dynamic Code (MDC) [41]. For the above DAGs, the number of the worst-case execution cycles $\omega_i$ for each task $\tau_i$ is assumed within the range [$4 \times 10^7$, $6 \times 10^8$] [44]. In addition, the system parameters during the simulations are considered as follows: the size of NoC platforms ($M$) is changed from $2 \times 2$ to $5 \times 5$; the weight of the objective function in problem (27) is set to $\mu \in [0, 1]$; the task deadline is $D_i = \delta(D_{max} - D_{min,i}) + D_{min,i}$ [45], where $D_{max} = H$ is the maximum task deadline (scheduling horizon), $D_{min,i}$ is the minimum execution and communication time of task $\tau_i$, and $\delta \in [0, 1.2]$ is a tuned deadline factor; the transient fault sensitivity and the reliable threshold are set to $d = \{2, 3, 4, 5, 6, 7, 8\}$ and $R_{th} = \{0.9, 0.95, 0.99, 0.9999\}$, respectively; the fault-tolerant model follows Poisson Distribution with the average fault rate $\lambda_0 = 10^{-6}$ [17], [35], [36]. The system parameters are summarized in Table III. Note that the values of these parameters do not affect the structure of the task mapping problem. Therefore, our proposed method is still applicable to other system parameters. The simulation is carried out on a computer with an Intel i7 processor operating at 2.30 GHz, and the algorithms are implemented in Matlab R2021b.

2) Simulation Results: Firstly, we illustrate the effectiveness of our method in terms of the joint optimization of energy, reliability, and network contention, compared with LCAS and TDPS. We set $\delta = 0.5$, $\mu = 0.5$, $d = 6$, and $R_{th} = 0.99$. Fig. 3 shows the task mapping results of CRATMS, LCAS, and TDPS when executing a realistic application, LU Decomposition ($N = 9$), on a 3 × 3 NoC platform. From it, we can see that under the real-time and reliability constraints, the total energy consumption of CRATMS ($E_{total} = 3.9$ J) is less than LCAS and TDPS, which are 5.1 J and 4.6 J, respectively. This is because LCAS sets all the cores/routers that operate at the same frequency level, while TDPS duplicates all the tasks to improve reliability, and thus, more energy is consumed to execute the tasks. As the results shown in Fig. 3(a) and Fig. 3(b), there is

<figure><img src="image_5.png" /><figcaption>Fig. 4. Evaluations of CRATMS with flexible and fixed V/F levels: effects of deadline parameter $\delta$.</figcaption></figure>

no network contention using CRATMS and LCAS. To alleviate network contention, CRATMS considers both flexible slack time $t_{i,j}^{slack}$ in (7) and task mapping from the aspects of time and space to optimize task and edge scheduling. However, LCAS only uses task mapping to reduce network contention, and thus, it consumes more energy than CRATMS. On the other hand, Fig. 3(c) shows that there exists network contention during the task mapping process of TDPS, which is due to task duplication, e.g., the contentions among the tasks $\tau_1 \rightarrow \tau_2, \tau_1 \rightarrow \tau'_2, \tau_1 \rightarrow \tau_3, \tau_1 \rightarrow \tau'_3, \tau_1 \rightarrow \tau_4$, and $\tau_1 \rightarrow \tau'_4$, where $\tau'_i$ represents the duplication of $\tau_i$. The above results show that the proposed CRATMS can simultaneously reduce energy consumption and network contention under reliability and real-time constraints.

Fig. 4 evaluates the influence of time factor $\delta$ on energy con-
sumption and problem feasibility using the CRATMS method.
We schedule the LU ($N = 9$), GE ($N = 14$), LE ($N = 16$),
and MW ($N = 24$) applications with flexible and fixed V/F
levels, such as ($v_{max}$, $f_{max}$) and ($v_{min}$, $f_{min}$), on a 3 × 3 NoC
platform. In addition, the parameters are set to $\mu = 0.5$,
$d = 6$, $R_{th} = 0.99$, and $\delta$ is varied from 0.2 to 1.2 with
the step of 0.2. As shown in Fig. 4, CRATMS with flexible
V/F level can lower the operation frequency to reduce energy
consumption while still satisfying the real-time and reliability
constraints. Therefore, under the given time factor $\delta$, it has a
smaller energy consumption, compared to CRATMS with the
fixed V/F level ($v_{max}$, $f_{max}$). In addition, with the value of
$\delta$ increasing, the energy consumption of CRATMS decreases.
This is because tasks with tight deadlines need to be executed
<figure><img src="image_6.png" /><figcaption>Fig. 3. Task allocation and scheduling of LU application when using CRATMS, LCAS, and TDPS in a 3 × 3 NoC.</figcaption></figure>

which minimizes the contention metrics to reduce commu-
nication latency through task mapping, and TDPS is a task
duplication-based reliability-aware task deployment scheme.

1) Simulation set-up: We deploy the proposed CRATMS and the other aforementioned methods on a 2D mesh NoC platform with DVFS technology. The NoC parameters are adopted from [14]. We conduct simulations on both randomly generated DAGs (the number of tasks *N* is changed within the range [5, 100]) and realistic application DAGs, such as LU Decomposition (LU) [41], Gaussian Elimination (GE) [41], Fast Fourier Transform (FFT) [41], Laplace Equation (LE) [42], Montage Workflows (MW) [43], and Molecular Dynamic Code (MDC) [41]. For the above DAGs, the number of the worst-case execution cycles $\omega_i$ for each task $\tau_i$ is assumed within the range [$4 \times 10^7$, $6 \times 10^8$] [44]. In addition, the system parameters during the simulations are considered as follows: the size of NoC platforms ($M$) is changed from $2 \times 2$ to $5 \times 5$; the weight of the objective function in problem (27) is set to $\mu \in [0, 1]$; the task deadline is $D_i = \delta(D_{max} - D_{min,i}) + D_{min,i}$ [45], where $D_{max} = H$ is the maximum task deadline (scheduling horizon), $D_{min,i}$ is the minimum execution and communication time of task $\tau_i$, and $\delta \in [0, 1.2]$ is a tuned deadline factor; the transient fault sensitivity and the reliable threshold are set to $d = \{2, 3, 4, 5, 6, 7, 8\}$ and $R_{th} = \{0.9, 0.95, 0.99, 0.9999\}$, respectively; the fault-tolerant model follows Poisson Distribution with the average fault rate $\lambda_0 = 10^{-6}$ [17], [35], [36]. The system parameters are summarized in Table III. Note that the values of these parameters do not affect the structure of the task mapping problem. Therefore, our proposed method is still applicable to other system parameters. The simulation is carried out on a computer with an Intel i7 processor operating at 2.30 GHz, and the algorithms are implemented in Matlab R2021b.

2) *Simulation Results:* Firstly, we illustrate the effectiveness of our method in terms of the joint optimization of energy, reliability, and network contention, compared with LCAS and TDPS. We set $\delta = 0.5$, $\mu = 0.5$, $d = 6$, and $R_{th} = 0.99$. Fig. 3 shows the task mapping results of CRATMS, LCAS, and TDPS when executing a realistic application, LU Decomposition ($N = 9$), on a 3 × 3 NoC platform. From it, we can see that under the real-time and reliability constraints, the total energy consumption of CRATMS ($E_{total} = 3.9$ J) is less than LCAS and TDPS, which are 5.1 J and 4.6 J, respectively. This is because LCAS sets all the cores/routers that operate at the same frequency level, while TDPS duplicates all the tasks to improve reliability, and thus, more energy is consumed to execute the tasks. As the results shown in Fig. 3(a) and Fig. 3(b), there is

<figure><img src="image_7.png" /><figcaption>Fig. 4. Evaluations of CRATMS with flexible and fixed V/F levels: effects of deadline parameter $\delta$.</figcaption></figure>

no network contention using CRATMS and LCAS. To alleviate network contention, CRATMS considers both flexible slack time $t_{i,j}^{\text{slack}}$ in (7) and task mapping from the aspects of time and space to optimize task and edge scheduling. However, LCAS only uses task mapping to reduce network contention, and thus, it consumes more energy than CRATMS. On the other hand, Fig. 3(c) shows that there exists network contention during the task mapping process of TDPS, which is due to task duplication, e.g., the contentions among the tasks $\tau_1 \rightarrow \tau_2$, $\tau_1 \rightarrow \tau_2'$, $\tau_1 \rightarrow \tau_3$, $\tau_1 \rightarrow \tau_3'$, $\tau_1 \rightarrow \tau_4$, and $\tau_1 \rightarrow \tau_4'$, where $\tau_i'$ represents the duplication of $\tau_i$. The above results show that the proposed CRATMS can simultaneously reduce energy consumption and network contention under reliability and real-time constraints.

Fig. 4 evaluates the influence of time factor $\delta$ on energy con-
sumption and problem feasibility using the CRATMS method.
We schedule the LU ($N = 9$), GE ($N = 14$), LE ($N = 16$),
and MW ($N = 24$) applications with flexible and fixed V/F
levels, such as ($v_{\text{max}}$, $f_{\text{max}}$) and ($v_{\text{min}}$, $f_{\text{min}}$), on a 3 × 3 NoC
platform. In addition, the parameters are set to $\mu = 0.5$,
$d = 6$, $R_{\text{th}} = 0.99$, and $\delta$ is varied from 0.2 to 1.2 with
the step of 0.2. As shown in Fig. 4, CRATMS with flexible
V/F level can lower the operation frequency to reduce energy
consumption while still satisfying the real-time and reliability
constraints. Therefore, under the given time factor $\delta$, it has a
smaller energy consumption, compared to CRATMS with the
fixed V/F level ($v_{\text{max}}$, $f_{\text{max}}$). In addition, with the value of
$\delta$ increasing, the energy consumption of CRATMS decreases.
This is because tasks with tight deadlines need to be executed
<figure><img src="image_6.png" /><figcaption>Fig. 5. Evaluation of CRATMS and TDPS under the Montage Workflow application: effects of reliability parameters *d* and *R<sub>th</sub>*.</figcaption></figure>

with a high V/F level to satisfy deadline constraints, which increases energy consumption. In Fig. 4, the symbol × denotes no feasible solution to the task mapping problem, and the energy consumption is set to zero. When the V/F levels are set to small values, CRATMS cannot meet real-time constraints for all tasks.

Fig. 5 and Fig. 6 compare the energy consumption of CRATMS and TDPS with the different transient fault sensitivities *d* and reliability thresholds *R*<sub>th</sub>. In Fig. 5, we execute the MW application (*N* = 24) on a 3 × 3 NoC platform, and we set *δ* = 0.5, *μ* = 0.5, *d* = {2, 3, 4, 5, 6, 7, 8}, and *R*<sub>th</sub> = {0.9, 0.95, 0.99, 0.9999}. Note that with parameter *d* increasing, the reliabilities of task execution and data transmission decrease. Therefore, the NoC platform needs to increase the V/F level to enhance task reliability with the high values of *d* and *R*<sub>th</sub>, increasing energy consumption. In Fig. 6, we compare CRATMS and TDPS under different *d* and *R*<sub>th</sub> parameters. During this process, we randomly generate 50 sets of DAGs, where the number of tasks *N* is varied within the range [5, 50]. The energy saving ratio is defined as (*E*<sub>total</sub><sup>TDPS</sup> − *E*<sub>total</sub><sup>CRATMS</sup>)/*E*<sub>total</sub><sup>TDPS</sup> × 100%, where *E*<sub>total</sub><sup>TDPS</sup> and *E*<sub>total</sub><sup>CRATMS</sup> are the total energy consumptions of TDPS and CRATMS, respectively. Since TDPS mainly uses task duplication to improve reliability, compared to TDPS, CRATMS has 52.17%, 48.23%, 39.43%, and 18.55% average lower energy consumption with *d* = 2, 4, 6, 8. When the value of parameter *d* is small, the system reliability is high. Therefore, CRATMS applies a low V/F level to satisfy reliability constraints and reduce energy consumption. However, with the values of parameters *d* and *R*<sub>th</sub> increasing, the system reliability will become lower and the reliability requirement will increase. To satisfy the reliability constraints, CRATMS needs to increase the V/F levels, leading to a decline in the energy-saving ratio.

Fig. 7 evaluates the effectiveness of reducing network contention using CRATMS under different NoC scales. We consider GE (*N* = 14), LE (*N* = 16), FFT (*N* = 15), MW (*N* = 24), and MDC (*N* = 41) applications, and the NoC size is changed from 2 to 5 × 5. Moreover, we set *δ* = 0.5, *μ* = 0.5, *d* = 6, and *R*<sub>th</sub> = 0.99. To evaluate the communication contention on the target platform, we introduce an average

<figure><img src="image_7.png" /><figcaption>Fig. 6. Average energy saving ratio comparison of CRATMS and TDPS under different reliability parameters *d* and *R<sub>th</sub>*.</figcaption></figure>

Route Utilization Factor (RUF) for the tasks [6]. For the edge $e_{i,j}$ between tasks $\tau_i$ and $\tau_j$, the RUF is defined as $RUF(e_{i,j}) = \frac{1}{|L_{s,d}|} \sum_{l_{m,n} \in L_{s,d}} \frac{|LOT_{l_{m,n}}^{e_{i,j}} \cap Z_{l_{m,n}}|}{|LOT_{l_{m,n}}^{e_{i,j}}|}$, where $LOT_{l_{m,n}}^{e_{i,j}}$ is the occupation time of link $l_{m,n}$ during the data transferring of the edge $e_{i,j}$, and $Z_{l_{m,n}}$ is the set of time slots when the link $l_{m,n}$ is occupied during the communication. Note that $LOT_{l_{m,n}}^{e_{i,j}} \cap Z_{l_{m,n}}$ indicates the slot of contention time of the link $l_{m,n}$, when data transmission of edge $e_{i,j}$ conflicts with other edges. $RUF(e_{i,j})$ represents the average ratio of the total contention time to the transmission time for the edge $e_{i,j}$. The lower the RUF, the less contention of the edge $e_{i,j}$. As the results depicted in Fig. 7, under the given application and NoC platform, the average RUF of CRATMS is the minimum and is close to zero. This is because CRATMS introduces flexible slack time and assigns the tasks to the cores with less route overlap, leading to reducing communication contention as much as possible. In contrast, ILP-HEU and TDPS omit communication contention. Moreover, CA-TMES mainly focuses on fixed slack time, which increases the communication time for the edges and makes real-time constraints hard to satisfy. At the same time, LCAS did not take slack time into account and only used task mapping to reduce task overlapping on routing links.

Fig. 8 compares the solution quality (e.g., objective function value, energy consumption, and computation time) achieved by the CRATMS and optimal method. Since task mapping problem (27) can be transformed into an MILP problem, the optimization solver, such as Gurobi, can be used to solve this problem and get the optimal solution. The parameters are set to $\delta = 0.5$, $\mu = 0.5$, $d = 6$, and $R_{th} = 0.99$. In Fig. 8, we perform LU ($N = 9$), GE ($N = 14$), FFT ($N = 15$), LE ($N = 16$) and MW ($N = 24$) applications on a 3 × 3 NoC platform. The results show that compared to the optimal solution, CRATMS has 24.8% higher energy consumption and 18.7% higher objective function value on average. However, the computation time of CRATMS is much less than that of the optimal method and almost varies linearly with the number of tasks. Therefore, CRATMS can achieve a trade-off between result quality and runtime.

Fig. 9(a)–Fig. 9(c) evaluate the energy consumption, reliability, and network contention of CRATMS, compared to ILP-HEU, TDPS, CA-TMES, and LCAS. We randomly generate ten DAGs, where the number of tasks *N* is changed from 10 to 100 with a step of 10. Compared to ILP-HEU and CA-TMES, CRATMS has an average 140% and 138% higher energy consumption, respectively. However, the reliabilities of ILP-HEU and CA-TMES are lower than the threshold $R_{th} = 0.99$, and ILP-HEU and CA-TMES have higher average RUF than
<figure><img src="image_8.png" /><figcaption>Fig. 5. Evaluation of CRATMS and TDPS under the Montage Workflow application: effects of reliability parameters *d* and *R<sub>th</sub>*.</figcaption></figure>

with a high V/F level to satisfy deadline constraints, which increases energy consumption. In Fig. 4, the symbol × denotes no feasible solution to the task mapping problem, and the energy consumption is set to zero. When the V/F levels are set to small values, CRATMS cannot meet real-time constraints for all tasks.

Fig. 5 and Fig. 6 compare the energy consumption of CRATMS and TDPS with the different transient fault sensitivities *d* and reliability thresholds *R*<sub>th</sub>. In Fig. 5, we execute the MW application (*N* = 24) on a 3 × 3 NoC platform, and we set *δ* = 0.5, *μ* = 0.5, *d* = {2, 3, 4, 5, 6, 7, 8}, and *R*<sub>th</sub> = {0.9, 0.95, 0.99, 0.9999}. Note that with parameter *d* increasing, the reliabilities of task execution and data transmission decrease. Therefore, the NoC platform needs to increase the V/F level to enhance task reliability with the high values of *d* and *R*<sub>th</sub>, increasing energy consumption. In Fig. 6, we compare CRATMS and TDPS under different *d* and *R*<sub>th</sub> parameters. During this process, we randomly generate 50 sets of DAGs, where the number of tasks *N* is varied within the range [5, 50]. The energy saving ratio is defined as (*E*<sub>total</sub><sup>TDPS</sup> − *E*<sub>total</sub><sup>CRATMS</sup>)/*E*<sub>total</sub><sup>TDPS</sup> × 100%, where *E*<sub>total</sub><sup>TDPS</sup> and *E*<sub>total</sub><sup>CRATMS</sup> are the total energy consumptions of TDPS and CRATMS, respectively. Since TDPS mainly uses task duplication to improve reliability, compared to TDPS, CRATMS has 52.17%, 48.23%, 39.43%, and 18.55% average lower energy consumption with *d* = 2, 4, 6, 8. When the value of parameter *d* is small, the system reliability is high. Therefore, CRATMS applies a low V/F level to satisfy reliability constraints and reduce energy consumption. However, with the values of parameters *d* and *R*<sub>th</sub> increasing, the system reliability will become lower and the reliability requirement will increase. To satisfy the reliability constraints, CRATMS needs to increase the V/F levels, leading to a decline in the energy-saving ratio.

Fig. 7 evaluates the effectiveness of reducing network contention using CRATMS under different NoC scales. We consider GE (*N* = 14), LE (*N* = 16), FFT (*N* = 15), MW (*N* = 24), and MDC (*N* = 41) applications, and the NoC size is changed from 2 to 5 × 5. Moreover, we set *δ* = 0.5, *μ* = 0.5, *d* = 6, and *R*<sub>th</sub> = 0.99. To evaluate the communication contention on the target platform, we introduce an average

<figure><img src="image_9.png" /><figcaption>Fig. 6. Average energy saving ratio comparison of CRATMS and TDPS under different reliability parameters *d* and *R<sub>th</sub>*.</figcaption></figure>

Route Utilization Factor (RUF) for the tasks [6]. For the edge $e_{i,j}$ between tasks $\tau_i$ and $\tau_j$, the RUF is defined as $RUF(e_{i,j}) = \frac{1}{|L_{s,d}|} \sum_{l_{m,n} \in L_{s,d}} \frac{|LOT_{l_{m,n}}^{e_{i,j}} \cap Z_{l_{m,n}}|}{|LOT_{l_{m,n}}^{e_{i,j}}|}$, where $LOT_{l_{m,n}}^{e_{i,j}}$ is the occupation time of link $l_{m,n}$ during the data transferring of the edge $e_{i,j}$, and $Z_{l_{m,n}}$ is the set of time slots when the link $l_{m,n}$ is occupied during the communication. Note that $LOT_{l_{m,n}}^{e_{i,j}} \cap Z_{l_{m,n}}$ indicates the slot of contention time of the link $l_{m,n}$, when data transmission of edge $e_{i,j}$ conflicts with other edges. $RUF(e_{i,j})$ represents the average ratio of the total contention time to the transmission time for the edge $e_{i,j}$. The lower the RUF, the less contention of the edge $e_{i,j}$. As the results depicted in Fig. 7, under the given application and NoC platform, the average RUF of CRATMS is the minimum and is close to zero. This is because CRATMS introduces flexible slack time and assigns the tasks to the cores with less route overlap, leading to reducing communication contention as much as possible. In contrast, ILP-HEU and TDPS omit communication contention. Moreover, CA-TMES mainly focuses on fixed slack time, which increases the communication time for the edges and makes real-time constraints hard to satisfy. At the same time, LCAS did not take slack time into account and only used task mapping to reduce task overlapping on routing links.

Fig. 8 compares the solution quality (e.g., objective function value, energy consumption, and computation time) achieved by the CRATMS and optimal method. Since task mapping problem (27) can be transformed into an MILP problem, the optimization solver, such as Gurobi, can be used to solve this problem and get the optimal solution. The parameters are set to $\delta = 0.5$, $\mu = 0.5$, $d = 6$, and $R_{th} = 0.99$. In Fig. 8, we perform LU ($N = 9$), GE ($N = 14$), FFT ($N = 15$), LE ($N = 16$) and MW ($N = 24$) applications on a 3 × 3 NoC platform. The results show that compared to the optimal solution, CRATMS has 24.8% higher energy consumption and 18.7% higher objective function value on average. However, the computation time of CRATMS is much less than that of the optimal method and almost varies linearly with the number of tasks. Therefore, CRATMS can achieve a trade-off between result quality and runtime.

Fig. 9(a)–Fig. 9(c) evaluate the energy consumption, reliability, and network contention of CRATMS, compared to ILP-HEU, TDPS, CA-TMES, and LCAS. We randomly generate ten DAGs, where the number of tasks *N* is changed from 10 to 100 with a step of 10. Compared to ILP-HEU and CA-TMES, CRATMS has an average 140% and 138% higher energy consumption, respectively. However, the reliabilities of ILP-HEU and CA-TMES are lower than the threshold $R_{th} = 0.99$, and ILP-HEU and CA-TMES have higher average RUF than
<figure><img src="image_8.png" /><figcaption>Fig. 7. Comparison of the average RUF of different task mapping methods with the different NoC platform scale.</figcaption></figure>

CRATMS. This is because ILP-HEU did not consider system reliability and network contention, while CA-TMES uses fixed slack time to alleviate the contention and ignore system reliability. Moreover, compared to LCAS and TDPS, where the reliability constraints are satisfied, CRATMS has 31.6% and 21.7% lower energy consumption, and 95.5% and 98.6% lower RUF on average, respectively. This is because LCAS minimizes the contention metric *RUF* through task-to-core allocation. It only considers the overlapping of routing links and omits the improvement of energy efficiency. In addition, TDPS uses task duplication to improve system reliability, leading to increased energy consumption and network contention. Since the flexible slack time and DVFS are optimized in task mapping, CRATMS has higher energy efficiency and lower network contention. Therefore, it is more suitable for large-scale and complex task scenarios. Fig. 9(d) evaluates the performances of CRATMS with and without DVFS switching overheads, and the parameters of switching overheads are adopted from [14]. The increment ratio of energy consumption is ($E_{total}^{switch} - E_{total}$)/$E_{total}$, where $E_{total}^{switch}$ and $E_{total}$ are the total energy consumption with and without switching overhead, respectively. Similarly, we can get the increment ratio of the objective function value in PP (27). Fig. 9(d) shows that the increment ratios of energy consumption and objective function value are 0.1% and 0.09% on average, respectively. Moreover, the ratio of switching time to task execution and communication time is 0.09% on average. Therefore, the energy and time overheads of frequency switching are much smaller than that of task execution and communication. This result is in line with the overhead analysis in [6], [29], [34]. Thus, the switching overhead can be omitted.

## VI. CONCLUSION

To minimize energy consumption, while balancing workload under real-time and reliability constraints, we formulate the task mapping problem on the NoC-based MPSoCs platform as an MINLP problem. On the one hand, the frequency scalings of both cores and links are considered simultaneously to improve task reliability and energy efficiency. On the other hand, load

<figure><img src="image_9.png" /><figcaption>Fig. 8. Energy consumption, objective function value, and running time comparison of MILP-based method and CRATMS.</figcaption></figure>

balancing and flexible slack time are introduced into the task allocation and scheduling process to alleviate network contention and increase communication efficiency while satisfying real-time constraints. Based on the structure of the task mapping problem, we propose three-step heuristics (CRATMS), including task allocation, frequency scaling and edge scheduling, and network contention management, to solve this problem efficiently. Finally, we compare CRATMS with the existing contention-aware and reliability-aware methods, and the results show that the proposed method can reduce energy consumption and network contention under multiple constraints. Therefore, CRATMS can be applied to applications with high energy efficiency, fault-tolerant, and real-time requirements. In future work, we will extend our method to heterogeneous NoC platforms considering both permanent and transient faults.

## ACKNOWLEDGMENT

This research was partly supported by the National Key Research and Development Program of China under Grant 2022YFF0902800, and the National Natural Science Foundation of China under Grants 61973163, 62303109, and 62374031.

## REFERENCES

[1] Z. Liao, Y. Ma, J. Huang, J. Wang, and J. Wang, "HOTSPOT: A UAV-assisted dynamic mobility-aware offloading for mobile-edge computing in 3-D space," *IEEE Internet Things J.*, vol. 8, no. 13, pp. 10 940–10 952, 2021.

[2] J. Wang, Y. Yang, T. Wang, R. S. Sherratt, and J. Zhang, "Big data service architecture: A survey," *J. Internet Technol.*, vol. 21, no. 2, pp. 393–405, 2020.

[3] C. Liu, K. Li, K. Li, and R. Buyya, "A new service mechanism for profit optimizations of a cloud provider and its users," *IEEE Trans. on Cloud Comput.*, vol. 9, no. 1, pp. 14–26, 2017.

[4] J. Zhang, S. Zhong, T. Wang, H.-C. Chao, and J. Wang, "Blockchain-based systems and applications: a survey," *J. Internet Technol.*, vol. 21, no. 1, pp. 1–14, 2020.

[5] M. Radetzki, C. Feng, X. Zhao, and A. Jantsch, "Methods for fault tolerance in networks-on-chip," *ACM Comput. Surv.*, vol. 46, no. 1, pp. 1–38, 2013.

[6] S. Paul, N. Chatterjee, and P. Ghosal, "Dynamic task allocation and scheduling with contention-awareness for Network-on-Chip based multicore systems," *J. Syst. Archit.*, vol. 115, pp. 1–16, 2021.

[7] K. Goossens, J. Dielissen, and A. Radulescu, "Aethereal network on chip: concepts, architectures, and implementations," *IEEE Des. Test.*, vol. 22, no. 5, pp. 414–421, 2005.

[8] I. Swarbrick, D. Gaitonde, S. Ahmad, B. Gaide, and Y. Arbel, "Network-on-chip programmable platform in VersalTM ACAP architecture," in *ACM International Symposium on Field-Programmable Gate Arrays*, 2019, pp. 212–221.

[9] J. Han, M. Choi, and Y. Kwon, "40-TFLOPS artificial intelligence processor with function-safe programmable many-cores for ISO26262 ASIL-D," *ETRI J.*, vol. 42, no. 4, pp. 468–479, 2020.
<figure><img src="image_10.png" /><figcaption>Fig. 7. Comparison of the average RUF of different task mapping methods with the different NoC platform scale.</figcaption></figure>

CRATMS. This is because ILP-HEU did not consider system reliability and network contention, while CA-TMES uses fixed slack time to alleviate the contention and ignore system reliability. Moreover, compared to LCAS and TDPS, where the reliability constraints are satisfied, CRATMS has 31.6% and 21.7% lower energy consumption, and 95.5% and 98.6% lower RUF on average, respectively. This is because LCAS minimizes the contention metric *RUF* through task-to-core allocation. It only considers the overlapping of routing links and omits the improvement of energy efficiency. In addition, TDPS uses task duplication to improve system reliability, leading to increased energy consumption and network contention. Since the flexible slack time and DVFS are optimized in task mapping, CRATMS has higher energy efficiency and lower network contention. Therefore, it is more suitable for large-scale and complex task scenarios. Fig. 9(d) evaluates the performances of CRATMS with and without DVFS switching overheads, and the parameters of switching overheads are adopted from [14]. The increment ratio of energy consumption is ($E_{total}^{switch} - E_{total}$)/$E_{total}$, where $E_{total}^{switch}$ and $E_{total}$ are the total energy consumption with and without switching overhead, respectively. Similarly, we can get the increment ratio of the objective function value in PP (27). Fig. 9(d) shows that the increment ratios of energy consumption and objective function value are 0.1% and 0.09% on average, respectively. Moreover, the ratio of switching time to task execution and communication time is 0.09% on average. Therefore, the energy and time overheads of frequency switching are much smaller than that of task execution and communication. This result is in line with the overhead analysis in [6], [29], [34]. Thus, the switching overhead can be omitted.

## VI. CONCLUSION

To minimize energy consumption, while balancing workload under real-time and reliability constraints, we formulate the task mapping problem on the NoC-based MPSoCs platform as an MINLP problem. On the one hand, the frequency scalings of both cores and links are considered simultaneously to improve task reliability and energy efficiency. On the other hand, load

<figure><img src="image_11.png" /><figcaption>Fig. 8. Energy consumption, objective function value, and running time comparison of MILP-based method and CRATMS.</figcaption></figure>

balancing and flexible slack time are introduced into the task allocation and scheduling process to alleviate network contention and increase communication efficiency while satisfying real-time constraints. Based on the structure of the task mapping problem, we propose three-step heuristics (CRATMS), including task allocation, frequency scaling and edge scheduling, and network contention management, to solve this problem efficiently. Finally, we compare CRATMS with the existing contention-aware and reliability-aware methods, and the results show that the proposed method can reduce energy consumption and network contention under multiple constraints. Therefore, CRATMS can be applied to applications with high energy efficiency, fault-tolerant, and real-time requirements. In future work, we will extend our method to heterogeneous NoC platforms considering both permanent and transient faults.

## ACKNOWLEDGMENT

This research was partly supported by the National Key Research and Development Program of China under Grant 2022YFF0902800, and the National Natural Science Foundation of China under Grants 61973163, 62303109, and 62374031.

## REFERENCES

[1] Z. Liao, Y. Ma, J. Huang, J. Wang, and J. Wang, "HOTSPOT: A UAV-assisted dynamic mobility-aware offloading for mobile-edge computing in 3-D space," *IEEE Internet Things J.*, vol. 8, no. 13, pp. 10 940–10 952, 2021.

[2] J. Wang, Y. Yang, T. Wang, R. S. Sherratt, and J. Zhang, "Big data service architecture: A survey," *J. Internet Technol.*, vol. 21, no. 2, pp. 393–405, 2020.

[3] C. Liu, K. Li, K. Li, and R. Buyya, "A new service mechanism for profit optimizations of a cloud provider and its users," *IEEE Trans. on Cloud Comput.*, vol. 9, no. 1, pp. 14–26, 2017.

[4] J. Zhang, S. Zhong, T. Wang, H.-C. Chao, and J. Wang, "Blockchain-based systems and applications: a survey," *J. Internet Technol.*, vol. 21, no. 1, pp. 1–14, 2020.

[5] M. Radetzki, C. Feng, X. Zhao, and A. Jantsch, "Methods for fault tolerance in networks-on-chip," *ACM Comput. Surv.*, vol. 46, no. 1, pp. 1–38, 2013.

[6] S. Paul, N. Chatterjee, and P. Ghosal, "Dynamic task allocation and scheduling with contention-awareness for Network-on-Chip based multicore systems," *J. Syst. Archit.*, vol. 115, pp. 1–16, 2021.

[7] K. Goossens, J. Dielissen, and A. Radulescu, "Aethereal network on chip: concepts, architectures, and implementations," *IEEE Des. Test.*, vol. 22, no. 5, pp. 414–421, 2005.

[8] I. Swarbrick, D. Gaitonde, S. Ahmad, B. Gaide, and Y. Arbel, "Network-on-chip programmable platform in VersalTM ACAP architecture," in *ACM International Symposium on Field-Programmable Gate Arrays*, 2019, pp. 212–221.

[9] J. Han, M. Choi, and Y. Kwon, "40-TFLOPS artificial intelligence processor with function-safe programmable many-cores for ISO26262 ASIL-D," *ETRI J.*, vol. 42, no. 4, pp. 468–479, 2020.