code wiki / (root) / nx_task_graph.nx

nx_task_graph.nx

buildroot/runtime/nx_task_graph.nx

9456 B255 linesdepth 7pulls 9 transitivereach 1 importersview sourcekind tooltopic task
docsdependenciesstructsconstsfunctions

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

nx_syscalls.nx nx_atom.nx nx_thread_pool.nx nx_task_graph.nx nx_task_graph_test.nx

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

main nx_pool_new nx_hw_worker_count nx_hw_cpu_count sys_mmap sys_munmap sys_mmap ↻ nx_chan_new sys_mmap ↻ _nx_chan_cell sys_thread_create nx_thread_spawn sys_mmap ↻ nx_thread_spawn_fn sys_mmap ↻ nx_graph_new sys_mmap ↻ sys_mmap ↻ nx_graph_add_node _nx_graph_node_at nx_graph_add_edge _nx_graph_node_at ↻ _nx_graph_set_succ nx_graph_run _nx_graph_node_at ↻ nx_pool_submit nx_atom_faa_i64 nx_chan_send nx_chan_try_send _nx_chan_cell ↻ nx_thread_yield _pool_futex_wake_all sys_futex_wake nx_atom_load_i64 nx_thread_yield ↻ nx_graph_n_completed nx_atom_load_i64 ↻ nx_pool_shutdown nx_atom_faa_i64 ↻ nx_chan_send ↻

structs

49struct NxGraphNode
72struct NxTaskGraph

consts

38const NX_MAGIC_2000000000: i64 = 2000000000
40const NX_GRAPH_MAX_SUCCS_PER_NODE: i64 = 8
42const NX_GRAPH_STATE_PENDING: i64 = 0
43const NX_GRAPH_STATE_READY: i64 = 1
44const NX_GRAPH_STATE_RUNNING: i64 = 2
45const NX_GRAPH_STATE_DONE: i64 = 3
68const NX_GRAPH_NODE_BYTES: i64 = 128
69const NX_GRAPH_OFF_PRED_DONE: i64 = 32 // offset of predecessors_done within NxGraphNode
70const NX_GRAPH_OFF_SUCC_0: i64 = 64 // offset of succ_0 within NxGraphNode
81const NX_GRAPH_OFF_COMPLETED: i64 = 32

functions

84func _nx_graph_node_at(g: *NxTaskGraph, idx: i64) -> *NxGraphNode
89func _nx_graph_set_succ(node: *NxGraphNode, k: i64, succ_idx: i64) -> i64
called by 1: nx_graph_add_edge
96func _nx_graph_get_succ(node: *NxGraphNode, k: i64) -> i64
called by 1: _nx_graph_run_node
104func _nx_graph_run_node(ctx: i64) -> i64
139func nx_graph_new(pool: *NxThreadPool, max_nodes: i64) -> *NxTaskGraph
called by 2: mainmain calls 1: sys_mmap
154func nx_graph_add_node(g: *NxTaskGraph, fn: func(i64) -> i64, ctx: i64) -> i64
called by 2: mainmain calls 1: _nx_graph_node_at
172func nx_graph_add_edge(g: *NxTaskGraph, from_idx: i64, to_idx: i64) -> i64
185func nx_graph_run(g: *NxTaskGraph) -> i64
209func nx_graph_n_completed(g: *NxTaskGraph) -> i64
called by 2: mainmain calls 1: nx_atom_load_i64
214func nx_graph_node_state(g: *NxTaskGraph, idx: i64) -> i64
222func _graph_self_test_task(ctx: i64) -> i64
calls 1: nx_atom_faa_i64
228func main() -> i64