Re: Motion P1788/M0008.01_Exception_Handling
<Arnold, apologies for second copy, I see I sent this only to you
instead of the list.>
Arnold, Nate, P1788 members
On 19 Sep 2009, at 00:10, Arnold Neumaier wrote:
John Pryce wrote:
BUT your 3.2 seems to contradict either this or Motion 3...
It seems you haven't read our response to Dan Zuras's comments on
3.2 since you raise the same point again. This was answered there.
You are right, sorry. OK, I begin to like this scheme. There is no
specific NaI, but any interval with "inv" set, counts as a NaI. So
operations on the interval part can run at full speed without
checking for special cases.
A2.
There is something strange about M8/2.4 ...
Section 2 consists of specifications, not definitions, hence
circularity is irrelevant. (A specification just lists requirements.)
It has no effect for xx*yy but is nontrivial for xx*Y or xx*d
OK, it needs a slight rewording.
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.
No. Continuity must also be checked, and Boundedness.
Thus you need 3 flags.
Yes. I have been conflating Vienna's
"definedButPossiblyDiscontinuous" and "possiblyUndefined" into one,
since in the applications I know of, one doesn't need them
separately. However I think it is good to have them separate.
"Bounded" is different, however. It applies to the input xx, not to
operations done on the input, and as such may be checked on entry to
function ff. And in the cases I know, a check is not needed because
the nature of the surrounding algorithm guarantees xx is bounded. I
am not convinced it's needed as a separate decoration.
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.
Once you want to do parallel computation, the picture changes
completely.
This isn't about parallel computation: for that, see below.
Moreover, the part of the computation that needs to be done with a
decoration is in most applications only a fraction of the total
computation time; most of the computations can be done without
decorations.
In particular, this holds here. The test for accepting as step in
the ODE method only need a function evaluation; the subsequent
improvement step needs no decorations but must propagate a high
order Taylor expansion, or something related, and therefore
dominates the computation.
I accept all you say here, but it doesn't affect the fact that this
is poor design.
C. the "huge SIMD calculation".
It seems, from what our experts have said, that some modern compilers
can efficiently handle the problems I posed; and that some hardware
in the past, and some hardware currently available or in development,
has support for "vectorised flags".
At the risk of being like the fairy-tale Fisherman and his Wife (who
asked the magic fish for more and more till in fury he hurled them
back to the hovel from which they started):
Really, I would like to handle the scenario where "global flag" and
"huge SIMD calculation" are combined. Namely, I 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.
But I now have P = a million xx vectors at once, and I wish to
evaluate the P output vectors yy in SIMD mode, assuming that the code
for ff can indeed be vectorised in that way (which is language- and
compiler-dependent). And I want the FLAG reported individually for
each component. A picture (using indexing from 1, not 0)
1 2 ... P
xx(1) x x x ... x x x }
... ... ... ... } inputs, an n by P array
xx(n) x x x ... x x x }
v1 x x x ... x x x }
v2 x x x ... x x x } intermediate variables in ff,
... } each is a P-vector
yy(1) x x x ... x x x }
... ... ... ... } outputs, an n by P array
yy(n) x x x ... x x x }
FLAG x x x ... x x x } a P-vector
Column p (for parallel) of this picture represents calculating (in
Matlab notation)
yy(:,p) = ff(xx(:,p)), for p=1:P.
This is done a row at a time, e.g.
v1 = xx(1,:) .* xx(3,:);
v2 = sin(v1);
...
This needs a vectorised library of interval arithmetic operations
(and elementary functions) like the level-1 functions in BIAS. These
operations set FLAG componentwise where appropriate.
I continue to believe that for some applications, this gives a
cleaner conceptual scheme than does leaving FLAG information in the
decorations of individual output components yy(i,p).
In discussion at PPAM we seem to have agreed this FLAG scheme is
efficiently implementable, with a "regional" FLAG vector.
(Contributions from Juergen W v Gudenberg, Vladik Kreinovich).
Snag: I don't at present see how, using standard Fortran or C++
constructs, one can automatically ensure FLAG is defined, and is a
vector of the same length as the numeric vectors -- if not, one risks
indexing outside array bounds. However Juergen is thinking about a
possible new C++ construct he calls "flagspace", syntactically
similar to "namespace". Juergen, could it solve this problem?
On 19 Sep 2009, at 02:02, Nate Hayes wrote:
John Pryce wrote:
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 accept this point to some extent. If my idea can't be cleanly
described as part of Level 2 (as it seems decorations can be), it
should be discarded.
Regards
John Pryce