sutro-problems

Matrix Multiplication

Author: @sigkillme0
Date: 2026-08-29
Problem: 16x16 matmul
Cost: 66,199
IR: best_66199.ir
Method: SSA recovery, dependency-safe rescheduling, and exact lifetime-tier allocation

Summary

Starting from the previous 66,300 physical-address IR, the optimization recovered its semantic SSA trace, applied dependency-safe schedule changes, and solved coordinated lifetime placement across address-cost tiers.

The result keeps 4,096 multiplications and 3,840 additions, uses four fewer copy operations and four fewer paid reads, and improves the score by 101 points to 66,199.

Cost Breakdown By Address Tier

tier addrs reads cost
1 1 5,171 5,171
2 2..4 4,995 9,990
3 5..9 2,373 7,119
4 10..16 855 3,420
5 17..25 1,089 5,445
6 26..36 1,321 7,926
7 37..49 307 2,149
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 145 1,740
13 145..169 122 1,586
14 170..196 108 1,512
15 197..225 87 1,305
16 226..256 93 1,488
17 257..289 99 1,683
18 290..324 70 1,260
19 325..361 74 1,406
20 362..400 78 1,560
21 401..441 81 1,701
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,199

Instruction Distribution

instruction count paid reads read cost
mul 4,096 8,192 14,272
add 3,840 7,680 26,088
copy 1,649 1,649 21,559
output exit 256 256 4,280
total 9,585 ops 17,777 66,199

Additional shape checks:

Verification

python3 matmul/submissions/best_66199.py

Observed locally:

best_66199.ir: score=66,199, sha256=16ecbd1a27eb779b8334fecbd2735ed001d3255b51ed0616cac830b79296cd7b
formal proof: 256/256 outputs match over the free noncommutative integer polynomial ring
operations: {'add': 3840, 'copy': 1649, 'mul': 4096}
read costs: {'add': 26088, 'copy': 21559, 'mul': 14272, 'output': 4280}