A Few More Branches in the Graph—and Synchronization Registers Run Out First?

Series contents · Resources and Scheduling · 阅读中文版

“The arithmetic barely grew. Why can’t we even generate the code?”

The graph on the whiteboard looks innocent: one producer, followed by many consumers. There is memory to spare and no increase in compute units, yet the dependency resource pool is the first to raise an alarm. Drawing a parallel program as nodes and edges is easy. The difficulty is that each edge eventually needs a waiting mechanism the device understands, and synchronization objects may be finite.

A Graph Edge Need Not Mean a Physical Synchronization Slot

Suppose transfer engine D produces some data, and compute engine V executes three consumers in order:

1
2
3
4
5

D:   P
     ├────────► C1
     ├────────► C2
     └────────► C3
V:              C1 → C2 → C3

The most direct implementation allocates an event for every cross-engine edge. P produces three notifications, and each consumer waits for its own. This is easy to understand, but synchronization-resource use may then grow with fanout.

If V’s queue guarantees that later commands cannot pass an earlier wait, waiting for P before C1 also constrains C2 and C3 indirectly. The semantics require all three consumers to follow P; they do not necessarily require three long-lived physical notifications.

The crucial word is “if.” Hardware differs in its definitions of queue ordering, command completion, and wait scope. Merging simply because consumers use the same engine, without the necessary queue semantics, mistakes an ordering drawn on paper for a device guarantee.

Turn Edges into Intervals, and the Problem Becomes Clearer

The verified implementation numbers the scheduled tasks and buckets edges by their producer-engine and consumer-engine pair. Each cross-engine edge becomes an interval:

1

(producer_position, consumer_position]

It then sorts by consumer position, chooses the earliest consumer as a barrier, and absorbs the edges covering that point into one group. The absorbed producers all notify the group on completion. The earliest consumer waits once, and queue ordering protects subsequent commands on the same consumer engine.

Consider three redesigned intervals:

1
2
3

P1 → C1 : (1, 5]
P2 → C2 : (3, 8]
P3 → C3 : (6, 9]

Choosing position 5 merges the first two intervals but not the third: P3 appears after the barrier. Making position 5 wait for P3 would require future work to complete first. At best this adds serialization; at worst it interacts with queue-issuance conditions to form a wait cycle.

The implementation compares producer positions with the barrier position and leaves future producers for the next group. This condition protects correctness. It cannot be removed during refactoring as a mere sorting detail.

Merging Also Introduces Conservative Waiting

Before merging, C1 may need only P1. Afterward, it also waits for P2, which originally served only C2. Fewer synchronization groups can therefore mean extra waiting for an earlier consumer.

The objective is not unconditional maximum overlap. It is a legal schedule under finite synchronization resources. The tradeoff is explicit: fewer active synchronization objects in exchange for potentially stronger timing constraints.

A common misunderstanding is: “The algorithm merges edges, so there are fewer waits and it must be faster.” More precisely, fewer explicit waits or synchronization groups do not imply a shorter critical path. Performance depends on whether P2 has already completed, whether C1’s extra wait blocks a long chain, and whether later tasks lose overlap opportunities.

This also explains grouping by engine pair first. Distinct consumer queues do not share an inherent ordering guarantee. Depending on the same data does not let one queue borrow the protection of another queue’s wait.

The Graph Scheduler Cannot Spend the Entire Budget

The code also introduces a graph-level dependency budget, reserving some resources for synchronization inside kernels. The actual counts are omitted from this public article because the principle does not depend on them.

In a teaching budget, suppose there are K slots in total and a complex kernel needs at most H internal slots. Graph-level concurrent usage must then stay at or below K−H. Otherwise, a graph schedule that “just fits” leaves an otherwise valid kernel unable to establish its internal synchronization.

A fixed reservation H is still a policy assumption. If a future kernel needs more internal events, the budget must change. A more general design could declare internal demand in task attributes and calculate the combined peak over the timeline, at the cost of more complex scheduler and kernel interfaces.

This resembles ordinary register allocation, but the analogy is incomplete. Synchronization slots also carry production counts, consumption counts, and a release protocol. Reclamation depends on completion of that protocol, not merely on a source variable leaving scope.

Why Check Twice?

The reviewed commit simulates dependency-group live intervals before generation and records the peak. If the budget is exceeded, it reports long-lived groups and their starting tasks. After generation, it separately checks that graph-level groups and internal registers have all been returned.

These checks address different errors. The first checks that the planned peak fits the budget. The second checks for missing waits, missing releases, or leaked internal resources during actual emission. A sound plan can still fail if a special path skips a release. Conversely, ending with a resource count of zero does not prove the budget was never exceeded along the way.

Diagnostics should also point toward an action. “Resources exhausted” only says that a wall was hit. Identifying where a group began and how many tasks it remained live across tells developers which lifetime they may need to shorten.

Walk Through the Merged Ledger

Consider producers P and Q and three consumers A, B, and C on one queue. A reads only P, B reads both P and Q, and C reads only Q. Assume P and Q both precede A. A merged group can register two distinct producers and be waited on once before A. “Distinct” matters: P appears on two edges, but that does not make it two independent pieces of producer work.

This explains why barrier construction deduplicates producers. If metadata promises three notifications but only two occur, a consumer may wait forever. If it promises two but an emission path generates three, premature reclamation or an accounting error may follow. Graph deduplication and runtime protocol counts must use the same unit.

Now move Q after A. The original merge condition immediately fails. A cannot wait for a task that has not yet been issued merely to preserve an attractive shared barrier. Move C to another consumer queue, and A’s wait no longer automatically protects C either. These two small changes test the algorithm’s core assumptions without a large model.

Finally, compare two diagnostics. One says only “allocation failed.” The other identifies an event that starts at P and spans many tasks before ending at C. The second turns pressure back into a time interval, giving developers a chance to move consumers, alter grouping, or shorten ownership. Pressure occurs at a particular moment; the total number of events created is a different statistic.

An Easy Counterexample to Miss

Suppose two consumers use the same engine but different queues, or later commands may bypass earlier waits. C1 having waited for P no longer implies that C2 has waited for P. A change in the queue model can thus invalidate a previously correct barrier-merging strategy.

Another counterexample arises when a logical operation becomes several tasks and dependency construction selects the wrong producer task: it waits for configuration preparation, not for the task that actually writes the output. Graph-level dependencies must agree with the task decomposition after lowering. The original operation’s name cannot identify its completion point on its own.

Regression Matrix and Experiments

The commit includes high-fanout graph-generation tests and checks for allocation boundaries, multiple-producer accounting, duplicate waits, and duplicate releases.

A proposed experiment has two stages. First, use a small discrete-event model to verify that every consumer starts after its actual producers complete. Then compare per-edge events with grouped barriers. Record peak synchronization slots, added waiting edges, theoretical critical-path length, and simulated queue utilization. Add end-to-end latency only when real device measurements are available.

A graph with a hundred edges does not necessarily need a hundred synchronization slots. Before removing the first slot, however, be able to name the queue-ordering guarantee that takes over its promise.

Back to series contents · Previous · Next

• ← Previous Post
• Next Post →