Alberto Bosio

Daniel Menard

Olivier Sentieys

A Comprehensive Analysis of Approximate Computing Techniques: From Component-to Application-Level

A new design paradigm, Approximate Computing (AxC), has been established to investigate how computing systems can be more energy efficient, faster, and less complex. Intuitively, instead of performing exact computation and, consequently, requiring a high amount of resources, AxC aims to selectively violate the specifications, trading accuracy off for efficiency. It has been demonstrated in the literature the effectiveness of imprecise computation for both software and hardware components implementing inexact algorithms, showing an inherent resiliency to errors [START_REF] Sentieys | A survey of techniques for approximate computing[END_REF], [START_REF] Chippa | Analysis and characterization of inherent application resilience for approximate computing[END_REF].

This tutorial introduces basic and advanced topics on AxC. We intend to follow a bottom-up approach: from component-up to application-level. More in detail, we will first present the main concept and techniques (e.g., functional approximation, voltage over-scaling). We then move to present some compile-time results in terms of energy-efficiency, area, performance versus accuracy of computations when using customized arithmetic (fixed-point, floating-point) and also try to derive some conclusions by comparing the different paradigms [START_REF] Barrois | The Hidden Cost of Functional Approximation Against Careful Data Sizing -A Case Study[END_REF]. The algorithmic-level approximation methods are then presented. Energy consumption can be reduced by approximating or skipping part of the computation. The concept of incremental refinement, early termination and fast decision will be detailed.

The last part of the tutorial focuses on existing methodology for applying AxC techniques at application-level. Finally, we present as a case study IIDEA [BAR], an automatic framework that compounds (i) a source-tosource manipulation tool and (ii) an evolutionary search engine, in order to find the best functional approximation version of the given C/C++ code.

Intended Audience

Approximate Computing (AxC) is a promising technique for reducing the cost (in terms of are and power consumption) of a computing system. However, AxC is still in its infancy since there is a lack of methodologies and automated tools for the entire design and manufacturing flow. We strongly believe that professionals already working on that will be very interested by the latest advances and experiences presented during the special session. Moreover, the tutorial could be attractive for all the people who want to extend their horizon and learn best practices across the levels and technologies in the areas of AxC.

Syllabus

Tutorial will cover:

1. Introduction 2. AxC techniques: functional approximation, over-scaling approximation 3. Data precision, number representation and approximate arithmetic 4. Algorithmic-level approximation 5. Application-level: Design Space Exploration

We would like to propose a half-day tutorial as lecture style for the first 4 points of the Syllabus. The last part (5) will consist of lab exercises. Attendees are supposed to have their own laptop and basic knowledge of UNIX like environment (bash). No particular SW requirements are demanded since a docker image will be provided.

Speakers:

• Alberto BOSIO -LIRMM (France)

• Daniel MENARD -INSA Rennes (France) He has more than 20 years of expertise in the fields of system-on-chip architectures, reconfigurable systems and their associated CAD tools, finite arithmetic effects, numerical accuracy analysis and low-power sensor networks. He authored or coauthored more than 150 journal publications or peer-reviewed conference papers and hold 6 patents. In particular, his research on methods for analytical analysis of errors in reduced-precision arithmetic and word-length optimization since 2000 with more than 50 publications, can be considered as a pioneering work in the field of approximate computing. Web: http://people.rennes.inria.fr/Olivier.Sentieys/

  Alberto Bosio received the PhD in Computer Engineering from the Politecnico di Torino, Italy in 2006. From 2007 he is an Associate Professor at LIRMM -University of Montpellier in France. His research interests include Approximate Computing, In-Memory Computing, Test and Diagnosis of Digital circuits and systems and Reliability. He co-authored 1 book, 3 patents 35 journals, and over 120 conference papers. He will be the chair of the ETTTC from January 2018. He is a member of the IEEE. Web: http://www.lirmm.fr/~bosio/home/ Daniel Menard received the Ph.D. and HDR degrees in Signal Processing and Telecommunications from the University of Rennes, respectively in 2002 and 2011. From 2003 to 2012 he was Associate Professor at University of Rennes in France. He is currently Full Professor at INSA Rennes. His research activities focus on the energy efficient implementation of signal and image processing applications in embedded systems. His research topics include approximate computing, fixed-point arithmetic, energy optimization in MPSoC, low power HEVC video encoding and decoding and embedded stereo-vision. He has published 25 papers in international journals and 63 papers in international conferences. He is member of the DISPS Technical Committee of the IEEE Signal Processing Society.

	• Olivier SENTIEYS -INRIA (France)
	Speaker biographies:

Web: http://dmenard.perso.insa-rennes.fr Olivier Sentieys is a Professor at the University of Rennes and holds an Inria Research Chair on Energy-Efficient Computing Systems.


Alberto Bosio

A Comprehensive Analysis of Approximate Computing Techniques: From Component-to Application-Level Organizer(s)

Today, the concept of approximation is becoming more and more a "hot topic". The relevance of this tutorial proposal is, therefore, very high, as it targets the design paradigm that has the potential to be the viable solution for dealing with the three main issues that are energy reduction, increase of performance and mitigating the intrinsic unreliability of the latest technology nodes.

In the last 5 years, numerous papers on approximate computing have been presented at DAC and DATE conferences. Several surveys on approximate computing have been published recently in different journals. This is the right moment to propose this tutorial which describes and classifies the different existing techniques and CAD frameworks.

Intended audience

This tutorial is primarily targeted at researchers and engineers working in the domain of Wireless Communications, Multimedia and in general, any Signal-Processing domain. System-level design engineers working on embedded software and hardware engineering aspects shall discover a new dimension, to improve performance and energy efficiency of their designs.

Objectives

The main objectives can be summarized as follows:

• Introduces the main concepts of Approximate Computing paradigm • Define the different Approximate Techniques accordingly to the target layer (i.e., HW, SW)

• Present existing automated tools for the design of Approximate Computing Systems

Abstract

A new design paradigm, Approximate Computing (AxC), has been established to investigate how computing systems can be more energy efficient, faster, and less complex. Intuitively, instead of performing exact computation and, consequently, requiring a high amount of resources, AxC aims to selectively relax the specifications, trading accuracy off for efficiency. It has been demonstrated in the literature the effectiveness of imprecise computation for both software and hardware components implementing inexact algorithms, showing an inherent resiliency to errors.

This tutorial introduces basic and advanced topics on AxC. We intend to follow a bottom-up approach: from component, up to application-level. More in detail, we will first present existing approximate computing techniques according to three levels: hardware, data and computation. At hardware level, functional approximation through inexact operators and voltage over-scaling will be detailed. At data level, approximation can be carried-out by using efficient arithmetic, precision scaling, less data or less-up-to-date data. We will present some compile-time results in terms of energy-efficiency, area, performance versus accuracy of computations when using customized arithmetic (fixed-point, floating-point) and also, we will try to derive some conclusions by comparing the different paradigms. At computation level, algorithmic transformations are used to reduce complexity by skipping or approximating parts of the processing. The concepts of loop perforation, early termination, memoïzation, and computation approximation will be detailed.

The last part of the tutorial is dedicated to methods and tools to exploit efficiently approximate computing. First of all, the different approaches to analyze approximation effects on application quality will be described. Then the complex problem of word-length optimization for fixed-point and floating-point is considered. Finally, the different frameworks for design space exploration will be detailed. He has more than 20 years of expertise in the fields of systemon-chip architectures, reconfigurable systems and their associated CAD tools, finite arithmetic effects, numerical accuracy analysis and low-power sensor networks. He authored or coauthored more than 150 journal publications or peer-reviewed conference papers and hold 6 patents. In particular, his research on methods for analytical analysis of errors in reduced-precision arithmetic and word-length optimization since 2000 with more than 50 publications, can be considered as a pioneering work in the field of approximate computing. Web: http://people.rennes.inria.fr/Olivier.Sentieys/

Necessary background

