Title: Scheduling imprecise task graphs for real-time applications

Authors: R.C. Ravindran; C. Mani Krishna; Israel Koren; Zahava Koren

Addresses: Department of Electrical and Computer Engineering, University of Massachusetts, Amherst, MA 01003, USA ' Department of Electrical and Computer Engineering, University of Massachusetts, Amherst, MA 01003, USA ' Department of Electrical and Computer Engineering, University of Massachusetts, Amherst, MA 01003, USA ' Department of Electrical and Computer Engineering, University of Massachusetts, Amherst, MA 01003, USA

Abstract: Many of the real-time tasks within embedded real-time control applications fall into the imprecise category. Such tasks are iterative in nature, with output precision improving as execution time increases (up to a point). These tasks can be terminated early at the cost of poorer quality output. Many imprecise tasks in CPS are dependent, with one task feeding other tasks in a task precedence graph (TPG). A task output quality depends on the quality of its input data as well as on the execution time that is allotted to it. In this paper, we study the allocation/scheduling of imprecise TPGs on multiprocessors to maximise output quality where resources (time and energy) are limited. Our heuristic algorithms can effectively reclaim resources when tasks finish earlier than their estimated worst-case execution time. Dynamic voltage scaling is used to manage energy consumption and keep it under a specified bound.

Keywords: imprecise tasks; dynamic voltage scaling; real time control; embedded systems; scheduling; task graphs; multiprocessors; energy consumption.

DOI: 10.1504/IJES.2014.060919

International Journal of Embedded Systems, 2014 Vol.6 No.1, pp.73 - 85

Received: 24 May 2013
Accepted: 08 Aug 2013

Published online: 31 Jul 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article