More Web Proxy on the site http://driver.im/

research-article

Iterative robust multiprocessor scheduling

Authors:

Shreya Adyanthaya,

Ramon SchiffelersAuthors Info & Claims

RTNS '15: Proceedings of the 23rd International Conference on Real Time and Networks Systems

Pages 23 - 32

https://doi.org/10.1145/2834848.2834857

Published: 04 November 2015 Publication History

Abstract

General purpose platforms are characterized by unpredictable timing behavior. Real-time schedules of tasks on general purpose platforms need to be robust against variations in task execution times. We define robustness in terms of the expected number of tasks that miss deadlines. We present an iterative robust scheduler that produces robust multiprocessor schedules of directed acyclic graphs with a low expected number of tasks that miss their deadlines. We experimentally show that this robust scheduler produces significantly more robust schedules in comparison to a scheduler using nominal execution times on both real world and synthetic test cases.

References

[1]

L. Abeni and G. Buttazzo. Integrating multimedia applications in hard real-time systems. In Real-Time Systems Symposium, 1998. Proceedings., The 19th IEEE, pages 4--13, Dec 1998.

Digital Library

[2]

S. Adyanthaya et al. Fast multiprocessor scheduling with fixed task binding of large scale industrial cyber physical systems. In Digital System Design (DSD), 2013 Euromicro Conference on, pages 979--988, 2013.

Digital Library

[3]

S. Adyanthaya et al. Robustness analysis of multiprocessor schedules. In Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS XIV), 2014 International Conference on, pages 9--17, 2014.

[4]

S. Ali et al. Measuring the robustness of a resource allocation. Parallel and Distributed Systems, IEEE Transactions on, 15(7):630--641, 2004.

Digital Library

[5]

L. Boloni and D. C. Marinescu. Robust scheduling of metaprograms. Journal of Scheduling, 5(5):395--412, 2002.

[6]

C. E. Clark. The greatest of a finite set of random variables. Operations Research, 9(2):145--162, 1961.

Digital Library

[7]

R. L. Daniels and J. E. Carrillo. β-robust scheduling for single-machine systems with uncertain processing times. IIE Transactions, 29(11):977--985, 1997.

[8]

A. Davenport, C. Gefflot, and C. Beck. Slack-based techniques for robust schedules. In Sixth European Conference on Planning, 2014.

[9]

R. I. Davis and A. Burns. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv., 43(4):35:1--35:44, Oct. 2011.

Digital Library

[10]

D. England, J. B. Weissman, and J. Sadagopan. A new metric for robustness with application to job scheduling. In HPDC, pages 135--143. IEEE, 2005.

Digital Library

[11]

F. Fauberteau et al. Robust partitioned scheduling for real-time multiprocessor systems. In Distributed, Parallel and Biologically Inspired Systems, pages 193--204. Springer, 2010.

[12]

D. Hardy and I. Puaut. Static probabilistic worst case execution time estimation for architectures with faulty instruction caches. In Proceedings of the 21st International Conference on Real-Time Networks and Systems, RTNS '13, pages 35--44, New York, NY, USA, 2013. ACM.

Digital Library

[13]

T. C. Hu. Parallel sequencing and assembly line problems. Operations Research, 9(6):841--848, 1961.

Digital Library

[14]

K. Li et al. Scheduling precedence constrained stochastic tasks on heterogeneous cluster systems. Computers, IEEE Transactions on, 64(1):191--204, Jan 2015.

[15]

M. Lombardi et al. Robust scheduling of task graphs under execution time uncertainty. Computers, IEEE Transactions on, 62(1):98--111, 2013.

Digital Library

[16]

S. Nadarajah and S. Kotz. Exact distribution of the max/min of two gaussian random variables. Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, 16(2):210--212, 2008.

Digital Library

[17]

R. Schiffelers, W. Alberts, and J. Voeten. Model based design, analysis and synthesis of servo controllers for lithoscanners. MPM, 2012.

Digital Library

[18]

V. Shestak et al. Stochastic robustness metric and its use for static resource allocations. J. Parallel Distrib. Comput., 68(8):1157--1173, 2008.

Digital Library

[19]

