Subject: hpff-distribute: Re: HPF reduce directive

From: Rob Schreiber <[email-masked]>
Date: Tue, 2 Jan 1996 09:16:40 -0800

---------------------------------------------------------------------------
[email-masked] is a mailing list for discussion of data
distribution in High Performance Fortran.  Instructions for adding or
deleting yourself from this list appear at the bottom of this message.
---------------------------------------------------------------------------

Dear Fabien,

I know this is a subtle issue.   I thought we had unabiguously defined the
answer to the "shich loop" question as the outermost DO loop that:

i)  Is independent

ii)  Does not have a NEW clause for the reduction variable, and

iii)  Does not *contain* in its range an independent DO loop with a NEW
      clause for the reduction variable.

Also, the reduction statement must be in the lexical range of the DO loop.
Thus, we have addressed the issues of whether more than one reduction statment
may occur (there is no restriction on the number or the place)
and which loops are the scope of the reduction.   Nevertheless, your
points about economy of expression are very well taken.    We should discuss
this alternative.

Rob

	From [email-masked] Tue Jan  2 07:49 PST 1996

	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?
No, I think one could require that ALL of S be treated as a redction variable;
so the list in 

     reduce(something-list)

would be a list of names, not subscripted instances of names (whatever the
F90 syntactic class is).

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