Sun researchers: Computers do bad math
- 18 December, 2003 08:34
On Feb. 25, 1991, during the first Gulf War, a Scud missile hit U.S. Army barracks in Dhahran, Saudi Arabia, killing 28 U.S. soldiers. The barracks was defended by a Patriot missile defense system, which for some reason failed to track and intercept the incoming Scud. A year later, a U.S. General Accounting Office (GAO) investigation into the Patriot's failure concluded that the battery's weapon control system suffered from a fatal flaw: It was bad at math.
On Tuesday, researchers at Sun Microsystems discussed work they are doing, as part of a three-year, US$50 million Defense Advanced Research Projects Agency (DARPA) grant, that aims to avoid the kind of errors that caused the Patriot failure.
Mathematical errors are far more common in the computer industry than most people realize, said Greg Papadopoulos, Sun's executive vice president and chief technology officer. While his company is normally the first to accuse Microsoft of shoddy operating system design, bad math and not Windows is sometimes behind those unexplained PC crashes, he admits.
"There are a lot of errors that happen in machines that go undetected," Papadopoulos said. "Sometimes a machine just goes away and freezes. You always blame it on Microsoft. We do, too. It's convenient. It's convenient for Intel, too."
"It's a dirty secret. Floating-point arithmetic is wrong," said John Gustafson, a principal investigator with Sun. "It only takes two operations to see that computers make mistakes with fractions."
The problem that Gustafson and Papadopoulos referred to stems from the fact that the binary mathematics employed by computers has a hard time accurately representing certain numbers. Fractions, for example, are particularly tough, because they often involve non-terminating numbers that are impossible to accurately express in binary format.
Dividing two by three on a calculator illustrates the problem. The fraction 2/3, when represented in a computer, is inevitably rounded up, making the last digit a seven.
In the case of the Gulf War incident, the Patriot battery's computer rounded a similar, non-terminating number in order to calculate time. But by shaving off a few digits during every calculation, the battery also shaved off a bit of time. After one hour, the Patriot's clock was off by .0034 seconds. On Feb 25, the computer had been in operation for 100 hours straight, and its clock was off by over one third of a second, enough to cause it to miss the incoming Scud.
Programmers who write software that requires these types of calculations are "very much aware of these problems," and use a variety of techniques to work around the inaccuracy, said Nathan Brookwood a principal analyst with the firm Insight64.
But with supercomputers that calculate billions of sums per second, some of these workarounds can slow down performance, and the risk that some unanticipated mathematical error may occur remains a niggling doubt.
Sun researchers are looking to solve both problems using a technique called interval arithmetic, which essentially traps a mathematically incorrect number between two other numbers that are known to be correct, and prevents mathematical inaccuracy from ballooning out of control over time. "If you can prove mathematically that the right answer is between this answer and that answer, you can restore mathematical rigor to computing," Gustafson said.
A number of compilers already support interval arithmetic, but Sun's work aims to speed up the performance of interval calculations, according to Gustafson. "We've done a lot of clever things in the compiler so the penalty for using intervals is as low as it can be," he said.
Sun's interval arithmetic work will be used in a prototype of a new supercomputer the company plans to build over the next two-and-a-half years as part of its DARPA grant.
In August, Sun created a new High Productivity Computing Solutions group to build the prototype. The group, run by the former head of the SunLabs research and development group, Jim Mitchell, has a staff of about 100 people, including four of Sun's most distinguished researchers, called Sun Fellows.
Sun's supercomputer, code named Hero because "it's a machine that scales to heroic proportions," according to Gustafson would be approximately 50 times faster than the fastest supercomputer today, the Earth Simulator in Yokohama, Japan.
The Earth Simulator can perform over 40 trillion mathematical operations per second. If Sun is able to secure a further round of DARPA funding and take Hero beyond the prototype stage, it will be capable of 50 times as many operations per second, Sun predicts.
Sun, along with IBM and Cray were awarded DARPA grants in July of this year to build prototypes of the next generation of supercomputers. Once the prototypes are built, the government agency plans to award further grants so that as many as two working supercomputers can be built.
Mitchell's team is working on an assortment of new technologies, including the interval arithmetic work and a new software development language for supercomputers. But the success or failure of Sun's bid to convince DARPA to go beyond prototype may ultimately depend on a new technique for inter-chip communication called "proximity interconnect," which was first announced by researchers in Mitchell's group at the Institute of Electrical and Electronics Engineers Inc.'s Custom Integrated Circuits Conference last September.
Proximity interconnect uses an electrical phenomenon called capacitance to transfer data between chips without using the pins and wires normally found on a computer's circuit board. If Sun is able to develop a viable manufacturing process based on the technique, it could have "a profound impact on the way people design computers," said Insight64's Brookwood.
It could make computers cheaper to build. Between one half and one third of the transistors in today's microprocessors are used for memory, Brookwood said. Engineers would prefer to place that memory in an inexpensive SRAM (static RAM) chip next to the microprocessor, but the amount of time it takes to transfer data from one chip to the other is prohibitive. "What Sun is saying with the proximity technology is there's no time penalty for going from one chip to the next," he said. "That's mind boggling if they can make that work in a general way."