Workshops Archive

Adapting Classic List-Scheduling Heuristics for Conditional Task Graphs


Workshop: 21st Workshop on Workflows in Support of Large-Scale Science (WORKS26)

Authors: Gabriel Twigg-Ho (Swinburne University of Technology), Jared Coleman and TainĂ£ Coleman (Loyola Marymount University), and Mohammadali Khodabandehlou and Bhaskar Krishnamachari (University of Southern California)

Abstract: Many scientific and machine-learning workflows are modeled as conditional task graphs (CTGs), in which some branches are chosen at runtime so only one of several alternative sub-graphs executes. Tasks on different branches are mutually exclusive, so a scheduler can overlap them on the same processor. We show that classic list-scheduling heuristics such as HEFT and CPoP can be adapted to CTGs with two small changes: a schedule representation that lets mutually exclusive tasks share a processor, and a priority function that weights each task by its probability of executing. Both are components of the open-source SAGA parametric list scheduler. Exploiting mutual exclusion is the dominant benefit, bringing expected makespan within a few percent of a clairvoyant scheduler. Probability reweighting does not help on generic conditional graphs, but helps decisively when a rare branch contains a heavy task competing with always-executed work for a fast processor, the structure of surrogate-model workflows.


Back to 21st Workshop on Workflows in Support of Large-Scale Science (WORKS26) Archive Listing

Back to Full Workshop Archive Listing