Re: A motion to revise the status of Exact Dot Product & Complete Arithmetic
> Subject: A motion to revise the status of Exact Dot Product & Complete Arithmetic
> From: John Pryce <prycejd1@xxxxxxxxxxxxx>
> Date: Wed, 5 Jun 2013 07:53:04 +0100
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
>
> P1788
>
> As a result of re-reading all the Motion 9 emails, I think we need a motion to reopen the status of Exact Dot Product EDP and associated Complete Arithmetic CA. I think Baker's summary at that time, copied at the end of this email, makes a good basis. This motion is about content, not the actual text, but I think, if this motion passes, the suggested Level 2 text will need little change. I hope that during the discussion period it will be possible to include, in this motion, the proposed revised text on EDP & CA at Level 3.
>
> ======
> Motion
> ======
> 1. The status of Exact Dot Product EDP and Complete Arithmetic CA be changed from required to recommended.
If you're going to 'reopen the status' of these functions, I wonder if
you mean whether or not the it is required that result be rounded
correctly or whether the functions are required. The former would be
bad & the latter acceptable. I therefore hope you mean whether or not
the functions are required. (It appears that is your intention in the
rest of this note. I just wanted to state it up front.)
>
> 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.
I'll repeat that the evaluation must be "as if in exact arithmetic" as
since 754-2008 hit the streets papers were published on how to do that
with finite precision & some inexactitude sufficiently low in the sum
as to not change the correctly rounded result.
>
> 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.]
I don't see the 2^88 terms in this with 2^63-1 counters. Could someone
post a quick explanation for me please? Thanks in advance.
>
> 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
Again, please point out that it is the existence of these functions
that may be considered optional, not their rounding. After all, we
cannot have a standard which gives different results among accepted
members, can we?
>
> (*) "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*.
Acceptable, IMHO.
>
> (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 â??0,
> - 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 â??0,
> - EXCEPT when all its terms are +0, in which case the result shall be +0.
> =====
>
> Baker's email cited above
> -------------------------
> On 18 Nov 2009, at 11:51, Ralph Baker Kearfott wrote:
> > My vote is NO
> >
> > A change that would make me vote YES:
> > I would vote "YES" if, instead of an exact dot product, we mandated
> > a dot product that is correctly rounded to the working precision.
> > In the case of point inputs, this would mean that round-down,
> > round-up, and round to nearest would be supported. For instance,
> > in round to nearest, it would mean the nearest floating point
> > number to the exact dot product.
> >
> > Note that this change would not preclude an implementer from supplying
> > an exact dot product, and that would be one way the requirement
> > could be achieved. However, a correctly rounded dot product
> > both ensures cross-platform reproducibility and avoids certain
> > efficiency or difficulty issues in implementation.
Let me clarify our thinking on sum & exact dot product in 754-2008.
Once we eliminated both NaN & infinite results we stated that:
"Otherwise, sums are computed in a manner that avoids overflow
or underflow in the calculation and the final result is
determined from that intermediate result. If that result
overflows, signal overflow. If the result underflows, signal
underflow."
This intermediate sum was considered to be calculated exactly at the
time. This was Ulrich's method & less expensive methods came later.
The behavior WRT +/-0 was implied by section 6.3.
We did NOT consider the behavior WRT summing over 2^88 terms &
overflow the intermediate result. But I imagine returning infinity or
NaN to be acceptable (assuming the operation ever terminates :-).
Hmm... There was something else I wanted to say but I forget it now.
As it is nearly 3 AM here that's not all that surprising I guess. :-)
Maybe one of you will state it for me...
Thanks,
Dan