# Exchange footprint model

Expanded-finalist selection now estimates encoded row storage from endpoint
geometry before placement or scheduling. The old estimate charged a full
nine-word primitive row for every TX/RX fragment. Scheduled rows share controls
and omit much of that primitive setup, so that estimate was a poor byte price.

The new ordinary-transfer estimate charges:

- 8 bytes per send for address setup and sending, plus 4 for a payload over 64 words;
- 8 bytes per receive for source/neutral controls;
- 4 bytes when the receive address differs from the preceding receive's end;
- 8 bytes per tile/phase for entry and return, rounded to eight-byte alignment.

Multicast transmission is counted once at the source. Before placement, receive
addresses are allocation ID plus byte offset, so separate allocations cannot
accidentally appear contiguous. Transfer lengths are split at the ISA limit.
Phase estimates accumulate on each tile before taking the maximum; Repeat bodies
contribute their stored program once. The existing geometry traversal supplies
these features without a second span expansion. The coarse mid beam estimate
has not changed: this refinement applies once concrete span geometry is available.

This is a ranking model, not an upper or lower bound. Capture order can differ
from scheduled order; scheduling changes pointer reuse, delays, bidirectional
instruction combinations and paired modes. Cross-phase normalized-row sharing was not predicted in the initial revision;
the structural sharing extension below now estimates it. The public capture estimator treats transfers as ordinary
Word32 equivalents, matching the pre-width-selection geometry model.

## Validation

Five large ordinary-transfer stages were compared with retained encoded results
in `artifacts/exchange-redesign-20260908/results.json`. These were not rescheduled.
B2 uses `vit-b2-f0.json`; B4 uses `vit-b4-f7.json` (phase IDs are not interchangeable
with those in `vit-b4-f2.json`). No empirical regression coefficients were fitted.

| Batch / phase | Old fragment-slot estimate | New estimate | Encoded bytes | Error | Estimate ms | Recorded scheduling ms |
| --- | ---: | ---: | ---: | ---: | ---: | ---: |
| B2 / 17 | 34,312 | 10,560 | 12,244 | -13.8% | 3.621 | 51,673 |
| B2 / 31 | 27,184 | 6,800 | 5,788 | +17.5% | 6.766 | 31,128 |
| B2 / 34 | 43,420 | 9,672 | 8,228 | +17.5% | 9.937 | 33,373 |
| B4 / 16 | 37,768 | 11,704 | 12,828 | -8.8% | 7.439 | 108,724 |
| B4 / 28 | 54,328 | 13,592 | 11,644 | +16.7% | 13.945 | 103,217 |

Old estimates in this table use captured endpoint counts, isolating the pricing
change from earlier logical-span fragmentation/coalescing differences. Times for
the new model exclude snapshot parsing, validation and geometry generation.

Three additional smaller B2 stages were then scheduled and validated with the
current scheduler, without changing the model:

| Phase | Estimated bytes | Encoded bytes | Error |
| --- | ---: | ---: | ---: |
| 0 | 32 | 36 | -11.1% |
| 1 | 136 | 152 | -10.5% |
| 2 | 664 | 648 | +2.5% |

The 64-phase B2 snapshot takes 57.8 ms for all footprint estimates and predicts
75,456 bytes on its busiest tile. The B4 snapshot predicts 96,368 bytes and takes
73.7 ms. These full-table estimates have not been compared with compact packages
for those exact snapshots; phase agreement does not establish whole-table
accuracy or current B2 build feasibility.

Results are under `artifacts/exchange-footprint/`. Reproduce estimates with:

```sh
target/release/ipu-exchange-schedule-bench \
  artifacts/exchange-redesign-20260908/vit-b2-f0.json --footprint-only
```

Omit `--footprint-only` and select `--phase 0 --phase 1 --phase 2` to reproduce the
held-out scheduling checks. The benchmark also reports estimates in ordinary
scheduling runs.

## Admission

Expanded candidates predicted within `exchange_table_budget_bytes` are ranked
before candidates predicted over it. Within budget, execution score (including
the configured storage penalty) orders candidates. If all are over budget, the
smallest predicted excess wins. The bounded admission shortlist retains the
minimum estimated storage alternative rather than the minimum raw fragment
count. An estimate alone never returns an infeasibility error: when all estimates
are too large, the smallest candidate can still be scheduled and checked exactly.
The separate hard fragment limit remains an explicit scheduling-effort safeguard.

Tests cover pointer continuity versus distinct allocations, per-tile phase
accumulation, Repeat storage reuse, priority for predicted-fit candidates, and
retaining an attempt when every estimate exceeds the budget. Full ViT builds
were not repeated for this change.


## Structural sharing extension

Each tile now hashes its ordered transfer routes, receiver fanout, payload lengths,
paired/ordinary mode and receive-pointer continuation decisions. Absolute memory
addresses are omitted. The planner uses the same accumulator on concrete spans;
the replay benchmark uses captured transfers. Encoded size and estimated patch
count also form part of the sharing key. These are per-tile signatures, allowing
unchanged rows to share even when other tiles have different work.

