4 ms·

I believe that these good results are explained at least in part by the fact that NVIDIA does not provide detailed enough documentation for their GPUs. For a p

I believe that these good results are explained at least in part by the fact that NVIDIA does not provide detailed enough documentation for their GPUs. For a processor with well-documented microarchitecture, for which a programmer or a compiler can deterministically write an optimal program, it is much less likely that applying ML/AI can be successful, except as a substitute for searching already known solutions. On the other hand, for less documented microarchitectures, like of the NVIDIA GPUs, finding an optimal program may be impossible other than by doing a random search guided by examples of previous optimized programs, and possibly doing some reverse-engineering work to determine the real behavior of the GPU in some circumstances. Improving over something like this is likely to be feasible for ML/AI, where training over known good programs may be able to extract some of the undocumented behavior that may be non-obvious for humans reading those examples.

almostgotcaught 1y ago
[flagged]
- speerer 1y ago
  The point was about being able to write an optimal program with certainty, not about just getting the thing to operate.
  - almostgotcaught 1y ago
    [flagged]
- throwaway81523 1y ago
  The running time of a CUDA kernel is apparently impossible to determine except by experiment and measurement, and might be nondeterministic. By contrast for a more typical CPU, there's a compiler whose assembly output you can examine, and there's a processor manual that gives the cycle timing of each instruction. So you can compute the running time at least of inner loops that stay in cache, and that sort of thing.
  - almostgotcaught 1y ago
    > By contrast for a more typical CPU, there's a compiler whose assembly output you can examine, and there's a processor manual that gives the cycle timing of each instruction 1. You can dump the SASS that corresponds to PTX: `cuobjdump --dump-sass <input_file>` 2. Getting the cycle count of a single instruction for an OOO architecture is completely meaningless because you have no idea when the instruction will actually be issued. This is true for both AMDGPU and NV.
  - saagarjha 1y ago
    CPUs are generally a lot harder to reason about than GPUs because they run deeply OOO.
- pca006132 1y ago
  While I think the OP did not mean the compilation process is nondeterministic, I won't be surprised if it is actually non-deterministic. A lot of algorithms and data structures rely on nondeterminism for performance or security (by default). It is too easy to introduce nondeterminism accidentally, and it is tempting to use that to speed up algorithms. Also, if it relies on floating point, results on different machines and environments may be different (depending on libm and hardware implementation), which is, in some sense, nondeterministic.
  - almostgotcaught 1y ago
    > A lot of algorithms and data structures rely on nondeterminism for performance or security (by default). It is too easy to introduce nondeterminism accidentally. You don't know what you're talking about - no compiler engineer in their right mind would intentionally use a randomized algorithm in a compiler. It's a bug every single time and it gets squashed immediately.
    - pca006132 1y ago
      They won't use it intentionally, but it is not like it can never happen. E.g., https://reproducible.nixos.org/nixos-iso-minimal-r13y/ https://reproducible.nixos.org/nixos-iso-minimal-r13y/ is still only 96.59% reproducible.
fulafel 1y ago
Even with full information, we generally (or practically) aren't able to write optimal programs.
pca006132 1y ago
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/ 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.
- adrian_b 1y ago
  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.
  - pca006132 1y ago
    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.
david-gpu 1y ago
> 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.
- adrian_b 1y ago
  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.
  - saagarjha 1y ago
    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.
  - david-gpu 1y ago
    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.
mjlee 1y ago
> 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 https://www.nature.com/articles/s41586-022-05172-4
- hmry 1y ago
  For those who don't want to read the article: The previous best was 49 scalar multiplications.
  - mattkrause 1y ago
    And I believe some humans subsequently knocked it down to 47?
- adrian_b 1y ago
  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.

almostgotcaught 1y ago

[flagged]

speerer 1y ago
The point was about being able to write an optimal program with certainty, not about just getting the thing to operate.
- almostgotcaught 1y ago
  [flagged]
throwaway81523 1y ago
The running time of a CUDA kernel is apparently impossible to determine except by experiment and measurement, and might be nondeterministic. By contrast for a more typical CPU, there's a compiler whose assembly output you can examine, and there's a processor manual that gives the cycle timing of each instruction. So you can compute the running time at least of inner loops that stay in cache, and that sort of thing.
- almostgotcaught 1y ago
  > By contrast for a more typical CPU, there's a compiler whose assembly output you can examine, and there's a processor manual that gives the cycle timing of each instruction 1. You can dump the SASS that corresponds to PTX: `cuobjdump --dump-sass <input_file>` 2. Getting the cycle count of a single instruction for an OOO architecture is completely meaningless because you have no idea when the instruction will actually be issued. This is true for both AMDGPU and NV.
- saagarjha 1y ago
  CPUs are generally a lot harder to reason about than GPUs because they run deeply OOO.
pca006132 1y ago
While I think the OP did not mean the compilation process is nondeterministic, I won't be surprised if it is actually non-deterministic. A lot of algorithms and data structures rely on nondeterminism for performance or security (by default). It is too easy to introduce nondeterminism accidentally, and it is tempting to use that to speed up algorithms. Also, if it relies on floating point, results on different machines and environments may be different (depending on libm and hardware implementation), which is, in some sense, nondeterministic.
- almostgotcaught 1y ago
  > A lot of algorithms and data structures rely on nondeterminism for performance or security (by default). It is too easy to introduce nondeterminism accidentally. You don't know what you're talking about - no compiler engineer in their right mind would intentionally use a randomized algorithm in a compiler. It's a bug every single time and it gets squashed immediately.
  - pca006132 1y ago
    They won't use it intentionally, but it is not like it can never happen. E.g., https://reproducible.nixos.org/nixos-iso-minimal-r13y/ https://reproducible.nixos.org/nixos-iso-minimal-r13y/ is still only 96.59% reproducible.

fulafel 1y ago

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

pca006132 1y ago

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/ 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.

adrian_b 1y ago
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.
- pca006132 1y ago
  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.

david-gpu 1y ago

> 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.

adrian_b 1y ago
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.
- saagarjha 1y ago
  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.
- david-gpu 1y ago
  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.

mjlee 1y ago

> 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 https://www.nature.com/articles/s41586-022-05172-4

hmry 1y ago
For those who don't want to read the article: The previous best was 49 scalar multiplications.
- mattkrause 1y ago
  And I believe some humans subsequently knocked it down to 47?
adrian_b 1y ago
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.