Kubishi Research Group

Backlinks

  • SAGA - Scheduling Algorithms Gathered
  • Welcome
Home

❯

Publications

❯

Evaluating the Impact of Algorithmic Components on Task Graph Scheduling

Evaluating the Impact of Algorithmic Components on Task Graph Scheduling

  • project-saga
  • distributed-computing
Jared Coleman, Ravi Vivek Agrawal, Ebrahim Hirani, Bhaskar Krishnamachari
JSSPP 2025 - The 28th Workshop on Job Scheduling Strategies for Parallel Processing
June 3, 2025
PDF

Abstract

Scheduling distributed applications modeled as directed, acyclic task graphs to run on heterogeneous compute networks is a fundamental (NP-Hard) problem in distributed computing for which many heuristic algorithms have been proposed over the past decades. Many of these algorithms fall under the list-scheduling paradigm, whereby the algorithm first computes priorities for the tasks and then schedules them greedily to the compute node that minimizes some cost function. Thus, many algorithms differ from each other only in a few key components (e.g., the way they prioritize tasks, their cost functions, where the algorithms consider inserting tasks into a partially complete schedule, etc.). We propose a generalized list-scheduling algorithm that allows mixing and matching different task prioritization and greedy node selection schemes to produce 72 unique algorithms. We benchmark these algorithms on 20 datasets to study the individual and combined effects of different algorithmic components on performance and runtime. We show that while every algorithmic component we consider is well-established in the literature, many of their combinations which have never before been considered are pareto-optimal with respect to average performance and runtime. We also report interesting interactions between algorithmic components and dataset features, suggesting that performance is highly application-dependent.


Created with Quartz v4.5.2 © 2025

  • GitHub
  • Discord Community