Saga

Saga: Scheduling Algorithms Gathered.

Introduction

This repository contains a collection of scheduling algorithms.
The algorithms are implemented in Python using a common interface.
Scripts for validating and comparing the performance of the algorithms are also provided.

Usage

Installation

Local Installation

Clone the repository and install the requirements:

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

To install additional dependencies like pytest for running tests, run:

pip install pytest pytest-timeout

Some of the algorithms might rely on external solvers, such as Z3. To install Z3 and configure pysmt, use:

pip install pysmt
pysmt-install --z3

Docker Installation

You can also run Saga using Docker. The provided Dockerfile will handle all dependencies, including solvers and testing tools.

1. Build the Docker image:

   docker build -t saga-schedulers .

2. Run the image:

   docker run --rm saga-schedulers

By default, the Docker image will run the tests when started.

Running the Tests

Locally

You can run the tests using pytest. Make sure you have installed the necessary dependencies, including pytest and pytest-timeout:

pip install pytest pytest-timeout

Then, run the tests:

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"

Using Docker

When running the Docker image, the tests will run automatically. You can also pass specific pytest options when running the Docker container.

For example, to run all tests with a 120-second timeout:

docker run --rm saga-schedulers pytest --timeout=120

Or to run a specific test combination (e.g., HeftScheduler and diamond):

docker run --rm saga-schedulers pytest -k "HeftScheduler and diamond"

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: nx.Graph = ...
task_graph: nx.DiGraph = ...
scheduler.schedule(network, task_graph)

See the examples in the examples directory for more!

Experiments from Papers

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