4 ms·

I strongly disagree. Bitwise reproducibility would make it impossible to change or improve matrix multiplication algorithms, since the order of operations matt

I strongly disagree. Bitwise reproducibility would make it impossible to change or improve matrix multiplication algorithms, since the order of operations matters, and will change across implementations. Do we really expect everyone who does linear regression to say "I did linear regression, using the following implementation of a linear solver". Because that's what is being asked. A much better alternative is to test that algorithms give expected answers (within some tolerance) on simulated but non-trivial data. It will still require some care to distinguish bugs from rounding errors, but it is more, er realistic, than expecting bitwise reproducibility.

yarvin9 11y ago
Not to be too harsh, but this seems like the kind of thinking that leads to solutions like the leap second. For the sake of an optimization in an important but specialized corner case, you abandon a general principle of universal applicability (repeatable computing, chronological time). Maybe the optimization is important. In that case, couldn't you add another layer devoted to that special case? For instance, reorder matrix multiplies in a source-to-source transformation? Put leap seconds in the presentation layer, not the chronology layer? Everyone who does linear regression for the purposes of publishing a scientific paper should post their code and data, so that anyone else can recompute it and get the same bits. How is this controversial in 2015?
- JesperRavn 11y ago
  It's not harsh to me, since you are critiquing the work of some of the best experts in the world, not me. What do you mean by "reorder matrix multiplies in a source-to-source transformation?" To be clear, the issue is that matrix multiplication (which forms the basis for a huge part of numerical computing) is only deterministic when the order of operations is known. But any kind of fast algorithm is going to have a highly complex order of operations that depends on the algorithm and parameters. You can't reorder these back to some canonical order without completely changing the algorithm (and destroying its performance gains). Given the above, posting code and data won't be enough for binary reproducibility. Source code for every dependency would be needed too. As I noted I do support testing and reproducibility, just not at the level of binary data.
  - yarvin9 11y ago
    Yes, source code for every dependency is needed too! This is a classic source-to-source transformation problem. You have an abstract matrix multiplication algebra which needs to be converted into a deterministic algorithm with a known order of operations. You need a second algorithm, essentially a macro, which converts the abstract operation into the concrete operations, which are then compiled to deterministic code. This macro should itself be deterministic, even if its inputs contain information about local hardware configuration that's needed to make the optimized code run as fast as possible. If this information is in your data set, it's in your data set. Optimization is typically much less important to the reproduction pass, so a reproduction will probably just use your configuration details rather than those matched to the reproducer's machine. Either way, both algorithms are deterministic and the result is reproducible. What's wrong with this picture? I ask because I genuinely want to know :-) [Edit: it's disappointing to see "disagree == downvote" applied to the parent.]
    - CJefferson 11y ago
      The main problem is that with floating point numbers, (a+b)+c is different to a+(b+c), so almost any change can produce slightly different answers. Also we have the problem of what is "right"? Maybe your first implementation does (a+b)+c, then someone finds doing (a+c)+b gives a more accurate answer. Should we change? Then you are given two CPUs. If I want to do x1 + x2 + ... + xn, then obvious thing to do is going to be to give each CPU half the input data. But now however I split will give me a (slightly) different answer. With matrix multiplication this is much worse -- all algorithms chop the matrix into little pieces in different ways, each giving a slightly different answer. Even if you try to define some plain simple algorithm, it will usually give a less accurate answer, due to how the floating point rounded! With integer matrices on finite fields, it is much easier to get what you want, 100% reproducability.
      - yarvin9 11y ago
        Let me say the same thing perhaps more clearly: there isn't any nondeterminism here, just failure to capture the inputs and outputs of a deterministic code transformation. Suppose CPU count is the configuration input. Then you have a deterministic macro function M(nCPU, abstract program) => concrete program. And another deterministic function C(concrete program) => CPU instructions. Now nCPU is no longer a random piece of information randomly found in your environment: it's data in your data set. And your results are bitwise reproducible. With a reproducible toolchain, I can use a 1-CPU machine to get the same results as you did on your 32-CPU machine, by using the same data set (including your nCPU=32). Why? Because I'm reproducing your results and I care more about precision than performance.
khinsen 11y ago
Your comment is a nice example of the frequent misunderstandings concerning bitwise reproducibility. My article argues that infrastructure tools (compilers, runtimes, ...) should ensure bitwise reproducibility, making it possible for a programmer to define a computational result exactly through a program's source code. This does not mean that we can't have different algorithms. It doesn't even mean that no compiler could ever re-arrange operations for optimization. The latter could well be enabled through a compiler option. All I am asking for is that infrastructure tools leave all these choices to the programmer.

yarvin9 11y ago

Not to be too harsh, but this seems like the kind of thinking that leads to solutions like the leap second. For the sake of an optimization in an important but specialized corner case, you abandon a general principle of universal applicability (repeatable computing, chronological time). Maybe the optimization is important. In that case, couldn't you add another layer devoted to that special case? For instance, reorder matrix multiplies in a source-to-source transformation? Put leap seconds in the presentation layer, not the chronology layer? Everyone who does linear regression for the purposes of publishing a scientific paper should post their code and data, so that anyone else can recompute it and get the same bits. How is this controversial in 2015?

JesperRavn 11y ago
It's not harsh to me, since you are critiquing the work of some of the best experts in the world, not me. What do you mean by "reorder matrix multiplies in a source-to-source transformation?" To be clear, the issue is that matrix multiplication (which forms the basis for a huge part of numerical computing) is only deterministic when the order of operations is known. But any kind of fast algorithm is going to have a highly complex order of operations that depends on the algorithm and parameters. You can't reorder these back to some canonical order without completely changing the algorithm (and destroying its performance gains). Given the above, posting code and data won't be enough for binary reproducibility. Source code for every dependency would be needed too. As I noted I do support testing and reproducibility, just not at the level of binary data.
- yarvin9 11y ago
  Yes, source code for every dependency is needed too! This is a classic source-to-source transformation problem. You have an abstract matrix multiplication algebra which needs to be converted into a deterministic algorithm with a known order of operations. You need a second algorithm, essentially a macro, which converts the abstract operation into the concrete operations, which are then compiled to deterministic code. This macro should itself be deterministic, even if its inputs contain information about local hardware configuration that's needed to make the optimized code run as fast as possible. If this information is in your data set, it's in your data set. Optimization is typically much less important to the reproduction pass, so a reproduction will probably just use your configuration details rather than those matched to the reproducer's machine. Either way, both algorithms are deterministic and the result is reproducible. What's wrong with this picture? I ask because I genuinely want to know :-) [Edit: it's disappointing to see "disagree == downvote" applied to the parent.]
  - CJefferson 11y ago
    The main problem is that with floating point numbers, (a+b)+c is different to a+(b+c), so almost any change can produce slightly different answers. Also we have the problem of what is "right"? Maybe your first implementation does (a+b)+c, then someone finds doing (a+c)+b gives a more accurate answer. Should we change? Then you are given two CPUs. If I want to do x1 + x2 + ... + xn, then obvious thing to do is going to be to give each CPU half the input data. But now however I split will give me a (slightly) different answer. With matrix multiplication this is much worse -- all algorithms chop the matrix into little pieces in different ways, each giving a slightly different answer. Even if you try to define some plain simple algorithm, it will usually give a less accurate answer, due to how the floating point rounded! With integer matrices on finite fields, it is much easier to get what you want, 100% reproducability.
    - yarvin9 11y ago
      Let me say the same thing perhaps more clearly: there isn't any nondeterminism here, just failure to capture the inputs and outputs of a deterministic code transformation. Suppose CPU count is the configuration input. Then you have a deterministic macro function M(nCPU, abstract program) => concrete program. And another deterministic function C(concrete program) => CPU instructions. Now nCPU is no longer a random piece of information randomly found in your environment: it's data in your data set. And your results are bitwise reproducible. With a reproducible toolchain, I can use a 1-CPU machine to get the same results as you did on your 32-CPU machine, by using the same data set (including your nCPU=32). Why? Because I'm reproducing your results and I care more about precision than performance.

khinsen 11y ago

Your comment is a nice example of the frequent misunderstandings concerning bitwise reproducibility. My article argues that infrastructure tools (compilers, runtimes, ...) should ensure bitwise reproducibility, making it possible for a programmer to define a computational result exactly through a program's source code. This does not mean that we can't have different algorithms. It doesn't even mean that no compiler could ever re-arrange operations for optimization. The latter could well be enabled through a compiler option. All I am asking for is that infrastructure tools leave all these choices to the programmer.