Re: Motion P1788/M0008.01_Exception_Handling: Discussion Period Begins.
> From: John Pryce <j.d.pryce@xxxxxxxxxxxx>
> Subject: Re: Motion P1788/M0008.01_Exception_Handling: Discussion Period Begins.
> Date: Fri, 18 Sep 2009 23:43:42 +0100
> To: stds-1788 <STDS-1788@xxxxxxxxxxxxxxxxx>
John,
Since Vincent & I started us all down this path, I feel
the need to attempt a defense of this motion. At least,
as best as I can... :-)
>
> Nate, Arnold, P1788 members
>
> On 16 Sep 2009, at 18:44, R. Baker Kearfott wrote:
> > Since this motion has been tendered by Nate Hayes and seconded
> > by Vladik Kreinovich, the three-week discussion period will begin.
> > Nate Hayes wrote:
> >> I submit the document "Exception Handling for Interval Arithmetic"
> >> as a
> >> formal motion (motion 8) to be voted upon.
> >> The document presents a general framework for exception handling. It
> >> uniformly accomodates all arithmetic and nonarithmetic exceptions
> >> that are
> >> relevant for interval arithmetic and its applications. It
> >> eliminates the
> >> need for separate global sticky flags, and integrates non-
> >> intervals (NaI),
> >> without introducing any overhead for users who don't make use of
> >> exceptions.
> >> The document is attached as a PDF (4 pages) to facilitate its
> >> reading. Thank
> >> you to Arnold Neumaier for his joint contributions in writing it.
>
> I applaud this motion for starting to crystallise discussions of the
> last few weeks. However I have some serious questions, which overlap
> with some of Dan Zuras's.
>
> I shall use notation as follows.
> (variables)
> X, Y, ... mean decorated-intervals.
> xx, yy, ... mean bare-intervals (as in Vienna proposal).
> d, e, ... mean bare decorations.
> A decorated-interval X is regarded as a "struct" with fields as follows.
> xx = X.ivl is the interval part.
> d = X.dec is the decoration part, a list of trits.
> <xx, d> is notation for constructing a decorated-interval.
> I write
> (named constant)
> All0 for the bare decoration whose trits all equal 0.
>
> Thus for any X,
> (eqn1) X = <X.ivl, X.dec>
>
> That this is how decorated-intervals are formed, follows from 1.3 of
> the Motion 8 rationale (M8/1.3, for short).
>
> A.
> My first question is a theory one, about what depends on what.
>
> M8/2.2 unambiguously says that if X, Y are "standard decorated-
> intervals" (a term that hasn't been defined so I am just taking it to
> mean "decorated-intervals", and if "op" is a binary operation on bare-
> intervals, then the overloaded operation Z = X op Y is defined by
> (eqn2) Z = <Z.ivl, Z.dec> = < X.ivl op Y.ivl,
> op(X.ivl, Y.ivl, X.dec, Y.dec) >
>
> Here, I have written op in infix form on the top line, because it
> takes just 2 inputs. But on the lower line there are 4 inputs: the
> decoration part of Z is a function of both the interval and the
> decoration part of each of X and Y. Using overloading-notation I have
> called the function "op" in all 3 places.
>
> I have two beefs about this.
> A1.
> Your 2.2 is indeed how I understand the concept "decoration", namely:
> - Z's interval part is unaffected by the decoration parts of the
> inputs.
> - The decoration part is set at initial construction, and that of a
> subsequently computed decorated-interval, say W, is entirely
> determined by the history of operations leading to W.
>
> BUT your 3.2 seems to contradict either this or Motion 3. You say
> "[normally,] given ... interval X
> X \union Empty = X
> some applications may need
> X \union Empty = Empty."
> Here, the named constant Empty is a decorated-interval, so I shall
> call it dEmpty to distinguish it from the bare-interval constant
> Empty (which, by motion 3, must exist as a member of the set of bare-
> intervals).
>
> Also, I assume the two dEmpty's in (eqn3) and (eqn4) only differ in
> their decoration fields. (The motion 8 scheme seems pretty pointless
> if this is not so.) So I call them dEmpty1 and dEmpty2 where
> dEmpty1.ivl = dEmpty2.ivl
> and I re-write the above quote as
>
> "(eqn3) X \union dEmpty1 = X
> but some applications may need
> (eqn4) X \union dEmpty2 = dEmpty2."
>
> From (eqn2, eqn3) we have
> X.ivl \union dEmpty1.ivl = X.ivl, (for all X)
> a bare-interval statement that can only be true if
> dEmpty1.ivl = Empty. (Thank goodness!)
>
> But then, (eqn4, eqn2) give
> X.ivl \union dEmpty2.ivl = dEmpty2.ivl, (for all X),
> a contradiction since dEmpty2.ivl is the same as dEmpty1.ivl, which
> is Empty.
>
> I do not see how to remove this without assuming that in (eqn2),
> Z.ivl depends on X.dec and Y.dec as well as on X.ivl and Y.ivl. But
> then, the .dec parts aren't like decorations; more like "mode
> switches". This would change the whole nature of the scheme and make
> it, in my view, complicated and unattractive.
>
> I have made several assumptions in the above; maybe I have
> misunderstood, and with other assumptions the contradiction can be
> removed.
>
> A2.
> There is something strange about M8/2.4 that may be related to the
> previous point. Namely it seems to be saying
> (eqn5) xx op yy = ( <xx, All0> op <yy, All0> ).ivl for any bare-
> intervals xx, yy;
>
> and the wording has the appearance of thereby _defining_ xx op yy.
>
> But then the definitions are circular since 2.2 defines operations on
> decorated intervals in terms of those on bare ones, while 2.4 does
> the reverse.
>
> If however (eqn5) is a constraint, not a definition, that is fine.
> But it doesn't read that way.
> ---------end of A.
The apparent contradiction that is at the heart of your
point (A) is lies in just where the notion of 'empty'
lives under this scheme.
I believe a sufficiently liberal attitude towards empty
can cure this problem.
Let us presume there exists a bare interval for empty
which we will call bbempty. Let us further presume that
ANY bare interval decorated with an 'isEmpty' decoration
may be considered a proxy for empty. Also, that intervals
that are empty for other reasons (say undefined) will also
decorated with 'isEmpty'.
Therefore, to use your notation, all of the following will
return true to the predicate isEmpty:
<bbempty,isEmpty>
<bbempty,isEmpty+notDefined>
<xx,isEmpty> for all bare intervals xx
<xx,isEmpty+notDefined> for all xx
I will pass on the issue of what happens to things like
<bbempty,notEmpty> on the grounds that they seems ill-formed
to me.
So, with such a rich set of empty's available to us we can
have:
<xx,anything> \union <bbempty,isEmpty> = <xx,anything>
as well as:
<xx,anything> \union <bbempty,isEmpty+notDefined>
= <xx,anything+isEmpty+notDefined>
Where the 'isEmpty' decoration is a consequence of the
'notDefined' decoration.
The interval portions are still a function of the interval
portions & the decorations are a function of both.
I am a little unclear as to the consequences of letting
these result 'empty's participate in further operations
but let's tackle one problem at a time. OK? :-)
>
> B.
> My next point is more of a software engineering one. Consider the
> standard validated ODE solver application, where you have
> - a vector function f: D \subseteq R^n -> R^n
> - a box xx in R^n
> and you want to check that
> - f is defined and continuous on the whole of xx, and
> - f maps xx into itself,
> which proves that a fixed-point theorem can be applied.
>
> With a "FLAG" approach it works very simply:
> - Assume f has been coded up as a function, as this is the typical case.
> - Evaluate the interval version ff of f:
> yy = ff(xx) where xx, yy are interval vectors of length n
> - If Vienna proposal's "possiblyUndefined" flag wasn't raised, then
> all is OK.
>
> But with decorated intervals:
> - Evaluate the decorated-interval version F of f:
> Y = F(X) where X, Y are decorated-interval vectors of length n
> - Now you have to check each component Y[i] of Y.
> If each "possiblyUndefined" field in Y[i].dec is un-set, 0<=i<n,
> then all is OK.
> This is more messy. What is really one bit of information has been
> spread over the n components of a vector. In my view this indicates
> an inherently poor design.
>
> Prof Wolff von Gudenberg has told me that if a flag is not global,
> but as he calls it, "regional" -- a static class-variable in C++ or
> Java, or a module-variable in Fortran, is of this kind -- then
> accessing it does not incur large performance penalties. It seems
> practical to implement flags in this way.
>
> Therefore I would like the authors of this motion to consider adding
> suitable flag support to it.
> ---------end of B.
I think your criticism in point (B) is well taken IF the
generalization of a scalar decorated interval is the cross
product of decorated intervals.
But a decoration is not so much a property of an interval
on its own but the tombstone left behind of the operation
of that interval on a specific function. It records the
consequences of applying that interval to that function.
So, the complete decoration for sqr(<[-2,0],All0>) is
<[0,4],isValid+isStandard+notEmpty+notEntire+
isBounded+isDefined+isContinuous+isTight>
Whereas the complete decoration for sqrt(<[-16,16],All0>) is
<[0,4],possiblyValid+isStandard+notEmpty+notEntire+
isBounded+possiblyDefined+isContinuous+isTight>
Both are the same interval as far as being a subset of
contiguous closed sets on R are concerned. But each was
arrived at via different histories. And it is those
histories that the decorations record.
Given that rather pedantic explanation (please forgive me),
I claim that the decoration of the cross product of two
intervals cannot be the cross product of the decorations
of those intervals. Indeed, that makes no sense.
It is like asking if there is a pole in the Riemann zeta
function in Re(z) = [0,2]. The question is ill posed.
For z in [0,2]x[-1,1] the answer is yes. For z in
[0,2]x[1,2] the answer is no.
Therefore, the proper decoration for the cross product of
two intervals is:
<xx \cross yy, decoration>
not the cross product of the decorations.
IMHO, of course. I speak for myself not the authors.
>
> C. the "huge SIMD calculation".
> We have discussed this problem in this forum, but I would welcome a
> statement from P1788's compiler and hardware specialists.
>
> Statement of problem:
> - I have a (fairly simple) function, say like
> f(x0,x1) = log(cos(x0)+sin(x1/exp(x0))+sqr(x0/x1))
> in Nate Hayes' recent "paving" example.
> - I want to evaluate it "vectorised", component-wise on
> an interval vector of length 1,000,000, say,
> and record whether "possiblyUndefined" was raised,
> individually for each component.
>
> "Vectorised" means that each elementary operation in f is a vector
> operation -- e.g. in Matlab this could be achieved by writing
> f = @(x0,x1)( log( cos(x0) + sin(x1./exp(x0)) + sqr(x0./x1) ) );
> and calling f with vectors x0 and x1.
>
> In fact they are to be decorated-interval vectors of length
> 1,000,000, and we assume vector elementary functions have been
> written that set the "possiblyUndefined" trit component-wise.
>
> Possible snags:
>
> - A binary64 interval is 2*8=16 bytes long. When decorated it grows
> to 17 bytes with a 4 trit design (or 18 bytes with 8 trits).
>
> - To achieve fast access the compiler probably likes to align each
> element of the array on a 16-byte boundary, which implies padding it
> out from 17 to 32 bytes long. Lots of wasted storage!
>
> - Or is it clever enough to store the interval part in one array, and
> the the decoration part in a separate array? Dan Zuras has said this
> may well be so.
>
> - Possible scenario is that at low optimisation level the 16-byte
> aligning doesn't happen. But user increases optimisation level and
> suddenly compiler does this aligning. Thus each of several arrays
> nearly doubles its required memory from 17,000,000 bytes to
> 32,000,000 bytes; program runs out of physical memory and page
> thrashing ensues.
>
> Questions to experts:
> - Can modern compilers handle this sort of thing intelligently? If
> they do, IMO it is a strong argument in favour of the motion 8
> scheme. If they don't, then decorated intervals won't be good for
> large problems.
> - How would this work out on something like the CELL machine?
> ---------end of C.
>
> Best wishes
>
> John Pryce
This last point (C) is harder to answer. Any or all
of your possible snags may happen.
It is true that solving a problem with the assurances
that intervals will provide the user will involve some
non-trivial overhead over solving the problem using
ordinary floating-point.
But it is also true that the user is rewarded with some
non-trivially more informative results than with ordinary
floating-point.
The cost of getting those results will always mean that
some problems will take non-trivially more space and/or
time. And a consequence of this is that some problems
that are very difficult to do in floating-point will be
outside the limit of our resources at any given moment.
We can only try to minimize that overhead as much as is
consistent with assured results.
So the question becomes: Are results with decorated
intervals more certain (or more to be believed) than
results with bare intervals? Is an attempt to use vast
amounts of parallelism more constrained by decorated
intervals or by bare intervals encumbered by the
synchronization choke point of global state? Are compilers
smart enough to manage decorations efficiently or must we
live with the problems of unaligned data structures?
Can efficient hardware be some day designed to take
advantage of one approach more easily than the other?
You each have expertise enough to answer some of these
questions for yourself. And collectively we should have
enough expertise to answer them all for each other.
That's what this conversation is all about. :-)
Yours,
Dan