dep_gen — Complete Per-Submit Dependency Graph (Tensor-Annotated)¶

1. Background & Motivation¶

The swimlane profiler used to expose a per-task fanout[] array — the obvious place to read "which tasks did task X feed into?" — but it was structurally incomplete on real hardware, so it has been removed from the record entirely. The device hot path no longer carries fanout; deps.json is now the sole source of truth for swimlane edges.

When it existed, each producer task carried its own L2SwimlaneAicpuTaskRecord.fanout[], populated by the AICPU scheduler at the moment it wired a downstream consumer. If a producer had already finished and transitioned to PTO2_TASK_COMPLETED by the time a later submit wanted to register a dependency on it, the consumer's edge had nowhere to go — the record was sealed, the slot was closed, and the edge was silently dropped. This was not a bug in fanout itself; fanout is "successors known at runtime", not "successors discoverable from the orchestrator's input". Race window in #599; see also the PR #500 archive for the historical attempt to fix this in-place.

dep_gen sidesteps the race by building the graph from the orchestrator's side of the dependency computation rather than the scheduler's, so a producer that has already retired is still an edge. How that is done depends on where the orchestrator runs — see §2 for the two shapes — but the output is the same deps.json, and either way it was a strict superset of the old fanout edges: every fanout edge appeared in deps.json, plus the edges fanout dropped due to the race — which is why deps.json now fully replaces the removed fanout[].

2. Overview¶

dep_gen has two shapes, chosen by where the orchestrator runs. Both emit the same deps.json (§4), so every consumer — deps viewer, swimlane join — reads either one the same way.

2.1 Device orchestration (`tensormap_and_ringbuffer`)¶

The orchestrator runs on the AICPU, where the host cannot observe it, so the inputs to each submit are captured and the graph is reconstructed afterwards.

Capture point. pto_orchestrator::submit_task writes a DepGenRecord (task_id, scope flag, tensor blobs, arg types, explicit deps, kernel ids, and SPMD block num) into a per-thread shared-memory ring buffer for every call when enable_dep_gen is on.
In-memory drain. The host DepGenCollector (background mgmt thread, ProfilerBase machinery shared with PMU / L2 Perf / Tensor Dump) drains the ring into a std::vector<DepGenRecord> resident on the runner. No submit_trace.bin lands on disk — the host already has the records once the run ends, and going through the filesystem would just be extra I/O.
Host replay (dual-pass, self-checking). After reconcile_counters() confirms a clean trace (no drops, no leftovers), dep_gen_replay_emit_deps_json runs every record back through two parallel host-resident PTO2TensorMap instances that evolve in lockstep:
Oracle pass drives the canonical compute_task_fanin template from pto_dep_compute.h and collects the producer-id set the runtime would have emitted.
Annotated pass runs an inlined mirror of STEP A (creator retention) + STEP B (tensormap lookup) against the second map, with a wider callback so each edge gets recorded with its tensor metadata (producer/consumer shape + offset, dtype, version). Per-record semantics mirror runtime submit_task exactly: STEP 1 (explicit deps), STEP 3 (creator retention + tensormap lookup), STEP 4 (register outputs). Per-successor dedup matches PTO2FaninBuilder::append_fanin_or_fail. After both passes finish per record, the replay asserts the two producer-id sets are equal; if they diverge, deps.json is not written and the function returns non-zero. This is the guarantee against silent shotgun modifications — anyone who changes compute_task_fanin semantics will trip the gate immediately and know to update the annotated mirror.
Output. <output_prefix>/deps.json — strided-Tensor schema with tasks[], tensors[], and tensor-annotated edges[] (see §4).

2.2 Host orchestration (`host_build_graph`)¶

The orchestrator runs on the host, to completion, before any scheduler thread starts. Every submit and every tensormap hit is therefore observable in-process and in order, so the graph is recorded as the runtime builds it — there is nothing to capture-then-reconstruct.

Capture point. submit_task_common opens the task's entry, and compute_task_fanin's Annotate hooks fire on each producer the runtime actually wires: creator retention (Step A) and tensormap lookup (Step B), plus the declared dependencies at STEP 1. The edges are the runtime's own, not a replay's inference, so they cannot drift from compute_task_fanin semantics.
No ring, no collector, no replay. The device-side dep_gen writer, its shared-memory ring, and the drain thread are all skipped (dep_gen_host_graph_active() tells the runner). Nothing is dropped under back-pressure because nothing is streamed.
Output. The same deps.json, written at run teardown from the graph that run's orchestration built.

3. How to Enable¶

