Subject: hpff-task: HPF reduce directive

From: [email-masked] (Chuck Koelbel)
Date: Tue, 2 Jan 1996 11:25:57 -0600

---------------------------------------------------------------------------
[email-masked] is a mailing list for discussion of control-parallel
features in HPF.  Instructions for adding or deleting yourself from this
list appear at the bottom of this message.
---------------------------------------------------------------------------

Fabien -
Actually, the mailing list that is discussing REDUCE is hpff-task.

hpff-task -
Forwarded from hpff-distribute.  Apologies to those of you who see this
twice.  I'll comment that I generally like the "external" syntax, modulo a
couple syntax nits (for example, INDEPEDENT does not name the loop index,
and doesn't apply to nested loops.)
        Chuck

Hi Rob,

I'm not sure you're in charge of the reduce directive, but anyway, I guess
someone on the "hpff-distribute" list is:

I just had a look the "reduce" directive proposal. I was wondering how
the compiler should guess at which level in a loop nest the reduction
must be performed.

My point is that the way the "reduce" directive is placed in the loop nest
does not give this information to the compiler, thus some analysis will be
needed. This analysis could be avoided with some other syntax in the "new"
and "independent" spirit.

EXAMPLE:
--------

Here is an example to illustrate this point.  (This example is not
designed to be meaningful from the computation point of view, but to
provide a set of problems in the same loop nest.) The reduction on s1 must
be performed at the j level, the ones on s2 and s3 at the i level. The s3
reduction has two contributions from B and A. The reduction on s1 is
initialized with B. It is used for the p reduction.

      real A(n,n), B(n)
! there may be some external loop around this piece of code
      ...
      p = 1.
      s2 = 0.
      s3 = 0.
      do i=1, n
         B(i) = 2.*real(i-j)
         s1 = B(i)
         s3 = s3 + n*B(i)
         do j=1, n
            A(j,i) = 1./real(i+j)
            s1 = s1 + A(j,i)
            s2 = s2 + A(j,i)
            s3 = s3 + A(j,i)
         enddo
         p = p * s1
      enddo
      ...
! p, s2 and s3 might be used...

CURRENT "INTERNAL" REDUCE SYNTAX:
---------------------------------

With the current syntax, it's quite verbose and the compiler must decide
at with level the reduction must be performed. Another issue is whether
or not several contributions are allowed:

      p = 1.
      s2 = 0.
      s3 = 0.
chpf$ independent(i), new(s1, j)
      do i=1, n
         B(i) = 2.*real(i-j)
         s1 = B(i)                 ! initialization of s1
chpf$ reduce                       ! first contribution to s3...
         s3 = s3 + n*B(i)
chpf$ independent(j)
         do j=1, n
            A(j,i) = 1./real(i+j)
chpf$ reduce                       ! must guess that it is at the j level
                                   ! what are the needed analysis for this?
                                   ! should it trust the "new" outside?
                                   ! "see" that s1 is "simply" (as opposed
                                   ! to s3) assigned and used in the i loop?
                                   ! note that both s1 and s3 are read and
                                   ! written within the i loop.
            s1 = s1 + A(j,i)
chpf$ reduce                       ! i level (2 loops outward)
            s2 = s2 + A(j,i)
chpf$ reduce                       ! i level, second contribution to s3...
            s3 = s3 + A(j,i)
         enddo
chpf$ reduce                       ! i level
         p = p * s1
      enddo

"EXTERNAL" REDUCE SYNTAX:
-------------------------

I would rather suggest the less verbose (and nothing/few to guess):

      p = 1.
      s2 = 0.
      s3 = 0.
chpf$ independent(i), new(j,s1), reduce(s2,s3,p)
      do i=1, n
         B(i) = 2.*real(i-j)
         s1 = B(i)
         s3 = s3 + n*B(i)
chpf$ independent(j), reduce(s1[,s2,s3]) ! [] optional?
         do j=1, n
            A(j,i) = 1./real(i+j)
            s1 = s1 + A(j,i)
            s2 = s2 + A(j,i)
            s3 = s3 + A(j,i)
         enddo
         p = p * s1
      enddo

Apart from the reduced (!) verbosity, the very fact that the reduce
directive is attached to a loop gives the compiler a hint about the level
at which the reduction (=> [partial] synchronization) is to be performed.

For checking purposes every scalar assigned in an independent loop should
appear in some "new" or "reduce" directive...  Also the multi-contribution
to a reduction does not require multiple annotations from the user (rising
the question of the semantics of the operation if some are forgotten...)

The compiler has to guess what are the reduction statement(s) for each
scalar, that is it has to find all the assignments to that scalar within
the loop nest.

The spirit of such an "external" reduce directive is quite different from
the "internal" one. It asserts at a higher level in the code a general
property about a loop nest and a scalar manipulated in this loop nest.
This is homogeneous with the existing "independent" and "new" directives,
ans thus improves the readability of the code.

NOTES:
------

As far as the forall is concerned, since it may not be independent, the
"external" reduce should exist without attachment:

chpf$ reduce(s)
      forall(i=2:n-1)
        s = s + a(i)
        a(i) = a(i)+a(i-1)+a(i+1)
      end forall

Also it is not very clear to me what to do with reductions into arrays.
(I'm not sure from the minutes whether this is allowed or not)...

chpf$ independent(i,j), reduce(S(i)) ???
      do i=1, n
        do j=1, n
          S(i) = S(i) + A(k,j)
        enddo
      enddo

means that an "internal" directive might be of some help?

CONCLUSION:
-----------

To conclude, I suggest that another "external" (as opposed to the current
"internal") syntax for the reduce directive would (1) leave less work to
the compiler about "guessing" things, (2) be more high level and readable
(3) be less verbose.

Hope this help. Thanks for having read this mail. Comments are welcome.
Have a nice day,

Fabien.

--
Fabien COELHO __ http://www.cri.ensmp.fr/~coelho __ [email-masked]

---------------------------------------------------------------------------
To (un)subscribe to this list, send mail to [email-masked].
Leave the subject line blank, and in the body put the line
(un)subscribe <email-address>
---------------------------------------------------------------------------