Re: Branch & bound for not everywhere defiend constraints
Dan Zuras Intervals wrote:
>> Date: Mon, 7 Sep 2009 14:50:05 -0400
>> From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
>> Subject: Re: Branch & bound for not everywhere defiend constraints
>> To: STDS-1788@xxxxxxxxxxxxxxxxx
>>
>> Dan Zuras Intervals wrote:
>>>> . . .
>>>
>>> Isn't another name for "TotallyUndefined", "Empty"?
>>> You define it to be true in exactly the same place
>>> as empty is true & you use it as others use empty.
>>>
>>> Are we just a name away from agreement?
>>
>> Almost.
>>
>> 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.
>
>>
>>
>>
>>>
>>> Finally, while I'm not happy with the concept of global
>>> flags for any purpose, I agree that 'syntactic sugar' AKA
>>> 'decorations' attached to intervals may be of value.
>>
>> 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.
>
> 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."
In other words, what is the reason to do this?
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.
Maybe someone should ask Intel or AMD so we don't have to guess.
>
>>
>> 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.
>
>>
>> THis is why I believe both should be examined and considered.
>
> Agreed. But, as it happens, for different reasons. :-)
It is more important right now we agree they should both be examined.
>
>>
>>>
>>> As for the naming of things, it could be that sufficiently
>>> many 'flavors' of 'syntactic sugar' could take the place
>>> of either or both of NaIs or empty for what we need them
>>> to do.
>>>
>>> We are having that discussion now. Let's see how it turns
>>> out.
>>
>> Yes.
>>
>>>
>>> Thanks for your explanations,
>>
>> You're welcome!
>>
>> Nate Hayes
>
> 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