Optimal Scheduling of Periodic Gang Tasks

Joël Goossens, Pascal Richard

Abstract


The gang scheduling of parallel implicit-deadline periodic task systems upon identical multiprocessor platforms is considered. In this scheduling problem, parallel tasks use several processors simultaneously. We propose two DPFAIR (deadline partitioning) algorithms that schedule all jobs in every interval of time delimited by two subsequent deadlines. These algorithms define a static schedule pattern that is stretched at run-time in every interval of the DPFAIR schedule. The first algorithm is based on linear programming and is the first one to be proved  optimal for the considered gang scheduling problem. Furthermore, it runs in polynomial time for a fixed number m of processors and an efficient implementation is fully detailed. The second algorithm is an approximation algorithm based on a fixed-priority rule that is competitive under resource augmentation analysis in order to compute an optimal schedule pattern. Precisely, its speedup factor is bounded by (2-1/m). Both algorithms are also evaluated through intensive numerical experiments.

Keywords


Real-time systems; Scheduling; Parallel tasks

Full Text:

PDF

References


Björn Andersson and Dionisio de Niz. Analyzing global-edf for multiprocessor scheduling of parallel tasks. In Roberto Baldoni, Paola Flocchini, and Binoy Ravindran, editors, Principles of Distributed Systems, 16th International Conference, OPODIS 2012, Rome, Italy, December 18-20, 2012. Proceedings, volume 7702 of Lecture Notes in Computer Science, pages 16–30. Springer, 2012. doi: 10.1007/978-3-642-35476-2_2.

Sanjoy K. Baruah, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Leen Stougie, and Andreas Wiese. A generalized parallel task model for recurrent real-time processes. In Proceedings of the 33rd IEEE Real-Time Systems Symposium, RTSS 2012, San Juan, PR, USA, December 4-7, 2012, pages 63–72. IEEE Computer Society, 2012. doi: 10.1109/RTSS.2012.59.

Sanjoy K. Baruah, N. K. Cohen, C. Greg Plaxton, and Donald A. Varvel. Proportionate progress: A notion of fairness in resource allocation. Algorithmica, 15(6):600–625, 1996. doi:10.1007/BF01940883.

V. Berten, P. Courbin, and J. Goossens. Gang fixed priority scheduling of periodic moldable real-time tasks. In 5th Junior Researcher Workshop on Real-Time Computing, pages 9–12, 2011. URL: http://arxiv.org/abs/0805.3237.

Jacek Blazewicz, Mieczyslaw Drabowski, and Jan Weglarz. Scheduling multiprocessor tasks to minimize schedule length. IEEE Trans. Computers, 35(5):389–393, 1986. doi:10.1109/TC.1986.1676781.

Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Sebastian Stiller, and Andreas Wiese. Feasibility analysis in the sporadic DAG task model. In 25th Euromicro Conference on Real-Time Systems, ECRTS 2013, Paris, France, July 9-12, 2013, pages 225–233. IEEE Computer Society, 2013. doi:10.1109/ECRTS.2013.32.

Rajkumar Buyya. High Performance Cluster Computing: Architectures and Systems, chapter Scheduling Parallel Jobs on Clusters, pages 519–533. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1999.

Robit Chandra, Leonardo Dagum, Dave Kohr, Dror Maydan, Jeff McDonald, and Ramesh Menon. Paral lel programming in OpenMP. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2001. URL: http://dl.acm.org/citation.cfm?id=355074.

Rohit Chandra, D Leonaldo, Kohr Dave, Maydan Dror, M Jeff, and Menon Ramesh. Parallel programming in OpenMP. Morgan Kaufmann, 2001. URL: http://lib.mdp.ac.id/ebook/Karya%20Umum/Parallel_Programming_in_OpenMP.pdf.

Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen. An optimal real-time scheduling algorithm for multiprocessors. In Proceedings of the 27th IEEE Real-Time Systems Symposium (RTSS 2006), 5-8 December 2006, Rio de Janeiro, Brazil, pages 101–110. IEEE Computer Society, 2006. doi:10.1109/RTSS.2006.10.

Sébastien Collette, Liliana Cucu, and Joël Goossens. Integrating job parallelism in real-time scheduling theory. Inf. Process. Lett., 106(5):180– 187, 2008. doi:10.1016/j.ipl.2007.11.014.

