|
Are Floating Point Operations on the Way Out? Bill Walster Thinks the Time Is Ripe for Interval Arithmetic
What's wrong with floating point calculations anyway? Not much, unless you're concerned with rounding errors that can result in different answers to the same problem run on parallel machines. Then you're stuck trying to figure out whether the difference stems from rounding, from a software error or a hardware flaw. Bill Walster suggests a better alternative: interval arithmetic. Reduced to its essentials, interval arithmetic, by "trapping" the correct answer within a set of possible values, avoids the undetected cascading of rounding errors. "With intervals, I am guaranteed that the value I'm computing is contained in the interval result. It's a mathematical guarantee, a numerical proof," claims Walster, a Sun research engineer hard at work on the DARPA supercomputer project. He goes even further, expressing his confidence in the method, with the assertion that computer simulations using interval arithmetic are so accurate that independent physical verification could become redundant. "Computing with intervals is the only approach that lets you reliably scale up some parallel computations to 100,000 processors and beyond," he continues. "You can't get there with floating-point arithmetic alone." "Computing with intervals is as big a paradigm shift in computing, science, and technology -- and even in mathematics -- as has ever occurred in these fields," Walster insists. "I call intervals the mother of all paradigm shifts. Not only are they a paradigm shift in computing, applied mathematics and numerical analysis, but they might also create paradigm shifts in physics, chemistry, biology, the life sciences and cosmology." A colleague on the Sun supercomputer project, Principal Investigator John Gustafson, corroborates Walster's view. "If you can prove mathematically the right answer is between this answer and that answer, you can restore mathematical rigor to computing," he states. Ramon Moore developed the concept of interval arithmetic in 1957. Walster has refined the notion by the application of set theory. "If you lay the foundation for interval arithmetic, not on real numbers, but on sets -- set theory -- then, since an interval is a set, you can develop a closed system in which there are no undefined computations," Walster maintains. He and co-author Eldon Hansen elaborated on containment set theory in their book "Global Optimization Using Interval Analysis. Walster credits Hansen with being the first to use interval analysis to solve nonlinear optimization problems, giving the lie to the traditional belief that it was impossible to derive numerical solutions to nonlinear problems. Which is the potential in interval arithmetic that excites Walster most: solving problems that involve an infinite sequence of digits that need to be represented on the finite machine that is the computer. "The trick," Walster explains, "is to develop fast interval algorithms that narrow the width of computed intervals to produce the degree of accuracy needed to solve real problems." The right answer will always be found within a machine-representable interval. By way of example, Walster cites the set of three algorithms developed as part of the control mechanism for the F-16 fighter. Because the algorithms were altitude sensitive, each of the three applied only within a specific 10,000 foot altitude range. Then, a single interval algorithm was developed that worked throughout all three altitude ranges and worked better than all of the earlier solutions. The trouble is the feedback loops on all those electronics can sometimes "go chaotic," as Walster puts it. To avoid disaster, the underlying control algorithms need to be robust. "With intervals you can prove they're robust," Walster says. So confident is he in the future of interval arithmetic-based computing that Walster says, "Sun has at least as big an opportunity to gain a technological advantage as any company has ever had in history of science and technology. Period."
And he adds, "Intervals have the potential to change the rules of the
computing game.... All your floating-point speed doesn't count any
more. It's just not relevant. The only speed that matters is interval
speed."
[...read more...]
Keywords:
From the latest issue:
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||
Print Friendly
Email this article
You can't get there with floating-point arithmetic
alone. 
Are Floating Point Operations on the Way Out?
Copyright © 1998-2009 System News, Inc.
