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.

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.

The point was about being able to write an optimal program with certainty, not about just getting the thing to operate.