Re: Branch & bound for not everywhere defiend constraints
> Date: Mon, 7 Sep 2009 23:05:43 -0400
> From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
> Subject: Re: Branch & bound for not everywhere defiend constraints
> To: STDS-1788@xxxxxxxxxxxxxxxxx
>
> Dan Zuras Intervals wrote:
> . . .
> >>
> >> The difference is "Empty" doesn't propagate the same way as
> >> "TotallyUndefined," since "Empty" may be absorbed by union operations
> >> whereas "TotallyUndefined" is guaranteed to propagate all the way
> >> to the end of a computation.
> >
> > Oh, I think we may be able to accomodate both.
> >
> > Read the propagation rules for decorations I proposed
> > in this forum more carefully.
> >
> > You will find that a domain error results in both an
> > empty, which is a property of the of the interval
> > portion of the decorated interval & persists so long
> > as the interval is empty, AND emptyHappened (or you
> > could call it isOrWasEmpty) which is a decoration,
> > never goes away, & has all the properties of an NaI
> > that you require.
> >
> > Further, you might object to a silent loss of information
> > in a PARTIAL domain error such as sqrt([-1,1]). I think
> > this a perfectly reasonable criticism. I also think it
> > perfectly reasonable to have a decoration called, say,
> > partialDomainError or partiallyEmpty that ALSO propagates
> > like an NaI.
> >
> > 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.
>
> . . .
>
> >> Along this route, I think its important to distinguish: a "decorated
> >> interval" is [double,double] plus a byte for state information.
> >> So the size (in bits) of any decorated interval is by nature not
> >> going to be a power-of-two, which means generally speaking it will
> >> not fit in one piece into a hardware register or buss. For NaI,
> >> the information that would otherwise be in the byte of a decorated
> >> interval is encoded into the payload of the NaI. In this way, the
> >> size (in bits) of NaI can remain power-of-two.
> >
> > Not so. Non-power-of-two busses happen all the time.
> >
> > Intel is perfectly happy with 80-bit busses to accommodate
> > their double extended datatypes. As they generally run
> > their memory systems aligned to 32-bit boundaries, they
> > handle the alignment problem by packing their 80-bit
> > double extendeds into 96-bit windows when stored in memory.
>
> 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.
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) & its costs (the compiler has to keep
track of things & the hardware assist needs an extra
address path).
But if our definition of decorated intervals is kept as
an abstraction, this sort of thing is an implementation
possibility.
>
> > 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.
>
> In other words, what is the reason to do this?
For the implementor, it is a tradeoff between the
extra effort to design & include special circuits for
interval support versus the interval market they
perceive they need to support to sell their machines.
So not only do we have to provide them with a standard
that is easy to implement in fast hardware, we have to
provide them with a market that wants it in the
computers they buy.
Not everything a standards committee does shows up in
the text of the standard. :-)
>
> 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.
>
> 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.
>
> >> So theoretically they may be similar concepts. In practice they have
> >> different implementation consequences.
> >
> > While I don't agree with your argument above, this is
> > still true.
> >
> > That is why one of the other principles I set forth in
> > the properties of decorated intervals is that the interval
> > portion of the result can only depend on the interval
> > portion of the operands. While the decoration portion of
> > the result may depend on BOTH the interval & decoration
> > portions of the operands.
> >
> > It is quite possible that implementors may choose to go
> > the route of handling the floating-point task only & leave
> > the decoration task up to software or some slower form of
> > instruction support.
> >
> > As a standard, we should permit this as a possibility.
>
> 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.
At least, it never did for me when I was designing chips. :-)
>
> . . .
>
> > We may be closer than you think...
>
> 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.
I look forward to it...
Dan