Energy-Aware Scheduling of Task Graphs with Imprecise Computations and End-to-End Deadlines

Imprecise computations provide an avenue for scheduling algorithms developed for energy-constrained computing devices by trading off output quality with the utilization of system resources. This work proposes a method for scheduling task graphs with potentially imprecise computations, with the goal...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-05
Main Authors: Esmaili, Amirhossein, Nazemi, Mahdi, Massoud Pedram
Format: Article
Language:English
Subjects:
Algorithms
Energy consumption
Energy management
Graphs
Linear programming
Mixed integer
Multiprocessing
Optimization
Schedules
Scheduling
Task scheduling
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Imprecise computations provide an avenue for scheduling algorithms developed for energy-constrained computing devices by trading off output quality with the utilization of system resources. This work proposes a method for scheduling task graphs with potentially imprecise computations, with the goal of maximizing the quality of service subject to a hard deadline and an energy bound. Furthermore, for evaluating the efficacy of the proposed method, a mixed integer linear program formulation of the problem, which provides the optimal reference scheduling solutions, is also presented. The effect of potentially imprecise inputs of tasks on their output quality is taken into account in the proposed method. Both the proposed method and MILP formulation target multiprocessor platforms. Experiments are run on 10 randomly generated task graphs. Based on the obtained results, for some cases, a feasible schedule of a task graph can be achieved with the energy consumption less than 50% of the minimum energy required for scheduling all tasks in that task graph completely precisely.
ISSN:2331-8422