Re: Motion P1788/M0008.01_Exception_Handling: Discussion Period Begins.
Hi John,
I don't repeat Arnold's comments, but just add a few additional observations
below.
Nate
----- Original Message -----
From: "John Pryce" <j.d.pryce@xxxxxxxxxxxx>
To: "stds-1788" <STDS-1788@xxxxxxxxxxxxxxxxx>
Sent: Friday, September 18, 2009 5:43 PM
Subject: 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
In this example, X and Empty are bare intervals.
(see Arnold's 9/16 response to Dan's post).
> 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.
It is essential for vectorized computing!
>
> 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.
This is entirely true; but it is an implementation choice that may be valid
or practical only for certain types of computing environments or
implementations. In motion 8, we try hard to detach the abstract
specification of decorations from their concrete implementation. In the
parlance of Design Patterns, this idea might be closely identified with the
"Bridge" pattern, which decouples an abstraction from its implementation so
the two can vary independently.
>
> Therefore I would like the authors of this motion to consider adding
> suitable flag support to it.
This may be the Camel's nose in the tent, since the abstraction is then no
longer decoupled from the implementation.
I would encourage people to check that the abstraction can be implemented
correctly using global flags, if that is what an implementor wishes (and we
can make changes as necessary if this is not the case). But I would also
encourage people to focus on keeping the abstraction decoupled from the
implementation, since this will allow the greatest freedom to implmentors
(present and future).
These are the reasons the motion essentially recommends that concrete
representation formats for bare intervals, bare decorations and decorated
intervals should not be standardized (global flags are a concrete
representation format for decorations).
> ---------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.
This example doesn't consider some other scenarios that would potentially be
allowed by Motion 8:
1. Compute the vectorized operation on bare intervals with forgetful
operators that throw away decorations; or
2. Copmute the vectorized operation on bare intervals with forgetful
operators that throw away intervals (if an exception occurs).
We therefore have three options (which correspond directly to the B1, B2 and
B3 examples you gave in one of your recent posts). If the vectorized
operation is performed on bare intervals with forgetful operators, then a
bare binary64 interval is 2*8=16 bytes long, and there is no memory needed
at all for decorations!!
If forgetful operators throw away the decorations, the results will always
be bare intervals according to the exception-free semantics described in
Motion 5, for example. If forgetful operators throw away the intervals (when
an exception occurs), then possibly an implementation can encode the bare
decoration into the 16 byte memory location of each bare interval result.
This latter scenario is then functionally equivalent to the "many NaI" or
"NaI with payload".
Since the abstraction is decoupled from the implementation, all of these
choices should be possible to implementors and/or users to avoid the snags
listed above.
Sincerely,
Nate Hayes