Subject: hpff-task: ON clause proposal

From: [email-masked] (Chuck Koelbel)
Date: Mon, 8 Jan 1996 16:14:37 -0600 (CST)

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

Apologies to HPFF attendees, who probably will not see this before they
arrive at the meeting.

Updates:
"ALL" option is now "EVERY"
"LOCAL" clause is now "RESIDENT"
Omitting the local-var-list in RESIDENT means "all references are local"
Added a "declarative" form of the ON clause.
Options for ON applied to a CALL statement -
        1. Propagate ON through the call, but the user
           must declare the matching ON in the callee.
        2. All CALLs execute on every processor, i.e.
           ON is ignored for calls
I highly favor the first option.

Hoping that, just this once, Eudora doesn't convert the attachment into
BinHex format...

                                                Chuck

The ON Clause

Charles Koelbel and Rob Schreiber

The purpose of the ON directive is to allow the programmer to control the
distribution of computations among the processors of a parallel machine.
In a sense, this is the dual of the DISTRIBUTE and ALIGN directives for
data.  Modern parallel machines will achieve their best performance if all
operations are performed by separate processors (as specified by ON) with
each processor accessing its local data (as specified by DISTRIBUTE).
If either explicit computation partitioning or explicit data mapping is not
present, the system must choose one.

A secondary purpose of the ON directive is to identify data accessed by
the computation as local to the executing processor.  The compiler can use
this information to avoid generating communication or to simplify array address
calculations.  Note that whether a given data element is local depends on
two facts:
        Where the data is stored (i.e. its DISTRIBUTE and ALIGN attributes)
        Where the computation is executed (i.e. its ON directive)
For these reasons, the LOCAL clause is added to the ON directive, which is
effectively the earliest point in the program where the needed facts might
be available.  Note that changing the ON directive may invalidate some
LOCAL clauses, or may make some new LOCAL clauses true.

Syntax

There are two flavors of the ON directive: a single-statement form, and a
multi-statement form.  The BNF for both is

        simple-on-directive     IS      ON HOME ( home-expr ) [ , resident-clause ]
        decl-on-directive IS ENVIRONMENT :: simple-on-directive
        
        resident-clause IS      RESIDENT [ ( local-var-list ] ) ]
        
        block-on-directive      IS      simple-on-directive BEGIN
        end-directive   IS      END [ BEGIN ]
        
        on-block        IS      
                block-on-directive
                block
                end-directive

        home-expr       IS      variable
                OR      template-elmt
                OR      processors-elmt
        
        template-elmt   IS      template-name [ ( section-subscript-list ) ]
        
        processors-elmt IS      processors-name [ ( section-subscript-list ) ]
        
        local-var       IS      variable
                OR      EVERY = variable-name

Notes:
Constraints need to be added above...
Also, changes are needed in some higher-level syntax (for example, adding
simple-on-directive as an option to executable-directive).

home-expr, template-elmt, and processors-elmt are just auxiliary syntax
categories.  Note that "variable" is an F90 syntax term that means
(roughly) "a reference, including an array element, array section, or
derived type field"; "variable" doesn't include template or processor
elements since those aren't first-class language constructs.  Note also
that "block" is an F90 syntax term for "a series of statements treated as
a group" - for example, the body of a DO construct.

simple-on-directive should be an option under executable-directive (HPF
syntax term), as redistribute-directive is now.  This means that
simple-on-directive can be used as an executable statement.

decl-on-directive should be an option under specification-directive, as
distribute-directive is now.  This means that decl-on-directive is used as
a declaration.  Any expressions in home-expr or resident-clause of
decl-on-directive must be specification expressions; this is not a
constraint on simple-on-directive.

on-block most naturally fits as a F90 executable-stmt, since that makes
constraints about "properly nesting" easier to state.

Any top-level variables in the RESIDENT clause must be explicitly
mapped.  Otherwise, the assertion (see below) is a statement about how the
compiler works, not about the program.

Rationale:
The keyword HOME is required, even when its argument is a processor.  It
seems more natural to eliminate the HOME keyword there, but this leads to
the following ambiguity:

        INTEGER X(4)    ! X(I) will be on processor I
        !HPF$ PROCESSORS HOME(4)
        !HPF$ DISTRIBUTE X(BLOCK)
        X = (/ 4,3,2,1 /)
        !HPF$ ON HOME(X(2))
        X(2) = X(1)

If HOME were not required, where should the computation be done:
1. Processor HOME(2) (i.e. the owner of X(2))?
2. Processor HOME(3) (i.e. the value of X(2), before the assignment)?
3. Processor HOME(4) (i.e. the value of X(2), after the assignment)?
The definition of ON clearly indicates interpretation 1 is correct.  One
can get the effect of interpretation 2 by the directive
        !HPF$ ON HOME(HOME(X(2)))
There is no way to get the effect of interpretation 3, short of building a
clairvoyant computer.  Introducing reserved keywords into Fortran was
suggested as a better solution to this problem, but was seen as too large a
change to the underlying language.

Separate syntax is needed for simple-on-directive and decl-on-directive
to avoid ambiguity.  If the same directive can be used as both both an
executable statement and a declaration, its role is unclear if it is the
last statement in the declarations/first statement in the executable
section.  This is particularly bad since the "scope" of the directive is
rather different in the two uses.  That said, I'd be grateful if somebody
could suggest a better declaration syntax.
End of rationale.

Semantics

The ON directive advises the compiler to perform a computation using the
processor(s) named in the argument to HOME.  It has two forms:
        * simple-on-directive, which applies to the next executable statement or
          a block of executable statements.
        * decl-on-directive, which is a declaration for an entire scope.
Like the mapping directives ALIGN and DISTRIBUTE, this is advice rather
than an absolute commandment; the compiler may override an ON directive if
necessary.  Also like ALIGN and DISTRIBUTE, the ON directive may affect the
efficiency of computation, but not the final results.

Advice to implementors:
If the compiler may override the user's advice in an ON directive, then
the compiler should also offer the user an option to force all directives
to be obeyed.
End advice to implementors.

