Angeliki Kritikakou

Member, IEEE Lei Mo

Member, IEEE Olivier Sentieys

Controllable QoS for Imprecise Computation Tasks on DVFS Multicores with Time and Energy Constraints

Keywords: Multicore architectures, task mapping, real-time and energy constraints, QoS, MILP, problem decomposition

Controllable QoS for Imprecise Computation Tasks on DVFS Multicores with Time and Energy Constraints

I. INTRODUCTION

In several application domains, less accurate results calculated in time are better solutions than accurate results calculated very late. Such domains include image and speech processing in multimedia applications, mobile target tracking, control system design etc. For instance, in control system design, the eigenvalues of the system state transfer matrix are of major importance, as they are related to the stability of system and the quality of control output. A minimum calculation accuracy is necessary. However, if increasing accuracy is possible, then the quality of the controller will be improved as well. This type of applications can be modeled as Imprecise Computation (IC) tasks [START_REF] Liu | Imprecise computations[END_REF], where a task is logically decomposed into a mandatory subtask and an optional subtask. The mandatory subtask must be completed before the deadline to have an acceptable result. The additional Quality of Service (QoS) is provided by the intermediate results of the optional subtask execution. The longer the execution of the optional subtasks, the higher the QoS. However, the optional subtask can be left incomplete at the cost of reduced quality.

The chip market has moved towards multi/many-core platforms [START_REF] Singh | Mapping on multi/many-core systems: survey of current and emerging trends[END_REF]. It is due to the increase in system requirements, and the bottleneck of single-core systems. Such systems provide massive computing power and can thus execute a higher volume of applications in parallel. However, energy L. Mo. A. Kritikakou, and O. Sentieys are with Univ Rennes, INRIA, IRISA, CNRS, 35042 Rennes Cedex, France. E-mail: lei.mo@inria.fr, angeliki.kritikakou@irisa.fr, olivier.sentieys@irisa.fr. consumption has become an important concern, especially for systems with limited energy budget, such as battery-powered or energy-harvesting devices. Hence, multicore platforms have been enhanced with the capability of scaling their voltage and frequency during execution to balance system performance and energy saving. To fully exploit the features of multicore systems, mechanisms are required to decide the efficient execution of the tasks on the considered multicores, while meeting system specifications.

However, the way the IC tasks are executed on a platform is decided by several factors. The first factor is the task mapping, which refers to both the task allocation (on which core each task is executed) and the task scheduling (when each task starts execution). The second factor is the decision of the voltage and frequency of the core when it runs a specific task. The third factor is the adjustment of the optional part of each task. Stateof-the-art task mapping approaches focus on how to minimize energy consumption under real-time constraints (energy-aware task mapping). Usually they are based on Dynamic Voltage and Frequency Scaling (DVFS) techniques, whereas the task model does not consider imprecise computation. Other approaches focus on how to maximize the QoS under energy and real-time constraints (QoS-aware task mapping). However, they focus on single core and multicore platforms without DVFS capabilities, whereas the task model is simplified considering independent tasks. The QoS-aware task mapping for multicore platforms is still an open issue, since there is no optimal polynomial-time solution [START_REF] Mendez-Diaz | Energy-aware scheduling mandatory/optional tasks in multicore real-time systems[END_REF].

In this work, we combine task mapping, DVFS and task adjustment for tasks with dependences under the IC model in order to: 1) maximize QoS by determining how many optional subtasks should be executed, and 2) satisfy the energy and realtime constraints by allocating and scheduling the tasks onto the cores and deciding the voltage/frequency among different tasks.

A. Related Work 1) Energy-aware Task Mapping: Several previous research contributions have addressed the energy-aware task mapping based on DVFS. When considering the independent realtime tasks and the multicore platforms, task allocation with DVFS is formulated as an Integer Linear Programming (ILP) problem in [START_REF] Li | Minimizing energy consumption for frame-based tasks on heterogeneous multiprocessor platforms[END_REF], as the frequency assigned to each processor is fixed. Therefore, a Linear Programming (LP)-based relaxation algorithm is proposed to solve this problem. Combining DVFS and Dynamic Power Management (DPM), a Mixed-Integer Linear Programming (MILP)-based task mapping problem is formulated in [START_REF] Chen | Energy optimization for realtime multiprocessor system-on-chip with optimal DVFS and DPM combination[END_REF]. The number of variables is further reduced by problem refinement, and then the refined MILP problem is optimally solved by the CPLEX solver.

Considering dependent real-time tasks adds another dimension to be optimized in the problem under study (i.e., the sequence between the tasks). In [START_REF] Zhang | Energy-efficient task scheduling for DVFS-enabled heterogeneous computing systems using a linear programming approach[END_REF]- [START_REF] Emeretlis | A logicbased Benders decomposition approach for mapping applications on heterogeneous multicore platforms[END_REF], ILP is used to formulate the voltage selection/task allocation problem. To solve the ILP problem, an LP-based heuristic method is proposed in [START_REF] Zhang | Energy-efficient task scheduling for DVFS-enabled heterogeneous computing systems using a linear programming approach[END_REF], a hybrid Genetic Algorithm (GA) is designed in [START_REF] Mahmood | Energyaware real-time task scheduling in multiprocessor systems using a hybrid genetic algorithm[END_REF], and an optimal Benders decomposition-based method is presented in [START_REF] Emeretlis | A logicbased Benders decomposition approach for mapping applications on heterogeneous multicore platforms[END_REF]. The work in [START_REF] Davare | Classification, customization, and characterization: using MILP for task allocation and scheduling[END_REF] considers an MILP-based task mapping problem and this problem is optimally solved by the CPLEX solver. The Mixed-Integer Non-Linear Programming (MINLP)based task mapping problem in [START_REF] Leung | Simultaneous task allocation, scheduling and voltage assignment for multiple-processors-core systems using mixed integer nonlinear programming[END_REF] is first relaxed to an MILP by linear approximation and then is solved by the Branch and Bound (B&B) method.

Besides minimizing computation energy, the communication energy is also taken into account in [START_REF] Ishak | Energy-aware task scheduling on heterogeneous NoC-based MPSoCs[END_REF]. The related problem is formulated by a Convex Non-Linear Programming (NLP) and an ILP-based algorithm is proposed as a solution. Some works also consider bi-objective optimization, e.g., minimizing the energy consumption/makespan (overall execution time of the tasks) and maximizing the reliability of system [START_REF] Tosun | Energy-and reliability-aware task scheduling onto heterogeneous MPSoC architectures[END_REF], [START_REF] Zhou | An efficient biobjective heuristic for scheduling workflows on heterogeneous DVS-enabled processors[END_REF]. As long as the constraints (e.g., deadline) of the tasks allows it, the aforementioned methods achieve significant energy reductions compared to the reference scenario where no DVFS is applied. However, they do not focus on QoS related issues.

2) QoS-aware Task Mapping: Other approaches aim at maximizing QoS for IC-tasks under energy supply and realtime constraints. Note that the aim of DPM is to explore the idle intervals of a processor and switch the processor to a sleep mode when the idle interval exceeds a certain level [START_REF] Chen | Energy optimization for realtime multiprocessor system-on-chip with optimal DVFS and DPM combination[END_REF]. The approaches that focus on QoS-aware task mapping are extensions of DVFS. Several works have been presented for single processors. Hence, they focus on task scheduling and optional subtasks adjustment, as there is no need to consider task allocation. For instance, the work in [START_REF] Cortes | Quasi-static assignment of voltages and optional cycles in imprecise-computation systems with energy considerations[END_REF] considers the dependent task model. It formulates the task scheduling problem with DVFS as an NLP, and a quasi-static approach is proposed as a solving method. A similar problem is considered in [START_REF] Rusu | Maximizing rewards for realtime applications with energy constraints[END_REF], [START_REF] Yu | Dynamic scheduling of imprecisecomputation tasks in maximizing QoS under energy constraints for embedded systems[END_REF], but tasks are considered independent.

For multicore platforms, most of the related work is on independent task model. In [START_REF] Zhou | Energy-adaptive scheduling of imprecise computation tasks for QoS optimization in realtime MPSoC systems[END_REF], [START_REF] Wei | Cost-constrained qos optimization for approximate computation real-time tasks in heterogeneous MPSoCs[END_REF], the task mapping of independent tasks is considered, but each processor has decided its own frequency upfront, whereas task allocation and optional subtasks adjustment sub-problems are solved in sequence. Previous work in [START_REF] Mo | Decomposed task mapping to maximize QoS in energy-constrained real-time multicores[END_REF] considers independent tasks and no DVFS capabilities. The work in [START_REF] Yu | Dynamic scheduling of imprecise-computation tasks on real-time embedded multiprocessors[END_REF] focuses on the task scheduling and optional subtasks adjustment of dependent tasks, since the task-processor binding is given upfront. Except single objective optimization, other existing approaches focus on bi-objective optimization, e.g., minimizing the energy consumption and maximizing the QoS but without restrictions on the energy supply [START_REF] Mendez-Diaz | Energy-aware scheduling mandatory/optional tasks in multicore real-time systems[END_REF], [START_REF] Micheletto | Using bioinspired metaheuristics to solve reward-based energy-aware mandatory/optional realtime tasks scheduling[END_REF]. All the aforementioned QoS-aware task mapping methods, except [START_REF] Cortes | Quasi-static assignment of voltages and optional cycles in imprecise-computation systems with energy considerations[END_REF], [START_REF] Mo | Decomposed task mapping to maximize QoS in energy-constrained real-time multicores[END_REF], employ heuristics to find the near-optimal solutions. Although heuristics can provide feasible solutions in a short amount of time, they do not provide any bounds on solution quality, and are sensitive to changes in the problem structure and parameters.

B. Contributions

Our goal is to solve the joint-design problem of QoSaware task mapping and DVFS for real-time dependent ICtasks on multicore platforms. We determine on which processor should the task be executed (task-to-processor allocation), its frequency (frequency-to-task assignment), the start time (task scheduling), and the end time (task adjustment) of each task, such that the system QoS is maximized while meeting the energy supply and the deadline of each task. The two main differences of this work with the state-of-the-art are that: i) task-to-processor allocation, frequency-to-task assignment, task scheduling and task adjustment are optimized simultaneously (joint-design problem). Solving these correlated sub-problems separately may lead to non-optimal solutions; ii) although the joint-design problem is complex, we propose a method to solve it using polynomial-time algorithms, and we can thus obtain an optimal solution while avoiding high computational complexity. To achieve that, the joint-design problem is initially formulated as an N P-hard MINLP and then it is safely transformed to an MILP without performance degradation. Further, the MILP problem is optimally solved by iterating Linear Programming (LP)-based subproblems.