Pierre Courbin, Irina Iulia Lupu, and Joël Goossens. Scheduling of hard real-time multiphase multi-thread (MPMT) periodic tasks. Real-Time Systems, 49(2):239–266, 2013. doi:10.1007/s11241-012-9173-x.

Robert I. Davis and Alan Burns. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv., 43(4):35, 2011. doi:10.1145/1978802.1978814.

M. Drozdowski. Handbook of Scheduling Algorithms, Models and Performance Analysis, chapter Scheduling Parallel Tasks — Algorithms and Complexity. Chapman & Hall/CRC, 2004.

Maciej Drozdowsli. On the complexity of multiprocessor task scheduling. Bulletin of the polish academy of sciences, 43(3):381–392, 1995. URL: http://www.cs.put.poznan.pl/mdrozdowski/txt/BullPAS95.pdf.

P.-F. Dutot, G. Mounie, and Denis Trystram.

Handbook of Scheduling Algorithms, Models and Performance Analysis, chapter Scheduling Parallel Tasks — Approximation Algorithms. Chapman & Hall/CRC, 2004.

P. Emberson, R. Stafford, and R.I. Davis. Techniques for the synthesis of multiprocessor task sets. In In proceedings 1st International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS 2010), pages 6–11, 2010. URL: http://retis.sssup.it/waters2010/waters2010.pdf.

Kenji Funaoka, Shinpei Kato, and Nobuyuki Yamasaki. Work-conserving optimal real-time scheduling on multiprocessors. In 20th Euromicro Conference on Real-Time Systems, ECRTS 2008, 2-4 July 2008, Prague, Czech Republic, Proceedings, pages 13–22. IEEE Computer Society, 2008. doi:10.1109/ECRTS.2008.15.

Shelby Funk. LRE-TL: an optimal multiprocessor algorithm for sporadic task sets with unconstrained deadlines. Real-Time Systems, 46(3):332– 359, 2010. doi:10.1007/s11241-010-9109-2.

Shelby Funk, Greg Levin, Caitlin Sadowski, Ian Pye, and Scott A. Brandt. Dp-fair: a unifying theory for optimal hard real-time multiprocessor scheduling. Real-Time Systems, 47(5):389–429, 2011. doi:10.1007/s11241-011-9130-0.

Shelby Funk and Vijaykant Nanadur. LRE-TL: An optimal multiprocessor scheduling algorithm for sporadic task sets. In 17th International Conference on Real-Time and Network Systems, pages 159–168, 2009. URL: https://hal.inria.fr/inria-00442002/document.

M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.

A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, and V. Sunderam. PVM: Parallel Virtual Machine A Users’ Guide and Tutorial for Networked Paral lel Computing. MIT Press, 1994. URL: http://www.netlib.org/pvm3/book/pvm-book.html.

Joël Goossens and Pascal Richard. Real-time Systems Scheduling, volume Fundamentals, chapter Multiprocessor Architecture Solutions. Wiley-ISTE, September 2014. URL: http://eu.wiley.com/WileyCDA/WileyTitle/productCd-1848216653.html.

Joël Goossens and Vandy Berten. Gang FTP scheduling of periodic and parallel rigid real-time tasks. CoRR, abs/1006.2617, 2010. URL: http://arxiv.org/abs/1006.2617.

Sergei Gorlatch and Holger Bischof. A generic MPI implementation for a data-parallel skeleton: Formal derivation and application to FFT. Parallel Processing Letters, 8(4):447–458, 1998. doi:10.1142/S0129626498000456.

R L Graham. Bounds for certain multiprocessing anomalies. Bel l System Technical Journal, 45:416– 426, 1966. URL: http://www.jstor.org/stable/ 2099572.

William Gropp, Ewing Lusk, and Anthony Skjellum. Using MPI: portable paral lel programming with the message-passing interface. Cambridge, MIT Press, 2nd edition, 1999. URL: http://mitpress.mit.edu/books/using-mpi.

Berit Johannes. Scheduling parallel jobs to minimize the makespan. J. Scheduling, 9(5):433–452, 2006. doi:10.1007/s10951-006-8497-6.

Shinpei Kato and Yutaka Ishikawa. Gang EDF scheduling of parallel task systems. In Theodore P. Baker, editor, Proceedings of the 30th IEEE Real-

Time Systems Symposium, RTSS 2009, Washington, DC, USA, 1-4 December 2009, pages 459–468. IEEE Computer Society, 2009. doi:10.1109/RTSS.2009.42.

