[Bug] READY NEXT_LEVEL group can be overtaken indefinitely by later singles (no Tier-0 equivalent at L3)

[ChaoWao]

Platform

All / Unknown

Runtime Variant

All / Unknown

Description

A NEXT_LEVEL group and the per-worker NEXT_LEVEL singles live in separate,
unordered queues, and the scheduler gives a blocked group no hold on its
already-idle targets. A single that becomes READY after the group can
therefore take a worker the group is waiting for, and it can do so on every
scheduler round. A group of N targets only launches if all N happen to be idle
within the same round, so under sustained single traffic on its targets a
READY group can be delayed without bound. The larger the group, the less likely
the simultaneous-idle window ever opens — a TP-8 group needs 8 workers idle in
one round.

The expected policy is the one L2 already implements for sync_start: an
all-or-nothing cohort is a strict Tier-0 that takes resources before any
regular task, and when it cannot fit it waits and retries rather than
yielding its share back.

src/common/hierarchical/scheduler.cpp:

void Scheduler::dispatch_ready() {
    dispatch_next_level_group();     // :353
    dispatch_next_level_singles();   // :354
    dispatch_sub_ready();
}

void Scheduler::dispatch_next_level_group() {
    ...
    for (int32_t i = 0; i < group_size; ++i) {
        ...
        if (!worker->idle()) return;   // :420 — gives up, leaves no trace
        workers.push_back(worker);
    }

dispatch_next_level_singles() (:437-458) then walks every worker and
dispatches to any that is idle(). It has no knowledge that a group is waiting
on that worker, so it refills the exact worker the group needs.

Group-before-singles ordering therefore only holds within one round, and each
round is triggered by a single completion — so whichever worker just went idle
is refilled in the same round it became available.

Steps to Reproduce

Two NEXT_LEVEL workers; a group targeting both; singles arriving on both after
the group.

T1 -> worker0 (single)             # running
T2 -> group {worker0, worker1}     # group FIFO head, blocked on worker0
T3 -> worker1 (single)             # submitted AFTER T2

round A (T1 running):  group: worker0 busy -> return
                       singles: worker1 idle -> dispatch T3      <-- overtakes T2
round B (T1 done):     group: worker1 busy  -> return
                       singles: worker0 idle -> dispatch T4
round C (T3 done):     group: worker0 busy  -> return
                       singles: worker1 idle -> dispatch T5
...

T2 launches only if worker0 and worker1 are idle in the same round. With
singles continuing to become READY on both targets, that never happens.

Note the queues are filled at READY time, not submit time (PENDING tasks live in task-slot state, not in a ready queue), so a dependency chain feeding
either worker is enough to sustain the traffic — no adversarial submission
pattern is needed. Pipelined multi-token / multi-request orchestration (#1379)
produces exactly this shape.

The overtaking half is already an asserted behavior in the suite —
tests/ut/cpp/hierarchical/test_scheduler.cpp:777
GroupSchedulerFixture.BlockedGroupDoesNotDispatchPartiallyOrReserveIdleWorker:

auto group = orch.submit_next_level_group(C(71), {group_a, group_b}, cfg, {0, 1});  // first
...
auto independent = orch.submit_next_level(C(72), ..., cfg, 1);                      // later
worker_b.wait_running();
EXPECT_EQ(worker_b.dispatched[0].callable_hash0, 72u);            // later task runs first
EXPECT_EQ(S(group.task_slot).state.load(), TaskState::READY);     // group still waiting

LaunchableGroupPrecedesConflictingSingles (:817) does cover group-first
dispatch, but only by holding sched.loop_mutex() while completing both
workers, forcing the scheduler to observe both idle in one round. Nothing covers
targets going idle one at a time with singles pending.

Expected Behavior

When a group is READY, singles pause and wait for it.

Concretely: while the group-FIFO head is READY, its target workers are reserved;
dispatch_next_level_singles skips a reserved worker; the reservation is
released when the group launches. Reserved workers drain naturally as their
running tasks complete, the group launches, and singles resume.

This is L2's sync_start contract applied at L3. From
src/a2a3/runtime/tensormap_and_ringbuffer/docs/RUNTIME_LOGIC.md:641-660:

the sync lane is drained as a strict Tier-0 before the regular lane
(sync_start > MIX > C/V)

1. Single ownership — a CAS on sync_start_pending (0 -> -1) makes drains
   mutually exclusive; only one cohort drains at a time.
2. All-or-nothing — thread 0 checks count_global_available >= block_num
   before staging. If short, it advances the attempt and retries after
   completions free cores. A cohort is fully staged or not at all.

Single ownership + all-or-nothing make the drain deadlock-free across
multiple cohorts: at most one drains, and it fully stages or waits, so two
cohorts can never each half-occupy the cluster set.

L3 groups are the same problem — all-or-nothing co-occupancy of N resources —
and should get the same answer. Restricting the reservation to the group-FIFO
head is the direct analogue of L2's single-ownership CAS: at most one reserver
exists, so the wait-for graph cannot contain a cycle.

Liveness argument for the reservation: a reservation only blocks new dispatch,
it never keeps a busy worker busy; the task currently running on a reserved
worker depends on nothing that is still queued; and a READY group has fanin 0,
so it depends on no queued single. Every reserved worker therefore reaches idle
in bounded time and the head group launches.

Precondition, which should be stated as an explicit invariant: a running task
must not block waiting on a not-yet-dispatched task at the same level. Splitting
a collective into independent singles already violates the intent of the group
API (nothing co-schedules independent singles), so this is making an existing
implicit requirement explicit rather than adding a new constraint.

Actual Behavior

The group yields. dispatch_next_level_group returns without recording that a
group wants those workers, and dispatch_next_level_singles immediately gives
one away.

This is currently documented as intended. docs/directed-next-level-scheduling.md:

Only the group FIFO head is examined, and a launchable group is tried before
conflicting singles. The runtime adds no fairness, aging, priority, or
reservation policy; callers choose worker sets that make acceptable progress.

## Non-goals
- No priorities, work stealing, rebinding, queue scanning, aging, quotas,
  preemption, starvation prevention, or partial group reservation.

Pushing "make acceptable progress" onto callers is not workable for the target
use case: a TP/EP group's worker set is fixed by the parallelism strategy, and
the caller has no way to stop unrelated singles on those same workers from
overtaking it.

Note the two properties bundled under "no partial reservation" in #1436 are
separable:

property	meaning	keep?
no partial dispatch	never launch only part of a group	yes — required
no partial reservation	never hold an idle worker for a waiting group	no — this is the defect

L2 keeps the first and rejects the second; L3 currently rejects both.

Git Commit ID

f0bd241

Host Platform

Linux (aarch64)

Additional Context

Scope of the fix:

• src/common/hierarchical/scheduler.cpp — a reserved-worker set owned solely
  by sched_thread_ (no lock needed); set by dispatch_next_level_group for
  the head group, honored by dispatch_next_level_singles, cleared on launch.
• tests/ut/cpp/hierarchical/test_scheduler.cpp:777 — this test asserts the
  behavior being removed and must be rewritten (its name encodes the old
  contract). Add a real regression: targets going idle one at a time with
  singles pending on each, asserting the group launches within a bounded number
  of rounds.
• docs/directed-next-level-scheduling.md — drop starvation prevention and
  partial group reservation from Non-goals; document the head-only reservation
  rule and the same-level no-blocking-on-undispatched invariant.

Only the head group reserves. Head-of-line blocking between groups (a group
needing {0,1} blocks one needing {2,3}) is retained as-is; relaxing that is a
separate FIFO-semantics question and should not be bundled here.

Related: #1436 (introduced the current model), #1379 (pipelined orchestration —
first workload that sustains the traffic pattern), #1548 (Tier-0 sync_start
drain fast path at L2).