Compared with previous work in [START_REF] Mo | Decomposed task mapping to maximize QoS in energy-constrained real-time multicores[END_REF], this paper considers dependent tasks (each task has its own deadline) and DVFSenabled multicore platforms. First, the problem formulation is different, as the joint-design problem (task-to-processor allocation, frequency-to-task assignment, task scheduling and task adjustment) is more complex than the previously published work. The previous work in [START_REF] Mo | Decomposed task mapping to maximize QoS in energy-constrained real-time multicores[END_REF] only considers taskto-processor allocation and task adjustment, and the related problem is formulated as an MILP. In contrast, the joint-design problem considered in this paper is an MINLP. Second, based on this new formulation, two algorithms are proposed in this paper which are able to find an optimal solution. Besides the basic method which is proposed in the previously published work, this paper also presents a way to accelerate the basic method.

Our main contributions are summarized as follows:

1) The joint-design problem to maximize system QoS, while the real-time and energy consumption constraints are not violated, is formulated as an MINLP problem.

2) We prove that by introducing the auxiliary variables and the additional constraints, the nonlinear items, which are introduced by the coupling of frequency-to-task assignment and task adjustment, can be linearized. As this linearization does not change the objective function and the feasible region of the problem, the MINLP problem is safely transformed to an MILP problem.

3) A novel Joint DVFS-QoS-aware Task mapping (JDQT) algorithm is proposed to optimally solve the MILP problem. The basic idea of JDQT algorithm is similar to closed-loop control and it is based on Benders decomposition. The MILP problem is decomposed into two smaller sub-problems with fewer variables and constraints: an ILP-based Master Problem (MP) for task-to-processor allocation and frequency-to-task assignment decisions, and an LP-based Slave Problem (SP) for task scheduling and task adjustment decisions. We prove that: i) at each iteration a lower bound and an upper bound are obtained by solving the SP and the MP, respectively, and ii) adding a proper constraint, which is constructed by the solution of the SP at previous iteration, into the MP at current iteration and solving the updated MP and the SP iteratively, the gap between the lower and the upper bounds converges to a predefined threshold within a finite number of iterations.

4) A novel Accelerated JDQT (AJDQT) algorithm is proposed to further reduce the computing time of JDQT algorithm, without violating optimality of the solution. The AJDQT algorithm is based on the fact that the computational complexity of JDQT algorithm is dominated by the cost of solving the ILPbased MP. Hence, we relax the MP to an LP to find a feasible solution. We prove that by replacing the optimal solution of MP with the feasible solution during the iteration between the MP and the SP, the optimality of the solution is guaranteed, since the additional constraints added into the MP only exclude the non-optimal and infeasible solutions. Moreover, based on the structure of the relaxed MP and SP, we design a twolayer subgradient-based algorithm to solve these problems in a distributed manner. We prove that this method is able to find an optimal solution and can further reduce the computing time of the obtained solution due to its distributed structure.

5) As the proposed JDQT and AJDQT algorithms run in an iterative way, the stopping criteria of JDQT and AJDQT algorithms can serve as the controllable parameters to tradeoff the quality of the solution (i.e., system QoS) and the computational complexity (i.e., computing time).

6) Finally, we provide extensive experimental results to analyze the quality of the solution, the computing time and the scalability of the proposed JDQT and AJDQT algorithms and compare it with stochastic methods, optimal methods and heuristics. The obtained results show that the proposed methods achieve optimal solution with reduced computing time compared to state-of-the-art optimal methods. In addition, we present how we can further reduce the computing time by controlling the solution quality.

C. Paper Organization

The paper is organized as follows: Section II presents the system model and problem formulation. In Section III, we present and formulate the JDQT and AJDQT algorithms. Section IV evaluates the performance of the proposed algorithms through several experimental results. Finally, we conclude this study in Section V.

II. SYSTEM MODEL AND PROBLEM FORMULATION

A. System Model 1) Task Model: We consider a set of dependent real-time tasks T {τ 1 , . . . , τ N }. The task set is modeled by a Directed Acyclic Graph (DAG) called G(V, E), where vertexes V denote the set of tasks to be executed, while edges E describe the data dependencies between the tasks. Without loss of generality, it is assumed that all tasks are released at the same time 0. A task starts its execution when all its preceding tasks have been completed. Each task is executed by only one processor with no preemption, such that multiple tasks can be executed on the same processor in non-overlapped time slots. Task τ i is described by a tuple {o i , M i , O i , t s i , d i , T i }, where M i is the mandatory subtask, o i is the optional subtask that can be executed to improve the result of mandatory subtask. The optional subtask has an upper bound O i (i.e., 0 ≤ o i ≤ O i ). M i and O i are measured in Worst Case Execution Cycles (WCECs) [START_REF] Yu | Dynamic scheduling of imprecisecomputation tasks in maximizing QoS under energy constraints for embedded systems[END_REF]. t s i and d i represent the start time and the deadline of task τ i , respectively. Note that t s i is an unknown variable, which is determined by task mapping decision. T i is the period of task τ i . H is the hyper-period of the task set T (i.e. the least common multiple of {T 1 , . . . , T N }). The sequences between the tasks in one hyper-period H can be formulated by an N × N binary matrix S. Denote s ij as the (i, j) th element of matrix S. If task τ i precedes task τ j (i.e., τ j starts after the end time of τ i ), s ij = 1, otherwise, s ij = 0 (i = j). Fig. 1 shows the DAG of an illustration example. The task sequence matrix associated with this DAG is given by

S =        0 1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0        .
2) Platform Model: We consider a multicore platform with M homogeneous DVFS-enabled processors {θ 1 , . . . , θ M }. Each processor θ k has L different Voltage/Frequency (V/F) levels {(v 1 , f 1 ), . . . , (v L , f L )}. The power of the processor under the given V/F level (v l , f l ) is computed as

P c l = P s l + P d l , (1)
where P s l is the static power, and P d l is the dynamic power. The dynamic power P d l is related to the clock frequency f l and supply voltage v l of the processor, expressed as

P d l = C ef f v 2 l f l ,
where C ef f is the average effective switching capacitance. For the static power P s l , we adopt P s l = v l K 1 e K2v l e K3v bs +|v bs |I j from [START_REF] Martin | Combined dynamic voltage scaling and adaptive body biasing for lower power microprocessors under dynamic workloads[END_REF]. The constants K 1 , K 2 and K 3 are technology dependent. I j is the approximately constant junction leakage current. v bs is a reverse bias voltage used to reduce the leakage power and can be treated as constant [START_REF] Jejurikar | Leakage aware dynamic voltage scaling for real-time embedded systems[END_REF]. The energy model described by [START_REF] Liu | Imprecise computations[END_REF] is widely adopted by similarly published works [START_REF] Chen | Energy optimization for realtime multiprocessor system-on-chip with optimal DVFS and DPM combination[END_REF], [START_REF] Zhou | Energy-adaptive scheduling of imprecise computation tasks for QoS optimization in realtime MPSoC systems[END_REF], [START_REF] Yu | Dynamic scheduling of imprecise-computation tasks on real-time embedded multiprocessors[END_REF].

We focus on inter-task DVFS [START_REF] Chen | Energy optimization for realtime multiprocessor system-on-chip with optimal DVFS and DPM combination[END_REF], [START_REF] Yu | Dynamic scheduling of imprecisecomputation tasks in maximizing QoS under energy constraints for embedded systems[END_REF] where the frequency of the processor stays constant during the execution of a task. It is assumed that when a processor does not execute a task, it goes to the idle state. This transition time and energy overhead is very small compared to the time and energy required to complete a task, and it is assumed to be incorporated into the execution time and energy of the task [START_REF] Li | Minimizing energy consumption for frame-based tasks on heterogeneous multiprocessor platforms[END_REF]. The system is energy-constrained in the sense that it has a fixed energy budget E s which cannot be replenished during the hyperperiod H [START_REF] Zhou | Energy-adaptive scheduling of imprecise computation tasks for QoS optimization in realtime MPSoC systems[END_REF]. Taking the available energy E s into account, the system operation can be divided into three states: i) Low: the supplied energy E s is insufficient to execute all the mandatory subtasks {M 1 , . . . , M N }, ii) High: the supplied energy E s is sufficient to execute all the mandatory and optional subtasks {M 1 +O 1 , . . . , M N +O N }, and iii) Medium: all the mandatory subtasks are ensured to finish, while not all the optional subtasks have enough energy to complete their executions. This work focuses on the medium state.

B. Problem Formulation

The problem consists of an objective function to maximize the QoS of the system subject to a set of real-time and energy constraints. In this context, we determine i) on which processor should the task be executed (task-to-processor allocation), ii) what V/F should be used for the task (frequency-to-task assignment), iii) when should the task starts (task scheduling), and iv) how many and how long are the optional subtasks (task adjustment). Therefore, we define the following variables: i) binary variable q ik = 1 if task τ i runs on processor θ k , otherwise, q ik = 0, ii) binary variable c il = 1 if task τ i executes with frequency f l , otherwise, c il = 0, iii) continuous variable t s i denotes the start time of task τ i , and iv) continuous variable o i represents the optional subtask of task τ i . We consider o i as continuous variables, and then we round the result down. This impact of one cycle is negligible since the tasks execute typically hundreds of thousands of cycles [START_REF] Cortes | Quasi-static assignment of voltages and optional cycles in imprecise-computation systems with energy considerations[END_REF]. In order to formulate the joint-design problem, we have to cope with the constraints of i) task non-preemption, ii) task dependency, iii) task deadline, and iv) energy supply, simultaneously. Let N {1, . . . , N }, M {1, . . . , M } and L {1, . . . , L}. We present our problem formulation as follows.

1) Task-to-Processor Allocation and Frequency-to-Task Assignment Constraints: Since i) each task can be assigned only one V/F, and ii) each task is executed on only one processor, the task allocation and frequency assignment variables c il and q ik must satisfy:

L l=1 c il = 1, ∀i ∈ N , (2)
M k=1 q ik = 1, ∀i ∈ N . (3)
2) Task Non-Preemption Constraints: Since each processor executes no more than one task at the same time, the nonpreemptive constraint requires that no task executed in the same processor can overlap with each other. Hence, we have

t e i ≤ t s j + (2 -q ik -q jk )H + (1 -s ij )H, ∀i, j ∈ N , i = j, ∀k ∈ M, (4)
t e j ≤ t s i + (2 -q ik -q jk )H + s ij H, ∀i, j ∈ N , i = j, ∀k ∈ M, (5)
where

