On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems

Alberto Marchetti-Spaccamela, Nicole Megow, Jens Schloter, Martin Skutella, Leen Stougie

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

63 Downloads (Pure)


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.

Original languageEnglish
Title of host publication2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
Subtitle of host publicationProceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages10
ISBN (Electronic)9781728168760
Publication statusPublished - 14 Jul 2020
Event34th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2020 - New Orleans, United States
Duration: 18 May 202022 May 2020


Conference34th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2020
Country/TerritoryUnited States
CityNew Orleans


Partially funded and supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) Projects ME 3825/1 and 146371743 - TRR 89 Invasive Computing, by the Netherlands Organisation for Scientific Research (NWO) Gravitation Programme Networks 024.002.003, by ERC Advanced Grant 788893 AMDROMA “Algorithmic and Mechanism Design Research in Online Markets” and by MIUR PRIN project ALGADIMAR “Algorithms, Games, and Digital Markets”.

FundersFunder number
Horizon 2020 Framework Programme788893
European Research Council
Deutsche Forschungsgemeinschaft146371743, ME 3825/1
Nederlandse Organisatie voor Wetenschappelijk Onderzoek024.002.003
Ministero dell’Istruzione, dell’Università e della Ricerca


    • complexity
    • conditional DAG
    • makespan
    • parallel processing


    Dive into the research topics of 'On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems'. Together they form a unique fingerprint.

    Cite this