Knowledge of

  Alberto Bosio received the PhD in Computer Engineering from the Politecnico di Torino, Italy in 2006. From 2007 to 2018 was an Associate Professor at LIRMM -University of Montpellier in France. He is now a Full Professor at the INL -Ecole Centrale de Lyon (France). His research interests include Approximate Computing, In-Memory Computing, Test and Diagnosis of Digital circuits and systems and Reliability. He co-authored 1 book, 3 patents 35 journals, and over 120 conference papers. He will be the chair of the ETTTC from January 2018. He is a member of the IEEE. Web: http://www.lirmm.fr/~bosio/home/ Daniel Menard received the Ph.D. and HDR degrees in Signal Processing and Telecommunications from the University of Rennes, respectively in 2002 and 2011. From 2003 to 2012 he was Associate Professor at University of Rennes in France. He is currently Full Professor at INSA Rennes. His research activities focus on the energy efficient implementation of signal and image processing applications in embedded systems. His research topics include approximate computing, accuracy evaluation, fixed-point arithmetic, energy optimization in MPSoC, low power HEVC video encoding and decoding and embedded stereo-vision. He has published more than 100 papers in international journals and in international conferences. He is member of the DISPS Technical Committee of the IEEE Signal Processing Society. Web: http://dmenard.perso.insa-rennes.fr Olivier Sentieys is a Professor at the University of Rennes and holds an Inria Research Chair on Energy-Efficient Computing Systems.

			2.1.4.	Less up-to-date data
		2.2.	Hardware level approximation (30 min)
			2.2.1.	Exact integer and floating-point operators
			2.2.2.	Inexact operators
			2.2.3.	Voltage over-scaling / Overclocking
			2.2.4.	Approximate memories
			2.2.5.	Comparison of fixed-point vs. inexact operators vs. custom floating-point
		2.3.	Computation level approximation (30 min)
			2.3.1.	Computation skip (Fine grained, coarse grained)
			2.3.2.	Computation approximation (Algorithm selection, Memoization, CNN)
	3.	Methods and tools for approximate computing
		3.1.	Analysis of approximation effect on application quality (30 min)
			3.1.1.	Error metrics
			3.1.2.	Approximate error modeling
			3.1.3.	Simulation-based approaches
			3.1.4.	Analytical approaches
		3.2.	Word-length optimization for fixed-point and floating-point (30mn)
			3.2.1.	Problem statement
			3.2.2.	State of the art algorithms
			3.2.3.	Case study of WLO
		3.3.	Design space exploration -(30 min)
			3.3.1.	Problem statement
			3.3.2.	State of the art (ACCEPT, REACT, PRECIMONIUS)
			3.3.3.	Issues
			3.3.4.	IIDEA Framework
			3.3.5.	Demo
			3.3.6.	Experimental Results
	Biographies
	Tutorial material
	Presentation slides will be available for download by the attendees
	Tutorial plan
	1.	General introduction Motivations (30 min)
		1.1.	Definition(s)
		1.2.	Overview and classification of techniques
		1.3.	Metrics
		1.4.	Approaches
	2.	Techniques for approximate computing
		2.1.	Data level approximation (30 min)
			2.1.1.	Data representation -arithmetic
			2.1.2.	Adaptive Precision scaling
			2.1.3.	Less data

Computer Architecture and Computer Arithmetic O. Sentieys, D. Menard, D. Novo, and K.Parashar. Fixed-point refinement, a guaranteed approach towards energy efficient computing Tutorial at IEEE/ACM Design Automation and Test in Europe (DATE'15), Grenoble, March 2015. D. Menard, D. Novo, K. Parashar, O. Sentieys,. Automatic fixed-point conversion : a gate way to high-level power optimization Tutorial at IEEE/ACM Design Automation and Test in Europe (DATE'14), Dresden, March 24 2014.


Member, IEEE Lei Mo

Angeliki Kritikakou

Member, IEEE Olivier Sentieys

Energy-Quality-Time Optimized Task Mapping on DVFS-enabled Multicores

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

Multicore architectures have great potential for energy-constrained embedded systems, such as energy-harvesting wireless sensor networks. Some embedded applications, especially the real-time ones, can be modeled as imprecise computation tasks. A task is divided into a mandatory subtask that provides a baseline Quality-of-Service (QoS) and an optional subtask that refines the result to increase the QoS. Combining dynamic voltage and frequency scaling, task allocation and task adjustment, we can maximize the system QoS under real-time and energy supply constraints. However, the nonlinear and combinatorial nature of this problem makes it difficult to solve. This work first formulates a mixed-integer non-linear programming problem to concurrently carry out task-to-processor allocation, frequencyto-task assignment and optional task adjustment. We provide a mixed-integer linear programming form of this formulation without performance degradation and we propose a novel decomposition algorithm to provide an optimal solution with reduced computation time compared to state-of-the-art optimal approaches (22.6% in average). We also propose a heuristic version that has negligible computation time.

I. INTRODUCTION

The increasing performance requirements of applications have pushed the embedded systems towards multicore architectures. Within thirty years, the code size of automotive, space and avionics applications has significantly increased [START_REF] Girbal | On the convergence of mainstream and mission-critical markets[END_REF]. Multicore architectures provide significant Space, Weight and Power savings (SWaP) while offering massive computing capabilities compared with single core processors. They are also capable of integrating diverse applications on the same platform [START_REF] Lemonnier | Towards future adaptive multiprocessor systems-on-chip: an innovative approach for flexible architectures[END_REF], [START_REF] Chen | Narrowband internet of things: Implementations and applications[END_REF].

In some application domains, e.g., audio/video streaming, radar tracking, and control system design, less accurate results computed before the deadline are preferable than accurate, but too late, results [START_REF] Aydin | Optimal reward-based scheduling for periodic real-time tasks[END_REF]. This statement holds because a real-time application has to provide a result before a given deadline. When not enough time is available, approximate results are acceptable as long as the baseline Quality-of-Service (QoS) is satisfied and the results are provided in time [START_REF] Chishiro | Practical imprecise computation model: theory and practice[END_REF]. For instance, in audio/video streaming, frames with a lower quality are better than missing frames. In radar tracking, an estimation of target's location in time is better than an accurate location arriving too late. In control loops, an approximate result produced by a control law is more preferable as long as the controlled system, e.g., cruise control system, remains stable. In these domains, the applications can be modeled as 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.

This article was presented in the International Conference on Hardware/Software Codesign and System Synthesis 2018 and appears as part of the ESWEEK-TCAD special issue.

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. All the mandatory subtasks must be completed before the deadline to have an acceptable result, while the optional subtasks can be left incomplete at the cost of reduced quality. The QoS of such systems increases with the longer execution of the optional subtasks.

At the same time, the energy consumption has become an important concern, especially for the systems with limited energy budget, such as battery powered devices and energyharvesting systems. Dynamic Voltage and Frequency Scaling (DVFS) is a technique that can manage both voltage and frequency, and, thus, control the energy and the time required to execute the tasks. By adequately allocating the tasks onto the processors and deciding the voltage/frequency of the processor for each task execution, the QoS can be further improved under the same energy supply and real-time constraints.

The majority of the task mapping approaches on multicores, e.g., [START_REF] Mahmood | Energyaware real-time task scheduling in multiprocessor systems using a hybrid genetic algorithm[END_REF]- [START_REF] Leung | Simultaneous task allocation, scheduling and voltage assignment for multiple-processors-core systems using mixed integer nonlinear programming[END_REF], has been conducted on how to allocate the tasks and/or decide the voltage/frequency in order to reduce the energy consumption of the system and guarantee the real-time constraints, i.e., energy-aware task mapping. However, most of these works focus only on the execution of the mandatory tasks. Some approaches, e.g., [START_REF] Aydin | Optimal reward-based scheduling for periodic real-time tasks[END_REF], [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], aim to maximize QoS by exploring the execution of the optional subtasks, with energy supply and real-time constraints, i.e., QoS-aware task mapping. However, the aforementioned approaches focus on different contexts compared to the problem considered in this paper, as summarized in Table I. Besides 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] Micheletto | Using bioinspired metaheuristics to solve reward-based energy-aware mandatory/optional realtime tasks scheduling[END_REF], [START_REF] Isabel | Energy-aware scheduling mandatory/optional tasks in multicore real-time systems[END_REF]. In addition, the task mapping problems on multicore platforms usually have an N P-hard complexity [START_REF] Fisher | The multiprocessor real-time scheduling of general task systems[END_REF]. Therefore, most of these QoS-aware task mapping approaches focus on heuristics to find feasible solutions [START_REF] Yu | Dynamic scheduling of imprecisecomputation tasks in maximizing QoS under energy constraints for embedded systems[END_REF]- [START_REF] Wei | Cost-constrained QoS optimization for approximate computation real-time tasks in heterogeneous MPSoCs[END_REF], [START_REF] Micheletto | Using bioinspired metaheuristics to solve reward-based energy-aware mandatory/optional realtime tasks scheduling[END_REF], [START_REF] Isabel | Energy-aware scheduling mandatory/optional tasks in multicore real-time systems[END_REF].

