SAGA

SAGA: Scheduling Algorithms Gathered.

Introduction

SAGA – Scheduling Algorithms Gathered – is a Python toolkit/library for designing, comparing, and visualising DAG-based computational workflow-scheduler performance on heterogeneous compute networks (also known as dispersed computing). It ships with a collection of scheduling algorithms, including classic heuristics (HEFT, CPOP), brute-force baselines, SMT-based optimisers, and more, all under one cohesive API.

The algorithms are all implemented in Python using a common interface. Scripts for validating and comparing the performance of the algorithms are also provided.

Prerequisites

Python Version

All components of this repository have been tested with Python 3.11. To ensure compatibility and ease of environment management, we recommend using uv, a fast Python package and project manager.

To create a new virtual environment with Python 3.11 (uv will download Python 3.11 for you if it isn't already installed):

uv venv --python 3.11
source .venv/bin/activate

For more information on managing Python versions with uv, refer to the uv documentation.

Usage

Installation

Local Installation

Clone the repository and install the requirements:

git clone https://github.com/ANRGUSC/saga.git
cd saga
uv pip install -e .

Running the Tests

Unit tests generate random task graphs and networks to verify scheduler correctness. They also check the RandomVariable utilities used for stochastic scheduling.

Locally

You can run the tests using pytest:

pytest ./tests

You may want to skip some of the tests that are too slow. You can do this ddirectly:

pytest ./tests -k "not (branching and (BruteForceScheduler or SMTScheduler))"

or by setting a timeout for the tests:

pytest ./tests --timeout=60

To run a specific test or scheduler-task combination, use the -k option. For example, to run the HeftScheduler tests on the diamond task graph:

pytest ./tests -k "HeftScheduler and diamond"

Linting and Type Checking

The CI pipeline also runs a linter and type checker. You can run these locally:

# Lint with ruff
ruff check src/saga

# Check formatting with ruff
ruff format --check src/saga

# Type check with mypy
mypy src/saga --ignore-missing-imports

To auto-fix lint issues or reformat code:

ruff check src/saga --fix
ruff format src/saga

Running the Algorithms

The algorithms are implemented as Python modules. The following example shows how to run the HEFT algorithm on a workflow:

from saga.schedulers import HeftScheduler

scheduler = HeftScheduler()
network: Network = ...
task_graph: TaskGraph = ...
scheduler.schedule(network, task_graph)

Examples

The repository contains several example scripts illustrating different algorithms and scenarios. You can find them under scripts/examples. To run an example, use:

python scripts/examples/<example_name>/main.py

The table of contents in scripts/examples/Readme.md lists examples ranging from basic usage to dynamic networks and scheduler comparisons.

Experiments

To reproduce the experiments from papers using SAGA, see the experiments directory.

Reference

A research paper that goes with this repo and that contains useful details is available online at ArXiV.

Acknowledgements

This work was supported in part by Army Research Laboratory under Cooperative Agreement W911NF-17-2-0196.

This material is based upon work supported by the National Science Foundation under Award No. 2451267.