t e i = t s i + L l=1 c il (w il + oi f l )
is the end time of task τ i , and w il = Mi f l is the execution time of mandatory subtask M i with frequency f l .

Constraint (4) guarantees that task τ j starts running only after task τ i is finished. Whereas constraint (5) describes the other case (i.e., task τ j should be finished before the start of task τ i ). If tasks τ i and τ j are executed on the same processor (i.e., q ik = q jk = 1), constraints (4) and ( 5) are meaningful, else, constraints (4) and ( 5) are always satisfied. Assume that q ik = q jk = 1 right now. If task τ i precedes task τ j (i.e., s ij = 1), we have constraint t e i ≤ t s j , and, thus, the constraint t e j ≤ t s i + H is always satisfied. On the other hand, if s ij = 0, the constraint t e j ≤ t s i is sufficient, as the constraint t e i ≤ t s j +H is always satisfied. Note that if task set T exists independent tasks, constraint (5) can be removed.

3) Task Dependency Constraints: One challenge to determine the number of cycles assigned to optional subtasks {o 1 , . . . , o N } is that the interval of two adjacent tasks is unknown, since the start time of the tasks is the variable. To illustrate this challenge, we use our illustration example in Fig. 1, where the tasks are allocated to four cores. Fig. 2 shows the corresponding task execution sequence. We can see that τ 5 is the closest task after task τ 1 . Hence, the start time of tasks τ 1 and τ 5 and the execution time of task τ 1 are highly correlated with each other. To determine the execution sequences between the tasks, based on the task sequence matrix S, we introduce an Execution Order Decision (EOD) matrix P [START_REF] Chen | Energy optimization for realtime multiprocessor system-on-chip with optimal DVFS and DPM combination[END_REF]. Denote p ij as the (i, j) th element of matrix P . If task τ i precedes task τ j and task τ j is the closest task to task τ i , p ij = 1, otherwise, p ij = 0.

The EOD matrix associated with the illustration example in Fig. 1 is given by

P =        0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0        .
According to the non-zero elements in matrix P , we obtain

a task execution sequence τ 1 → τ 3 → τ 4 → τ 2 τ 5 → τ 6 .
Therefore, tasks τ 5 and {τ 3 , τ 4 , τ 2 } can be executed in different cores simultaneously since they are independent. Based on the EOD matrix P , the constraints on the start time and the end time of tasks τ i and τ j are

t s j + (1 -p ij )H ≥ t s i + p ij L l=1 c il w il + o i f l , ∀i, j ∈ N , i = j, (6)
t s j -(1 -p ij )H ≤ t s i + p ij L l=1 c il w il + o i f l , ∀i, j ∈ N , i = j. (7)
If p ij = 1, task τ i precedes task τ j and τ j is the closest task of task τ i . Constraints ( 6) and ( 7) will be meaningful for task start time t s i and t s j (i.e., t s j = t s i + L l=1 c il (w il + oi f l )). While for p ij = 0, constraints ( 6) and ( 7) can be ignored since the inequalities t s j + H ≥ t s i and t s j -H ≤ t s i are always true. 4) Task Deadline Constraints: Since task τ i should be executed within a time threshold d i (0 ≤ d i ≤ H), the task real-time constraint is given by

t s i + L l=1 c il w il + o i f l ≤ d i , ∀i ∈ N . (8)

5) Energy Supply Constraint:

Based on the energy model described by [START_REF] Liu | Imprecise computations[END_REF], the total energy consumed by M processors during the hyper-period H is bounded by

N i=1 L l=1 c il w il + o i f l (P s l + P d l ) + M H - N i=1 L l=1 c il w il + o i f l P s 0 ≤ E s , (9)
where P s 0 is the static power of idle state, and M H -

N i=1 L l=1 c il (w il + oi f l )
is the time of M processors being in the idle state during the hyper-period H.

Since the system QoS derives from executing the optional subtasks {o 1 , . . . , o N }, we introduce a QoS function [START_REF] Zhou | Energy-adaptive scheduling of imprecise computation tasks for QoS optimization in realtime MPSoC systems[END_REF], [START_REF] Wei | Cost-constrained qos optimization for approximate computation real-time tasks in heterogeneous MPSoCs[END_REF], defined as N i=1 o i , and our aim is to maximize it (or to minimize its negative). Based on this objective function and the aforementioned constraints, the Primal Problem (PP) is formulated as

PP : min c,q,o,t s Φ = - N i=1 o i (10) s.t. (2) -(9), c il , q ik ∈ {0, 1}, 0 ≤ t s i ≤ H, 0 ≤ o i ≤ O i , ∀i ∈ N , ∀l ∈ L, ∀k ∈ M.
Due to the product c il o i of the optimization variables in the constraints ( 4) -( 9), the PP ( 10) is an MINLP problem.

Theorem 2.1: The QoS-aware IC-task mapping problem based on DVFS (i.e., PP [START_REF] Leung | Simultaneous task allocation, scheduling and voltage assignment for multiple-processors-core systems using mixed integer nonlinear programming[END_REF]) is N P-hard.

Proof: Please refer to [START_REF] Burer | Non-convex mixed-integer nonlinear programming: a survey[END_REF] for the details.

III. MILP-BASED APPROACH This section presents the proposed MILP formulation to linearize the MINLP problem and the two proposed algorithms, i.e. the optimal JDQT and the Accelerated JDQT algorithms.

A. MINLP linearization

Note that as the PP ( 10) is an MINLP problem, solving it is much more time consuming than solving an MILP problem [START_REF] Leung | Simultaneous task allocation, scheduling and voltage assignment for multiple-processors-core systems using mixed integer nonlinear programming[END_REF]. In this section, we adopt the idea of variable replacement [START_REF] Chen | Energy optimization for realtime multiprocessor system-on-chip with optimal DVFS and DPM combination[END_REF], [START_REF] Chantem | Temperature-aware scheduling and assignment for hard real-time applications on MPSoCs[END_REF] to eliminate the nonlinear item c il o i . By doing so, the MINLP can be safely transformed to an MILP without performance degradation.

Lemma 3.1: Given constants s 1 , s 2 > 0 and two constraint spaces

S 1 = {[h, b, x]|h = bx, -s 1 ≤ x ≤ s 2 , b ∈ {0, 1}} and S 2 = {[h, b, x]| -bs 1 ≤ h ≤ bs 2 , h + bs 1 -x -s 1 ≤ 0, h -bs 2 -x + s 2 ≥ 0, b ∈ {0, 1}}, then S 1 S 2 . Proof: Based on h = bx and -s 1 ≤ x ≤ s 2 , we have -bs 1 ≤ h ≤ bs 2 .
And further, we obtain (b -1)(x + s 1 ) ≤ 0 and (b -1)(x -s 2 ) ≥ 0 due to -s 1 ≤ x ≤ s 2 and b ∈ {0, 1}.

Hence, we have

h + bs 1 -x -s 1 ≤ 0 and h -bs 2 -x + s 2 ≥ 0. S 1 ⇒ S 2 holds. If b = 0, based on -bs 1 ≤ h ≤ bs 2 , h + bs 1 -x -s 1 ≤ 0 and h -bs 2 -x + s 2 ≥ 0, we have h = 0 and -s 1 ≤ x ≤ s 2 . For the same reason, if b = 1, we have -s 1 ≤ h = x ≤ s 2 . S 2 ⇒ S 1 holds.
Since variables c il ∈ {0, 1} and 0 ≤ o i ≤ O i , based on Lemma 3.1, an auxiliary variable (continuous) h il is introduced to replace the nonlinear item c il o i . Therefore, the constraints (4) -( 9) are safely replaced by the following constraints:

t s i + L l=1 c il w il + h il f l ≤ t s j + (2 -q ik -q jk ) H + (1 -s ij ) H, ∀i, j ∈ N , i = j, ∀k ∈ M, (11) t s j + L l=1 c jl w jl + h jl f l ≤ t s i +(2 -q ik -q jk ) H +s ij H, ∀i, j ∈ N , i = j, ∀k ∈ M, ( 12
)
t s j + (1 -p ij )H ≥ t s i + p ij L l=1 c il w il + h il f l , ∀i, j ∈ N , i = j, (13)
t s j -(1 -p ij )H ≤ t s i + p ij L l=1 c il w il + h il f l , ∀i, j ∈ N , i = j, (14)
t s i + L l=1 c il w il + h il f l ≤ d i , ∀i ∈ N , (15)
N i=1 L l=1 c il w il + h il f l (P d l + P s l -P s 0 ) + M HP s 0 ≤ E s , (16) h il ≤ c il O i , ∀i ∈ N , ∀l ∈ L, (17)
h il ≤ o i , ∀i ∈ N , ∀l ∈ L, (18)
h il + (1 -c il )O i ≥ o i , ∀i ∈ N , ∀l ∈ L. ( 19
)
where ( 17) -( 19) are the additional constraints introduced by the linearization. Consequently, the PP ( 10) is rewritten as

PP1 : min c,q,o, t s ,h Φ = - N i=1 o i (20)
s.t.

(2), ( 3), ( 11)

-(19), c il , q ik ∈ {0, 1}, 0 ≤ t s i ≤ H, 0 ≤ o i , h il ≤ O i , ∀i ∈ N , ∀l ∈ L, ∀k ∈ M.
The PP1 ( 20) is an MILP problem, as the binary and continuous variables are coupled with each other linearly. Hence, it is much easier to solve than the PP [START_REF] Leung | Simultaneous task allocation, scheduling and voltage assignment for multiple-processors-core systems using mixed integer nonlinear programming[END_REF]. Furthermore, Lemma 3.1 implies that the variable replacement will not change the feasible region of the problem (S 1 S 2 ). Since the objective functions of PP and PP1 are the same, solving PP1 is equivalent to solving PP (i.e., the optimal objective function values of PP and PP1 are the same).

B. Basic Solution Method: JDQT

