Task Graph Scheduling Eval

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

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

@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