Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Real-Time Systems

25.05.2023

The shape of a DAG: bounding the response time using long paths

verfasst von: Qingqiang He, Nan Guan, Mingsong Lv, Xu Jiang, Wanli Chang

Erschienen in: Real-Time Systems

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In 1969, Graham developed a well-known response time bound for a DAG task using the total workload and the longest path of the DAG, which has been widely applied to solve many scheduling and analysis problems of DAG-based task systems. This paper presents a new response time bound for a DAG task using the total workload and the lengths of multiple long paths of the DAG, instead of the longest path in Graham’s bound. Our new bound theoretically dominates and empirically outperforms Graham’s bound. Based on the insight of the new bound, we propose a new task model called the multi-path model, which intuitively describes the shape of a DAG task. We further extend the proposed approach to multi-task systems using the new task model under both federated scheduling and global scheduling. Our schedulability test theoretically dominates federated scheduling and significantly outperforms the state-of-the-art.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
In a box plot, the middle line of the box indicates the median of data. The bottom and top edges of the box represent the 25th and 75th percentiles, respectively. The whiskers extending from the box show the range of data. And the outliers are plotted individually using the ’+’ symbol.
 
Literatur
Agrawal K, Baruah S (2018) A measurement-based model for parallel real-time tasks. In: 30th Euromicro Conference on Real-Time Systems (ECRTS 2018), Schloss Dagstuhl–Leibniz–Zentrum fuer Informatik
Baruah S (2007) Techniques for multiprocessor global schedulability analysis. In: 28th IEEE international real-time systems symposium (RTSS), IEEE, pp 119–128
Baruah S (2014) Improved multiprocessor global schedulability analysis of sporadic DAG task systems. In: 2014 26th Euromicro conference on real-time systems, IEEE, pp 97–105
Baruah S (2015a) The federated scheduling of constrained-deadline sporadic DAG task systems. In: 2015 design, automation & test in Europe conference & Exhibition (DATE), IEEE, pp 1323–1328
Baruah S (2015b) Federated scheduling of sporadic DAG task systems. In: 2015 IEEE international parallel and distributed processing symposium, IEEE, pp 179–186
Baruah S (2015c) The federated scheduling of systems of conditional sporadic DAG tasks. In: Proceedings of the 12th international conference on embedded software, IEEE Press, pp 1–10
Baruah S, Fisher N (2005) The partitioned multiprocessor scheduling of sporadic task systems. In: 26th IEEE international real-time systems symposium (RTSS), IEEE, pp 9
Bi R, He Q, Sun J, et al (2022) Response time analysis for prioritized DAG task with mutually exclusive vertices. In: 2022 IEEE real-time systems symposium (RTSS), IEEE, pp 460–473
Bonifaci V, Marchetti-Spaccamela A, Stiller S, et al (2013) Feasibility analysis in the sporadic DAG task model. In: 2013 25th Euromicro conference on real-time systems, IEEE, pp 225–233
Casini D, Biondi A, Nelissen G, et al (2018) Partitioned fixed-priority scheduling of parallel tasks without preemptions. In: 2018 IEEE real-time systems symposium (RTSS), IEEE, pp 421–433
Chen P, Liu W, Jiang X et al (2019) Timing-anomaly free dynamic scheduling of conditional DAG tasks on multi-core systems. ACM Trans Embed Comput Syst (TECS) 18(5s):1–19
Cordeiro D, Mounié G, Perarnau S, et al (2010) Random graph generation for scheduling simulations. In: Proceedings of the 3rd international ICST conference on simulation tools and techniques, ICST, p 60
Dong Z, Liu C (2017) Analysis techniques for supporting hard real-time sporadic gang task systems. In: 2017 IEEE real-time systems symposium (RTSS), IEEE, pp 128–138
Fonseca J, Nelissen G, Nélis V (2017) Improved response time analysis of sporadic DAG tasks for global FP scheduling. In: Proceedings of the 25th international conference on real-time networks and systems, pp 28–37
Fonseca J, Nelissen G, Nélis V (2019) Schedulability analysis of DAG tasks with arbitrary deadlines under global fixed-priority scheduling. Real-Time Syst 55(2):387–432CrossRefMATH
Han M, Guan N, Sun J et al (2019) Response time bounds for typed DAG parallel tasks on heterogeneous multi-cores. IEEE Trans Parallel Distrib Syst 30(11):2567–2581CrossRef
He Q, Jiang X, Guan N et al (2019) Intra-task priority assignment in real-time scheduling of DAG tasks on multi-cores. IEEE Trans Parallel Distrib Syst 30(10):2283–2295CrossRef
He Q, Lv M, Guan N (2021) Response time bounds for DAG tasks with arbitrary intra-task priority assignment. In: 33rd Euromicro conference on real-time systems (ECRTS), Schloss Dagstuhl-Leibniz-Zentrum für Informatik
He Q, Guan N, Lv M, et al (2022) Bounding the response time of DAG tasks using long paths. In: 2022 IEEE real-time systems symposium (RTSS), IEEE, pp 474–486
He Q, Guan N, Lv M, et al (2023a) On the degree of parallelism in real-time scheduling of DAG tasks. In: 2023 design, automation & test in Europe conference & exhibition (DATE), IEEE
He Q, Sun J, Guan N, et al (2023b) Real-time scheduling of conditional DAG tasks with intra-task priority assignment. IEEE Transactions on computer-aided design of integrated circuits and systems
Jiang X, Long X, Guan N, et al (2016) On the decomposition-based global EDF scheduling of parallel real-time tasks. In: 2016 IEEE real-time systems symposium (RTSS), IEEE, pp 237–246
Jiang X, Guan N, Long X, et al (2017) Semi-federated scheduling of parallel real-time tasks on multiprocessors. In: 2017 IEEE real-time systems symposium (RTSS), IEEE, pp 80–91
Jiang X, Sun J, Tang Y et al (2019) Utilization-tensity bound for real-time DAG tasks under global EDF scheduling. IEEE Trans Comput 69(1):39–50MathSciNetCrossRefMATH
Jiang X, Guan N, Long X et al (2020) Real-time scheduling of parallel tasks with tight deadlines. J Syst Archit 108(101):742
Jiang X, Guan N, Liang H, et al (2021) Virtually-federated scheduling of parallel real-time tasks. In: 2021 IEEE real-time systems symposium (RTSS), IEEE, pp 482–494
Jiang X, Chen Z, Yang M, et al (2022) A unified blocking analysis for parallel tasks with spin locks under global fixed priority scheduling. IEEE transactions on computers
Koike R, Azumi T (2021) Federated scheduling in clustered many-core processors. In: 2021 IEEE/ACM 25th international symposium on distributed simulation and real time applications (DS-RT), IEEE, pp 1–8
Lee S, Lee S, Lee J (2022) Response time analysis for real-time global gang scheduling. In: 2022 IEEE real-time systems symposium (RTSS), IEEE, pp 92–104
Li J, Agrawal K, Lu C, et al (2013) Outstanding paper award: analysis of global EDF for parallel tasks. In: 2013 25th Euromicro conference on real-time systems, IEEE, pp 3–13
Li J, Chen JJ, Agrawal K, et al (2014) Analysis of federated and global scheduling for parallel real-time tasks. In: 2014 26th Euromicro conference on real-time systems, IEEE, pp 85–96
Li J, Agrawal K, Lu C (2022) Parallel real-time scheduling. In: Handbook of real-time computing. Springer, p 447–467
Lin CC, Shi J, Ueter N, et al (2022) Type-aware federated scheduling for typed DAG tasks on heterogeneous multicore platforms. IEEE transactions on computers
Melani A, Bertogna M, Bonifaci V, et al (2015) Response-time analysis of conditional DAG tasks in multiprocessor systems. In: 2015 27th Euromicro conference on real-time systems, IEEE, pp 211–221
Melani A, Bertogna M, Bonifaci V et al (2016) Schedulability analysis of conditional parallel task graphs in multicore systems. IEEE Trans Comput 66(2):339–353MathSciNetMATH
Serrano MA, Melani A, Vargas R, et al (2015) Timing characterization of OpenMP4 tasking model. In: 2015 international conference on compilers, architecture and synthesis for embedded systems (CASES), IEEE, pp 157–166
Sun J, Guan N, Wang Y, et al (2017) Real-time scheduling and analysis of OpenMP task systems with tied tasks. In: 2017 IEEE real-time systems symposium (RTSS), IEEE, pp 92–103
Sun J, Guan N, Sun J, et al (2019) Calculating response-time bounds for OpenMP task systems with conditional branches. In: 2019 IEEE real-time and embedded technology and applications symposium (RTAS), IEEE, pp 169–181
Sun J, Li F, Guan N, et al (2020) On computing exact wcrt for DAG tasks. In: 2020 57th ACM/IEEE design automation conference (DAC), IEEE, pp 1–6
Sun J, Guan N, Guo Z, et al (2021) Calculating worst-case response time bounds for OpenMP programs with loop structures. In: 2021 IEEE real-time systems symposium (RTSS), IEEE, pp 123–135
Tang Y, Guan N, Yi W (2022) Real-time task models. Handbook of real-time computing, p 469
Ueter N, Von Der Brüggen G, Chen JJ, et al (2018) Reservation-based federated scheduling for parallel real-time tasks. In: 2018 IEEE Real-time systems symposium (RTSS), IEEE, pp 482–494
Voudouris P, Stenström P, Pathan R (2017) Timing-anomaly free dynamic scheduling of task-based parallel applications. In: real-time and embedded technology and applications symposium (RTAS), 2017 IEEE, IEEE, pp 365–376
Voudouris P, Stenström P, Pathan R (2021) Bounding the execution time of parallel applications on unrelated multiprocessors. Real-time systems pp 1–44
Wang Y, Guan N, Sun J, et al (2017) Benchmarking OpenMP programs for real-time scheduling. In: 2017 IEEE 23rd international conference on embedded and real-time computing systems and applications (RTCSA), IEEE, pp 1–10
Wang Y, Jiang X, Guan N, et al (2022) Scheduling and analysis of real-time tasks with parallel critical sections. In: Proceedings of the 59th ACM/IEEE design automation conference, pp 1255–1260
Wu Y, Zhang W, Guan N, et al (2021) Improving interference analysis for real-time DAG tasks under partitioned scheduling. IEEE transactions on computers
Zhao S, Dai X, Bate I, et al (2020) DAG scheduling and analysis on multiprocessor systems: Exploitation of parallelism and dependency. In: 2020 IEEE real-time systems symposium (RTSS), IEEE, pp 128–140
Zhao S, Dai X, Bate I (2022) DAG scheduling and analysis on multi-core systems by modelling parallelism and dependency. IEEE transactions on parallel and distributed systems
Metadaten
Titel
The shape of a DAG: bounding the response time using long paths
verfasst von
Qingqiang He
Nan Guan
Mingsong Lv
Xu Jiang
Wanli Chang
Publikationsdatum
25.05.2023
Verlag
Springer US
Erschienen in
Real-Time Systems
Print ISSN: 0922-6443
Elektronische ISSN: 1573-1383
DOI
https://doi.org/10.1007/s11241-023-09397-y

Premium Partner

    Bildnachweise