In this section, we propose a novel Joint DVFS QoSaware Task mapping (JDQT) algorithm, to efficiently solve the PP1 [START_REF] Yu | Dynamic scheduling of imprecise-computation tasks on real-time embedded multiprocessors[END_REF]. The structure of JDQT is shown in Fig. 3. To solve the PP1, finding the optimal task-to-processor allocation and frequency-to-task assignment decisions is the most important step. This is because if binary variables c and q are determined, the PP1 will reduce to an LP problem, which has a simpler structure and is much easier to solve. Benders decomposition [START_REF] Benders | Partitioning procedures for solving mixed-variables programming problems[END_REF], [START_REF] Qian | Joint base station association and power control via Benders' decomposition[END_REF] is an effective method for solving MILP with guaranteed global optimality. Instead of considering all the variables and the constraints of PP1 simultaneously, Benders decomposition divides the PP1 into two smaller subproblems with fewer variables and constraints (i.e. Master Problem (MP) and Slave Problem (SP)). Then, it solves the subproblems iteratively by utilizing the solution of one in the other. The MP involves all the binary variables {c, q} and the corresponding part of the objective function, as well as the constraints of PP1. It also contains one auxiliary (continuous) variable Φ that is introduced to facilitate the interaction between the MP and the SP. On the other hand, the SP incorporates all the continuous variables {o, t s , h} and the associated constraints of PP1. Initially, we solve the MP and obtain a lower bound for PP1's optimal objective function value along with a set of values for the binary variables. We then substitute these values into the SP and solve the dual of the SP (DSP) to obtain an upper bound for PP1's optimal objective function value. Based on the solution of the DSP, a new constraint called Benders cut is generated. This constraint is added into the MP, and a new iteration is performed to solve the updated MP and SP. The iteration process stops when the gap between the upper and lower bounds is smaller than a predefined threshold.

1) The MP and The SP: Based on the structure of PP1 ( 20), the corresponding MP and SP are formulated as follows:

MP : Φ l (m) = min Φ,x Φ (21)
s.t.          (2), (3), Φ ≥ F(x, ω(ς)), ∀ς ∈ A, 0 ≥ F(x, ν(ϑ)), ∀ϑ ∈ B, c il , q ik ∈ {0, 1}, Φ ≥ 0, ∀i ∈ N , ∀l ∈ L,
where function F(x, ω) is given by

F(x, ω) = N i=1,i =j N j=1 M k=1 (α k ij + β k ij ) + (γ ij -δ ij )p ij • L l=1 c il w il - M k=1 {(α k ij + β k ij )(2 -q ik -q jk ) + [α k ij (1 -s ij ) + β k ij s ij ]}H -(γ ij + δ ij )(1 -p ij )H + N i=1 L l=1 {[c il w il (P d l + P s l -P s 0 ) + M HP s 0 -E s ]ϕ -[(θ il + τ il )c il + τ il ]O i }.
In MP (21), x (c, q) are the binary variables, ω(m)

(α(m), β(m), γ(m), δ(m), ε(m), ϕ(m), θ(m), λ(m), τ (m))
is the solution of the DSP [START_REF] Qian | Joint base station association and power control via Benders' decomposition[END_REF] at the m th iteration, and ν(m) ( α(m), β(m), γ(m), δ(m), ε(m), φ(m), θ(m), λ(m), τ (m)) is the solution of the Dual Feasibility Check Problem (DFCP) [START_REF] Chen | Cross-layer congestion control, routing and scheduling design in Ad Hoc wireless networks[END_REF] at the m th iteration. Replacing ω in F(x, ω) with ν, we obtain F(x, ν). Items Φ ≥ F(x, ω(ς)) and 0 ≥ F(x, ν(ϑ)) are the feasibility and infeasibility constraints (Benders cuts), respectively. They are generated from the solution of the DSP. A and B are the sets of iterations that the DSP has the bounded and unbounded solutions, respectively. Since i) the objective function of PP1 is constructed by the continuous variables o, and ii) the MP only considers the binary variables x, we introduce an auxiliary variable (continuous) Φ for the MP as the objective function. Φ is a proxy of PP1's objective function Φ, and both have the same physical meaning. We explain the relationship between them in the next section.

SP : Φ u (m) = min y 0 Φ (22) s.t. (11) -(19) with x(m),
where y (o, t s , h) are the continuous variables, and x(m) is the solution of the MP at the m th iteration. In fact, the SP ( 22) is "identical" to the PP1 [START_REF] Yu | Dynamic scheduling of imprecise-computation tasks on real-time embedded multiprocessors[END_REF]. Their formulations are the same except that the binary variables x(m) in the SP are fixed and given in advance.

2) The Iterations Between The MP and The SP: Note that the MP [START_REF] Micheletto | Using bioinspired metaheuristics to solve reward-based energy-aware mandatory/optional realtime tasks scheduling[END_REF] only contains the task-to-processor allocation and the frequency-to-task assignment decisions (i.e., x). Compared with the PP1 (20), the task scheduling and adjustment related constraints are relaxed, thus solving the MP yields a lower bound Φ l (m) (the proof is provided in Lemma 3.2). On the other hand, since i) x(m) may be just a feasible solution, and ii) the PP1 is a minimization problem, solving the SP with the non-optimal decision x(m) yields an upper bound Φ u (m). Denote (x * , y * ) as the optimal solution of PP1, and Φ * as the corresponding optimal objective function value. Hence, we have Φ u (m) ≤ Φ * ≤ Φ l (m). At each iteration, there is always a new feasibility constraint [START_REF] Mcdaniel | A modified Benders' partitioning algorithm for mixed integer programming[END_REF] or infeasibility constraint [START_REF] Joshi | Sensor selection via convex optimization[END_REF] added into the MP [START_REF] Micheletto | Using bioinspired metaheuristics to solve reward-based energy-aware mandatory/optional realtime tasks scheduling[END_REF] to raise the lower bound Φ l (m) and reduce the upper bound Φ u (m).

If |Φ u (m) -Φ l (m)| ≤ , (x(m), y(m)
) is an -optimal solution. And further, if is a small positive value, the optimal solution (x * , y * ) is found. The iteration process is summarized as follows:

Step 1 -Initialization: Initialize the iteration counter m = 0, the solution x(0) of the MP, the lower bound Φ l (0) = -∞, and the upper bound Φ u (0) = ∞. The feasibility and infeasibility constraints are set to null. The initial solution x(0) can be given arbitrarily, as long as it satisfies the constraints (2) -(3).

Step 2 -Solving Slave Problem: In this paper, rather than solving the SP ( 22) directly, we solve its dual problem. This is because i) the SP is a LP problem and the optimal objective function values of the SP and its dual problem are equivalent due to the strong duality [START_REF] Boyd | Convex optimization[END_REF], ii) we can construct the feasibility and infeasibility constraints through the solution of the DSP, and iii) the dual problem has fewer number of constraints than its primal problem.

To construct the dual problem of SP, we introduce the positive Lagrange multipliers α

[α k ] (α k [α k ij ]), β [β k ] (β k [β k ij ]), γ [γ ij ], δ [δ ij ], ε [ε i ], ϕ, θ [θ il ], λ [λ il ], τ [τ il ] (∀i, j ∈ N , ∀l ∈ L, ∀k ∈ M)
to the constraints ( 11) - [START_REF] Mo | Decomposed task mapping to maximize QoS in energy-constrained real-time multicores[END_REF]. The corresponding Lagrangian is

L(x(m), y, ω) = - N i=1 o i + N i=1,i =j N j=1 M k=1 α k ij t s i -t s j + L l=1 c il (m)w il + h il f l -(2 -q ik (m) -q jk (m))H -(1 -s ij )H + β k ij t s j + L l=1 c il (m)w il + h il f l -t s i -(2 -q ik (m) -q jk (m))H -s ij H + N i=1,i =j N j=1 γ ij p ij L l=1 c il (m)w il + h il f l + t s i -t s j -(1 -p ij )H + δ ij t s j -(1 -p ij )H -t s i -p ij L l=1 c il (m)w il + h il f l + N i=1 ε i t s i + L l=1 c il (m)w il + h il f l -d i + ϕ N i=1 L l=1 c il (m)w il + h il f l (P d l + P s l -P s 0 ) + M HP s 0 -E s + N i=1 L l=1 [θ il (h il -c il (m)O i ) + λ il (h il -o i ) + τ il (o i -h il -(1 -c il (m))O i )].
The dual function R(x(m), ω) is defined as the minimum value of the Lagrangian L(x(m), y, ω) with respective to the variables y [START_REF] Boyd | Convex optimization[END_REF], i.e., under the given ω,

R(x(m), ω) = min y 0 L(x(m), y, ω) = min y F(x(m), ω) + N i=1 L l=1 (τ il -λ il ) -1 o i + N i=1,i =j N j=1 M k=1 (α k ij -β k ij ) + γ ij -δ ij (t s i -t s j ) + N i=1 ε i t s i + N i=1,i =j L l=1 N j=1 M k=1 (α k ij + β k ij ) f l h il + N i=1,i =j L l=1 N j=1 (γ ij -δ ij )p ij f l h il + N i=1 L l=1 ε i + η f l + θ il + λ il -τ il h il .
For the dual function R(x(m), ω), since the continuous variables o i , t s i and h il are positive, they are finite only when following constraints hold:

L l=1 (τ il -λ il ) -1 ≥ 0, 1 ≤ i ≤ N, (23)
M k=1 (α k ij -β k ij ) + γ ij -δ ij ≥ 0, 1 ≤ i, j ≤ N, i = j, (24)
N j=1 M k=1 (α k ij + β k ij ) + (γ ij -δ ij )p ij f l ≥ 0, 1 ≤ i ≤ N, i = j, 1 ≤ l ≤ L, ( 25
)
ε i + η f l + θ il + λ il -τ il ≥ 0, 1 ≤ i ≤ N, 1 ≤ l ≤ L. ( 26
)
Thus, the dual problem associated with the SP [START_REF] Martin | Combined dynamic voltage scaling and adaptive body biasing for lower power microprocessors under dynamic workloads[END_REF] is

DSP : max ω 0 F(x(m), ω) (27)
s.t. ( 23), ( 24), ( 25), [START_REF] Benders | Partitioning procedures for solving mixed-variables programming problems[END_REF].

For convenience, the matrices and the vectors are used to denote the constraints and the variables. Hence, the PP1 ( 20) is reformulated as

PP1 : min x,y Φ(x, y) = f y (28) s.t. Ax b 1 , Cx + Dy b 2 .
where {x, y} are the variables, x is a binary vector, and y is a continuous vector. Vector f represents the objective function coefficients and f represents the transpose of vector f . DSP : max

ω 0 F(x(m), ω) = (Cx(m) -b 2 ) ω (30)
s.t. f + D ω 0.

Since DSP ( 30) is an LP problem, it can be efficiently solved using polynomial-time algorithms, such as simplex method or interior point method [START_REF] Li | Minimizing energy consumption for frame-based tasks on heterogeneous multiprocessor platforms[END_REF].

