Re: Motion P1788/M0045.01:ExactDotProductRevision -- discussion period begins
I second.
On 2013-06-05 14:36:45 -0500, Ralph Baker Kearfott wrote:
> P-1788:
>
> Since Motion 45 has been made by John Pryce and
> seconded by Vladik Kreinovich, the discussion period now
> begins, and will end after Wednesday, June 26, 2013.
> I append the motion and rationale.
>
> Discussion on this motion will proceed according to the rules for
> position papers (quorum and simple majority).
>
> Juergen: Please place the motion and associated information
> in the appropriate place on the web page, as
> you have aptly done in the past.
>
> Acting secretary: Please record the transaction in the minutes.
>
> As usual, please contact me if you need the password to the private
> area of the P-1788 web site.
>
> Best regards,
>
> Baker (acting as chair, P-1788)
>
> P.S. Note the discussion period extends through the time for
> our in-person P-1788 meeting in Edmonton.
> ---------------------------------------------------------------
>
> ======
> Motion
> ======
> 1. The status of Exact Dot Product EDP and Complete Arithmetic CA
> be changed from required to recommended.
>
> 2. The current text on EDP and CA (11.11.11 in the current
> draft) be moved to Level 3 with minor revisions and replaced at
> Level 2 by the following text:
>
> ---start of text---
> An implementation that provides 754-conforming interval types
> shall provide the four reduction operations sum, dot, sumSquare
> and sumAbs of IEEE 754-2008 §9.4, correctly rounded. These shall
> be provided for the parent formats of each such type.
>
> Correctly rounded means that the returned result is defined as follows.
> - If the exact result is defined as an extended-real number,
> return this after rounding to the relevant format according to
> the current rounding mode, except in the case of unavoidable
> overflow. An exact zero shall be returned as +0 in all rounding
> modes.
> - Otherwise return NaN.
>
> All other behavior, such as overflow, underflow, setting of IEEE
> 754 flags, raising of exceptions, and behavior on vectors whose
> length is given as non-integral, zero or negative, shall be as
> specified in IEEE 754-2008 §9.4. In particular evaluation is as
> if in exact arithmetic up to the final rounding, normally with no
> possibility of intermediate overflow or underflow.
>
> Unavoidable overflow results from adding an extremely large
> (implementation-dependent) number of large terms of the same
> sign. If it occurs, NaN shall be returned and an
> implementation-defined exception shall be raised. [Note. An
> implementation should be designed such that the relevant number
> of terms is unachievable with current hardware, making overflow
> impossible in practice. For example, CA for IEEE 754 binary64,
> parameterized as recommended by Kulisch and Snyder, requires 2^88
> terms before overflow can occur.]
>
> It is recommended that these operations be based on an
> implementation of Complete Arithmetic as specified in §X.Y.
> ---end of text---
>
> =========
> Rationale
> =========
> The reasons for the change of status of EDP+CA are that the
> majority expert view has urged this, during P1788 discussions.
>
> The reasons for moving it to Level 3 are to do with the
> structure of our standard, see below.
>
> The reason for basing the new text on 754 §9.4 is that it is
> sensible to build on text that is already in that standard.
> Further points:
>
> (1) I do not think Prof Kulisch has made the case that there are
> many problems that can only (or even best) be solved by EDP,
> rather than a dot product correctly rounded, or faithfully
> rounded, to the working precision (CRDP and FRDP respectively).
> In current discussion, he cites the same two applications he did
> in late 2009: Rump operator & logistic map. And Lefevre, Neumaier
> & Rump all say these can be solved nearly as well using FRDP.
>
> (2) The fact that IFIP WG's letter in support of an interval
> standard asks for EDP has some, but limited, weight. P1788 must
> make the final decision.
>
> (3) It is often arguable what counts as *functionality* and what
> counts as *a way to achieve functionality*. It depends on
> project aims. It seems to be P1788 consensus that normative text
> ("shall") be confined to Levels 1 & 2 as far as possible. This
> issue is about precision so Level 1 is irrelevant to it. So what
> is the relevant Level 2 functionality? In view of point (1), it
> seems to be
>
> (*) "Obtain the value of a dot product (or sum, etc.)
> with small relative error."
>
> This can be stated squarely as a Level 2 requirement.
>
> (4) Vincent Lefevre and others have stated a view that CA is out
> of place in P1788 as a whole. My view is that it looks very out
> of place at present, but that is because it has been put within
> Level 2. It fits, if seen as a Level 3 way to meet the above
> Level 2 requirement. So I suggest it be in Level 3 as (J-M Muller
> 20091118):
> > *highly recommended*, yet not *mandatory*.
>
> (5) We must do our best not to put off implementors, as warned
> by George Corliss (20091030),
> > I'd like to hear people from the implementation side say at least, "We are
> > willing to do an exact dot product" before I am willing to say, "You must do
> > an exact dot product."
> and also (J-M Muller, cited email):
> > My primary concern is that interval arithmetic should be both:
> > - implementable on very simple platforms
> > - able to perform computations at very high speed on sophisticated ones
>
> CA is not appropriate at *all* points along that spectrum. But
> if CA is as good as its supporters say, the market will find it a
> place somewhere in that spectrum. A strong recommendation in
> 1788 should help this happen.
>
> It seems to me it should be straightforward to implement CA
> (initially the binary64 version which IMO is always likely to be
> the most used one) as a commercially available co-processor chip
> -- similarly to how the first commercial version of 754
> arithmetic was the 8087 co-processor. I look forward to someone
> taking up the challenge to create a CA chip.
>
> Prof Martin Berz has written (20091106) that CA would be very
> useful to his Taylor Model calculations, which have been crucial
> to various large projects such as designing the beam guidance for
> the Large Hadron Collider. Martin, how about your group taking
> on the CA chip?
>
> (6) Why do I propose achieving (*) above by
> - Correctly Rounded CR reduction operations, instead of
> - Faithfully Rounded FR ones, or
> - some weaker requirement on relative error, maybe just
> leaving it as a Quality of Implementation issue?
>
> Because I think the balance of view among the experts is that
> algorithms for FR and CR are so well established that we should
> do *at least* FR. And CR is *on average* only slightly slower
> than FR in practice, and has the massive advantage of being
> uniquely defined and therefore reproducible.
> ================
> End of Rationale
> ================
>
> =====
> Note on "unavoidable overflow"
> ------------------------------
> The Kulisch-Snyder paper on CA says that for the capacity
> parameters they recommend for the binary64 version, it takes
> about 2^88 accumulations of (maxreal* maxreal) before overflow
> can occur, which a back-of-envelope estimate suggests would take
> current machines more time than the current age of the universe,
> to achieve. So it is impossible in practice. However fast
> machines become, this can always be achieved by adding a few more
> bits at the most significant end of the accumulator. This is
> true not just for CA but for the alternative algorithms on the
> market.
>
> =====
> Note on exact zero results
> --------------------------
> In the proposed text on reduction operations:
> (a) It says an exact zero value of a reduction operation shall
> be returned as +0 in all rounding modes. This is consistent with
> 754 §9.4 saying the result, when the vector-length is zero, shall
> be "+0 without exception". However §9.4 does not mention exact
> zero results in any other context. Nor does it mention rounding
> modes, which *suggests* that the exact result is to be rounded
> according to the current mode but obviously doesn't require it.
>
> (b) But it is not consistent with 754 §6.3, which has the rather
> baroque statement:
> - An exactly zero sum of two operands shall have the
> sign +0 in all rounding modes,
> - EXCEPT roundTowardNegative, in which case it shall be \u22120,
> - EXCEPT when doing (+0)+(+0), in which case it shall be +0.
>
> Now, roundTowardNegative is important to interval people, so
> should we take notice of this? Since a reduction "may associate
> in any order" (says §9.4) one may say that §6.3, which is about
> two operands, just doesn't apply. But I think there *are* some
> relevant questions:
>
> - For sumSquare and sumAbs, this issue can only apply to an
> all-zero vector, and one is then definitely adding terms that are
> all +0, so the baroque rule of §6.3 is consistent with returning
> +0 even with mode roundTowardNegative.
>
> - For sum and dot, suppose the exact sum is zero and the mode is
> roundTowardNegative.
> If the terms being added are not all zero, or if they are all
> zero and at least one of them is -0, then §6.3 implies that
> adding term-by-term (as a sequence of binary additions) *in any
> order* is bound to give -0.
> While if the terms are all +0, §6.3 implies adding in any order
> is bound to give +0.
>
> Should the text follow §6.3? If so, the rule would be
> For a vector of positive length:
> - An exactly zero result of sumSquare or sumAbs shall have the
> sign +0 in all rounding modes.
> - An exactly zero result of sum or dot shall have the sign +0 in
> all rounding modes,
> - EXCEPT roundTowardNegative, in which case the result shall be
> \u22120,
> - EXCEPT when all its terms are +0, in which case the result
> shall be +0.
> =====
>
>
> ---------------------------------------------------------------
--
Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)