dep_gen is gated by CallConfig.enable_dep_gen (alongside enable_l2_swimlane, enable_dump_args, enable_pmu). The CLI flag is --enable-dep-gen:

# Standalone
python test_my_case.py --platform <a2a3|a5> --enable-dep-gen --enable-l2-swimlane

# Pytest
pytest tests/st/... --platform <a2a3|a5> --enable-dep-gen --enable-l2-swimlane

The --enable-l2-swimlane flag is independent but recommended in pair because:

deps.json is the dep_gen artifact.
l2_swimlane_records.json (from swimlane) is the timing artifact; merged_swimlane.json (the Perfetto trace) uses deps.json for dependency arrows when both files exist (without it, the trace has no dependency arrows — the record no longer carries fanout[]).

For perf-sensitive runs where you'd rather measure each profiler in isolation, see the split workflow described in l2-swimlane-profiling §3.5 — one dep_gen capture per topology, then any number of swimlane runs that the converter joins back to that captured graph.

When --enable-dep-gen is on with any other diagnostic flag, an output_prefix directory must be set (the runtime throws otherwise). The standard SceneTest path (outputs/<TestName>_<case>_<timestamp>/) handles that automatically.

4. Output: `deps.json`¶

{
  "tasks": [
    {"task_id": "0",          "scope": "auto", "kernel_ids": [-1,-1,-1], "block_num": 1, "args": []},
    {"task_id": "4294967296", "scope": "auto", "kernel_ids": [7,-1,-1], "block_num": 4, "args": [
      {"idx": 0, "type": "INPUT", "tensor_id": "13451765318376212391",
       "dtype": "FLOAT32", "shape": [16384],
       "start_offset": "0", "strides": [1]}
    ]}
  ],
  "tensors": [
    {"tensor_id": "13451765318376212391",
     "buffer_addr": "29204938752", "version": 0,
     "dtype": "FLOAT32", "buffer_numel": "16384"}
  ],
  "edges": [
    {"pred": "0", "succ": "4294967296", "arg": 0, "source": "creator",
     "tensor_id": "13451765318376212391", "consumer_dtype": "FLOAT32",
     "consumer_shape": [16384],
     "consumer_start_offset": "0", "consumer_strides": [1]},
    {"pred": "4294967296", "succ": "4294967298", "arg": 0, "source": "tensormap",
     "overlap": "covered",
     "tensor_id": "9514117477438350967", "consumer_dtype": "FLOAT32",
     "consumer_shape": [16384],
     "consumer_start_offset": "0", "consumer_strides": [1],
     "producer_shape": [16384],
     "producer_start_offset": "0", "producer_strides": [1]}
  ]
}

All 64-bit unsigned fields (task_id, tensor_id, pred, succ, buffer_addr) are serialized as JSON strings, not numbers. Many JavaScript-based JSON parsers can only safely represent integers up to Number.MAX_SAFE_INTEGER (2^53 − 1); tensor_id (FNV-1a hash) and buffer_addr (hardware address) routinely exceed that limit and would silently lose precision if encoded as numbers. Python consumers pass these through int(v) which accepts either form, so the schema is JS-safe without burdening Python.

Task ids encode (ring_id << 32) | local_id — the same layout as PTO2TaskId::raw:

ring = (raw >> 32) & 0xFF
local = raw & 0xFFFFFFFF

`tasks[]`¶

One entry per task observed in the trace. scope is "manual" when the submit happened inside a manual scope (no automatic dependency wiring) and "auto" otherwise. kernel_ids is the per-subslot [aic,aiv0,aiv1] kernel id triple, with inactive subslots encoded as -1. block_num is the SPMD logical block num for the submit; 1 means a normal single-block task and values greater than 1 identify SPMD tasks. Tools that only need task-pair edges can ignore this block.

`tensors[]`¶

One entry per unique (buffer_addr, version) pair touched by the trace. tensor_id is a stable FNV-1a 64-bit hash of that pair — identical inputs across runs yield the same id, making deps.json files diffable. buffer_numel is the element count of the underlying buffer, not the slice; per-edge slice geometry (shape + start_offset + strides) lives in the edges[] entries.

`edges[]`¶

Each edge is {pred, succ} plus annotation. Fields:

