6 ms·

"The obstacle we shall have to overcome, if we are to successfully program manycore systems, is our cherished assumption that we write programs that always get

"The obstacle we shall have to overcome, if we are to successfully program manycore systems, is our cherished assumption that we write programs that always get the exactly right answers." Most of the time, this is not a trade off worth making. I can't think of a researcher that would willingly trade replicability for speed. I can't think of a mathematician who would base a proof on the idea that a number is probably prime. I can't think of a bank customer who would be fine with the idea that the balance displayed on the ATM is pretty close to where it should be. I can't think of an airline passenger who would be totally fine with the flight computer usually being pretty good. It would be a fine trade off for games, however. And I'm sure there is room for some fudging in complex simulations that have plenty of randomness already. But given the choice between an answer that is correct, and an answer that is probably correct, I will take the correct answer. Even if I have to wait a little.

arghnoname 15y ago
In most applications, using a IEEE float is fine. It's a trade-off where a loss in accuracy is acceptable. Lots of digital things (images for instance) are discrete approximations of continuous phenomenon. The question is the degree of inaccuracy that is tolerated and the sorts of things you have to do to prevent it from propagating (which should be familiar to anyone who has to do math and work with finite precision floating point numbers).
- tomp 15y ago
  floating points have well defined rules and have perfectly accurate calculations, they are only "inaccurate" when used as a computer representation/approximation of real numbers. However, they still do not exhibit any randomness (indeterminacy), are usually not a cause of strange, hard-to-reproduce errors (that concurrent, non-sequential memory instructions often cause).
  - aaronblohowiak 15y ago
    It depends on if you are using "accurate" in the STEM jargon sense or if you are using it in the common parlance. In jargon, there is a difference between accuracy and precision. http://en.wikipedia.org/wiki/Accuracy_and_precision http://en.wikipedia.org/wiki/Accuracy_and_precision Floats are inaccurate (sometimes far from real,) but precise (always yield the same output given the same input.) Edit: reading the article, it calls out a special (different) meaning of the use of precise in the IEEE float spec > In the case of full reproducibility, such as when rounding a number to a representable floating point number, the word precision has a meaning not related to reproducibility. For example, in the IEEE 754-2008 standard it means the number of bits in the significand, so it is used as a measure for the relative accuracy with which an arbitrary number can be represented.
    - deleted 15y ago
      [deleted]
    - brazzy 15y ago
      Most "accuracy" issues that crop up with floats have nothing to do with either accuracy or precision, but simply with wrong expectations about decimal behaviour.
TheEzEzz 15y ago
Due to round off error correct programs are not a subset of replicable programs. Scientists do trade replicability for speed.
- sliverstorm 15y ago
  Exactly. So long as we're talking about accuracy in terms of precision, and not "5% of the time the result will be nonsense", people already make this sacrifice every day. There are also plenty of existing models where accuracy is ultimately assured, but not always maintained internally. Branch prediction, for example. The computer guesses which way the branch will go! This can give a big speed boost depending on the workload and the predictor, and the computer assures accuracy by fact-checking the guess down the line.
