Controllable QoS for Imprecise Computation Tasks on DVFS Multicores With Time and Energy Constraints
- 2 July 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Emerging and Selected Topics in Circuits and Systems
- Vol. 8 (4) , 708-721
Abstract
Multicore architectures have been used to enhance computing capabilities, but the energy consumption is still an important concern. Embedded application domains usually require less accurate, but always in-time, results. Imprecise computation (IC) can be used to divide a task into a mandatory subtask providing a baseline quality of service (QoS) and an optional subtask that further increases the baseline QoS. This paper aims at maximizing the system QoS by solving task mapping and dynamic voltage and frequency scaling for dependent IC-tasks under real-time and energy constraints. Compared with the existing approaches, we consider the joint-design problem, where task-to-processor allocation, frequency-to-task assignment, task scheduling, and task adjustment are optimized simultaneously. The joint-design problem is formulated as an NP-hard mixed-integer non-linear programming, and it is safely transformed to a mixed-integer linear programming (MILP) without performance degradation. Two methods (basic and accelerated version) are proposed to find the optimal solution to an MILP problem. They are based on problem decomposition and provide a controllable way to trade off the quality of the solution and the computational complexity. The optimality of the proposed methods is proved rigorously, and the experimental results show reduced computation time (23.7% in average) compared with the existing optimal methods.Keywords
Funding Information
- INRIA Post-Doctoral Research Fellowship Program
- ANR AppRoximaTivE Flexible Circuits and Computing for IoT Project (ANR-15-CE25-0015)
- National Natural Science Foundation of China (61403340)
This publication has 31 references indexed in Scilit:
- An Efficient Biobjective Heuristic for Scheduling Workflows on Heterogeneous DVS-Enabled ProcessorsJournal of Applied Mathematics, 2014
- Energy optimization for real-time multiprocessor system-on-chip with optimal DVFS and DPM combinationACM Transactions on Embedded Computing Systems, 2014
- Non-convex mixed-integer nonlinear programming: A surveySurveys in Operations Research and Management Science, 2012
- Energy- and reliability-aware task scheduling onto heterogeneous MPSoC architecturesThe Journal of Supercomputing, 2011
- The feasibility pumpMathematical Programming, 2005
- Maximizing rewards for real-time applications with energy constraintsACM Transactions on Embedded Computing Systems, 2003
- Imprecise computationsProceedings of the IEEE, 1994
- On the complexity of integer programmingJournal of the ACM, 1981
- A Modified Benders' Partitioning Algorithm for Mixed Integer ProgrammingManagement Science, 1977
- Partitioning procedures for solving mixed-variables programming problemsNumerische Mathematik, 1962