Field	Type	When present	Meaning
`pred`, `succ`	uint64 (string)	always	`PTO2TaskId::raw` of producer and consumer
`arg`	int32	always	Consumer's arg-slot index; `-1` for `explicit` source
`source`	string	always	`explicit` (from `explicit_deps[]`), `creator` (`owner_task_id` retention), or `tensormap` (overlap lookup hit)
`overlap`	string	`source=tensormap`	`covered` (producer slice fully contains consumer slice) or `other`
`tensor_id`	uint64 (string)	not `explicit`	Identity of the underlying tensor; cross-references `tensors[]`
`consumer_dtype`	string	not `explicit`	Element type the consumer reads as
`consumer_shape`	uint32 array	not `explicit`	Per-dim element count of the consumer slice
`consumer_start_offset`	uint64 (string)	not `explicit`	Element offset of the consumer slice into the buffer
`consumer_strides`	uint32 array	not `explicit`	Per-dim stride (in elements) of the consumer slice; runtime invariant > 0
`producer_shape`	uint32 array	`source=tensormap`	Per-dim element count of the producer slice
`producer_start_offset`	uint64 (string)	`source=tensormap`	Element offset of the producer slice
`producer_strides`	uint32 array	`source=tensormap`	Per-dim stride of the producer slice; runtime invariant > 0

A single (pred, succ) pair can appear in edges[] multiple times if the producer drives the consumer through multiple slots, multiple sources, or multiple tensormap matches (different slice / version). For "is task X a successor of task Y at all?" questions, project edges down to the (pred, succ) set; for "what specifically did Y feed into X?", keep the full annotation.

deps.json can have "edges":[] when the workload's tasks have no inter-task data dependencies (e.g. embarrassingly parallel kernels under scope_end barriers). tasks[] and tensors[] still list every observed task and tensor — that is not an error.

5. Visualizing — `deps_viewer.py`¶

simpler_setup/tools/deps_viewer.py turns deps.json into either a plain-text dependency view (default) or a self-contained pan/zoom HTML page (Graphviz SVG with inline vanilla-JS drag/scroll panning and Ctrl+scroll or pinch zooming). The text view is optimized for grep / diff / "what does task X depend on?" debugging; the HTML view stays available when you want a visual layout.

# Newest deps.json under outputs/ -> deps_viewer.txt
python -m simpler_setup.tools.deps_viewer

# Specific path -> deps_viewer.txt next to deps.json
python -m simpler_setup.tools.deps_viewer outputs/.../deps.json

# Explicit HTML output
python -m simpler_setup.tools.deps_viewer outputs/.../deps.json --format html

# HTML output with per-task tensor details
python -m simpler_setup.tools.deps_viewer outputs/.../deps.json --format html --show-tensor-info

# Big HTML graphs: use force-directed layout (recommended >1000 nodes)
python -m simpler_setup.tools.deps_viewer deps.json --format html --engine sfdp

The default text output contains:

SUMMARY — input path plus task / edge / tensor counts.
tasks: number of task ids rendered in the output
unique_task_edges: number of unique (pred, succ) task pairs
annotated_edges: number of annotated edge rows across all task pairs
perf_sidecar: yes when l2_swimlane_records.json was successfully loaded
func_name_map: yes when at least one task label resolved to a named func_name from either an explicit --func-names file or an auto-discovered sibling name_map*.json. When the kernel_ids fallback is used, func_id= shows an aligned 3-slot integer array in [aic,aiv0,aiv1] order; inactive slots remain -1. func_name_map stays no unless a real human-readable name was resolved.
TASK INDEX — one line per task with kind= + func_id= and unique fanin= / fanout= counts for quick grep. SPMD tasks additionally carry SPMD block num = N, where N is the captured logical block num.
TASK DETAILS — one block per task with FANIN / FANOUT peer task references (task-adjacency-only, no tensor detail).

In text mode, HTML-only flags such as --engine and --direction are rejected rather than silently ignored.

Node visual encoding (legend top-right of the rendered HTML):

Shape + color	Meaning
Blue rounded box	AIC (cube) — kernel ran on the matrix unit
Orange ellipse	AIV (vector) — kernel ran on the vector unit
Green diamond	mix — single `submit_task` with `MixedKernels` spanning both core types
Gray dashed note	alloc — task from `alloc_tensors` (got a task_id, references downstream via `owner_task_id`, but never dispatched a kernel so has no perf record)
Red border + right-side `xN` label	SPMD task with `block_num=N`

Node labels read as (ring, local) with a red border and right-side xN block num label for SPMD tasks. The text output (deps_viewer.txt) carries the full kind= + func_id= labels and adds SPMD block num = N only for SPMD tasks; the HTML view keeps the graph focused on structure and the SPMD marker. When you need per-task tensor rows (storage / shape / strides / start_offset) and arg-port edge routing, rerun the HTML export with --show-tensor-info.