- rauljara 15y ago
  You are perhaps not understanding what I mean by replicability. By replicability, I mean that if you run some statistics on a large dataset several times, you will get the same answer each time. Rounding errors in floating point arithmetic don't harm replicability, because all modern computers have that issue. There is some loss in accuracy, but floating point arithmetic is still deterministic.
  - TheEzEzz 15y ago
    > There is some loss in accuracy, but floating point arithmetic is still deterministic. Not in a multi-core setting. When you do a floating point reduce operation the order in which you reduce your floating point numbers matters, but this order is not necessarily deterministic.
    - deleted 15y ago
      [deleted]
    - palish 15y ago
      Translation for readers: Let's say you have some floating point numbers, like... float A = 42.90F; float B = 00.01F; float C = /* ... */; float D = /* ... */; (A + B + C) will not necessarily produce the same result as (A + C + B). In fact, if you do (A + B + B + B ...) very much, then you will wind up exacerbating the problem --- it can be a source of bugs if you repeatedly increment a counter by small floating point values. For example: const int Iterations = 10; for ( int i = 0; i < Iterations; ++i ) A += B; printf( "%2.4f\n", A ); The output is 43.0000, as you'd expect. But what if we increase Iterations to 100? We get 43.8998. Astute readers probably would note that 00.01F can't be exactly represented in base 2, and wonder whether something like 00.0125F would still suffer from this problem. Alas, yes: A = 42.9000F B = 00.0125F 8 iterations == 43.0000 80 iterations == 43.9001 800 iterations == 52.9006 8000 iterations == 142.8820 /* we would expect 142.9 */ So if you want to parallelize some computations, and you want to do 4000 iterations on core #1 and 4000 iterations on core #2 and then sum the results, well... let's see what happens: float A1 = 42.9000F; float B1 = 00.0125F; float A2 = 42.9000F; float B2 = 00.0125F; const int Iterations = 4000; for ( int i = 0; i < Iterations; ++i ) { A1 += B1; A2 += B2; } float A = A1 + A2 - 42.9000F; printf( "%2.4f\n", A ); The output is 142.8885 -- which is different from our earlier result of 142.8820! You may be tempted to try various things to get around this fact... for example, what about counting from zero rather than from 42.9000? (Answer: the error can be even worse, which is a topic worthy of its own separate post) ... but you will quickly discover that this is a fundamental issue. The order of operations matters.
ajuc 15y ago
And yet our brains works that way, and we trust them. If I understand correctly - no single neuron is neccesary for your brain to work ok. Brain does not depend on any single link working correctly. Somehow it works reliable enough. It's possible to make reliable systems from unreliable parts.
- andrewflnr 15y ago
  We trust our brains, but they're not, in fact, very reliable, not without lots of training anyway. In everything from long-term decision making to remembering why you walked into the room, they make little errors that sometimes get us into big trouble. A large part of the reason computers are so useful is precisely because they don't usually make those kinds of mistakes.
  - ajuc 15y ago
    They are reliable for things they are "designed" to. For example for motoric coordination, coordinationg body automatic functions - breathing, pumping blood, etc. They are also highly reliable for new things, if properly trained - like playing music, riding bike, flying plane, playing games, etc. Parsing natural language is not easy task, it involves symbolic processing, yet brains are better at this than computers. Complaining that brains without training are not reliable is like complaining computers don't work correctly without software. BTW - many of the errors brains make are not because of unreliable parts, but because of system design - we have some firmware that made sense before, and now is problematic. This firmware is reliable - it works as intended, only now the problems changed, and we can't change the firmware, and patching this in software causes some problems.
    - jiggy2011 15y ago
      It's difficult to say how reliable our brains are at doing things like driving cars or riding bikes because we don't really have anything to compare them to. I expect that it won't take long before we can build automated cars that are far safer drivers than any human. Parsing natural language is probably inherently non deterministic since no natural language grammers are context free. When we parse a sentance there is almost always at least some ambiguity in the sentence itself, plus we also have to process other things that the person has said; in many cases years in the past and what motivation they may have for saying a certain thing. It is very unlikely that 2 people will get exactly the same meaning out of some natural language sentence because it comes with all kinds of side effects for example something somebody says may also change your opinion of them and other things they have said. I suspect that if we cannot get deterministic behavior out of future computers because of the amount of parallelization required to make efficient use of their CPUs we will end up with 2 streams of computing , one of which will stay relatively static and be interested in using computers for the types of problems we currently do and another which will be interested in applying it to new problems that do not require determinism. The software for these computers will be radically different so most likely you will have 2 computers on your desk (or in your pocket , or in VMs), one with < 10 cores and one with > 1000 cores. I don't know much about how the brain works but I guess this is a process that uses allot of heuristics and psuedo randomness that probably lends itself well to being parallelized which is why we set up our languages this way.