Complementary to the state-of-the-art, our work jointly optimizes task-to-processor allocation, frequency-to-task assignment and optional subtask adjustment, under energy supply and real-time constraints, with an objective of maximizing the QoS. Two algorithmic solutions are proposed: 1) an optimal approach, named Optimal Joint DVFS Task Mapping (OJTM), with lower computational complexity than the state-of-the-art optimal approaches, and 2) a polynomial-time complexity algorithm, named Heuristic Joint DVFS Task Mapping (HJTM), with better quality results compared with the state-of-theart heuristics. Heuristics are of great practical significance, since they are able to find feasible solutions in a short time. However, it is also important to find the optimal solution. Only by doing so, we can find out how far the obtained feasible solution is from the optimal one, and how to improve the heuristics based on the optimal solution. A. Related Work 1) Energy-aware Task Mapping: Existing works that focus on the pure energy-aware task mapping problem aim at minimizing the energy consumption under resource and application constraints, e.g., [START_REF] Mahmood | Energyaware real-time task scheduling in multiprocessor systems using a hybrid genetic algorithm[END_REF]- [START_REF] Leung | Simultaneous task allocation, scheduling and voltage assignment for multiple-processors-core systems using mixed integer nonlinear programming[END_REF]. DVFS is widely used in energy-aware task mapping. When voltage level is discrete, the problems are usually formulated as Integer Programming (IP), e.g., [START_REF] Mahmood | Energyaware real-time task scheduling in multiprocessor systems using a hybrid genetic algorithm[END_REF]- [START_REF] Li | Minimizing energy consumption for frame-based tasks on heterogeneous multiprocessor platforms[END_REF]. To efficiently solve the IP problems, a hybrid Genetic Algorithm (GA) is proposed in [START_REF] Mahmood | Energyaware real-time task scheduling in multiprocessor systems using a hybrid genetic algorithm[END_REF], a polynomialtime complexity two-step heuristic is designed in [START_REF] Xu | Energy minimizing for parallel realtime tasks based on level-packing[END_REF], and the IP problem is relaxed to a Linear Programming (LP) in [START_REF] Li | Minimizing energy consumption for frame-based tasks on heterogeneous multiprocessor platforms[END_REF]. Combining DVFS and Dynamic Power Management (DPM), a Mixed-Integer Linear Programming (MILP)-based task mapping problem is considered in [START_REF] Chen | Energy optimization for realtime multiprocessor system-on-chip with optimal DVFS and DPM combination[END_REF] and the problem is solved using the CPLEX optimization solver. When the voltage level is continuous, a convex problem is formulated in [START_REF] Kong | Energy-efficient scheduling of real-time tasks on cluster-based multicores[END_REF] and the problem can be solved by using polynomial-time methods. In [START_REF] Leung | Simultaneous task allocation, scheduling and voltage assignment for multiple-processors-core systems using mixed integer nonlinear programming[END_REF], Mixed-Integer Non-Linear Programming (MINLP) is used to formulate the task mapping problem. The problem is relaxed to an MILP by linear approximation and solved by Branch and Bound (B&B) method [START_REF] Boyd | Branch and bound methods[END_REF]. However, the tasks in aforementioned approaches are not modifiable, and, thus, no exploration of the QoS improvement through the optional subtasks adjustment is considered.

2) QoS-aware Task Mapping: Other works consider the QoS-aware task mapping problem using the IC task model and having a goal to maximize the QoS under a set of realtime and/or energy supply constraints, e.g., [START_REF] Aydin | Optimal reward-based scheduling for periodic real-time tasks[END_REF], [START_REF] Cortes | Quasi-static assignment of voltages and optional cycles in imprecise computation systems with energy considerations[END_REF]- [START_REF] Isabel | Energy-aware scheduling mandatory/optional tasks in multicore real-time systems[END_REF]. The target platforms considered in [START_REF] Cortes | Quasi-static assignment of voltages and optional cycles in imprecise computation systems with energy considerations[END_REF], [START_REF] Yu | Dynamic scheduling of imprecisecomputation tasks in maximizing QoS under energy constraints for embedded systems[END_REF] are single core platforms. Therefore, the task allocation problem is not taken into account. Although the works in [START_REF] Aydin | Optimal reward-based scheduling for periodic real-time tasks[END_REF], [START_REF] Yu | Dynamic scheduling of imprecise computation tasks on real-time embedded multiprocessors[END_REF]- [START_REF] Isabel | Energy-aware scheduling mandatory/optional tasks in multicore real-time systems[END_REF] target at multicore platform, some assumptions are made during the problem formulation. More precisely, the task-to-processor allocation is fixed and given in advance for all the tasks in [START_REF] Yu | Dynamic scheduling of imprecise computation tasks on real-time embedded multiprocessors[END_REF], while in [START_REF] Aydin | Optimal reward-based scheduling for periodic real-time tasks[END_REF], [START_REF] Zhou | Energy-adaptive scheduling of imprecise computation tasks for QoS optimization in real-time MPSoC systems[END_REF]- [START_REF] Mo | Decomposed task mapping to maximize QoS in energy-constrained real-time multicores[END_REF] each processor has a predefined frequency, and in [START_REF] Micheletto | Using bioinspired metaheuristics to solve reward-based energy-aware mandatory/optional realtime tasks scheduling[END_REF], [START_REF] Isabel | Energy-aware scheduling mandatory/optional tasks in multicore real-time systems[END_REF] the energy supply constraints are not taken into account since the aim is to maximize the QoS as well as to minimize the energy consumption. When taking multiple system requirements into account, the complex coupling between the optimization variables makes the problem difficult to solve, especially when the coupling is non-linear and non-convex. The methods that used to solve the aforementioned problems can be classified into two main classes. The first class includes the methods based on heuristics, e.g., [START_REF] Yu | Dynamic scheduling of imprecisecomputation tasks in maximizing QoS under energy constraints for embedded systems[END_REF]- [START_REF] Wei | Cost-constrained QoS optimization for approximate computation real-time tasks in heterogeneous MPSoCs[END_REF], [START_REF] Micheletto | Using bioinspired metaheuristics to solve reward-based energy-aware mandatory/optional realtime tasks scheduling[END_REF], [START_REF] Isabel | Energy-aware scheduling mandatory/optional tasks in multicore real-time systems[END_REF]. The second class includes the methods that always produce an optimal solution, e.g., [START_REF] Aydin | Optimal reward-based scheduling for periodic real-time tasks[END_REF], [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].

B. Contributions

This paper solves the following problem: Given a DVFSenabled multicore platform and a set of IC tasks, we determine which processor should the task be executed on as well as the frequency of each task, such that the system QoS is maximized while guaranteeing the system constraints, i.e., energy supply and task deadline. Hence, we need to decide task-to-processor allocation, frequency-to-task assignment and task adjustment. Our main contributions are summarized as follows:

1) We propose an MINLP formulation of the QoS-aware mapping problem of IC tasks on DFVS multicore platforms under a set of energy supply and real-time constraints. The task-to-processor allocation, frequency-totask assignment, and task adjustment are optimized simultaneously. Solving these correlated subproblems separately may lead to non-optimal solutions. Then, applying the variable replacement method, the N Phard joint-design problem is safely transformed to an MILP. We prove that the proposed linearization does not cause performance degradation, compared with the existing linear approximation methods [START_REF] Leung | Simultaneous task allocation, scheduling and voltage assignment for multiple-processors-core systems using mixed integer nonlinear programming[END_REF]. 2) We design an OJTM solving approach based on Benders decomposition [START_REF] Benders | Partitioning procedures for solving mixed-variables programming problems[END_REF]. The MILP-based task mapping problem is divided into two subproblems with simpler structures, i.e., with less constraints and variables. The first subproblem is an Integer Linear Programming (ILP) and it is responsible for the taskto-processor allocation and the frequency-to-task assignment. The second subproblem is an LP and it is related to the task adjustment. The solution is found through iterations. During one iteration, the solution of the first subproblem is used as input to the second sub-problem. The solution of the second subproblem is incorporated to the first one by adding new constraints for the next iteration. We prove that by iterating these two subproblems, the OJTM is guaranteed to reach the global optimal solution. 3) We present a novel HJTM algorithm that reduces the complexity of OJTM by removing the iteration process.

