Subject: ON-Clause / Execute

From: [email-masked] (C.A. Thole)
Date: Tue, 6 Oct 92 15:05:51 GMT

I agree with Tin-Fook, that something like the on-clause should be 
contained in HPF. I brought a proposal with me to the last HPF meeting 
which was distributed by Chuck, but neither the FORALL working group
nor the plenary had time to discuss the proposal.

I enclosed a slightly modified version of the original proposal.
Tin-Fock's proposal and my proposal both use templates as reference
objects.
Tin-Focks proposal is restricted to DO constructs and indexed
parallel assignments while my proposal deals with any statement 
(in particular array assignment statements). 
Tin-Focks proposal has the optional LOCAL directive. 
This proposal introduces statement blocks for more compact 
spezification of on-clauses. 

I would appreciate comments on the different features.

Clemens

------------------------------------------------------------------

Proposal for a statement grouping syntax and ON clause

original:          September 9, 1992
slightly modified: October 5, 1992

Clemens-August Thole
GMD-I1.T
Schloss Birlinghoven
D-5205 Sankt Augustin 1

e-mail: [email-masked]

1. Introduction

This proposal introduces an extension to HPF to group several 
statements in order to be able to specify properties for a whole block
of statement at once. A block of statements is called HPF-section.
HPF-sections can be used to describe properties for independent execution
between blocks of statements aswell as the mapping of their execution.

For the spezification of a specific mapping of the execution of statements
or HPF-sections the ON-clause is introduced. A subset of a template is used
as reference object onto which the statements are mapped in an canonical
manner. The careful selection of the reference template allows to specify,
how the execution of the code is mapped onto the parallel architecture.

2. HPF-sections

The HPF directives SECTIONS, SECTION, and END SECTIONS are used to specify
grouping of statements. SECTIONS and END SECTIONS specify the beginning
and end of a list of HPF-sections and SECTION the beginning of the next 
HPF-section. The syntax is as follows:

	!HPF$ SECTION
		[HPF-section-list]
	!HPF$ END SECTIONS

where HPF-section is

	!HPF$ SECTION
		[execution-part]

Constraint: For any HPF-section under no circumstances a transfer of control
is performed during the execution of the code outside of its execution-part.

Example:
	
	!HPF$ SECTIONS
	!HPF$ SECTION
		A = A + B
		B = C + D
	!HPF$ SECTION
		E = B
		IF (E.GT.F) GOTO 10
			E = 0D0
	 10	CONTINUE
	!HPF$ END SECTIONS

This example specifies a list of two HPF-sections. The control statement in
the second HPF-section is valid because after the transfer of control the
execution continues in the same HPF-section.

2. ON-clause

The ON-clause specifies a subsection of a template, which is used as a reference
object for the execution of the next statement, construct, of HPF-section.
If the left-hand-side of an assignment coinsides in shape with the reference
object, the evaluation of the right-hand-side and the assignment for 
a specific element of the left-hand-side is performed at that processor, onto
which the corresponding element of the reference object is mapped.

Syntax:

Add the following rules:

[executable-construct] is

	!HPF$ ON [on-spec]
		[executable-construct]

and

[HPF-section] is

	!HPF$ ON [on-spec]
		[HPF-section]
	
where [on-spec] is

	[align-spec].

The [executable-construct] of [HPF-section] is called on-clause-target.

Constraints:

1. No [executable-construct] may be used as object of the on-clause, which
   generates any transfer of control out of the construct itself. This
   includes the entry-statement. 
2. [statement-block]s used in constructs must fulfill the constraints of
   HPF-sections.
3. The shape of the [on-spec] must cover in each dimension the shape of
   of any left-hand-side of an assignment statement, which is target of an
   on-clause. If a "*" is used in the [on-spec], this dimension is skipped
   for constructing the shape of the [on-spec].
4. If an on-clause is contained in the on-clause-target, the new [on-spec]
   must be a subsection of the [on-spec] of the outer on-clause.

Example:

		REAL, DIMENSION(n) :: a, b, c, d
	!HPF$	TEMPLATE grid(n)
	!HPF$	ALIGN WITH grid :: a, b, c, d

	!HPF$	ON grid(2:n)
		a(1:n-1) = a(2:n) + b(2:n) + c(2:n)

The on-clause indicates, that the evaluation of the right-hand-side is 
performed on that processors, which hold the data elements of the 
right-hand-side. For the assignment to the left-hand-side data movement is
necessary.

Interpretation:

The interpretation of the on-clause depends on the type of the on-clause-target.

If the on-clause-target is an assignment statement the [on-spec] is used to
determine where the assignment statement is executed. If the shape of the 
right-hand-side is identically to the shape of [on-spec], the computation for
a specific element of the assignment statement is performed where the 
corresponding element of the [on-spec] is mapped to. If the shape of the 
[on-spec] is larger, the compiler may use any sufficient larger subsection.
The use of "*" in the [on-spec] specifies, that the same computations are
mapped onto the corresponding line of processors and several processors
will do the same update. This may save communication operations.
The the case of the where-statement, the forall-statement, and the 
forall-construct the same mapping is applied to the evaluation of the 
conditions and each assignment.

If the on-clause is placed in front of the if-construct, that case-construct,
or the do-construct, the [on-spec] is used for the evaluations of the 
conditions as well as the loop bounds and the execution of the statement-blocks,
which are part of the construct. For the statement-blocks the interpretation 
rules for HPF-sections apply.

With respect to the allocate, deallocate, nullify, and I/O related statements
the [on-spec] is used for the evaluation of the parameters of the statements
and the evaluation of I/O objects. 

In the case of subroutine calls and functions the [on-spec] is used for the
evaluation of the parameters. It determines also the mapping of the resulting 
object. The [on-spec] determines also the set of processors, which will be
used for the evaluation of the subroutine. 

In the case of HPF-sections the on-clause is applied to each statement of the
execution part. Control transfer statements are allowed in this case and the 
constraints ensure, that the context on the same [on-spec] is not lost.

Additional example:

		REAL, DIMENSION(n,n) :: a, b, c, d
	!HPF$	TEMPLATE grid(n,n)
	!HPF$	ALIGN WITH grid :: a, b, c, d

	!HPF$	ON grid(2:n,2:n)
		DO i=2,n
	!HPF$		ON grid(i,2:n)
			DO j=2,n
	!HPF$			ON grid(i,j)
				a(i-1,j-1) = a(i,j) + b(i,j)*c(i,j)
			ENDDO
		ENDDO

Comment:

The compiler should be able to adjust the span of the loops to the local extend 
due to the restrictions on the specifiers of the sections of the [on-spec].