Author: @sigkillme0
Date: 2026-08-30
Problem: 16x16 matmul
Cost: 66,178
IR: best_66178.ir
Method: exact LP relaxation of whole-program tier allocation, optimal-face search under complementary slackness
This submission keeps the 66,199/66,179 lineage’s operation order (4,096 multiplications, 3,840 additions, 1,649 copies, 17,777 paid reads) and changes only the address assignment. It comes with an unusual guarantee: 66,178 is provably the cheapest possible address assignment for this operation order.
The address-assignment problem for a fixed instruction order is: every SSA
value picks one address-cost tier (tier t holds the 2t-1 addresses at
read distance t), concurrent occupancy of a tier never exceeds its size, and
the objective is the total read-weighted distance. The full LP relaxation of
that problem — 272,619 assignment variables over all 10,097 live values and
27 tiers, with per-(tier, time) occupancy states — solves to optimality in
about 25 minutes (HiGHS interior point + crossover). Its optimum is exactly
66,178.
Floating-point LP output is not a proof, so the certificate is rebuilt in
exact arithmetic: the event-row duals are converted into interval capacity
multipliers y[tier][time] >= 0, rationalized by bounded-denominator
continued fractions, and the capacity Lagrangian
L(y) = - sum_t capacity_t * sum_time y[t][time]
+ sum_value min_t ( reads * t + sum_{time in lifetime} y[t][time] )
is evaluated over the integers. Weak duality makes L(y) a valid lower bound
for any nonnegative multipliers, so no solver tolerance is trusted; the
multipliers give L(y) = 66,178 exactly.
Because the bound is met with equality, any assignment costing 66,178 must
satisfy complementary slackness: every value sits on a tier attaining its
exact per-value minimum (8,506 values have more than one choice) and all
5,863 positive-multiplier (tier, time) capacities are exactly full. CP-SAT
decided this face-feasibility problem FEASIBLE and returned a complete
10,097-value assignment; per-tier optimal interval coloring materialized it
into the submitted IR. The point is 3,463 tier memberships (5,102 addresses)
away from the 66,179 predecessor, which is why local search never found it.
| tier | addrs | reads | cost |
|---|---|---|---|
| 1 | 1 | 5,171 | 5,171 |
| 2 | 2..4 | 4,984 | 9,968 |
| 3 | 5..9 | 2,386 | 7,158 |
| 4 | 10..16 | 854 | 3,416 |
| 5 | 17..25 | 1,089 | 5,445 |
| 6 | 26..36 | 1,321 | 7,926 |
| 7 | 37..49 | 308 | 2,156 |
| 8 | 50..64 | 105 | 840 |
| 9 | 65..81 | 119 | 1,071 |
| 10 | 82..100 | 133 | 1,330 |
| 11 | 101..121 | 147 | 1,617 |
| 12 | 122..144 | 143 | 1,716 |
| 13 | 145..169 | 123 | 1,599 |
| 14 | 170..196 | 108 | 1,512 |
| 15 | 197..225 | 88 | 1,320 |
| 16 | 226..256 | 93 | 1,488 |
| 17 | 257..289 | 99 | 1,683 |
| 18 | 290..324 | 71 | 1,278 |
| 19 | 325..361 | 74 | 1,406 |
| 20 | 362..400 | 78 | 1,560 |
| 21 | 401..441 | 78 | 1,638 |
| 22 | 442..484 | 43 | 946 |
| 23 | 485..529 | 45 | 1,035 |
| 24 | 530..576 | 47 | 1,128 |
| 25 | 577..625 | 49 | 1,225 |
| 26 | 626..676 | 21 | 546 |
| total | 17,777 | 66,178 |
| instruction | count | paid reads | read cost |
|---|---|---|---|
mul |
4,096 | 8,192 | 14,288 |
add |
3,840 | 7,680 | 26,086 |
copy |
1,649 | 1,649 | 21,433 |
| output exit | 256 | 256 | 4,371 |
| total | 9,585 ops | 17,777 | 66,178 |
Additional shape checks:
1..646.python3 matmul/submissions/best_66178.py
Observed locally:
best_66178.ir: score=66,178, sha256=dd5489cf946972837f38eaed2294abdaa7e56dee87ad6982081595e231518d22
formal proof: 256/256 outputs match over the free noncommutative integer polynomial ring
operations: {'add': 3840, 'copy': 1649, 'mul': 4096}
read costs: {'add': 26086, 'copy': 21433, 'mul': 14288, 'output': 4371}
Any further record on this operation order is impossible; improvement now requires a different instruction schedule or arithmetic circuit.