Step 3 -Solving Master Problem: Based on the solution of the DSP [START_REF] Papadimitriou | On the complexity of integer programming[END_REF], two different types of constraints are generated and are added into the MP [START_REF] Micheletto | Using bioinspired metaheuristics to solve reward-based energy-aware mandatory/optional realtime tasks scheduling[END_REF].

Φ ≥ (Cx -b 2 ) ω(m) = F(x, ω(m)) (31)
is generated and added into the MP at the (m + 1) th iteration. Note that i) the objective functions of the SP (29) and the PP1 (28) are the same, and ii) the SP (29) and the DSP [START_REF] Papadimitriou | On the complexity of integer programming[END_REF] are equivalent due to the strong duality. From [START_REF] Mcdaniel | A modified Benders' partitioning algorithm for mixed integer programming[END_REF], we can see that the auxiliary variable Φ has the same physical meaning as the objective function of the PP1 [START_REF] Boyd | Convex optimization[END_REF].

c) If the DSP has an unbounded solution: i.e., F(x(m), ω(m)) = +∞, due to the strong duality, the SP (29) has no feasible solution with x(m), and B ← {m} ∪ B. For the SP, its feasibility is related to the constraints rather than the objective function. This problem is feasible if the positive variables ξ [ξ i ] (1 ≤ i ≤ v) are introduced to relax the constraints. Based on this idea, we construct a Feasibility Check Problem (FCP)

FCP : min ξ 0 1 ξ (32) s.t. Cx(m) + Dy b 2 + ξ.
To develop the dual problem of FCP, we introduce the positive Lagrange multipliers ν(m) = [ν i (m)] (1 ≤ i ≤ v) to the FCP. Hence, the dual problem associated with the FCP (DFCP) is

DFCP : max ν 0 F(x(m), ν) = (Cx(m) -b 2 ) ν (33) s.t. 1 -ν 0.
Since FCP and DFCP are LP problems, they can be solved by methods used to solve the DSP. Denote ξ(m) and ν(m) as the solutions of FCP and DFCP at the m th iteration, respectively. If the SP (29) exists infeasible constraints, the related relax variables are non-zero, while the others are zero. Hence, we have 1 ξ(m) > 0. Since the strong duality is guaranteed between the FCP and its dual problem, we get 1 ξ(m) = (Cx(m) -b 2 ) ν(m) > 0. To avoid selecting the infeasible solution x(m) again, a new infeasibility constraint

0 ≥ (Cx -b 2 ) ν(m) = F(x, ν(m)) (34)
is generated and added into the MP at the (m + 1) th iteration.

Note that in constraints ( 31) and ( 34), all the parameters are constant except Φ and x, which are the MP variables at the (m + 1) th iteration. The reason we solve DFCB rather than FCB is that the objective function of DFCB (i.e., F(x, ν)) is a function with respect to the variables x, but not 1 ξ (i.e., the objective function of the FCB). In other word, 0 ≥ 1 ξ(m) is a less useful constraint for the MP. With this new added feasibility/infeasibility constraint, the MP is solved again to obtain a new solution x(m + 1) for the next round iteration. The iteration stops when |Φ u (m) -Φ l (m)| ≤ is satisfied.

C. Convergence Analysis

Although the MP ( 21) is composed of binary variables x and of a continuous variable Φ, it can be solved by only considering the binary variables [START_REF] Qian | Joint base station association and power control via Benders' decomposition[END_REF], [START_REF] Mcdaniel | A modified Benders' partitioning algorithm for mixed integer programming[END_REF]. The reason is as follow. From ( 21), we can see that the real constraints are (2), (3) and 0 ≥ F(x, ν(ϑ)) (∀ς ∈ A). Items F(x, ω(ς)) (∀ϑ ∈ B) can be viewed as the objective functions. Comparing the following ILP problem

MP i : Φr (i) = min x F(x, ω(i)) (35)
s.t.

   (2), (3), 0 ≥ F(x, ν(i)), ∀i ∈ B, c il , q ik ∈ {0, 1}, ∀i ∈ N , ∀l ∈ L.
with the MP, since the constraints of the MP i (∀i ∈ A) and the MP are the same, we have Φ(m) = max ∀i∈A { Φr (i)}. Hence, the MP is an ILP, which is an N P-complete problem [START_REF] Papadimitriou | On the complexity of integer programming[END_REF]. Lemma 3.2: The lower bound Φ l (m) (upper bound Φ u (m)) on the optimal objective function value Φ * is derived from the solution of the MP (21) (SP [START_REF] Martin | Combined dynamic voltage scaling and adaptive body biasing for lower power microprocessors under dynamic workloads[END_REF]) at the m th iteration.

Proof: First, we prove that Φ(m) is a lower bound of Φ * , where Φ(m) is the solution of the MP at the m th iteration. Without loss of generality, we assume that Φ(m) = Φr (ρ) = max ∀i∈A { Φr (i)}, where ρ ∈ A. Hence, we get

Φ(m) = min x F(x, ω(ρ)) ≤ F(x * , ω(ρ)) (36a) ≤ max ω 0 F(x * , ω) = Φ * , (36b)
where min x F(x, ω(ρ)) and max ω 0 F(x * , ω) are the optimal objective function values of the MP ρ (35) and the DSP (30), respectively. (36a) holds since x * is not the optimal solution of MP ρ , and (36b) holds since by solving the DSP with the optimal binary variables x * we can find the optimal objective function value Φ * . [START_REF] Boyd | Branch and bound methods[END_REF] shows that Φ l (m) = Φ(m) is a lower bound of Φ * . Next, we prove that Φ u (m) = min{Φ u (m -1), F(x(m), ω(m))} is an upper bound of Φ * . Note that min{Φ u (m -1), F(x(m), ω(m))} = min 1≤i≤m {F(x(i), ω(i))}, where x(i) and ω(i) are the solutions of the MP (21) and the DSP (30) at the i th iteration, respectively. Depending on the solution of the DSP, F(x(i), ω(i)) can be either finite or infinite. If the DSP has an unbounded solution (i.e., F(x(i), ω(i)) = +∞), it is obvious that +∞ is an upper bound of Φ * . Thus, we focus on the case when the DSP has a bounded solution (x(i), ω(i)). Due to the duality between the SP and the DSP, we have

F(x(i), ω(i)) = min y 0 Φ(x(i), y) ≥ min y 0 Φ(x * , y) = Φ * , ( 37
)
where min y 0 Φ(x, y) is the optimal objective function value of the SP under the given binary variables x. From (37), we can see that Φ u (m) = min 1≤i≤m {F(x(i), ω(i))} is an upper bound of Φ * .

Lemma 3.3: The lower bound sequence {Φ l (m)} is increasing, while the upper bound sequence {Φ u (m)} is decreasing.

Proof: Note that i) the aim of the MP is to minimize the objective function, ii) the optimal objective function value of the MP equals to the lower bound (i.e., Φ l (m) = Φ(m)), iii) the optimal objective function values of the MP at previous m iterations (i.e., { Φ(0), . . . , Φ(m)}) have been excluded by the constraints [START_REF] Mcdaniel | A modified Benders' partitioning algorithm for mixed integer programming[END_REF] and [START_REF] Joshi | Sensor selection via convex optimization[END_REF], and iv) with iteration number m increasing, more constraints are added into the MP (i.e., the feasible region of the MP shrinks). The lower bound at the + 1) th iteration (i.e., Φ l (m + 1)) is larger than the previous lower bounds {Φ l (0), . . . , Φ l (m)}. On the other hand, since Φ u (m) is achieved by Φ u (m) = min{Φ u (m -1), (Cx(m)b 2 ) ω(m)}, the upper bound at the (m + 1) th iteration (i.e., Φ u (m + 1)) is not larger than the previous upper bounds {Φ u (0), . . . , Φ u (m)}.

Theorem 3.1: At each iteration with a new feasibility constraint [START_REF] Mcdaniel | A modified Benders' partitioning algorithm for mixed integer programming[END_REF] or infeasibility constraint (34) added into the MP ( 21), the solution obtained by JDQT converges to the global optimal value within a finite number of iterations.

Proof: At each iteration m, by solving the MP and the SP, we obtain a lower bound Φ l (m) and an upper bound Φ u (m) of the optimal objective function value Φ * . The bound sequence {Φ l (0), . . . , Φ l (m)} is increasing, while the upper bound sequence {Φ u (0), . . . , Φ u (m)} is decreasing. In addition, at each iteration, there is always one new constraint (feasibility constraint [START_REF] Mcdaniel | A modified Benders' partitioning algorithm for mixed integer programming[END_REF] or infeasibility constraint [START_REF] Joshi | Sensor selection via convex optimization[END_REF]) added into the MP to exclude these non-optimal or infeasible values of binary variables x. Since the dimension of binary variables x is finite, according to the Theorem 2.4 in [START_REF] Mcdaniel | A modified Benders' partitioning algorithm for mixed integer programming[END_REF], the solution converges to the global optimal value within a finite number of iterations.

D. Accelerated Solution Method: AJDQT

Although the solution provided by JDQT is optimal, this method cannot be used to efficiently solve large problem sizes. This is due to the following reasons: i) as the MP ( 21) is an ILP, this problem is still hard to solve directly, compared with the SP, and ii) at each iteration, a new feasibility constraint [START_REF] Mcdaniel | A modified Benders' partitioning algorithm for mixed integer programming[END_REF] or infeasibility constraint ( 34) is added into the MP. With an increasing number of iterations, the computational complexity and the size of MP both increase. In order to circumvent these difficulties, we propose an accelerated JDQT (AJDQT) algorithm to further reduce the computational complexity of JDQT. This algorithm contains two parts and its structure is shown in Fig. 4.

1) Relaxation of The MP: The computational complexity of JDQT is dominated by the cost of solving the MP at each iteration. In order to reduce the computing time of JDQT, we relax the binary variables x to be continuous variables with their ranges in [0, 1]. Hence, the relaxed MP is formulated as Compared with MP, MP1 is an LP problem since all the variables are continuous. Note that if the DSP ( 30) is solved with x(m), where x(m) is the solution of the MP1, the DSP may be infeasible since x(m) may not be a binary solution. One way to solve this problem is to round the solution of MP1 (i.e., x(m)) to the nearest binary solution that is feasible to the MP. Such a binary solution, denoted by x(m), can be found by heuristics such as Feasibility Pump (FP) method [START_REF] Fischetti | The feasibility pump[END_REF].

