# Exchange scheduler global-search experiments This note covers optimization paradigms that do not construct a schedule by repeatedly choosing one ready transfer or one matching wave. All candidates still preserve semantic memory dependencies and are accepted only after exact production row materialization. ## Reduced-MILP shifting bottleneck The implemented experimental scheduler treats an exact incumbent as a disjunctive graph: - semantic memory dependencies are fixed arcs; - every send bus and receive bus contributes a resource sequence; - the tile at the exact event horizon is selected as the bottleneck; - that endpoint's sequence arcs are removed while every other resource sequence remains fixed; - release times and delivery tails are computed through the remaining DAG; - an eight-operation critical tail is solved as a single-machine MILP with release times, precedence constraints, pairwise disjunctions, and a makespan-plus-tail objective; - the solved sequence is placed back into the incumbent's global slots and exact-rematerialized. The MILP uses `good_lp` 1.15 with the pure-Rust `microlp` backend and a two-second per-core limit. Search may walk across equal-horizon incumbents internally, but the production result is replaced only by a strictly shorter exact horizon. Run the offline experiment with: ```bash cargo run --release -p ipu-tests --bin ipu-exchange-schedule-bench -- \ profiles/siglip-mlp-f16-b1.exchange-schedule.json \ --phase 3 --experimental-shifting-bottleneck --iterations 1 ``` ### Results The broad shifting-bottleneck variants were valid but inferior on phase 3: | Critical resequencing | Exact phase-3 horizon | | --- | ---: | | Incumbent | 16,388 | | Whole-endpoint Schrage sequence | 17,781 | | 16-operation MILP core | 16,832 | | Centered 8-operation MILP core | 16,550 | | Tail 8-operation MILP core | 16,388 | Phase 3 has three tiles tied at 16,388. Solving each tail in turn generated three different equal-horizon exact schedules, but their combination did not break the plateau. The experimental run took approximately 21.2 seconds, versus approximately 10.6 seconds for the default scheduler. Phase 1 also remained at 5,466 and phase 2's selected bottleneck core was already in the MILP-optimal approximate order. This is retained behind an explicit benchmark flag rather than added to normal compile time. The result is useful evidence that payload-duration release/tail models miss the sequence-dependent receive-control cost which dominates these critical rows. ## Other substantially different approaches ### Time-indexed RCPSP with Lagrangian relaxation Relax each send/receive capacity constraint into a time-dependent endpoint price, schedule every transfer against those prices and semantic precedences, then update prices by subgradient steps where capacity is exceeded. This gives a global lower bound and a fractional/preemptive schedule. Deterministic rounding plus exact materialization would produce candidates. Unlike list scheduling, contention is represented by dual prices across the whole phase. The main design question is the time grid. Payload words give a 4,800–48,000 cycle horizon, so a coarse grid followed by refinement around congested intervals is more practical than a per-cycle model. ### Benders decomposition around the exact row encoder Use a master problem to choose endpoint sequences and an exact-materialization subproblem to test instruction encodability, receive-stream transitions, and memory hazards. When exact materialization exposes a bad critical pattern, add a cut forbidding that local sequence or bounding its completion. This directly learns the quirks that the current payload-only approximate models miss. The challenge is deriving cuts stronger than simply excluding one complete order. A useful first cut family would cover receive-address cutovers which cannot be fused into sends on the same tile. ### Rolling multi-resource CP-SAT window The second implemented experiment jointly schedules a bounded tail across all of its interacting endpoint resources: - take the final 16 transfers from up to eight endpoints tied at the exact horizon; - expand by four predecessors and successors on every send and receive bus touched by those transfers, capped at 128 transfers; - give each selected transfer one integer start variable, retaining its exact incumbent route offsets and role durations; - add reified disjunctions for all selected/fixed and selected/selected same-direction bus conflicts; - add the same disjunctions for full-duplex send/receive pairs whose SRAM spans share an effective memory element; - preserve semantic memory dependencies and keep the relative global order of all transfers outside the window; - minimize the completion of the tied critical tile rows, translate the solved resource orientations back into a topological global order, then run the exact production materializer. This uses Google CP-SAT through the optional `cp_sat` 0.4.1 dependency. The published binding needs two small compatibility workarounds for OR-Tools 10: the renamed `OR_ORTOOLS_PROTO_DLL` define and an explicit link to the split `ortools_core` library. Normal builds do not enable or link CP-SAT. Run it with: ```bash cargo run --release -p ipu-tests --features experimental-cp-sat \ --bin ipu-exchange-schedule-bench -- \ profiles/siglip-mlp-f16-b1.exchange-schedule.json \ --phase 3 --experimental-critical-window --iterations 1 ``` #### Results The CP model found large improvements in its frozen-offset objective, but none survived exact materialization: | Phase / window | CP predicted horizon | Exact candidate horizon | Incumbent used by CP | | --- | ---: | ---: | ---: | | Phase 3, 30 transfers | 15,543 | 16,388 | 16,388 | | Phase 3, 108 transfers | 14,335 | 16,388 | 16,388 | | Phase 1, 50 transfers | 4,694 | 5,841 | 5,553 | The 108-transfer phase-3 candidate also worsened the exact plateau sum from 16,127,821 to 16,132,231 cycles. The production result and rolling incumbent advance only when the complete exact plateau tuple `(horizon, tied tiles, tile-cycle sum)` improves, so rejected candidates cannot displace the incumbent. The normal final results remain 16,388 for phase 3 and 5,466 for phase 1 after its existing exact critical-neighborhood repair. Multicast phase 2 is deliberately excluded from this first CP experiment. With the rejected candidate materialized once, the final phase-3 experimental run took 14.66 seconds, compared with roughly 10.6 seconds for the default scheduler on the same machine. Increasing the window made the model/exact discrepancy larger rather than smaller. The important missing state is not merely another resource interval: receive source selection, pointer cutovers, composite send/control encoding, and the timing shifts induced in nominally fixed transfers all depend on the chosen sequence. Incumbent role offsets therefore stop being predictive as soon as the order changes. This is direct evidence that a useful next global solver needs exact-encoder feedback, such as cuts learned from failed address cutovers, rather than a still larger frozen-offset interval model. #### Exact-encoder feedback cuts The CP experiment now treats production materialization as a logic-based Benders subproblem. When an exact candidate does not improve the incumbent, it adds one cumulative cut for each exact critical tile: - select a 12-transfer pattern centered on the last discontinuous destination address transition, or the exact role tail when no such transition exists; - forbid reproducing the complete local pair-order assignment; - identify the actual final transfer in the selected exact role tail and require a different transfer to follow it in the next master solution. This is encoder feedback rather than another approximate duration adjustment: the master cut is derived from the critical rows, address transitions, and terminal events produced by the exact row encoder. Four feedback rounds are enabled in the experiment. An exact plateau improvement clears the accumulated cuts and restarts the rolling window from the improved schedule. The cuts successfully force distinct exact schedules and change the CP bound, but they did not improve the canonical horizons: | Experiment | Best rejected exact result | Final selected result | | --- | ---: | ---: | | Phase 3, four feedback rounds | 16,388; tile sum 16,131,916 | 16,388; tile sum 16,127,821 | | Phase 1, ten feasible feedback rounds | 5,596 | 5,466 after existing repair | On phase 3, the first master solution predicted 14,335 cycles. Terminal cuts raised this to 14,343, but all three exact critical tiles stayed at 16,388. A 12-round saturation run applied 33 cumulative endpoint cuts; every candidate still had a 16,388-cycle horizon, the exact tile sum eventually worsened to 16,135,696, and scheduler/codegen time rose to 52.86 seconds. The four-round configuration took 26.06–26.54 seconds across a deterministic two-iteration replay. On phase 1, feedback diversified an initial 5,841-cycle exact candidate down to 5,596 cycles in round seven, still above the 5,553 matching-wave incumbent. After ten cut sets the CP master had no further feasible candidate. This shows that exact no-good/terminal cuts are being honored and can guide the exact outcome, but local permutation exclusion alone does not learn the roughly 2,000-cycle control-state gap seen on phase 3. A stronger next decomposition would need reusable transition-cost cuts or an exact incremental row-state model, not merely additional rejected permutations. #### Reusable exact transition costs The next feedback variant measures the setup omitted by each CP role interval. For an adjacent ordered pair on an exact critical send/receive row, it compares the exact separation of the two transfer anchors with the separation implied by their incumbent role offsets. A positive residual becomes a conditional constraint on the same `(tile, role, before, after)` tuple in later masters. Unlike a no-good, the constraint is reusable in any later solution containing that orientation; reversing the pair does not activate it. Duplicate observations retain the largest exact delay. On phase 3 the first failed materialization learned 114 costs, with a maximum 97-cycle residual. Four rounds accumulated 438 observations (334 were active in the final master) and raised the predicted horizon from 14,335 to 14,501. The exact horizon nevertheless stayed at 16,388. The best later exact plateau was `(16,388, 3, 16,132,021)`, slightly better than the first rejected candidate but still worse than the `(16,388, 3, 16,127,821)` incumbent. Runtime was 25.42 seconds for the deterministic offline replay. This closes part of the timing-model gap, but pair-local setup cannot represent the complete prefix-dependent receive-source and row-control state. The next experiment therefore evaluates moves by cloning and advancing exact encoder state rather than estimating their durations from fixed incumbent offsets. #### Incremental exact row-state window The first version of `--experimental-exact-row-window` checkpointed immediately before a 12-transfer terminal window. Its checkpoint had already reached the complete 16,388-cycle horizon, so the selected region was downstream of the decisions which formed the critical row state. The upstream version moves the frontier to the first critical-row activity within 4,096 cycles of the final horizon, starts 96 global transfers before that frontier, and rebuilds a 128-transfer window. It adds a non-mutating exact preview operation to the production scheduler: every dependency-ready choice is evaluated with real topology plans, receive-stream state, instruction alignment, and SRAM hazards without advancing the encoder. The current version retains a width-four beam of exact checkpoints. Per-tile encoder and SRAM-history states are copy-on-write, so a branch shares the 89,000-transfer prefix and copies only the source/receiver tiles it changes. At least one child per live parent survives each level before remaining slots are filled by the globally best partial exact scores. This prevents the beam from immediately collapsing onto one locally best parent. Every final beam state advances through the complete fixed suffix; only the best distinct order is fully rematerialized and validated. Preview/commit and checkpoint copy-on-write behavior are covered by a unit test. On phase 3 the frontier moved to rank 89,769 and the checkpoint before the window had a 12,188-cycle horizon, versus the 16,388 final horizon. The beam evaluated 32,640 exact alternatives. All four distinct final branches converged to the same exact plateau, `(16,388, 3, 16,128,493)`, and that preview exactly matched full rematerialization. This retained the horizon but worsened the incumbent tile sum by 672, so it was rejected. The run took 19.95 seconds. Phase 1's four branches likewise converged to the 5,553-cycle matching-wave plateau, after which the normal repair still produced 5,466. This rules out both one-step greedy commitment and a small exact beam on this contiguous upstream window. The remaining structural limitation is the window itself: 128 adjacent global transfers contain relatively few consecutive roles from any one critical endpoint. An endpoint-sequence beam or non-contiguous destroy set is more likely to preserve genuinely different receive-control states through the suffix. #### Non-contiguous exact endpoint-sequence beam `--experimental-exact-endpoint-beam` replaces the contiguous global window with a scattered destroy set. For each tile tied at the exact horizon, it selects 24 roles before and eight roles after the point 4,096 cycles upstream on that tile's bottleneck direction. The selected transfers keep their non-contiguous global slots, while a width-four beam assigns different selected transfers to those slots. Intervening unselected transfers are replayed in their incumbent order, semantic memory predecessors must be complete at every slot, and every choice advances a copy-on-write checkpoint of the production encoder. Complete branches replay the fixed suffix before comparison. On phase 3 this selected 96 transfers scattered from global ranks 83,105 to 90,357; the exact checkpoint at the first selected slot had a 9,166-cycle horizon. The beam evaluated 18,336 alternatives. All four branches reached the same fully rematerialized plateau, `(16,388, 3, 16,121,150)`. The exact horizon and number of tied tiles were unchanged, but the tile-cycle sum improved by 6,671 over the incumbent `(16,388, 3, 16,127,821)`. This is an order of magnitude larger plateau movement than the contiguous beam's 672-cycle loss, and confirms that preserving endpoint-sequence density matters. The improved plateau was retained as an internal search state but not returned as a production result, whose acceptance rule remains a strictly shorter horizon. A second endpoint-beam round was slightly worse at `(16,388, 3, 16,121,325)` and stopped the rolling search. Feeding the improved state into the existing critical-neighborhood repair also failed: its first candidate regressed to 18,114 cycles. The complete two-round experiment plus that rejected repair took approximately 32 seconds. On phase 1 only 11 transfers met the endpoint selection rule. They spanned almost the whole order and produced a 6,424-cycle candidate, well above the 5,553-cycle matching-wave state. This beam is therefore retained only behind the benchmark flag. It is the first exact search here to improve phase 3's plateau substantially, but shortening the horizon appears to require a move which changes all three tied terminal rows together rather than optimizing their locally visible upstream roles. #### Critical-block ejection chains `--experimental-ejection-chain` treats every tile's send and receive direction as a separate job-shop resource. Twelve deterministic templates move one- to four-transfer blocks either near the terminal critical block or at the 4,096-cycle upstream frontier. The initiating move is applied to every tied critical row. Each displaced transfer continues in the same direction on its other endpoint resources, recursively ejecting crossed transfers in the opposite direction for up to three links. Modified resource sequences are first requested as disjunctive-graph arcs alongside the semantic memory dependencies. When those requests form a cycle, the propagated rank changes instead guide a semantic-only topological reconstruction; the production encoder remains the final authority in both cases. Phase 3 also tries six heterogeneous patterns which apply the useful frontier move to only a subset of the three tied rows and a neutral terminal move to the remainder. Candidates share their exact prefix and advance copy-on-write encoder state only through their distinct suffixes. An initial three-round tabu exploration admits schedules up to 64 cycles above the selected production horizon. It prefers an exact horizon descent whenever one exists; otherwise it prefers fewer tied critical tiles. After a strict improvement, the search intensifies only the winning uniform template for up to 32 rounds and stops when neither the horizon nor the exact plateau improves. Production output is still replaced only by a strictly shorter exact horizon. On phase 3 the first round evaluated 18 chains from an exact shared prefix at global rank 76,812, whose horizon was 8,043 cycles. The best symmetry-breaking pattern used a frontier move on one critical row and neutral tail moves on the other two. It reached `(16,418, 1, 16,128,151)` directly. The next one-row frontier move descended to `(16,388, 3, 16,127,821)`: the incumbent aggregate score on a distinct order, but not a strict horizon improvement. The third round began another 16,440-cycle one-tile excursion. Thus the chains expose a repeatable transition between a three-way 16,388 plateau and a nearby single-bottleneck basin, but do not cross below the plateau. The three-round run took 53.54 seconds and exact validation passed. On phase 1, terminal chains improved the matching-wave plateau from `(5,553, 1, 6,573,803)` to `(5,553, 1, 6,573,077)` over two rounds. The normal critical-neighborhood repair still produced the unchanged final 5,466-cycle schedule. That experiment took 5.73 seconds. Phase 2 supplies the strict win. The smallest terminal template has fully acyclic resource arcs and repeatedly moves one final transfer one role earlier, then propagates eleven displacements through six endpoint resources. The first round reduced 48,086 to 48,078 cycles. Intensification continued through exact horizons 48,076, 48,074, 48,072, 48,070, 48,068, 48,065, 48,064, 48,060, and finally 48,059. This is a 27-cycle reduction from the previous selected schedule. Later equal-horizon states reduced the tied-tile count from ten to nine and the tile-cycle sum from 62,556,152 to 62,540,732; they were useful internal states but did not replace the strictly selected result. Search stopped when round 14 reproduced the same exact plateau. The complete run took 76.56 seconds and exact validation passed. The 27-cycle phase-2 gain demonstrates that ejection chains can cross a local endpoint-order minimum, but their host cost keeps this implementation behind the benchmark flag. Phase 3 still motivates deadline-driven search next: its useful one-bottleneck state is reachable, but a plateau/threshold walk lacks a direct signal for which next ordering can finish below 16,388. #### Compound water-filling of the terminal frontier The iterative phase-2 trace revealed that every next strict critical row was already visible in the original exact tile horizons. In descending distinct levels, its receive resources were: ```text 48,086: 10 48,078: 11, 12 48,076: 8 48,074: 9 48,072: 14 48,070: 13 48,068: 16 48,065: 20 48,064: 15, 18 48,060: 17 ``` This permits a compound `--experimental-compound-ejection` algorithm. Starting from the incumbent order, it visits these equal-horizon endpoint groups in order. At each level it applies template zero, propagates the displaced roles, and performs a cheap memory-precedence topological reconstruction. It updates the rank and endpoint sequences between virtual passes, preserving the causal semantics of iterative ejection, but does not rebuild exchange rows until all productive levels have been composed. The final order is then materialized and validated once; as with every experiment, it is selected only for a strictly shorter exact horizon. Two rejected batching models clarify why this works. Moving every tile below a cumulative slack waterline repeatedly was much too broad: its best candidate regressed phase 2 to 51,392 cycles. A learned-duration list-scheduling surrogate preserved the first 48,078-cycle state but then predicted the distant 649--665 receive group instead of the real 11/12 handoff. Exact encoder timing is still essential; the useful shortcut is that its initial per-tile frontier, not a payload surrogate, already supplies the batch order. An exploratory exact sweep confirmed the composition: | Composed frontier levels | Exact phase-2 horizon | Tied tiles | Tile-cycle sum | | ---: | ---: | ---: | ---: | | 2 | 48,076 | 1 | 62,680,281 | | 4 | 48,072 | 1 | 62,652,765 | | 6 | 48,068 | 1 | 62,625,173 | | 8 | 48,064 | 2 | 62,597,611 | | 10 | **48,059** | 10 | 62,556,152 | | 12 | 48,059 | 9 | 62,541,264 | | 14 | 51,546 | 1 | 62,549,861 | The implementation stops before a level wider than two tied endpoints or more than 32 cycles below the incumbent. On phase 2 that admits the ten strict descent levels and stops at the ten-way 48,059 plateau; continuing blindly to 14 levels crosses into a different regime. The resulting run initiates 12 endpoint moves, propagates 132 moves, changes 36 transfers across 72 resources, and retains fully acyclic resource arcs. It exactly matches the iterative search's selected aggregate and encoded row size (328,738 words). With one warmup and three measured release runs, compound ejection had a 7.19-second median. Iterative ejection took 65.30 seconds in the comparison build, 9.1x longer; the earlier recorded iterative run was 76.56 seconds, or 10.6x longer. The normal phase-2 scheduler took 5.03 seconds in a nearby run, so the compound search adds roughly two seconds rather than the iterative search's roughly one minute. Exact validation passed. The other phases retained their normal final horizons: phase 0 stayed at 7,179, phase 1 at 5,466, and phase 3 at 16,388. Phase 1 and phase 3 produced an equal-plateau compound candidate which was correctly rejected. The narrow- frontier rule now avoids a compound replay on phase 3's initial three-way tie. More snapshots are required before enabling the method by default. ### Population ruin-and-recreate with exact fitness The `--experimental-population-search` experiment changes paradigms from mathematical programming and strict local repair to a population metaheuristic: - destroy up to 256 transfers from the final 24 roles on every tied critical endpoint, expanded by three neighbors on all touched endpoints; - freeze only the relative order outside that neighborhood; - reconstruct a complete memory-precedence-feasible order with a deterministic randomized-rank topological sort; - fully materialize every individual with the production encoder; - retain the best three exact plateau scores, including worse individuals as parents, for six mutations. Allowing worse parents is the key difference from the existing hill climber: it can cross an exact plateau or valley without relaxing validation or schedule semantics. On phase 3 the first individual retained the 16,388 horizon but worsened the tile sum from 16,127,821 to 16,153,020. Another individual also retained 16,388 with a worse plateau; the rest ranged from 16,389 to 17,825 cycles, so the incumbent remained selected. The six-candidate run took 30.79 seconds. On phase 1 the mutations were much worse (6,942--8,106 cycles versus the 5,553 matching-wave parent), and the existing repair still produced the final 5,466-cycle schedule. This broad random-rank repair has enough reach to diversify, but destroys too much useful synchronization structure. A stronger population variant should repair endpoint sequences explicitly (for example with matching waves and address-continuity insertion), then use exact materialization only on the most promising diverse offspring. ### Preemptive optimum followed by packet-preserving rounding Solve the relaxed problem in which transfers may be preempted into word ranges, using max-flow over send/receive capacity. Placement and the final transfer set remain unchanged: the preemptive solution is only a lower bound and ordering guide. Round contiguous pieces back to each original indivisible transfer, then exact-rematerialize. The gap between relaxed and rounded schedules would also quantify how much indivisibility, rather than control encoding, costs.