# Exchange scheduler optimization brief

## Objective

Improve the physical exchange scheduler's generated event horizon and its host
compile time without weakening correctness. The main target is the canonical
1472-tile FP16 SigLIP MLP snapshot already present at:

`profiles/siglip-mlp-f16-b1.exchange-schedule.json`

This is an ignored, local 14 MiB JSON file containing 114,128 address-resolved
physical transfers across four exchange phases. It is captured after logical
transfer splitting/coalescing and placement, but before physical scheduling.
It is therefore suitable for repeatedly changing the scheduler without running
the planner, compiler toolchain, package builder, driver, or hardware.

Optimize globally for the maximum per-tile event horizon, not the sum of
transfer completion times. Sending and receiving can overlap on one tile. Two
sends or two receives cannot overlap because each direction has one bus. A
simultaneous send and receive must not access the same effective SRAM memory
element during their memory hazard windows.

## Running the benchmark

Build and replay all captured phases:

```bash
cargo run --release -p ipu-tests --bin ipu-exchange-schedule-bench -- \
  profiles/siglip-mlp-f16-b1.exchange-schedule.json --iterations 1
```

Iterate on one phase, with repeated deterministic runs:

```bash
cargo run --release -p ipu-tests --bin ipu-exchange-schedule-bench -- \
  profiles/siglip-mlp-f16-b1.exchange-schedule.json \
  --phase 2 --warmup 1 --iterations 3
```

The reported `scheduleCodegen*Ms` includes the production ordering algorithm,
exact transfer timing, and production exchange-row construction. The separately
reported `validationMedianMs` checks the captured transfer set against the
activities and decoded rows. Every measured run is validated. Multiple runs
must produce identical `PhysicalExchangePhase` values.

To capture a different program build without loading hardware:

```bash
cargo run --release -p ipu-tests --bin ipu-trivial-test -- \
  c600-init.ipucfg --workload siglip-mlp-benchmark --mlp-batch 1 \
  --tiles 1472 --no-profile \
  --export-exchange-schedule profiles/another.exchange-schedule.json
```

## Baseline

The initial release-mode run on 2026-08-15 produced:

| Phase | Transfers | Destinations | Initial horizon | Selected horizon | Endpoint lower bound | Approx. scheduler/codegen |
| ---: | ---: | ---: | ---: | ---: | ---: | ---: |
| 0 | 736 | 2,208 | 7,179 | 7,179 | 6,912 | 0.012 s |
| 1 | 16,140 | 16,140 | 5,796 | 5,692 | 3,384 | 0.54 s |
| 2 | 6,244 | 100,896 | 48,293 | 48,293 | 28,560 | 5.06 s |
| 3 | 91,008 | 91,008 | 16,388 | 16,388 | 4,800 | 10.72 s |

Phase 1 is the only phase improved by the current repair pass: one
critical-neighborhood iteration saves 104 cycles. Phases 2 and 3 have large
lower-bound gaps and are the main schedule-quality targets. The endpoint bound
only counts directional payload work; route/control and memory hazards make it
optimistic.

## Relevant implementation

The scheduler and replay interface are in
`crates/ipu-codegen/src/exchange.rs`:

- `PendingTransfer`: one multicast hyperedge with fixed source/destination
  addresses and a word count.
- `memory_dependencies`: preserves semantic ordering for overlapping SRAM
  reads/writes while leaving independent transfers reorderable.
- `TransferScheduler`: incremental greedy list scheduler. It selects the
  dependency-ready transfer with the earliest endpoint availability, then uses
  remaining endpoint word pressure, fanout, size, and stable IDs as tie-breaks.
- `MaterializedSchedule::append` and `append_transfer`: query exact topology,
  instruction encodability, receive-stream state, and SRAM-element hazards.
- `critical_neighborhood_order`: traces the incumbent critical chain and
  constructs one approximate reordered neighborhood. Its inner model uses
  payload words and endpoint availability rather than exact row timings; the
  resulting full order is subsequently rematerialized exactly.
- `optimize_pending_schedule`: accepts only a strictly smaller exact horizon.
- `schedule_exchange_problem`: reconstructs a production scheduling problem
  from the captured snapshot and runs ordering plus row codegen.
- `validate_exchange_schedule`: independently checks transfer conservation,
  role intervals, send/receive SRAM hazards, active state, and decoded row
  horizons.

The phase-wide row builder and instruction-level validation are in
`crates/ipu-exchange/src/lib.rs`, principally `PhaseProgramBuilder`. It builds
each tile row from the complete scheduled phase, allowing receive controls to
be fused into sends and permitting legal full-duplex operation. Do not replace
this with concatenated primitive rows or serialize all send/receive roles.

Instruction semantics and reverse-engineering evidence are summarized in
`docs/EXCHANGE_INSTRUCTION_REFERENCE.md`. Additional SDK oracle programs live
in the sibling `../ipu-exchange-re` repository. The interconnect patent figure
used during the full-duplex work is at
`../US11321272-20220503-D00005.png`.

## Constraints and suggested approach

1. Keep placement and transfer formation fixed while using this snapshot. A
   better result must come from scheduling, exact timing/codegen, or an
   implementation-speed improvement, not by silently changing the workload.
2. Preserve memory-dependency order. In particular, write/write and
   read/write ordering exists for program semantics, not merely conservative
   bus scheduling.
3. Preserve full duplex. Same-role payload intervals are exclusive, but a send
   and receive may overlap when the instruction stream is encodable and their
   SRAM memory-element hazard windows are disjoint.
4. Evaluate candidates with exact rematerialization before claiming a horizon
   improvement. Approximate models are suitable for search guidance only.
5. Keep deterministic stable tie-breaking. The benchmark compares complete
   output phases across repeated runs.
6. Run `cargo test --workspace` before handing changes back. Add randomized
   property tests for new general scheduler rules; avoid tests that simply
   restate particular constants or one captured schedule.

Useful first investigations:

- Profile phases 2 and 3 separately to distinguish repeated exact
  rematerialization, dependency construction, heap churn, topology planning,
  and final row encoding.
- Compute critical-chain and per-endpoint slack information once, then retain
  multiple promising orders or neighborhoods rather than making one greedy
  repair proposal.
- Improve the search objective using exact or safely bounded endpoint release
  times. Large multicast fanout makes phase 2 qualitatively different from the
  many point-to-point transfers in phase 3.
- Cache schedule-independent transfer plans and timing data where correctness
  permits. Do not cache state-dependent receive-stream cutovers as though they
  were independent of surrounding transfers.
- Track both schedule quality (cycles and lower-bound gap) and compiler wall
  time. A slower algorithm is acceptable if it produces a material runtime
  improvement, but phase 3 should remain practical for iterative work.

The branch starts at commit `e957082` (`Add offline exchange scheduling
benchmark`). Keep scheduler work and benchmark baselines on this branch so it
can be compared or merged independently of mainline profiler/UI work.