The single-statement ON directive (i.e.  simple-on-directive) precedes the
statement for which it is advising behavior, and is said to apply to that
statement.  If the statement is a compound statement (e.g.  a DO loop or an
IF-THEN-ELSE construct), then the ON directive also applies to all nested
statements therein.  Similarly, the block ON directive (i.e.  on-block)
applies the initial ON clause to all statements up to the matching END
directive.  The declarative form of the ON directive (i.e.
decl-on-directive) applies to all statements and declarations in a scope;
its intended use is for functions and subroutines that may be called on a
subset of the processors.

The HOME clause can name a program variable, a template, or a processors
arrangement.  For each of these possibilities, it can further specify a
single element or multiple elements.  This is translated into the
processor executing the computation as follows:
*       If the HOME clause names a program variable (that is, an array element
        or section), then every processor owning any part of that variable
        should execute the computation.  For example, if a is a distributed array
                !HPF$ ON HOME ( a(2:4) )
        tells the compiler to perform the statement on the processors owning
        a(2), a(3), and a(4).  If a were distributed BLOCK, this might be one
        processor; if a were distributed CYCLIC, it would be three processors.
*       If the HOME clause names a template element or section, then every
        processor owning any element of the template should execute the computation.
        The example above applies here as well, if a is a template rather than an
        array.
*       If the HOME clause names a processors arrangement, then the processor(s)
        referenced there should execute the computation.  For example, if p
        is a processors arrangement,
                !HPF$ ON HOME ( p(2:4) )
        will execute the statement on the three processors p(2), p(3), and p(4).
For the executable forms of the directive, the value(s) of the HOME clause
are determined as if the HOME argument was evaluated when control flow
reached the ON directive.  For the declarative form, the values are
determined on entry to the scope.  That is, if the value of a variable used
in the HOME clause changes within the on-block, work is not migrated to a
new processor.  If evaluation of the argument of the HOME clause would
change the value of any variable in the program, then the value of that
variable becomes undefined after the ON clause is reached.  Finally, note
that the HOME clause only specifies how computation is partitioned among
processors; it does not indicate processors that may be involved in data
transfer.

Rationale:
This is the heart of the ON clause.

The "as if" wording and making side effects undefined avoids the following
problem: ON is a directive.  Therefore, it cannot have side effects.  But
implementing the ON clause may require evaluating some functions, therefore
causing the side effects.
End of rationale.

Advice to implementors:
If the HPF program is compiled into Single-Program-Multiple-Data (SPMD)
code, then the ON clause can always be implemented (albeit inefficiently)
by having all processors compare their processor id to an id (or list of
ids) generated from the HOME clause.  (Similar naive implementations can be
constructed in other paradigms as well.) If the ON clause will be executed
repeatedly, for example in a DO loop, it is probably worthwhile to invert
this process.  That is, instead of all processors executing all the HOME
clause tests, the compiler should determine the range of loop iterations
that will give a true test.  (See the "Advice to implementors" in the
Examples section below for more details.) For example, consider the
following complex case:
        DO I = 1, N
                !HPF$ ON HOME( A(MY_FCN(I)) ) BEGIN
                ...
                !HPF$ END ON
        END DO
Here, the generated code can perform an "inspector" (i.e.  a skeleton loop
that only evaluates the HOME clause of each iteration) to produce a list of
iterations assigned to each processor.  This list can be produced in
parallel, since MY_FCN must be side-effect free; however, distributing it
to all processors may require unstructured communications patterns,
possibly negating the advantage of parallelism.  In general, more advanced
compilers will be able to efficiently invert more complex HOME clauses.  It
is recommended that the abilities (and limitations) of a particular
compiler be documented clearly for users.

Note that processors "screened out" by the naive implementation may still
be required to participate in data transfer.  (The RESIDENT clause can
eliminate this, but it is optional.)  If the underlying architecture
allows one-sided communication, this is not a problem.  On traditional
message-passing machines, a request-reply protocol may be used.  This
requires the inactive processors to enter a wait loop until the ON block
completes, or requires the runtime system to handle requests
asynchronously.  Again, it is recommended that the documentation tell
programmers which cases are likely to be efficient and which inefficient
on a particular system.
End advice to implementors.

Advice to programmers:
The argument to HOME in an ON clause can be arbitrarily complex.  This is a
two-edged sword; it can express very complicated computation partitioning,
but the implementation of these partitions may not be efficient.  More
concretely, it may express a perfectly load-balanced computation, but force
the compiler to serialize the computation of the HOME clauses.  Although
the amount of overhead for an ON clause will vary based on the HPF code,
the compiler, and the hardware, one can expect that compilers will generate
very good code based solely on array mappings or a named processor
arrangement, and progressively worse code as the complexity of the HOME
clause increases.  A rough measure of the complexity of an ON directive is
the amount of run-time data used to compute it; for example, a constant
offset is fairly simple, while a permutation array is very complex.  See
the Examples section below for more concrete examples of this phenomenon.

It is worth noting that the ON clause alone does not address data
movement.  (The RESIDENT clause will do this.)  Therefore, on some
machines additional processors will have to enter the ON block to take
part in communication.
End of advice to programmers.

It is legal to nest ON directives, provided that the processors named by
the inner ON directive are also named by the outer directive.  The syntax
of on-block automatically ensures that it is properly nested inside other
compound statements, and that compound statements properly nest inside of
it.  As with other Fortran 90 compound statements, transfer of control to
the interior of an on-block from outside the block is prohibited, while
transfers within a block may occur.  However, HPF also prohibits transfers
of control from the interior of a on-block to outside the on-block.  Note
that this is stricter than Fortran 90.  If ON clauses are nested, then the
innermost HOME clause effectively controls execution of the statement(s).
A programmer can think of this as successively restricting the set of
processors at each level of nesting; clearly, the last restriction must be
the strongest.  Alternately, the programmer can think of this as a
fork-join approach to nested parallelism.

Rationale:
The restrictions about control flow into and out of an ON block essentially
make it a single-entry single-exit region, thus simplifying the semantics
considerably.
End Rationale.

