As parallel processing became ubiquitous in modern computing systems, parallel task models have been proposed to describe the structure of parallel applications. The workflow scheduling problem has been studied extensively over past years, focusing on multiprocessor systems and distributed environments (e.g. grids, clusters). In workflow scheduling, applications are modeled as directed acyclic graphs (DAGs). DAGs have also been introduced in the real-time scheduling community to model the execution of multi-threaded programs on a multi-core architecture. The DAG model assumes, in most cases, a fixed DAG structure capturing only straight-line code. Only recently, more general models have been proposed. In particular, the conditional DAG model allows the presence of control structures such as conditional (if-then-else) constructs. While first algorithmic results have been presented for the conditional DAG model, the complexity of schedulability analysis remains wide open. We perform a thorough analysis on the worst-case makespan (latest completion time) of a conditional DAG task under list scheduling (a.k.a. fixed-priority scheduling). We show several hardness results concerning the complexity of the optimization problem on multiple processors, even if the conditional DAG has a well-nested structure. For general conditional DAG tasks, the problem is intractable even on a single processor. Complementing these negative results, we show that certain practice-relevant DAG structures are very well tractable.

On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems / Marchetti Spaccamela, A.; Megow, N.; Schloter, J.; Skutella, M.; Stougie, L.. - (2020), pp. 1061-1070. (Intervento presentato al convegno 34th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2020 tenutosi a New Orleans; USA) [10.1109/IPDPS47924.2020.00112].

On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems

Marchetti Spaccamela A.
;
2020

Abstract

As parallel processing became ubiquitous in modern computing systems, parallel task models have been proposed to describe the structure of parallel applications. The workflow scheduling problem has been studied extensively over past years, focusing on multiprocessor systems and distributed environments (e.g. grids, clusters). In workflow scheduling, applications are modeled as directed acyclic graphs (DAGs). DAGs have also been introduced in the real-time scheduling community to model the execution of multi-threaded programs on a multi-core architecture. The DAG model assumes, in most cases, a fixed DAG structure capturing only straight-line code. Only recently, more general models have been proposed. In particular, the conditional DAG model allows the presence of control structures such as conditional (if-then-else) constructs. While first algorithmic results have been presented for the conditional DAG model, the complexity of schedulability analysis remains wide open. We perform a thorough analysis on the worst-case makespan (latest completion time) of a conditional DAG task under list scheduling (a.k.a. fixed-priority scheduling). We show several hardness results concerning the complexity of the optimization problem on multiple processors, even if the conditional DAG has a well-nested structure. For general conditional DAG tasks, the problem is intractable even on a single processor. Complementing these negative results, we show that certain practice-relevant DAG structures are very well tractable.
2020
34th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2020
complexity; conditional DAG; makespan; parallel processing
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems / Marchetti Spaccamela, A.; Megow, N.; Schloter, J.; Skutella, M.; Stougie, L.. - (2020), pp. 1061-1070. (Intervento presentato al convegno 34th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2020 tenutosi a New Orleans; USA) [10.1109/IPDPS47924.2020.00112].
File allegati a questo prodotto
File Dimensione Formato  
MarchettiSpaccamela_preprint_On-the-Complexity_2020.pdf

accesso aperto

Note: DOI: 10.1109/IPDPS47924.2020.00112
Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 305.12 kB
Formato Adobe PDF
305.12 kB Adobe PDF
MarchettiSpaccamela_On-the-Complexity_2020.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 230.91 kB
Formato Adobe PDF
230.91 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1457114
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 11
social impact