4.5.10 (34/5) Erroneous execution, if distributive law (or more general condition) is not satisfied

[blieberger]

4.5.10 (34/5) states that it is a bounded error if a parallel reduction expression is not associative. This is correct. But similar problems occur if a distributive law is not obeyed, e.g. for fixed point types with Text_IO; procedure T is type D is delta 0.01 digits 3; A : D := 0.04; B : D := 1.10; begin Text_IO.Put_Line (D'Image(AB+AB+AB)); -- 0.12 Text_IO.Put_Line (D'Image((A+A+A)B)); -- 0.13 end T;

Suppose one defines a reducer subprogram for a fixed point type like S := S + X*1.1; This is associative, so 4.5.10 (34/5) does not apply.

The underlying problem is not easy to describe here. Simply stating that the reducer subprogram has to obey the distributive law is wrong, since this law talks about two operations. I think the real problem is that the reducer subprogram delivers different results depending on different chunk specifications. Maybe we should write that it is an erroneous execution if a parallel reduction expression delivers different results depending on different chunk specifications.

On the other hand, I can think of more complex types (such as balanced tree structures) where a parallel modification may result in different objects depending on some chunk specifications. But each of these results may be correct after the modification (e.g. still being balanced). So the implementation may be correct although it produces different results on different chunk specifications.

Johann

[sttaft]

I don't see any reason to impose limits here. So long as the range of possible results is well defined, then I see no reason to require the user to specify operations that are somehow guaranteed to produce the same result independent of chunking or order of evaluation. Even with the full power of a formal proof system, it is not trivial to verify such a requirement, so I can't imagine a compiler that could take advantage of a complex erroneousness rule to know when it is OK to perform some fancy optimization.

[sttaft]

Steve Baird writes: There may be an issue here (and I agree about bounded error vs. erroneous), but the example provided already violates the rule about associativity and so it doesn't demonstrate any such problem.

I'm talking about a reducer of Accumulator := Accumulator + (1.1 * Next_Value); where these values are of the decimal fixed type given in the example.

If X = 0.0, Y = 0.0, and z = 0.27 then the assertion in the following code fails because A1 = 0.29 and A2 = 0.31.

    A1, A2, Temp : D := 0.0;
 begin
    Red (A1, X);
    Red (A1, Y);
    Red (A1, Z);
    Red (A2, X);
    Red (Temp, Y);
    Red (Temp, Z);
    Red (A2, Temp);
    pragma Assert (A1 = A2);

So this example already violates the associativity rule and therefore does not demonstrate a need for some new RM rule.

[sttaft]

NOTE: I copied Steve's comment, and then added the "Red(A2, X)" line to it, as otherwise X was not contributing to Accumulator A2.

[blieberger]

I think the problem occurs for Red (A1, X); Red (A1, Y); Red (A1, Z); Red (A2, X+Y); Red (A2, Z);

[sttaft]

In any case, I don't think we should try to specify any sort of complex rule here. -Tuck

[blieberger]

So I conclude that parallel loops (and sequential loops) may deliver different results depending on the chunk specifications. (Programmers should know this fact; perhaps something to note in John's textbook.) Thus, "for a parallel reduction expression, it is a bounded error if the reducer subprogram is not associative" is too restrictive. A compiler may raise Program_Error, where the programmer does not expect it. Thus, IMHO paragraph 4.5.10 should be deleted.

[ARG-Editor]

If "Red" as described here is not associative (and Steve claims it is), then the bounded error is triggered and different results are to be expected (or a Program_Error), regardless of what order Red is used in. So I don't see the point of this second example. The question was whether there was an example where the associativity rule is actually passes for the reducer function and the individual expressions are well-defined (note: most real expressions fail this qualification - if one of a set of results can occur, then OF COURSE any complex operation involving those results can have different output values) and yet the results of a reduction vary. In the absence of such an example, there is no problem here to discuss.

We often use Bounded_Errors in Ada to tell to users about things to avoid -- that's what this rule is for. Outside of trivial cases, it's not expected to be detected (and any case that was detected should have a strong warning in any sane implementation).

Some of us were very against any feature where it is too easy to get garbage results by making a simple change (like slapping "parallel" on it, in this case). This Bounded Error was a compromise so that at least the RM has a warning about potential problems. Removing it would destroy that compromise and potentially cause opposition to Ada 202x. It's way too late to be changing those sorts of decisions.

Therefore, nothing should be done with this issue, and I've marked it No Action.

[ARG-Editor]

To add a bit more: this rule is not about rounding or model arithmetic. Of course combining floats in different orders will give different answers; that's a consequence of the interval model of float math. This rule is about warning programmers not to slap "parallel" on just any reduction. For instance, the hash function in Janus/Ada uses a reducer something like: function Add_Char (Accum : in Hash_Value; Char : in Character) return Hash_Value is (Accum*2 + Character'Pos(Char) - 32); This would work nicely in a sequential reducer, but I believe would cause a garbage result if used in some other order (as in a parallel reduction). This rule is about pointing that out to readers of the RM, and making a strong suggestion to avoid such parallel reducers.