2024/03/11 by Jared Coleman, Bhaskar Krishnamachari, Coleman, Jared +1 · 1 citation
Computer Science · Engineering · #Cloud Computing and Resource Management #Distributed #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #Scheduling and Optimization Algorithms #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2403.07120
openalex publication_date 2024/03/11 · openalex created_date 2024/03/14 · openalex updated_date 2026/07/28
Scheduling a task graph representing an application over a heterogeneous network of computers is a fundamental problem in distributed computing. It is known to be not only NP-hard but also not polynomial-time approximable within a constant factor. As a result, many heuristic algorithms have been proposed over the past few decades. Yet it remains largely unclear how these algorithms compare to each other in terms of the quality of schedules they produce. We identify gaps in the traditional benchmarking approach to comparing task scheduling algorithms and propose a simulated annealing-based adversarial analysis approach called PISA to help address them. We also introduce SAGA, a new open-source library for comparing task scheduling algorithms. We use SAGA to benchmark 15 algorithms on 16 datasets and PISA to compare the algorithms in a pairwise manner. Algorithms that appear to perform similarly on benchmarking datasets are shown to perform very differently on adversarially chosen problem instances. Interestingly, the results indicate that this is true even when the adversarial search is constrained to selecting among well-structured, application-specific problem instances. This work represents an important step towards a more general understanding of the performance boundaries between task scheduling algorithms on different families of problem instances.