Subject: hpff-task: reduction comments

From: [email-masked] (Rob Schreiber)
Date: Fri, 15 Sep 1995 12:43:54 -0700

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

Original comments by Pres, and replies by me.

-- Rob

	Major items:

	 - I am still not comfortable with the " ; IDENTITY = value" clause.
	What if the user codes:

	       program AbsurdInitialization
	       x=0
	!HPF$ INDEPENDENT, REDUCTION( x; COMBINE = +; IDENTITY = 2. )
	       do i=1,100
	!HPF$    REDUCE
	         x = x + log(i)
	       enddo
	       print *,x
	       end

	Should they be allowed to state an absurd "zero" value for an
	intrinsic operation?  
Absurd, hardly.  The semantics are well defined.   It prints a
processor dependent approiximation to 2*number_of_processors() +
sigma(i=1 to 100) log(i)

I have changed it, however, to forbid combine and identity phrases (clauses?) in the
optional reduction clause for an intrinsic operators.   
Maybe we should just bar the whole REDUCTION clause on the independent directive
for intrinsic reductions.   Should we define the term "intrinsic reduction" in the
text?

        (I wonder if the keyword would be more intuitive
	as "ZERO" rather than "IDENTITY".)  
As in, like, 
!HPF$ INDEPENDENT, REDUCTION(X, COMBINE = *, ZERO = 1)
The mind boggles.

        If each processor initializes its
	local value of x to 2., it would seem that the HPF interpretation of
	this code (if run on more than one processor) would give wildly
	different results than a sequential F90 interpretation.
Yes, a very BAD processor dependent approximation to the sequential result.
This is disconcerting, but I dont see any way around this for user defined
operators, except to REQUIRE that the user create a value "foo" for
his operator bar(x,y) that has the property that bar(foo,y) = y for all y.
Should we.

	I agree that you need a hook for the "zero" value of a user-defined
	operator or reduction function, but I think you also need either:

	 (a) constraint language about the defined state, _and_ _defining_
	_value_ of the reduction variable prior to entry to the loop nest with
	the reduction, or
Do you mean what I said above about the "identity element" property of the
reduction operator and the identity value?

	 (b) prohibit use of the clause for the trivial cases you have
	enumerated in section 3.
Those are the intrinsic cases, where we could certainly make this prohibition.

	 - Again, I think you've surrounded the syntax with so many lexical
	restrictions that any undergraduate senior-level compiler course
	project could find and deal with the reductions with absolutely _no_
	directives!!  Could you at least relax the form of the reduction
	statement to include:

	  var = expr op var

	and maybe even:

	  var = expr1 op var op expr2   ! with constraint that the 2 ops are indentical

No problem here semantically, I guess;   not my call.

	 - It would seem that one cannot:

	 ...
	!HPF$ REDUCE
	          var = var .op. f(x)
	 ...
	!HPF$ REDUCE
	          var = var .op. f(x)
	 ...

	Why not?
Oh?  Where is this rule?

	 - I think the constraints on types of lists of variables and on other
	things that should agree in type, etc., are a little slack.
Got to show me a bug, however, before I can fix them.

	Bottom line:  For user-defined operators and reduction functions, and
	defined-type reduction variables, the clause on the INDEPENDENT and
	the REDUCTION directive are (probably) necessary.  I think you really
	_only_ have to define *protected* for the other cases without any
	clauses and directives, and then you can do the relaxation of
	constraints on the body of INDEPENDENT for the simple situations and
	not have to require any extra stuff for those simple cases.

Can you be a little clearer?   If i understand you, in the case of
reductions with intrinsic operators, you suggest no reduction clause on
the loop and no reduce directive on the operation.   I like this idea;
however, we have, in that case, to prohibit mixed operators, so that
the combine operator and identity value are implied by the (one class
of) reduction operator/function that occurs in the loop.

Rob

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