Dokumentdetails
ID
oai:arXiv.org:2403.07120
Thema
Computer Science - Distributed, Pa...Autor
Coleman, Jared Krishnamachari, BhaskarKategorie
Computer Science
Jahr
2024
Auflistungsdatum
19.06.2024
Schlüsselwörter
approach scheduling taskZusammenfassung
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.
Coleman, Jared,Krishnamachari, Bhaskar, 2024, Comparing Task Graph Scheduling Algorithms: An Adversarial Approach
Configurable Safety Tuning of Language Models with Synthetic Preference Data
data preference cst dpo configurable language safety
Affective flexibility as a developmental building block of cognitive reappraisal: An fMRI study
cognitive success affective flexibility
