# GEMM partition solver

The production path now branches over partition domains before constructing
layouts. The preceding implementation eagerly enumerated complete assignments
and only then pruned them. Exhaustive grid construction remains in tests as an
oracle, not in production candidate generation.

## Construction and search

`planner/gemm/mod.rs` defines the problem and constructs an assigned GEMM;
`planner/gemm/solver.rs` searches its partitions. For each external input/output
layout combination:

1. Search independent orientation, batch/head partition, resident-weight format
   and weight-memory-class branches in parallel.
2. Propagate the available tile count through M/N/K split domains. Bound local
   panel sizes, individual allocations and compute cycles before creating any
   operand/result layouts. Reject impossible allocations and domains dominated
   by an incumbent in the local model.
3. Split a remaining domain, visiting smaller local panels first. Only complete
   surviving assignments construct tile-order and reduction-owner alternatives.
4. Cost preparation once for each shared compute geometry, then its reduction
   alternatives. Retain the uncapped local cycle/memory Pareto frontier.
5. Construct executable MidGraphs for survivors. Copy composition, detailed mid
   costing, global DP, and low-cost reranking follow through the existing path.

This is a finite-domain branch-and-bound solver with constraint propagation;
it does not use a general CP library or introduce a symbolic model language.
Kernel code supplies the compute lower bound. Approximate communication costs
do not participate in bounds on unfinished partition domains.

Resident parameters have balanced unreplicated packed homes, independently of
compute replication. Merely stripping replicas from a compute layout had left
some weights concentrated on a small subset of the tiles. The baseline resident
home remains an alternative, and shared parameters still have one home.

GEMM outputs now offer balanced ordinary and transposed packed layouts alongside
the row-major defaults. Existing layout propagation carries these through
elementwise operations. Compatible reduction outputs may use the requested
boundary directly. These are regular distributed layouts, not benchmark-specific
grids or new low-level operations.

## Costing and limitations

Complete assignments use kernel estimates, communication volume, residency and
temporary peaks. Compatible packed micro-panels do not incur a fictitious dense
unpack/repack. Replicated receivers in compatible default tile orders get the
paired-receive bandwidth discount; sender traffic is not discounted.

Generic permutations use the same copy coalescing, word-width selection and
helper pricing as lowering. In particular, scalar halfword copies are much
slower than dense memcpy. Semantic exchanges from subword source runs also need
local gathering before transmission; both local and detailed mid models charge
this work. Hardware regression testing exposed this missing term when packed
boundaries first became available.

Copy composition also preserves a specialized source unpack before conversion
to an incompatible packed order. Previously, joining selected fragments could
erase the efficient unpack/repack sequence that DP had priced, replacing it with
scalar halfword gathers. More accurate gather pricing alone did not fix that
post-selection rewrite.

These remain approximations. Source-gather pricing uses a representative whole
shard; splitting it among receivers can change helper launch costs. Volume
costing cannot reproduce fragmentation, exchange ordering or conflicts. Local
memory objectives combine shard maxima rather than exact physical-owner
liveness. Bounds preserve the local model's optimum over the partition domains,
not hardware runtime,
placement feasibility or global dominance between different parameter layouts.
Detailed costing and placement still validate complete plans.

## Measurements

Standalone batch-one MLP: 729 tokens, 1152 input/output channels, 4304 expanded
channels, no biases, 1472 compute tiles. Device cycles use the profile renderer's
normalized interval. Host transfers and reference computation are excluded.

| FP16 version | Device cycles |
| --- | ---: |
| Previous eager-assignment solver | 270,408 |
| Partition solver alone | 270,408 |
| Balanced homes, packed boundaries, corrected permutation prices | 213,846 |
| Direct compatible reduction outputs | 213,726 |
| Same, with 32 low finalists instead of 8 | 213,726 |
| Final gather-cost and composition corrections | 213,732 |
| SDK 3.4 reference | 204,243 |

The final plan is 21.0% faster than the starting version, but still takes
4.6% more cycles than the SDK. Increasing low reranking width did not help and
the original defaults remain. The partition solver alone did not find a faster
plan: resident/boundary choices and faithful preparation prices were necessary.
See [the SDK comparison](SDK_STANDALONE_MLP_2026_09_22.md) for instrumentation
differences and the reconstructed SDK partitions.

The FP16 numerical checks passed with maximum absolute error 0.001465. Initial
packed-boundary FP8 testing exposed a regression to 446,832 cycles, dominated
by source halfword gathering. That experiment prompted the source-gather cost
correction and unpack-composition fix; it is not a successful performance result.

With both fixes, FP8 runs in **155,826 normalized cycles**, versus the preceding
186,258: a 16.3% improvement. The full hardware reference check passes at maximum
absolute error 0.006042. There is no measured standalone SDK FP8 result here;
this must not be described as an equal-precision SDK comparison.

Planning is not demonstrated faster overall. Construction through low reranking
took approximately 93 seconds for the initial partition rewrite, 174 seconds
with the additional boundaries/reduction choices, and 253 seconds with 32
finalists. The starting version took 98 seconds. Concurrent development work
makes these diagnostic timings, not controlled throughput benchmarks.
The final builds took approximately 187 seconds for FP16 and 160 for FP8 through
low reranking, while running concurrently.

Artifacts: `artifacts/sdk-partition-solver-20260923/`. `branch`, `priced`,
`direct`, and `wide` correspond to the intermediate FP16 results above.
`packed` and `aligned` are failed costing experiments. `f8` is the regressed
FP8 experiment; `f16-gather` and `f8-gather` test the source-gather correction.
Final composition-corrected builds are `f16-unpack` and `f8-unpack`. Rendered
profiles are `profiles/siglip-mlp-f16-b1-partition-solver.html` and
`profiles/siglip-mlp-f8-b1-partition-solver.html`.

## Validation

Randomized tests compare the partition solver with exhaustive optima at memory
tradeoff boundaries, and check lower bounds against batched, transposed and
quantized completions. Distributed GEMM construction is numerically interpreted
and lowered. Copy-cost tests compare estimates with ordinary low expansion,
including generic strided/halfword permutations and packed-to-packed gathering.
The hardware MLP fixture checks full randomized outputs against its numerical
reference. The final suite passed 312 unit tests and the doctest, with five
explicit opt-in tests ignored. Passing these checks does not establish globally
accurate ranking.