Document Open Access Logo

Response-Time Analysis for Non-Preemptive Periodic Moldable Gang Tasks

Authors Geoffrey Nelissen , Joan Marcè i Igual , Mitra Nasri

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2022.12.pdf
  • Filesize: 2.62 MB
  • 22 pages

Document Identifiers

Author Details

Geoffrey Nelissen
  • Eindhoven University of Technology, The Netherlands
Joan Marcè i Igual
  • Eindhoven University of Technology, The Netherlands
Mitra Nasri
  • Eindhoven University of Technology, The Netherlands

Funding

  • Marcè i Igual, Joan: This work was made with the support of the NWO SAM-FMS project (project number 17931) as a part of the MASCOT program.
  • Nasri, Mitra: This work was made with the support of the EU ECSEL Joint Undertaking under grant agreement no 101007260 (project TRANSACT).

Cite As Get BibTex

Geoffrey Nelissen, Joan Marcè i Igual, and Mitra Nasri. Response-Time Analysis for Non-Preemptive Periodic Moldable Gang Tasks. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ECRTS.2022.12

Abstract

Gang scheduling has long been adopted by the high-performance computing community as a way to reduce the synchronization overhead between related threads. It allows for several threads to execute in lock steps without suffering from long busy-wait periods or be penalized by large context-switch overheads. When combined with non-preemptive execution, gang scheduling significantly reduces the execution time of threads that work on the same data by decreasing the number of memory transactions required to load or store the data. In this work, we focus on two main types of gang tasks: rigid and moldable. A moldable gang task has a presumed known minimum and maximum number of cores on which it can be executed at runtime, while a rigid gang task always executes on the same number of cores. This work presents the first response-time analysis for non-preemptive moldable gang tasks. Our analysis is based on the notion of schedule abstraction; a new approach for response-time analysis with the promise of high accuracy. Our experiments on periodic rigid gang tasks show that our analysis is 4.9 times more successful in identifying schedulable tasks than the existing utilization-based test for rigid gang tasks.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
Keywords
  • schedulability analysis
  • response time analysis
  • moldable gang tasks
  • rigid gang tasks
  • schedule abstraction graph
  • multiprocessor
  • non-preemptive

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Benny Akesson, Mitra Nasri, Geoffrey Nelissen, Sebastian Altmeyer, and Robert I. Davis. An empirical survey-based study into industry practice in real-time systems. In IEEE Real-Time Systems Symposium (RTSS), pages 1-9, 2020. Google Scholar
  2. Tanya Amert, Nathan Otterness, Ming Yang, James H. Anderson, and F. Donelson Smith. GPU Scheduling on the NVIDIA TX2: Hidden Details Revealed. In IEEE Real-Time Systems Symposium (RTSS), pages 104-115, 2017. Google Scholar
  3. Neil Audsley, Alan Burns, Mike Richardson, Ken Tindell, and Andy J. Wellings. Applying new scheduling theory to static priority preemptive scheduling. Software Engineering Journal, 8(5):284-292, 1993. Google Scholar
  4. Vandy Berten, Pierre Courbin, and Joël Goossens. Gang fixed priority scheduling of periodic moldable real-time tasks. In Junior Researcher Workshopon Real-Time Computing (JRWRTC), pages 9-12, 2011. Google Scholar
  5. A. Biondi, A. Balsini, M. Pagani, E. Rossi, M. Marinoni, and G. Buttazzo. A Framework for Supporting Real-Time Applications on Dynamic Reconfigurable FPGAs. In IEEE Real-Time Systems Symposium (RTSS), pages 1-12, 2016. Google Scholar
  6. Jacek Blazewicz, Mieczyslaw Drabowski, and Jan Weglarz. Scheduling Multiprocessor Tasks to Minimize Schedule Length. IEEE Transactions on Computers, c-35(5):389-393, 1986. Google Scholar
  7. Felipe Cerqueira, Geoffrey Nelissen, and Björn B Brandenburg. On strong and weak sustainability, with an application to self-suspending real-time tasks. In Euromicro Conference on Real-Time Systems (ECRTS), pages 26-1, 2018. Google Scholar
  8. Sébastien Collette, Liliana Cucu, and Joël Goossens. Integrating job parallelism in real-time scheduling theory. Information Processing Letters, 106(5):180-187, 2008. Google Scholar
  9. Zheng Dong and Cong Liu. Analysis techniques for supporting hard real-time sporadic gang task systems. Real-Time Systems, 55(3):641-666, 2019. Google Scholar
  10. Zheng Dong and Cong Liu. Work-in-progress: Non-preemptive scheduling of sporadic gang tasks on multiprocessors. In Work-in-Progress of IEEE Real-Time Systems Symposium (WiP-RTSS), pages 512-515. IEEE, 2019. Google Scholar
  11. Dror G. Feitelson. Packing schemes for gang scheduling. In Job Scheduling Strategies for Parallel Processing (JSSPP), pages 89-110, 1996. Google Scholar
  12. Dror G. Feitelson and Larry Rudolph. Gang scheduling performance benefits for fine-grain synchronization. Journal of Parallel and Distributed Computing, 16(4):306-318, 1992. Google Scholar
  13. Joël Goossens and Vandy Berten. Gang FTP scheduling of periodic and parallel rigid real-time tasks. In International Conference on Real-Time Networks and Systems (RTNS), pages 189-196, 2010. Google Scholar
  14. Joël Goossens, Emmanuel Grolleau, and Liliana Cucu-Grosjean. Periodicity of real-time schedules for dependent periodic tasks on identical multiprocessor platforms. Real-Time Systems, 52(6):808-832, 2016. Google Scholar
  15. Joël Goossens and Pascal Richard. Optimal scheduling of periodic gang tasks. Leibniz transactions on embedded systems, 3(1):4:1-4:18, 2016. Google Scholar
  16. Shinpei Kato and Yutaka Ishikawa. Gang EDF scheduling of parallel task systems. In IEEE Real-Time Systems Symposium (RTSS), pages 459-468, 2009. Google Scholar
  17. Konstantinos Koiliaris and Chao Xu. Faster Pseudopolynomial Time Algorithms for Subset Sum. ACM Transactions on Algorithms, 15(3):1062-1072, 2019. Google Scholar
  18. Mitra Nasri and Björn B. Brandenburg. An exact and sustainable analysis of non-preemptive scheduling. In IEEE Real-Time Systems Symposium (RTSS), pages 1-12, 2017. Google Scholar
  19. Mitra Nasri, Nelissen Geoffrey, and Björn B. Brandenburg. Response-Time Analysis of Limited-Preemptive Parallel DAG Tasks Under Global Scheduling. In Euromicro Conference on Real-Time Systems (ECRTS), volume 133, pages 21:1-21:23, 2019. Google Scholar
  20. Mitra Nasri, Geoffrey Nelissen, and Björn B. Brandenburg. A Response-Time Analysis for Non-Preemptive Job Sets under Global Scheduling. In Euromicro Conference on Real-Time Systems (ECRTS), volume 106, pages 9:1-9:23, 2018. Google Scholar
  21. Saranya Natarajan, Mitra Nasri, David Broman, Björn B. Brandenburg, and Geoffrey Nelissen. From code to weakly hard constraints: A pragmatic end-to-end toolchain for timed C. In IEEE Real-Time Systems Symposium (RTSS), pages 167-180, 2019. Google Scholar
  22. Suhail Nogd, Geoffrey Nelissen, Mitra Nasri, and Björn B. Brandenburg. Response-Time Analysis for Non-Preemptive Global Scheduling with FIFO Spin Locks. In IEEE Real-Time Systems Symposium (RTSS), pages 115-127, 2020. Google Scholar
  23. John K. Ousterhout. Scheduling Techniques for Concurrent Systems. In International Conference on Distributed Computing Systems (ICDCS), pages 22-30, 1982. Google Scholar
  24. Sayra Ranjha, Mitra Nasri, and Geoffrey Nelissen. Work-in-progress: Partial-order reduction in reachability-based response-time analyses. In 2021 IEEE Real-Time Systems Symposium (RTSS), pages 544-547, 2021. Google Scholar
  25. Sayra Ranjha, Geoffrey Nelissen, and Mitra Nasri. Partial-order reduction for schedule-abstraction-based response-time analyses of non-preemptive tasks. In IEEE 28th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 121-132, 2022. Google Scholar
  26. Pascal Richard, Joël Goossens, and Shinpei Kato. Comments on "Gang EDF Schedulability Analysis", 2017. URL: http://arxiv.org/abs/1705.05798.
  27. Maria A. Serrano, Alessandra Melani, Sebastian Kehr, Marko Bertogna, and Eduardo Quiñones. An analysis of lazy and eager limited preemption approaches under DAG-based global fixed priority scheduling. In IEEE International Symposium on Real-Time Distributed Computing (ISORC), pages 193-202, 2017. Google Scholar
  28. Srinidhi Srinivasan, Geoffrey Nelissen, and Reinder J. Bril. Work-in-progress: Analysis of tsn time-aware shapers using schedule abstraction graphs. In Real-Time Systems Symposium (RTSS), pages 508-511, 2021. Google Scholar
  29. Roger Stafford. Random vectors with fixed sum. Technical report, University of Oxford, 2006. URL: http://www.mathworks.com/matlabcentral/fileexchange/9700.
  30. Saud Wasly and Rodolfo Pellizzoni. Bundled scheduling of parallel real-time tasks. In IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 130-142, 2019. Google Scholar
  31. Beyazit Yalcinkaya, Mitra Nasri, and Björn B. Brandenburg. An exact schedulability test for non-preemptive self-suspending real-time tasks. In IEEE/ACM Design, Automation and Test in Europe (DATE), pages 1222-1227, 2019. Google Scholar
  32. Yanyong Zhang, H. Franke, J. Moreira, and A. Sivasubramaniam. An integrated approach to parallel scheduling using gang-scheduling, backfilling, and migration. IEEE Transactions on Parallel and Distributed Systems, 14(3):236-247, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact