The affinity test on integer values in a upc_forall statement is undefined for negative values

GoogleCodeExporter commented 9 years ago

A discussed in 
http://code.google.com/p/upc-specification/issues/detail?id=43#c7 ...

We saw this definitional aspect of '%' crop up on a test failure in the a GUTS 
'main' test: iteration4.

Until we fixed the compiler, the test was failing on this test, when compiled 
in a static THREADS compilation environment.

#define N 10
upc_forall (i=-N; i<N; i++; i) {
  if (i >= 0)
    check(i % THREADS == MYTHREAD);
  else
    check(((i % THREADS)+THREADS)%THREADS == MYTHREAD);
}

You'll note that the index, 'i' ranges from -N .. (N-1).  You'll also note that 
the test doesn't make any shared references at all, so the question of 
array/pointer bounds doesn't come into play.

The bug turned out to be due to the fact that the compiler used an unsigned 
type when performing the '%' operation, and further, this unsigned '%' was 
optimized to be performed as a multiply by the reciprical and that gave 
incorrect values when i is negative. 

This reference discusses the defined behavior of %.
http://bytes.com/topic/c/answers/444522-modulus-negative-operands [^]
The gist is that in C89 this was implementation-defined. In C99 they defined 
'/' as always rounding towards 0, which is conventional and compatible with 
Fortran.

If 'affinity' is determined in terms of '%', but '%' returns a negative number, 
how can upc_forall() determine affinity?

The test masks over this issue by doing something different for negative values 
of 'i'.

  if (i >= 0)
    check(i % THREADS == MYTHREAD);
  else
    check(((i % THREADS)+THREADS)%THREADS == MYTHREAD);

In any event, we "fixed" this test failure by insuring that the division was 
done using signed arithmetic.

Proposal
--------

Based upon the above example and discussion, we propose that a semantics clause 
is added that says that if an integer valued expression is used as the affinity 
expression that it effect is undefined for values less than zero.

Alternatively, the specification could be changed to add a constraint that the 
integer expression value shall be greater than or equal to zero, which would 
make the use of negative values an error.  Such a constraint is not backwards 
compatible with version 1.2 of the specification, however.

Original issue reported on code.google.com by gary.funck on 2 Jul 2012 at 5:57

GoogleCodeExporter commented 9 years ago

Correct the subject line to add the word "negative".

Original comment by gary.funck on 2 Jul 2012 at 6:06

Changed title: The affinity test on integral values in a upc_forall statement are undefined for negative values

GoogleCodeExporter commented 9 years ago

Original comment by gary.funck on 2 Jul 2012 at 6:07

Changed title: The affinity test on integer values in a upc_forall statement is undefined for negative values

GoogleCodeExporter commented 9 years ago

Some relavent text from 6.6.2 in the current spec

Constraints:
4 The expression for aﬃnity shall have pointer-to-shared type or integer type.

Semantics:
8 When aﬃnity is an integer expression, the loop body of the upc forall
statement is executed for each iteration in which the value of MYTHREAD equals
the value aﬃnity mod THREADS.

Note that Constraint clause #4 says "integer" which is unambiguously a signed 
type.  So, as Gary says this proposed change would be an incompatible one 
(though with admittedly small real-world impact in my estimation).

Note the use of the "mod" (not "%") in Semantic clause #8.
Since "mod" was given a specific definition in 6.4.2 with respect to the 
specification of shared pointer arithmetic, one is left to wonder if the same 
definition was intended here.  I suspect that it was.  If so, then there is a 
clear definition of the behavior for negative affinity expression.

So...

COUNTER proposal:

Append to Semantic clause #8 of Section 6.6.2:
   "where the \texttt{mod} operator is defined as in Section 6.4.2"

Original comment by phhargr...@lbl.gov on 2 Jul 2012 at 6:53

GoogleCodeExporter commented 9 years ago

Paul's suggested resolution is semantically cleaner, but I'm worried about the 
potential impact on current and future loop optimizations if we require 
well-defined semantics for this dirty special case. Specifically, we don't want 
to burden a loop optimizer with PROVING the affinity expression returns a 
non-zero result before it can apply the straightforward arithmetic instructions 
for the expected common case. 

This scenario is notably somewhat different from pointer arithmetic, where 
dealing with negative values is commonplace and should have well-defined 
behavior. It seems like a very strange programming practice to use an affinity 
expression that evaluates to a negative value, but a programmer who 
deliberately does this probably has a very specific behavior in mind they want. 
So rather than trying to second-guess what that might be, Gary's proposal 
forces them to resolve the ambiguity themselves (ie make the programmer apply 
the mathematical expression that maps it to a positive number so that % always 
results in a valid thread id). It also has the benefit of not rendering 
existing loop optimizer implementations non-compliant in ways that might be 
devilishly tricky to fix (for a very minimal payoff). The downside is this may 
break some small number of existing codes that intentionally use a negative 
affinity expression (does anyone have reason to believe this is a common 
practice?), but the "fix" that would be required is small and localized (and 
easily detectable if the compiler has a debugging feature to report this).

So I think I agree with Gary - make behavior undefined if the affinity 
expression returns a negative value.

Original comment by danbonachea on 17 Aug 2012 at 8:35

GoogleCodeExporter commented 9 years ago

Set default Consensus to "Low".

Original comment by gary.funck on 19 Aug 2012 at 11:26

Added labels: Consensus-Low

GoogleCodeExporter commented 9 years ago

This issue seems easy to fix.. if we can agree on which semantic we want.

Bump it back to new for more discussion.

I'd especially like to hear opinions from implementers of loop optimizations.

Original comment by danbonachea on 26 Sep 2012 at 6:53

Changed state: New

GoogleCodeExporter commented 9 years ago

Based on the discussion on the 9/26/2012 telecon, we seem to have consensus 
that affinity expressions that evaluate to a negative value should have 
undefined behavior. 

This resolution allows implementations to issue a helpful error message for 
this case (which probably represents a programming mistake). In the rare cases 
where such practice was intentional, it places the burden on the programmer to 
explicitly map the negative value to a positive value using their preferred 
algorithm, which seems like a Good Thing.

Original comment by danbonachea on 26 Sep 2012 at 10:35

Changed state: Accepted
Added labels: Consensus-High
Removed labels: Consensus-Low

GoogleCodeExporter commented 9 years ago

Would it be useful to constrain "non-negative" (not just positive) integer to 
be within the range 0..(THREADS-1)?

Original comment by gary.funck on 26 Sep 2012 at 10:43

GoogleCodeExporter commented 9 years ago

Official change proposal mailed to the lists 9/26/2012:
Proposed Change:
-------------------------
--- upc-language.tex    (revision 143)
+++ upc-language.tex    (working copy)
@@ -964,6 +974,7 @@
 \np When {\em affinity} is an integer expression, the loop body of
     the {\tt upc\_forall} statement is executed for each iteration in which
     the value of {\tt MYTHREAD} equals the value {\em affinity }{\tt mod THREADS}.
+    \xadded[id=DB]{59}{If the value of {\em affinity} is negative, behavior is 
undefined.}

 \np When {\em affinity} is {\tt continue} or not specified, each loop
     body of the {\tt upc\_forall} statement is performed by every thread and

Original comment by danbonachea on 26 Sep 2012 at 10:46

Changed state: PendingApproval

GoogleCodeExporter commented 9 years ago

> Would it be useful to constrain "non-negative" (not just positive) integer to 
be within the range 0..(THREADS-1)?

I think that would be a significant departure from the "spirit" of an integer 
affinity expression, which definitely is supposed to include a mod operation 
for positive values exceeding THREADS. Removing that seems far more likely to 
break existing codes.

The point of this issue was to resolve the ambiguity of mod on negative values 
(which we've decided to resolve by passing the responsibility on to the user), 
not to remove the mod entirely.

Original comment by danbonachea on 26 Sep 2012 at 10:50

GoogleCodeExporter commented 9 years ago

Gary asked:
> Would it be useful to constrain "non-negative" (not just positive) integer to 
be within the range 0..(THREADS-1)?

That restriction is out of the question in my opinion, as it breaks the 
"classic" example:
  upc_forall (i=0; i<SIZE; ++i; i) { a[i] = whatever; }

Even if it didn't break a huge fraction of existing codes, I expect an 
optimizer to be able to recognize that idiom easily, where an explicit "i % 
THREADS" in the affinity expression would be "harder" for a compiler to match 
to the "a[i]" in the loop body.

Original comment by phhargr...@lbl.gov on 26 Sep 2012 at 10:52

GoogleCodeExporter commented 9 years ago

these issues have all reached the end of their 4-week comment period 
and were accepted into the working draft at the 10/31 telecon.
Committed SVN r181

Original comment by danbonachea on 31 Oct 2012 at 8:49

Changed state: Ratified

Intrepid / upc-specification

The affinity test on integer values in a upc_forall statement is undefined for negative values #59