Re: Motion P1788/M0008.01_Exception_Handling: Discussion Period Begins.
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.
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.
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