As the HJTM is a reduced version of OJTM, it is easy to be applied to similar MILP problems, compared with the existing heuristics. When the problem formulation is changed, existing heuristics usually have to be redeveloped, such as [START_REF] Zhou | Energy-adaptive scheduling of imprecise computation tasks for QoS optimization in real-time MPSoC systems[END_REF], [START_REF] Isabel | Energy-aware scheduling mandatory/optional tasks in multicore real-time systems[END_REF]. 4) We evaluate the performance of the proposed approaches by a set of extended experiments, where the proposed approaches are compared both in QoS and in computation time with the state-of-the-art optimal, stochastic and heuristic approaches. The obtained results show an average 22.6% reduction in the computation time for the OJTM compared with state-of-theart optimal approaches. On the other hand, HJTM runs ∼100 times faster than OJTM with a cost of 26.3% QoS reduction. Moreover, compared with the state-of-the-art heuristics, HJTM achieves an average 96.7% QoS improvement.

C. Paper Organization

The remainder of this paper is organized as follows: Section II presents the system model and the problem formulation. Section III describes the OJTM algorithm to optimally map IC tasks to DVFS-enabled multicore platform and in Section IV we present the details of HJTM algorithm. Section V evaluates the performance of OJTM and HJTM algorithms through several simulations and Section VI concludes this study.

II. MINLP PROBLEM FORMULATION

A. Task model

The applications of our target domain are modeled as IC tasks [START_REF] Liu | Imprecise computations[END_REF].

Definition 2.1 (Imprecise computation task): A task τ i is defined as an imprecise computation task when it can be logically divided into a mandatory subtask and an optional subtask. The mandatory subtask executes M i cycles to generate the baseline QoS level. The optional subtask executes o i cycles to improve the QoS.

Consider a task set of N independent IC tasks {τ 1 , . . . , τ N }. Task τ i is described by a tuple {o i , M i , O i , D i }, where O i is the upper bound on the number of possible optional cycles, i.e., 0 ≤ o i ≤ O i . Therefore, the total length of task τ i , measured in execution cycles, is M i + o i . The exact number of mandatory cycles M i and maximum optional cycles O i of a task τ i depends on the actual execution of the task on the multicore system [START_REF] Aydin | Optimal reward-based scheduling for periodic real-time tasks[END_REF], [START_REF] Chishiro | Practical imprecise computation model: theory and practice[END_REF]. As we require to guarantee the deadline of the task, the 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]. For each task τ i , there is a relative deadline D i before which both the mandatory and the optional subtasks of τ i must be completed. The relative deadline is defined as the time interval between the start of a task and the time instance when the deadline occurs [START_REF] Huang | Self-suspension real-time tasks under fixed-relative-deadline fixed-priority scheduling[END_REF]. The scheduling horizon H is given by the global period of the tasks [START_REF] Zhou | Energy-adaptive scheduling of imprecise computation tasks for QoS optimization in real-time MPSoC systems[END_REF]. Hence, the relative deadline D i cannot be greater that the scheduling horizon H, i.e., D i ≤ H.

B. Energy model

We assume that the IC tasks run on a multicore platform that contains M homogeneous processors {θ 1 , . . . , θ M }. The processors can support DVFS and each processor

θ k has L differ- ent discrete voltage/frequency levels {(v 1 , f 1 ), . . . , (v L , f L )}.
We consider that the processor energy consumption is not only determined by the dynamic power, but also by the static power due to CMOS device feature scaling. The dynamic power by executing task τ i is related to processor clock frequency f l and supply voltage v d , expressed as

P d l = C ef f v 2 l f l ,
where C ef f is the average effective switching capacitance. For static power, 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 depend on the processor technology. 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]. Hence, the power of the processor under the voltage/frequency level (v l , f l ) is

P c l = P s l + P d l . ( 1
)
This model is widely adopted by the similarly published works [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 imprecise computation tasks on real-time embedded multiprocessors[END_REF], [START_REF] Zhou | Energy-adaptive scheduling of imprecise computation tasks for QoS optimization in real-time MPSoC systems[END_REF].

For readability reasons in the rest of the manuscript, we use the term "frequency" instead of "voltage/frequency". When the frequency is determined, the corresponding voltage is also given. Examples of processor frequency-voltage characteristics are provided in Table II of the experimental section. In this paper, we consider 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], i.e., the frequency of a processor stays constant for the entire execution of a task. Unlike the big.LITTLE platforms [START_REF] Chwa | Energy and feasibility optimal global scheduling framework on big.LITTLE platforms[END_REF] that support task migration, we consider that a task starts execution on a processor and ends its execution on the same processor [START_REF] Wei | Cost-constrained QoS optimization for approximate computation real-time tasks in heterogeneous MPSoCs[END_REF], [START_REF] Isabel | Energy-aware scheduling mandatory/optional tasks in multicore real-time systems[END_REF]. We assume that the system is energyconstrained in the sense that it has a fixed energy budget E s that cannot be replenished during the scheduling horizon H [START_REF] Zhou | Energy-adaptive scheduling of imprecise computation tasks for QoS optimization in real-time MPSoC systems[END_REF], [START_REF] Wei | Cost-constrained QoS optimization for approximate computation real-time tasks in heterogeneous MPSoCs[END_REF]. Taking the available energy E s into account, the system operation can be divided into three states: 1) Low: the supplied energy E s is insufficient to execute all the mandatory cycles {M 1 , . . . , M N }, 2) High: the supplied energy E s is sufficient to execute all the mandatory and optional cycles {M 1 +O 1 , . . . , M N +O N }, and 3) Medium: all the mandatory cycles are ensured to finish, while not all the optional cycles can complete their executions. In this paper, we focus on medium state.

C. Problem Formulation

The objective is to maximize the QoS subject to a set of real-time and energy constrains. In this context, we determine 1) on which processor should the task be executed (task-toprocessor allocation), 2) what frequency should be used for the task (frequency-to-task assignment), and 3) how many optional cycles should be executed (task adjustment). Therefore, we define the following variables:

1) Binary variables

q ik = 1 if task τ i runs on processor θ k , 0 otherwise. c il = 1 if task τ i executes with frequency f l , 0 otherwise. 2) Continuous variable o i optional cycles of task τ i .
For tractability reasons, o i is considered as continuous variable in the problem formulation. When the problem is solved, the result is rounded down. As the tasks execute typically hundreds of thousands of cycles, this impact is negligible [START_REF] Li | Minimizing energy consumption for frame-based tasks on heterogeneous multiprocessor platforms[END_REF]. Let N {1, . . . , N }, M {1, . . . , M } and L {1, . . . , L}. Since 1) each task can be assigned only one frequency level, and 2) each task is executed at only one processor, the binary variables c il and q ik must satisfy the following constraints:

L l=1 c il = 1, ∀i ∈ N , (2)
M k=1 q ik = 1, ∀i ∈ N . (3)
For the real-time constraints, since 1) the execution time of task M i + o i cannot exceed the relative deadline D i , and 2) the tasks assigned to processor θ k must be executed within the scheduling horizon H, we have

L l=1 c il w il + o i f l ≤ D i , ∀i ∈ N , (4)
N i=1 q ik L l=1 c il w il + o i f l ≤ H, ∀k ∈ M, (5)
where w il = Mi f l is the execution time of the mandatory subtask M i with frequency f l . D i is determined by the applications and

D i ≥ min ∀l∈L Mi f l .
Based on the energy model (1), the total energy consumed by M processors within the horizon 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 , (6)
where M H -

N i=1 L l=1 c il w il + oi f l
is the time of M processors in the idle state during the scheduling horizon H and P s 0 is the static power of idle state. It has been shown in [START_REF] Aydin | Optimal reward-based scheduling for periodic real-time tasks[END_REF], [START_REF] Yu | Dynamic scheduling of imprecise computation tasks on real-time embedded multiprocessors[END_REF], [START_REF] Wei | Cost-constrained QoS optimization for approximate computation real-time tasks in heterogeneous MPSoCs[END_REF], [START_REF] Yu | Quality-driven dynamic scheduling for real-time adaptive applications on multiprocessor systems[END_REF] that applications exist, e.g., Tier-2 coder in M-JPEG2000, where the QoS highly depends on its optional subtask and it can be represented as a linear function of the optional cycles. The linear function increases its value uniformly with the optional cycles. To quantify the relationship between QoS and optional cycles, each task τ i is associated with a linear function g i (o i ). In order to maximize QoS function N i=1 g i (o i ) (or to minimize its negative), based on all the aforementioned constraints, the Primal Problem (PP) is formulated as 3), ( 4), ( 5), [START_REF] Liu | Imprecise computations[END_REF],

