Subject: Re: A proposal for EXECUTE-ON directive

From: [email-masked]
Date: Fri, 2 Oct 1992 17:31:52 +0100

>I have sent the following proposal to the FORALL subgroup. Since I 
>strongly believe that the proposed (or alike) feature should be in HPF, I 
>wish you will seriously consider it for inclusion in the first official 
>draft.
>
>
>Tin-Fook
>

I'm not sure that the FORALL group is the right forum for your proposal.
The EXECUTE-ON is a more eleborate form of the "ON HOME xx" type of
annotations as in FORTRAN-D. In fact it is a form of *computation
annotation* as opposite of *data annotation*. As far as I know only the
Booster language is completely orthogonal in this sense. FORTRAN-D only
allows a limited form within a forall. 

As the proposal also relies on templates, I think the distribute-subgroup
is the one who should discuss this. 

There are a few remarks on the proposal: 

1. The execution model of HPFF (not completely approved yet) states: 

-: The code compiled by an HPF compiler ought do no worse than code
compiled using the owner compute rule.

This is more relaxed than saying "it uses the owner compute rule". Your
EXECUTE ON is much more specific towards fixing execution on a specified
processor. 

2. A template is not executed, so one can't say EXECUTE x ON T. Something
like 
EXECUTE_ON_HOME T should be adopted (Since templates are currently no
objects one could even deny this)

3. Adopting EXECUTE x ON on DO loops without any indepence requirements, as

your proposal seems to allow, can yield all kind of intricate
synchronization schemes, when iterations are not independent (or must be
assumed to be dependent). This seems to go further than the first simple
step, which HPFF ought to be.

4. Binding iterations to templates can currently only be done statically,
since 
the current draft does not allow dynamic templates. So iterations
boundaries must be known at compile time. One has to apply the subroutine
trick to allow this, which is not very neat.

5. Allowing EXECUTE x ON on groups of statements, gives a scoping issue, so
there should also be something like END EXECUTE x ON, do undo the
annotation. 

6. Again we have complicated scoping problems. How about this example:

Template T1(N), T2(N)
DO I=1,N
   EXECUTE (I) ON T1(I)
   C(I) = D(I)
  DO J=1,N
    EXECUTE (J) ON T2(J)
    A(I,J) =  A(I,J) + B(I,J) 

This example satisfies the constraint only if by entering the J-loop, the
I-index is dereferenced from the assertion just after the I-loop. Although
logical, it might be confusing to users. However, in the program

Template T1(N), T2(N)
DO I=1,N
   EXECUTE (I) ON T1(I)
   C(I) = D(I)
  DO J=1,N
    A(I,J) =  A(I,J) + B(I,J) 

there is no such dereferencing. 
Now if the J-loop is embedded in a subroutine call, we are in trouble:

Template T1(N), T2(N)
DO I=1,N
   EXECUTE (I) ON T1(I)
   C(I) = D(I)
  DO J=1,N
    CALL FOO(A(I,J),B(I,J))
     
SUBROUTINE FOO(X,Y)
X = X + Y

We cannot compile this subroutine independently. So we could forbid
subroutine calls.

The question then is what kind of restrictions do we have to impose and how
many are there ?

7. The wrap feature of templates will probably be deleted from the draft.
The same thing (shifting data each iteration) can reached by using CSHIFT
or the subroutine trick and making the template as large as the ieteration
space.

With these remarks I hope to have shown that there are many strings
attached to your proposal.

- henk

================================================================
Henk J. Sips

Delft University of Technology
Lorentzweg 1
2628 CJ  Delft, the Netherlands
tel: +31.15.783191                     fax: +31.15.626740
e-mail: [email-masked]

---

From: Tin-Fook Ngai <[email-masked]>
Date: Fri, 2 Oct 92 15:47:05 -0700

Thanks for the comments.  I like to see more discussions and to find a
better solution to the proposed or alike feature.

> EXECUTE ON is much more specific towards fixing execution on a specified

?? (The EXECUTE ON is a directive.)

> objects one could even deny this)

Agree.  I never feel comfortable with the key words I used.  I don't have
objection to "EXECUTE x ON_HOME T".  Any other suggestions are also
welcome.

> step, which HPFF ought to be.

Clearly, the proposed feature is primarily intended for INDEPENDENT DO,
FORALL and other parallel indexed assignments.  Before making the
proposal, I have also thought about ordinary DO loops as you pointed out
here. Code generation seems not a problem: If the user choose to specify
execution location of an iteration of an ordinary DO loops, simple
compilation requires only one synchronication at the end of each iteration
to ensure the DO sequential semantics. This naive compilation looks dumb
but the user may still gain due to the already data distribution.  (A
smarter compiler of course can do a better job but definitely is not
required.)  That is why I don't restrict EXECUTE ON to INDEPENDENT DOs and
make the rule simpler.

> trick to allow this, which is not very neat.

That is the intention of the proposal:  Only static binding is allowed.
Even the loop index is bounded by runtime variable, the binding to
template node is still static.

> there should also be something like END EXECUTE x ON, do undo the

The current proposal seems sufficient in this issue.  The scope for single
statement (FORALL statement, single statement in FORALL construct, and array
assignment statement) is clear.  For groups of statements, EXECUTE ON can
only applies to either the entire body within a FORALL construct or the
entire iteration of a DO loop.

> there is no such dereferencing. 

Good examples.  This bug surely needs to be fixed.  Here is my solution:

- For nested EXECUTE ON directives, only the immediate enclosed EXECUTE ON
  directive is effective.

In the former example, the statement "C(I) = D(I)" will be executed on the
home of T1(I) while the statement "A(I,J) =  A(I,J) + B(I,J)" will be
executed on home of T2(J) for all I.  In the latter case, the entire
I-loop body that includes the DO J loop is executed on the home of T1(I).

> We cannot compile this subroutine independently. So we could forbid

Why can't FOO be compile independently?  The EXECUTE ON directive means
that FOO is called on the home of T1(I).  

> The question then is what kind of restrictions do we have to impose and how

Hope there doesn't need many restrictions for this important feature.

> or the subroutine trick and making the template as large as the ieteration

I and Wolfe discussed the example (Example 6 in the proposal) long before
our revision on the wrap feature.  Sorry for any confusion from this
example.  (However, this example also illustrates the use of wrap in data
distribution -- we should come up with a cleaner solution next meeting.)

> - henk

Appreciate. 

Tin-Fook