Sun researchers: Computers do bad math ;)
John Plank
http://www.infoworld.com/article/03/12/17/HNbadmath_1.html
************************************************************ This message is posted via FreeNewsPost Inc. FreeNewsPost is supported by http://bestlinks.altervista.org the collection of the best shopping links for the UK & USA HOT Christmas & New Year DISCOUNTS are now available!
Toby Thain
> http://www.infoworld.com/article/03/12/17/HNbadmath 1.html
Do you mean
http://www.infoworld.com/article/03/12/17/HNbadmath_1.html
> --
John Plank
Sorry about that. I was just curious if people agree with
this article ... For me, it looks like Sun says obvious things
just to get more money?
"Toby Thain" <to...@telegraphics.com.au> wrote in message
news:d6ce4a6c.03121...@posting.google.com...
Rmyers1400
Rmyers1400
>From: "John Plank" john_...@mail.com
>Date: 12/18/2003 11:51 AM Eastern Standard Time
>Message-id: <brslu5$bc2$1...@titan.btinternet.com>
>
>Yes - you are right, I made a mistake.
>Sorry about that. I was just curious if people agree with
>this article ... For me, it looks like Sun says obvious things
>just to get more money?
>
answer to are open:
http://www.cs.utep.edu/interval-comp/neum02.html
There are rough and ready ways to tackle the problem of getting a practical
handle on error bounds, but they offer no guarantees.
This is an example of people spending money who know what they're doing.
This is a good example of why this computational scientist is very skeptical of
unverified and unverifiable results from petaflop machines.
RM
Del Cecchi
"Rmyers1400" <rmyer...@aol.com> wrote in message
news:20031218131627...@mb-m02.aol.com...
If the petaflop machine is modeling a physical phenomenon that can actually
be made or made to happen, then one builds one and tries it. This would
work well for VLSI chips and protein molecules, but not so well for global
warming and the evolution of the universe.
It might even work for some classes of nuclear weaponry simulation.
del cecchi
Bernd Paysan
> It might even work for some classes of nuclear weaponry simulation.
I don't understand why we would need petaflop nuclear weaponry
simulations. This sort of things have already been calculated
successfully when "computer" was a job description for a clerk. The
bombs they calculated did explode, and we saw the results. It was
clear: We don't want this to happen again.
Unfortunately, most of our leaders are of the childish type, so that the
only thing stopping them to nuke someone else is the threat that
they'll be nuked then, too. A reasonable petaflops computer would work
like Hactar in "Life, Universe and Everything", and build a small flaw
into his ultimate weapon ;-).
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/
glen herrmannsfeldt
> I don't understand why we would need petaflop nuclear weaponry
> simulations. This sort of things have already been calculated
> successfully when "computer" was a job description for a clerk. The
> bombs they calculated did explode, and we saw the results. It was
> clear: We don't want this to happen again.
The first bombs were over designed enough that they could be reasonably
sure that they would work.
As designs got fancier they were closer to the edge of not
working, and so need more work to be sure that you believe
that they will work. That is, if you want to believe that
they will work.
-- glen
Greg Lindahl
Bernd Paysan <bernd....@gmx.de> wrote:
>I don't understand why we would need petaflop nuclear weaponry
>simulations. This sort of things have already been calculated
>successfully when "computer" was a job description for a clerk.
There was a posting a few days ago which described what the ASCI
people compute, and why. It isn't at all like what was being computed
back when "computers" were people. Perhaps you could read about it
before you post? There are probably some docs on, say, the ASCI
website, too.
-- greg
Stephen Sprunk
news:s7hcb1-...@cohen.paysan.nom...
> I don't understand why we would need petaflop nuclear weaponry
> simulations. This sort of things have already been calculated
> successfully when "computer" was a job description for a clerk. The
> bombs they calculated did explode, and we saw the results. It was
> clear: We don't want this to happen again.
Determining the amount of energy released by a freshly-manufactured nuke is
doable with a pencil and HS-level math and physics textbooks. Even with all
the very bright folks working on it at the time, they still thought driving
a couple miles away and watching the first test with only sunglasses for
protection was perfectly acceptable.
Determining the exact blast radius, fallout, etc. of a nuke that's been
sitting in storage for 40+ years, subjected to internal and external
radiation sources, mechanical abuse, etc. is a totally different matter.
And, if those results tell you it's time to scrap those tens of thousands of
warheads, you also need to calculate the effects of reusing material in new
nukes or removing and storing it, etc.
The latter is the justification I was given for Red Storm when I asked some
of the researchers involved in the project.
S
--
Stephen Sprunk "God does not play dice." --Albert Einstein
CCIE #3723 "God is an inveterate gambler, and He throws the
K5SSS dice at every possible opportunity." --Stephen Hawking
glen herrmannsfeldt
(snip)
> Determining the amount of energy released by a freshly-manufactured
> nuke is doable with a pencil and HS-level math and physics
> textbooks.
> Even with all the very bright folks working on it at the time,
> they still thought driving a couple miles away and watching the
> first test with only sunglasses for protection was perfectly acceptable.
It isn't so easy. Some parts are flying apart faster than they
can react, so figuring out which stay together long enough
isn't so easy. The maximum isn't so hard, but a reasonably
accurate value is much harder.
-- glen
Rmyers1400
>Date: 12/19/2003 2:59 PM Eastern Standard Time
>Message-id: <brvlbm$83nof$1...@ID-129159.news.uni-berlin.de>
<snip>
>> This is an example of people spending money who know what they're doing.
>>
>> This is a good example of why this computational scientist is very
>skeptical of
>> unverified and unverifiable results from petaflop machines.
>>
>If the petaflop machine is modeling a physical phenomenon that can actually
>be made or made to happen, then one builds one and tries it. This would
>work well for VLSI chips and protein molecules, but not so well for global
>warming and the evolution of the universe.
>
Well, yes, but I'd still be cautious. Computational scientists doing
predictions where ther is or will be much experience can be more cavalier than
scientists doing predictions where there is little or no experience, and where
the calculation must be relied upon before the circumstance being predicted
actually arise. Nuclear warfare is a dramatic example. A jumbo jet flying
into the World Trade Center is another.
We now have two data points for the WTC event, and both yielded catastrophic
and unexpected effects. Building codes and practices will almost certainly
change as a result. You don't get a second chance at events like that, and you
won't get a second chance at nuclear war. What went wrong probably had little
or nothing to do with the fact that the design parameter (a possible collision
with a 707) was exceeded. The catastrophic failure of the towers, which should
not have happened, can probably be explained pretty easily--but in retrospect.
>It might even work for some classes of nuclear weaponry simulation.
It might, but are you happy with the use of such a word in the context of such
extreme scenarios?
I have tried to stay away from the policy questions (do we need them, are they
good or bad for our security, what should we do with them) to focus only on the
role that computers are supposed to play.
Since I have said so many negative things about government bureuacracies
regarding the funding and management of large technical undertakings, I was
happy that the OP asked a question to which I could respond, this is an example
of what we should be doing, and, indeed, what we need to be doing. The example
of what went wrong with the patriot missile incident in the article cited by
the OP, btw, is a circumstance where the weaponry was built and tested, just
not under the circumstances under which it had to be relied upon.
With the kinds of do or die scenarios you described where resources are
committed to a design that exist only on paper and where a complete failure
would be catastrophic for the company, actually building the system will
invariably turn up mistakes or omissions in the design analysis. If such
things *didn't* happen, a superstitious person might prepare for the
apocalypse. Even gross errors and omissions are rarely unfixable. They get
fixed, and you acquire experience for future projects.
National security applications often don't work that way. If you make a
mistake, you won't get a chance to fix it.
The national policy question I did want to address is that if computers are
playing such a fundamental role in national security, then the country is
playing a fool's game not to fund a significant amount of basic, disinterested,
and skeptical research about how to build and use computers, especially for
large applications. More sandbox work at LLNL would not qualify, nor would
annual classified reviews by hired wizards with a sinecure to protect.
RM
>
>del cecchi
>
>
>
>
>
>
>
>
Joe Pfeiffer
>
> We now have two data points for the WTC event, and both yielded catastrophic
> and unexpected effects. Building codes and practices will almost certainly
> change as a result. You don't get a second chance at events like that, and you
> won't get a second chance at nuclear war. What went wrong probably had little
> or nothing to do with the fact that the design parameter (a possible collision
> with a 707) was exceeded. The catastrophic failure of the towers, which should
> not have happened, can probably be explained pretty easily--but in retrospect.
Was the collapse unexpected? My impression has been that, given the
damage sustained when the planes hit the towers and the amount of
flaming kerosene sloshed around, nobody involved in big skyscraper
design was the list bit surprised (we laymen were shocked, but that
has nothing to do with whether people who knew what they were talking
about were).
--
Joseph J. Pfeiffer, Jr., Ph.D. Phone -- (505) 646-1605
Department of Computer Science FAX -- (505) 646-1002
New Mexico State University http://www.cs.nmsu.edu/~pfeiffer
Southwestern NM Regional Science and Engr Fair: http://www.nmsu.edu/~scifair
Rmyers1400
>Date: 12/20/2003 12:11 PM Eastern Standard Time
>Message-id: <1bekuzs...@cs.nmsu.edu>
>
>rmyer...@aol.com (Rmyers1400) writes:
>>
>The catastrophic failure of the towers, which
>should
>> not have happened, can probably be explained pretty easily--but in
>retrospect.
>
>Was the collapse unexpected? My impression has been that, given the
>damage sustained when the planes hit the towers and the amount of
>flaming kerosene sloshed around, nobody involved in big skyscraper
>design was the list bit surprised (we laymen were shocked, but that
>has nothing to do with whether people who knew what they were talking
>about were).
I guess you've been listening to and/or reading different accounts from the
ones I have listened to and read. The impact alone did not do enough damage to
cause the collapse. It is true that a raging inferno of the jet fuel from a
fully loaded jumbo jet is probably outside the original design envelope of the
building, but the fire protection that is required on structural elements
should have provided more time to evacuate than it did--whether the building
eventually fell or not.
What did the building in, and so quickly, is that the steel joists that span
the otherwise unsupported interior of the building (except for the elevator
shaft, which is held to an even higher standard of protection) turned to jello
from the intense heat. It's important to understand that while the intensity
of the blaze was unplanned for, the fact that steel structural members are
incredibly vulnerable to heat due to a fire is known and some way of coping
with exposure to intense heat would have been planned for in the building's
design. The methods of heat protection are _tested_ and characterized by how
long a structural element can withstand the direct application of an intense
flame, and the degrees of protection expected to be provided are measured in
hours, not minutes.
Where the fragile insulating protection on steel beams was torn away by the
blast of the impact, it is no particular surprise that there would have been
almost immediate structural failure, but it should have been localized. The
question is, how did so much of the building become damaged so quickly, and the
most recent speculation I've read is that examination of other buildings of the
same era in New York show a couple of things: very uneven application of the
insulating protection, and critical places where the protection has been
applied thinly or not at all. In the case of the WTC, the insulating
contractor was told not to get fire retardant on the viscoelastic dampers that
help to keep a building from shaking itself to pieces, and so at every place
where the joists join the exterior walls, the fire retardant is thin or missing
from the bottom of the joists where it connects with the viscoelastic damper.
In ordinary (not high rise) construction, there is no material at all in the
space occupied by the viscoelastic damper at all, so one shouldn't be too
concerned about damage to the joist there. Right?
Wrong. Steel is not only weakened by heat, it conducts it, and every place the
structure was exposed directly to radiant or convective heat transfer because
the insulation was thin or missing is a place where heat could enter the
structure far away from the actual blaze, and it was the cumulative effect of
many floors above the blaze collapsing that caused the entire structure to come
down.
What I have described is a contributing factor, but it is not the only one, and
it is not for me to say it is the most important one. It is fair to say that
methods of insulating steel structural elements will be given much greater
scrutiny and that steel structural elements will not be poorly-protected in
future structures, whether the elements themselves are structurally important
or not.
Any blame to be placed on computer modelling here? Not so far as I know. The
calculations to support the hypothesis I just shared with you could easily be
done on a PC--if you knew that it was important to take into account the
missing insulation at the viscoelastic dampers, or even that the insulation
would be missing. As it is, it is a fair bet that no calculation of any direct
relevance to the proposed failure mechanism was part of the design process.
Does this have any relevance to using computers to predict events with which
you have no actual experience? I think it does.
RM
del cecchi
We must recognize that we had two choices: ratify a comprehensive test
ban treaty or don't ratify and continue to test. We chose to ratify.
Once the test ban was ratified, we again had two choices: figure out
what was happening to the stockpile we still needed by simulation and
also perhaps use it to design new or modified weapons or just let the
stockpile sit there and hope it works if, God forbid, we needed to use
it. Well, actually there might be a third choice, rebuild all weapons
Equivilent To New periodically after a time interval for which they are
known to stay good.
Starts to make simulation look good to me.
>
> I have tried to stay away from the policy questions (do we need them,
are they
> good or bad for our security, what should we do with them) to focus
only on the
> role that computers are supposed to play.
good decision, I will too.
I don't think of a chip as a do or die scenario. And building the chip
or protein will reveal errors. Just way fewer and easier to find ones.
Here is an example for you programmer folks. Imagine writing one of
those big programs, takes 30 or 40 people a year or two. million lines
of code more or less. You can do whatever you want, but to actually
compile and run it will cost 1 million USD. Oh and it takes 4 months to
compile and load, probably 6 months total until you find out it works.
If you want to change something it costs between .5 and 1 million
dollars and takes 2 to 4 months, depending on exactly what the change
is.
How would that change your development methodology and tools?
>
> National security applications often don't work that way. If you make
a
> mistake, you won't get a chance to fix it.
>
> The national policy question I did want to address is that if
computers are
> playing such a fundamental role in national security, then the country
is
> playing a fool's game not to fund a significant amount of basic,
disinterested,
> and skeptical research about how to build and use computers,
especially for
> large applications. More sandbox work at LLNL would not qualify, nor
would
> annual classified reviews by hired wizards with a sinecure to protect.
>
> RM
Where you going to find these objective (I presume that is what you
meant by disinterested) competent knowledgable researchers? And if they
are objective do they need to be skeptical? I mean they could hire me,
but how much can one man accomplish? :-)
> >
> >del cecchi
> >
Why did they tag the data with time of day on the patriot anyway? Or
did I misunderstand?
del
Rmyers1400
>Date: 12/20/2003 11:07 PM Eastern Standard Time
>Message-id: <_39Fb.199$kg....@eagle.america.net>
>
<snip>
>
>Starts to make simulation look good to me.
As always, your analysis is built on experience and common sense, and I would
find it hard to quarrel with, but I'm going to do the best I can to duck larger
policy questions and to stick to computers.
<snip>
>I don't think of a chip as a do or die scenario.
I was referring to an earlier post in which you had referred to the fact that
companies have to commit resources to systems that exist only on paper and that
if paper analysis couldn't support such decisions, companies that did business
that way would go out of business.
>And building the chip
>or protein will reveal errors. Just way fewer and easier to find ones.
>Here is an example for you programmer folks. Imagine writing one of
>those big programs, takes 30 or 40 people a year or two. million lines
>of code more or less. You can do whatever you want, but to actually
>compile and run it will cost 1 million USD. Oh and it takes 4 months to
>compile and load, probably 6 months total until you find out it works.
>If you want to change something it costs between .5 and 1 million
>dollars and takes 2 to 4 months, depending on exactly what the change
>is.
>
>How would that change your development methodology and tools?
Hardware designers have learned to live with very harsh rules where they don't
get to say whoops and put out number 12 in a series of ongoing "critical"
patches. That's why I think software designers should be looking at the tools
and methodologies of hardware designers for clues as to how to do business, not
the other way around. I said so repeatedly in a thread with many software
types participating and got repeatedly flamed for doing so. I've spent as much
time as I can shake loose trying to follow my own advice, which is to try to
learn how hardware designers do business.
There are *some* things about large numerical systems, about numerical
artifacts, and about algorithms for which hardware designers might find it
helpful to have someone around who has had the time to study such things, but
having such a subject matter expert involved wouldn't change the methodologies.
<snip>
>
>Where you going to find these objective (I presume that is what you
>meant by disinterested) competent knowledgable researchers? And if they
>are objective do they need to be skeptical? I mean they could hire me,
>but how much can one man accomplish? :-)
You have to live with the fact that disinterested researchers are hard to find
and that most of what you get will be self-interested. You try to compensate
for that by trying to create a diverse ecology of research, rather than an
introspective monoculture.
That means moving more of the money and as much of the criticism as possible
outside the charmed circle of the bomb club.
>Why did they tag the data with time of day on the patriot anyway? Or
>did I misunderstand?
>
The sensing system and the targeting system have to agree about time of day.
If you synchronize and then run for a long period of time without
resynchronizing, the targeting system will be aiming at a point where the
target would have been at some time other than what the sensing system is
really trying to tell it. There is a very similar problem in almost all
non-trivial networking scenarios. Maybe you just don't get to see it or are so
focused on other non-trivial problems that you don't have the time to process
it.
RM
George William Herbert
Once a couple of coeficients were determined
experimentally and a bunch of tests were run,
the efficiency equations in use reached very
high accuracy relatively rapidly for conservative
spherical implosion weapons designs.
The US, of course, wanting to push all sorts of
design envelopes, has designed nuclear weapons
that defy any sort of pen and paper numerical
analysis and require serious computer time to
validate.
A large part of this is geometrical; spheres
stopped being the answer in around 1955.
There's a good treatment on the basics of the
Serber and similar efficiency equations on
the Nuclear Weapons FAQ website at:
http://nuclearweaponarchive.org
-george william herbert
gher...@retro.com
George William Herbert
>Joe Pfeiffer pfei...@cs.nmsu.edu wrote:
>>rmyer...@aol.com (Rmyers1400) writes:
>>> The catastrophic failure of the towers, which
>>> should not have happened, can probably be explained pretty easily--
>>> but in retrospect.
>>
>>Was the collapse unexpected? My impression has been that, given the
>>damage sustained when the planes hit the towers and the amount of
>>flaming kerosene sloshed around, nobody involved in big skyscraper
>>design was the list bit surprised (we laymen were shocked, but that
>>has nothing to do with whether people who knew what they were talking
>>about were).
>
>I guess you've been listening to and/or reading different accounts from the
>ones I have listened to and read. The impact alone did not do enough damage to
>cause the collapse. It is true that a raging inferno of the jet fuel from a
>fully loaded jumbo jet is probably outside the original design envelope of the
>building, but the fire protection that is required on structural elements
>should have provided more time to evacuate than it did--whether the building
>eventually fell or not.
Few points. One, it wasn't a fully loaded jumbo jet;
the 767 weighs about half what a 747 does. Two, the 767
was aabout twice as heavy as the 707 they evaluated as
possibly hitting the towers when they were built. Three,
the lead designer of the WTC towers has quite publically
admitted that a fuel fire was not taken into
>What did the building in, and so quickly, is that the steel joists that span
>the otherwise unsupported interior of the building (except for the elevator
>shaft, which is held to an even higher standard of protection) turned to jello
>from the intense heat. [...]
>
>Where the fragile insulating protection on steel beams was torn away by the
>blast of the impact, it is no particular surprise that there would have been
>almost immediate structural failure, but it should have been localized. The
>question is, how did so much of the building become damaged so quickly,
The answer is rather more simple than your speculation;
the aircraft debris were moving fast enough to blow out the
far wall and columns when they exited the building; anything
in between which was as weak as the insulation on the trusses
that made up the joists would have been blown off over large
parts of the structure from one side to the other.
>[...]
>In ordinary (not high rise) construction, there is no material at all in the
>space occupied by the viscoelastic damper at all, so one shouldn't be too
>concerned about damage to the joist there. Right?
>
>Wrong. Steel is not only weakened by heat, it conducts it, and every place the
>structure was exposed directly to radiant or convective heat transfer because
>the insulation was thin or missing is a place where heat could enter the
>structure far away from the actual blaze, and it was the cumulative effect of
>many floors above the blaze collapsing that caused the entire structure to come
>down.
Have you read the detailed failure analysis reports?
It's clear from them that mere damage to the floors which were
hit, and collapses from that level, is enough to explain the
collapse itself.
Also, the viscoelastic dampers weren't in the joints,
though it's not clear that's what you were trying to say.
>Does this have any relevance to using computers to predict events with which
>you have no actual experience? I think it does.
Certainly. But it also applies to using people to predict
events with which you have no actual experience...
I think some time ago that this spun off the nuclear
weapons simulation thread. Going back to that point,
we do in fact have a large database of experience
on how those work, and a number of tests were done of
off-nominal conditions just to see what happened.
While the credibility of a program that continued to
test warheads would be higher, we can with some degree
of accuracy model existing designs which are just
subject to aging, if we can understand the component
aging and simulate well enough.
The WTC weren't the first highrise buildings to have
large fires, but they were the first highrise buildings
hit by jetliners. Many lessons learned the hard way.
-george william herbert
gher...@retro.com
Rmyers1400
>Date: 12/21/2003 4:19 AM Eastern Standard Time
>Message-id: <bs3oi6$qtl$1...@gw.retro.com>
>
>Rmyers1400 <rmyer...@aol.com> wrote:
<snip>
>>Does this have any relevance to using computers to predict events with which
>>you have no actual experience? I think it does.
>
>Certainly. But it also applies to using people to predict
>events with which you have no actual experience...
>
Before preparing the post to which you are replying, I reread the WTC detailed
failure report and a separate report from an ASCE publication.
1. I mischaracterized the jets as a jumbo jets when in fact they were 767's.
The actual jets were going more slowly than the assumed 707, and the actual
kinetic energy at impact was comparable to that assumed in the original
analysis.
2. I have no idea where you get the idea that the impact damage was enough to
cause a collapse. One building stood for nearly an hour and another for nearly
two hours. The damage assessment is clear that the buildings would have stood
indefinitely in that condition, short of further insult, like a hurricane. In
fact, the redistributed load resulting from the initial damage is the sort of
redistribution of load a high-rise might experience in a high wind. The load
was clearly successfully redistributed after the initial impact.
3. I have no idea what you are talking about with regard to the viscoelastic
dampers. They are attached to the bottom chord of the floor trusses and to the
exterior wall. The only thing the viscoelastic dampers have to do with
anything is that the insulating contractors were told not to get insulating
material on them, very difficult to do without affecting application to the
surrounding area. Those areas became points of entry for heat into a material
with good thermal conductivity.
4. If someone asked me if a particular structural design was adequate, I would
respond that I am not a licensed structural engineer and that they should
consult someone who is. If someone asked me about methodologies for analyzing
complicated systems that might exhibit unexpected behavior, I would contribute
my opinion because I have considerable experience with that, and I have.
>I think some time ago that this spun off the nuclear
>weapons simulation thread. Going back to that point,
>we do in fact have a large database of experience
>on how those work, and a number of tests were done of
>off-nominal conditions just to see what happened.
>While the credibility of a program that continued to
>test warheads would be higher, we can with some degree
>of accuracy model existing designs which are just
>subject to aging, if we can understand the component
>aging and simulate well enough.
>
Even though I made the mistake of commenting on the wisdom of the entire
program once, I'm not going to go there again.
There are some aspects of nuclear technology, like the ignition temperature of
tritium that, whether it does any good or not, are going to remain classified.
That such things will become known one way or another (like a DoE official
spilling the beans in public), won't cut any ice. I'm going to live with the
fact that the chinese government knows more about the details of american
nuclear warheads than american citizens do. Those things are going to remain
behind the fence at National Laboratories and a small number of defense
contractors. That's just the way it's going to be.
There is no corresponding reason why the national laboratories should be left
to play safely in their own computer sandboxes. There is a great deal we don't
know about large simulations, the OP of this thread mentioned one important
area of uncertainty brought forward by Sun, and my point is that, if the
government is going to rely on simulation to the extent of buying the largest
computer in existence to do the calculations, it should seek a larger, more
diverse body of expertise than simply giving more money to the national
laboratories. I didn't reach the conclusion I am advancing by lying awake
staring at the ceiling, but by actual, direct experience. Even if I had no
such experience, the record of the national laboratories with respect to
advancing knowledge in the area of massively parallel simulations is, um,
disappointing.
For any number of reasons, many of them supported by the DoE's own rhetoric,
the case for building a strong national infrastructure for using computation as
a reliable tool for engineering and science is strong. I also believe that the
case for not using that as an excuse to bloat further an already bloated
national laboratory system is equally strong.
>The WTC weren't the first highrise buildings to have
>large fires, but they were the first highrise buildings
>hit by jetliners. Many lessons learned the hard way.
>
At least there is something we agree on.
RM
Andrew Huo
Could we use 256, even 512 bit floating-point unit?
John Plank <john_...@mail.com> wrote:
> [-- text/plain, encoding quoted-printable, charset: koi8-r, 12 lines --]
--
Rmyers1400
>Date: 12/21/2003 7:39 AM Eastern Standard Time
>Message-id: <bs449a$hd6$1...@news.yaako.com>
>
>Rounding is a fundamental problem for any radix.
>Could we use 256, even 512 bit floating-point unit?
>
rounding error in a calculation, and it would tell you if you needed to use a
greater degree of precision, whether the needed precision was supported in
hardware or not. That's a much bigger win than just implementing wider
floating point units.
RM
Thomas Womack
Rmyers1400 <rmyer...@aol.com> wrote:
>>Subject: Re: Sun researchers: Computers do bad math ;)
>>From: zg...@ncic.ac.cn (Andrew Huo)
>>Date: 12/21/2003 7:39 AM Eastern Standard Time
>>Message-id: <bs449a$hd6$1...@news.yaako.com>
>>
>>Rounding is a fundamental problem for any radix.
>>Could we use 256, even 512 bit floating-point unit?
>>
>Properly-implemented interval arithmetic would provide absolute bounds on the
>rounding error in a calculation, and it would tell you if you needed to use a
>greater degree of precision, whether the needed precision was supported in
>hardware or not.
I had been led to believe that interval arithmetic normally provided
absurdly wide bounds on the rounding error, usually vastly larger than
the actual error -- basically because its assumptions are that
independent errors should add as e1 + e2, whilst there's a reasonable
argument that independent errors should add as the variance of normal
distributions with variances e1 and e2, and N errors of size epsilon
correspond to one error of size epsilon \sqrt N. One model lets you
do 2^23 operations on floats without losing precision, the other
something nearer 2^46.
Are we now seeing interval arithmetic with actually-useful error
properties?
Tom
Rmyers1400
>Date: 12/21/2003 8:42 AM Eastern Standard Time
>Message-id: <Fkq*xJ...@news.chiark.greenend.org.uk>
>
<snip>
>
>I had been led to believe that interval arithmetic normally provided
>absurdly wide bounds on the rounding error, usually vastly larger than
>the actual error -- basically because its assumptions are that
>independent errors should add as e1 + e2, whilst there's a reasonable
>argument that independent errors should add as the variance of normal
>distributions with variances e1 and e2, and N errors of size epsilon
>correspond to one error of size epsilon \sqrt N. One model lets you
>do 2^23 operations on floats without losing precision, the other
>something nearer 2^46.
>
>Are we now seeing interval arithmetic with actually-useful error
>properties?
>
No magic that I know of has occurred while your back was turned.
With the state of large-scale computation as it is, and with the proposed
applications, you can't afford to intone "law of large numbers" and hope for
the best.
So does that mean you run your application and get accurate but useless
results? No. It means you have to hand-hold your calculation and do what is
necessary (including higher-precision in software, if necessary) to keep the
absolute error bounds in check.
This is a case where what you don't know can definitely hurt you.
<suppressed pontification about it's high time people start demanding results
of known precision from computer simulation>
RM
jonah thomas
> Here is an example for you programmer folks. Imagine writing one of
> those big programs, takes 30 or 40 people a year or two. million lines
> of code more or less. You can do whatever you want, but to actually
> compile and run it will cost 1 million USD. Oh and it takes 4 months to
> compile and load, probably 6 months total until you find out it works.
> If you want to change something it costs between .5 and 1 million
> dollars and takes 2 to 4 months, depending on exactly what the change
> is.
> How would that change your development methodology and tools?
My immediate reaction is Don't Do That.
If you need the results, I have to say Don't Need That.
It won't work. You know it won't work, I know it won't work, they know
it won't work. Why pretend?
A project that takes one person one year has a fair chance. If it takes
three people a year it has a fair chance. If it takes 10 people a year
it has a chance. If it takes 30 people a year or two and results in a
million lines of code it's doubtful. If it takes 4 months to compile
and load it's very doubtful.
I've been in one project that took 30 people a year after the specs were
complete. (They took a year to write the specs before there was any
code but a few prototypes.) There were a few million lines of code
written, but much fewer in the final result, only a few thousand for
each of the distributed parts of the system. No component took more
than half an hour or so to compile, and they could be tested in
isolation. The whole thing worked on schedule. The only really
critical error was an error in the customer specs that could be handled
the next release. Then the consortium decided to scrap it in favor of
another system proposed by a different consortium member that wasn't
working yet.
If it has a million lines of code you know there are errors, you just
don't know whether there are critical errors. It's more dangerous if it
appears to work because then you might tend to believe the results.
The only excuse for using a system that complicated is that you don't
care whether the results are correct, you only care that they look like
they're correct most of the time. This is fine for, say, a billing
system. If one customer in 50,000 notices an error and calls you on it,
you just fix it for him and continue as if nothing happened. It's fine
for an internet application, if people get garbage every now and then
they just shrug and try the link again or else quit and look at
something that interests them. That's the sort of market you ought to
be looking for, for complicated software. You want it to be something
where it doesn't matter much when it doesn't work very well and it's
acceptable that a lot of the time it doesn't work at all, but they're
very pleased when it does give them something that appears to be correct.
Pardon me if I sound too cynical. I'm overstating the case slightly.
jonah thomas
>From: zg...@ncic.ac.cn (Andrew Huo)
>>Rounding is a fundamental problem for any radix.
>>Could we use 256, even 512 bit floating-point unit?
> Properly-implemented interval arithmetic would provide absolute bounds on the
> rounding error in a calculation, and it would tell you if you needed to use a
> greater degree of precision, whether the needed precision was supported in
> hardware or not. That's a much bigger win than just implementing wider
> floating point units.
Is interval arithmetic overkill? If it gives the absolute maximum and
minimum bounds, aren't those too big?
Say it turns out you have a one in quintillion chance there are no
significant digits, and a one in a trillion chance there are fewer than
seven significant digits. That kind of interval arithmetic wouldn't be
very useful for final calculations.
Something that would be much more useful would be something that can
test small routines and say which inputs in the allowed ranges would
give the worst results, and how bad those results could be. Then you
could at least build up libraries of routines that had the worst
problems patched.
But is this going too far from comp.arch? My central point is that
traditional interval arithmetic is widely regarded as giving intervals
that are too wide to be useful. Is this widespread idea wrong?
Anne & Lynn Wheeler
> I don't think of a chip as a do or die scenario. And building the chip
> or protein will reveal errors. Just way fewer and easier to find ones.
> Here is an example for you programmer folks. Imagine writing one of
> those big programs, takes 30 or 40 people a year or two. million lines
> of code more or less. You can do whatever you want, but to actually
> compile and run it will cost 1 million USD. Oh and it takes 4 months to
> compile and load, probably 6 months total until you find out it works.
> If you want to change something it costs between .5 and 1 million
> dollars and takes 2 to 4 months, depending on exactly what the change
> is.
>
> How would that change your development methodology and tools?
one place is anything human rated .... following is something I had
dredged up from 20 years ago (posted by somebody else) with regard to
dates (slightly related to a y2k thread) ... however, point three
mentions a minor software fix:
http://www.garlic.com/~lynn/99.html#24 BA Solves Y2K (Was: Re: Chinese Solve Y2K)
3.We have an interesting calendar problem in Houston. The Shuttle
Orbiter carries a box called an MTU (Master Timing Unit). The MTU
gives yyyyddd for the date. That's ok, but it runs out to ddd=400
before it rolls over. Mainly to keep the ongoing orbit calculations
smooth. Our simulator (hardware part) handles a date out to ddd=999.
Our simulator (software part) handles a date out to ddd=399. What we
need to do, I guess, is not ever have any 5-week long missions that
start on New Year's Eve. I wrote a requirements change once to try to
straighten this out, but chickened out when I started getting odd
looks and snickers (and enormous cost estimates).
--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/
Internet trivia 20th anv http://www.garlic.com/~lynn/rfcietff.htm
Tom Knight
There's real problems here, having to do with correlations between
numbers. Let's say I want to calculate the parallel resistance of R1
and R2. I can do this as 1/( 1/R1 + 1/R2) and get one result, or I
can do this as R1*R2/(R1 + R2) with a quite different result. Have
fun with compiler optimizations. Of course, these problems arise with
communitivity and associativity of floating add even in today's
machines.
Thomas Womack
Rmyers1400 <rmyer...@aol.com> wrote:
><suppressed pontification about it's high time people start demanding results
>of known precision from computer simulation>
I'm sure they do; run their molecular dynamics program to compute the
expected melting point of erbium, go off to the laboratory and melt
some erbium to see what happens, fix the molecular dynamics and
continue.
http://www.research.ibm.com/journal/sj/402/duan.html
has notes like "For example, Dill and coworkers [7,46] have argued that a
small set of amino acids (hydrophobic and hydrophilic) can be combined
to produce foldable protein-like peptides, a prediction that has been
confirmed recently by experiments. [47]"
These people are scientists, after all.
I don't know how good present techniques are for watching proteins fold
on the time-scales that protein-folding simulations simulate; I'm sure
somebody has checked that the final folded structure is the same one
that comes out of the X-ray crystallography side of things.
Tom
Rmyers1400
>Date: 12/21/2003 12:37 PM Eastern Standard Time
>Message-id: <mSkFb.32$7V2....@news.uswest.net>
>
>Rmyers1400 wrote:
>>From: zg...@ncic.ac.cn (Andrew Huo)
>
>>>Rounding is a fundamental problem for any radix.
>>>Could we use 256, even 512 bit floating-point unit?
>
>> Properly-implemented interval arithmetic would provide absolute bounds on
>the
>> rounding error in a calculation, and it would tell you if you needed to use
>a
>> greater degree of precision, whether the needed precision was supported in
>> hardware or not. That's a much bigger win than just implementing wider
>> floating point units.
>
>Is interval arithmetic overkill? If it gives the absolute maximum and
>minimum bounds, aren't those too big?
>
>Say it turns out you have a one in quintillion chance there are no
>significant digits, and a one in a trillion chance there are fewer than
>seven significant digits. That kind of interval arithmetic wouldn't be
>very useful for final calculations.
>
for you as you go?
Somewhere in your calculation there may be the equivalent of a
poorly-conditioned problem, and you have to pull an answer corresponding to the
smallest eigenvalue out of the numerical soup. Guessing that the law of large
numbers will take care of it for you doesn't cut it. Your answer will be total
garbage, and nothing about the color plots you produce will tell you so.
I might have done it myself, but if I have it's not because I failed to take
steps to avoid it. I've watched other people do it, and I've heard the words
"numerical garbage" used by a national laboratory to dismiss physics that
should have been paid attention to.
Maybe I am attracted to this idea because the circumstance will frequently
arise where you actually have to know what you're doing to coax an answer with
reaonable error bounds out of a problem in a reasonable amount of computing
time.
>Something that would be much more useful would be something that can
>test small routines and say which inputs in the allowed ranges would
>give the worst results, and how bad those results could be. Then you
>could at least build up libraries of routines that had the worst
>problems patched.
>
The equivalent of solvers for systems of stiff ODE's. Sure, when you have a
known problem that you have enough insight to identify ahead of time, you can
probably find a prepackaged solution, but if you're solving a problem with
millions of degrees of freedom, you might not be lucky enough to spot the
poorly-conditioned problem embedded in your simulation.
>But is this going too far from comp.arch? My central point is that
>traditional interval arithmetic is widely regarded as giving intervals
>that are too wide to be useful. Is this widespread idea wrong?
The widespread idea that is wrong is that because computers are available you
no longer have to understand traditional analysis.
You don't need to be able to count on many digits in the final answer for most
engineering problems, but you do need to know how many you can count on, and
you shouldn't be leaving it to luck or a WAG.
The fact that the error bounds are too big is trying to tell you something.
Traditional applied mathematics in the days before computers concerned itself
with ways of subtracting out a large, known part of the answer and using the
limited and painful precision available to address the small, unknown part of
the problem. Not only do you get an answer that's accurate, you gain insight
into the physics and the mathematics.
I don't expect interval arithmetic to take the world by storm anytime soon, but
I don't know of any other methodology that will routinely give you answers of
known accuracy.
Is this too far from comp.arch? Seems like a pretty important question for
computer architects to know about. Why do you need precision? How do you know
how much you need? If you only need a slide-rule answer, why should you need
128 bits to get there? Should you just build computers with wider floating
point units, or do you need to do something like what Sun is proposing? Pretty
boring stuff if you're processing W-2 forms, but if you're building bombs, you
might want to take notes.
RM
Rmyers1400
>Date: 12/21/2003 1:19 PM Eastern Standard Time
>Message-id: <ghx*lK...@news.chiark.greenend.org.uk>
>
>In article <20031221093016...@mb-m15.aol.com>,
>Rmyers1400 <rmyer...@aol.com> wrote:
>
>><suppressed pontification about it's high time people start demanding
>results
>>of known precision from computer simulation>
>
>I'm sure they do; run their molecular dynamics program to compute the
>expected melting point of erbium, go off to the laboratory and melt
>some erbium to see what happens, fix the molecular dynamics and
>continue.
>
>http://www.research.ibm.com/journal/sj/402/duan.html
>
>has notes like "For example, Dill and coworkers [7,46] have argued that a
>small set of amino acids (hydrophobic and hydrophilic) can be combined
>to produce foldable protein-like peptides, a prediction that has been
>confirmed recently by experiments. [47]"
>
of known precision. They have results that agree with experiment to some known
level of accuracy. I'm not going to belabor when, where, and why the
difference could be important, but the circumstances do arise.
The broader context was circumstances where you can't run off to the lab and
confirm your predictions (test ban treaty, and all). Or maybe you've got a
protein folding calculation going that takes a year. Wouldn't you rather find
out after a month that the error was probably going to be unacceptable rather
than wait the entire year?
>These people are scientists, after all.
>
Mmmmph. _Some_ of the people involved in this kind of work have the skills to
be trusted with a computer.
>I don't know how good present techniques are for watching proteins fold
>on the time-scales that protein-folding simulations simulate; I'm sure
>somebody has checked that the final folded structure is the same one
>that comes out of the X-ray crystallography side of things.
>
I don't expect people struggling with protein structure to worry about
precision any time soon. At some point between teraflop and petaflop, people
will start routinely using 128-bits, and that will be that. I'm a realist.
RM
Rmyers1400
>Date: 12/21/2003 1:12 PM Eastern Standard Time
>Message-id: <vuy1xqy...@suspiria.ai.mit.edu>
>
<snip>
>
>There's real problems here, having to do with correlations between
>numbers. Let's say I want to calculate the parallel resistance of R1
>and R2. I can do this as 1/( 1/R1 + 1/R2) and get one result, or I
>can do this as R1*R2/(R1 + R2) with a quite different result. Have
>fun with compiler optimizations. Of course, these problems arise with
>communitivity and associativity of floating add even in today's
>machines.
>
happen), people would get real smart about finite precision arithmetic real
fast. Even if what Sun is proposing results only in heightened awareness of
the problem, that will be a good thing. If people had to live with the harsh
rules imposed by interval arithmetic, people would have to do a good deal more
thinking in setting up and examining the results of numerical simulations, and
that would be a VVGT (Very very good thing).
You may or may not be old enough to remember the horror with which practicing
scientists and engineers greeted the arrival of calculators. I hit graduate
school just as that tidal wave hit, and I thought that the professors who made
such a fuss should really think about retiring. It would appear that with
advancing age, I've come to have more sympathy for their point of view. Maybe
it's time for me to think about retiring.
RM
Mayan
>That's why I think software designers should be looking at the tools
> and methodologies of hardware designers for clues as to how to do business, not
> the other way around.
Having been on both sides of the fence (i.e. both developing uPs and
very large software systems), I'd say the following: there is very
little that they can learn from each other.
First of all: the tough stuff in building a _synthesized_ chip where
_performance_ is not a concern is getting the micro-architecture (i.e.
design) done. Getting the actual verilog/vhdl written is almost never a
big deal; about the only thing that might be complex (in a uP) would be
the decoders.
Now, for a uP, the machine organization, including decisions like
back-pressure signals, where interrupts will get handled, interfaces
with caches etc. are complex, and one has to handle them with care, but
they are no different than, say, designing the core data structures and
the module structure for a compiler or an operating system.
In a synthesized chip, there is another area of complexity - back-end
issues such as hold time violations, etc. These have no real
correspondence in software.
What makes designing a synthesized chip hard is trying to hit an
aggressive timing target. In that case, once the tools come back with
timing information that identifies the critical paths, you have to go in
and optimize those paths. One major difference between software and
hardware is that the frequency is determined by your slowest path. Even
if that path is in a rarely exercised part of the chip, it still impacts
your overall performance.
The ways to optimize are different, too. There is a lot more stuff done
at the level of "lets swap the order of these two statements so that the
compiler does a better job" - things which current software compilers
have become good enough at that most people don't bother.
One tool which hardware people use which software people don't are
formal equivalence checkers. So, if you have a block, and you mutate it,
then these tools tell you if the the two blocks are formally equivalent.
It turns out to be fairly useful but only because the sizes of these
blocks are relatively small. [Say a block has 128 bits of inputs - thats
only 4 words!].
Another area where there is complexity in hardware design is if you go
to full or semi-custom - sort of the equivalent of recoding all or part
of your program using assembly. Again, hardware uses formal tools to
proove that the custom block is semantically equivalent to the orignal
synthesized block (actually, its quite often a 2 step translation:
high-level to schemtic to layout, followed by a two step proof process,
LVS and formal equivalence of schematic vs verilog/vhdl). I think the
actual work of going from C to assembler is somewhat less than Verilog
to a custom layout, probably by a factor of 2 to 4, but this is
completely dependent on the skill of the implementor.
To summarize: the parts of hardware implementation that resemble
software programming are not the difficult bits of a hardware
implementation. The number of states of even a modern microprocessor is
miniscule compared to the number of states of larger programs. Most
(all?) of the tools and approaches used on the hardware side are either
already being used in software, or are not applicable.
Peter Boyle
On Sat, 20 Dec 2003, del cecchi wrote:
> I don't think of a chip as a do or die scenario. And building the chip
> or protein will reveal errors. Just way fewer and easier to find ones.
>
> Here is an example for you programmer folks. Imagine writing one of
> those big programs, takes 30 or 40 people a year or two. million lines
> of code more or less. You can do whatever you want, but to actually
> compile and run it will cost 1 million USD. Oh and it takes 4 months to
> compile and load, probably 6 months total until you find out it works.
> If you want to change something it costs between .5 and 1 million
> dollars and takes 2 to 4 months, depending on exactly what the change
> is.
>
> How would that change your development methodology and tools?
:)
Well the compile probably takes a day or two, it's the load that's
hard. So, I think I would try to write a fast loading but slow
(5Hz?) simulator with a snazzy name like cadopsys and sell it for
extortionate amounts to these people with all this money.
That would let them simulate their code for very short
instruction sequences before hitting the 1Million dollar carriage return
with some reasonable degree of confidence.
if simulators didn't work no-one could build _any_ modern chips.
Peter
jonah thomas
>From: jonah thomas j2th...@cavtel.net
>>Is interval arithmetic overkill? If it gives the absolute maximum and
>>minimum bounds, aren't those too big?
>>Say it turns out you have a one in quintillion chance there are no
>>significant digits, and a one in a trillion chance there are fewer than
>>seven significant digits. That kind of interval arithmetic wouldn't be
>>very useful for final calculations.
> Do you have some methodology that will magically calculate those probabilities
> for you as you go?
No, I don't. But I'm proposing a hypothetical situation. Suppose that
in reality as you do your math, there is a one in quintillion chance
that there are no significant digits, and a one in a trillion chance
that there are fewer than seven significant digits. And suppose that in
this case you do interval arithmetic and it tells you the interval for
your single final answer is [-4.85 E8 to 5.0 E8] when the computed
answer is 3.189267184 E7. The fact that there is a tiny tiny chance
that your answer is total and complete garbage is not the result you
need. The fact that there is only one chance in a trillion that you
have fewer than seven significant digits would be far far more useful to
you.
Now, when you're looking for numerical errors, getting false positives
is a whole lot better than false negatives, up to a point. If you make
a thousand calculations and one of them is wrong, and you throw out the
wrong one along with ten good ones, that's good. You have 989 answers
you can be confident in. Good.
But what happens if interval analysis tells you that none of your
results are any good, when really all but one in a trillion of them are
just fine? If that happens there ought to be a better way.
So, does that happen? Does interval arithmetic actually give useful
error bounds for complex problems?
> Somewhere in your calculation there may be the equivalent of a
> poorly-conditioned problem, and you have to pull an answer corresponding to the
> smallest eigenvalue out of the numerical soup. Guessing that the law of large
> numbers will take care of it for you doesn't cut it. Your answer will be total
> garbage, and nothing about the color plots you produce will tell you so.
> I might have done it myself, but if I have it's not because I failed to take
> steps to avoid it. I've watched other people do it, and I've heard the words
> "numerical garbage" used by a national laboratory to dismiss physics that
> should have been paid attention to.
> Maybe I am attracted to this idea because the circumstance will frequently
> arise where you actually have to know what you're doing to coax an answer with
> reaonable error bounds out of a problem in a reasonable amount of computing
> time.
The complaint I've heard about interval analysis is that it tends to
give error bounds that are too wide to be useful.
So I've tended to prefer monte carlo arithmetic. The complaints I've
heard about that are that it takes 30 times the computations to get the
same result and there are potential concerns that the random number
generators might mess up.
>>Something that would be much more useful would be something that can
>>test small routines and say which inputs in the allowed ranges would
>>give the worst results, and how bad those results could be. Then you
>>could at least build up libraries of routines that had the worst
>>problems patched.
> The equivalent of solvers for systems of stiff ODE's. Sure, when you have a
> known problem that you have enough insight to identify ahead of time, you can
> probably find a prepackaged solution, but if you're solving a problem with
> millions of degrees of freedom, you might not be lucky enough to spot the
> poorly-conditioned problem embedded in your simulation.
Agreed. It doesn't solve everything. But the larger the library of
proven solutions, the more we can isolate the catastrophic problems in
the new code or the glue code. And if we had methods to do automated
numerical analysis for small routines maybe in time they could be
expanded to do automated analysis of small-to-moderate-size routines.
It might eventually lead somewhere.
>>But is this going too far from comp.arch? My central point is that
>>traditional interval arithmetic is widely regarded as giving intervals
>>that are too wide to be useful. Is this widespread idea wrong?
> The widespread idea that is wrong is that because computers are available you
> no longer have to understand traditional analysis.
Yes, agreed. But I find myself imagining what it's like for managers.
They can get lots of programmers who never think about numerical
analysis. So you're a manager who figures he'll do it right this time.
He hires a real, scarce, expensive numerical analyst to figure out
what algorithms to use. The analyst starts thinking. Meanwhile the
coders go ahead and code. When the timeline is 60% complete the analyst
tells the coders they have it all wrong and gives them a more
complicated approach to follow. Meanwhile the manager has no way to
tell whether this analyst even knows what he's talking about except to
get a smarter analyst to give a second opinion. Why risk the schedule
when the customers aren't complaining about bad software anyway?
So again I like the idea of monte carlo arithmetic. "There's no money
to do it right but there's money to do it over."
> Is this too far from comp.arch? Seems like a pretty important question for
> computer architects to know about.
I agree. So long as the computer architects agree we're set.
George William Herbert
>gher...@gw.retro.com (George William Herbert) wrote:
>>>Does this have any relevance to using computers to predict events with which
>>>you have no actual experience? I think it does.
>>
>>Certainly. But it also applies to using people to predict
>>events with which you have no actual experience...
>>
>Before preparing the post to which you are replying, I reread the WTC detailed
>failure report and a separate report from an ASCE publication.
>2. I have no idea where you get the idea that the impact damage was enough to
>cause a collapse. One building stood for nearly an hour and another for nearly
>two hours. The damage assessment is clear that the buildings would have stood
>indefinitely in that condition, short of further insult, like a hurricane. In
>fact, the redistributed load resulting from the initial damage is the sort of
>redistribution of load a high-rise might experience in a high wind. The load
>was clearly successfully redistributed after the initial impact.
I think you misread what I wrote. What I wrote was:
] Have you read the detailed failure analysis reports?
] It's clear from them that mere damage to the floors which were
] hit, and collapses from that level, is enough to explain the
] collapse itself.
I was not referring to initial impact damage; I was referring to
the damage to insulation and thus heat entrance into the structural
system from just the impact being adequate and what we believe
was seen to explain the collapse. You posited that heat entrance
from the viscoelastic dampers above and possibly below the
impact zone caused the collapse to occur across a wider height
of the building, but the best guess is that the actual collapses
in both towers cascaded outwards from failures in the impact
regions due to heating from the immediate fire.
>>I think some time ago that this spun off the nuclear
>>weapons simulation thread. Going back to that point,
>>we do in fact have a large database of experience
>>on how those work, and a number of tests were done of
>>off-nominal conditions just to see what happened.
>>While the credibility of a program that continued to
>>test warheads would be higher, we can with some degree
>>of accuracy model existing designs which are just
>>subject to aging, if we can understand the component
>>aging and simulate well enough.
>>
>Even though I made the mistake of commenting on the wisdom of the entire
>program once, I'm not going to go there again.
>
>There are some aspects of nuclear technology, like the ignition temperature of
>tritium that, whether it does any good or not, are going to remain classified.
The ignition temperature (or rather, temperature/pressure) of tritium
is not classified and is well known. In particular, the fission yield
required to ignite D/T boosting (250 tons) is very well established...
-george william herbert
gher...@retro.com
CJT
> Rmyers1400 wrote:
>
>> From: zg...@ncic.ac.cn (Andrew Huo)
>
>
>>> Rounding is a fundamental problem for any radix.
>>> Could we use 256, even 512 bit floating-point unit?
>
>
>> Properly-implemented interval arithmetic would provide absolute bounds
>> on the
>> rounding error in a calculation, and it would tell you if you needed
>> to use a
>> greater degree of precision, whether the needed precision was
>> supported in
>> hardware or not. That's a much bigger win than just implementing wider
>> floating point units.
>
>
> Is interval arithmetic overkill? If it gives the absolute maximum and
> minimum bounds, aren't those too big?
>
> Say it turns out you have a one in quintillion chance there are no
> significant digits, and a one in a trillion chance there are fewer than
> seven significant digits. That kind of interval arithmetic wouldn't be
> very useful for final calculations.
Murphy's law dictates that the bound will be reached in practice. <g>
>
> Something that would be much more useful would be something that can
> test small routines and say which inputs in the allowed ranges would
> give the worst results, and how bad those results could be. Then you
> could at least build up libraries of routines that had the worst
> problems patched.
>
> But is this going too far from comp.arch? My central point is that
> traditional interval arithmetic is widely regarded as giving intervals
> that are too wide to be useful. Is this widespread idea wrong?
>
--
After being targeted with gigabytes of trash by the "SWEN" worm, I have
concluded we must conceal our e-mail address. Our true address is the
mirror image of what you see before the "@" symbol. It's a shame such
steps are necessary. ...Charlie
CJT
<snip>
>
> The complaint I've heard about interval analysis is that it tends to
> give error bounds that are too wide to be useful.
> <snip>
Those voicing such a compaint probably have a vested interest in having
their (possibly completely flawed) results accepted.
Stephen Sprunk
> Before preparing the post to which you are replying, I reread the WTC
> detailed failure report and a separate report from an ASCE publication.
>
> 1. I mischaracterized the jets as a jumbo jets when in fact they were
767's.
> The actual jets were going more slowly than the assumed 707, and the
actual
> kinetic energy at impact was comparable to that assumed in the original
> analysis.
>
> 2. I have no idea where you get the idea that the impact damage was
> enough to cause a collapse. One building stood for nearly an hour and
> another for nearly two hours. The damage assessment is clear that the
> buildings would have stood indefinitely in that condition, short of
further
> insult, like a hurricane. In fact, the redistributed load resulting from
the
> initial damage is the sort of redistribution of load a high-rise might
> experience in a high wind. The load was clearly successfully
> redistributed after the initial impact.
I saw an interview with the lead designer and he said that while the impact
damage was within their parameters, the critical element was that a B767
carries significantly more fuel than a B707, thus the duration of the
ensuing fire far exceeded what they had designed for and the structure
collapsed. If the hijackers had picked, say, a B737 or had hijacked B767's
closer to the end of their flights, the WTC would still be standing.
S
--
Stephen Sprunk "Stupid people surround themselves with smart
CCIE #3723 people. Smart people surround themselves with
K5SSS smart people who disagree with them." --Aaron Sorkin
Rmyers1400
>Date: 12/21/2003 3:48 PM Eastern Standard Time
>Message-id: <MFnFb.48$7V2....@news.uswest.net>
<snip>
>Suppose that
>in reality as you do your math, there is a one in quintillion chance
>that there are no significant digits, and a one in a trillion chance
>that there are fewer than seven significant digits. And suppose that in
>this case you do interval arithmetic and it tells you the interval for
>your single final answer is [-4.85 E8 to 5.0 E8] when the computed
>answer is 3.189267184 E7. The fact that there is a tiny tiny chance
>that your answer is total and complete garbage is not the result you
>need. The fact that there is only one chance in a trillion that you
>have fewer than seven significant digits would be far far more useful to
>you.
>
First thing I'm going to do to help my frazzled brain is to get rid of an
extraneous factor of 1E7, so my computed answer is 3.189267184 with absolute
error bounds -48.5 and +50.0. To get the kind of result you're talking about,
you'd need to do to about 100 peta-adds of numbers of alternating sign, if I've
done my bit counting correctly (and if I haven't, someone will straighten me
out).
If we have a teraflop machine available to us, the calculation is going to take
100,000 seconds, or about a day of computation, so we've used up a serious
amount of horsepower to arrive at a questionable result.
What to do? Even if quad precision were ten times slower, we'd probably take
the ten days to do the calculation just to see. If we did that a couple of
times and found out that, for the most part, we got the same answer, we might
be tempted to live with the uncertainty of the double precision result.
But suppose we didn't get the same answer. If we got tolerable error bounds
with the quad precision calculation, we might decide just to live with it. If
we couldn't live with it, then we'd have to look for ways to get smart. The
details of getting smart would vary tremendously from problem to problem, but
they would all come down to the same thing: effectively extending the precision
of the calculation by complicated ad hoc bookeeping that allows us to set aside
exactly known large numbers so we can use all of the precision for smaller
numbers that carry all the uncertainty. We can arrange it so that instead of
picking up exactly 1 bit of noise with every addition, we pick up on the
average significantly less than 1 bit of noise with every addition.
Doing that kind of analysis and recoding is expensive, and you'd have to decide
whether it's worth it or not. That's what managers get the big bucks for.
If you didn't have the interval arithmetic available to you, though, you might
never have a clue that something was amiss, so you'd never have an opportunity
to decide how you wanted to cope. You'd just present your color plots and
collect your paycheck.
>So, does that happen? Does interval arithmetic actually give useful
>error bounds for complex problems?
>
I don't think people have done enough routine interval arithmetic to know. Sun
must have done some work to sell the business. :-).
<snip>
>So I've tended to prefer monte carlo arithmetic. The complaints I've
>heard about that are that it takes 30 times the computations to get the
>same result and there are potential concerns that the random number
>generators might mess up.
>
A researcher in Austria claims that random number generators tend to clump
points and that a deterministic series actually works better for integration.
There is a SIAM monograph on the subject, which I could dig up if you were
really interested. You might be able to locate it just from those clues. I
like Monte Carlo for all kinds of reasons.
<snip>
>
>Agreed. It doesn't solve everything. But the larger the library of
>proven solutions, the more we can isolate the catastrophic problems in
>the new code or the glue code. And if we had methods to do automated
>numerical analysis for small routines maybe in time they could be
>expanded to do automated analysis of small-to-moderate-size routines.
>It might eventually lead somewhere.
>
But it all begins with knowing there is a potential problem, and interval
arithmetic is the only routine way I know to identify a potential problem.
<snip>
>Why risk the schedule
>when the customers aren't complaining about bad software anyway?
>
People will get more from computation when they demand more and not sooner.
Fortunately, the pressure to expect more from computation is becoming
significant.
RM
Rmyers1400
<snip>
>
>The ignition temperature (or rather, temperature/pressure) of tritium
>is not classified and is well known. In particular, the fission yield
>required to ignite D/T boosting (250 tons) is very well established...
>
tritium ignites. A DoE official who obligingly told them during a visit to
China that "Tritium ignites if you drop it on the floor" was chastised for
revealing classified information.
RM
RM
del cecchi
"jonah thomas" <j2th...@cavtel.net> wrote in message
news:3FE5D44C...@cavtel.net...
close description of something like a north bridge. For a
microprocessor the numbers are several times worse. It's not 30 people
it's 100 or maybe 200.
del cecchi
>
George William Herbert
>>is not classified and is well known. In particular, the fission yield
>>required to ignite D/T boosting (250 tons) is very well established...
>
>The Chinese Academy of Sciences was very eager to know the
>temperature at which tritium ignites. A DoE official who
>obligingly told them during a visit to China that "Tritium
>ignites if you drop it on the floor" was chastised for
>revealing classified information.
While I am not aware of that particular incident,
as I stated, the ignition parameters for D-T are well known
from inertial confinement fusion, other fusion research,
and other sources, and are widely published in open media,
I seriously doubt that the Chinese are incapable of reading
open source physics journals, or using Google.
They are generally smart and competent people.
There are a lot of details about nuclear programs that
people assume have to be classified material but are
in fact quite widely available.
-george william herbert
gher...@retro.com
Mayan
> Then you never get a new chip design. Cause what I said is a pretty
> close description of something like a north bridge. For a
> microprocessor the numbers are several times worse. It's not 30 people
> it's 100 or maybe 200.
Sorry, del, thats not necessarily true. It depends on:
- how hard are you trying to push technology?
- are you doing a custom (or semi-custom) design, or a synthesized design?
- are you implementing this ISA for the first time?
- how experienced are the designers?
- can you afford to pay for _ALL_ the tools out there?
As a counter point, I'd suggest you look at Raleigh, and see how many
people were involved in the effort to develop some of the 40x
processors. Also, rumor has it that the size of the original Alpha team
wasn't that big (I'm talking just the uP implementation guys, not the
systems, tools, or software teams)
del cecchi
"Mayan" <ma...@sandbridgetech.com> wrote in message
news:vucllqg...@corp.supernews.com...
Poughkeepsie or Boeblingen when I referred to microprocessors. And as
for Raleigh and the 4xx powerPC, how much did they steal ^H^H^H borrow?
And how hard were they pushing that core? I know that the crew in
Rochester that did the Summit chips was pretty good sized and that was
mostly ASIC.
Maybe I was a little heavy, if you are only counting the guys writing
the VHDL, and not the simulators or the timers or the AEs or the PD
guys. But I think you would be hard pressed to do the logic design for
a current generation ASIC with much less than a department. And that is
just the VHDL and a little unit sim.
del cecchi
jonah thomas
> "jonah thomas" <j2th...@cavtel.net> wrote
>>del cecchi wrote:
>>>Here is an example for you programmer folks. Imagine writing one of
>>>those big programs, takes 30 or 40 people a year or two. million
>>>lines
>>>of code more or less. You can do whatever you want, but to actually
>>>compile and run it will cost 1 million USD. Oh and it takes 4
>>>months to
>>>compile and load, probably 6 months total until you find out it
>>>works.
>>>If you want to change something it costs between .5 and 1 million
>>>dollars and takes 2 to 4 months, depending on exactly what the
>>>change is.
>>>How would that change your development methodology and tools?
>>My immediate reaction is Don't Do That.
>>If you need the results, I have to say Don't Need That.
>>It won't work. You know it won't work, I know it won't work, they
>>know it won't work. Why pretend?
>>A project that takes one person one year has a fair chance. If it
>>takes three people a year it has a fair chance. If it takes 10 people a
>>year
>>it has a chance. If it takes 30 people a year or two and results in a
>>million lines of code it's doubtful. If it takes 4 months to compile
>>and load it's very doubtful.
> Then you never get a new chip design. Cause what I said is a pretty
> close description of something like a north bridge. For a
> microprocessor the numbers are several times worse. It's not 30 people
> it's 100 or maybe 200.
Oh! That's different! It also takes a whole department to make a new
automobile design every three years. But it isn't exactly a *new*
automobile design. It takes that many people to make minor
modifications of an existing design that works.
You can't make a new design with that many people.
Mayan
> "Mayan" <ma...@sandbridgetech.com> wrote in message
> news:vucllqg...@corp.supernews.com...
>
>>>del cecchi wrote:
>>>For a
>>>microprocessor the numbers are several times worse. It's not 30 people
>>>it's 100 or maybe 200.
>>
>>Sorry, del, thats not necessarily true. It depends on:
>>As a counter point, I'd suggest you look at Raleigh, and see how many
>>people were involved in the effort to develop some of the 40x
>>processors. Also, rumor has it that the size of the original Alpha
>>team wasn't that big
>
> Poughkeepsie or Boeblingen when I referred to microprocessors.
>
> Maybe I was a little heavy, if you are only counting the guys writing
> the VHDL, and not the simulators or the timers or the AEs or the PD
> guys. But I think you would be hard pressed to do the logic design for
> a current generation ASIC with much less than a department. And that is
> just the VHDL and a little unit sim.
>
> del cecchi
>
Personal estimate - using Verilog OR VHDL, access to full Cadence/Ambit
or Synopsys tool suite, targetting 0.25u using some reasonable standard
cell library, with a moderately experienced team, one could probably do
a synthesized 150 MHz single issue 6 stage pipeline 40x style PowerPC
processor using about 15-20 people in about 18 months, including
modelling, verification, timing closure etc. Basically cold start to
GDS-II.
The stuff you are talking about using 100s of people is mostly where
* you're pushing the technology (first chip in the process, or one of
the first)
* you're pushing the envelope in terms of circuits (dynamic logic + CPL
+ standard CMOS in the same design)
* you're doing a *lot* of custom circuits
* you're pushing existing EDA tools to the edge
* you're building new EDA tools where the existing ones break
* you're trying to control clock-skew to pico-seconds across the entire chip
* you're pushing enough power through the chip that dI/dt becomes a
factor...
* you're putting in massive amounts of RAS etc.
and none of the techniques/tools used to solve these problems really
have any analogues or lessons on the software side.
Nick Maclaren
In article <bs449a$hd6$1...@news.yaako.com>,
zg...@ncic.ac.cn (Andrew Huo) writes:
|> Rounding is a fundamental problem for any radix.
|> Could we use 256, even 512 bit floating-point unit?
Yes. And some of us have done it. As the radix increases, the
numerical properties get worse.
Regards,
Nick Maclaren.
Nick Maclaren
In article <MFnFb.48$7V2....@news.uswest.net>,
jonah thomas <j2th...@cavtel.net> writes:
|>
|> But what happens if interval analysis tells you that none of your
|> results are any good, when really all but one in a trillion of them are
|> just fine? If that happens there ought to be a better way.
That isn't a common scenario. What is more common is for the code
to be iterative and "self-correcting", so worst-case analysis says
there is no accuracy but in fact there is a lot. Try analysing
Newt-Raphson using interval analysis on the basic operations for
an example.
|> So, does that happen? Does interval arithmetic actually give useful
|> error bounds for complex problems?
Not in general, no. It MIGHT do so if it were applied at a higher
level than basic operations.
Regards,
Nick Maclaren.
Nick Maclaren
In article <bs5jvs$3j5$1...@gw.retro.com>,
gher...@gw.retro.com (George William Herbert) writes:
|> Rmyers1400 <rmyer...@aol.com> wrote:
|> >gher...@gw.retro.com (George William Herbert) wrote:
|> >>The ignition temperature (or rather, temperature/pressure) of tritium
|> >>is not classified and is well known. In particular, the fission yield
|> >>required to ignite D/T boosting (250 tons) is very well established...
|> >
|> >The Chinese Academy of Sciences was very eager to know the
|> >temperature at which tritium ignites. A DoE official who
|> >obligingly told them during a visit to China that "Tritium
|> >ignites if you drop it on the floor" was chastised for
|> >revealing classified information.
|>
|> While I am not aware of that particular incident,
|> as I stated, the ignition parameters for D-T are well known
|> from inertial confinement fusion, other fusion research,
|> and other sources, and are widely published in open media,
|>
|> I seriously doubt that the Chinese are incapable of reading
|> open source physics journals, or using Google.
|> They are generally smart and competent people.
I suspect that they were trying to find out which of the visiting
team from the USA were scientists and which were their minders :-)
Regards,
Nick Maclaren.
Jan C. Vorbrüggen
> is determined by your slowest path. Even if that path is in a rarely > exercised part of the chip, it still impacts your overall performance.
Hard real-time systems are conceptually similar.
> One tool which hardware people use which software people don't are
> formal equivalence checkers. So, if you have a block, and you mutate it,
> then these tools tell you if the the two blocks are formally equivalent.
> It turns out to be fairly useful but only because the sizes of these
> blocks are relatively small.
You can do that in software, if your programming language allows you to
do it. It has been done for some languages and designs. Given the "state
of the art" - i.e., C(++) - no way.
Jan
Jan C. Vorbrüggen
> >did I misunderstand?
>
> The sensing system and the targeting system have to agree about time of day.
> If you synchronize and then run for a long period of time without
> resynchronizing, the targeting system will be aiming at a point where the
> target would have been at some time other than what the sensing system is
> really trying to tell it.
I believe that in this case the specification (mostly implicitly, I think)
said that the system wasn't going to run for more than a few hours at a
stretch without relocation and thus resynchronization. Thus, it was being
used contrary to specification during Desert Storm in this respect.
It probably was even a correct decision by the implementors at the time.
Getting two real-time systems to synchronize on the fly is a problem that
has a solution, but it is non-trivial and carries its own risks. Leaving
this feature out when there was no requirement was likely the correct way
of going about it.
Jan
Nick Maclaren
In article <3FE6ACBF...@mediasec.de>,
Jan C. =?iso-8859-1?Q?Vorbr=FCggen?= <jvorbr...@mediasec.de> writes:
|> > One major difference between software and hardware is that the frequency
|> > is determined by your slowest path. Even if that path is in a rarely > exercised part of the chip, it still impacts your overall performance.
|>
|> Hard real-time systems are conceptually similar.
As are seriously parallel applications.
|> > One tool which hardware people use which software people don't are
|> > formal equivalence checkers. So, if you have a block, and you mutate it,
|> > then these tools tell you if the the two blocks are formally equivalent.
|> > It turns out to be fairly useful but only because the sizes of these
|> > blocks are relatively small.
|>
|> You can do that in software, if your programming language allows you to
|> do it. It has been done for some languages and designs. Given the "state
|> of the art" - i.e., C(++) - no way.
It's close to impossible in Fortran, but I agree that C/C++/etc.
are orders of magnitude worse.
Regards,
Nick Maclaren.
Jan C. Vorbrüggen
> |> do it. It has been done for some languages and designs. Given the "state
> |> of the art" - i.e., C(++) - no way.
>
> It's close to impossible in Fortran, but I agree that C/C++/etc.
> are orders of magnitude worse.
I was thinking more along the lines of occam or Z...
Jan
Jan C. Vorbrüggen
> conditioned problem, and you have to pull an answer corresponding to the
> smallest eigenvalue out of the numerical soup. Guessing that the law of
> large numbers will take care of it for you doesn't cut it. Your answer
> will be total garbage, and nothing about the color plots you produce will
> tell you so.
I think that's the main problem - the ill-conditioned problem basically
turns the problem you think you are solving into a different one that you
are _not_ interested in solving. So you need to detect when that happens.
That's what should be good about the Monte-Carlo approach. There are of
course other possibilies if you are solving physical problems - conservation
laws, for instance.
On the other hand, if you're solving physical problems, your results
should not depend on exact initial, intermediate and final values - at
least, as long as the world you are simulating isn't at exactly 0 K.
Jan
Robert Myers
wrote:
>Having been on both sides of the fence (i.e. both developing uPs and
>very large software systems), I'd say the following: there is very
>little that they can learn from each other.
>
<snip>
>
>Another area where there is complexity in hardware design is if you go
>to full or semi-custom - sort of the equivalent of recoding all or part
>of your program using assembly. Again, hardware uses formal tools to
>proove that the custom block is semantically equivalent to the orignal
>synthesized block (actually, its quite often a 2 step translation:
>high-level to schemtic to layout, followed by a two step proof process,
>LVS and formal equivalence of schematic vs verilog/vhdl). I think the
>actual work of going from C to assembler is somewhat less than Verilog
>to a custom layout, probably by a factor of 2 to 4, but this is
>completely dependent on the skill of the implementor.
The by-play between you and Del (hardware) and other posters
(software) suggests why I might not be ready to yield immediately to
your greater experience.
A relatively low-key presentation from IBM has some of the spirit of
my thinking:
http://www.haifa.il.ibm.com/Workshops/SoftwareTesting2002/papers/Cross_cs.pdf
but, IMHO, it would require the skills of a cultural anthropologist
with a strong technical background to understand why two fields with
so much in common function so differently. And I persist in believing
it would be worth the effort.
RM
Robert Myers
>
>In article <MFnFb.48$7V2....@news.uswest.net>,
>jonah thomas <j2th...@cavtel.net> writes:
>|>
>|> But what happens if interval analysis tells you that none of your
>|> results are any good, when really all but one in a trillion of them are
>|> just fine? If that happens there ought to be a better way.
>
>That isn't a common scenario. What is more common is for the code
>to be iterative and "self-correcting", so worst-case analysis says
>there is no accuracy but in fact there is a lot. Try analysing
>Newt-Raphson using interval analysis on the basic operations for
>an example.
>
Naive application of interval arithmetic to Newton-Raphson would be
silly. Naive implementation of Newton-Raphson without interval
arithmetic can fail to converge or converge to an unexpected zero.
If you need to know that a zero of a function lies with 100% certainty
within a certain (hyper)-volume of the domain of a function, it might
be best to have a numerical analyst handy. Double that if you need to
know that you know with 100% certainty that you have found all the
zeroes within a specified (hyper)-volume of the domain of the
function.
I do not agree with the assertion that most numerical applications are
iterative. It certainly has not been true of the applications I have
encountered in practice. The only common exception I can think of is
finding zeroes, which can be a nasty business if you have limited
knowledge of the function whose zeroes you are seeking.
RM
Nick Maclaren
In article <10jduvso2hloajg23...@4ax.com>,
Robert Myers <rmy...@rustuck.com> writes:
|> >
|> >That isn't a common scenario. What is more common is for the code
|> >to be iterative and "self-correcting", so worst-case analysis says
|> >there is no accuracy but in fact there is a lot. Try analysing
|> >Newt-Raphson using interval analysis on the basic operations for
|> >an example.
|> >
|> Naive application of interval arithmetic to Newton-Raphson would be
|> silly. Naive implementation of Newton-Raphson without interval
|> arithmetic can fail to converge or converge to an unexpected zero.
That was my point. However, PRECISELY the same remarks apply to ALL
convergent iterative methods, and there are a lot of them. Newton-
Raphson is merely an excellent example, because it is simple enough
to analyse and powerful enough to be widely used.
|> I do not agree with the assertion that most numerical applications are
|> iterative. It certainly has not been true of the applications I have
|> encountered in practice. The only common exception I can think of is
|> finding zeroes, which can be a nasty business if you have limited
|> knowledge of the function whose zeroes you are seeking.
Who asserted that?
If that is the only common exception you have seen, then you need
to get out and about a bit - there are lots of others, including
most forms of non-linear optimisation.
Regards,
Nick Maclaren.
Robert Myers
>
>In article <10jduvso2hloajg23...@4ax.com>,
>Robert Myers <rmy...@rustuck.com> writes:
<snip>
>
>|> I do not agree with the assertion that most numerical applications are
>|> iterative. It certainly has not been true of the applications I have
>|> encountered in practice. The only common exception I can think of is
>|> finding zeroes, which can be a nasty business if you have limited
>|> knowledge of the function whose zeroes you are seeking.
>
>Who asserted that?
>
>If that is the only common exception you have seen, then you need
>to get out and about a bit - there are lots of others, including
>most forms of non-linear optimisation.
>
That's not just another form of finding zeroes?
As to your advice to get out more, most of my friends would agree.
How do I tell my friends that they are less interesting than the
people on comp.arch? ;-).
RM
Nick Maclaren
In article <aeoduvc8l5kih4751...@4ax.com>,
Robert Myers <rmy...@rustuck.com> writes:
|> >
|> >If that is the only common exception you have seen, then you need
|> >to get out and about a bit - there are lots of others, including
|> >most forms of non-linear optimisation.
|>
|> That's not just another form of finding zeroes?
No. At a naive level, there are similarities, but optimisation
covers a multitude of sins, not all of which can me mapped into
that form. Consider, for example, seriation. This involves finding
an order of points that approximately minimises a mismatch function.
Because the ordering is a discrete set, the mismatch function is not
differentiable.
|> As to your advice to get out more, most of my friends would agree.
|> How do I tell my friends that they are less interesting than the
|> people on comp.arch? ;-).
Get some new friends?
Regards,
Nick Maclaren.
Kim Enkovaara
>
> First of all: the tough stuff in building a _synthesized_ chip where
> _performance_ is not a concern is getting the micro-architecture (i.e.
> design) done. Getting the actual verilog/vhdl written is almost never a
> big deal; about the only thing that might be complex (in a uP) would be
> the decoders.
But verification of that design is a huge task. Nowadays 60-70% of the total design time go to verification of the design. At least in the telecom side chips. There are all kinds of new formal methods (model checking, assertions etc.) to check designs, but mainly it is just hard work. My impression is that at SW side testing is not taken as seriously, you can always just make a new release of the SW. With HW it takes months to even get something out of the fab.
> One tool which hardware people use which software people don't are
> formal equivalence checkers. So, if you have a block, and you mutate it,
> then these tools tell you if the the two blocks are formally equivalent.
> It turns out to be fairly useful but only because the sizes of these
> blocks are relatively small. [Say a block has 128 bits of inputs - thats
> only 4 words!].
Fortunaltely your information is old :) Currently the best equivalence checkers can easily verify 5-10M gates in one go at gate-to-gate level. Usually that doesn't even need over 4G of memory, and it takes few hours. From RTL-to-gates the capacity is little smaller, but still millions of gates. RTL->gate verification is extremely useful methodoly for ECO rounds, where you tweak netlist by hand. After that you just verify formaly, that the netlist fix is the same as the real RTL fix.
--Kim
jonah thomas
>>Somewhere in your calculation there may be the equivalent of a poorly-
>>conditioned problem, and you have to pull an answer corresponding to the
>>smallest eigenvalue out of the numerical soup. Guessing that the law of
>>large numbers will take care of it for you doesn't cut it. Your answer
>>will be total garbage, and nothing about the color plots you produce will
>>tell you so.
> I think that's the main problem - the ill-conditioned problem basically
> turns the problem you think you are solving into a different one that you
> are _not_ interested in solving. So you need to detect when that happens.
> That's what should be good about the Monte-Carlo approach. There are of
> course other possibilies if you are solving physical problems - conservation
> laws, for instance.
If you do monte carlo arithmetic you have a perfect candidate for
parallel computing. Run 30 or more similar problems that need no
interconnection until the end. They'll be doing single-instruction too,
until one of them diverges enough to take a different branch.
If we did all our math that way we'd have a perfect excuse for 30-fold
or 50-fold parallelism even without really good communication. If you
can sell that then you have something to build on.
Robert Myers
<kim.en...@tellabs.com> wrote:
>Mayan wrote:
>>
>> First of all: the tough stuff in building a _synthesized_ chip where
>> _performance_ is not a concern is getting the micro-architecture (i.e.
>> design) done. Getting the actual verilog/vhdl written is almost never a
>> big deal; about the only thing that might be complex (in a uP) would be
>> the decoders.
>
>But verification of that design is a huge task. Nowadays 60-70% of the
> total design time go to verification of the design. At least in the telecom
>side chips. There are all kinds of new formal methods (model checking,
>assertions etc.) to check designs, but mainly it is just hard work.
>My impression is that at SW side testing is not taken as seriously, you
>can always just make a new release of the SW. With HW it takes months
>to even get something out of the fab.
>
I keep trying to tell people that's the story. The software people
(who knows what I am; a hopeless theoretician, I guess) react with
horror. You don't understand...blah, blah, blah. More states...blah,
blah, blah.
>> One tool which hardware people use which software people don't are
>> formal equivalence checkers. So, if you have a block, and you mutate it,
>> then these tools tell you if the the two blocks are formally equivalent.
>> It turns out to be fairly useful but only because the sizes of these
>> blocks are relatively small. [Say a block has 128 bits of inputs - thats
>> only 4 words!].
>
>Fortunaltely your information is old :) Currently the best equivalence
>checkers can easily verify 5-10M gates in one go at gate-to-gate level.
>Usually that doesn't even need over 4G of memory, and it takes few hours.
>From RTL-to-gates the capacity is little smaller, but still millions of gates.
>RTL->gate verification is extremely useful methodoly for ECO rounds,
>where you tweak netlist by hand. After that you just verify formaly, that
>the netlist fix is the same as the real RTL fix.
>
Real story: the tools are out there. People hide behind the idea that
it's an impossible problem, anyway, so they don't bother.
Real reality: it's expensive, and a software vendor who was routinely
that careful would soon go out of business.
So we have a new law of nature, right up there with the second law of
thermodynamics: convenient, true by observation, founded on who knows
what: software is inherently buggy and there is nothing you can do
about it.
RM
Toon Moene
"Friend" is a C++ word.
--
Toon Moene - mailto:to...@moene.indiv.nluug.nl - phoneto: +31 346 214290
Saturnushof 14, 3738 XG Maartensdijk, The Netherlands
Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
GNU Fortran 95: http://gcc.gnu.org/fortran/ (under construction)
Del Cecchi
> Rmyers1400 wrote:
> >That's why I think software designers should be looking at the tools
> > and methodologies of hardware designers for clues as to how to do
business, not
> > the other way around.
>
> Having been on both sides of the fence (i.e. both developing uPs and
> very large software systems), I'd say the following: there is very
> little that they can learn from each other.
>
> _performance_ is not a concern is getting the micro-architecture (i.e.
> design) done. Getting the actual verilog/vhdl written is almost never a
> big deal; about the only thing that might be complex (in a uP) would be
> the decoders.
>
Then there should never be logical errors in a first pass synthesized chip.
And the bug counts during simulation should rapidly drop to zero.
Unfortunately that is not the case.
del cecchi
I'm not sure that there is much cross pollination possible, but don't
trivialize the problem.
Nick Maclaren
In article <vubv7nk...@corp.supernews.com>,
Mayan <ma...@sandbridgetech.com> writes:
|>
|> Having been on both sides of the fence (i.e. both developing uPs and
|> very large software systems), I'd say the following: there is very
|> little that they can learn from each other.
Well, I have been on only one, but I have extensive experience of
debugging both in the field (a.k.a. known as systems management),
and I disagree.
|> One tool which hardware people use which software people don't are
|> formal equivalence checkers. So, if you have a block, and you mutate it,
|> then these tools tell you if the the two blocks are formally equivalent.
|> It turns out to be fairly useful but only because the sizes of these
|> blocks are relatively small. [Say a block has 128 bits of inputs - thats
|> only 4 words!].
Oh, really? I was doing that 30+ years ago - in software - and I
was and am not unique. I would agree that software people ALMOST
never do that, but one thing that they should learn from the
hardware people is that they SHOULD do it!
|> To summarize: the parts of hardware implementation that resemble
|> software programming are not the difficult bits of a hardware
|> implementation. The number of states of even a modern microprocessor is
|> miniscule compared to the number of states of larger programs. Most
|> (all?) of the tools and approaches used on the hardware side are either
|> already being used in software, or are not applicable.
Far more of them are applicable than you might think. As Jan
Vorbrueggen and I were agreeing, 99% of the problem is that the
programming languages and programming paradigms commonly used by
the software communities are not amenable to formal or even
semi-formal verification. The same was true of the methods of
hardware design used for first-generation systems.
What the software people need to learn from the hardware people
is that using such languages and paradigms is incompatible with
building large, robust, scalable systems.
Regards,
Nick Maclaren.
Del Cecchi
somewhat easier. And of course you have to have RAS, and testability, and
JTAG and LBIST.... And you usually have to figure out the function too, at
least at the level of fine detail.
I'm not sure that the tools do have commonality, since software is so much
easier to change. If Microsoft had to replace chips everytime they had
released a security patch, they wouldn't have 50 billion in the bank. :-)
I don't know that arguing over the details is necessary, and I'm not in a
position to be posting detailed information anyway.
del
jonah thomas
> Far more of them are applicable than you might think. As Jan
> Vorbrueggen and I were agreeing, 99% of the problem is that the
> programming languages and programming paradigms commonly used by
> the software communities are not amenable to formal or even
> semi-formal verification. The same was true of the methods of
> hardware design used for first-generation systems.
!! What would it take for a language/paradigm etc to be good for formal
verification? Could you throw us a link or two?
> What the software people need to learn from the hardware people
> is that using such languages and paradigms is incompatible with
> building large, robust, scalable systems.
Yes, that's clear. My thought has been that if we can't have large,
robust, scalable systems we should settle for small robust systems, and
possibly arrange for small robust systems that are scalable with respect
to data.
If we could do verification and make it actually work, we might get
large software systems that work.
Tell us how!
Nick Maclaren
In article <bKDFb.380$wS4....@news.uswest.net>, jonah thomas <j2th...@cavtel.net> writes:
|> Nick Maclaren wrote:
|>
|> > Far more of them are applicable than you might think. As Jan
|> > Vorbrueggen and I were agreeing, 99% of the problem is that the
|> > programming languages and programming paradigms commonly used by
|> > the software communities are not amenable to formal or even
|> > semi-formal verification. The same was true of the methods of
|> > hardware design used for first-generation systems.
|>
|> !! What would it take for a language/paradigm etc to be good for formal
|> verification? Could you throw us a link or two?
Look up the Z system for an example. The main requirements are that
it is precisely defined, with enough power that people can program
without invoking undefined behaviour. The secondary ones, which are
harder to specify, is that it is mathematically 'clean', so that
standard invariants, results and tools can be used.
Java fails badly on the second. Fortran is mediocre on both. C and
C++ are dismal on both.
|> > What the software people need to learn from the hardware people
|> > is that using such languages and paradigms is incompatible with
|> > building large, robust, scalable systems.
|>
|> Yes, that's clear. My thought has been that if we can't have large,
|> robust, scalable systems we should settle for small robust systems, and
|> possibly arrange for small robust systems that are scalable with respect
|> to data.
|>
|> If we could do verification and make it actually work, we might get
|> large software systems that work.
|>
|> Tell us how!
See if you can find out IBM Hursley (if I recall) did the redesign
of CICS using the Z system. See if you can find out about tools
like PFORT (c. 1970).
Regards,
Nick Maclaren.
Jean-Marc Bourguet
> What the software people need to learn from the hardware people
> is that using such languages and paradigms is incompatible with
> building large, robust, scalable systems.
The case seems difficult... Do you know in which langages and with
which paradigms are programmed the formal verification tools hardware
people use ? :-(
Yours,
--
Jean-Marc
Mayan
> On Mon, 22 Dec 2003 14:55:05 +0200, Kim Enkovaara
> <kim.en...@tellabs.com> wrote:
>
>
>>Mayan wrote:
>>
> I keep trying to tell people that's the story. The software people
> (who knows what I am; a hopeless theoretician, I guess) react with
> horror. You don't understand...blah, blah, blah. More states...blah,
> blah, blah.
Actually, its a lot of things. Here's how the formal verification tools
that I am familiar with work:
- they build a DAG for each of the circuits
- they reduce the DAG to a normal form
- they check to see if the normal form of the DAG is identical.
(Usually, they use some form of BDDs; for instance, they represent the
circuit using only AND+INV or NANDs or something like that)
Now, here are a couple of drawbacks:
- they don't deal with cycles. It generally doesn't matter in uPs since
if you cut the cycles at identical points in both circuits and prove the
equivalence of the resulting DAGs, you've proved the equivalence of the
circuit with cycles. However, this doesn't work if the number of
iterations is different (e.g. I don't think you can prove the
equivalence of a unrolled (or partly unrolled) loop and the original
loop using h/w style verification)
- they don't deal with state. But this is not important to them, since
they don't look at cycles, so the value of a register/RAM can be safely
treated as separate variables. Constructs like pointer traversals
definitely don't fit in that mindset.
- they don't deal with very large states. As someone said, they can
handle upto 5-10M gates. Assuming that a 32 bit variable is set at each
step, and _only_ 32 equations are introduced at each point, that is
equivalent to a 200k-instruction program {50klocs?}; on the other hand,
things like + and (worse * or / - or floating point!) end up introducing
way more equations. You'd be lucky to be able to check the equivalence
of a 10kloc program.
So: you can prove the equivalence of 10kloc programs that have identical
looping behavior and have very severe constraints on the kinds of
memory accesses that are allowed.
> Real story: the tools are out there. People hide behind the idea that
> it's an impossible problem, anyway, so they don't bother.
Real story: people have looked at it, quite extensively. And figured out
that it _is_ impossible for any real problem.
Instead of going after a hardware based approach, look up the literature
on global value numbering and static alias analysis in compilers. Thats
a much closer analog - you're trying to prove equivalence of two
different expressions (i.e. the pointer addresses). Its considerably
easier, since the expressions are being evaluated in the context of the
same program and false positives are acceptable, but even then, its
still pretty intractable.
BTW: there's another issue: these tools work by proving the equivalence
of _TWO_ programs; that means, up-front, writing two pieces of code with
identical semantics. Reason why it works in h/w is that they have to
write multiple programs [HDL -> schematic -> layout], and/or their tools
don't work all the time, so they have to verify the output of the tools
w.r.t the original.
Another place they use it is when they modify a circuit to improve
performance; however, those modifications are fairly trivial compared to
what one does in software to improve performance, in terms of the effort
to verify. They very rarely do things that are the equivalent of
space-time tradeoffs or algorithm changes such as replacing a
bucket-sort with a merge-sort.
Nick Maclaren
In article <pxbwu8o...@news.bourguet.org>,
I know about them, yes. But I also know of at least one case where
a large software product (CICS) was verified using Z, and the figures
on improvement to RAS, speed to (real) production release and number
of bug reports when released were impressive.
Regards,
Nick Maclaren.
Peter Boyle
On Mon, 22 Dec 2003, jonah thomas wrote:
> If you do monte carlo arithmetic you have a perfect candidate for
> parallel computing. Run 30 or more similar problems that need no
> interconnection until the end. They'll be doing single-instruction too,
> until one of them diverges enough to take a different branch.
>
> If we did all our math that way we'd have a perfect excuse for 30-fold
> or 50-fold parallelism even without really good communication. If you
> can sell that then you have something to build on.
Then you'll discover that in the _hard_ problems (10^30 parameter space)
you need to importance sample.
Then you start using a Metropolis algorithm.
Then you discover the algorithm doesn't generate independent
samples fast enough to thermalise when you're running trivially parallel.
Then you start parallelising, and you're back to tightly coupled.
Peter
Erik Elmgren
...
Not really responding directly...
Assuming bugs _are_ more frequent in software:
Might another reason for more and higher frequency of bugs in software
compared to hardware be that the total amount of software is far
larger than the amount of hardware. When measured by "complexity".
Or, to put it another way.
If you measure the total number of critical (bug might result)
decisions for all "designers" in the world. I assume you will find
that a much larger number of such are made in the software design
compared to hardware design. If we further assume that being hit by a
software bug is about as bad as being hit by a hardware bug. Is it not
then correct that we (humankind) spend a lot more effort per
complexity in preventing hardware bugs from happening?
How would yo compare the complexity of a program to the complexity of
a chip anyway? one logic gate = one line of code?
And does _anyone_ have an actual count of bugs in software per
complexity with bugs in hardware per complexity?
Not that bugs are beneficial or anything like that, but sometimes more
of good _is_ better than less of perfect.
Erik
Del Cecchi
"Robert Myers" <rmy...@rustuck.com> wrote in message
news:qdhduv04675ltd9g2...@4ax.com...
If building the product costs little, then folks will find the errors by
doing so. It is only if building the product is expensive that simulation
and other tools will be employed to find the errors prior to building the
product. Simulation is a poor substitute for the real thing. I would ventu
re to say that FPGA designers rely much less on simulation (or formal
verification) than do custom or ASIC designers.
I'm not convinced that the two fields really have that much in common.
Perhaps there is more a continuum like so:
custom =>ASIC=>FPGA=>microcode=>device drivers/hard
realtime=>OS/transaction=>scientific
del cecchi
Robert Myers
wrote:
<snip>
>
>If building the product costs little, then folks will find the errors by
>doing so. It is only if building the product is expensive that simulation
>and other tools will be employed to find the errors prior to building the
>product. Simulation is a poor substitute for the real thing. I would ventu
>re to say that FPGA designers rely much less on simulation (or formal
>verification) than do custom or ASIC designers.
>
>I'm not convinced that the two fields really have that much in common.
>Perhaps there is more a continuum like so:
>
>custom =>ASIC=>FPGA=>microcode=>device drivers/hard
>realtime=>OS/transaction=>scientific
>
That's a nice proposal.
Barring an implausible (but possible) advance in compiler technology,
we've got to find the connections. People have to write
comprehensible, maintainable code that will execute efficiently and
reliably on multiple generations of real hardware.
As far as I am concerned, we have progressed barely past the ad hoc
Fortran compiler stage on the software side. That's why I am so
stubborn.
RM
jonah thomas
Wow.
Let me make an analogy.
Some PCs use a parity bit for each byte of RAM. This increases the RAM
needed by 1/8 and there are various overheads. In theory this means you
get some indication of RAM problems; if you don't have it you could be
getting hardware errors that you simply don't find out about. Of
course, in theory you also miss the multiple errors that result in
unchanged parity, so you don't actually find them all. And in practice
most people have no interest in parity errors. Their software doesn't
deal with it so when it happens every six months to two years or so
their computer crashes. They'd usually rather just get an error they
don't notice than have a crash and lose work.
I feel like I just recommended using a parity bit so you at least don't
stay completely unaware of the problem, and you told me that it isn't
enough, that we must bank all RAM in triplicate and do a triple compare
and choose the best 2 out of 3 when there's a discrepancy, and log the
errors -- and that all the software has to be rewritten to deal with the
case when the triplicate RAM has three different values.
Do you see what I mean? Here's a simple approach that can find many
algorithmic errors using very little thought on anybody's part. It
could be used for relatively simple problems without people particularly
noticing except when it finds an error. It provides a *use* for the
processing power that vendors want to pack into PCs that most users
currently have little use for. If users start noticing the occasional
errors in their simple routines it will help spread the idea that
there's an issue here.
There could be a market, solving the problems we know how to solve
easily. And that would help create the market for solutions to the hard
problems.
j...@watson.ibm.com
on 21 Dec 2003 13:22:54 GMT,
rmyer...@aol.com (Rmyers1400) writes:
>>Subject: Re: Sun researchers: Computers do bad math ;)
>>From: zg...@ncic.ac.cn (Andrew Huo)
>>Date: 12/21/2003 7:39 AM Eastern Standard Time
>>Message-id: <bs449a$hd6$1...@news.yaako.com>
>>
>>Rounding is a fundamental problem for any radix.
>>Could we use 256, even 512 bit floating-point unit?
>>
>Properly-implemented interval arithmetic would provide absolute bounds on the
>rounding error in a calculation, and it would tell you if you needed to use a
>greater degree of precision, whether the needed precision was supported in
>hardware or not. That's a much bigger win than just implementing wider
>floating point units.
Interval arithmetic on real problems will generally give an
error bound of (-Inf,Inf) which tells you absolutely nothing. Wider
floating point is far more useful which is why it is far more widely
available.
James B. Shearer
jonah thomas
> rmyer...@aol.com (Rmyers1400) writes:
>>Properly-implemented interval arithmetic would provide absolute bounds on the
>>rounding error in a calculation, and it would tell you if you needed to use a
>>greater degree of precision, whether the needed precision was supported in
>>hardware or not. That's a much bigger win than just implementing wider
>>floating point units.
> Interval arithmetic on real problems will generally give an
> error bound of (-Inf,Inf) which tells you absolutely nothing. Wider
> floating point is far more useful which is why it is far more widely
> available.
Would it be possible to use a variation on interval arithmetic, or some
alternative that does something similar, to get more reasonable error
bounds?
If every real problem gives the possibility of a wild concatenation of
errors that makes the result completely worthless, still some algorithms
are better than others and it would be valuable if we got a confidence
interval of 95%, or 99%, or 99.99999% as opposed to absolute certainty.
j...@watson.ibm.com
on 21 Dec 2003 23:26:39 GMT,
rmyer...@aol.com (Rmyers1400) writes:
<snip>
>But it all begins with knowing there is a potential problem, and interval
>arithmetic is the only routine way I know to identify a potential problem.
This is so wrong.
First interval arithmetic is not a routine way to identify
problems. It is almost never used for this and for good reasons.
Second there are routine ways to identify problems.
These include
1. Running test cases for which the answer is known.
2. Running test cases with slightly perturbed input data.
3. Running test cases in higher precision.
James B. Shearer
Robert Myers
Perhaps I should have said it is the only automatic way I know of to
identify problems. The way that most people due numerical analysis
corresponds to running a compiler with all the warning flags turned
off. For Terje, that might be a safe practice. For most people, it
wouldn't.
Who knows what kinds of problems you are used to doing and under what
kind of pressure. What we're talking about here are huge applications
of critical importance often being run by people with little or no
insight into the numerics and often under considerable time pressure.
No time to do sensitivity analysis, no time to take the code apart, no
time to do anything but put the code on the computer and run it.
If you don't think that engineering models are used that way, you
didn't pay attention to the most recent incident with the shuttle.
That was a small model, but some of the models are not small.
You've got thousands, hundreds of thousands of lines of code, you're
running it under circumstances you've not encountered before, and
you're not sitting in ibm's watson labs.
Interval arithmetic is overkill? Possibly. *If* people start to use
it to any extent, the technology will evolve, or, as I said to Tom
Knight, people will get smart about finite precision arithmetic real
fast.
RM
Robert Myers
>In article <20031221082254...@mb-m15.aol.com>,
> on 21 Dec 2003 13:22:54 GMT,
> rmyer...@aol.com (Rmyers1400) writes:
>>>Subject: Re: Sun researchers: Computers do bad math ;)
>>>From: zg...@ncic.ac.cn (Andrew Huo)
>>>Date: 12/21/2003 7:39 AM Eastern Standard Time
>>>Message-id: <bs449a$hd6$1...@news.yaako.com>
>>>
>>>Rounding is a fundamental problem for any radix.
>>>Could we use 256, even 512 bit floating-point unit?
>>>
>>Properly-implemented interval arithmetic would provide absolute bounds on the
>>rounding error in a calculation, and it would tell you if you needed to use a
>>greater degree of precision, whether the needed precision was supported in
>>hardware or not. That's a much bigger win than just implementing wider
>>floating point units.
>
> Interval arithmetic on real problems will generally give an
>error bound of (-Inf,Inf) which tells you absolutely nothing.
That has happened with code you run, and it doesn't trouble you? You
made no effort to find out where the error bound got out of control
and why?
>Wider
>floating point is far more useful which is why it is far more widely
>available.
>
And what happens to the error bound when you widen the precision?
Still [-inf,+inf], then you still have a problem.
What Tom Womack said, I will agree with: the law of large numbers
generally lets you get alot more than what the worst case analysis
would predict, but you are counting on luck.
You can run sensitivity analyses if you have the time, but you still
have to pull the code apart and find out where the poorly conditioned
problem is.
The compiler warning is a fairly good analogy: with interval
arithmetic you would wind up doing some work juggling arithmetic to
get more reasonable error bounds without really changing the
reliability of the calculation. That is to say, you will respond to
alot of false alarms. Just as with compiler warnings, it's the case
you fix that isn't a false alarm that counts.
Back to the case I mentioned: running an engineering model under
pressure. Even if there is no time to fix the problem, wouldn't you
rather know that there might be a problem, and that the prediction
can't necessarily be counted on (conservative) than just to hope for
the best? That wouldn't have happened in the shuttle orbiter
incident, but if it had been such a model, and you decided that you
couldn't rely on it, the story might have turned out differently.
Same story with the dead Americans in Saudi Arabia.
Hope everything is safe and comfy at the labs.
RM
jonah thomas
> - they don't deal with very large states. As someone said, they can
> handle upto 5-10M gates. Assuming that a 32 bit variable is set at each
> step, and _only_ 32 equations are introduced at each point, that is
> equivalent to a 200k-instruction program {50klocs?}; on the other hand,
> things like + and (worse * or / - or floating point!) end up introducing
> way more equations. You'd be lucky to be able to check the equivalence
> of a 10kloc program.
So a rough measure of complexity would put a line of code as roughly
equivalent to 500 to 1000 gates? That sounds plausible, somewhere
around the right order of magnitude doesn't it?
> Real story: people have looked at it, quite extensively. And figured out
> that it _is_ impossible for any real problem.
Maybe some way might be found to change the problems to something solvable?
> Instead of going after a hardware based approach, look up the literature
> on global value numbering and static alias analysis in compilers. Thats
> a much closer analog - you're trying to prove equivalence of two
> different expressions (i.e. the pointer addresses). Its considerably
> easier, since the expressions are being evaluated in the context of the
> same program and false positives are acceptable, but even then, its
> still pretty intractable.
So, don't do that?
> BTW: there's another issue: these tools work by proving the equivalence
> of _TWO_ programs; that means, up-front, writing two pieces of code with
> identical semantics. Reason why it works in h/w is that they have to
> write multiple programs [HDL -> schematic -> layout], and/or their tools
> don't work all the time, so they have to verify the output of the tools
> w.r.t the original.
That would give a way for hardware teams to be bigger without increasing
the complexity. If you re-do the same work three times and the goal is
not to change anything and show that it isn't changed, that's at first
approximation three times the coding time. But it's one design,
translated 3 times. One set of bugs plus whatever people introduce when
they rewrite.
> Another place they use it is when they modify a circuit to improve
> performance; however, those modifications are fairly trivial compared to
> what one does in software to improve performance, in terms of the effort
> to verify. They very rarely do things that are the equivalent of
> space-time tradeoffs or algorithm changes such as replacing a
> bucket-sort with a merge-sort.
There's a lesson for software people. Do *less* modification and *more*
design, documentation, testing etc and you'll introduce fewer bugs.
jonah thomas
> If building the product costs little, then folks will find the errors by
> doing so. It is only if building the product is expensive that simulation
> and other tools will be employed to find the errors prior to building the
> product. Simulation is a poor substitute for the real thing.
This is clearly true, and clearly it's wrong for it to be that way.
Agreed, simulation is a poor substitute for the real thing. Instead of
just the errors in the product you also get the errors in the
simulation, and sometimes the latter hide the former.
But when we want the product to be reliable, it isn't enough to make
some copies and test them some and release them to the public to test
them further. At least, it isn't acceptable for hardware. It seems to
be the norm for software.
Formal methods that worked would be very good. Lacking that, maybe the
best method is to do simple things and connect them simply, and try to
keep it simple enough to make sense.
j...@watson.ibm.com
on Mon, 22 Dec 2003 19:11:57 -0500,
jonah thomas <j2th...@cavtel.net> writes:
>j...@watson.ibm.com wrote:
>> rmyer...@aol.com (Rmyers1400) writes:
>
>>>Properly-implemented interval arithmetic would provide absolute bounds on the
>>>rounding error in a calculation, and it would tell you if you needed to use a
>>>greater degree of precision, whether the needed precision was supported in
>>>hardware or not. That's a much bigger win than just implementing wider
>>>floating point units.
>
>> Interval arithmetic on real problems will generally give an
>> error bound of (-Inf,Inf) which tells you absolutely nothing. Wider
>> floating point is far more useful which is why it is far more widely
>> available.
>
>Would it be possible to use a variation on interval arithmetic, or some
>alternative that does something similar, to get more reasonable error
>bounds?
Probably not in general.
>If every real problem gives the possibility of a wild concatenation of
>errors that makes the result completely worthless, still some algorithms
>are better than others and it would be valuable if we got a confidence
>interval of 95%, or 99%, or 99.99999% as opposed to absolute certainty.
That is not the problem. Interval arithmetic may give
error bounds of (-Inf,Inf) when it is absolutely certain, not just
overwhelmingly probable, that your answer is correct to 12 digits.
James B. Shearer
j...@watson.ibm.com
on Mon, 22 Dec 2003 19:38:34 -0500,
Interval arithmetic is useless here. You do not have time
to run the problem with interval arithmetic which is certainly not
currently automatic. Not that it matters much since you know it
will report error bounds of (-Inf,Inf) regardless of the actual
errors.
>If you don't think that engineering models are used that way, you
>didn't pay attention to the most recent incident with the shuttle.
>That was a small model, but some of the models are not small.
>
>You've got thousands, hundreds of thousands of lines of code, you're
>running it under circumstances you've not encountered before, and
>you're not sitting in ibm's watson labs.
I don't use tests which will always report the code is
broken even when it isn't.
The lesson of the shuttle is you will get nowhere telling
management there might be a problem. You best be able to prove there
is a problem. If you run the code on a test problem where the answer
is known and the code gets the wrong answer you have a chance of
convincing management that the code might have a problem. If on the
other hand the code gets the right answer on all the test cases but
interval arithmetic says the error bounds are (-Inf,Inf) management
is unlikely to do anything.
James B. Shearer
j...@watson.ibm.com
on Mon, 22 Dec 2003 20:00:34 -0500,
This is not how you use wider precision. If the double
precision (64 bit) answer agrees with the extended precision (128
bit) answer to 12 decimal places it is likely (but not certain)
that the double precision answer is correct to 12 decimal places.
If on the other hand the double precision answer and the
extended precision answer agree to 0 decimal places then you know
you have a problem.
>What Tom Womack said, I will agree with: the law of large numbers
>generally lets you get alot more than what the worst case analysis
>would predict, but you are counting on luck.
No, you are not counting on luck. Interval arithmetic
assumes errors are not correlated so in the worst case they will
always reinforce. But in many real algorithms the errors are
correlated in such a way that they will tend to cancel out as
the calculation proceeds. There is no luck involved.
>You can run sensitivity analyses if you have the time, but you still
>have to pull the code apart and find out where the poorly conditioned
>problem is.
Not if there is no poorly conditioned problem.
>The compiler warning is a fairly good analogy: with interval
>arithmetic you would wind up doing some work juggling arithmetic to
>get more reasonable error bounds without really changing the
>reliability of the calculation. That is to say, you will respond to
>alot of false alarms. Just as with compiler warnings, it's the case
>you fix that isn't a false alarm that counts.
Modifying code to eliminate compiler warnings is usually
easy even when there is no real problem.
Modifying code to get rid of false interval arithmetic
alarms is generally extremely difficult.
>Back to the case I mentioned: running an engineering model under
>pressure. Even if there is no time to fix the problem, wouldn't you
>rather know that there might be a problem, and that the prediction
>can't necessarily be counted on (conservative) than just to hope for
>the best? That wouldn't have happened in the shuttle orbiter
>incident, but if it had been such a model, and you decided that you
>couldn't rely on it, the story might have turned out differently.
>Same story with the dead Americans in Saudi Arabia.
Almost any real code might have problems. Interval
arithmetic isn't telling you anything you don't already know.
>Hope everything is safe and comfy at the labs.
You got something against my employer?
James B. Shearer
dooley
> Nick Maclaren wrote:
>
> > Far more of them are applicable than you might think. As Jan
> > Vorbrueggen and I were agreeing, 99% of the problem is that the
> > programming languages and programming paradigms commonly used by
> > the software communities are not amenable to formal or even
> > semi-formal verification. The same was true of the methods of
> > hardware design used for first-generation systems.
>
> !! What would it take for a language/paradigm etc to be good for formal
> verification? Could you throw us a link or two?
>
language and a subset of ada
Phil
http://www.sparkada.com/ and http://www.sparkada.com/publications.html
Nick Maclaren
In article <20031222....@pkmfgvm4.POK.IBM.COM>,
j...@watson.ibm.com writes:
|> In article <o04fuv0ogbceiu9h6...@4ax.com>,
|> on Mon, 22 Dec 2003 20:00:34 -0500,
|> Robert Myers <rmy...@rustuck.com> writes:
|>
|> >What Tom Womack said, I will agree with: the law of large numbers
|> >generally lets you get alot more than what the worst case analysis
|> >would predict, but you are counting on luck.
|>
|> No, you are not counting on luck. Interval arithmetic
|> assumes errors are not correlated so in the worst case they will
|> always reinforce. But in many real algorithms the errors are
|> correlated in such a way that they will tend to cancel out as
|> the calculation proceeds. There is no luck involved.
Actually, Robert Myers is right. Until you have done the analysis,
which requires skill and effort even for simple problems and is
often impractical in large ones, you have no idea how the errors
will interact. Incidentally, to your list of techniques, I would
add
4. Running on a machine with different arithmetic or with
probabilistic rounding
There are classic cases where the errors interact in such a way as
to produce a stable but completely bogus answer (see Kahan and
others). Interval arithmetic will detect these case but, as you
say, it will not distinguish them from convergent iteration.
Kahan is right in that it is the only sure method of detecting all
causes of inaccuracy, but he skips over its deficiencies. In
addition to its failure to handle error cancellation and convergence,
it is reliable ONLY if it is extended to all data types. This is
the same reason why IEEE error handling has been and will continue
to be a failure - i.e. it is too easy to lose the error state.
Regards,
Nick Maclaren.
Norbert Juffa
> In article <20031221082254...@mb-m15.aol.com>,
> on 21 Dec 2003 13:22:54 GMT,
> rmyer...@aol.com (Rmyers1400) writes:
> >Properly-implemented interval arithmetic would provide absolute bounds on the
> >rounding error in a calculation, and it would tell you if you needed to use a
> >greater degree of precision, whether the needed precision was supported in
> >hardware or not. That's a much bigger win than just implementing wider
> >floating point units.
>
> Interval arithmetic on real problems will generally give an
> error bound of (-Inf,Inf) which tells you absolutely nothing. Wider
> floating point is far more useful which is why it is far more widely
> available.
> James B. Shearer
I don't think this is strictly true. Certainly a naive approach to interval
arithmetic won't do much good. But improved versions have been somewhat
successful as I recall. I remember that about 10 years ago, IBM sold software
called ARITH-XSC. I think it was based mostly on the work of Prof. Kulisch,
then at the University of Karlsruhe, Germany. One basic idea was to combine
interval arithmetic with an accurate dot-product. The other idea was to use
variable precision arithmetic in conjunction with interval arithmetic.
Certainly the ARITH-XSC software wasn't without flaws and a quick check on
IBM's website seems to indicate that they are no longer selling the product.
Kahan et al published a critical paper on the predecessor software ARITH in
the mid 1980s or thereabouts.
-- Norbert
Russell Wallace
wrote:
>Here is an example for you programmer folks. Imagine writing one of
>those big programs, takes 30 or 40 people a year or two. million lines
>of code more or less. You can do whatever you want, but to actually
>compile and run it will cost 1 million USD. Oh and it takes 4 months to
>compile and load, probably 6 months total until you find out it works.
>If you want to change something it costs between .5 and 1 million
>dollars and takes 2 to 4 months, depending on exactly what the change
>is.
>
>How would that change your development methodology and tools?
A sine qua non would be some sort of emulator for the target platform,
so we could (at least mostly) test the code without spending $1
million a shot. If such an emulator didn't exist, it would have to be
written early in the project. If it couldn't be written, the project
would have to be cancelled.
Obviously, a simulator for microchips or other hardware devices can be
regarded as an emulator for the laws of physics.
--
"Sore wa himitsu desu."
To reply by email, remove
the small snack from address.
http://www.esatclear.ie/~rwallace
Terje Mathisen
> Perhaps I should have said it is the only automatic way I know of to
> identify problems. The way that most people due numerical analysis
> corresponds to running a compiler with all the warning flags turned
> off. For Terje, that might be a safe practice. For most people, it
> wouldn't.
Wow! No way!
Rather the opposite, in fact:
I routinely run my compilers in some sort of 'maximally-pedantic' mode,
i.e. turn on all possible warnings and make all warnings full stop errors.
Then I'll go back in and identify the few exceptions, like in the places
where I'll have an inline asm function with no visible return value
(because I know that the proper register already contains it), and turn
off that specific error for that function only.
I always write an explicit compare with zero if I want to use some form
of assignment in a C if() test, i.e.:
if ((c = *inbuf++) == 0) break;
I've been programming since 1977, and I've written 3 or 4 non-trivial
programs that were "perfect", i.e. working as intended on the first
invocation of the compiler/assembler, as well as no bugs detected later.
(Notice that I am not claiming that they are bugfree though!)
What this has taught me is that I need all the help I can get to at
least get rid of all (most of) my trivial mistakes.
Terje
--
- <Terje.M...@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"
Robert Myers
>In article <o04fuv0ogbceiu9h6...@4ax.com>,
> on Mon, 22 Dec 2003 20:00:34 -0500,
> Robert Myers <rmy...@rustuck.com> writes:
<snip>
>
>>What Tom Womack said, I will agree with: the law of large numbers
>>generally lets you get alot more than what the worst case analysis
>>would predict, but you are counting on luck.
>
> No, you are not counting on luck. Interval arithmetic
>assumes errors are not correlated so in the worst case they will
>always reinforce. But in many real algorithms the errors are
>correlated in such a way that they will tend to cancel out as
>the calculation proceeds. There is no luck involved.
>
If I only isolated this statement as a measure of your competence and
judgment, I would conclude that I didn't want you to do any numerical
analysis for me, because, as you started out responding to my comments
about interval arithmetic, "it is so wrong."
I will assume that, just like me, you occasionally turn a statement in
which you have strong personal belief into a statement in which
everyone should have a strong personal belief and overstate it.
You are _counting_ on the errors not correlating. You don't know that
they don't. The fact that they very often don't, and with
overwhelming likelihood, doesn't mean that you have any certainty that
they don't. You are counting on luck.
In my list of horror stories, I have an experience where sets of
quasi-random data were correlated in a way that changed the answer to
the problem in a significant way. Were it not for an off-hand
conversation passed on to me second-hand from one programmer to
another, it might have taken me forever to untangle what was
happening. In the meantime, the customer was suspicious that we
didn't know what we were doing, and you don't ever fully recover from
a black eye like that.
In the mind of the programmer, I'm sure it was something like "Well,
they are just random, so what difference does it make if I do it one
way or another." It made a big difference.
>>You can run sensitivity analyses if you have the time, but you still
>>have to pull the code apart and find out where the poorly conditioned
>>problem is.
>
> Not if there is no poorly conditioned problem.
>
Right. If there is no problem, you are happy, and you go on with your
work.
>>The compiler warning is a fairly good analogy: with interval
>>arithmetic you would wind up doing some work juggling arithmetic to
>>get more reasonable error bounds without really changing the
>>reliability of the calculation. That is to say, you will respond to
>>alot of false alarms. Just as with compiler warnings, it's the case
>>you fix that isn't a false alarm that counts.
>
> Modifying code to eliminate compiler warnings is usually
>easy even when there is no real problem.
> Modifying code to get rid of false interval arithmetic
>alarms is generally extremely difficult.
>
So someone with some competence and insight looks at the code where
the problem is occurring, concludes that it is an artifact of interval
arithmetic and also makes a judgment that the time cannot be spared to
make it behave acceptably under interval arithmetic, so you use
standard arithmetic, bugger the interval arithmetic results, make a
note that you have done so, and move on.
You will no longer have results with known error bounds, but you have
results where you have examined all of the possible causes for
significant error due to roundoff, and made a professional judgment
that they are unimportant. Not only that, there is a record that you
made such a judgment and the changes to the code are documented, so
people will know where to come looking when something goes wrong.
That's why you get the big bucks.
>>Back to the case I mentioned: running an engineering model under
>>pressure. Even if there is no time to fix the problem, wouldn't you
>>rather know that there might be a problem, and that the prediction
>>can't necessarily be counted on (conservative) than just to hope for
>>the best? That wouldn't have happened in the shuttle orbiter
>>incident, but if it had been such a model, and you decided that you
>>couldn't rely on it, the story might have turned out differently.
>>Same story with the dead Americans in Saudi Arabia.
>
> Almost any real code might have problems. Interval
>arithmetic isn't telling you anything you don't already know.
>
It would have in Saudi Arabia.
>>Hope everything is safe and comfy at the labs.
>
> You got something against my employer?
No. I am a great admirer both of IBM and of the Watson labs, both of
which have a proud record of advancing the state of the art rather
than simply trying to make money as fast as possible from what others
have discovered.
RM
Christoph Breitkopf
> I routinely run my compilers in some sort of 'maximally-pedantic'
> mode, i.e. turn on all possible warnings and make all warnings full
> stop errors.
I like to do that, too ...
> Then I'll go back in and identify the few exceptions, like in the
> places where I'll have an inline asm function with no visible return
> value (because I know that the proper register already contains it),
> and turn off that specific error for that function only.
... but if you happen to work on multiple platforms with
different compilers, that approach can end up with the
warning-suppressing comments or pragmas being longer than
the code itself :-( Unless I'm overlooking a good
solution?
Regards,
Chris
Nick Maclaren
In article <bs924m$5l5$1...@osl016lin.hda.hydro.com>,
Terje Mathisen <terje.m...@hda.hydro.com> writes:
|> Robert Myers wrote:
|> > Perhaps I should have said it is the only automatic way I know of to
|> > identify problems. The way that most people due numerical analysis
|> > corresponds to running a compiler with all the warning flags turned
|> > off. For Terje, that might be a safe practice. For most people, it
|> > wouldn't.
|>
|> Wow! No way!
|>
|> Rather the opposite, in fact:
|>
|> I routinely run my compilers in some sort of 'maximally-pedantic' mode,
|> i.e. turn on all possible warnings and make all warnings full stop errors.
I attempt that, but find that I can't do the last because of compiler
bugs and prejudices. Usually, I can write code to be warning-free,
but some compilers issue incorrect or unreasonable warnings. gcc
-Wall -ansi -pedantic is a pretty good set of defaults for most uses,
though switching on extra checking is worth it for seriously portable
code, as is compiling it on 2-3 other compilers in similar modes.
|> I've been programming since 1977, and I've written 3 or 4 non-trivial
|> programs that were "perfect", i.e. working as intended on the first
|> invocation of the compiler/assembler, as well as no bugs detected later.
|>
|> (Notice that I am not claiming that they are bugfree though!)
|>
|> What this has taught me is that I need all the help I can get to at
|> least get rid of all (most of) my trivial mistakes.
Quite. I have been programming since 1966, and don't claim any
more than that. What is more, is that they were written in the
days when it took half a day to get a compilation, and so I triple
checked before attempting it. Nowadays, I slam it through the
compiler, get rid of the obvious errors, and THEN double-check
the logic.
And the longest was c. 200 lines. David Wheeler has said that he
doesn't believe a correct program has ever been written, and I
am not prepared to assert the contrary :-)
I have written longer programs where the only errors were in my
error handling. So, if I had followed the modern practice of not
coding any error detection, the program would have worked ....
But, generally, my test for a well-engineered program is the
proportion of errors that are picked up and diagnosed by itself,
rather than being exposed as failures.
Regards,
Nick Maclaren.
Tarjei T. Jensen
> I always write an explicit compare with zero if I want to use some form
> of assignment in a C if() test, i.e.:
>
> if ((c = *inbuf++) == 0) break;
That should of course be (white space added for my convenience)
if ( 0 == (c = *inbuf++) ) break;
In C one should always put the constant before the expression when comparing
values. That make it easier to detect comparison errors.
greetings,
Nick Maclaren
In article <m3wu8nl...@eddie.mignet.magrathea.de>,
Yes, you are. NEVER use those things! A spurious warning is
better than complicating the code with a system-dependent hack to
supress it. Remember that such hacks have to be maintained.
The correct solution is to rewrite the code in a way that doesn't
provoke such warnings, which normally indicate a slightly dubious
or risky construction. You can get rid of 95% of such warnings,
without complicating your code, and often by improving it.
In the cases where you can't (e.g. the compiler is prejudiced
against something, or just plain broken), then you should insert
a comment saying that spurious warning is to be expected, why and
why it does not matter. It may happen elsewhere.
The same thing applies to most system-dependent code. I have
rewritten several hundred lines of #ifdef spaghetti as 5 lines of
portable code, only to have the change rejected on the grounds
that the maintainer didn't know what the original code did on all
systems!
Regards,
Nick Maclaren.
jonah thomas
>Interval arithmetic may give
> error bounds of (-Inf,Inf) when it is absolutely certain, not just
> overwhelmingly probable, that your answer is correct to 12 digits.
You mean, you know the right answer and the computed answer happens to
be close? Sure, that can happen. But even if it happens 95% of the
time, is that good enough?
My concern here is how *often* does interval arithmetic give error
bounds that are far too wide. If it's one time in a thousand, I'd live
with that to throw out the real errors. One in a hundred is pushing it
and one in two is too much.
Sometimes the law of large numbers will be reliable. It looks like the
problems come particularly when a few errors are particularly important.
Russell Wallace
>In article <bs449a$hd6$1...@news.yaako.com>,
>zg...@ncic.ac.cn (Andrew Huo) writes:
>|> Rounding is a fundamental problem for any radix.
>|> Could we use 256, even 512 bit floating-point unit?
>
>Yes. And some of us have done it. As the radix increases, the
>numerical properties get worse.
How so? I understand there are certain (hopefully rare) cases where
higher precision won't help, but how could it ever be actually harmful
(apart from costing more)?
Christoph Breitkopf
Easier for the compiler - people are another matter. And it
would be nice if we could write more for the next programmer,
not for the compiler. I still say "if x is zero ...", not the
other way round. Of course, it's just a matter of getting used
to an idiom - we programmers have had to get used to lots of
strange ways to express ourselves. This is just one I have
avoided so far.
As Terje said, he has lots of warnings switched on, so the first
form should be ok, too (with a recent (younger than 10 years) compiler,
at least).
Regadrs,
Chris
Nick Maclaren
In article <3fe8162d....@news.eircom.net>,
wallacet...@eircom.net (Russell Wallace) writes:
|> On 22 Dec 2003 08:21:34 GMT, nm...@cus.cam.ac.uk (Nick Maclaren) wrote:
|> >In article <bs449a$hd6$1...@news.yaako.com>,
|> >zg...@ncic.ac.cn (Andrew Huo) writes:
|> >|> Rounding is a fundamental problem for any radix.
|> >|> Could we use 256, even 512 bit floating-point unit?
|> >
|> >Yes. And some of us have done it. As the radix increases, the
|> >numerical properties get worse.
|>
|> How so? I understand there are certain (hopefully rare) cases where
|> higher precision won't help, but how could it ever be actually harmful
|> (apart from costing more)?
Well, I could provide examples of where extra precision can harm,
but I agree that they are VERY rare. However, the original question
was about the RADIX.
For a given number of bits and all other properties being equal,
the numerical properties of a floating-point representation get
worse as the radix increases. This is largely because of the
inscreasing discrepancy between the largest and smallest relative
precision.
Regards,
Nick Maclaren.