OPTIONS

Note to language designers:
Here follow two possible semantics for ON applied to procedure calls.  The
first is close in spirit to the original proposal - roughly speaking, ON
applies to statements inside the called procedure.  (I've attempted to
avoid some compilation problems by requiring ON clauses in the callee.
More stringent restrictions, like only allowing PURE functions, could avoid
one-way communication, maybe.)  The second is my take on the
"everybody participates in CALLs" proposal at the September meeting.  (My
memory is a bit vague, so I apologize if it is not what was meant.)  I
believe these are mutually exclusive.  I guess that a third proposal would
be to disallow CALL inside an ON directive, but this makes ON
much less useful.
End of note to language designers.

OPTION 1: ON IS PROPOGATED THROUGH CALL STATEMENTS.

It is legal for an ON directive to apply to a CALL statement or a statement
containing a function invocation.  In this case, the treatment is similar
to that for a compound statement.  The ON directive tells the compiler
which processors should execute the statements in the procedure body.  Any
processor named by an ON directive inside the subroutine must be included
by the ON directive in the caller.  If ON clauses appear in a subroutine
call chain, then the deepest ON clause (i.e.  the one in the last called
routine that is still active) effectively controls the computation.

In addition, any procedure whose caller is controlled by an ON directive
must include a valid declarative ON directive which applies to the entire
called procedure.  If the procedure has an explicit interface, this
ON declaration which must be included in this interface.  (I.e.  if the
interface is though an INTERFACE block, then the INTERFACE specification
must include the ENVIRONMENT :: ON clause.) If the procedure uses an
implicit interface, then the compiler may assume that the directive is in
fact present.

Note that EXTRINSIC procedures always have an explicit interface, and thus
will require an ON declaration if they are called from an ON block.  In
this case, the effect of the call is still as if the procedure were called
on all processors.

If the procedure uses alternate return, then the target of the return must
be in the same ON block as the CALL statement.  This implies that labels
passed as arguments must refer to statements in the same ON block as the
CALL statement.

Rationale:
It is natural to treat a procedure call within an ON clause as if it were
an in-lined program block.  This leads to "propagating" the ON directive
into the procedure.  Making the ON directive explicit in the callee allows
separate compilation (i.e.  the compiler need not perform interprocedural
analysis in order to select the calling convention).

The constraint on alternate return is similar to the prohibition against
jumping out of an ON block, and has the same justification.
End of Rationale.

Note to language designers:
I just had an epiphany:
        * The declarative ON constrains the declarations to only map to the ON
          processor set.
        * Global data must be declared.
        * Therefore, only global data stored on the ON processor set can be
          accessed.
        * Therefore, we don't need one-way communication for global data inside
          CALLS from ON clauses.
        * Similar reasoning applies to dummy arguments.