MP1 : min Φ,x Φ (38) s.t.          (2), (3), Φ ≥ F(x, ω(ς)), ∀ς ∈ A, 0 ≥ F(x, ν(ϑ)), ∀ϑ ∈ B, 0 ≤ c il , q ik ≤ 1, Φ ≥ 0, ∀i ∈ N , ∀l ∈ L.
Theorem 3.2: Assume that x(m) is an arbitrary feasible solution of the MP. The feasibility and infeasibility constraints generated by solving the DSP (30) with x(m) do not exclude the optimal solution of PP1 [START_REF] Yu | Dynamic scheduling of imprecise-computation tasks on real-time embedded multiprocessors[END_REF].

Proof: If the DSP has a bounded solution ω(m) with x(m), the feasibility constraint is

Φ ≥ F(x, ω(m)). (39)
On the other hand, if the DSP has an unbounded solution with x(m), the infeasibility constraint is

0 ≥ F(x, ν(m)). ( 40
)
Note that (x * , y * ) is the optimal solution of PP1, and Φ * is the optimal objective function value. In the following, we prove that the optimal solution (x * , y * ) does not violate the constraints [START_REF] Sayuti | Real-time low-power task mapping in networks-on-chip[END_REF] and (40).

If the DSP has a bounded solution ω(m) with x(m), suppose that x * and Φ * violate the feasibility constraint (i.e., Φ * < F(x * , ω(m))). This contradicts the fact that Φ * is the optimal objective function value of the DSP with x * (i.e., Φ * = max ω 0 F(x * , ω) ≥ F(x * , ω(m))). Hence, the feasibility constraint [START_REF] Sayuti | Real-time low-power task mapping in networks-on-chip[END_REF] will not exclude the optimal solution x * . On the other hand, if the DSP has an unbounded solution with x(m), this solution will be excluded by the infeasibility constraint (40). Since x * = x(m), x * does not violate the infeasibility constraint (40).

2) Distributed Solution: Two-layer Subgradient-based Algorithm: Based on the structure of the MP1 [START_REF] Randazzo | A comparison of optimal methods for local access uncapacitated network design[END_REF] and the SP (29), we design a distributed solution based on two-layer subgradient algorithm to solve these problems. For convenience, the previous problem formulations of MP1 and SP are reformulated in an abstract manner as follows:

min z g z (41) s.t. b i z ≤ e i , 1 ≤ i ≤ p, z j ≤ z j ≤ z j , 1 ≤ j ≤ q,
where z is a vector of continuous variables, g is a vector of objective function coefficients, B [b 1 , . . . , b p ] and e [e 1 , . . . , e p ] are the constraints related matrix and vector, respectively.

Lemma 3.4: The MP1 (38) and the SP (29) are convex.

Proof: Let R(z) g z and

G i (z) b i z-e i (1 ≤ i ≤ p). Since O =     ∂ 2 R(z) ∂z 2 1 • • • ∂ 2 R(z) ∂z1∂zq . . . . . . . . . ∂ 2 R(z) ∂zq∂z1 • • • ∂ 2 R(z) ∂z 2 q     = 0 q×q , C i =     ∂ 2 Gi(z) ∂z 2 1 • • • ∂ 2 Gi(z) ∂z1∂zq . . . . . . . . . ∂ 2 Gi(z) ∂zq∂z1 • • • ∂ 2 Gi(z) ∂z 2 q     = 0 q×q , 1 ≤ i ≤ p,
the Hessian matrices of functions R(z) and G i (z) are positive semi-definite. Thus, the objective function and the constraints of the problem (41) are convex. According to the definition of convex problem [START_REF] Boyd | Convex optimization[END_REF], the MP1 and the SP are convex. By introducing the positive Lagrange multipliers ψ [ψ 1 , . . . , ψ p ] to the problem (41), the corresponding Lagrangian is H(z, ψ) = g z + ψ (Bz -e). Hence, the dual function is D(ψ) = min z z z H(z, ψ), and the dual problem associated with problem (41) is

max ψ 0 D(ψ) = -ψ e (42) s.t. g + B ψ 0.
For simplicity and generality, we introduce indexes n and k to count the outer-layer and inner-layer iterations, respectively. The inner-layer iteration aims to update variables z under the given Lagrange multipliers ψ, while the outer-layer iteration aims to update Lagrange multipliers ψ under the given variables z. The details are as follows.

a) Inner-Layer Iteration: Assume that the current outerlayer iteration is n. Based on the updated result of previous outer-layer iteration (i.e., ψ(n)), the variable z i is iteratively updated by

z i (n, k + 1) = z i (n, k) -σ ∂H(z(n), ψ(n)) ∂z i (n) zi z i , 1 ≤ i ≤ q, (43)
where [z i ] zi z i = max{z i , min{z i , z i }} and σ is a positive small step-size.

Since i) the functions R(z) and G i (z) are convex, and ii) the sum operation preserves the convexity, H(z, ψ) is a convex function. Denote ζ ≥ 0 as a small tolerance. The inner-layer iteration can start from an arbitrary initial point z(n, 0), and stops when ||z(n, k + 1) -z(n, k)|| 2 ≤ ζ. Hence, by iterating (43), we can obtain z(n) (i.e., the optimal solution of dual function D(ψ) under the given ψ(n)).

b) Outer-Layer Iteration: Based on the updated results of the previous inner-layer and outer-layer iterations (i.e., z(n) and ψ(n)), the Lagrange multiplier ψ j is iteratively updated by

ψ j (n + 1) = ψ j (n) + σ ∂D(ψ(n)) ∂ψ j (n) + , 1 ≤ j ≤ p, (44)
where [ψ j ] + = max{0, ψ j }.

Since the Lagrangian H(z, ψ) is convex, its dual function D(ψ) is concave [START_REF] Boyd | Convex optimization[END_REF]. Hence, the outer-layer iteration can start from the arbitrary initial points ψ(0), and stops when

||ψ(n + 1) -ψ(n)|| 2 ≤ ζ.
Note that H(z, ψ) and D(ψ) are the linear functions with respect to the variables z and the Lagrange multipliers ψ, respectively. The partial derivatives

∂H(z(n),ψ(n)) ∂zi(n)
and D(ψ(n)) ∂ψj (n) are coefficients, which implies that the variable z i (n, k) and the Lagrange multiplier ψ j (n) are updated individually (i.e., the SP (29) and the MP1 (38) can be solved in a distributed manner). c) Convergence Analysis: Note that problem (41) is convex, there is no duality gap between this problem and its dual problem (42) (i.e., solving the dual problem equals to solving its primal problem). The following Theorem 3.3 proves the convergence of the algorithm. Definition 3.2: (Statistical convergence [START_REF] Chen | Cross-layer congestion control, routing and scheduling design in Ad Hoc wireless networks[END_REF]) For an optimization problem min χ S(χ) and an iterative solution with step size σ, let χ * and χ = 1 n n l=1 χ(l) be the optimal solution and the average solution found by the n th iteration, respectively. The statistical convergence means that for any φ ≥ 0, there exists an σ such that lim sup n→∞ (S( χ)-S(χ * )) ≤ φ.

Theorem 3.3: With the iterations between the outer-layer and the inner-layer, the Lagrange multipliers ψ statistically converge to the optimal values ψ * when step size σ is a small enough value.

Proof: We construct a Lyapunov function

V(ψ(n)) = p j=1 (ψ * j -ψ j (n)) 2
, where ψ * j is the optimal value of ψ j . Denote M j (n)

D(ψ(n))
∂ψj (n) as the sub-gradient of the dual function D(ψ(n)) at the point ψ j (n). According to ψ j (n + 1) = [ψ j (n) + σM j (n)] + , we have ψ j (n + 1) ≥ 0 and ψ j (n) ≥ 0. Since σ > 0 and M j (n) could be either positive or negative, we get ψ j (n + 1) ≥ ψ j (n) + σM j (n). And further,

(ψ * j -ψ j (n + 1)) 2 ≤ (ψ * j -ψ j (n) -δM j (n)) 2 due to ψ * j ≥ 0. Hence, we have V(ψ(n + 1)) = p j=1 (ψ * j -ψ j (n + 1)) 2 ≤ p j=1 (ψ * j -ψ j (n) -σM j (n)) 2 =V(ψ(n)) + p j=1 [2σ(ψ j (n) -ψ * j )M j (n) + σ 2 M j (n) 2 ] ≤V(ψ(n)) + 2σ[D(ψ(n)) -D(ψ * )] + p j=1 σ 2 M j (n) 2 ≤V(ψ(1)) + n l=1 2σ[D(ψ(l)) -D(ψ * )] + p j=1 σ 2 M j (l) 2 , (45)
where the second inequality holds since D(ψ) is a concave function, and, thus, based on the definition of subgradient we have

p j=1 (ψ j (n) -ψ * j )M (n) ≤ D(ψ(n)) -D(ψ * ). Let ψ(n) = 1 n n l=1 ψ(l).
Based on the concavity of dual function D(ψ) and Jensen's inequality [START_REF] Boyd | Convex optimization[END_REF], we get

n l=1 [D(ψ(l)) -D(ψ * )] ≤ n[D(ψ(n)) -D(ψ * )]. (46)
Assume that p j=1 ψ j (l) 2 ≤ B since {ψ j (l)} are bounded. Substituting (46) into (45) and noting that V(ψ(n + 1)) ≥ 0, we have

D(ψ * ) -D(ψ(n)) ≤ T (ψ(1))+nσ 2 B 2nσ . From lim sup n→∞ (D(ψ * )) -D(ψ(n)) ≤ σB
2 , we can see that the Lagrange multipliers ψ statistically converge to the optimal values ψ * when step size σ is a small enough value.

Hence, by iterating the equations ( 43) and (44), we obtain the optimal solutions of the MP1 [START_REF] Randazzo | A comparison of optimal methods for local access uncapacitated network design[END_REF] and the SP [START_REF] Mcdaniel | A modified Benders' partitioning algorithm for mixed integer programming[END_REF].

3) Run-Time Complexity: The MP1 (38) and the SP (29) can be solved by either the interior point method or the proposed distributed method. Using the interior point method, the computational complexity is O(d 3 ), where d is the number of the variables [START_REF] Joshi | Sensor selection via convex optimization[END_REF]. Based on the structures of MP1 and SP, we have d = N (2 + L) and d = 2N L, respectively. When using the proposed distributed method, since the inter-layer and the outer-layer iterations are based on the subgradient method, the computational complexity is O(U 2 R 2 ζ -2 ) [START_REF] Ito | A family of subgradient-based methods for convex optimization problems in a unifying framework[END_REF]. U is the distance between an optimal solution and the initial point, and R is a Lipschitz constant for the objective function. Therefore, the proposed distributed method has lower computational complexity.

IV. SIMULATION RESULTS

