research-article

A semi-partitioned approach for parallel real-time scheduling

Authors:

Laurent George,

Pierre Courbin,

Joël GoossensAuthors Info & Claims

RTNS '12: Proceedings of the 20th International Conference on Real-Time and Network Systems

Pages 151 - 160

https://doi.org/10.1145/2392987.2393006

Published: 08 November 2012 Publication History

Abstract

In this paper, we consider the problem of scheduling periodic Multi-Phase Multi-Thread tasks on a set of m identical processors with Earliest Deadline First (EDF) scheduling. Each periodic task is defined by a sequence of phases with offsets that can be possibly parallelized. We use a portioned semi-partitioned approach with migrations at local deadlines assigned to each phase. We extend this approach to take into account phase parallelism. The phase parallelism we consider is an extension of the popular job parallelism. A phase, if parallelizable, can be decomposed into parallel threads run on a configurable number of processors. We only require simultaneous execution of threads inside a window equal to the local deadline of their associated phase. To decide on the schedulability of a Multi-Phase Multi-Thread task, we extend the popular uniprocessor EDF feasibility condition for periodic asynchronous tasks. We propose two new schedulability tests for EDF that significantly improve the well known Leung and Merill feasibility test based on the feasibility interval [O_min, O_max + 2P], where O_min and O_max are respectively the minimum and maximum phase offsets and P the least common multiple of the task periods. The first schedulability test is used when an EDF simulation is needed and gives, by simulation, a 44% gain in simulation speed. The second method provides a sufficient schedulability test with a time interval of length P based on the demand bound function. Finally, we study three local deadline assignment heuristics assigned to parallelizable phases. We compare and analyze the performances obtained by simulation for those three local deadline assignment heuristics.

References

[1]

V. Berten, S. Collette, and J. Goossens. Feasibility Test for Multi-Phase Parallel Real-Time Jobs, pages 33--36. Proceedings of the Work-in-Progress session of the IEEE Real-Time Systems Symposium 2009, 2009.

[2]

A. Choquet-Geniet and E. Grolleau. Minimal schedulability interval for real-time systems of periodic tasks with offsets. Theor. Comput. Sci., 310(1--3):117--134, 2004.

Digital Library

[3]

S. Collette, L. Cucu, and J. Goossens. Integrating job parallelism in real-time scheduling theory. Inf. Process. Lett., 106(5):180--187, 2008.

Digital Library

[4]

S. Funk and S. K. Baruah. Restricting EDF migration on uniform heterogeneous multiprocessors. Technique et Science Informatiques, 24(8):917--938, 2005.

[5]

L. George, P. Courbin, and Y. Sorel. Job vs. portioned partitioning for the earliest deadline first semi-partitioned scheduling. Journal of Systems Architecture - Embedded Systems Design, 57(5):518--535, 2011.

Digital Library

[6]

L. George and J. Hermant. Characterization of the Space of Feasible Worst-Case Execution Times for Earliest-Deadline-First scheduling, volume Vol. 6, Num. 11. Journal of Aerospace Computing, Information and Communication (JACIC), American Institute of Aeronautics and Astronautics (AIAA), November 2009.

[7]

L. George and J.-F. Hermant. A norm approach for the partitioned EDF scheduling of sporadic task systems. In ECRTS, pages 161--169, 2009.

Digital Library

[8]

C.-C. Han and K.-J. Lin. Scheduling parallelizable jobs on multiprocessors. In IEEE Real-Time Systems Symposium, pages 59--67, 1989.

[9]

S. Kato, N. Yamasaki, and Y. Ishikawa. Semi-partitioned scheduling of sporadic task systems on multiprocessors. In ECRTS, pages 249--258, 2009.

Digital Library

[10]

K. Lakshmanan, S. Kato, and R. R. Rajkumar. Scheduling parallel real-time tasks on multi-core processors. In Proceedings of the 2010 31st IEEE Real-Time Systems Symposium, RTSS '10, pages 259--268, Washington, DC, USA, 2010. IEEE Computer Society.

Digital Library

[11]

J. Y.-T. Leung and M. L. Merrill. A note on preemptive scheduling of periodic, real-time tasks. Inf. Process. Lett., 11(3):115--118, 1980.

[12]

J. M. López, J. L. Díaz, and D. F. García. Utilization bounds for EDF scheduling on real-time multiprocessor systems. Real-Time Systems, 28(1):39--68, 2004.

Digital Library

[13]

I. Lupu, P. Courbin, L. George, and J. Goossens. Multi-criteria evaluation of partitioning schemes for real-time systems. Emerging Technologies and Factory Automation (ETFA), 2010 IEEE Conference, pages 1--8, sept. 2010.

[14]

G. Manimaran, C. S. R. Murthy, and K. Ramamritham. A new approach for scheduling of parallelizable tasks in real-time multiprocessor systems. Real-Time Systems, 15(1):39--60, 1998.

Digital Library

[15]

A. Saifullah, K. Agrawal, C. Lu, and C. Gill. Multi-core real-time scheduling for generalized parallel task models. In Proceedings of the 2011 32st IEEE Real-Time Systems Symposium, RTSS '11, Washington, DC, USA, 2011. IEEE Computer Society.

Digital Library

Cited By