PP : min c,q,o Φ = - N i=1 g i (o i ) s.t.    (2), (
c il , q ik ∈ {0, 1}, 0 ≤ o i ≤ O i , ∀i ∈ N , ∀l ∈ L, ∀k ∈ M.
Due to the products of optimization variables c il o i and q ik c il o i in the constraints (4), ( 5) and ( 6), the PP is an MINLP problem, which is difficult to directly solve because of the nonlinear items [START_REF] Leung | Simultaneous task allocation, scheduling and voltage assignment for multiple-processors-core systems using mixed integer nonlinear programming[END_REF].

Theorem 2.1: The MINLP-based QoS-aware IC-tasks mapping problem, i.e., the PP, is N P-hard.

Proof: Due to page limitations, the proof is excluded from the manuscript. However, the details can be found in [START_REF] Samuel | Non-convex mixed-integer nonlinear programming: a survey[END_REF].

III. OPTIMAL APPROACH

In this section, we present our optimal approach for solving the problem defined in Section II.

A. MILP formulation

We adopt the idea of variable replacement to efficiently solve the PP. In this way, the MINLP can be safely transformed to an MILP with a simpler structure, and, thus, easier to solve. To achieve this, we first introduce an intermediate (continuous) variable

t i = L l=1 c il w il + o i f l , ∀i ∈ N , (7)
which is the execution time of task τ i . Then, we linearize the nonlinear items c il o i and q ik t i according to Lemma 3.1. Lemma 3.1: Given constants s 1 > 0 and 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 . Similarly, if b = 1, we have -s 1 ≤ h = x ≤ s 2 . S 2 ⇒ S 1 holds.
Although the lower bound of

t i is min ∀l∈L Mi f l ≥ 0 (= 0 when M i = 0), we assume that 0 ≤ t i ≤ D i since the range 0, min ∀l∈L Mi f l
is excluded by [START_REF] Mahmood | Energyaware real-time task scheduling in multiprocessor systems using a hybrid genetic algorithm[END_REF]. Note that c il ∈ {0, 1},

q ik ∈ {0, 1}, 0 ≤ o i ≤ O i and 0 ≤ t i ≤ D i .
We introduce two intermediate (continuous) variables h il and d ik to replace the nonlinear items c il o i and q ik t i , respectively. Therefore, the constraints ( 4) and ( 6) are safely replaced by

L l=1 c il w il + h il f l ≤ D i , ∀i ∈ N , (8)
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 , (9) h il ≤ c il O i , ∀i ∈ N , ∀l ∈ L, (10)
h il ≤ o i , ∀i ∈ N , ∀l ∈ L, (11)
o i -h il -(1 -c il ) O i ≤ 0, ∀i ∈ N , ∀l ∈ L. ( 12
)
Based on the intermediate variables t i and h il , the constraint (5) is safely replaced by

t i = L l=1 c il w il + h il f l , ∀i ∈ N , (13)
N i=1 d ik ≤ H, ∀k ∈ M, (14)
d ik ≤ q ik D i , ∀i ∈ N , ∀k ∈ M, (15)
d ik ≤ t i , ∀i ∈ N , ∀k ∈ M, (16)
t i -d ik -(1 -q ik ) D i ≤ 0, ∀i ∈ N , ∀k ∈ M, (17)
where ( 10)-( 12) and ( 15)-( 17) are the additional constraints introduced by the linearization. Consequently, the PP is rewritten as the MILP problem:

PP1 : min c,q,o, t,h,d Φ = - N i=1 g i (o i ) s.t.         
(2), ( 3), ( 8)

-(17), c il , q ik ∈ {0, 1}, 0 ≤ o i , h il ≤ O i , min ∀l∈L Mi f l ≤ t i ≤ D i , 0 ≤ d ik ≤ D i , ∀i ∈ N , ∀l ∈ L, ∀k ∈ M.
Remark 3.1: Lemma 3.1 implies that the variable replacement does 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 PP1 and PP are the same.

B. Optimal Joint DVFS Task Mapping

We propose an optimal algorithm, i.e., OJTM, to solve PP1 based on its special characteristics, i.e., the binary and continuous variables are coupled with each other linearly.

The key idea of OJTM comes from Benders decomposition. Instead of considering all the variables and the constraints of PP1 simultaneously, OJTM decomposes the PP1 into a Master Problem (MP) and a Slave Problem (SP), which are solved iteratively through a feedback loop. By doing so, the computational complexity of the solution is significantly reduced [START_REF] Benders | Partitioning procedures for solving mixed-variables programming problems[END_REF], [START_REF] Mcdaniel | A modified Benders' partitioning algorithm for mixed integer programming[END_REF], even if the PP1 is non-convex. The structure of OJTM is shown in Fig. 1. The MP accounts for all the binary variables (task-to-processor allocation and frequency-to-task assignment) and the corresponding part of the objective function and the constraints of PP1. It also includes a set of constraints called Benders cuts. The SP includes all the continuous variables (task adjustment) and the associated constraints of PP1. The SP solution provides additional constraint, which is incorporated in the MP through the Benders cuts.

Task-to-processor allocation

Frequency-to-task assignment For presentation convenience, matrices and vectors are used to denote the constraints and variables. Hence, the PP1 is reformulated as

PP1 : min x,y f y s.t. Ax b 1 , Cx + Dy b 2 ,
where x is a binary vector, and y is a continuous vector. Vector f represents the objective function coefficients, and f represents the transposition of f . Matrices A, C and D represent the constraints' coefficients. b 1 and b 2 are the udimensional and v-dimensional vectors, respectively. Based on the structure of the PP1, at the m th iteration, the MP is formulated as

MP : Φ l (m) = min x, Φ Φ (18)
s.t.

     Ax b 1 , Φ ≥ λ(ς) (Cx -b 2 ), ∀ς ∈ A, 0 ≥ λ(ϑ) (Cx -b 2 ), ∀ϑ ∈ B,
where where x(m) is the MP solution at the m th iteration. In fact, the SP is "identical" to PP1: the formulations are the same, except that the binary variables x(m) in the SP are fixed. Denote Φ * as the optimal objective function value of the PP1. Note that the MP [START_REF] Mo | Decomposed task mapping to maximize QoS in energy-constrained real-time multicores[END_REF] only contains the frequency-to-task and task-to-processor information, i.e., x(m). Compared with the PP1, the task adjustment related constraints are relaxed. Solving the MP yields a lower bound of Φ * , i.e., Φ l (m). On the other hand, x(m) may be just a feasible solution (not optimal yet), and SP is a minimization problem. Solving the SP with x(m) yields an upper bound of Φ * , i.e., Φ u (m) (the proof is provided in Theorem 3.1). Therefore, we have Φ l (m) ≤ Φ * ≤ Φ u (m). At each iteration, introducing a new feasibility constraint [START_REF] Isabel | Energy-aware scheduling mandatory/optional tasks in multicore real-time systems[END_REF] or infeasibility constraint [START_REF] Boyd | Branch and bound methods[END_REF] into the MP, the gap between the upper and lower bounds, i.e., Φ u (m) -Φ l (m), gradually reduces (the proof is provided in Lemma 3.3), and the iterations stop when Φ u (m)-Φ l (m) ≤ ε.

Φ ≥ λ(ς) (Cx -b 2 ) (∀ς ∈ A) and 0 ≥ λ(ϑ) (Cx - b 2 ) (∀ϑ ∈ B)
Definition 3.1 (ε-optimal solution): A solution ( x, ỹ) of the PP1 is an ε-optimal solution, if it satisfies the constraint 0 ≤ f ỹ -Φ * ≤ ε.

Lemma 3.2: Based on the iteration termination criterion Φ u (m) -Φ l (m) ≤ ε, the solution (x(m), y(m)) obtained by OJTM is an ε-optimal solution.

Proof: Substituting the solution (x(m), y(m)) into the PP1, we have

Φ l (m) ≤ f y(m) = Φ u (m). Since Φ u (m) - Φ l (m) ≤ ε, we get 0 ≤ f y(m) -Φ * ≤ ε, which means (x(m), y(m)) is an ε-optimal solution.
If ε is a small positive value, the optimal value Φ * is found by OJTM (the proof is provided in Theorem 3.2). The iteration process is summarized as follows:

1) 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. Note that the initial solution x(0) can be given arbitrarily, as long as it satisfies the constraints (2) and (3).