Browser controls in the HTML viewer:

drag → pan
scroll / two-finger swipe → pan
Ctrl+scroll / trackpad pinch → zoom about cursor
f key → fit to view
r key → reset to 1:1

The HTML scales to graphs the browser's SVG renderer can handle — in practice, ~50k nodes with --engine sfdp. Past that, you want a canvas/WebGL viewer (Cytoscape.js, sigma.js), which is out of scope for this tool. The default text output does not depend on Graphviz and is the preferred mode for large graphs that need fast generation or grep-first inspection.

6. Relationship to `fanout[]` + Validation Gate¶

When checking fanout coverage, project annotated edges down to a {(pred, succ)} set first — the per-edge annotation distinguishes sources / args / slices, so the raw edges[] count is a superset of the underlying task-pair count.

deps.json (projected) was a superset of the now-removed fanout[] edges — which is exactly why it replaced them as the sole edge source:

Edge source	Captures	Drops on race?
`task.fanout[]` (removed; formerly on L2SwimlaneAicpuTaskRecord)	Successors known at producer-retire time	Yes — sealed when producer retires
`deps.json` (this feature)	Every consumer → producer reachable via tensormap / explicit_deps	No — replay sees every submit

tests/st/{a2a3,a5}/tensormap_and_ringbuffer/dfx/dep_gen/test_dep_gen.py enforces the 6-edge expectation against the vector_example orchestration as a validation gate: any edge missing from deps.json is a replay-side regression and fails the test. (The record no longer carries fanout[], so there is no longer a fanout ⊆ deps cross-check — deps.json is the only edge source.) The swimlane_converter.py uses deps.json (when present) as the source of flow events in the Perfetto trace, and flags any edge whose pred.end_time > succ.start_time as hb_violation (rendered as a distinct flow event name so Perfetto colors it apart from regular dependencies). Dependency flows connect the source and destination bar starts; the completion timestamps are used only for the hb_violation classification, not for flow geometry.

7. Big-Fanin Submits: Overflow Chain¶

A DepGenRecord carries up to 64 explicit_deps inline. Submits with more than 64 explicit deps spill into a chain of DepGenOverflowRecord slots that overlay normal record slots in the buffer.

Submit `explicit_dep_count`	Chain shape	Per-submit slots used
`0 ≤ dc ≤ 64`	base only — fast path, no chain bookkeeping	1
`65 ≤ dc ≤ 646`	base (64 deps) + 1 overflow (up to 582 deps)	2
`647 ≤ dc ≤ 1228`	base + 2 overflow	3
general	base + `⌈(dc − 64) / 582⌉` overflow	`1 + ⌈(dc − 64) / 582⌉`

Wire format. An overflow record reinterprets the same 4672-byte slot as { task_id (8) + flags (4) + dep_count (2) + _reserved (2) + deps[582] } — no tensor blobs (those live on the base record). Replay distinguishes the two views by flags & DEP_GEN_FLAG_OVERFLOW. Chain records always share the base's task_id, and the last one sets DEP_GEN_FLAG_LAST_OVERFLOW so replay knows the chain is complete without peeking ahead.

Atomicity. The AICPU writer reserves all chain slots up front: if the current buffer can't hold the full chain, it switches buffer first. buf->count is published with a single store at the end, so the host either sees the old count (chain invisible) or the new count with the full chain committed. Chain records are therefore always contiguous within one buffer — replay scans linearly and ties them back to the base via task_id.

Truncation tail. A submit whose chain exceeds the buffer's slot budget (PLATFORM_DEP_GEN_RECORDS_PER_BUFFER = 1024 slots → roughly 64 + 1023 × 582 = 595450 deps max in the best case) is logged via LOG_ERROR and truncated to the largest dc that fits. Runtime correctness is unaffected — L0TaskArgs::set_dependencies keeps the full dep list; only the dep_gen replay graph loses the tail.

8. Architecture Touchpoints¶

Layer	File	Role
Shared-mem layout	`src/{a2a3,a5}/platform/include/common/dep_gen.h`	`DepGenRecord` (4672 B base, cache-line aligned, ≤64 inline explicit_deps, per-task `block_num`) + `DepGenOverflowRecord` chain view (≤582 deps per slot) + SPSC ring + per-thread ready queue. Byte-identical layout across platforms.
AICPU writer	`src/{a2a3,a5}/platform/include/aicpu/dep_gen_collector_aicpu.h`, `src/common/platform/shared/aicpu/dep_gen_collector_aicpu.cpp`	Single-instance write path; weak-fallback exported to host build. Both platforms share the same writer implementation — the writer accesses its own device-side view of shared memory, independent of how host↔device transport is implemented.
Host collector	`src/common/platform/include/host/dep_gen_collector.h`, `src/common/platform/shared/host/dep_gen_collector.cpp`	`ProfilerBase<DepGenCollector, DepGenModule>` — drains ring → `records_` vector. On non-SVM platforms it uses the base `alloc_paired_buffer`, which malloc's a host shadow + `copy_to_device`'s it and registers it via `add_malloc_shadow` so teardown can free it; `reconcile_counters` explicitly `copy_from_device`'s the BufferState before reading, and `finalize` lets `BufferPoolManager::clear_mappings()` release all shadows as the single source of truth.
Capture call site (device-orch)	`src/{a2a3,a5}/runtime/tensormap_and_ringbuffer/runtime/pto_orchestrator.cpp` `submit_task_common`	One conditional block that snapshots inputs into the ring when `is_dep_gen_enabled()`; fires for both `submit_task` and `submit_dummy_task`. The schema carries `kernel_ids[3] = {aic, aiv0, aiv1}` so the swimlane post-processor can resolve `task_id → kernel` from `deps.json` at level=1 where the AICore record is the sole device-side identity source. Inactive subslots stay at `INVALID_KERNEL_ID = -1`. It also carries the SPMD logical block num (`block_num` on a2a3, `core_num` on a5's launch spec) as `tasks[].block_num`.
Replay	`src/{a2a3,a5}/runtime/tensormap_and_ringbuffer/host/dep_gen_replay.{h,cpp}`	Pure CPU; runs dual-pass differential replay — `compute_task_fanin` (oracle) + inlined STEP A/B mirror (annotated) against two `PTO2TensorMap` instances. Emits `deps.json` when both passes agree per record. Platform-agnostic — a5 reuses the a2a3 source verbatim.
Host-direct capture (host-orch)	`src/a2a3/runtime/host_build_graph/runtime/dep_gen_host_graph.h`, `src/a2a3/runtime/host_build_graph/host/dep_gen_host_graph.cpp`	Task / tensor / edge tables filled from `submit_task_common` + `compute_task_fanin`'s `Annotate` hooks (`src/a2a3/runtime/host_build_graph/runtime/pto_dep_compute.h`), reset per orchestration by `run_host_orchestration`, serialized by the same `deps.json` writer. The runtime translation unit carries weak no-op fallbacks so the AICPU build links without it.
Device-runner hookup	`src/{a2a3,a5}/platform/{onboard,sim}/host/device_runner.cpp`	`dep_gen_host_graph_active()` picks the shape: host-orch calls `dep_gen_host_graph_emit(deps_path)` and skips collector init/start/reconcile entirely; device-orch calls `dep_gen_replay_emit_deps_json(records.data(), records.size(), deps_path)` post-`reconcile_counters`. The c_api latches the CallConfig before the bind so host capture is armed before the orchestration it records.
Viewer	`simpler_setup/tools/deps_viewer.py`	`deps.json` → text (default) or pan/zoom HTML
Test	`tests/st/{a2a3,a5}/tensormap_and_ringbuffer/dfx/dep_gen/test_dep_gen.py` + `test_dep_gen_chain.py`, `tests/st/a2a3/host_build_graph/dfx/dep_gen/test_dep_gen.py`	Smoke test + 6-edge validation against `vector_example` orchestration (both platforms share byte-identical orchestration code). The host_build_graph case runs the same orchestration through host-direct capture and asserts the same 6 edges, so a divergence between the two shapes fails a test.

The device-orch shape is supported on both a2a3 and a5. The a5 host collector differs from a2a3 only in its host↔device transport path (a5 has no SVM, so all transfers go through profiling_copy_to_device / profiling_copy_from_device instead of relying on halHostRegister's shared mapping); the AICPU writer, shared-memory ABI, runtime call site, and replay are platform-agnostic.

The host-direct shape lives in a2a3's host_build_graph, the one host-orchestrated runtime. src/a5/runtime/host_build_graph/ has no dep_gen of either shape.

dep_gen — Complete Per-Submit Dependency Graph (Tensor-Annotated)¶

1. Background & Motivation¶

2. Overview¶

2.1 Device orchestration (tensormap_and_ringbuffer)¶

2.2 Host orchestration (host_build_graph)¶

3. How to Enable¶

4. Output: deps.json¶

tasks[]¶

tensors[]¶

edges[]¶

5. Visualizing — deps_viewer.py¶

6. Relationship to fanout[] + Validation Gate¶