Scheduling imprecise task graphs for real-time applications

被引：11

作者：

Ravindran, R. C. ^{[1
]}

Krishna, C. Mani ^{[1
]}

Koren, Israel ^{[1
]}

Koren, Zahava ^{[1
]}

机构：

[1] Univ Massachusetts, Dept Elect & Comp Engn, Amherst, MA 01003 USA

来源：

INTERNATIONAL JOURNAL OF EMBEDDED SYSTEMS | 2014年 / 6卷 / 01期

基金：

美国国家科学基金会;

关键词：

imprecise tasks; dynamic voltage scaling; real-time systems;

D O I：

10.1504/IJES.2014.060919

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：73 / 85

页数：13

共 24 条

[1] Quasi-static assignment of voltages and optional cycles in imprecise-computation systems with energy considerations [J].

Alejandro Cortes, Luis ;

Eles, Petru ;

Peng, Zebo .

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, 2006, 14 (10) :1117-1129

[2]

Cheng A. M. K., 2004, Proceedings of the 28th Annual International Computer Software and Applications Conference. COMPSAC 2004, P167, DOI 10.1109/CMPSAC.2004.1342822

[3] Global Semi-Fixed-Priority Scheduling on Multiprocessors [J].

Chishiro, Hiroyuki ;

Yamasaki, Nobuyuki .

2011 IEEE 17TH INTERNATIONAL CONFERENCE ON EMBEDDED AND REAL-TIME COMPUTING SYSTEMS AND APPLICATIONS (RTCSA 2011), VOL 1, 2011, :218-223

[4] Semi-Fixed-Priority Scheduling: New Priority Assignment Policy for Practical Imprecise Computation [J].

Chishiro, Hiroyuki ;

Takeda, Akira ;

Funaoka, Kenji ;

Yamasaki, Nobuyuki .

16TH IEEE INTERNATIONAL CONFERENCE ON EMBEDDED AND REAL-TIME COMPUTING SYSTEMS AND APPLICATIONS (RTCSA 2010), 2010, :339-348

[5] SCHEDULING PERIODIC JOBS THAT ALLOW IMPRECISE RESULTS [J].

CHUNG, JY ;

LIU, JWS ;

LIN, KJ .

IEEE TRANSACTIONS ON COMPUTERS, 1990, 39 (09) :1156-1174

[6] Scheduling imprecise tasks in real-time distributed systems [J].

de Oliveira, WS ;

Fraga, JD ;

Farines, JM .

FOURTH IEEE INTERNATIONAL SYMPOSIUM ON OBJECT-ORIENTED REAL-TIME DISTRIBUTED COMPUTING, PROCEEDINGS, 2001, :319-326

[7]

Dey J. K., 1993, Performance Evaluation Review, V21, P217, DOI 10.1145/166962.167013

[8] On-line scheduling policies for a class of IRIS (increasing reward with increasing service) real-time tasks [J].

Dey, JK ;

Kurose, J ;

Towsley, D .

IEEE TRANSACTIONS ON COMPUTERS, 1996, 45 (07) :802-813

[9]

Feng W., 1993, Proceedings of the IEEE Workshop on Real-Time Applications (Cat.No.93TH0559-5), P76, DOI 10.1109/RTA.1993.263112

[10] Algorithms for scheduling real-time tasks with input error and end-to-end deadlines [J].

Feng, WC ;

Liu, JWS .

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1997, 23 (02) :93-106

← 1 2 3 →