#directed-acyclic-graph #graph-node #dag #schedule #solver #read-write #ecs

dagga

For scheduling directed acyclic graphs of nodes that create, read, write and consume resources

4 releases

0.2.1 Jul 15, 2023
0.2.0 Apr 2, 2023
0.1.1 Mar 16, 2023
0.1.0 Mar 11, 2023

#1162 in Algorithms

Download history 71/week @ 2024-07-04 86/week @ 2024-07-11 70/week @ 2024-07-18 79/week @ 2024-07-25 100/week @ 2024-08-01 62/week @ 2024-08-08 168/week @ 2024-08-15 124/week @ 2024-08-22 158/week @ 2024-08-29 95/week @ 2024-09-05 77/week @ 2024-09-12 115/week @ 2024-09-19 100/week @ 2024-09-26 53/week @ 2024-10-03 67/week @ 2024-10-10 86/week @ 2024-10-17

339 downloads per month
Used in 6 crates (3 directly)

MIT/Apache

46KB
1K SLoC

dagga 🌿

A crate for scheduling directed acyclic graphs.

Features

  • node creates resources semantics
  • node reads resource semantics, ie borrow
  • writes resource semantics, ie mutable/exclusive borrow
  • consumes resource semantics, ie move
  • node dependencies
    • node X must run before node Y
    • node X must run after node Y
    • barriers - nodes added before a barrier will always be scheduled before the barrier and nodes added after a barrier will always be scheduled after the barrier

Example uses

  • scheduling parallel operations with dependencies, shared and exclusive resources
  • scheduling steps in a render graph
  • scheduling system batches in ECS
  • scheduling audio nodes in an audio graph

Example

use dagga::*;

// Create names/values for our resources.
//
// These represent the types of the resources that get created, passed through
// and consumed by each node.
let [a, b, c, d]: [usize; 4] = [0, 1, 2, 3];

// Add the nodes with their dependencies and build the schedule.
// The order they are added should not matter (it may cause differences in
// scheduling, but always result in a valid schedule).
let dag = Dag::<(), usize>::default()
    .with_node({
        // This node results in the creation of an `a`.
        Node::new(()).with_name("create-a").with_result(a)
    })
    .with_node({
        // This node creates a `b`.
        Node::new(()).with_name("create-b").with_result(b)
    })
    .with_node({
        // This node reads `a` and `b` and results in `c`
        Node::new(())
            .with_name("create-c")
            .with_read(a)
            .with_read(b)
            .with_result(c)
    })
    .with_node({
        // This node modifies `a`, but for reasons outside of the scope of the types
        // expressed here (just as an example), it must be run before
        // "create-c". There is no result of this node beside the side-effect of
        // modifying `a`.
        Node::new(())
            .with_name("modify-a")
            .with_write(a)
            .with_read(b)
            .run_before("create-c")
    })
    .with_node({
        // This node consumes `a`, `b`, `c` and results in `d`.
        Node::new(())
            .with_name("reduce-abc-to-d")
            .with_move(a)
            .with_move(b)
            .with_move(c)
            .with_result(d)
    });

dagga::assert_batches(
    &[
        "create-a, create-b", /* each batch can be run in parallel w/o violating
                                * exclusive borrows */
        "modify-a",
        "create-c",
        "reduce-abc-to-d",
    ],
    dag.clone(),
);

You can also have dagga create a dot graph file to visualize the schedule (using graphiz or similar): dagga example schedule

Dependencies

~2MB
~42K SLoC