2) Step 2 -Solving SP: Assume that the current iteration is m. Since the SP is a LP problem, 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]. Introducing the positive Lagrange multipliers λ [λ i ] (1 ≤ i ≤ v) to the SP, the associated dual problem (DSP) is

DSP : max λ 0 λ (Cx(m) -b 2 ) (19) s.t. f + D λ 0.
Since the DSP is a LP problem, the solution can be found quickly using standard 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].

3) Step 3 -Solving MP: Depends on the following cases: 1) The DSP is infeasible: The SP has an unbounded solution. Hence, the PP1 has no feasible solution.

2) The DSP has a bounded solution λ(m): The SP is feasible due to the strong duality, and A ← {m} ∪ A.

Assume that Φ(m) and y(m) are the solution of the MP and the SP at the m th iteration, respectively. Since i) x(m) is a feasible solution (not optimal) of PP1, and ii) f y(m) = λ(m) (Cx(m) -b 2 ) due to the strong duality, the upper bound of Φ * at the m th iteration is updated by

Φ u (m) = min{Φ u (m - 1), λ(m) (Cx(m) -b 2 )}. Note that i) Φ(m) < λ(m) (Cx(m) -b 2 )
, and ii) x(m) is not the optimal solution. In order to avoid selecting the non-optimal solution x(m) again, a new feasibility constraint

Φ ≥ λ(m) (Cx -b 2 ) (20)
is generated and added into the MP at the (m + 1) th iteration.

3) The DSP has an unbounded solution, i.e., λ(m) (Cx(m) -b 2 ) = +∞: Due to the strong duality, the SP has no feasible solution under given solution x(m), and B ← {m}∪B. For the SP, its feasibility is related to the constraints rather than the objective function. This problem may 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 ξ s.t. Cx(m) + Dy b 2 + ξ.
Since the FCP is a LP problem, the strong duality exists between the FCP and its dual problem. Introducing the positive Lagrange multipliers λ = λi (1 ≤ i ≤ v) to the FCP, the associated dual problem (DFCP) is

DFCP : max λ 0 λ (Cx(m) -b 2 ) (21)
s.t. 1 -λ 0.

The presented method used to solve DSP can be also applied here to solve FCP and DFCP, as both are LP problems. Assume that ξ(m) and λ(m) are the solutions of FCP and DFCP, respectively. If the SP exists infeasible constraints, the related relax variables are non-zero, while the others are zero, i.e., 1 ξ(m) > 0. Due to the strong duality, we have

1 ξ(m) = λ(m) (Cx(m) -b 2 ) > 0.
In order to avoid selecting the infeasible solution x(m) again, a new infeasibility constraint

0 ≥ λ(m) (Cx -b 2 ) (22)
is generated and added into the MP at the (m + 1) th iteration. Note that in [START_REF] Isabel | Energy-aware scheduling mandatory/optional tasks in multicore real-time systems[END_REF] and [START_REF] Boyd | Branch and bound methods[END_REF], all the parameters are constant except Φ and x. These are the variables of the MP at the (m+ 1) th iteration. With this new added feasibility/infeasibility constraint, the MP is solved again to obtain a new solution x(m + 1) at the next iteration.

Remark 3.2: Note that 1) the SP has the same objective function as the PP1, i.e., f y, and 2) the SP and the DSP are equivalent due to the strong duality, i.e., they have the same optimal objective function values. From [START_REF] Isabel | Energy-aware scheduling mandatory/optional tasks in multicore real-time systems[END_REF], we can see that the auxiliary variable Φ has the same physical meaning as the objective function of PP1.

Remark 3.3: We solve the DSP rather than solving the SP directly, because 1) the SP and its dual problem are equivalent due to the strong duality, and 2) we can construct feasibility and infeasibility constraints through the solution of the DSP. The reason why we select the solution of the DFCB rather than the solution of the FCB to construct infeasibility constraint is that λ (Cx -b 2 ) is a function with respect to x but not 1 ξ, i.e., 0 ≥ 1 ξ is an invalid constraint for the MP.

C. Convergence analysis

Equation [START_REF] Mo | Decomposed task mapping to maximize QoS in energy-constrained real-time multicores[END_REF] shows that 1) the MP is composed of the binary variables x and a continuous variable Φ, 2) the real constraints are Ax b 1 and 0 ≥ λ(ϑ) (Cx -b 2 ) (∀ϑ ∈ B), and 3) λ(ς) (Cx -b 2 ) (∀ς ∈ A) can be treated as objective functions. Therefore, the MP can be solved by only considering the binary variables x [START_REF] Mcdaniel | A modified Benders' partitioning algorithm for mixed integer programming[END_REF]. Comparing the MP with the following optimization problem, which has the same constraints, we have Φ(m) = max ∀i∈A Φr (i) .

MP i : Φr (i) = min x λ(i) (Cx -b 2 ) s.t. Ax b 1 , 0 ≥ λ(ϑ) (Cx -b 2 ), ∀ϑ ∈ B.
Theorem 3.1: Solving the MP and the SP at the m th iteration, we obtain a lower bound Φ l (m) and an upper bound Φ u (m) of the optimal value of the objective function Φ * , respectively.

Proof: First, we prove that Φ l (m) = Φ(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 have

Φ(m) = min x λ(ρ) (Cx -b 2 ) ≤ λ(ρ) (Cx * -b 2 ) (23a) ≤ max λ 0 λ (Cx * -b 2 ) = Φ * , (23b)
where min x λ(ρ) (Cx-b 2 ) is the objective function value of the MP ρ , and max λ 0 λ (Cx * -b 2 ) is the objective function value of the DSP. (23a) holds since x * is not the optimal solution of problem min x λ(ρ) (Cx -b 2 ). (23b) holds since solving the DSP with the optimal binary variables x * we find optimal value Φ * . [START_REF] Benders | Partitioning procedures for solving mixed-variables programming problems[END_REF] shows that Φ l (m) = Φ(m) is a lower bound of Φ * .

In the following, we prove that

Φ u (m) = min{Φ u (m - 1), λ(m) (Cx(m) -b 2 )} is an upper bound of Φ * . Note that we have min{Φ u (m -1), λ(m) (Cx(m) -b 2 )} = min 1≤i≤m {λ(i) (Cx(i) -b 2 )},
where x(i) and λ(i) are the solutions of the MP and the DSP at the i th iteration, respectively. Depending on the solution of the DSP, the objective function value of the DSP, i.e., λ(i) (Cx(i) -b 2 ), can be either finite or infinite. If the DSP has an unbounded solution, i.e., λ(i) (Cx(i) -b 2 ) = +∞, it is obvious that +∞ is an upper bound of Φ * . Thus, we consider the case when the DSP has a bounded solution λ(i). Due to the strong SP and DSP duality, we have

λ(i) (Cx(i) -b 2 ) = min y 0 f y|x(i) ≥ min y 0 f y|x * = Φ * , 1 ≤ i ≤ m,
where min y 0 f y|x(i) is the objective function value of the DSP with x(i). Thus, Φ u (m) = min 1≤i≤m {λ(i) (Cx(i)b 2 )} 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: Assume that ( Φ(m), x(m)) is the solution of the MP at the m th iteration. If x(m) are the non-optimal (infeasible) values of variables x, x(m) are excluded by adding new constraint

Φ ≥ λ(m) (Cx -b 2 ) (0 ≥ λ(m) (Cx -b 2 )
) into the MP at the (m + 1) th iteration. Note that the variables of the MP, i.e., x and Φ, are coupled with each other linearly. If x(m) are excluded, Φ(m) is excluded as well. Since 1) the aim of the MP is to minimize the objective function, 2) the non-optimal values of Φ * , i.e., { Φ(0), . . . , Φ(m)}, have been excluded by the constraints and3) with iteration number m increasing, more constrains are added into the MP (i.e., the feasible region of the MP will shrink), Φ l (m+1) = Φ(m+1) is larger than the previous lower bounds {Φ l (0), . . . , Φ l (m)}.

Φ ≥ λ(ς) (Cx-b 2 ) (∀ς ∈ A) and 0 ≥ λ(ϑ) (Cx -b 2 ) (∀ϑ ∈ B),
Assume that Φ u (m + 1) > Φ u (m). This contradicts the fact that

Φ u (m + 1) ≤ Φ u (m) and Φ u (m + 1) ≤ λ(m + 1) (Cx(m+1)-b 2 ) due to Φ u (m+1) = min{Φ u (m), λ(m+ 1) (Cx(m+1)-b 2 )}. Therefore, Φ u (m+1) is no larger than the previous upper bounds {Φ u (0), . . . , Φ u (m)}.
Theorem 3.2: At each iteration with a new feasibility constraint [START_REF] Isabel | Energy-aware scheduling mandatory/optional tasks in multicore real-time systems[END_REF] or infeasibility constraint [START_REF] Boyd | Branch and bound methods[END_REF] added into the MP, the solution obtained by OJTM converges to the global optimal value within a finite number of iterations.

Proof: At each iteration, there is a new constraint ((20) or ( 22)) added into the MP to exclude the non-optimal or the infeasible values of the binary variables x. Note that 1) the lower bound sequence {Φ l (0), . . . , Φ l (m)} is increasing, 2) the upper bound sequence {Φ u (0), . . . , Φ u (m)} is decreasing, and 3) the dimension of binary variables x is finite. According to the Theorem 2.4. in [START_REF] Geoffrion | Generalized Benders decomposition[END_REF], the solution converges to the global optimal value within a finite number of iterations.

IV. HEURISTIC APPROACH

The computational complexity of OJTM is dominated by the cost of solving the ILP-based MP at each iteration. Although the solution provided by OJTM is optimal, this method cannot be used to efficiently solve large problem sizes. To enhance the scalability of the proposed approach, we provide a novel heuristic algorithm, i.e., HJTM, to efficiently solve the PP. The reasons why we target PP rather than PP1 are that 1) these two problems are equivalent, and 2) the PP contains less variables and constraints making the heuristic less complex. The main idea of the HJTM is that the most important step of solving the PP is to find proper task-to-processor and frequency-to-task decisions (similar to basic idea of the OJTM). If the binary variables c and q are determined, the PP reduces to a LP problem. The structure of HJTM is shown in Fig. 2. HJTM has three steps. During the first step, we obtain feasible frequency-to-task assignment. Having determined the frequency-to-task decision, the problem reduces to finding feasible task allocation to the processors. In the final step, the optional cycles are defined to meet the real-time and the energy supply constraints.

Task-to-processor decision

Frequency-to-task decision FAP (ILP) TAP (ILP)

OTAP (LP)

Task adjustment decision

Feasibility pump

Relaxed problem (LP) Fig. 2. The structure of HJTM algorithm.

A. Frequency-to-task Assignment

Since the mandatory subtasks must be always executed, we initially consider only the frequency assignment of the mandatory subtasks and our aim is to minimize the energy consumption by assigning proper frequency to each task. From the constraint (6), we observe that if o i = 0 (∀i ∈ N ), the consumed energy of M processors reduces to

N i=1 L l=1 c il w il P s l + P d l -P s 0 + M HP s 0 . Since item M HP s 0 is fixed, the Frequency Assignment Problem (FAP) is formulated as FAP : min c N i=1 L l=1 c il w il P s l + P d l -P s 0 s.t.
(2),

L l=1 c il w il ≤ D i , ∀i ∈ N .

B. Task-to-processor Allocation

Solving the FAP, we obtain the execution time of task τ i 's mandatory subtask, i.e., L l=1 c il Mi f l . Taking task allocation decision q into account, the execution time of processor θ k is computed by

Λ(k) = N i=1 q ik L l=1 c il Mi f l .
Since the processors have the same voltage/frequency levels {(v 1 , f 1 ), . . . , (v L , f L )}, different task allocation schemes will not influence the solution of FAP, i.e., the task-to-processor decision can be made when frequency-to-task assignment is done. We introduce an auxiliary(continuous) variable U , which is denoted as the maximum task execution time among the processors, i.e., U = max ∀k∈M {Λ(k)}, and our aim is to minimize U by allocating the selected tasks to each processor. Thus, the Task Allocation Problem (TAP) is formulated as

TAP : min q,U U s.t.          U ≥ N i=1 q ik L l=1 c il M i f l , ∀k ∈ M, (3),
N i=1 q ik L l=1 c il M i f l ≤ H, ∀k ∈ M.
Note that the TAP is composed of binary variables q and a continuous variable U . It can be solved using a similar method as the one presented for the solution of the MP.

C. Optional Task Adjustment

Based on frequency-to-task assignment decision c and taskto-processor allocation decision q, the PP reduces to the following Optional Task Adjustment Problem (OTAP): 4), ( 5), [START_REF] Liu | Imprecise computations[END_REF] under given c and q.

OTAP : min o - N i=1 g i (o i ) s.t. (
Although the FAP and the TAP are ILP, compared with LP, they are still complex to solve directly, especially when problem size is large. To reduce the computational complexity, we relax FAP and TAP to LP problems. In particular, for the FAP (TAP), we introduce continuous variables q (ĉ), where 0 ≤ qik ≤ 1 (0 ≤ ĉil ≤ 1), to replace the original integer variables q (c). And then, we solve the relaxed problem (LP) and round the solution q (ĉ) to the nearest binary matrix that is feasible to the FAP (TAP). Such a binary matrix can be efficiently found by using the Feasibility Pump (FP) method proposed in [START_REF] Matteo | The feasibility pump[END_REF].

V. EXPERIMENTAL RESULTS

The values and the tuned parameters of the experimental set-up are summarized in Table II. The processor parameters are adopted from [START_REF] Chen | Energy optimization for realtime multiprocessor system-on-chip with optimal DVFS and DPM combination[END_REF], where the platform is based on 70 nm technology and the accuracy of the parameters' values has been verified by SPICE simulations. The number of processors M is tuned from 4 to 10 with a step of 2. The WCECs of tasks are assumed to be in the range provided in Table II. This range is calculated in [START_REF] Ramkumar | Temperature aware task sequencing and voltage scaling[END_REF] from the MiBench and MediaBench benchmark suites. The number of tasks N is tuned from 10 to 50 with a step of 10. The QoS function of the tasks, i.e., the objective function of the PP, is adopted from [START_REF] Zhou | Energy-adaptive scheduling of imprecise computation tasks for QoS optimization in real-time MPSoC systems[END_REF], [START_REF] Wei | Cost-constrained QoS optimization for approximate computation real-time tasks in heterogeneous MPSoCs[END_REF]. The scheduling horizon H is assumed to be proportional to the average processor workload, and the energy supply E s is set to E s = ηE h , where E h is the minimum energy required to execute {M 1 + O 1 , . . . , M N + O N } cycles, η ∈ [0, 1] is an energy efficiency factor, and η is tuned from 0.8 to 0.9 with a step of 0.05. Note that different processor and task parameters lead to different values in the parameters {A, C, D, f , b 1 , b 2 } for the PP1. However, the problem structures under different values of parameters are the same, and, thus, the proposed methods are still applicative.

M i +O i f l Objective function N i=1 gi(oi) = N i=1 oi Constraints H = N M N i=1 D i N Es = ηE h E h = M HP s 0 + N i=1 min ∀l∈L M i +O i f l P s l + P d l -P s 0 Tuned parameters M N η Min/Max/Step 4/10/2
10/50/10 0.8/0.9/0.05

We compare the behavior (QoS and computation time) of the proposed OJTM and HJTM with: 1) optimal approaches, i.e. Branch and Bound method (B&B) [START_REF] Boyd | Branch and bound methods[END_REF], which is known to provide optimal solution for the MILP problem -as far as we know no optimal algorithm exist for the problem formulation PP1, 2) stochastic approaches, i.e. Genetic Algorithm (GA) [START_REF] Sayuti | Real-time low-power task mapping in networks-on-chip[END_REF], and 3) heuristics, i.e. Adaptive Task Allocation (ATA) [START_REF] Zhou | Energy-adaptive scheduling of imprecise computation tasks for QoS optimization in real-time MPSoC systems[END_REF] -a two-step optimization approach. 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.

