5 ms·

Rice professor sees probabilistic method revolutionizing computing

48 points by peter123 18y ago

Jebdm 18y ago
The big problem I see is that if you ever want to do something which has to be precise, you'll have to have two processors. Perhaps in the future we'll see chips with a "probability drive" in addition to the normal cores. Now we've just got to develop an improbability drive...
- gregstoll 18y ago
  Or just do everything twice - if it really runs seven times faster than "today's best technology" than it shouldn't be an issue. It's a very interesting idea...wish they had more details in the article.
  - gojomo 18y ago
    You might have to do it far more than 7 times to converge on a suitably reliable answer... but perhaps precise recomputation could be deferred to off-hours, or lagged batch processing, or after disputes, etc.
- LogicHoleFlaw 18y ago
  On mainframes where it really, really matters that the answers be right, three processors will do the same calculation in lockstep and any one processor deviating will have its results thrown out.
  - JulianMorrison 18y ago
    If I read the article right, it's not that it sometimes fails, rather it almost always fails, but the amount of error is predictable. You can converge on the exact value by repeating and averaging the calculation, but it would be simpler to have an exact co-processor.
bprater 18y ago
Does anyone have any technical info on how this is accomplished?
- shadytrees 18y ago
  Google Scholar has picked up on Krishna Palem's previous publications. There should be a law that internet articles about scientific research have to back everything up with links to a journal article or something. http://scholar.google.com/scholar?q=Krishna+Palem+probabilistic+computing&hl=en&lr=&btnG=Search http://scholar.google.com/scholar?q=Krishna+Palem+probabilis... For example, here's an interesting paper that talks about saving power by making AND/NOT gates probabilistic. http://www2.computer.org/portal/web/csdl/doi/10.1109/TC.2005.145 http://www2.computer.org/portal/web/csdl/doi/10.1109/TC.2005... I guess there's an inherent assumption that that reduced power consumption will scale up to the level of "checking email and browsing the internet".
  - michaelneale 18y ago
    The power consumption angle is quite interesting - but I given the power saving they demonstrated wasn't really of an order of magnitude or more, then it might be hard to make it scale up to practical tasks and have errors worked out of it. Perhaps there are more savings to be made, but I would expect to see orders of magnitude less power for this stuff to be practical.
  - f3lix 18y ago
    Maybe. I think it may work in computer graphics applications. Most calculation is done for only a single frame and then discarded. If it were a little off there would not really be any bad effect.
    - ars 18y ago
      The libavcodec has an option that does exactly that. It skips steps in the filter loop that only affect the single frame. It makes things quite a bit faster.
tlrobinson 18y ago
"To compensate, engineers increase the voltage applied to computer circuits to overpower the noise and ensure precise calculations." "Precise"? How about "correct"?
- bdr 18y ago
  Most floating point calculations are only correct according to a standard.
  - deleted 18y ago
    [deleted]
  - tlrobinson 18y ago
    Yes, but who said anything about floating point numbers? I guess I should have explained, but my point was that in "normal" microprocessors the voltage level has nothing to do with the precision of the computation... if it's low enough that errors are introduced the results will be wildly incorrect, not merely imprecise as that statement implies.
- timf 18y ago
  Not an option. http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems http://en.wikipedia.org/wiki/Floating_point#Accuracy_problem... An annoying problem for distributed/grid systems where the compilers are different across nodes/sites.
dnaquin 18y ago
“Numbers that fool the Fermat test are called Carmichael numbers, and little is known about them other than that they are extremely rare. There are 255 Carmichael numbers below 100,000,000. The smallest few are 561, 1105, 1729, 2465, 2821, and 6601. In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a “correct” algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the differences between mathematics and engineering.” footnote pg. 53 SICP
- jacquesm 18y ago
  "In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a “correct” algorithm." Where are the numbers for that ? If the fermat test already fails for 255 numbers out of 100 million input values then that would make it one in about 400K numbers. I would really be surprised if computers were that susceptible to cosmic radiation. Or should I start shielding my machines with u-metal ?
  - reitzensteinm 18y ago
    It says for very large numbers. Presumably it's a reflection of the amount of computational power required, if a bit of your memory gets flipped every year by cosmic radiation it's not a serious problem, unless you're doing a calculation that takes 10 computer years (eg with 1000 machines over 3 days). Kind of like Google's terabyte sort test where each time they ran it at least one hard drive died.
  - dnaquin 18y ago
    "Let C(n) denote the number of Carmichael numbers less than n. ... The upper bound C(n)<n*exp(-(lnnlnlnlnn)/(lnlnn)) (4) has also been proved (R. G. E. Pinch)." So that ratio isn't constant. Key is "...of very large numbers...". Clearly larger than 100,000,000.

