Author: @cosminscn and Codex
Date: 2026-09-04 (UTC)
Problem: 16x16 matmul
Cost: 64,431
The program keeps the classical 4,096 scalar products and changes when values
are staged, accumulated, and released. Columns are split into panels of widths
6 and 10. The first panel visits row groups 4+4+4+4; the second visits
5+5+6. Contractions are consumed in chunks of one and two terms respectively,
with per-tile rotations 3,11,0,0,0,0,4. Alternating column traversal shortens
the handoff between neighboring tiles.
For B columns 8–15, the first staged copy of each B[k,j] is retained for later
row groups. Those 128 persistent captures replace 256 later reads from the
original B addresses. The tradeoff is longer live ranges, which the row/column
geometry and physical allocator arrange around the cheapest address tiers.
Five dependency-safe block moves adjust the operation order before allocation.
Each row uses zero-based positions in the list produced by the preceding row:
remove operations[source:source+length], then insert the block at
destination in the shortened list.
| Step | Source | Destination | Length |
|---|---|---|---|
| 1 | 7902 | 7905 | 2 |
| 2 | 7893 | 7991 | 1 |
| 3 | 1823 | 1825 | 1 |
| 4 | 226 | 222 | 4 |
| 5 | 1281 | 1287 | 1 |
The moves preserve every instruction and operand. Every source still precedes
its use, and the arithmetic/copy graph is unchanged. Weighted lifetime-chain
initialization followed by pair-tier allocation (2 rounds with seed 0, then
5 with seed 11) produces the submitted physical assignment. Each selected
two-tier flow problem is solved exactly; the complete allocator is heuristic.
| Instruction | Count | Paid reads | Read cost |
|---|---|---|---|
mul |
4,096 | 8,192 | 19,352 |
add |
3,840 | 7,680 | 20,751 |
copy |
1,504 | 1,504 | 19,884 |
| Output exit | — | 256 | 4,444 |
| Total | 9,440 | 17,632 | 64,431 |
All 512 inputs are present at entry. Every source read and all 256 output reads
pay ceil(sqrt(address)). Physical reuse follows read-before-write semantics.
No global optimality claim is made.
From the repository root:
python3 -S matmul/submissions/best_64431.py
python3 -S -m unittest matmul.test_record_64431 -v
python3 -m pip install -r matmul/submissions/search_64431/requirements.txt
python3 matmul/submissions/search_64431/reproduce.py
The standard-library verifier checks all 256 outputs with the official scorer and an independent exact noncommutative-polynomial proof. It also checks the frozen artifact hash, operation counts, and per-instruction read costs. The portable replay rebuilds the raw schedule, applies the five moves, verifies every intermediate program, allocates addresses, and reproduces the submitted IR byte for byte. It needs no research checkout, native extension, or compiler.
SHA-256: 9d94114a87fecd30168fbcf63931bbc98a50778984a11fe0c3b16940218bcf11.
The construction builds on the repository’s column-major staging, value-lifetime coloring, and cheap-capture work. The snake traversal follows the direction explored by Juraj Selep in PR #50. Credit also goes to @sigkillme0 for the 66,178 record and its exact fixed-order allocation analysis.