Benchmarking DYTAS against HEFT and Dynamic List DAG scheduling algorithms

Abstract

Efficient task scheduling in high-performance computing (HPC) systems remains a critical challenge, particularly when managing complex scientific workflows modeled as Directed Acyclic Graphs (DAGs). The Heterogeneous Earliest Finish Time (HEFT) algorithm is a well-established static scheduler, and Dynamic List variants are increasingly popular among dynamic schedulers. By contrast, the DYnamic TAsk Scheduler (DYTAS) is frequently referenced, yet reviewing the accessible literature uncovered no broad or systematic benchmark of the original algorithm. This thesis addresses that gap through a large-scale empirical comparison of DYTAS against HEFT and a Dynamic List variant across 548 DAGs and 324 simulated system configurations-including both homogeneous and heterogeneous environments. The study also introduces Proposed-DYTAS, an enhanced version of DYTAS optimized for multicore-aware scheduling.<br /> <br /> Using simulation-based benchmarking within the DSLab framework, each scheduler is evaluated using makespan, schedule length ratio (SLR), speedup, efficiency, and runtime. Statistical analysis reveals that HEFT outperforms all algorithms in heterogeneous systems, while Dynamic List achieves comparable performance in homogeneous systems. Proposed-DYTAS significantly improves upon base DYTAS, particularly in multicore environments, although it does not surpass HEFT or Dynamic List. These findings affirm the importance of empirical validation in scheduler selection and contribute new insights for practitioners optimizing workflows in modern HPC settings.