Zhao SDai XLesage BBate I(2023)Cache-Aware Allocation of Parallel Jobs on Multi-cores based on Learned RecencyProceedings of the 31st International Conference on Real-Time Networks and Systems10.1145/3575757.3593642(177-187)Online publication date: 7-Jun-2023
https://dl.acm.org/doi/10.1145/3575757.3593642
Goossens JMasson D(2022)Simulation intervals for uniprocessor real-time schedulers with preemption delayProceedings of the 30th International Conference on Real-Time Networks and Systems10.1145/3534879.3534887(36-45)Online publication date: 7-Jun-2022
https://dl.acm.org/doi/10.1145/3534879.3534887
Zhao SDai XBate I(2022)DAG Scheduling and Analysis on Multi-Core Systems by Modelling Parallelism and DependencyIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.317704633:12(4019-4038)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TPDS.2022.3177046
Show More Cited By

Index Terms

A semi-partitioned approach for parallel real-time scheduling
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems

Recommendations

A semi-partitioned real-time scheduling approach for periodic task systems on multicore platforms
SAC '12: Proceedings of the 27th Annual ACM Symposium on Applied Computing

Semi-partitioned scheduling is regarded as a viable alternative to partitioned or global scheduling approaches. Advantage of semi-partitioned scheduling is two-folds: it has reduced runtime overhead compared to global scheduling, and improved ...
Job vs. portioned partitioning for the earliest deadline first semi-partitioned scheduling

In this paper, we focus on the semi-partitioned scheduling of sporadic tasks with constrained deadlines and identical processors. We study two cases of semi-partitioning: (i) the case where the worst case execution time (WCET) of a job can be portioned, ...
Statically optimal dynamic soft real-time semi-partitioned scheduling
Abstract
Semi-partitioned scheduling is an approach to multiprocessor real-time scheduling where most tasks are fixed to processors, while a small subset of tasks is allowed to migrate. This approach offers reduced overhead compared to global scheduling, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

RTNS '12: Proceedings of the 20th International Conference on Real-Time and Network Systems

November 2012

216 pages

ISBN:9781450314091

DOI:10.1145/2392987

General Chairs:
Liliana Cucu-Grosjean
INRIA Nancy-Grand Est, France
,
Nicolas Navet
University of Luxembourg, Luxembourg
,
Program Chairs:
Christine Rochange
University of Toulouse/IRIT, France
,
James H. Anderson
University of North Carolina

Copyright © 2012 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]

Sponsors

University of Lorraine: University of Lorraine
INRIA: Institut Natl de Recherche en Info et en Automatique
GDR ASR: GDR Architecture, Systèmes et Réseaux

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 November 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

real-time scheduling theory

Qualifiers

Research-article

Conference

RTNS '12

Sponsor:

University of Lorraine
INRIA
GDR ASR

RTNS '12: 20th International Conference on Real-Time and Network Systems

November 8 - 9, 2012

Pont à Mousson, France

Acceptance Rates

Overall Acceptance Rate 119 of 255 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
164
Total Downloads

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

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhao SDai XLesage BBate I(2023)Cache-Aware Allocation of Parallel Jobs on Multi-cores based on Learned RecencyProceedings of the 31st International Conference on Real-Time Networks and Systems10.1145/3575757.3593642(177-187)Online publication date: 7-Jun-2023
https://dl.acm.org/doi/10.1145/3575757.3593642
Goossens JMasson D(2022)Simulation intervals for uniprocessor real-time schedulers with preemption delayProceedings of the 30th International Conference on Real-Time Networks and Systems10.1145/3534879.3534887(36-45)Online publication date: 7-Jun-2022
https://dl.acm.org/doi/10.1145/3534879.3534887
Zhao SDai XBate I(2022)DAG Scheduling and Analysis on Multi-Core Systems by Modelling Parallelism and DependencyIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.317704633:12(4019-4038)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TPDS.2022.3177046
Cho YKim DPark DLee SLee C(2022)Optimal Parallelization of Single/Multi-Segment Real-Time Tasks for Global EDFIEEE Transactions on Computers10.1109/TC.2021.307173071:5(1077-1091)Online publication date: 1-May-2022
https://doi.org/10.1109/TC.2021.3071730
Cho YShin DPark JLee C(2021)Conditionally Optimal Parallelization of Real-Time DAG Tasks for Global EDF2021 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS52674.2021.00027(188-200)Online publication date: Dec-2021
https://doi.org/10.1109/RTSS52674.2021.00027
Cho YKim DPark DLee SLee C(2019)Conditionally Optimal Task Parallelization for Global EDF on Multi-core Systems2019 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS46320.2019.00027(194-206)Online publication date: Dec-2019
https://doi.org/10.1109/RTSS46320.2019.00027
Kim KCho YEo JLee CHan J(2018)System-Wide Time versus Density Tradeoff in Real-Time Multicore Fluid SchedulingIEEE Transactions on Computers10.1109/TC.2018.279391967:7(1007-1022)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1109/TC.2018.2793919
Maia CYomsi PNogueira LPinho L(2017)Real-time semi-partitioned scheduling of fork-join tasks using work-stealingEURASIP Journal on Embedded Systems10.1186/s13639-017-0079-52017:1Online publication date: 13-Sep-2017
https://doi.org/10.1186/s13639-017-0079-5
Bonifaci VBrandenburg BDAngelo GMarchetti-Spaccamela A(2016)Multiprocessor Real-Time Scheduling with Hierarchical Processor Affinities2016 28th Euromicro Conference on Real-Time Systems (ECRTS)10.1109/ECRTS.2016.24(237-247)Online publication date: Jul-2016
https://doi.org/10.1109/ECRTS.2016.24
Goossens JGrolleau ECucu-Grosjean L(2016)Periodicity of real-time schedules for dependent periodic tasks on identical multiprocessor platformsReal-Time Systems10.1007/s11241-016-9256-152:6(808-832)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1007/s11241-016-9256-1
Show More Cited By

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