The QoS achieved by OJTM for all M , N and η parameters is shown in Fig. 3. During the simulations, the task sets in the experiments with N = i (i = 20, . . . , 50) and N = i -1 are correlated, i.e., the task set in the experiment with N = i is extended based on the task set in the experiment with N = i -1. Note that 1) the scheduling horizon H is proportional to the average processor workload, 2) the energy supply E s is proportional to the number of tasks N , and 3) the QoS is given by N i=1 o i . The QoS generally increases with respect to 1) N and 2) η under given M and N . We further explore the behavior of OJTM and HJTM by comparing the QoS gain of each method with the optimal B&B for all the aforementioned cases. Fig. 4 shows the statistical property of the QoS gain. The QoS gain of OJTM and HJTM (OJTM and B&B) is given by Qo(M,N,η)-Q h (M,N,η)

Qo(M,N,η) Qo(M,N,η)-Q b (M,N,η) Qo(M,N,η)
, where Q b (M, N, η), Q o (M, N, η) and Q h (M, N, η) are the QoS achieved by B&B, OJTM and HJTM under given M , N and η parameters, respectively. The box plot "OJTM vs HJTM" ("OJTM vs B&B") with η = 0.8 shows the statistical property of data set Qo(M,N,0.8)-Q h (M,N,0.8)

Qo(M,N,0.8) Qo(M,N,0.8)-Q b (M,N,0.8) Qo(M,N,0.8)
for all 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. From Fig. 4, we observe that 1) the solutions given by B&B and OJTM are same, and, thus, OJTM also finds the optimal solution, and 2) OJTM achieves higher QoS (26.3% in average) than that of HJTM. The computation time of OJTM, HJTM and B&B is evaluated in Fig. 5. From Fig. 5(a), which shows the OJTM (HJTM) computation time for solving the PP1 (PP), we observe that 1) the HJTM computation time is almost unchanged with M , N and η varying, and 2) when M and N are fixed and η is tuned from 0.8 to 0.9, the changes of the OJTM computation time are small, compared with the changes of the OJTM computation time with M and N varying. Therefore, compared with OJTM, HJTM has a negligible computation time. We further compare the computation time gain of OJTM and B&B for all M , N and η parameters. The result is shown in Fig. 5 for all M and N parameters. With N increasing, the computation time of B&B and OJTM grows. However, OJTM takes a shorter computation time than that of B&B (22.6% in average). For an optimization problem, its computational complexity increases significantly with the number of variables and constraints. Solving iteratively smaller problems, i.e., the MP and the SP, is more efficient than solving a single large problem. This result agrees with the comparison of [START_REF] Randazzo | A comparison of optimal methods for local access uncapacitated network design[END_REF]: the decomposition-based method is faster than the B&B for lager problem instances.

We define the OJTM convergence iteration as the number of iterations to achieve Φ u (m) -Φ l (m) ≤ ε, where ε = 0.01. Fig. 6 shows that with M and N increasing, more constraints are involved into the problem, and, thus, a higher number of iterations is required to converge to the optimal solution. We observe that when M ≤ 8 and N ≤ 40, the OJTM convergence iteration almost increases linearly with M and N .

Denote Q g (M, N, η) and T g (M, N, η) as the QoS achieved by GA and the computation time of GA under given M , N and η parameters, respectively. The QoS and computation time gains of OJTM and GA, i.e., , for all M , N and η parameters, are shown in Fig. 7. From this figure we observe that 1) OJTM achieves a higher QoS than that of GA (7.6% in average), and 2) OJTM takes a shorter computation time than that of GA (35.6% in average). Although GA can solve complex nonlinear programming problem (non-convex), such as MINLP, the optimality of the solution is hard to guarantee. Compared with OJTM, the GA structure is more complex, as in each iteration GA needs to generate new populations. Therefore, the problem transformation from MINLP-based PP to MILPbased PP1 is necessary, since it can simplify the structure of the problem, and, thus, the optimal solution is much easier to find. Denote Q a (M, N, η) and T a (M, N, η) as the QoS achieved by ATA and the computation time of ATA under given M , N and η parameters, respectively. The QoS gain of HJTM and ATA, i.e., Q h (M,N,η)-Qa(M,N,η)

Q h (M,N,η)
, and the computation time gap of HJTM and ATA, i.e., {T h (M, N, η) -T a (M, N, η)}, for all M , N and η parameters, are shown in Fig. 8. ATA solves the task-to-processor allocation and the optional subtask adjustment problems in sequence, where each processor has its own frequency. Since the HJTM optimizes also the frequencyto-task assignment, and, thus, achieves a higher QoS (96.7% in average) than that of ATA. We observe that 1) the difference between T h (M, N, η) and T a (M, N, η) is small, and 2) the average value of {T h (M, N, η)} is slightly higher than {T a (M, N, η)}. HJTM and ATA are both polynomial-time algorithms. Sometimes T h (M, N, η) can be a bit larger than T a (M, N, η), since 1) HJTM is a three-step heuristic while ATA is a two-step heuristic, and 2) we need to run FP method repeatedly until feasible solutions are found when solving the FAP and the TAP.

VI. CONCLUSION

In this paper, we formulated the problem of task mapping on DVFS-enabled homogeneous multicore as an MILP, with the goal of maximizing QoS without violating the real-time and the energy supply constraints. This problem is optimally solved by the OJTM algorithm. A novel algorithm, HJTM, is proposed to further reduce the computational complexity. Our numerical results show that OJTM is guaranteed to converge to the optimal solution, while HJTM can find a feasible solution within a negligible computation time, compared with OJTM. In the future, we plan to extend our method to heterogeneous multicore platforms (e.g., big.LITTLE platforms), accelerate the OJTM and consider the dependency among the tasks.

Fig. 1 .

 1 Fig. 1. The structure of OJTM algorithm.

  are the sets of feasibility and infeasibility constraints (Benders cuts), respectively. λ(m) and λ(m) are the solutions of the Dual Slave Problem (DSP)[START_REF] Micheletto | Using bioinspired metaheuristics to solve reward-based energy-aware mandatory/optional realtime tasks scheduling[END_REF] and the Dual Feasibility Check Problem (DFCP)[START_REF] Fisher | The multiprocessor real-time scheduling of general task systems[END_REF] at the m th iteration, respectively. A and B are the sets of iterations that the DSP has bounded and unbounded solutions, respectively. Note that 1) the objective function of the PP1 only contains continuous variables y, and 2) the MP only considers binary variables x. We introduce an auxiliary (continuous) variable Φ for the MP as the objective function, where Φ has the same physical meaning as the objective function of the PP1. The relationship between Φ and Φ is explained in the next section.The corresponding SP is formulated as SP : Φ u (m) = min y 0 f y s.t. Cx(m) + Dy b 2 ,

Fig. 3 .

 3 Fig. 3. QoS of OJTM with M , N and η varying.

Fig. 4 .

 4 Fig. 4. QoS gain of OJTM, HJTM and B&B with M , N and η varying.

  (b). Denote T b (M, N, η) and T o (M, N, η) as the computation time of B&B and OJTM under given M , N and η parameters, respectively. The box plot "B&B vs OJTM" with η = 0.8 shows the statistical property of data set T b (M,N,0.8)-To(M,N,0.8) T b (M,N,0.8)

  Qo(M,N,η)-Qg(M,N,η) Qo(M,N,η) and Tg(M,N,η)-To(M,N,η) Tg(M,N,η)

  Computation time of OJTM and HJTM with M , N and η varying.

  Computation time gain of OJTM and B&B with M , N and η varying.

Fig. 5 .

 5 Fig. 5. Comparison of OJTM, HJTM and B&B computation time with M , N and η varying.

Fig. 6 .

 6 Fig. 6. OJTM convergence iteration.

Fig. 7 .

 7 Fig. 7. QoS and computation time gains of OJTM and GA with M , N and η varying.

Fig. 8 .

 8 Fig. 8. QoS and computation time comparison of HJTM and ATA with M , N and η varying.

TABLE I

 I

					.		TASK MAPPING METHOD
			Energy-aware								QoS-aware
	[10]	[11]	[12]	[9]	[7]	[8]	[4]	[13]	[20]	[19]	[18]	[17]	[14]	[15]	[16]

TABLE II

 II

		.	EXPERIMENTAL SET-UP
		Processor θ k characteristics
	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) P s 0 (µW)	184.9 246	266.7 370.4 498.9 290.1 340.3 397.6 80	655.5 462.7
		Task τi characteristics
	Mi, Oi ∈ [4 × 10 7 , 6 × 10 8 ]	Di = min ∀l∈L

√ √ √ √

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).