Somebody check this.  If this really finesses the one-way communications
problem, then we need to point it out!  (It's also a pretty significant
restriction on HPF expressibility - can't get to global data sometimes.)
        
Is this what we want for EXTRINSIC procedures?  On one hand, ON and
EXTRINSIC ought to be orthogonal.  On the other, it seems more natural that
an EXTRINSIC called within an ON would synchronize only the processors
from the ON, not all the processors.  But that would mean that ON would
change the semantics of EXTRINSIC (maybe...)

We could disallow alternate returns from procedures called from ON
clauses.  I'd sort of prefer that, but in the spirit of backward
compatibility I've just specified the minimum (I think) constraints.
End of note to language designers.

Advice to implementors:
Notice that nested ON clauses do not present additional problems for the
naive implementation.  If a processor failed the outer HOME comparison,
then it would fail any tests inside the ON as well.  Thus, it need not even
make the tests.

The difficulties of implementing one-way communication on message-passing
machines remain, however.
End of advice to implementors.

Advice to users:
A CALL statement from within an ON block effectively executes the
subroutine on a subset of processors.  In conjunction with other
declarations, this allows a fork-join style of parallelism.

Note that the earlier advice regarding data movement still applies.
Message-passing machines may need to perform the call statement on many
(even all) processors in order to properly exchange data between
processors.
End of advice to users.

OPTION 2: ALL SUBROUTINES PARTICIPATE IN ALL CALL STATEMENTS

It is legal for an ON directive to apply to a CALL statement or a statement
containing a function invocation.  In this case, the semantics are
somewhat different from an equivalent ON block.  The procedure invocation
is performed on all processors, although ON clauses in the called procedure
may again restrict execution to a subset of processors.

If the procedure uses alternate return, then the target of the return must
be in the same ON block as the CALL statement.  This implies that labels
passed as arguments must refer to statements in the same ON block as the
CALL statement.

Rationale:
Procedures may declare local variables and (re)declare globals, both of
which may be mapped onto all processors.  Therefore, the CALL must be
executed on all processors to properly handle memory allocation.  Note
that this is the same semantics as EXTRINSIC subroutines, which are also
conceptually invoked on all processors.

The constraint on alternate return is similar to the prohibition against
jumping out of an ON block, and has the same justification.
End of Rationale.

Note to language designers:
We could disallow alternate returns from procedures called from ON
clauses.  I'd sort of prefer that, but in the spirit of backward
compatibility I've just specified the minimum (I think) constraints.
End of note to language designers.

Advice to implementors:
This simplifies separate compilation of subroutines.  The compiler can
assume that the procedure is always invoked on all processors, and
therefore be assured that global operations (e.g. barriers) will not deadlock
due to inactive processors.  The CALL statement can be implemented by a
new request type in the request-reply loop.
End of advice to implementors.

END OF OPTIONS

Operations controlled by an ON clause must follow certain restrictions:

* If an ON directive applies to a DISTRIBUTE directive, then the set of
processors named in the HOME clause must include
        - All processors named in the DISTRIBUTE's ONTO clause if one is present
        - All processors in the default processors arrangement, if there is no
          ONTO clause
* If an ON directive applies to a REDISTRIBUTE directive, then the set of
processors named in the HOME clause must include
        - All processors that stored any element of the distributee before
          the REDISTRIBUTE was encountered
        - The processors required by an equivalent DISTRIBUTE directive
* If an ON directive applies to a REALIGN directive, then the set of
processors named in the HOME clause must include
        - All processors that store any element of the align-with-clause
* If an ON directive applies to a REALIGN directive, then the set of
processors named in the HOME clause must include
        - All processors that stored any element of the alignee before
          the REALIGN was encountered
        - The processors required by an equivalent ALIGN clause
* If an ON directive applies to an ALLOCATE statement which creates an
explicitly mapped variable, then the set of processors named in the HOME clause
must include the processors required by the associated DISTRIBUTE or ALIGN
directive.
* If an ON directive applies to any other declaration of an explicitly
mapped variable, then the set of processors named in the HOME clause
must include the processors required by the associated DISTRIBUTE or ALIGN
directive.

If operations within an ON block do not follow these constraints, then the
program is not HPF-conforming.

Note to language designers:
An alternative for the DISTRIBUTE would be that an missing ONTO clause
would mean "distribute on all processors in the nearest enclosing ON
directive" rather than "distribute on all processors".  In some sense, this
makes the nested fork-joins more modular (declarations inside a forked
region only need to know about the region they are part of).  It is
especially appropriate now that we have the declarative ON directive.  I
have not investigated the difficulty of writing things this way, but it
probably requires fine-tooth combing through the data mapping chapter and
inquiry intrinsics.
End of note to language designers.

Rationale:
Operations which allocate memory require the cooperation of all processors
that will own that memory.  Therefore, ON clauses must schedule those
operations to execute on the cooperating processors.
End of rationale.

Advice to implementors:
These restrictions ensure that HPF data distribution directives inside
an ON block (either lexically or in a dynamic call chain) can be
implemented without relying on one-way communication outside of the
"current" processing group.
End of advice to implementors.

The RESIDENT clause, if present, is an assertion to the compiler that
certain array references made within the ON are stored in local memory if
the computation is performed by the processor(s) named in the HOME clause.
Specifically, if an element in the local-var list is a variable, array, or
array section, then that element will be stored on at least one of the
processors from the HOME clause.  If the local-var is of the form
EVERY=variable-name, then all references to that variable that the ON
applies to will be stored on at least one of the named processors.  If
there is no local-var-list, then all references to all variables that the
ON clause applies to will be stored on at least one of the named
processors.  As with the HOME clause, the value(s) of the RESIDENT clause
are determined as if the local-var-list was evaluated when control flow
reached the ON directive, and possible side effects in the RESIDENT clause
cause the affected variables to become undefined.

Rationale:
The EVERY=variable-name form is syntactic sugar for listing every reference
to an array in the ON block.  In fact, it is more powerful than such a list
because the values of subexpressions within a reference need not be defined
when EVERY is encountered.  This is similar in spirit to APR's grouping
IGNORE directives by variable.  (Note that EVERY(variable-name) doesn't
work, since then a program with a variable named EVERY would be ambiguous.)

RESIDENT without any local-var-list is syntactic sugar for listing EVERY
for all variables referenced within an ON block.  It might well have been
named the ALL_RESIDENT clause; the present form, however, does not add yet
another keyword to the directive sublanguage.

The pseudo-evaluation of the RESIDENT clause is the same as the HOME clause,
for the same reason.  Treating the RESIDENT clause as naming sets of
variables, rather than as a list of lexical references, gives a reasonably
firm  logical basis to what the assertion means.  It is unclear whether
compilers would rather see this "symbolic" information or longer lists that
need to be pattern-matched.  It is also unclear which approach would
appeal more to programmers.
End Rationale.

OPTIONS

Note to language designers:
Here are two options for RESIDENT when applied to CALL.  They mirror the
above propagate/don't propagate options.
End of note to language designers.

OPTION 1: RESIDENT IS PROPAGATED TO CALLEES

If a RESIDENT clause applies to a CALL statement, then it is an assertion
about the internals of the called procedure as well as an assertion about
code in the caller.  For example,
        * RESIDENT( A(I) ) means that for the current value of I, if the called
          procedure accesses element A(I) then that element is stored on a
          processor named by this ON directive.
        * RESIDENT( EVERY=B ) means that all elements of B that are accessed by
          the callee are stored on a processor named by this ON directive.
        * RESIDENT with no local variable list means that all references made by
          the callee are stored on a processor named by this ON directive.

Rationale:
This provides maximum information to the compiler.  It is also in line with
the propagation of ON directives to the callee.
End of rationale.

Advice to implementors:
RESIDENT without a variable list guarantees that no one-sided
communication outside of the ON processor set will be generated by the
callee.  Such a procedure can be called only on the "active" processors,
unless the runtime system has additional constraints (for example, if the
runtime system requires all processors to participate in collective
communications).

The other forms of RESIDENT provide information that could be propagated
interprocedurally.  If the information is not propagated, the only result
will be less optimization.
End of advice to implementors.

Advice to programmers:
Although the RESIDENT assertion applies interprocedurally, it is by no
means certain that all compilers will make use of this information.  In
particular, separate compilation limits the propagation that can take
place.  It is therefore good practice to include a RESIDENT clause
both in the caller's ON directive and in the callee's ON declaration.
This ensures that the compiler has the RESIDENT information available when
it is compiling both ends of the procedure call.  This is especially
useful for RESIDENT clauses without a variable list; knowing that all data
accessed is local allows many optimizations that are not otherwise
possible.
End of advice to programmers.

OPTION 2: RESIDENT IS NOT PROPAGATED TO CALLEES

A RESIDENT clause that applies to a CALL statement does not assert
anything about the internals of the called procedure.  In particular,
        * RESIDENT( EVERY=A ) asserts that all references to A in the caller
          (including actual arguments to a subroutine) are stored on the ON
          processor set, but does not guarantee that the subroutine makes no
          nonlocal accesses.
        * RESIDENT without a local variable list ensures that the actual
          arguments to the CALL are all stored locally, but allows the subroutine
          to access global data from other processors.
Other RESIDENT assertions (in particular, asserting that particular
elements or subsections of an array are local) are true in both the caller
and the callee.  (Note that these are essentially statements of fact about
the array section bounds, so they must be universally true.)  However,
compilers are not required to propagate this information to the callee.

Rationale:
Propagated EVERY clauses are susceptible to becoming invalid if a procedure
is modified.  In particular, adding a reference in a subroutine could
invalidate EVERY assertions in all of its callers.
End of rationale.

END OF OPTIONS

Note that if the HOME clause specifies more than one processor, then RESIDENT
only asserts that the variables are stored on one of the processors.  For
example, if a statement is executed on a section of the processors
arrangement, then communication within that section may be needed for some
variables in the RESIDENT clause.  Communication with processors outside of
the section will not be needed for those variables, however.

Rationale:
The alternative to this interpretation would be that any variable named in
the RESIDENT clause would be local to all processors, i.e. replicated.
While that certainly allows more extensive optimizations, it is a less
common case.  In addition, it does not seem to capture the intent of ON
directives applied to CALL statements or compound statements.  For example,
        !HPF$ PROCESSORS PROCS(MP,MP)
        !HPF$ DISTRIBUTE X(BLOCK,BLOCK) ONTO PROCS
        !HPF$ ON HOME(PROCS(1,1:MP)), RESIDENT( X(K,1:N) )
        CALL FOO( X(K,1:N) )
would presumably call FOO on a row of the processors arrangement, passing
elements of X in place.  This is what the current definition does; if
RESIDENT meant "resident on every processor", the call would force X to be
replicated.
End Rationale.

The RESIDENT assertion is similar to the INDEPENDENT directive, in that if it
is correct it does not change the meaning of the program.  If the RESIDENT
clause in incorrect, the program is not standard-conforming (and is thus
undefined).  Like the INDEPENDENT directive, the compiler may use the
information in the RESIDENT clause, or ignore it if it is insufficient for the
compiler's purposes.  If the compiler can detect that the RESIDENT clause is
incorrect (i.e.  that a RESIDENT variable is definitely nonlocal), it is
justified in producing a warning.  Unlike the INDEPENDENT directive,
however, the truth of the RESIDENT clause depends on the mapping of
computations (specified with the ON clause) and the mapping of data
(specified with DISTRIBUTE and ALIGN clauses); if the compiler overrides
either of these, then it may not be able to use information in the RESIDENT
directive.

Rationale:
Knowing that a reference is local is valuable information for the
optimizer.  It is in keeping with the spirit of HPF to phrase this as an
assertion of fact, which the compiler can use as it pleases.  Expressing
it as advice to the compiler seems to have disadvantages.  Some possible ways
this advice could be phrased, and the counter-arguments, are
*       "Don't generate communication for this reference" has great potential
        for changing the meaning of the program.  Some programmers want this
        capability, but it violates the "correct directives should not change the
        meaning of a program" principle of HPF.  Also, once communication is
        "turned off" for a reference, it's not clear how to turn it back on.
*       "Generate communication for this reference" is not a useful directive,
        since the compiler has to do this anyway.
*       "Generate communication for this reference, and place it here" is useful,
        since it can override the default placement by the compiler.  It still
        has potential for changing program meaning.  It also has the potential to
        create programs as complex as message-passing, as programmers try to move
        communication out of loops.
End of rationale.

Examples

The following are valid examples of ON directives.  Most of them are
"reasonable" in the sense that they illustrate idioms that programmers
might want to use, rather than contrived situations.  For simplicity, the
first several examples assume the following array declarations:

        REAL A(N), B(N), C(N), D(N)
        !HPF$ DISTRIBUTE A(BLOCK), B(BLOCK), C(BLOCK), D(BLOCK)

One of the most commonly requested capabilities for HPF as to control how
loop iterations were assigned to processors.  (Historically, the ON clause
first appeared to perform exactly this role in the Kali FORALL construct.)
This can be done by the ON directive, as shown in the following examples:

        !HPF$ INDEPENDENT
        DO I = 2, N-1
          !HPF$ ON HOME(A(I))
          A(I) = (B(I) + B(I-1) + B(I+1))/3
        END DO
        
        !HPF$ INDEPENDENT
        DO J = 2, N-1
          !HPF$ ON HOME(A(J+1)) BEGIN
            A(J) = B(J+1) + C(J+1) + D(J+1)
          !HPF$ END ON
        END DO

The ON directive in the I loop advises the compiler to have each processor
run over its local section of the A array (and therefore B as well).  The
references to B(I-1) and B(I+1) must be fetched from off-processor for the
first and last iterations on each processor (except for the boundary
processors); note that those processors are not mentioned in the HOME
clause.  The ON directive in the J loop advises the compiler to "shift"
computations so that each processor does a vector sum of its local sections
of B, C, and D, stores the first element of the result on the processor to
its left, and stores the rest of the result (shifted by one) in A.  It is
worth noting that the directives would still be valid (and minimize
nonlocal data accesses) if the arrays were distributed CYCLIC, although the
number of nonlocal references would be much higher.

Advice to implementors:
It is highly recommended that compilers concentrate on optimizing DO loops
with a single ON clause including the entire loop body.  Schematically,
the code will be:

        DO i = lb, ub, stride
                !HPF$ ON HOME(array(f(i))) BEGIN
                body
                !HPF$ END ON
        END DO

Where array has some data mapping.  Assume the mapping give processor p
the elements my_set(p).  (In a BLOCK distribution, for example, my_set(p)
is a contiguous range of integers.)  Then the generated code on processor
p should be

        DO i in [lb:ub:stride] intersect f^-1(my_set(p))
                body
        END DO

(This schematic does not show where communication or synchronization must
be placed; that must be derived from analysis of the body.) Moreover, f is
most likely to be the identity function or a linear function with integer
coefficients, both of which can be inverted easily.  Given this, techniques
for iterating through the set can be found in several recent conferences.
End of advice to implementors.

Advice to users:
One can expect the I loop above to generate efficient code for the
computation partitioning.  In effect, the compiler will arrange for each
processor to iterate over its own section of array A.  The J loop is
slightly more complex, since the compiler must find the inverse of the HOME
clause's subscripting function.  That is, the compiler must solve K=J+1 for
J, where K ranges over the local elements of A.  Of course, in this case
J=K-1; in general, linear functions can be inverted by the compiler.  (It
should be pointed out, however, that complex combinations of ALIGN and
DISTRIBUTE may make the description of K unwieldy, and this may add
overhead to the inversion process.)
End of advice to users.
Sometimes it is advantageous to "split" an iteration between processors.
The following case shows one example of this:
        
        !HPF$ INDEPENDENT
        DO I = 2, N-1
          !HPF$ ON HOME(A(I))
          A(I) = (B(I) + B(I-1) + B(I+1))/3
          !HPF$ ON HOME C(I+1)
          C(I+1) = A(I) * D(I+1)
        END DO

Due to the first ON clause, the reference to A(I) is local in the first
statement. The second ON clause makes A(I) nonlocal (for some values of I)
there.  This maximizes the data locality in both statements, but does
require data movement between the two.

Advice to implementors:
If there are several non-nested ON clauses in a loop, then the schematic
above needs to be generalized.  In essence, the iteration range for each
individual ON clause must be generated.  A processor will then iterate over
the union of these ranges. Statements guarded by an ON directive must now
be guarded by an explicit test.  In summary, the code for

        DO i = lb, ub, stride
                !HPF$ ON HOME(array1(f1(i)))
                stmt1
                !HPF$ ON HOME(array2(f2(i)))
                stmt2
        END DO

on processor p becomes

        set1 = [lb:ub:stride] intersect f1^-1(my_set1(p))
        set2 = [lb:ub:stride] intersect f2^-1(my_set2(p))
        DO i in set1 union set2
          IF (i in set1) THEN
            stmt1
          ENDIF
          IF (i in set2) THEN
            stmt2
          ENDIF 
        END DO

where my_set1(p) is the local set for array1, and my_set2(p) is the local
set for array2.  (Again, synchronization and communication must be handled
by other means.)  Code transformations such as loop distribution and loop
peeling can be used to eliminate the tests in many cases.  They will be
particularly profitable if there are data dependences between the ON
blocks.
End of advice to implementors.

Advice to users:
Splitting an iteration like this is likely to require either additional
tests at runtime or additional analysis by the compiler.  Even if the
compiler can generate low-overhead scheduling for the individual ON
clauses, combining them is not necessarily low-overhead.  The locality
benefits must be rather substantial for this to pay off, but there are
cases where multiple ON clauses are valuable.  (All these statements are
particularly true if one ON block uses data computed in another one.)
End of advice to users.

Because ON clauses nest naturally, they can be useful for expressing
parallelism along different dimensions.  Consider the following examples:

        REAL X(M,M)
        !HPF$ DISTRIBUTE X(BLOCK,BLOCK)
        
        !HPF$ INDEPENDENT, NEW(I)
        DO J = 1, M
          !HPF$ ON HOME(X(:,J)) BEGIN
            DO I = 2, M
              !HPF$ ON HOME(X(I,J))
              X(I,J) = (X(I-1,J) + X(I,J)) / 2
            END DO
          !HPF$ END ON
        END DO

Each iteration of the J loop is executed by a column of the processors
arrangement.  The I loop further subdivides the computation, giving each
processor responsibility for computing the elements it owns.  Many
compilers would have chosen this computation partitioning automatically for
such a simple example.  However, the compiler might have attempted to fully
parallelize the outer loop, executing each inner loop sequentially on one
processor.  (This might be attractive on a machine with very fast
communications.) By inserting the ON clauses, the user has advised against
this strategy, thus trading additional locality for restricted parallelism.
Notice that the ON directive neither requires nor implies the INDEPENDENT
assertion.  In both nests, each iteration of the I loop depends on the
preceeding iteration, but the ON directive can still partition the
computation among processors.  The ON directive does not automatically make
a loop parallel.

Advice to implementors:
"Dimension-based" nesting, as above, will probably be a common case.  The
HOME clauses can be inverted at each level, treating indices from outer
loops as run-time invariants.
End of advice to implementors.

Advice to programmers:
Nested ON directives will tend to have efficient implementations if their
HOME clauses refer to different dimensions of the processors arrangements,
as in the above example.  This minimizes the interaction between the levels
of the loops, simplifying the implementation.
End of advice to programmers.

Consider the following variation on the above example:

        !HPF$ DISTRIBUTE Y(BLOCK,*)

        !HPF$ INDEPENDENT, NEW(I)
        DO J = 1, M
          !HPF$ ON HOME(Y(:,J)) BEGIN
            DO I = 2, M
              !HPF$ ON HOME(Y(I,J))
              Y(I,J) = (Y(I-1,J) + Y(I,J)) / 2
            END DO
          !HPF$ END ON
        END DO

Note that the ON clauses have not changed, except for the name of the
array.  The interpretation is similar to the above, except that the outer
ON directive assigns each iteration of the J loop to all of the processors.
The inner ON directive again implements a simple owner-computes rule.  The
programmer has directed the compiler to distribute a serial computation
across all the processors.  There are a few scenarios where this is more
efficient than parallelizing the outer loop:

1. Parallelizing the outer loop will generate many non-local references,
   since only a part of each column is on any processor. If nonlocal references
   are very expensive (or if M is relatively small), this overhead
   may outweigh any gain from parallel execution.
2. The compiler may take advantage of the INDEPENDENT directive to avoid
   inserting any synchronization.  This allows a natural pipelined execution.
   A processor will execute its part of the I loop for one value of J, then
   immediately go on to the next J iteration.  Thus, the first processor
   will start on J=2 while the second receives the data it needs (from
   processor one) for J=1.  (A similar pipeline would develop in the X
   example above.)

Clearly, the suitability of these ON clauses will depend on the underlying
parallel architecture.

Advice to programmers:
This example points out how ON may improve software engineering.  While the
"value" of HOME(X(I)) will change if X's mapping changes, its intent will
usually stay the same - run the loop "aligned with" the array X.  Moreover,
the form of the clauses is portable, and they simplify experimenting with
alternative computation partitioning.  Both qualities are similar to the
advantages of DISTRIBUTE and ALIGN over low-level data layout mechanisms.
End advice to programmers.

ON directives are particularly useful when the compiler cannot accurately
estimate data locality, for example when the computation uses indirection
arrays.  Consider three variations of the same loop:

        REAL X(N), Y(N)
        INTEGER IX1(M), IX2(M)
        !HPF$ DISTRIBUTE X(BLOCK), Y(BLOCK)
        !HPF$ DISTRIBUTE IX(BLOCK), IY(BLOCK)
        
        !HPF$ INDEPENDENT
        DO I = 1, N
          !HPF$ ON HOME( X(I) )
          X(I) = Y(IX(I)) - Y(IY(I))
        END DO
        
        !HPF$ INDEPENDENT
        DO J = 1, N
          !HPF$ ON HOME( IX(J) )
          X(J) = Y(IX(J)) - Y(IY(J))
        END DO

        !HPF$ INDEPENDENT
        DO K = 1, N
          !HPF$ ON HOME( X(IX(K)) )
          X(K) = Y(IX(K)) - Y(IY(K))
        END DO

In the I loop, each processor runs over its section of the X array.  Only
the reference X(I) is guaranteed to be local.  (If M<>N, then IX and IY
have a different block size than X, and thus a different mapping.)
However, if it is _usually_ the case that X(I), Y(IX(I)), and Y(IY(I)) are
located on the same processor, then this mapping may be the best one
available.  If X(I) and Y(IX(I)) are _always_ on the same processor, then
the RESIDENT clause should be added:
        !HPF$ ON HOME( X(I) ), RESIDENT( Y(IX(I)) )
This will avoid communication setup overhead on most systems, and there is
little chance that the compiler would deduce this automatically.  If both
references to Y are _always_ on the same processor as X(I), then further
improvement is possible and desirable:
        !HPF$ ON HOME( X(I) ), RESIDENT( EVERY=Y )
In the J loop, references IX(J) and IY(J) are always local.  This is the
most common array reference class in the loop, so it minimizes the
number of nonlocal data references in the absence of any special
properties of IX and IY.  It may not evenly balance the load among
processors; for example, if N=M/2 then half the processors will be idle.
As before, if the values in IX or IY ensure that one of the Y references is
always local, a RESIDENT assertion should be added.  In the K loop, only
reference Y(IX(K)) is guaranteed to be local (because Y and X have the same
distribution).  However, the values stored in IX and IY may ensure that
Y(IY(K)) and X(K) always local, a fact that should be noted if true:
  !HPF$ ON HOME( X(IX(K)) ), RESIDENT( Y(IY(K)), X(K) )
Even if the three REAL values are not always, but merely "usually" on the
same processor, this may be a good computation partitioning for both
locality and parallelism.  However, these advantages must be weighed
against the cost of computing this partitioning.  Since the HOME clause
depends on a (presumably large) array of runtime values, substantial time
may be required to determine which iterations are assigned to each
processor.  It should be clear from this discussion that there is no magic
solution for handling complex computation partitionings; the best answer
is usually a combination of application knowledge, careful data structure
design (including ordering of the elements), and efficient compilation
methodology and runtime support.

Advice to implementors:
The K loop is the situation that the inspector strategy described above is
designed for.  If there is an outer loop around any of these examples, and
that loop does not modify the distribution of X or the values of IX, then
a record of each processor's iterations can be saved for reuse.  The cost
is at worst linear in the sizes of the arrays.
End of advice to implementors.

Advice to users:
It is unlikely that any production compiler will generate low-overhead code
for K loop above in the near term.  The difference from previous examples
is that the HOME clause is not a function that can be easily inverted by
the compiler.  Some compilers may choose to execute every iteration on all
processors, testing the HOME clause at run-time; others may pre-compute a
list of iterations for every processor.  Of course, the cost of computing
the list will be substantial.

In practice, one would make all the arrays the same size to avoid some of
the alignment problems above; the example was written this way for
pedagogical reasons, not as an example of good data structure design.
End advice to programmers.

Explicit use of processors arrangements in ON directives is usually
associated with task parallelism.  Many examples can be found there (I
assume...) The following example illustrates how processors can be used
for a one-dimensional domain decomposition algorithm:

        !HPF$ PROCESSORS (PROCS(NP))
        !HPF$ DISTRIBUTE X(BLOCK) ONTO PROCS

        ! Compute ILO(IP) = lower bound on PROCS(IP)
        ! Compute IHI(IP) = upper bound on PROCS(IP)
        DONE = .FALSE.
        DO WHILE (.NOT. DONE)
          !HPF$ INDEPENDENT, NEW( ILO, IHI )
          DO IP = 1, NP
            !HPF$ ON HOME(PROCS(IP)), RESIDENT( X(ILO(IP):IHI(IP)) )
            CALL SOLVE_SUBDOMAIN( IP, X(ILO(IP):IHI(IP)) )
          END DO
          !HPF$ ON HOME(X) BEGIN
            CALL SOLVE_BOUNDARIES( X, ILO(1:NP), IHI(1:NP) )
            DONE = CONVERGENCE_TEST( X, ILO(1:NP), IHI(1:NP) )
          !HPF$ END ON
        END DO

The algorithm divides the entire computational domain (array X) into NP
subdomains, one for each processor.  The INDEPENDENT IP loop performs a
computation on each subdomain's interior.  The processors then collaborate
to update the boundaries of the subdomains and test for convergence.  The
subroutine SOLVE_SUBDOMAIN can use a transcriptive or descriptive
mapping for its array argument, placing it on a single processor.  An ON
block encompassing the entire procedure could then ensure the computation
proceded on a single processor.  Subroutines SOLVE_BOUNDARIES and
CONVERGENCE_TEST may well have their own loops similar to the IP loop, with
similar RESIDENT clauses.  Note that only the lower and upper bound of each
subdomain is recorded; this allows different processors to process
different-sized subdomains.  However, each subdomain must "fit" into one
processor's section of the X array.

Advice to implementors:
The IP loop above is likely to be a common idiom among programmers doing
block-structured codes.  In general, it can be implemented by inverting the
HOME clause as was done above.  In the one-to-one case shown here (probably
very popular with programmers), it can be implemented by assigning the
processor id to the loop index variable and testing the range of the loop
(once).
End of advice to implementors.

Advice to programmers:
Some compilers will propogate the ON information from the caller to the
callee at compile time, and some at run time.  Repeating the ON clause in
the caller and callee will tend to give the compiler better information,
resulting in better generated code.

Again, note the usefulness of RESIDENT clauses in giving the compiler
information.  Few compilers would be able to unravel nontrivial assignments
to ILO and IHI, and no current compiler would even attempt to understand
the comments in the above code fragment.
End of advice to programmers.

Because it is an assertion of act, the compiler can draw many inferences
from a single RESIDENT clause.  For example, consider the following case:

        !HPF$ ALIGN Y(I) WITH X(I)
        !HPF$ ALIGN Z(J) WITH X(J+1)
        
        !HPF$ ON HOME( X(K) ), RESIDENT( X(INDX(K)) )
        X(K) = X(INDX(K)) + Y(INDX(K)) + Z(INDX(K))

The compiler is justified in making the following assumptions in compiling
the assignment statement (assuming it honors both the ALIGN directives and
the ON directive):

* X(K) requires no communication (because of the HOME clause)
* X(INDX(K)) requires no communication (because of the RESIDENT clause)
* Y(INDX(K)) requires no communication (because Y has the same mapping as X)

The compiler cannot make any assumption about INDX(K) or Z(INDX(K)) from
the above code.  There is no indication how INDX is mapped relative to X,
so the ON directive gives no guidance.  Note that the fact that an
expression (here, X(INDX(K))) is local does not imply that its
subexpressions (here, INDX(K)) are also local.  Similarly, Z's mapping does
not determine if Z(INDX(K)) would be local; it indicates that Z(INDX(K)-1)
is local, but that isn't a great help.  If the compiler has additional
information (for example, X is distributed by BLOCK and INDX(K) is not near
a block boundary), it might be able to make additional deductions.

Advice to implementors:
One mark of a good compiler will be that it aggressively propagates RESIDENT
assertions.  This is likely to significantly reduce communication costs.
Note the cases under "Advice to users" below.
End advice to implementors.

Advice to users:
One can expect compilers to differ in how aggressive they are in drawing
these deductions.  Higher-quality compilers will be able to identify more
references as local, and use this information to eliminate data movement.
All compilers should recognize that if an element of one array is local,
then the same element of any other arrays with the same static mapping
(i.e.  arrays ALIGNed together, or with the same DISTRIBUTE pattern and
array size) will also be local.  That is, any compiler should recognize
Y(INDX(K)) in the above example as local.  Dynamically changing array
mappings (i.e. REALIGN and REDISTRIBUTE) will tend to limit such
information and information propagation.
End advice to users.

Another example of drawing further inferences from RESIDENT clauses is the
following:

        !HPF$ ON HOME(PROCS(IP)), RESIDENT( X(ILO(IP):IHI(IP)) )
        DO I = ILO(IP)+1, IHI(IP)-1
          X(I) = (X(I-1) + 2*X(I) + X(I+1)) / 4
        END DO

(Note that this is the construct form of the DO, so the ON clause applies
to all three lines below it.) Here, I is alwas between ILO(IP) and IHI(IP).
Therefore, the two references to X(I) require no communication, since they
always refer to an element of the RESIDENT array section.  Slightly deeper
reasoning reveals that the same is true of X(I-1) and X(I+1).  In short,
the entire DO loop can be executed without communication on PROCS(IP).

Advice to implementors:
Analysis of ranges with symbolic bounds will pay big dividends for
applications such as block-structured CFD codes.  Of course, the expense
of doing this analysis must be weighed against its benefits.  See also
the "Advice to programmers" below.
End advice to implementors.

Advice to programmers:
As with the previous example, one can expect the capabilities of compilers
to differ widely in making these inferences.  Most compilers should
recognize and use compile-time constants in RESIDENT clauses and the
executable code.  Many compilers will extend this to variables that are
invariant within the ON clause and will propogate the bounds of DO loops;
others will use pattern recognition to achieve some of this effect.  Such
pattern recognition suffices to recognize X(I) in the example.  Detailed
reasoning about symbolic values is beyond the capabilities of most
compilers.  For example, determining the range of X(I-1) in the above
example may require symbolic manipulation (or rather aggressive
pattern-matching).
End advice to users.

Consider the statements

        !HPF$ PROCESSORS PROC(NP)
        !HPF$ DISTRIBUTE X(BLOCK)
        ...
        !HPF$ ON HOME(PROC(1)), RESIDENT( EVERY=X )
        X(I) = X(I+2) + X(I) + X(I-2)
        ...
        !HPF$ ON HOME(PROC(2)), RESIDENT( X )
        X(I) = X(I+2) + X(I) + X(I-2)

The two RESIDENT clauses have slightly different meanings.  The EVERY
clause refers to the elements of X actually referenced; thus, it is a
statement about X(I), X(I+2), and X(I-2).  In effect, the first ON clause
asserts that I is at least two elements away from any block boundary.
Without EVERY, the RESIDENT clause applies to the entire array.  In effect,
the second ON directive asserts that all of X is mapped to processor
PROC(2).  This is clearly impossible given the distribution of X, so the
compiler would be justified in warning the programmer.  A different mapping
of X could make the second ON clause true (for example, if X were ALIGNed
to a subsection of a larger array, that subsection might reside entirely on
PROC(2)).  Both ON clauses are valid simultaneously if and only if X is
replicated.

Advice to programmers:
The EVERY clause is typically the right way to assert that all references
to an array are local.
End of advice to programmers.

--============_-1391005225==_============--
---------------------------------------------------------------------------
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>
---------------------------------------------------------------------------