# Support-Graph Parallel Scheduler

- ID: 598
- Canonical URL: https://synthcore.org/idea/598/support-graph-parallel-scheduler
- API JSON: https://synthcore.org/api/idea/598.json
- API Markdown: https://synthcore.org/api/idea/598.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.08841](https://arxiv.org/abs/2607.08841)
- Category: architecture
- Solves: speedup, scalability
- ML areas: transformer, mlp, inference-speedup, batching
- Math tags: graph-theory, combinatorics, dynamics
- Ratings: usefulness 7/10; difficulty 5/10; novelty 5/10

## Idea description

Convert a sequential modular network into parallel execution layers by placing mutually commuting operators in the same layer. The resulting circuit preserves all noncommuting precedence constraints while exposing safe concurrency and fusion opportunities for inference or training.

## Mathematical statement

The paper represents a circuit as a sequence \(C=(K_1,K_2,\ldots,K_k)\) of vertical layers, where each \(K_i\subseteq X\) is a clique in the commutation graph \(\mathcal G\); operators in one layer commute and execute in parallel, while different layers execute sequentially. For a wire representation, each operator \(x\) acts on a support \(S_x\) consisting of the wires it touches. Given wire words \(W=(w_1,\ldots,w_m)\) and current head positions \(h=(h_1,\ldots,h_m)\), the paper defines the feasible set \(F(W;h)=\{x\in X:\forall i\in S_x,(w_i)_{h_i}=x\}\). Here \((w_i)_{h_i}\) is the first unconsumed operation on wire \(i\); an operation is feasible exactly when it is simultaneously visible on every wire it uses. Consuming all feasible operations forms the next parallel layer. The same construction can be applied to a neural computation graph, with wires representing disjoint channel groups, heads, tensor blocks, or device partitions. The depth of the resulting layered circuit is the critical-path execution depth, not the total number of operators.

## Key formulas

- $$C=(K_1,K_2,\ldots,K_k),\qquad K_i\subseteq X\text{ is a clique in }\mathcal G.$$
- $$F(W;h):=\{x\in X:\ \forall i\in S_x,\ (w_i)_{h_i}=x\}.$$
- $$h_i\leftarrow h_i+1\quad\text{for every }i\in S_x\text{ when }x\text{ is placed in the current layer}.$$
- $$\operatorname{depth}(C)=\min\{k:C=(K_1,\ldots,K_k)\text{ respects all noncommuting precedence constraints}\}.$$

## Implementation notes

Integrate the scheduler into inference graph construction, after tracing a modular model but before kernel compilation. Partition the model state into explicit wires: channel groups for grouped convolutions or MLPs, attention heads for head-local projections, and separate feature blocks for block-diagonal linear layers. Represent each primitive operation \(x\) by its wire support \(S_x\) and by its occurrence in each wire word \(w_i\). Initialize head pointers \(h_i=1\). At each scheduling step compute \(F(W;h)=\{x:\forall i\in S_x,(w_i)_{h_i}=x\}\); put every element of \(F\) into the next layer if their supports are pairwise disjoint or if a backend-certified fused kernel exists. Advance all pointers on the supports of selected operators and repeat until all words are consumed. If multiple feasible operations share wires, choose the subset maximizing estimated kernel occupancy, or greedily select the largest support-disjoint set. Preserve the original order for every pair whose supports overlap. The scheduler computes feasibility from the paper’s head rule; kernel launch cost, memory bandwidth, and fusion benefit must be measured empirically. First test a 12-layer grouped MLP and a 4-head Transformer with head-local feed-forward modules on an NVIDIA GPU, comparing sequential execution against this scheduler at batch sizes 1 and 32. Measure critical-path latency, number of kernel launches, peak activation memory, and exact output agreement. The expected signal is reduced inference latency and launch count, with no measurable change in logits or perplexity.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: no_effect
- Verdict: Built the support-graph wire-word scheduler with head-pointer feasibility, disjoint-support layer selection, prediction sweeps, and a grouped-MLP benchmark. All 17/17 quantitative toy checks matched prediction: independent chains had depth L and parallelism m, critical-path cases had depth max(critical, side), and shared-support precedence was preserved exactly. On the CUDA grouped MLP, the scheduled implementation reduced the launch proxy from 48 to 12 and measured 3.28x speedup at batch 1 and 3.58x at batch 32, with maximum absolute output error at or below 3.7e-9.

### Mechanism check

- Verdict: Built the support-graph wire-word scheduler with head-pointer feasibility, disjoint-support layer selection, prediction sweeps, and a grouped-MLP benchmark. All 17/17 quantitative toy checks matched prediction: independent chains had depth L and parallelism m, critical-path cases had depth max(critical, side), and shared-support precedence was preserved exactly. On the CUDA grouped MLP, the scheduled implementation reduced the launch proxy from 48 to 12 and measured 3.28x speedup at batch 1 and 3.58x at batch 32, with maximum absolute output error at or below 3.7e-9.
- Confidence: 9/10
- Limitations: The benchmark uses a small synthetic grouped MLP and compares a Python per-group baseline with a batched einsum implementation; launch counts are proxies rather than traced kernel-launch counts. No real traced Transformer, compiler integration, peak activation-memory measurement, training experiment, or multi-run statistical confidence interval was tested.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 1
- Paired wins: 1/8
- Benchmark verdict: no measurable effect

## Artifacts

- [bench_report.json](https://synthcore.org/code/271/bench_report.json)
- [report.md](https://synthcore.org/code/271/report.md)
- [report_bench_2026-08-30T235111.md](https://synthcore.org/code/271/report_bench_2026-08-30T235111.md)
- [results.json](https://synthcore.org/code/271/results.json)
- [scheduler_experiment.py](https://synthcore.org/code/271/scheduler_experiment.py)
- [stage2_scheduler_bench.py](https://synthcore.org/code/271/stage2_scheduler_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/271)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.