[Feature] Reduce redundant WAIT edges with a bounded reachability bitmap

[ChaoWao]

Summary

Important

Blocked by #1375. This issue must not be implemented until WAIT/readiness and RETAIN/lifetime are independently representable. The reduction described here removes only WAIT; any required RETAIN relation must remain.

After #1375 is complete, add an orchestrator-side bounded transitive-reduction mechanism for the WAIT dependency graph. Each task records a fixed-size bitmap of recently reachable WAIT ancestors. When a new task is submitted, a direct WAIT candidate within the bitmap window can be removed if the bitmap proves that another direct predecessor already provides a transitive WAIT path.

Use BL=64 as the initial design point, then evaluate BL=64/128/256 against representative dependency graphs before selecting the production value. Candidates outside the tracked window are always retained conservatively.

Motivation / Use Case

Consider:

A -> B -> C
A ------> C

The direct A -> C WAIT is redundant because A -> B -> C already orders the tasks. If C also reads an output allocated by A, #1375 allows the direct relation to become RETAIN-only rather than deleting the lifetime reference.

Removing redundant WAIT edges reduces:

• readiness fanin count and atomics;
• producer fanout nodes and dep-pool pressure;
• orchestrator wiring work;
• completion-time fanout traversal;
• dense dependency degree seen by scheduling and early-dispatch bookkeeping.

A full transitive closure is too expensive for the AICPU hot path. A bounded bitmap provides exact reduction for candidates inside a recent task window while paying a small, fixed per-task cost.

Related: #545, #984

Proposed API / Behavior

Preconditions and edge semantics

Before reduction, dependency discovery must:

1. validate producer task generation/liveness;
2. deduplicate by (producer, consumer);
3. OR all edge flags/reasons from creator, TensorMap, and explicit dependencies.

Only edges carrying WAIT participate in reachability. RETAIN-only edges neither set nor propagate reachability bits.

For an edge with WAIT | RETAIN, successful WAIT reduction produces RETAIN-only. A redundant WAIT-only edge is removed completely.

Global submission sequence

The current PTO2TaskId is (ring_id << 32) | per_ring_local_id, so raw task IDs are not globally monotonic and must not be subtracted.

Assign every dependency-graph task a monotonically increasing submit_seq, including relevant dummy/hidden allocation tasks. Store or otherwise recover the producer sequence with generation validation. Cross-ring candidates use this global sequence.

A same-ring-only prototype may conservatively keep every cross-ring WAIT, but the production design should define cross-ring behavior explicitly.

Bitmap definition

For task t, define an ancestor bitmap R[t] of BL bits:

R[t][i] = 1
iff the task with submit sequence seq(t) - i - 1 has a WAIT path to t

Thus bit 0 represents the immediately preceding submitted task and bit BL-1 represents the task submitted BL positions earlier.

For predecessor candidate p:

d = seq(t) - seq(p)
bit_index = d - 1
tracked iff 1 <= d <= BL

Order-independent two-pass reduction

Use two local bitmaps, direct and via, so correctness does not depend on creator/TensorMap/explicit discovery order:

Bitmap direct = 0;
Bitmap via = 0;

for (Candidate &p : unique_wait_candidates) {
    uint64_t d = seq(t) - seq(p);
    if (1 <= d && d <= BL) {
        p.bit = bit(d - 1);
        direct |= p.bit;

        if (d < BL) {
            via |= R[p] << d;
        }
    }
}

R[t] = direct | via;

for (Candidate &p : unique_candidates) {
    DepFlags effective = p.flags;

    if (has_wait(effective) && p.is_tracked() && (via & p.bit)) {
        effective &= ~WAIT;
    }

    if (effective != NONE) {
        materialize_dependency(p, effective);
    }
}

With bit 0 representing t-1, predecessor reachability must be shifted left by d, not right by d-1. For d == BL, set the direct bit but do not shift by BL; shifting a 64-bit value by 64 is undefined and all ancestors of that predecessor are already outside the window.

This two-pass test is exact inside the window:

