The Paper

PISA: An Adversarial Approach To Comparing Task Graph Scheduling Algorithms

Jared Coleman and Bhaskar Krishnamachari

Loyola Marymount University · University of Southern California

View on arXiv Code on GitHub

Abstract

Scheduling tasks represented as directed acyclic graphs (DAGs) onto heterogeneous networks of processors to minimize the overall execution time (makespan) is a fundamental problem in distributed computing. Many heuristic-based scheduling algorithms have been proposed over the years, each typically evaluated on a limited set of benchmarks. Traditional benchmarking approaches compare algorithms by averaging their performance across problem instances, but this can obscure significant performance variations on specific instances. In this paper, we introduce PISA (Problem Instance Simulated Annealing), a meta-heuristic approach that searches for problem instances on which a given scheduling algorithm performs poorly relative to another. We demonstrate that for every scheduling algorithm evaluated, PISA can find instances where it performs at least 2x worse than another algorithm, and for 10 out of 15 algorithms, instances where they perform 5x or worse. Our results reveal that no single algorithm dominates across all problem instances, highlighting the value of adversarial analysis in understanding algorithm performance boundaries.

Key Findings

  • 1. For every scheduling algorithm, PISA finds instances where it performs at least 2x worse than another algorithm.
  • 2. For 10 of 15 algorithms, PISA finds instances where they perform 5x or worse.
  • 3. Even HEFT (the most popular algorithm) can perform 4.34x worse than FastestNode on adversarial instances.
  • 4. Nearly every pair of algorithms shows bidirectional performance gaps — no single algorithm dominates.
  • 5. In application-specific scenarios, WBA can perform 1000x worse than FastestNode on certain SRASearch workflows.

Citation

@article{coleman2024pisa,
  title={Comparing Task Graph Scheduling Algorithms:
         An Adversarial Approach},
  author={Coleman, Jared and Krishnamachari, Bhaskar},
  journal={arXiv preprint arXiv:2403.07120},
  year={2024}
}

Supported by the Army Research Laboratory, Cooperative Agreement W911NF-17-2-0196 and NSF Award 2451267.