Re: Motion 52 -- Time to revive the "Expression" subgroup?

[Ian McIntosh <ianm@xxxxxxxxxx>]

> > (b) If it writes a*b + c*d as fma(a,b,c*d) or reduces x-x to 0, that's
> > *changing the _expression_* itself.
>
> No, that is not what is seen under the contraction of floating
> expressions in C. You just know that the evaluation of a*b + c*d
> can be done with more accuracy than the naive evaluation. It can
> correspond to something like fma(a,b,c*d), but the evaluation
> could also just be more accurate, without corresponding to any
> _expression_ transformation.

An fma is more precise than doing a separate multiply and add with rounding between them.

An fma in an _expression_ often makes the _expression_ more precise but can also make it less precise.  This is most obvious when doing a subtract of "equal" values, but the problem can occur with an add of other values.

In the case of evaluating the floating point _expression_ a*b - a*b you might expect the result to be zero.
If it's evaluated using fma(a, b, -(a*b)), the result will often be nonzero!
The reason is that the third parameter -(a*b) is evaluated then rounded, while the product of the first two parameters a and b is evaluated then not rounded before the add.  The evaluation using an fma is fma(a, b, -round(a*b)).
When one of the two products in the _expression_ is rounded and the other isn't, they may have different values, and their difference may be nonzero even though the mathematical value is zero and the non-fma evaluation (a*b) - (a*b) with two separate multiples and a subtract will correctly give zero (excluding cases involving infinities and NaNs).

- Ian McIntosh          IBM Canada Lab         Compiler Back End Support and Development


Vincent Lefevre ---2013-11-19 07:36:25 PM---On 2013-11-16 17:18:13 +0000, John Pryce wrote: > Vincent, P1788

From:	Vincent Lefevre <vincent@xxxxxxxxxx>
To:	Ian McIntosh/Toronto/IBM@IBMCA,
Date:	2013-11-19 07:36 PM
Subject:	Re: Motion 52 -- Time to revive the "_expression_" subgroup?

---

On 2013-11-16 17:18:13 +0000, John Pryce wrote:
> Vincent, P1788
> 
> You raise important practical issues here, but what I say is still 
> correct: I haven't said it clearly enough, so I hope you can help me 
> do so.
> 
> On 2013 Nov 15, at 10:13, Vincent Lefevre wrote:
> > On 2013-11-03 15:57:06 -0500, Michel Hack wrote:
> >> At the end of Clause 6.1 (c) one of the effects of repeated
> >> subexpressions is mentioned:
> >> 
> >>   "If the algebraic _expression_ is evaluated naively, such a
> >>   subexpression is evaluated more than once, which affects
> >>   efficiency but not the numerics of what is computed."
> >> 
> >> Assuming no side-effects, this may be the only worry for *point*
> >> evaluation.
> > 
> > This is not clear. By "not the numerics of what is computed", does
> > this mean the exact result (i.e. assuming infinite precision)? But
> > this would be misleading after "evaluated".
> > 
> > If this means the computed result on a machine,
> which is what I mean,
> 
> > ... this is obviously incorrect in practice...due to extended precision
> According to how I see it, this doesn't contradict what I said. What I'm
> assuming is that *exactly the same library operations* are used in each
> place where "the same" evaluation is being done. The operation starts 
> when its inputs are accessed from memory (possibly a register) and ends 
> when its result is stored in the form it will be used as a final output, 
> or as input to other operation(s). If the operation is performed, and/or 
> the result stored, in extended precision in one place and not in another, 
> those are two different (versions of) a given library operation.

This can be a way to see this, but it also means that the user may
be unaware which version will be used. For instance, after

  y = f(x);
  z = f(x);

whether you have y == z or y != z may be unspecified by the language.
Such things occur in C. See

  http://www.vinc17.net/research/slides/sieste2010.pdf

slides 11 to 17, and

  http://gcc.gnu.org/bugzilla/show_bug.cgi?id=46080

(invalid bug: the different results are allowed by the C standard).

> > (some reported problems are actually not
> > bugs: if IEEE 754 is not supported, then the C language does not
> > guarantee that 1/3. - 1/3. gives 0). There may be similar problems
> > with languages that allow a FMA to be used for x*y+z.
> 
> Two ways to change an _expression_-evaluation are being considered here. 
> (a) If the system switches from normal to extended precision, that's 
> *changing the versions* of library operations used. 

but C, for instance, can do that silently, possibly in a non
reproducible way. By using the word "version", I think this
should imply that the user knows which version is used.

> (b) If it writes a*b + c*d as fma(a,b,c*d) or reduces x-x to 0, that's 
> *changing the _expression_* itself. 

No, that is not what is seen under the contraction of floating
expressions in C. You just know that the evaluation of a*b + c*d
can be done with more accuracy than the naive evaluation. It can
correspond to something like fma(a,b,c*d), but the evaluation
could also just be more accurate, without corresponding to any
_expression_ transformation.

> (Actually, the fma example might be interpreted as a case of (a).)

You could assume that f(a,b,c,d) = a*b + c*d has different versions
like in (a), with the same issues as mentioned above: how the
evaluation is done may be unspecified.

> The text only says the result is invariant *if* one evaluates in a particular 
> way; it doesn't say that implementations *shall* do that. So all we need, I 
> think, is to make my text clearer, in the briefest possible way, referring 
> to the Annex that I hope Michel is writing for a fuller discussion, which
> will no doubt include problems of reproducibility. 
> Can you help me with that?

Sorry, I've been busy, with in particular a meeting these past two
days, and also tomorrow (Wednesday). I hope I'll have more time after
the meeting. I'll look at the revised version tomorrow. Now I need
some sleep...

-- 
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)