Hacker News Reader

> 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

For those who don't want to read the article: The previous best was 49 scalar multiplications.

And I believe some humans subsequently knocked it down to 47?

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.

> For a processor with well-documented microarchitecture, for which a programmer or a compiler can deterministically write an optimal program

You severely underestimate the landscape of possible implementations for these kernels. There are many ways of performing a matrix multiplication and predicting which one will perform best without running them all is nontrivial, even with perfect knowledge of the underlying system.

This is just a completely incorrect take, speaking as a former insider.

If you cannot predict the running time of an algorithm without running it on the target processor, then by definition the documentation of that processor is incomplete.

For a processor that is completely documented one must be able to run a simulation model that provides the running time for a given program, when the processor is so complex that simpler methods for computing the execution time do not work.

For older NVIDIA GPUs, there exist such simulation models, but they are only partially accurate, because they are based on reverse engineering, without cooperation from the GPU vendor.

Nobody writing high-performance code for these machines has that documentation. They largely do ok anyway because the time of cycle counting is long in the past and the name of the game involves cache effects and synchronization that is very hard to reason about individually but clearly visible if taken in aggregate. You don't get a cookie if you can accurately time 10 instructions, but you do if your matrix multiply over a hundred million of them is 1% faster.

The point being made is that in a production environment you cant't run/simulate all the possible candidate implementations to find out the fastest one -- it would take far longer than just choosing one at random. Therefore, you need an algorithmic way of picking a good candidate out of the many you have, and you can't take forever to make that selection either, because the clock is ticking the moment you receive a request to run that matrix multiply.

You can't precompute all the possible options in advance and fetch the running time from a database either, because the parameter space is just way too huge.

Notice that none of this has anything to do with having accurate models of the system. This is what people who do this for a living and have perfect knowledge of the system choose to do, for good reasons.

While it is decidable, people typically never produce optimal programs even for the hot path. It is just intractable and too slow to do right now.

For register allocation and instruction selection, there is hope because it is FPT and there are algorithms to do it optimally in polynomial time, albeit with a large constant factor (FPT), making it impractical to apply to compilers as of today. For instruction scheduling, it is just too hard. If you read literature on scheduling algorithms, it is NP-hard for apparently simple instances, e.g., 2 parallel identical machines with no preemption and bounding completion time (https://www2.informatik.uni-osnabrueck.de/knust/class/), while actual microarchitecture is much more complicated than this...

Needless to say, these are already the simpler problems. The longer the program or the more profiling data you can optimize for, the more tricks you can throw at it, and most of them are NP-hard to optimize optimally.

Being NP-hard doesn't imply that you can't obtain the optimal result, but compilers that I know of do not implement them, because most users are not willing to wait for days for such a compilation to complete. Ideally, one should make something that can run on clusters of CPUs or GPUs to optimize this, and people having those clusters will typically be willing to do this because they want to optimize the program they later run on the clusters. However, to my knowledge, no one is working on this at the moment.

While you are right that in general it may be very difficult or quasi-impossible to generate optimal programs, there are also plenty of cases where an optimal program is achievable.

The latter happens when there is one dominant bottleneck for the algorithm, which is determined by the hardware, e.g. the maximum throughput of a certain instruction, like multiplication or memory load. When the implemented program reaches a throughput almost equal with that absolute limit, then one can be certain of its optimality.

Yeah, in that case I guess it is usually memory-bound? When it is memory-bound you don't really care that much about scheduling etc.

Matrix multiplies are typically compute bound, but you don't get much option to improve the actual algorithm because Nvidia gives you an accelerator for one and anything else would be slower.

Even with full information, we generally (or practically) aren't able to write optimal programs.