The multicore platform model used in the experiments is based on 70 nm technology [START_REF] Chen | Energy optimization for realtime multiprocessor system-on-chip with optimal DVFS and DPM combination[END_REF]. The processor operates at five voltage levels in the range of [0.65 V, 0.85 V ] with a step of 50 mV (i.e., L = 5). The power of the processor in the idle state is set to P s 0 = 80 µW , while the corresponding frequency f l , the dynamic power P d l , and the static power P s l under different voltage levels are shown in Table I. The number of processors (i.e., M ) is tuned from 4 to 8 with a step of 2. We generate task graphs with 10 to 50 tasks (i.e., the task number N is tuned from 10 to 50 with a step of 5). The WCECs of the mandatory part M i and the maximum optional part O i of task τ i (∀i ∈ N ) are assumed to be in the range [4 × 10 7 , 6 × 10 8 ] [17]. To set the absolute deadline of task τ i , we introduce temporary start time ti s and relative deadline r i for task τ i . Then, the absolute deadline d i is calculated by d i = ti s + r i . The relative deadline r i is assumed to be in the range [r i , r i ],

where

r i = min ∀l∈L { Mi+Oi f l } and r i = max ∀l∈L { Mi+Oi f l }
are the minimum time and the maximum time required to execute {M 1 + O 1 , . . . , M N + O N } cycles, respectively. We calculate the value of temporary start time ti s through the EOD matrix P . When p ij = 1 (i.e., task τ i precedes task τ j and τ j is the closest task of τ i ), we set the temporary end time of task τ i equal to the temporary start time of task τ j (i.e., ti e = ti s +r i = tj s ). If τ i is the first task in one hyper-period, we set ti s = 0. Moreover, we assume that the hyper-period of the tasks is H = max ∀i∈N {d i }. Since system is in the medium energy state, the energy supply is set to E s = ηE h , where

E h = M HP s 0 + N i=1 [min ∀l∈L Mi+Oi f l (P s l + P d l -P s 0 )
] is the minimum energy required to execute {M 1 + O 1 , . . . , M N + O N } cycles. The energy efficiency factor η is tuned from 0.8 to 0.9 with a step of 0.05. Note that different multi-core platforms and task graphs will lead to different parameters {A, C, D, f , b 1 , b 2 } for the PP1 [START_REF] Boyd | Convex optimization[END_REF]. However, the problem structures under different parameters are the same, and, thus, different algorithms can be compared under given system parameters. Initially, we compare the behavior (system QoS and computing time) of the proposed JDQT with: i) optimal approaches, i.e. Branch and Bound method (B&B) [START_REF] Boyd | Branch and bound methods[END_REF], [START_REF] Pang | Communication-aware branch and bound with cluster-based latency-constraint mapping technique on network-on-chip[END_REF] and Branch and Cut method (B&C) [START_REF] Randazzo | A comparison of optimal methods for local access uncapacitated network design[END_REF], which are known to provide optimal solution for the MILP problem -as far as we know no optimal algorithm exists for the problem formulation PP1 [START_REF] Yu | Dynamic scheduling of imprecise-computation tasks on real-time embedded multiprocessors[END_REF], ii) stochastic approaches (i.e. Genetic Algorithm (GA) [START_REF] Sayuti | Real-time low-power task mapping in networks-on-chip[END_REF]), and iii) heuristic (i.e., a two-step method that combines B&B and LP relaxation provided by Matlab optimization toolbox [40]). Then, we compare the computing time and the convergence iterations of JDQT and AJDQT and we explore the QoS and the computing time under controlled solution degradation. Finally, we compare the QoS and the energy consumption of applying JDQT to solve the QoS-aware task mapping problem (QoS-OPT, i.e., PP1 (20)), and the following energy-aware task mapping problem (NRG-OPT): 2), ( 3), ( 11), ( 12), ( 13), ( 14), ( 15), ( 17), [START_REF] Wei | Cost-constrained qos optimization for approximate computation real-time tasks in heterogeneous MPSoCs[END_REF], [START_REF] Mo | Decomposed task mapping to maximize QoS in energy-constrained real-time multicores[END_REF].

min c,q,o, ts ,h N i=1 L l=1 c il w il + h il f l (P l d + P l s -P 0 s ) s.t. (
The simulations are performed on a laptop with quad-core 2.5 GHz Intel i7 processor and 16 GB RAM, and the algorithms are implemented in Matlab 2016a.

A. Comparison with Existing Algorithms

The QoS achieved by JDQT for all tuned parameters (i.e., processor number M , task number N , and energy efficiency factor η) is shown in Fig. 5. With M , N and η parameters varying, 3 × 9 × 3 = 81 instances are generated. We observe that the QoS i) increases with η under given M and N , and ii) increases with N under given M and η (as the energy supply E s increases with N and η). However, when we fix N and η and change the value of M , the differences between the achieved QoS are small, compared with changing N and η. Although with M increasing, more tasks are allowed to be executed on different processors simultaneously. As the energy supply E s and the task deadline, which is determined by the EOD matrix P , are fixed, the QoS improvement achieved by increasing the value of M is limited. Moreover, the QoS achieved by JDQT, B&B and B&C are the same for all tuned M , N and η parameters, and, thus, JDQT also finds an optimal solution. We further compare the QoS gain of JDQT with GA and heuristic. The statistical property of QoS gain is shown in Fig. 6. The QoS gain between JDQT and GA (JDQT and heuristic) is given by Q J (M,N,η)-Q G (M,N,η)

Q J (M,N,η) ( Q J (M,N,η)-Q H (M,N,η) Q J (M,N,η)
), where Q J (M, N, η), Q G (M, N, η) and Q H (M, N, η) are the QoS achieved by JDQT, GA and heuristic under given M , N and η parameters, respectively. The box plot of "JDQT vs GA" with η = 0.8 shows the statistical property of data set { Q J (M,N,0.8)-Q G (M,N,0.8)

Q J (M,N,0.8)
} for all tuned M and N parameters. On each box, the central mark indicates the median, and the bottom and top edges of the box indicate the 25 th and 75 th percentiles, respectively. The whiskers extend to the most extreme data points that are not considered outliers, and the outliers are plotted individually using the '+' symbol. Fig. 6 shows that i) JDQT achieves higher QoS (6.8% and 17.9% in average, respectively) than GA and heuristic, and ii) the gap between the upper and lower bounds of "JDQT vs GA" is smaller than the gap between the upper and lower bounds of "JDQT vs heuristic", which implies that the quality of the solution achieved by GA is more "stable" than the heuristic. This is because i) the aim of heuristic is to find feasible solution, and the searching process stops when an arbitrary feasible solution is found, and ii) the quality of the solution of GA can be improved through the iterations.

Gain

QoS gain

JDQT vs Heuristic JDQT vs GA Fig. 6. QoS gain of JDQT, GA and heuristic.

7 compares the computing time of JDQT, B&B, B&C, GA and heuristic. Note that energy efficiency factor η does not change the problem size (i.e., the number of variables and constraints), and, thus, its influence on computing time is limited. We set η = 0.8 and tune M and N parameters. Fig. 7 shows the statistical property of computing time gain between i) JDQT and B&B, ii) JDQT and B&C, iii) JDQT and GA, and iv) JDQT and heuristic for all tuned M and N parameters. Denote T J (M, N, η), T B (M, N, η), T C (M, N, η), T G (M, N, η) and T H (M, N, η) as the computing time of JDQT, B&B, B&C, GA and heuristic under given , N and η parameters, respectively. The box plot of "B&B vs JDQT" with η = 0.8 shows the statistical property of data set { T B (M,N,0.8)-T J (M,N,0.8) T B (M,N,0.8) } for all tuned M and N parameters. The simulation results show that when M and N increase, the computing time of JDQT, B&B, B&C and GA grows, since more variables and constraints are involved in the problem (i.e. the problem size is enlarged). For the heuristic, since it is based on a relaxed B&B method, the number of nodes still increases with problem size. Thus, the change of M and N parameters also influences the computing time of heuristic. However, the computing time increase of heuristic is much smaller than other algorithms.

As shown in Fig. 7, JDQT takes a shorter computing time than B&B (27.8% in average), B&C (19.6% in average) and GA (73.2% in average). The heuristic has a shorter computing time (81.2% in average) than JDQT. However, the quality of the solution is hard to control, as shown in Fig. 6. Although GA can solve mixed non-linear programming problem such as MINLP, the optimality of the solution is hard to guarantee. Moreover, compared with JDQT, the architecture of GA is more complex since at each iteration GA needs to generate new populations through several procedures, such as selection, reproduction, mutation and crossover. Therefore, the problem transformation from MINLP-based PP [START_REF] Leung | Simultaneous task allocation, scheduling and voltage assignment for multiple-processors-core systems using mixed integer nonlinear programming[END_REF] to MILP-based PP1 [START_REF] Yu | Dynamic scheduling of imprecise-computation tasks on real-time embedded multiprocessors[END_REF] is necessary, since it can simplify the structure of the problem, and, thus, the optimal solution is much easier to find. Although B&B can optimally solve MILP problems for large problem sizes, B&B explores a large number of nodes to find the optimal solution. B&C, which combines the benefits of B&B and Gomory cutting scheme, can better explore optimality, efficiency and stability trade-off. Usually, B&C has a faster convergence speed than B&B. For an optimization problem, its computational complexity usually increases significantly with the number of variables and constraints. Hence, solving the smaller problems with less variables and constraints (i.e., MP and SP) iteratively is more efficient than solving a single large problem. This result is in line with the comparison of [START_REF] Randazzo | A comparison of optimal methods for local access uncapacitated network design[END_REF] where the decomposition-based method is faster than B&B and B&C for solving lager problem instances.

B. Comparison between JDQT and AJDQT

