Document Open Access Logo

Feasibility Analysis of Conditional DAG Tasks

Authors Sanjoy Baruah, Alberto Marchetti-Spaccamela

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2021.12.pdf
  • Filesize: 0.8 MB
  • 17 pages

Document Identifiers

Author Details

Sanjoy Baruah
  • Washington University in Saint Louis, MO, USA
Alberto Marchetti-Spaccamela
  • La Sapienza University, Rome, Italy

Funding

  • Baruah, Sanjoy: National Science Foundation Grants CNS-1814739 and CPS-1932530.

Cite AsGet BibTex

Sanjoy Baruah and Alberto Marchetti-Spaccamela. Feasibility Analysis of Conditional DAG Tasks. In 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ECRTS.2021.12

Abstract

Feasibility analysis for Conditional DAG tasks (C-DAGs) upon multiprocessor platforms is shown to be complete for the complexity class pspace. It is shown that as a consequence integer linear programming solvers (ILP solvers) are likely to prove inadequate for such analysis. A demarcation is identified between the feasibility-analysis problems on C-DAGs that are efficiently solvable using ILP solvers and those that are not, by characterizing a restricted class of C-DAGs for which feasibility analysis is shown to be efficiently solvable using ILP solvers.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Embedded and cyber-physical systems
  • Software and its engineering → Real-time schedulability
Keywords
  • Multiprocessor feasibility analysis
  • Conditional Directed Acyclic Graphs
  • PSPACE-complete

Metrics

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

References

  1. Clark W. Barrett, Roberto Sebastiani, Sanjit A. Seshia, and Cesare Tinelli. Satisfiability modulo theories. In Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors, Handbook of Satisfiability, volume 185 of Frontiers in Artificial Intelligence and Applications, pages 825-885. IOS Press, 2009. URL: https://doi.org/10.3233/978-1-58603-929-5-825.
  2. Sanjoy Baruah. Feasibility Analysis of Conditional DAG Tasks is co-NP^NP-Hard (Why This Matters). In Proceedings of the Twenty-Ninth International Conference on Real-Time and Network Systems, RTNS '21, New York, NY, USA, 2020. ACM. Google Scholar
  3. Sanjoy Baruah. Scheduling DAGs when processor assignments are specified. In Proceedings of the Twenty-Fifth International Conference on Real-Time and Network Systems, RTNS '20, New York, NY, USA, 2020. ACM. Google Scholar
  4. Sanjoy Baruah, Marko Bertogna, and Giorgio Buttazzo. Multiprocessor Scheduling for Real-Time Systems. Springer Publishing Company, Incorporated, 2015. Google Scholar
  5. Sanjoy Baruah, Vincenzo Bonifaci, Renato Bruni, and Alberto Marchetti-Spaccamela. Ilp-based approaches to partitioning recurrent workloads upon heterogeneous multiprocessors. In Proceedings of the 2016 28th EuroMicro Conference on Real-Time Systems, ECRTS '16, Toulouse (France), 2016. IEEE Computer Society Press. Google Scholar
  6. Sanjoy Baruah, Vincenzo Bonifaci, and Alberto Marchetti-Spaccamela. The global EDF scheduling of systems of conditional sporadic DAG tasks. In Proceedings of the 2014 26th Euromicro Conference on Real-Time Systems, ECRTS '15, pages 222-231, Lund (Sweden), 2015. IEEE Computer Society Press. Google Scholar
  7. Sanjoy Baruah, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Leem Stougie, and Andreas Wiese. A generalized parallel task model for recurrent real-time processes. In Proceedings of the IEEE Real-Time Systems Symposium, RTSS 2012, pages 63-72, San Juan, Puerto Rico, 2012. Google Scholar
  8. Sanjoy K. Baruah, Vincenzo Bonifaci, Renato Bruni, and Alberto Marchetti-Spaccamela. ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors. Journal of Scheduling, December 2018. URL: https://doi.org/10.1007/s10951-018-0593-x.
  9. Slim Ben-Amor. Multicore Scheduling of Dependent Tasks with Probabilistic Execution Times. PhD thesis, Sorbonne Université, 2021. Google Scholar
  10. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, third edition, 2009. Google Scholar
  11. Jose Fonseca, Vincent Nelis, Gurulingesh Raravi, and Luis Miguel Pinho. A Multi-DAG model for real-time parallel applications with conditional execution. In Proceedings of the ACM/ SIGAPP Symposium on Applied Computing (SAC), Salamanca, Spain, April 2015. ACM Press. Google Scholar
  12. Robert A. Hearn and Erik D. Demaine. Games, puzzles and computation. A K Peters, 2009. Google Scholar
  13. Klaus Jansen. Analysis of scheduling problems with typed task systems. Discrete Applied Mathematics, 52(3):223-232, 1994. Google Scholar
  14. R. Karp. Reducibility among combinatorial problems. In R. Miller and J. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, New York, 1972. Google Scholar
  15. Jing Li, Abusayeed Saifullah, Kunal Agrawal, Christopher Gill, and Chenyang Lu. Analysis of federated and global scheduling for parallel real-time tasks. In Proceedings of the 2012 26th Euromicro Conference on Real-Time Systems, ECRTS '14, Madrid (Spain), 2014. IEEE Computer Society Press. Google Scholar
  16. Y. S. Li and S. Malik. Performance analysis of embedded software using implicit path enumeration. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 16(12):1477-1487, 1997. URL: https://doi.org/10.1109/43.664229.
  17. Alessandra Melani, Marko Bertogna, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, and Giorgio Buttazzo. Response-time analysis of conditional DAG tasks in multiprocessor systems. In Proceedings of the 2014 26th Euromicro Conference on Real-Time Systems, ECRTS '15, pages 222-231, Lund (Sweden), 2015. IEEE Computer Society Press. Google Scholar
  18. L. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3:1-22, 1976. Google Scholar
  19. J. Ullman. NP-complete scheduling problems. Journal of Computer and System Sciences, 10(3):384-393, 1975. Google Scholar
  20. Reinhard Wilhelm. Why AI + ILP Is Good for WCET, but MC Is Not, Nor ILP Alone. In Verification, Model Checking, and Abstract Interpretation, pages 309-322, 2004. URL: https://doi.org/10.1007/978-3-540-24622-0_25.
  21. C. Wrathall. Complete sets and the polynomial-time hierarchy. Theoretical Computer Science, 3:23-33, 1976. Google Scholar
  22. Houssam-Eddine Zahaf, Nicola Capodieci, Roberto Cavicchioli, Marko Bertogna, and Giuseppe Lipari. The HPC-DAG task model for heterogeneous real-time systems. IEEE Transactions on Computers, pages 1-1, 2020. 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 Imprint Privacy Contact