• If direct candidate p is redundant, every alternate path ends with another direct predecessor q -> t; R[q] contains p, so p appears in via.
• If p appears in via, some direct predecessor q proves the path p -> ... -> q -> t.
• R[t] still includes the direct bit for a reduced candidate because the task remains transitively reachable.

The original one-pass form is not sufficient: current dependency discovery can emit creator A before modifier B, so it may retain A -> C before learning that B already reaches A. The result would depend on candidate enumeration order.

Safety and storage

• d > BL: keep WAIT and do not merge R[p]; p and all of its ancestors are outside the current window.
• Validate TaskId generation and submit_seq before reading R[p]. A stale reused-slot bitmap could create a false positive and delete a required WAIT edge.
• Publish each task bitmap once and keep it immutable for that task generation.
• Prefer orchestrator-private side storage so scheduler cache lines and atomics are not expanded or false-shared.
• Preserve any temporary producer pin required by [Feature] Split wait and retain dependency semantics for safe transitive reduction #1375 until candidate validation/reduction is complete; release it according to the final effective flags.
• Re-evaluate early-dispatch bookkeeping that currently depends on the direct fanin set, while preserving logical launch readiness.

At the default four rings with 16,384 task slots each (65,536 total), bitmap capacity is:

BL	Per task	Total bitmap capacity	Per-candidate bitmap work
64	8 B	512 KiB	one 64-bit word
128	16 B	1 MiB	two words plus cross-word shift
256	32 B	2 MiB	four words

A global sequence side mapping adds another 4 or 8 bytes per live task unless it can be packed into existing per-task metadata without changing hot structure sizes.

BL selection and measurement

Extend dependency replay/analysis to simulate the exact full WAIT graph and the bounded online algorithm for at least BL=64, 128, and 256. Use task record order as global submission order rather than packed PTO2TaskId ordering.

Report:

• total logical WAIT candidates;
• full-graph redundant WAIT edges;
• redundant edges removed at each BL;
• WAIT | RETAIN -> RETAIN conversions;
• pure WAIT edges removed completely;
• window misses and cross-ring misses;
• producer-consumer sequence-distance CDF;
• estimated reduction in readiness fanout nodes/dep-pool entries;
• orchestrator and effective runtime performance before/after the selected BL.

BL=64 should be the default candidate because it is one native machine word. Increase it only if the measured additional coverage justifies multiword loads, shifts, and cache traffic.

Acceptance criteria

1. [Feature] Split wait and retain dependency semantics for safe transitive reduction #1375 is complete and WAIT/RETAIN flags are independently represented.
2. For pure WAIT A -> B -> C plus A -> C, the direct A -> C WAIT is removed when all tasks are within BL.
3. If A -> C is WAIT | RETAIN, reduction leaves a RETAIN-only relation.
4. The online bitmap result matches full-DAG transitive reachability for all candidate edges whose sequence distance is within BL.
5. Candidate discovery order does not change the reduced graph.
6. d == BL, d > BL, same-ring, cross-ring, slot reuse, duplicate-source, and sequence-wrap boundaries have explicit tests.
7. A stale or generation-mismatched bitmap can never cause WAIT removal.
8. a2a3 and a5 tensormap_and_ringbuffer behavior remains aligned.
9. BL=64/128/256 coverage and runtime costs are measured before selecting the final production value.

Alternatives Considered

• One-pass greedy bitmap: cheaper to describe but order-dependent. It misses the target case when an older creator candidate is processed before a newer modifier candidate. An incorrect right shift can also mark an unrelated task reachable and remove a required edge.
• Full transitive closure/reduction: exact for all distances but has unacceptable memory and update cost on the orchestration hot path.
• Same-ring local-ID bitmap: correct if cross-ring candidates are retained conservatively, but misses cross-ring and cross-ring-witness reductions.
• Keep all WAIT edges: correct but retains the readiness/fanout overhead this feature targets.

Additional Context

Dependency:

• Blocked by [Feature] Split wait and retain dependency semantics for safe transitive reduction #1375

The predecessor/resource classification explored by https://github.com/hw-native-sys/simpler/tree/feat/two-kinds-of-dep is relevant background through #1375, but this issue starts only after the independent WAIT/RETAIN representation is available.