Motion P1788/M0045.01:ExactDotProductRevision -- discussion period begins
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.
=====
---------------------------------------------------------------
--
---------------------------------------------------------------
R. Baker Kearfott, rbk@xxxxxxxxxxxxx (337) 482-5346 (fax)
(337) 482-5270 (work) (337) 993-1827 (home)
URL: http://interval.louisiana.edu/kearfott.html
Department of Mathematics, University of Louisiana at Lafayette
(Room 217 Maxim D. Doucet Hall, 1403 Johnston Street)
Box 4-1010, Lafayette, LA 70504-1010, USA
---------------------------------------------------------------