Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

In Dijkstra's Notes on Structured Programming he talks a lot about the provability of computer programs as abstract entities. As a corollary, he remarks how testing isn't enough. E.g., he points out the fact that it would be impossible to test a multiplication function f(x,y) = x*y for any large values of x and y across the entire ranges of x and y. My question concerns his misc. remarks on "lousy hardware". I know the essay was written in the 1970s when computer hardware was less reliable, but computers still aren't perfect, so they must make calculation mistakes sometimes. Does anybody know how often this happens or if there are any statistics on this?

share|improve this question
1  
cstheory.stackexchange.com –  NickC Jan 6 '11 at 3:21
    
Here's the wikipedia page on the Pentium FDIV bug, mentioned by the two currently existing answers. –  Jefromi Jan 6 '11 at 5:36
    
We get by without any kind of backup or error checking on basic CPU operations, so we can easily estimate an upper bound for the frequency of random transient computational errors. Most CPU instructions involve math (in calculating addresses for memory operations as well as computation), and modern CPUs are doing billions of operations per second, call it > 1e14 operations a day. If 1 in 10 math errors would have an obvious effect on the program (probably a low estimate), and we don't see such errors on a daily basis, the basic error rate for the ALU must be < 1e-13, and I would guess < 1e-15. –  Russell Borogove Sep 2 '11 at 21:30
    
@NickC: are you implying that there is nothing practical about this question? So you think the question of whether hardware works or not doesn't matter? What about when it actually matters whether the program works properly (is hard real time programming only theoretical, or too advanced for people on this site?)? What about hardware where one user can steal keys from other users because of information leaking through side channel? Damn I wish there was a downvote button for comments. –  Longpoke Jun 1 '12 at 22:06
    
@Longpoke Me too. –  NickC Jun 1 '12 at 22:30
show 1 more comment

5 Answers

up vote 10 down vote accepted

Real/Actual errors in a CPU's design aside, I think you are looking for this SO Question: Cosmic Rays. What is the probability they will affect a program. I can't get quotes from it because SO is blocked again at work here (sigh).

Ignoring the above, I seem to recall there was some FPU calculation bugs in early Pentiums, so they certainly are not infallible.

I have no hard evidence at hand, but my gut tells me you should probably be more concerned about bits of Cache/RAM/Disk being corrupt then the calculation being incorrect.

share|improve this answer
26  
SO is blocked at work? Is someone in your company trying to sabotage software development? –  NickC Jan 6 '11 at 3:29
2  
You say that as if it is only one person and they haven't been successful yet... ;) –  Dan McGrath Jan 6 '11 at 5:07
8  
I never could understand the rationale of blocking SFW sites at the corporate level. As search engines are an extremely valuable tool, you should be able to view the information that they yield. –  Tim Post Jan 6 '11 at 10:23
    
@Dan, unblock it. You should be able to do https-tunnelling to home. –  user1249 Aug 26 '11 at 21:26
2  
Getting caught bypassing the system was just cause for termination. I moved to the US and got a new job. –  Dan McGrath Aug 26 '11 at 21:37
add comment

In terms of what you consider the actual "CPU" (execution units, pipeline..ect) it pretty much never happens. There was a known issue with one of the Pentium flavors a while back, but that is the only one that I have ever heard of. Now, if you consider the chips sets that are built into the processors or at least the same packaging such USB controllers, TSEC, DMA controller or memory controller then there are plenty of errata out there. I doubt there is any sort of statistical data about that though.

share|improve this answer
add comment

Back when I worked for a hardware vendor it was claimed that no CPU ever built was bugfree. And that is just logic bugs. Usually the manufacturer finds most of them and either respins the chip, or finds BIOS settings that work around them. But in addition to the fact the stuff like cosmic rays occasionally flip a bit in memory (and memory usually has parity bits or SECDED circuitry to save your bacon), there is always a finite chance that a bit will be read incorrectly. Note that bits aren't real logical zeroes and ones,but noisy things like voltages and currents , and given finite noise in the system there is always the chance that a wrong bit will be read. In the old days (as a app programmer), I found a few HW bugs -both of the bad logic kind, and of the unit X in CPU Y is occasionally giving me a bad result type, time to get the HW guys to replace a chip variety. Actual circuits do drift with time and use, and if yours is getting ready to fail, you could start picking up bit errors, especially if you are overclocking, or otherwise exceeding the recommended operating range.

It is a real issue for supercomputing, where computations invlolving 1e18 or more floating point operations are contemplated.

share|improve this answer
add comment

A big issue in answering this question these days is that CPU manufacturers wrap the errata for the chip in a NDA ( NonDisclosure Agreement). Intel do this, IIRC.

Many less secretive manufacturers issue corrections to the data sheet, but don't tell you what changed, so unless you fancy comparing all 300 pages, you'll have a hard time telling.

There have been plenty of bad instructions in CPU's, watching a Linux kernel report which ones it finds on boot is moderately interesting.

Very related is the paper Google on memory errors, they are more common than you think. "DRAM errors in the Wild:A Large-Scale Field Study" Schoeder, Pinheiro and Weber Originally published in ACM SIGMETRICS in 2009. Republished in Communications of the ACM Feb 2011

What all these memory errors mean for you question, is that without ECC memory, you will get wrong calculations anyway.

share|improve this answer
add comment

Another "lousy hardware" issue to consider in this context is that floating point hardware is inherently "lossy": it has limited precision, and with sufficiently large numbers (refer back to the original Dijkstra quote) you will not be able to distinguish between x and x + 1, or even x + 1000000. You can get "infinite" precision floating point libraries, but they are slow and ultimately still limited by available memory.

In short, Dijkstra was working in the realm of theory, and real hardware/software doesn't match up to theoretical ideals very well. (Remember, the original "Turing machine" specified an infinite paper tape.)

share|improve this answer
1  
This doesn't necessarily effect provability, though, which was the context of the question. Upper bounds on these sorts of losses can be, and often are, precisely accounted for theoretically. In other words programs can still be provably correct to within a certain predetermined margin of error. In certain fields I'd consider anyone who didn't take these issues into account to not be doing their jobs properly! –  Elias Vasylenko Oct 31 '12 at 16:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.