Leonid G Khachiyan. Polynomial algorithms in linear programming. USSR Computational Mathematics and Mathematical Physics, 20(1):53–72, 1980. URL: http://www.sciencedirect.com/science/article/pii/0041555380900610.

Karthik Lakshmanan, Shinpei Kato, and Ragunathan Rajkumar. Scheduling parallel real-time

tasks on multi-core processors. In Proceedings of the 31st IEEE Real-Time Systems Symposium, RTSS 2010, San Diego, California, USA, November 30 - December 3, 2010, pages 259–268. IEEE Computer Society, 2010. doi:10.1109/RTSS.2010.42.

Greg Levin, Shelby Funk, Caitlin Sadowski, Ian Pye, and Scott A. Brandt. DP-FAIR: A simple model for understanding optimal multiprocessor scheduling. In 22nd Euromicro Conference on Real-Time Systems, ECRTS 2010, Brussels, Belgium, July 6-9, 2010, pages 3–13. IEEE Computer Society, 2010. doi:10.1109/ECRTS.2010.34.

Jing Li, Kunal Agrawal, Chenyang Lu, and Christopher D. Gill. Outstanding paper award: Analysis of global EDF for parallel tasks. In 25th Euromicro Conference on Real-Time Systems, ECRTS 2013, Paris, France, July 9-12, 2013, pages 3–13. IEEE Computer Society, 2013. doi:10.1109/ECRTS.2013.12.

C. L. Liu and James W. Layland. Scheduling algorithms for multiprogramming in a hard-realtime environment. J. ACM, 20(1):46–61, 1973. doi:10.1145/321738.321743.

Cláudio Maia, Marko Bertogna, Luís Nogueira, and Luís Miguel Pinho. Response-time analysis of synchronous parallel tasks in multiprocessor systems. In Mathieu Jan, Belgacem Ben Hedia, Joël Goossens, and Claire Maiza, editors, 22nd International Conference on Real-Time Networks and Systems, RTNS ’14, Versaille, France, October 8-10, 2014, page 3. ACM, 2014. doi:10.1145/2659787.2659815.

R McNaughton. Scheduling with deadlines and loss functions. Management Science, 6(1), 1959. URL: http://www.jstor.org/stable/2627472.

Geoffrey Nelissen, Vandy Berten, Joël Goossens, and Dragomir Milojevic. Techniques optimizing the number of processors to schedule multi- threaded tasks. In Robert Davis, editor, 24th Euromicro Conference on Real-Time Systems, ECRTS 2012, Pisa, Italy, July 11-13, 2012, pages 321–330. IEEE Computer Society, 2012. doi:10. 1109/ECRTS.2012.37.

Abusayeed Saifullah, Kunal Agrawal, Chenyang Lu, and Christopher D. Gill. Multi-core real-time scheduling for generalized parallel task models. In Proceedings of the 32nd IEEE Real-Time Systems Symposium, RTSS 2011, Vienna, Austria, November 29 - December 2, 2011, pages 217–226. IEEE Computer Society, 2011. doi:10.1109/RTSS.2011.27.

Vaidy S. Sunderam. PVM: A framework for parallel distributed computing. Concurrency - Practice and Experience, 2(4):315–339, 1990. doi:10.1002/ cpe.4330020404.

David W Walker and Jack J Dongarra. MPI: a standard message passing interface. Supercomputer, 12:56–68, 1996.

Dakai Zhu, Daniel Mossé, and Rami G. Melhem. Multiple-resource periodic scheduling problem: how much fairness is necessary? In Proceedings of the 24th IEEE Real-Time Systems Symposium (RTSS 2003), 3-5 December 2003, Cancun, Mexico, pages 142–151. IEEE Computer Society, 2003. doi:10.1109/REAL.2003.1253262.




DOI: http://dx.doi.org/10.4230/LITES-v003-i001-a004

URN (PDF): http://nbn-resolving.de/urn:nbn:de:0030-lites-v003-i001-a004-pdf3



Copyright (c) 2016 Joël Goossens and Pascal Richard

Creative Commons License CC BY
This work is licensed under a Creative Commons Attribution 3.0 Germany License (CC BY 3.0 DE).

License URL: http://creativecommons.org/licenses/by/3.0/de/deed.en

Published by the European Design and Automation Association (EDAA) \ EMbedded Systems Special Interest Group (EMSIG) and Schloss Dagstuhl -- Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing.