Task Graph Scheduling Eval

---
name: task-graph-scheduling-eval
description: Evaluates task graph scheduling algorithms by measuring their makespan on standard and adversarially modified network topologies. It probes how well algorithms minimize execution time across heterogeneous datasets and reveals performance reversals under minor structural changes. Use when the user wants to benchmark on Parallel Chains (and 15 other SAGA framework datasets), or asks about evaluating this task. Reports makespan.
metadata:
  skill_kind: dataset_eval
  source_arxiv: 2403.07120
  bibtex_key: coleman2024pisa
  confidence: medium
---

# task-graph-scheduling-eval

> PISA: An Adversarial Approach To Comparing Task Graph Scheduling Algorithms — Coleman et al. (2024) (arXiv:2403.07120, 2024)

## What this evaluates

Evaluates task graph scheduling algorithms by measuring their makespan on standard and adversarially modified network topologies. It probes how well algorithms minimize execution time across heterogeneous datasets and reveals performance reversals under minor structural changes.

## Datasets

- **Parallel Chains (and 15 other SAGA framework datasets)** — total ?; splits: test (-1)

## Metrics

- `makespan` **(primary)** — range: other
  - The total time required to complete all tasks in the directed acyclic graph given a specific schedule and network topology. Often reported as a ratio relative to a baseline or optimal makespan for cross-algorithm comparison.

## Input / output format

**Input**: A directed acyclic task graph with computation/communication weights, paired with a heterogeneous network topology specifying node processing speeds and link bandwidths.

**Output**: A schedule mapping each task to a processing node over time, or the scalar makespan value resulting from that schedule.

## Scoring recipe

```python
def compute_makespan(schedule, task_graph):
    finish_times = {}
    for task in task_graph.topological_order:
        dep_finish = max(finish_times.get(dep, 0) for dep in task.dependencies)
        node = schedule[task]
        start = dep_finish
        duration = task.computation_cost / node.speed
        finish_times[task] = start + duration
    return max(finish_times.values())
```

## Common pitfalls

- Averaging makespan across datasets masks adversarial cases where one algorithm performs orders of magnitude worse than another on specific instances.
- Scaling all node/edge weights uniformly does not preserve performance rankings; minor topological alterations can completely reverse which algorithm is superior.

## Evidence (verbatim from paper)

> Figure 2 shows the results of benchmarking 15 algorithms on 16 datasets. Figure 2. Makespan Ratios of 15 algorithms evaluated on 16 datasets. ... Observe that a structurally equivalent instance of this problem with all node/edge weights scaled so they are between 0 and 1 could have been generated by the Parallel Chains dataset generator in SAGA.

## Citation

```bibtex
@misc{coleman2024pisa,
  title={PISA: An Adversarial Approach To Comparing Task Graph Scheduling Algorithms},
  author={Coleman et al. (2024)},
  year={2024},
  note={arXiv:2403.07120}
}
```

- arXiv: 2403.07120