Re: Branch & bound for not everywhere defiend constraints
> Date: Tue, 8 Sep 2009 10:35:07 -0400
> From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
> Subject: Re: Branch & bound for not everywhere defiend constraints
> To: STDS-1788@xxxxxxxxxxxxxxxxx
>
> Dan Zuras Intervals wrote:
> >> . . .
> >>>
> >>> Under these circumstances, your previously described
> >>> algorithm would require nothing more than these.
> >>>
> >>> Would that get us closer?
> >>
> >> Probably. I should mention it does not matter to me what we call the
> >> various flags, states, etc. It is the properties of them that
> >> matter, as well as the implementation choices (hardware and
> >> software) that 1788 may allow or prohibit, either explicitly or
> >> implicity.
> >
> > The properties are just what we have to define in 1788.
> >
> > However, the implementation choices are not up to us.
> > They are the choice of the implementor.
> >
> > We cannot mandate that they provide hardware support
> > for intervals at all, much less of any particular
> > architecture.
> >
> > The best we can do is make it easy for them to choose
> > fast & efficient implementations.
> >
> > The rest is up to them & the market they serve.
>
> Yes, all of this is true. But how the standard is written will largely
> determine if anyone will even pay notice or consider an implementation at
> all. We can't shrug our shoulders and say the choice isn't up to us, since
> how we write the standard will have influence.
I thought I had been saying that.
>
> . . .
>
> >> Yes. However, the trend clearly seems to be away from this and
> >> towards large vector processing units of only 32-bit and 64-bit
> >> floating-point values, e.g., SSE registers and the Larrabee VPU.
> >
> > Again, not so. In Itanium they are using an 82-bit
> > datatype both internally & in memory. And, while the
> > machines you mention have a 32- or 64-bit memory
> > architecture, their internal busses are wider to
> > accomodate extra range and/or precision.
> >
> > There is another thing to consider & another reason to
> > keep things like decorations at the level of an
> > abstraction.
> >
> > So long as we specify that a decorated interval consist
> > of an 'undecorated' interval together with an associated
> > decoration, we have said nothing about how that decoration
> > appears or how it is associated with the interval.
>
> No. This absolutely rules out the entire NaI concept.
Other than in name, I don't see how.
>
> . . .
>
> >
> > An adequately clever implementation might choose to store
> > the interval part in one place & the decoration somewhere
> > else & count on a similarly smart compiler to maintain
> > the association. So, for example, arrays of intervals
> > parts could be packed up efficiently on power-of-two
> > boundaries with arrays of their decorations stored
> > elsewhere (perhaps ALSO on smaller power-of-two
> > boundaries).
> >
> > Such an approach has its merits (it eliminates all your
> > valid complaints)
>
> Nothing is further from the truth!
Really?
>
> I think you miss the most important facts about NaI:
Do I?
>
> For the branch-and-bound algorithms, everything you describe is entirely
> unneccesary. All that a user needs to get up and running with fast
> branch-and-bound using NaI can be written in a few pages of C++ code; it
> only uses power-of-two datatypes; and it does not chop the interval datatype
> into two separate pieces of memory that must be managed separately by a
> compiler and specialized hardware.
It all seems entirely equivalent to me. The issue of
power-or-two in size is not so important as you make it
out to be, IMHO. The rest is a question of the choices
an implementation makes to beat its competition.
>
> In the past, Arnold has mentioned probably the only reason for use of the
> PossiblyUndefined flag (a decoration) will be for existence algorithms. If
> these algorithms can be reformulated into branch-and-bound, and if NaIs
> exist, the existence problems can be solved entirely without global/local
> flags or decorated intervals!
Or, entirely without NaIs as you conceive them. Beyond
your desire for powers of two, it is a question of name
only, I think.
>
> So why would any user or vendor want to incur all the overhead you describe?
> It makes no sense to me, and I don't think it will to users or vendors,
> either. There needs to be a more clear reason why this is necessary.
Is there extra overhead? How can one compare without a
similar abstraction describing NaIs as you wish them to be?
>
> . . .
>
> >>> There is every reason to expect that efficient hardware
> >>> support for decorated intervals could be implemented along
> >>> similar lines.
> >>
> >> I don't think its a question of "could." Its a question of "should."
> >
> > That is not a question for us. The implementors must
> > answer that question. The best we can do is make it
> > easy to make the choice we would like to see.
>
> I agree.
>
> . . .
>
> >
> >>
> >> I'm highly skeptical there is one. More likely, hardware vendors
> >> will want to retrofit intervals into their existing products with
> >> power-of-two registers.
> >
> > Could be. Especially at first. We must proselytize
> > intervals to the world if we expect anything more.
>
> Yes. And provide interval software products/applications that demonstrate
> the benefits of intervals, perhaps sans the speed of a hardware-supported
> platform but otherwise as fast as possible.
Of course. I believe I said that.
>
>
>
>
> >
> >>
> >> Maybe someone should ask Intel or AMD so we don't have to guess.
> >
> > They won't know yet. And they won't bother to find
> > out until Intel thinks AMD might beat them in the
> > market with fast interval hardware. Or vice versa.
>
> I'm not so sure. In any case, it wouldn't hurt to get their opinion.
Very well: Any Intel or AMD guys out there who wish
to weigh in on how they would like to implement
intervals in hardware? If not & you know anyone at
either company, please forward the request.
>
> . . .
>
> >> Yes. As a *possibility*. However, a fully functional and efficient
> >> implementation of 1788 should also be possible to retrofit into
> >> existing power-of-two registers. If not, hardware vendors may resort
> >> to non-conforming implementations to get around this. Or they may
> >> simply decide not to support intervals at all.
> >
> > Again, look more carefully at these chips. Even those
> > chips you cite that have power-or-two memory architectures
> > have non-power-of-two busses at the register level.
> >
> > But none of this is important to us. The implementors
> > will either support intervals in some way or they won't.
> > And a thing like not having a power-or-two number of bits
> > in a data abstraction won't rise to the level of changing
> > that decision for them.
>
> I'm very skeptical this is true, especially since non-power-of-two datatype
> formats don't seem to be neccessary at all if NaIs are used.
Or NaIs by the name you give them are unneccessary given
as adequate set of decorations. Is it a question of
perspective, is it not?
>
> . . .
>
> >>> We may be closer than you think...
Then again, I may have been premature. :-)
> >>
> >> I just want to see blazing fast interval hardware. Soon. If we make
> >> it easy for hardware vendors to retrofit intervals into existing
> >> floating-point hardware, like the SSE registers or the Larrabee VPU,
> >> I think it increases chances the hardware vendors will actually
> >> provide interval support.
> >>
> >> At the same time, I agree this shouldn't compromise the flexibility
> >> of other possible implementations. So I appreciate there is a
> >> tension between many competing forces. But this is further reason in
> >> my mind why we should examine all of them carefully.
> >>
> >> Nate Hayes
> >
> > I'd like to see blazing fast hardware as well.
> >
> > Don't expect it to show up the day we publish 1788.
> >
> > Maybe not even for the design cycle after that.
> >
> > But if we do our job well AND the world finds there
> > is a demand for interval methods, it will happen in
> > the next design cycle.
> >
> > Call it 4 to 6 years. Give or take.
>
> That's about what I would expect and/or hope for.
>
> Nate Hayes
Nate, I think this should be a relatively minor issue
given all the others we need to settle before we have
a workable standard.
Let it play out. It may turn out that decorations will
have some flaw other than the non-power-of-two business
that damns them for our purposes. Or they may save us
from throwing away all (or most) NaIs altogther.
Let's see.
Yours,
Dan