# Exchange scheduler algorithm ideas This note records candidate improvements considered against the canonical SigLIP MLP exchange-schedule snapshot. The objective is the exact maximum tile event horizon. Approximate models are only used to choose an order; production materialization and validation remain the acceptance test. Fundamentally different RCPSP, MILP, decomposition, and population-search approaches are covered in `docs/EXCHANGE_SCHEDULER_GLOBAL_SEARCH_EXPERIMENTS.md`. ## 1. Remaining endpoint pressure for multicast (implemented) The initial list scheduler ranked ready transfers using the total payload work incident on their endpoints. That pressure was initialized once and never reduced, so it described the original problem rather than the work left after each scheduling decision. For multicast phases, subtract the selected transfer's words from its source and every destination before newly ready or lazily refreshed transfers are ranked. This gives the greedy scheduler a cheap, deterministic approximation of the residual bottleneck load. Point-to-point phases retain static pressure: on those phases it acts as a stable bipartite-matching priority, while dynamic pressure was neutral to slightly worse on the snapshot. Cumulative exact replay results after the implemented algorithms: | Phase | Baseline horizon | Selected horizon | Change | | ---: | ---: | ---: | ---: | | 0 | 7,179 | 7,179 | 0 | | 1 | 5,692 | 5,466 | -226 (-3.97%) | | 2 | 48,293 | 48,086 | -207 (-0.43%) | | 3 | 16,388 | 16,388 | 0 | Phase 2 scheduler/codegen time remained approximately five seconds. The exact number varied by a few percent between single runs, so this change should be treated as schedule-quality work rather than a demonstrated compile-time win. ## 2. Dependency-ready matching waves (implemented for low-degree phases) Point-to-point phases can be viewed as bipartite graphs whose left vertices are source-send buses and right vertices are destination-receive buses. The new alternative scheduler repeatedly constructs a deterministic maximum-cardinality matching from the dependency-ready edges. An entire matching is committed as a wave, its memory dependents are released, and the process repeats. Within the set of maximum-cardinality choices it preserves the incumbent rank and uses residual endpoint work and transfer size as stable secondary priorities. This is a phase-wide graph algorithm rather than an edge-at-a-time list priority. Memory dependencies are topologically preserved between waves, but unequal transfer sizes, route latency, receive-stream state, and instruction encodability remain outside the matching model. The candidate is therefore exact-rematerialized and accepted only when its actual event horizon is lower. On phase 1, matching waves produced a 5,553-cycle exact candidate. One existing critical-neighborhood pass then reduced that schedule to 5,466 cycles. This is 226 cycles (3.97%) below the previous selected schedule and 330 cycles (5.69%) below the 5,796-cycle greedy schedule. With one warmup and three deterministic measured iterations, phase-1 scheduler/codegen time had a 0.638-second median, versus approximately 0.54 seconds before matching waves. This is the expected cost of exact candidate materialization and the subsequent accepted repair. The phase-3 graph is qualitatively different: its busiest receiver has 124 roles, versus 21 in phase 1. A measured matching-wave candidate for phase 3 was valid but took 18,213 cycles, worse than the 16,388-cycle incumbent, and added roughly 3.4 seconds of host search time. Matching waves are consequently limited to point-to-point problems with at most 32 roles on every endpoint. This retains the phase-1 win without running a known-poor candidate on phase 3. ## 3. Exact-slack critical-chain repair The current neighborhood repair traces only one predecessor chosen from an endpoint that was latest in the approximate schedule. It does not retain the actual dependency predecessor when a memory dependency sets the release time, and it scores moves with payload-only timing. A better repair pass would record all exact tight predecessors during materialization, compute backward slack from the exact horizon, and reorder a bounded zero/low-slack neighborhood. Several candidates could be retained and only exact improvements accepted. This is more likely to help phases with a small critical tail than a phase-wide alternative priority. ## 4. Receive-stream continuity as a secondary objective Prioritizing transfers whose destination address continues the current receive stream substantially reduced encoded row size in an experiment on phase 3 (460,497 to 426,701 total row words), but did not reduce its 16,388-cycle horizon. Applied too early in the priority key, it also made phase 2's initial schedule worse and required extra exact repair passes. This remains promising for host compile time if it is applied only after an order has met a horizon budget, or used as the secondary score for equal- horizon candidates. ## 5. Cached schedule-independent transfer plans Topology route selection and address-independent sender/receiver templates can be cached per `(source, destination set, words, point-receiver mode)`. Patched addresses and state-dependent receive-stream cutovers must remain per materialization. This targets host time rather than horizon and would make a multi-start search more affordable. ## 6. Stable input-presentation order sweep The greedy heap ends with deterministic source and transfer-index tie-breaks, so the planner's presentation order can select among many otherwise identical ready transfers. The snapshot order is already structured: phase 3 is source-major, destination-major, with four address chunks interleaved per destination. The `--experimental-input-order` control replaces only this last stable presentation rank; transfer identities and the original semantic memory dependency order are unchanged. Four static alternatives were exact-rematerialized: | Phase | Original | Source-address | Destination-address | Rotated destination | Reverse | | ---: | ---: | ---: | ---: | ---: | ---: | | 1, final horizon | **5,466** | 5,569 | 5,467 | 5,548 | not measured | | 2, final horizon | **48,086** | 48,087 | 48,089 | 48,733 | not measured | | 3, final horizon | **16,388** | **16,388** | 16,393 | 16,393 | 16,396 | Rotated destination order improved phase 1's raw greedy horizon from 5,796 to 5,658, but produced a worse matching/repair starting point. On phase 3 it reduced encoded row words from 460,497 to 447,899 while losing five horizon cycles. Source-address order tied the phase-3 horizon but increased row words to 473,742. Thus presentation rank strongly affects both timing and encoder locality, but none of these simple static ranks improves the primary exact horizon after the existing alternatives and repair have run. The useful follow-up would be a horizon-budgeted secondary selection: retain several greedy input ranks, reject any longer exact schedule, then choose the equal-horizon candidate with the smallest encoded rows. Static replacement of the captured order is not justified by this snapshot. ## 7. Candidate algorithms after exact endpoint search The global-search experiments establish three useful constraints on the next algorithm. Frozen-duration MILP and CP objectives are not reliable after the order changes, width-four exact beams rapidly converge to the same encoder state, and phase 3 has three tiles tied at the horizon. A useful search must therefore coordinate multiple endpoint rows, evaluate production encoder state, and traverse equal-horizon or temporarily worse schedules. ### Critical-block ejection chains (implemented experimentally) Treat every tile's send and receive direction as a separate job-shop resource. Move a short block on a critical endpoint; operations displaced by the move are in turn moved on their other endpoint resources until the chain closes. Reconstruct a memory-precedence-feasible global order and evaluate completed chains exactly. Apply initiating moves to every tied critical row and retain a tabu or threshold-accepted internal state so the search can cross the exact horizon plateau. The implemented three-round search reaches a one-bottleneck 16,418-cycle state from phase 3's three-way 16,388 plateau, then descends to a distinct order with the original 16,388 aggregate score. It does not find a strict horizon improvement. Phase 1 improves its intermediate equal-horizon tile-cycle sum, but retains the same final 5,466-cycle result after normal repair. On multicast phase 2, strict intensification of the winning terminal chain reduces the horizon from 48,086 to 48,059 cycles before reaching an exact plateau. Detailed construction and measurements are recorded in the global-search experiments. ### Compound frontier ejections (implemented experimentally) The phase-2 ejection sequence is not arbitrary. Before any ejection, the exact tile horizons already form the later critical frontier: tile 10 ends at 48,086, tiles 11 and 12 at 48,078, tile 8 at 48,076, and the following distinct levels continue through 48,060. Applying the winning one-position terminal chain once to each equal-horizon level reproduces the iterative search's ten strict descents. Each virtual pass performs only endpoint-sequence rotation and a memory-precedence topological reconstruction; the complete compound order is exact-materialized once. `--experimental-compound-ejection` reaches the same 48,059-cycle phase-2 result as iterative intensification with a 7.19-second warmed median, versus 65.30 seconds for the iterative experiment (and 76.56 seconds in the original recorded run). It is therefore orthogonal to the earlier residual-pressure improvement: pressure constructs the 48,086-cycle incumbent, while compound ejection changes 36 transfers near its terminal frontier to save another 27 cycles. The search stops when the next level is more than 32 cycles behind the incumbent or widens beyond two tied endpoints. It does not improve phases 0, 1, or 3 and remains experimental pending evidence on more snapshots. ### Deadline-driven branch-and-bound Search the decision problem "does a schedule of at most incumbent minus one cycle exist?" on the causal cone of the terminal critical rows. Advance exact encoder checkpoints, prune with endpoint-work and dependency-tail bounds, hash equivalent partial states, and learn no-goods from infeasible partial orders. Unlike plateau scoring, every branch is judged directly against the horizon improvement required for acceptance. ### Encoder-automaton CP-SAT Extract a compact row state containing receive source, address continuation, control fusion, alignment, and restart information. Model successor-dependent state transitions and their exact setup costs using circuit, table, or automaton constraints in a CP solver. Restrict this richer model to the critical cone; the previous experiments indicate that changing OR-Tools for a different solver without changing this state model would not address the main error. ### Endpoint-sequence column generation Generate complete exact sequences for individual critical send and receive resources as columns, then select compatible columns in a master problem which synchronizes each transfer and enforces semantic memory dependencies. Master dual prices guide generation of new endpoint sequences. This follows the hardware's natural decomposition while retaining exact local row costs, but global consistency makes it a substantially larger implementation. ### Exact MCTS or tabu large-neighborhood search Use endpoint block moves and ejection chains as actions, exact materialization as the evaluation, and retain a diverse archive keyed by horizon, tied-tile count, tile-cycle sum, and critical encoder-state signatures. Monte Carlo tree search, tabu search, or parallel tempering can intentionally cross plateaus which stop greedy exact beams. This cannot prove local infeasibility as a deadline search can, but is a practical broad-search fallback. ## Rejected priority experiments The following deterministic variants were exact-rematerialized but not kept: - Ranking endpoint pressure ahead of earliest start intentionally idled usable resources and produced a 17,395-cycle repaired phase-3 schedule. - Fully refreshing every heap entry after any pressure change produced a 49,112-cycle phase-2 schedule. Lazy refresh is useful because it changes the priority when a shared role becomes busy without globally perturbing an otherwise feasible wave. - Separating send and receive pressure in the priority, while superficially matching full duplex, produced a 50,164-cycle repaired phase-2 schedule. Tile control and memory interactions mean combined tile pressure remains the better empirical proxy. - A dependency-tail payload priority produced 16,390 cycles on phase 3, two cycles worse than the incumbent. - Unbounded maximum-cardinality matching waves produced 18,213 cycles on the high-degree phase 3. The bounded version remains enabled for phase 1. Phase 3's endpoint payload lower bound is especially optimistic. The critical tiles in the measured schedule each had 64 sends and 124 receives; receive control/route costs, rather than payload work alone, account for much of the gap. A matching-wave objective should include that cost before expecting a large improvement over 16,388 cycles.