> For a processor with well-documented microarchitecture, for which a programmer or a compiler can deterministically write an optimal program
We don't even know the optimal algorithms! AlphaEvolve recently found "an algorithm to multiply 4x4 complex-valued matrices using 48 scalar multiplications, improving upon Strassen’s 1969 algorithm that was previously known as the best in this setting." - https://www.nature.com/articles/s41586-022-05172-4
I was not referring to algorithm designing, but to algorithm implementation on a given processor, which consists in things like register allocation, machine instruction selection and static instruction scheduling.
We don't even know the optimal algorithms! AlphaEvolve recently found "an algorithm to multiply 4x4 complex-valued matrices using 48 scalar multiplications, improving upon Strassen’s 1969 algorithm that was previously known as the best in this setting." - https://www.nature.com/articles/s41586-022-05172-4