4 ms·

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 s

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.
- deleted 11y ago
  [deleted]
- JesperRavn 11y ago
  In principal there is nothing wrong with what you say, it's just that you need to now keep track of every possible change to the code and the environment. For what I am proposing, keeping track of the major versions of dependencies should be enough. See also sibling comment.
davexunit 11y ago
> Source code for every dependency would be needed too. Yes, reproducibility requires source code for the entire dependency graph, down to a set of bootstrap binaries. This is what tools such as GNU Guix and Nix allow you to do. They enable reproducible science.
- JesperRavn 11y ago
  I don't think the effort needed for this is worth it. Most scientists even ones who code, don't even know what bootstrap binaries are. My original point is that the complexity of dealing with differing environments and code versions, combined with the sensitivity of floating point results on the exact source code and environment, practically kills the possibility for exact reproducibility. That's why I'm claiming that a better goal is approximate reproducibility.
  - yarvin9 11y ago
    In a way we're arguing past each other: you're saying that approximate reproducibility is realistically the best scientists can do with today's toolchains. I'm saying that programmer's writing tomorrow's toolchains should do better. It seems at least possible that we could both be right :-)
    - JesperRavn 11y ago
      Yes, I agree that the issue is in the toolchain. And more reproducibility in this area is a much more general and important problem. Even without aiming for bitwise reproducibility, it's still very hard to properly package your software and its dependencies. That is one reason why reproduction is so rare: simply installing the dependencies is too hard. So a sufficient improvement in toolchains/package management etc. would probably enable bitwise reproducibility, but I think a lot of people in this thread, and the original article, were implying that current tools are sufficient and scientists just need to stop being lazy.
  - davexunit 11y ago
    And you're completely wrong.

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.
deleted 11y ago
[deleted]
JesperRavn 11y ago
In principal there is nothing wrong with what you say, it's just that you need to now keep track of every possible change to the code and the environment. For what I am proposing, keeping track of the major versions of dependencies should be enough. See also sibling comment.

davexunit 11y ago

> Source code for every dependency would be needed too. Yes, reproducibility requires source code for the entire dependency graph, down to a set of bootstrap binaries. This is what tools such as GNU Guix and Nix allow you to do. They enable reproducible science.

JesperRavn 11y ago
I don't think the effort needed for this is worth it. Most scientists even ones who code, don't even know what bootstrap binaries are. My original point is that the complexity of dealing with differing environments and code versions, combined with the sensitivity of floating point results on the exact source code and environment, practically kills the possibility for exact reproducibility. That's why I'm claiming that a better goal is approximate reproducibility.
- yarvin9 11y ago
  In a way we're arguing past each other: you're saying that approximate reproducibility is realistically the best scientists can do with today's toolchains. I'm saying that programmer's writing tomorrow's toolchains should do better. It seems at least possible that we could both be right :-)
  - JesperRavn 11y ago
    Yes, I agree that the issue is in the toolchain. And more reproducibility in this area is a much more general and important problem. Even without aiming for bitwise reproducibility, it's still very hard to properly package your software and its dependencies. That is one reason why reproduction is so rare: simply installing the dependencies is too hard. So a sufficient improvement in toolchains/package management etc. would probably enable bitwise reproducibility, but I think a lot of people in this thread, and the original article, were implying that current tools are sufficient and scientists just need to stop being lazy.
- davexunit 11y ago
  And you're completely wrong.