S. Stuijk et al. SDF³: SDF For Free. In Application of Concurrency to System Design, 6th International Conference, ACSD, Proceedings, pages 276--278, 2006. {Online}. Available: http://www.es.ele.tue.nl/sdf3.

Digital Library

[20]

B. Theelen. A performance analysis tool for scenario-aware streaming applications. In Quantitative Evaluation of Systems, 2007. QEST 2007. Fourth International Conference on the, pages 269--270, Sept 2007.

Digital Library

[21]

D. Wang et al. Estimating deadline-miss probabilities of tasks in large distributed systems. In Advances in Grid and Pervasive Computing, pages 254--263. 2012.

Digital Library

Cited By

Nasri MVoeten J(2024)A Position Paper on Transforming Embedded Real-Time Systems to the Cloud: Challenges and New Research Directions2024 IEEE Workshop on Design Automation for CPS and IoT (DESTION)10.1109/DESTION62938.2024.00012(30-32)Online publication date: 13-May-2024
https://doi.org/10.1109/DESTION62938.2024.00012
Kessler CLitzinger SKeller J(2021)Crown-scheduling of sets of parallelizable tasks for robustness and energy-elasticity on many-core systems with discrete dynamic voltage and frequency scalingJournal of Systems Architecture10.1016/j.sysarc.2021.101999(101999)Online publication date: Jan-2021
https://doi.org/10.1016/j.sysarc.2021.101999
Kessler CLitzinger SKeller J(2020)Robustness and Energy-elasticity of Crown Schedules for Sets of Parallelizable Tasks on Many-core Systems with DVFS2020 28th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP)10.1109/PDP50117.2020.00027(136-143)Online publication date: Mar-2020
https://doi.org/10.1109/PDP50117.2020.00027

Recommendations

Utilization Bounds for Multiprocessor Rate-Monotonic Scheduling

In this paper, we extend Liu and Layland’s utilization bound for fixed priority scheduling on uniprocessors to homogeneous multiprocessor systems under a partitioning strategy. Assuming that tasks are pre-emptively scheduled on each processor according ...
Scheduling multiprocessor UET tasks of two sizes

In this paper we study task scheduling problems on m identical parallel processors, where each task has unit execution time, and needs either a single processor, or q processors concurrently, and it has a release date and a due date. Under the ...
Scheduling chained multiprocessor tasks onto large multiprocessor system

In this paper, we proposed an effective approach for scheduling of multiprocessor unit time tasks with chain precedence on to large multiprocessor system. In this work, we considered splitable and non-splitable multiprocessor tasks, which is a new and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

RTNS '15: Proceedings of the 23rd International Conference on Real Time and Networks Systems

November 2015

320 pages

ISBN:9781450335911

DOI:10.1145/2834848

General Chair:
Julien Forget
Université de Lille, France

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 November 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

RTNS '15

RTNS '15: 23rd International Conference on Real-Time Networks and Systems

November 4 - 6, 2015

Lille, France

Acceptance Rates

RTNS '15 Paper Acceptance Rate 31 of 66 submissions, 47%;

Overall Acceptance Rate 119 of 255 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
60
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nasri MVoeten J(2024)A Position Paper on Transforming Embedded Real-Time Systems to the Cloud: Challenges and New Research Directions2024 IEEE Workshop on Design Automation for CPS and IoT (DESTION)10.1109/DESTION62938.2024.00012(30-32)Online publication date: 13-May-2024
https://doi.org/10.1109/DESTION62938.2024.00012
Kessler CLitzinger SKeller J(2021)Crown-scheduling of sets of parallelizable tasks for robustness and energy-elasticity on many-core systems with discrete dynamic voltage and frequency scalingJournal of Systems Architecture10.1016/j.sysarc.2021.101999(101999)Online publication date: Jan-2021
https://doi.org/10.1016/j.sysarc.2021.101999
Kessler CLitzinger SKeller J(2020)Robustness and Energy-elasticity of Crown Schedules for Sets of Parallelizable Tasks on Many-core Systems with DVFS2020 28th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP)10.1109/PDP50117.2020.00027(136-143)Online publication date: Mar-2020
https://doi.org/10.1109/PDP50117.2020.00027

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents