Runtime Task Dependency Resolution for Parallel Workflows

34 concepts26 papers1 proposal

When we write software, we naturally think in terms of sequential steps: do step A, then use its output to do step B. When scaling these computations across distributed clusters or heterogeneous hardware, forcing a program into a rigid, step-by-step sequence leaves massive amounts of performance on the table.

To unlock parallelism, developers traditionally had to manually orchestrate threads, manage message queues, or explicitly define a static Directed Acyclic Graph (DAG) of tasks. However, static graphs break down when a program involves complex control flow—such as loops, conditional branches, or execution paths that change based on intermediate data.

The solution is runtime task dependency resolution. Instead of requiring the programmer to map out parallelism beforehand, the system executes code sequentially in appearance, but a runtime layer intercepts operations on the fly. By tracking data requirements as they evolve, the runtime implicitly constructs and updates an execution graph, automatically dispatching tasks the moment their dependencies are satisfied.


Interception and Implicit Graph Construction

How does a system discover what depends on what without explicit instructions? The core mechanism relies on intercepting program execution at key boundaries—such as function calls, JIT compilation, or device command streams—and analyzing data flow.

In high-level scripting languages, this is frequently achieved through asynchronous futures. As demonstrated by Yadu Babuji et al. in Parsl: Scalable Parallel Scripting in Python, when a parallelized function is invoked, the runtime intercepts the call and immediately returns an unresolved "future" object. If a subsequent function takes this future as an argument, the runtime detects the relationship and implicitly logs a directed edge in a dependency graph. This allows the main program to continue executing ahead of the actual computation, mapping out the workflow's structure in real time.

Programmer's View (Sequential Script)
  x = step_A(data)       --> Returns a Future immediately
  y = step_B(x)          --> Detects dependency on x; adds edge to graph

Runtime's View (Dynamic DAG)
  [ step_A ] -----------> [ step_B ]
  (Executes when          (Executes when
   data is ready)          step_A finishes)

This interception can happen at various layers of the software stack depending on the performance goals:

  • Language Annotations: Programmers can explicitly tag function arguments with roles like input or output. As shown by Polyvios Pratikakis et al. in Parallel Programming of General-Purpose Programs Using Task-Based Programming Models, the runtime reads these annotations during execution to construct a dynamic task graph, automating pipeline parallelization without verbose boilerplate.
  • Compiler Interception: In deep learning, architectures are often non-sequential. Ho Young Jhoo et al. demonstrate in Pfeife: Automatic Pipeline Parallelism for PyTorch that just-in-time (JIT) compilation can capture a model's complete data-flow graph at runtime, allowing the system to transparently slice and parallelize execution across multiple GPUs.
  • Hardware and Command Queues: For heterogeneous systems, Eduard Ayguadé et al. show that a runtime layer can intercept task invocations to build a data-flow graph that safely schedules execution and manages memory transfers across multiple GPUs. Similarly, the authors of Exploiting Task Parallelism with OpenCL: A Case Study monitor command streams sent to compute devices to extract task parallelism from standard in-order queues.

Unfolding Data-Dependent Control Flow

The true power of runtime graph construction lies in its ability to handle dynamic control flow. If a workflow contains a loop where the number of iterations depends on a live scientific calculation, a static graph cannot represent it.

By interleaving graph generation with execution, the runtime dynamically "unfolds" the graph. In Wings for Pegasus: Creating Large-Scale Scientific Applications Using Semantic Representations of Computational Workflows, Yolanda Gil et al. describe a paradigm where the system generates and executes a partial workflow, then uses the resulting metadata and intermediate data to dynamically construct the remaining computational graph.

This flexibility allows interactive data science and complex simulations to scale fluidly. Because the graph is built as data is produced, loops and conditionals resolve naturally based on actual runtime values rather than compile-time guesses.


Shifting the Burden to the Dataflow Model

Once a dependency graph is dynamically resolved, execution shifts from a traditional control-flow model to a dataflow model. In a standard program, an instruction pointer dictates what runs next. In a dataflow model, computation is driven entirely by data availability.

As Brunno F. Goldstein et al. explain in Implementing a parallel sparse matrix-vector multiplication using dataflow, tasks execute immediately when their required inputs become available. The runtime environment absorbs the overhead of monitoring these data triggers and allocating computational resources. This decoupling means that independent branches of a graph are executed concurrently across available workers without requiring manual synchronization primitives from the developer.

Furthermore, resolving dependencies at runtime allows the system to adapt to live hardware conditions. For instance, Ziheng Wang et al. demonstrate in Efficient Fault Tolerance for Pipelined Query Engines via Write-ahead Lineage that determining data dependencies and batch sizes at runtime allows distributed query engines to adapt to work stealing and cache states, bypassing the rigid performance trade-offs of static lineage models.

Summary

By shifting graph construction from a static compile-time phase to an active runtime process, modern execution frameworks bridge the gap between human-readable sequential logic and high-performance parallel execution. Whether processing large-scale biological sequences, running deep learning models, or executing linear algebra routines, the system handles the complexity of concurrency, fault tolerance, and resource allocation—all by simply watching how data flows through the program.

Key Foundational Work

Coarse-Grain Parallel Programming in Jade (1991) — contributed 2 concept elements to this direction.
Pegasys: software for executing and integrating analyses of biological sequences (2004) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_dynamic_dependency_graph_construction_953b56b3,
  title = {dynamic dependency graph construction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dynamic-dependency-graph-construction/rdr_953b56b3b4624f1490d80b5d8de0d9ac},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_dynamic_dependency_graph_construction_953b56b3_v1,
  title = {dynamic dependency graph construction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dynamic-dependency-graph-construction/rdr_953b56b3b4624f1490d80b5d8de0d9ac/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake