Skip to content

Tasks, dependencies and high-throughput computing

By the end of this introduction, you should be able to describe a task by its inputs and outputs, draw a dependency between two tasks, and identify work that could run concurrently.

Why automate a workflow?

Suppose you need to run the same program for ten parameter choices and then collect the results. You can type each command into a terminal, but you must also remember which runs have finished, where their outputs are and when it is safe to start the collection step.

A workflow makes these relationships explicit. A task is one concrete piece of work, such as running a program for one parameter choice. If task B needs a file produced by task A, then B depends on A. Starting B before A has produced that file cannot give the intended result.

Before choosing software, ask three questions:

  1. What final result do I want?
  2. Which tasks produce it, and what does each task read and write?
  3. Which outputs must exist before another task can begin?

HTC and HPC

High-throughput computing (HTC) emphasizes completing a large amount of computational work over time. A common example is a collection of independent runs for different inputs or parameters. High-performance computing (HPC) often emphasizes reducing the time required for a demanding calculation, for example by using many communicating processes. These are useful emphases, not mutually exclusive kinds of machines: an HTC workflow can run on an HPC cluster, and one task in a workflow can itself be a parallel program. HTCondor's introduction to HTC discusses the throughput perspective.

Our starting point is simpler: several tasks can run independently, each using a small amount of resources. We first need to expose that independence. Adding more cores does not remove a dependency between tasks.

A small example

In SnakeMake.intro, app.py waits for three seconds and prints one random integer between 0 and 99. We will eventually run it ten times and save each result separately. The delay makes overlapping execution easy to observe; it does not model a CPU-intensive calculation.

Each invocation can finish without reading the output of another invocation. They are independent for scheduling purposes, provided they write to separate files. This does not make a claim about the statistical independence of random-number streams.

For the following diagram, imagine three such invocations and an additional task that collects all three outputs into a table. The collection step is a teaching extension used to illustrate a dependency; it is not a script supplied in the intro repository.

run A → result A ─┐
run B → result B ─┼→ collect results → table
run C → result C ─┘

Runs A, B and C may overlap if resources permit. Collection must wait for all three results. The arrows mean “produces data needed by”, not “appears earlier in a script”.

What Snakemake describes

Snakemake describes how to produce files using rules. A rule identifies inputs, outputs and the operation that connects them. A job is a concrete application of a rule to particular files. A workflow definition is usually stored in a file called Snakefile. Starting from requested output files, Snakemake can identify the jobs and dependencies needed to produce them. See the official introductory tutorial.

For a fixed set of jobs, we can draw these dependencies as a directed acyclic graph (DAG):

  • directed: each arrow points from a prerequisite to work that needs it;
  • acyclic: the arrows do not form a loop in which tasks must wait for one another indefinitely.

Independent branches can run concurrently within the available resources. Later, we will distinguish this workflow-level decision from the cluster scheduler's job of allocating resources. We will also distinguish running several tasks concurrently from parallelizing the program inside a single task.

From a small example to a scientific analysis

The second repository, SnakeMake.main, has three stages: fit correlation-function data, collect selected energy results, and fit and plot a dispersion relation. You do not need the physics yet. For now, identify the interfaces: which files leave one stage and enter the next?

This is the same design process as in the small example:

  1. Define the objective.
  2. Identify the tasks.
  3. Determine their dependencies.
  4. Specify the input and output files.
  5. Draw the workflow.
  6. Test a small case and inspect the result.
  7. Run the intended workload.

Automation supports repeatable execution, but checking that a workflow finishes is different from checking its scientific conclusions. Data, software versions, parameters and random-number settings also matter for reproducibility. Mölder et al. discuss reproducibility, adaptability and transparency in Sustainable data analysis with Snakemake, version 2 (2021).

Continue with installation, then test your understanding with the exercises.