Re: Branch & bound for not everywhere defiend constraints
Dan Zuras Intervals wrote:
>> 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.
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.
>
>>
>> . . .
>>
>>>> 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.
No. This absolutely rules out the entire NaI concept.
>
> 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!
I think you miss the most important facts about NaI:
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.
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!
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.
> & its costs (the compiler has to keep
> track of things & the hardware assist needs an extra
> address path).
Which is unnecessary...
>
> But if our definition of decorated intervals is kept as
> an abstraction, this sort of thing is an implementation
> possibility.
I'm still trying to understand: what is the motivation for this?
I don't see that there is any.
>
>>
>>> 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.
>
>>
>> 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. :-)
Yes. We are working hard on this other aspect of things at Sunfish Studio.
>
>>
>> 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.
>
>>
>> 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.
>
>>
>>>> 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.
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.
Plus, vendors are not the only ones that need convincing. You will also need
to explain to users why they can't just allocate a large array of
tightly-packed intervals that fall on nice word boundaries without a)
wasting space due to memory padding; b) choping the interval datatype into
two separate pieces and then dealing with the overhead of managing such a
data structure; or c) waiting for some compiler vendor to figure-out all
these details 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.
That's about what I would expect and/or hope for.
Nate Hayes