In this section, we first explore the convergence of the proposed two-layer subgradient-based algorithm used in AJDQT to solve the MP1 [START_REF] Randazzo | A comparison of optimal methods for local access uncapacitated network design[END_REF] and the SP [START_REF] Mcdaniel | A modified Benders' partitioning algorithm for mixed integer programming[END_REF] with respect to the outer-layer iterations, which are the most dominant ones as they determining the convergence criteria, as shown in the proof of Theorem 3.3. Fig. 8 shows the convergence of the objective function to the optimal solution with respect to the number of the outer-layer iterations for the MP1, with ζ = 0.01, σ = 0.1, η = 0.8, M = 4 and N = 20. The results are similar then for the SP. From the experimental results, the optimal solution is found usually within 15 outer-layer iterations. The simulation results show that the solutions of PP1 (20) achieved by JDQT and AJDQT are the same, for stopping criteria = 0.01 and all tuned M , N and η parameters. Therefore, AJDQT is also able to find an optimal solution. The computing time of JDQT and AJDQT is compared in Fig. 9. Since energy efficiency factor η does not change problem size, we set η = 0.8 and tune M and N parameters. From it, we can see that i) when increasing M and N , the computing time of JDQT and AJDQT grows, and ii) under the same M and N parameters, AJDQT has a shorter computing time than JDQT (17.6% in average). This is because at each iteration the MP of AJDQT is relaxed to an LP, but the MP of JDQT is still an ILP. LP is much easier to solve than ILP, especially when the problem size is large. We also observe that the computational complexity of AJDQT is largely influenced by the algorithm used to find the feasible solution to the MP (i.e., FP algorithm in our case). When FP cannot find a feasible solution x(m) for the first time, we need to repeat FP again until an arbitrary feasible solution is found. The convergence iterations of JDQT and AJDQT are compared in Fig. 10, where the convergence iteration is defined as the number of iterations to achieve |Φ u (m) -Φ l (m)| ≤ . We set = 0.01, η = 0.8 and tune M and N parameters. From Fig. 10, we can see that i) the convergence iterations of JDQT and AJDQT increase with M and N parameters. Since more variables and constraints are added into the problem, the feasible region of the problem becomes more complex, and, thus, a higher number of iterations is required to search the optimal solution; ii) under the same M and N parameters, the difference of convergence iterations between JDQT and AJDQT is small. Usually, the difference is within several iterations, and this difference comes from twofold: i) the initial solution x(0) of the MP is generated randomly (no matter for JDQT or AJDQT), as long as it satisfies the constraints (2) and (3) (the value of initial solution x(0) only influences convergence iteration but not the convergence of the algorithm), and ii) the feasible solution of the MP (i.e., x(m)), rather than the optimal solution of the MP, is inserted into the iteration between the MP and the SP of AJDQT, and, thus, the lower bound sequence of AJDQT is not strictly increasing, compared with the lower bound sequence of JDQT. Note that i) the upper bound sequence of AJDQT is still decreasing (as the upper bound update processes of JDQT and AJDQT are the same), and ii) the feasibility or infeasibility constraints of AJDQT exclude the non-optimal and the infeasible solutions rather than the optimal solution. The optimality of the solution achieved by AJDQT is guaranteed (see Theorem 3.2). The characteristics of the lower and the upper bounds of JDQT and AJDQT imply that the convergence iteration of AJDQT may be larger than JDQT, but the computing time of AJDQT at each iteration is smaller than JDQT, since AJDQT has a simpler structure.

In Fig. 11, we explore the behavior (i.e., computing time, convergence iteration and QoS) achieved by JDQT and AJDQT with stopping criteria varying, where we set M = 4, N = 20 and η = 0.8. To better evaluate the influence of exerts on algorithm performance, the gap between the lower and the upper bounds at the m th iteration is calculated by Φu(m) Φ l (m) , and is tuned from 1 to 2.5 with a step of 0.5. From Fig. 11, we can see that the computing time, convergence iteration and QoS decrease when increases. Note that except = 1, the solutions found by JDQT and AJDQT are non-optimal. In the non-optimal cases, the QoS achieved by JDQT is not always larger than AJDQT under the same , but it is always within the upper and lower bounds. If we just want to find a feasible solution, we can run JDQT (AJDQT) and stop the iteration when the fist time that the DSP has a bounded solution (assume that at the m th iteration). This means the optimal task scheduling and adjustment decisions y(m) are found under the given task-to-processor allocation and frequencyto-task assignment decisions x(m). Since x(m) is not the optimal solution, (x(m), y(m)) is a feasible solution of the PP1 [START_REF] Yu | Dynamic scheduling of imprecise-computation tasks on real-time embedded multiprocessors[END_REF]. Based on the lower bound Φ l (m) and the upper bound Φ u (m) under given solution (x(m), y(m)), we can say that this solution is |Φ u (m) -Φ l (m)|-optimal. Similarly, if an is given in advance, we can find the corresponding solution by iteratively solving the MP and SP of JDQT (AJDQT) until i) the gap between the upper and the lower bounds of JDQT (AJDQT) is smaller than , and ii) the DSP is feasible under the temporary solution given by the MP. C. QoS-Aware vs Energy-Aware Task Mapping Fig. 12 compares the QoS gain and the energy consumption gain of QoS-OPT with NRG-OPT for all tuned M , N and η parameters. Denote Q E (M, N, η), E J (M, N, η) and E E (M, N, η) as the QoS achieved by NRG-OPT, and the consumed energy of QoS-OPT and NRG-OPT under given M , N and η parameters, respectively. The box plot of "QoS-OPT vs NRG-OPT" with title "QoS gain" ("Energy consumption gain") shows the statistical property of data set { Q J (M,N,η)-Q E (M,N,η) Q J (M,N,η) } ({ E J (M,N,η)-E E (M,N,η) E J (M,N,η) }) for all tuned M , N and η parameters. From Fig. 12, we can see that when using NRG-OPT to perform IC-task mapping, the QoS is always equal to 0, which is obviously lower than the QoS achieved by QoS-OPT. This is normal since, if the mandatory subtask of a task is fixed and given in advance, the smaller the optional subtask, the lower the energy consumed to execute this task. On the other hand, Fig. 12 also shows that QoS-OPT consumes more energy than NRG-OPT (60.3% in average), since QoS-OPT maximizes QoS and therefore executes more optional subtasks than NRG-OPT. However, the consumed energy of QoS-OPT is always no more than the supplied energy E s , as the energy supply constraint (9) must be satisfied. Hence, using QoS-OPT to perform IC-task mapping can provide a better balance between QoS-enhancing and energy-utilizing. In fact, when the system is in the low energy state, QoS-OPT is equal to NRG-OPT since only mandatory subtasks can be used to perform task mapping. V. CONCLUSION In this paper, we address the problem of IC-tasks mapping on DVFS-enabled homogeneous multicore platforms, with the goal of maximizing system QoS without violating the realtime and energy constraints. We first develop an MINLP model to describe this joint-design problem. And then, we propose an MILP description of this model without performance degradation. By doing so, we avoid high computational complexity and we use a simpler model to find an optimal solution. To optimally solve the MILP problem, we propose a JDQT algorithm. It reduces the computational complexity by iterating two smaller, but highly correlated, subproblems: an MP problem for task-to-processor allocation and frequency-totask assignment, and a SP problem for task scheduling and task adjustment. We prove that the proposed JDQT algorithm converges to the optimal solution through finite number of iterations. To further reduce the computational complexity of JDQT algorithm, we propose an AJDQT algorithm. We prove that by relaxing the MP problem of JDQT algorithm to an LP problem, the computing time can be reduced but the optimality of solution is still guaranteed. The results show that the desired system performance can be achieved by the proposed JDQT and AJDQT algorithms. Moreover, we have shown that the stopping criteria of JDQT and AJDQT algorithms can be used as a control parameter to trade-off QoS and algorithm computing time.

Fig. 1 .

 1 Fig. 1. Task graph of illustration example.

6 M 1 o 1 Hyper-period HFig. 2 .

 612 Fig. 2. Task execution sequence example corresponding to task sequence S defined in Fig. 1.

Fig. 3 .

 3 Fig. 3. The structure of JDQT algorithm.

Definition 3 . 1 :

 31 ( -optimal solution) Denote (x(m), y(m)) as an arbitrary solution of the PP1 (20), and Φ(m) as the corresponding objective function value. If |Φ(m) -Φ * | ≤ , we say (x(m), y(m)) is an -optimal solution.

b 1 and b 2

 2 are the u-dimensional and v-dimensional vectors, respectively. Matrices A, C and D represent the coefficients in the constraints with appropriate dimensions. Therefore, the SP and the DSP associated with the PP1 (28) are expressed as SP : min y 0 Φ(x(m), y) = f y (29) s.t. Cx(m) + Dy b 2 .

  a) If the DSP is infeasible: the SP (29) has an unbounded solution. Hence, the PP1 (28) has no feasible solution. b) If the DSP has a bounded solution ω(m): the SP (29) is feasible due to the strong duality, and A ← {m} ∪ A. Denote ( Φ(m), x(m)) and y(m) as the solutions of the MP and the SP at the m th iteration, respectively. Since i) x(m) is a feasible solution (not optimal) of the PP1 (28), and ii) f y(m) = (Cx(m) -b 2 ) ω(m) due to the strong duality, the upper bound of Φ * at the m th iteration is updated by Φ u (m) = min{Φ u (m -1), (Cx(m) -b 2 ) ω(m)}. Since Φ(m) and (Cx(m) -b 2 ) ω(m) are the lower bound and the upper bound of Φ * at the m th iteration, respectively, we have Φ(m) < (Cx(m) -b 2 ) ω(m). To avoid selecting the non-optimal solution x(m) again at the next iteration, a new feasibility constraint

Fig. 4 .

 4 Fig. 4. Structure of the Accelerated JDQT (AJDQT) algorithm.

Fig. 5 .

 5 Fig. 5. QoS of JDQT with M , N and η varying.

Fig. 7 .

 7 Fig. 7. Computing time gain of JDQT, B&B, B&C, GA and heuristic.

Fig. 8 .

 8 Fig. 8. Convergence of two-layer subgradient-based algorithm.

Fig. 9 .

 9 Fig. 9. Computing time of JDQT and AJDQT with M and N varying.

Fig. 10 .

 10 Fig. 10. Convergence iterations of JDQT and AJDQT with M and N varying.

Fig. 11 .

 11 Fig. 11. Quality of solution achieved by JDQT and AJDQT with varying.

Fig. 12 .

 12 Fig. 12. QoS and energy consumption gains of QoS-OPT and NRG-OPT.

TABLE I

 I

	.	DYNAMIC POWER CONSUMPTION AND STATIC POWER
		CONSUMPTION FOR 70 NM PROCESSOR
	v l (V )		0.65	0.7	0.75	0.8	0.85
	f l (GHz)	1.01	1.26	1.53	1.81	2.10
	P d l (mW ) P s l (mW )	184.9 266.7 370.4 498.9 655.5 246 290.1 340.3 397.6 462.7

ACKNOWLEDGMENT This research is funded by INRIA post-doctoral research fellowship program, and is partially funded by ANR ARTE-FACT (AppRoximaTivE Flexible Circuits and Computing for IoT) project (Grant No. ANR-15-CE25-0015), and is partly sponsored by the National Natural Science foundation of China (Grant No. 61403340).