vindvaki 15y ago
I think I understand your point, but I don't agree with some of your examples. "I can't think of a mathematician who would base a proof on the idea that a number is probably prime." I can assure you that such a proof probably exists :) Just look at https://en.wikipedia.org/wiki/Probable_prime https://en.wikipedia.org/wiki/Probable_prime Probability theory can be an extremely powerful tool when researching things that are otherwise difficult to reason about. And the theorem statement does not have to be probabilistic for the probabilistic method to be applicable. Just see http://en.wikipedia.org/wiki/Probabilistic_method http://en.wikipedia.org/wiki/Probabilistic_method http://en.wikipedia.org/wiki/Probabilistic_proofs_of_non-probabilistic_theorems http://en.wikipedia.org/wiki/Probabilistic_proofs_of_non-pro... As for the following: "I can't think of an airline passenger who would be totally fine with the flight computer usually being pretty good." Actually, I would think it's pretty much the opposite. That is, the only type of airline passenger I can think of, is one who is fine with the flight computer (and the airplane in general) usually being pretty reliable. We already know that computers can malfunction and airplanes can crash. Now, of course, how reliable you want the airplane to be is up to you, but if you want it to be flawless, then you should never board an airplane.
- msellout 15y ago
  It's not just the examples that are flawed. In most practical situations, provably correct answers do not exist. In most cases, one can only choose a level of certainty. Sometimes not even the level of certainty is possible to know.
- deleted 15y ago
  [deleted]
- lordlicorice 15y ago
  Also, no airline passenger cares exactly what trajectory they take through the air to reach their destination. If it's easier to program an autopilot which tacks slightly off course, nobody will care.