48 points by peter123 18y ago

Jebdm 18y ago

The big problem I see is that if you ever want to do something which has to be precise, you'll have to have two processors. Perhaps in the future we'll see chips with a "probability drive" in addition to the normal cores. Now we've just got to develop an improbability drive...

gregstoll 18y ago
Or just do everything twice - if it really runs seven times faster than "today's best technology" than it shouldn't be an issue. It's a very interesting idea...wish they had more details in the article.
- gojomo 18y ago
  You might have to do it far more than 7 times to converge on a suitably reliable answer... but perhaps precise recomputation could be deferred to off-hours, or lagged batch processing, or after disputes, etc.
LogicHoleFlaw 18y ago
On mainframes where it really, really matters that the answers be right, three processors will do the same calculation in lockstep and any one processor deviating will have its results thrown out.
- JulianMorrison 18y ago
  If I read the article right, it's not that it sometimes fails, rather it almost always fails, but the amount of error is predictable. You can converge on the exact value by repeating and averaging the calculation, but it would be simpler to have an exact co-processor.

bprater 18y ago

Does anyone have any technical info on how this is accomplished?

shadytrees 18y ago
Google Scholar has picked up on Krishna Palem's previous publications. There should be a law that internet articles about scientific research have to back everything up with links to a journal article or something. http://scholar.google.com/scholar?q=Krishna+Palem+probabilistic+computing&hl=en&lr=&btnG=Search http://scholar.google.com/scholar?q=Krishna+Palem+probabilis... For example, here's an interesting paper that talks about saving power by making AND/NOT gates probabilistic. http://www2.computer.org/portal/web/csdl/doi/10.1109/TC.2005.145 http://www2.computer.org/portal/web/csdl/doi/10.1109/TC.2005... I guess there's an inherent assumption that that reduced power consumption will scale up to the level of "checking email and browsing the internet".
- michaelneale 18y ago
  The power consumption angle is quite interesting - but I given the power saving they demonstrated wasn't really of an order of magnitude or more, then it might be hard to make it scale up to practical tasks and have errors worked out of it. Perhaps there are more savings to be made, but I would expect to see orders of magnitude less power for this stuff to be practical.
- f3lix 18y ago
  Maybe. I think it may work in computer graphics applications. Most calculation is done for only a single frame and then discarded. If it were a little off there would not really be any bad effect.
  - ars 18y ago
    The libavcodec has an option that does exactly that. It skips steps in the filter loop that only affect the single frame. It makes things quite a bit faster.

tlrobinson 18y ago

"To compensate, engineers increase the voltage applied to computer circuits to overpower the noise and ensure precise calculations." "Precise"? How about "correct"?

bdr 18y ago
Most floating point calculations are only correct according to a standard.
- deleted 18y ago
  [deleted]
- tlrobinson 18y ago
  Yes, but who said anything about floating point numbers? I guess I should have explained, but my point was that in "normal" microprocessors the voltage level has nothing to do with the precision of the computation... if it's low enough that errors are introduced the results will be wildly incorrect, not merely imprecise as that statement implies.
timf 18y ago
Not an option. http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems http://en.wikipedia.org/wiki/Floating_point#Accuracy_problem... An annoying problem for distributed/grid systems where the compilers are different across nodes/sites.

dnaquin 18y ago

“Numbers that fool the Fermat test are called Carmichael numbers, and little is known about them other than that they are extremely rare. There are 255 Carmichael numbers below 100,000,000. The smallest few are 561, 1105, 1729, 2465, 2821, and 6601. In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a “correct” algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the differences between mathematics and engineering.” footnote pg. 53 SICP

jacquesm 18y ago
"In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a “correct” algorithm." Where are the numbers for that ? If the fermat test already fails for 255 numbers out of 100 million input values then that would make it one in about 400K numbers. I would really be surprised if computers were that susceptible to cosmic radiation. Or should I start shielding my machines with u-metal ?
- reitzensteinm 18y ago
  It says for very large numbers. Presumably it's a reflection of the amount of computational power required, if a bit of your memory gets flipped every year by cosmic radiation it's not a serious problem, unless you're doing a calculation that takes 10 computer years (eg with 1000 machines over 3 days). Kind of like Google's terabyte sort test where each time they ran it at least one hard drive died.
- dnaquin 18y ago
  "Let C(n) denote the number of Carmichael numbers less than n. ... The upper bound C(n)<n*exp(-(lnnlnlnlnn)/(lnlnn)) (4) has also been proved (R. G. E. Pinch)." So that ratio isn't constant. Key is "...of very large numbers...". Clearly larger than 100,000,000.