A repeated signature stores the estimated row once. On the second occurrence the
estimate adds shared patch offsets and address values for both invocations;
subsequent occurrences add only their address values. This also allows the model
to account for patch overhead exceeding the savings on short rows. Inactive rows
share without patch data. Sender rows with iterated source pointers are excluded,
matching the emitter's phase-specific treatment of Repeat patches.

Signature matches are predictions, not permission to share actual executable
code: placement, memory dependencies and global scheduling can change timing and
break sharing. The emitter still compares normalized encoded words exactly.
Hash collisions therefore affect only a heuristic estimate, never correctness.

On the retained captures, the updated model predicts:

| Capture | Without sharing | With sharing |
| --- | ---: | ---: |
| B2 finalist 0 | 75,456 bytes | 72,800 bytes |
| B4 finalist 7 | 96,368 bytes | 85,552 bytes |

Complete estimation with hashing took approximately 0.51 seconds per capture
(excluding snapshot parsing and validation). Results are in
`artifacts/exchange-footprint/{b2,b4}-sharing.log`. These are predicted savings;
no full package was rebuilt to measure actual savings for these captures.

Regression tests cover relocated compatible rows, address-value/offset storage,
inactive rows, changed routes and payloads, and exclusion of iterated senders.

## Full B2 build after structural sharing

On commit `b23d46f`, the full one-layer FP8 B2 ViT build exhausted all configured
storage-penalty retries and failed before hardware execution. Command and log:
`artifacts/vit/footprint-sharing-b2-fp8/{command.sh,run.log}`. The build used the
existing 64-KiB encoded-table budget and 16,384-fragment effort limit, with no
layout or precision overrides beyond the benchmark's usual FP8 scale -4.

| Storage penalty | Mid search ms | Expanded candidates | Admitted layouts | Encoded bytes |
| --- | ---: | ---: | ---: | ---: |
| 0 | 239,373 | 14 | 1 | 77,584 |
| 16 | 222,683 | 12 | 1 | 77,584 |
| 256 | 207,589 | 12 | 1 | 77,444 |

The complete selection took 1,170,051 ms (19.5 minutes), including 669,645 ms
(11.2 minutes) of repeated mid planning. Admission correctly avoided scheduling
all 38 expanded candidates, but the three attempts still found nearly identical
oversized tables and repeated a costly 52,812-transfer instruction-alignment
retry. The first selected estimate was 95,696 bytes against 77,584 encoded bytes
(23.3% high). The model recognized its storage risk; it did not recover a plan
under budget.

No new executable or hardware profile was produced. B1 was not rebuilt in this
validation. The previous successful B1 and older successful B2 results remain
historical evidence, not validation of current automatic B2 selection. Further
work needs to trace why the known compact complete plan is absent or loses
selection, and avoid repeating substantially equivalent failed work across
penalty retries. Increasing penalties alone did not solve this run.

## Wider shortlist experiment

Commit `063465d` separates three admission limits:

- `expanded_plan_finalists` / `--expanded-plan-finalists`: 16 complete plans per
  planning configuration, before packing variants and deduplication (previously 4).
- `placement_finalists` / `--placement-finalists`: 4 expanded candidates admitted
  to placement and mapping, plus a minimum-storage alternative if needed.
- `exchange_schedule_finalists`: the existing scheduling limit, default 1, with
  its minimum-storage alternative retained independently.

Both admission stages use the same budget-aware ranking. Geometry screening
precedes placement; widening the expansion shortlist therefore does not widen
placement or scheduling implicitly. Capture export uses the same expanded-plan
count as package selection. The beam remains 64 wide.

The B2 initial-search experiment is in
`artifacts/vit/wide-shortlist-b2-fp8/{command.sh,run.log,stop-reason.txt}`. It screened
62 complete expanded candidates, compared with 14 previously. None was predicted
to fit; the minimum remained exactly 95,696 bytes. Four candidates were placed
and mapped, then one was scheduled. Its encoded table remained exactly 77,584
bytes, exceeding the unchanged 65,536-byte limit. No package or hardware profile
was produced. The experiment was stopped after this first rejection; stronger
storage-penalty retries with the wider shortlist were deliberately not tested.

Timing on this run:

- Mid search: 239.708 seconds (previous initial run: 239.373 seconds).
- Mid completion to placement admission: 73.723 seconds for 62 candidates.
- Individual expansion wall times under parallel load: 23.836–36.819 seconds,
  median 28.880 seconds.
- Additional footprint pass: 1.875–4.377 seconds, median 2.623 seconds. This
  includes span matching, unlike snapshot-only model timings above.
- Placement/mapping admission to scheduling admission: 7.857 seconds.
- Scheduling admission to encoded-table rejection: 107.277 seconds.

The broader initial shortlist did not recover a compact plan. This rules out a
simple increase from four to sixteen returned plans as a sufficient fix for this
initial search; it does not establish that all possible beam candidates or
stronger-penalty searches fail. Candidate generation and earlier beam retention
remain the next places to trace against the older successful B2 plan.

Validation: 186 codegen tests and the doctest passed (4 ignored), and Clippy
passed for codegen and tests. The selection regression tests cover preservation
of compact alternatives and bounded work after package rejection.