mikeash 15y ago
Isn't every real computer program inherently probabilistic? Even if the code is not, the hardware always has some chance of failure. Even with ECC RAM etc, there is always some chance that multiple bits will get simultaneously corrupted into a new but still valid configuration. You can't get to 100% reliability. You just have to choose how many nines you want. Why should this be any different?
- exDM69 15y ago
  This is different. If you get a failure, like a flipped bit in RAM, it's a failure. With many-core processors, the normal mode of operation is to provide correct results but they may be different from time to time, assuming more than one correct solution exists. Even if the results are exactly the same or only one solution exists, the process of getting there might be different.
  - mikeash 15y ago
    Sure, it's different in terms of why it's not reliable, but the outcome is the same, so why does it matter?
    - exDM69 15y ago
      If I understood correctly, the outcome is not the same. In a memory failure you get incorrect results. In a concurrent program, you get correct results but they might not be the same results every time (provided that there's more than one correct answer) or the computation that took us there might be different (in terms of timing, power consumption, etc).
      - mikeash 15y ago
        Still seems the same to me in principle. For problems where there are multiple correct answers, probabilistic methods are frequently used to find them (e.g. genetic algorithms). All kinds of things can change timing and power consumption, especially when using a probabilistic method.
rayiner 15y ago
The user of a search engine is probably willing to get the occasional poorly-ranked result. The user of an AI system is probably willing to get the occasional wrong answer, etc.
wisty 15y ago
Implicit numerical schemes tend to handle errors better.
wladimir 15y ago
Those are examples of problems that exist within the space of mathematics and number games we created for ourselves. Computers as we have them now are great for those. However, when interfacing to the real, non-exactly specified, incomplete information world, "good enough most of the time" is not only fine, it is all you can hope for. For example, robots that need to navigate rough terrain, or in living orgamisms at the nano-scale, or communicate in human language. There is a huge class of things that simply cannot be addressed with the current "correct" model of computation because they are not well-specified to the lowest level in the first place. Computers, in other words, needs to be more like brains. Yes, this does give up certain advantages, and safety guarantees. But it does not give up everything. People have trusted their life to animals and other humans, for example, for all history, even though they are far from perfectly safe and/or compliant... (and even now, it is "fallible" humans that control the technology, so you could make a point that nothing is lost, as it was never there in the first place)
- RyanMcGreal 15y ago
  > Computers, in other words, needs to be more like brains. I wonder about this. One of the most common human methods of making decisions with incomplete information and/or short time frames is to fall back on heuristics rather than try to reason through the data. Heuristics have the advantage of being fast and available, but they're also notoriously bad at producing the quality of decision that might come from a more thorough analysis of the data. Frankly, I think I'd feel more comfortable with computers that made decisions through brute force processing and bayesian analysis.
  - wladimir 15y ago
    Yes, we'd all like to live in the best of all worlds. But in any real-life scenario, there is a trade-off. Brute forcing all possible combinations and finding the best one (for your specific goal, or taking into account all externalities as well) would be great. But it is impossible for two reasons: 1) incomplete, or even purposefully incorrect information 2) time constraints/compexity. For a non-linear system with more than a few variables, it is just not feasible to enumerate everything. You end up with heuristics. The challenge is that remains is finding good heuristics. If the decision is given more time, you can probably come up with better heuristics and even sort-of brute force through the "best" options (which is what humans do when they reason).
mseebach 15y ago
The concept is less foreign that you think: When you do a Google search, do you get a replicable, provably correct result? Or do you get a result that 99% of the time is good enough?

arghnoname 15y ago

In most applications, using a IEEE float is fine. It's a trade-off where a loss in accuracy is acceptable. Lots of digital things (images for instance) are discrete approximations of continuous phenomenon. The question is the degree of inaccuracy that is tolerated and the sorts of things you have to do to prevent it from propagating (which should be familiar to anyone who has to do math and work with finite precision floating point numbers).

tomp 15y ago
floating points have well defined rules and have perfectly accurate calculations, they are only "inaccurate" when used as a computer representation/approximation of real numbers. However, they still do not exhibit any randomness (indeterminacy), are usually not a cause of strange, hard-to-reproduce errors (that concurrent, non-sequential memory instructions often cause).
- aaronblohowiak 15y ago
  It depends on if you are using "accurate" in the STEM jargon sense or if you are using it in the common parlance. In jargon, there is a difference between accuracy and precision. http://en.wikipedia.org/wiki/Accuracy_and_precision http://en.wikipedia.org/wiki/Accuracy_and_precision Floats are inaccurate (sometimes far from real,) but precise (always yield the same output given the same input.) Edit: reading the article, it calls out a special (different) meaning of the use of precise in the IEEE float spec > In the case of full reproducibility, such as when rounding a number to a representable floating point number, the word precision has a meaning not related to reproducibility. For example, in the IEEE 754-2008 standard it means the number of bits in the significand, so it is used as a measure for the relative accuracy with which an arbitrary number can be represented.
  - deleted 15y ago
    [deleted]
  - brazzy 15y ago
    Most "accuracy" issues that crop up with floats have nothing to do with either accuracy or precision, but simply with wrong expectations about decimal behaviour.

TheEzEzz 15y ago

Due to round off error correct programs are not a subset of replicable programs. Scientists do trade replicability for speed.

sliverstorm 15y ago
Exactly. So long as we're talking about accuracy in terms of precision, and not "5% of the time the result will be nonsense", people already make this sacrifice every day. There are also plenty of existing models where accuracy is ultimately assured, but not always maintained internally. Branch prediction, for example. The computer guesses which way the branch will go! This can give a big speed boost depending on the workload and the predictor, and the computer assures accuracy by fact-checking the guess down the line.
rauljara 15y ago
You are perhaps not understanding what I mean by replicability. By replicability, I mean that if you run some statistics on a large dataset several times, you will get the same answer each time. Rounding errors in floating point arithmetic don't harm replicability, because all modern computers have that issue. There is some loss in accuracy, but floating point arithmetic is still deterministic.
- TheEzEzz 15y ago
  > There is some loss in accuracy, but floating point arithmetic is still deterministic. Not in a multi-core setting. When you do a floating point reduce operation the order in which you reduce your floating point numbers matters, but this order is not necessarily deterministic.
  - deleted 15y ago
    [deleted]
  - palish 15y ago
    Translation for readers: Let's say you have some floating point numbers, like... float A = 42.90F; float B = 00.01F; float C = /* ... */; float D = /* ... */; (A + B + C) will not necessarily produce the same result as (A + C + B). In fact, if you do (A + B + B + B ...) very much, then you will wind up exacerbating the problem --- it can be a source of bugs if you repeatedly increment a counter by small floating point values. For example: const int Iterations = 10; for ( int i = 0; i < Iterations; ++i ) A += B; printf( "%2.4f\n", A ); The output is 43.0000, as you'd expect. But what if we increase Iterations to 100? We get 43.8998. Astute readers probably would note that 00.01F can't be exactly represented in base 2, and wonder whether something like 00.0125F would still suffer from this problem. Alas, yes: A = 42.9000F B = 00.0125F 8 iterations == 43.0000 80 iterations == 43.9001 800 iterations == 52.9006 8000 iterations == 142.8820 /* we would expect 142.9 */ So if you want to parallelize some computations, and you want to do 4000 iterations on core #1 and 4000 iterations on core #2 and then sum the results, well... let's see what happens: float A1 = 42.9000F; float B1 = 00.0125F; float A2 = 42.9000F; float B2 = 00.0125F; const int Iterations = 4000; for ( int i = 0; i < Iterations; ++i ) { A1 += B1; A2 += B2; } float A = A1 + A2 - 42.9000F; printf( "%2.4f\n", A ); The output is 142.8885 -- which is different from our earlier result of 142.8820! You may be tempted to try various things to get around this fact... for example, what about counting from zero rather than from 42.9000? (Answer: the error can be even worse, which is a topic worthy of its own separate post) ... but you will quickly discover that this is a fundamental issue. The order of operations matters.

ajuc 15y ago

And yet our brains works that way, and we trust them. If I understand correctly - no single neuron is neccesary for your brain to work ok. Brain does not depend on any single link working correctly. Somehow it works reliable enough. It's possible to make reliable systems from unreliable parts.

andrewflnr 15y ago
We trust our brains, but they're not, in fact, very reliable, not without lots of training anyway. In everything from long-term decision making to remembering why you walked into the room, they make little errors that sometimes get us into big trouble. A large part of the reason computers are so useful is precisely because they don't usually make those kinds of mistakes.
- ajuc 15y ago
  They are reliable for things they are "designed" to. For example for motoric coordination, coordinationg body automatic functions - breathing, pumping blood, etc. They are also highly reliable for new things, if properly trained - like playing music, riding bike, flying plane, playing games, etc. Parsing natural language is not easy task, it involves symbolic processing, yet brains are better at this than computers. Complaining that brains without training are not reliable is like complaining computers don't work correctly without software. BTW - many of the errors brains make are not because of unreliable parts, but because of system design - we have some firmware that made sense before, and now is problematic. This firmware is reliable - it works as intended, only now the problems changed, and we can't change the firmware, and patching this in software causes some problems.
  - jiggy2011 15y ago
    It's difficult to say how reliable our brains are at doing things like driving cars or riding bikes because we don't really have anything to compare them to. I expect that it won't take long before we can build automated cars that are far safer drivers than any human. Parsing natural language is probably inherently non deterministic since no natural language grammers are context free. When we parse a sentance there is almost always at least some ambiguity in the sentence itself, plus we also have to process other things that the person has said; in many cases years in the past and what motivation they may have for saying a certain thing. It is very unlikely that 2 people will get exactly the same meaning out of some natural language sentence because it comes with all kinds of side effects for example something somebody says may also change your opinion of them and other things they have said. I suspect that if we cannot get deterministic behavior out of future computers because of the amount of parallelization required to make efficient use of their CPUs we will end up with 2 streams of computing , one of which will stay relatively static and be interested in using computers for the types of problems we currently do and another which will be interested in applying it to new problems that do not require determinism. The software for these computers will be radically different so most likely you will have 2 computers on your desk (or in your pocket , or in VMs), one with < 10 cores and one with > 1000 cores. I don't know much about how the brain works but I guess this is a process that uses allot of heuristics and psuedo randomness that probably lends itself well to being parallelized which is why we set up our languages this way.

vindvaki 15y ago

I think I understand your point, but I don't agree with some of your examples. "I can't think of a mathematician who would base a proof on the idea that a number is probably prime." I can assure you that such a proof probably exists :) Just look at https://en.wikipedia.org/wiki/Probable_prime https://en.wikipedia.org/wiki/Probable_prime Probability theory can be an extremely powerful tool when researching things that are otherwise difficult to reason about. And the theorem statement does not have to be probabilistic for the probabilistic method to be applicable. Just see http://en.wikipedia.org/wiki/Probabilistic_method http://en.wikipedia.org/wiki/Probabilistic_method http://en.wikipedia.org/wiki/Probabilistic_proofs_of_non-probabilistic_theorems http://en.wikipedia.org/wiki/Probabilistic_proofs_of_non-pro... As for the following: "I can't think of an airline passenger who would be totally fine with the flight computer usually being pretty good." Actually, I would think it's pretty much the opposite. That is, the only type of airline passenger I can think of, is one who is fine with the flight computer (and the airplane in general) usually being pretty reliable. We already know that computers can malfunction and airplanes can crash. Now, of course, how reliable you want the airplane to be is up to you, but if you want it to be flawless, then you should never board an airplane.

msellout 15y ago
It's not just the examples that are flawed. In most practical situations, provably correct answers do not exist. In most cases, one can only choose a level of certainty. Sometimes not even the level of certainty is possible to know.
deleted 15y ago
[deleted]
lordlicorice 15y ago
Also, no airline passenger cares exactly what trajectory they take through the air to reach their destination. If it's easier to program an autopilot which tacks slightly off course, nobody will care.

mikeash 15y ago

Isn't every real computer program inherently probabilistic? Even if the code is not, the hardware always has some chance of failure. Even with ECC RAM etc, there is always some chance that multiple bits will get simultaneously corrupted into a new but still valid configuration. You can't get to 100% reliability. You just have to choose how many nines you want. Why should this be any different?

exDM69 15y ago
This is different. If you get a failure, like a flipped bit in RAM, it's a failure. With many-core processors, the normal mode of operation is to provide correct results but they may be different from time to time, assuming more than one correct solution exists. Even if the results are exactly the same or only one solution exists, the process of getting there might be different.
- mikeash 15y ago
  Sure, it's different in terms of why it's not reliable, but the outcome is the same, so why does it matter?
  - exDM69 15y ago
    If I understood correctly, the outcome is not the same. In a memory failure you get incorrect results. In a concurrent program, you get correct results but they might not be the same results every time (provided that there's more than one correct answer) or the computation that took us there might be different (in terms of timing, power consumption, etc).
    - mikeash 15y ago
      Still seems the same to me in principle. For problems where there are multiple correct answers, probabilistic methods are frequently used to find them (e.g. genetic algorithms). All kinds of things can change timing and power consumption, especially when using a probabilistic method.

rayiner 15y ago

The user of a search engine is probably willing to get the occasional poorly-ranked result. The user of an AI system is probably willing to get the occasional wrong answer, etc.

wisty 15y ago

Implicit numerical schemes tend to handle errors better.

wladimir 15y ago

Those are examples of problems that exist within the space of mathematics and number games we created for ourselves. Computers as we have them now are great for those. However, when interfacing to the real, non-exactly specified, incomplete information world, "good enough most of the time" is not only fine, it is all you can hope for. For example, robots that need to navigate rough terrain, or in living orgamisms at the nano-scale, or communicate in human language. There is a huge class of things that simply cannot be addressed with the current "correct" model of computation because they are not well-specified to the lowest level in the first place. Computers, in other words, needs to be more like brains. Yes, this does give up certain advantages, and safety guarantees. But it does not give up everything. People have trusted their life to animals and other humans, for example, for all history, even though they are far from perfectly safe and/or compliant... (and even now, it is "fallible" humans that control the technology, so you could make a point that nothing is lost, as it was never there in the first place)

RyanMcGreal 15y ago
> Computers, in other words, needs to be more like brains. I wonder about this. One of the most common human methods of making decisions with incomplete information and/or short time frames is to fall back on heuristics rather than try to reason through the data. Heuristics have the advantage of being fast and available, but they're also notoriously bad at producing the quality of decision that might come from a more thorough analysis of the data. Frankly, I think I'd feel more comfortable with computers that made decisions through brute force processing and bayesian analysis.
- wladimir 15y ago
  Yes, we'd all like to live in the best of all worlds. But in any real-life scenario, there is a trade-off. Brute forcing all possible combinations and finding the best one (for your specific goal, or taking into account all externalities as well) would be great. But it is impossible for two reasons: 1) incomplete, or even purposefully incorrect information 2) time constraints/compexity. For a non-linear system with more than a few variables, it is just not feasible to enumerate everything. You end up with heuristics. The challenge is that remains is finding good heuristics. If the decision is given more time, you can probably come up with better heuristics and even sort-of brute force through the "best" options (which is what humans do when they reason).

mseebach 15y ago

The concept is less foreign that you think: When you do a Google search, do you get a replicable, provably correct result? Or do you get a result that 99% of the time is good enough?