nx_task_graph.nx
buildroot/runtime/nx_task_graph.nx
about
nx_task_graph.nx -- DAG of tasks with explicit dependency edges.
Built on nx_thread_pool: each node is a (fn_ptr, ctx) task plus
dependency edges to/from other nodes. Scheduling is topo-sort
via atomic counters: when a task finishes, it atomic-decrements
each successor's `predecessors_done` counter; any successor whose
counter reaches `n_predecessors` is now ready and gets submitted
to the pool. Initial frontier (nodes with zero predecessors) is
submitted by `nx_graph_run`.
Why this matters for SSS-class workloads:
* ML inference: layer N can't run before layer N-1 finishes.
Task graph naturally expresses this without manual barriers.
* Render pipelines: vertex -> raster -> pixel -> tonemap
stages with parallelism inside each stage.
* Build systems: target depends on N source files; ninja is
basically a task-graph engine.
* MapReduce: map tasks -> shuffle -> reduce tasks.
MVP shape -- 8 successors per node ceiling (fixed-size inline),
no cycle detection (caller's responsibility), no priorities.
All three are next-evolution concerns.
Composes against: [[nx_thread_pool_shared_queue]] (executor),
[[atomic_intrinsics_real_amo]] (predecessor counters),
[[fn_ptr_indirect_call]] (typed task dispatch),
[[vyukov_mpmc_channel]] (pool's task queue).
dependencies 3 imports · 1 importers
imports: nx_syscalls.nxnx_atom.nxnx_thread_pool.nx
imported by: nx_task_graph_test.nx
call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown
structs
| 49 | struct NxGraphNode |
| 72 | struct NxTaskGraph |
consts
| 38 | const NX_MAGIC_2000000000: i64 = 2000000000 |
| 40 | const NX_GRAPH_MAX_SUCCS_PER_NODE: i64 = 8 |
| 42 | const NX_GRAPH_STATE_PENDING: i64 = 0 |
| 43 | const NX_GRAPH_STATE_READY: i64 = 1 |
| 44 | const NX_GRAPH_STATE_RUNNING: i64 = 2 |
| 45 | const NX_GRAPH_STATE_DONE: i64 = 3 |
| 68 | const NX_GRAPH_NODE_BYTES: i64 = 128 |
| 69 | const NX_GRAPH_OFF_PRED_DONE: i64 = 32 // offset of predecessors_done within NxGraphNode |
| 70 | const NX_GRAPH_OFF_SUCC_0: i64 = 64 // offset of succ_0 within NxGraphNode |
| 81 | const NX_GRAPH_OFF_COMPLETED: i64 = 32 |
functions
| 84 | func _nx_graph_node_at(g: *NxTaskGraph, idx: i64) -> *NxGraphNode |
| 89 | func _nx_graph_set_succ(node: *NxGraphNode, k: i64, succ_idx: i64) -> i64 called by 1: nx_graph_add_edge |
| 96 | func _nx_graph_get_succ(node: *NxGraphNode, k: i64) -> i64 called by 1: _nx_graph_run_node |
| 104 | func _nx_graph_run_node(ctx: i64) -> i64 |
| 139 | func nx_graph_new(pool: *NxThreadPool, max_nodes: i64) -> *NxTaskGraph |
| 154 | func nx_graph_add_node(g: *NxTaskGraph, fn: func(i64) -> i64, ctx: i64) -> i64 |
| 172 | func nx_graph_add_edge(g: *NxTaskGraph, from_idx: i64, to_idx: i64) -> i64 |
| 185 | func nx_graph_run(g: *NxTaskGraph) -> i64 |
| 209 | func nx_graph_n_completed(g: *NxTaskGraph) -> i64 |
| 214 | func nx_graph_node_state(g: *NxTaskGraph, idx: i64) -> i64 calls 1: _nx_graph_node_at |
| 222 | func _graph_self_test_task(ctx: i64) -> i64 calls 1: nx_atom_faa_i64 |
| 228 | func main() -> i64 |