Subject: Re: hpff-task: Proposal for task parallelism

From: [email-masked] (Chuck Koelbel)
Date: Wed, 13 Sep 1995 13:13:43 -0500

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

>Here is a modified task parallelism proposal. This proposal is not
>quite formal since the final wording will be somewhat dependent on
>SUBGROUP and ON features which are under development. On the bright
>side, I think it is relatively easy to read and better debugged
>than earlier proposals.

I tend to agree, and will make sure that it gets printed for the next meeting.

A couple details follow...

>The following restrictions must hold for the code inside a task region.
>
>A code block directed to execute ON a subgroup must be a single
>entry single exit region.

Good news, this is part of the ON proposal already.  (Albeit phrased as "no
jumps into or out of the region)

>A code block directed to execute ON a subgroup P may access a variable
>location not mapped to P  only if that variable location is:
>
>a) accessed exclusively in code  directed to execute ON P.
>               OR
>b) not written to in the task region.

Shouldn't the second constraint be
b) not written to by code in another ON block in the task region.
?

Another way of asking this is, "Aren't the sequential regions also in the
task region?"

>COMPILATION/EXECUTION MODEL
>
>The execution model for a subgroup is  to unconditionally execute code
>ON it, unconditionally skip code  ON others, and participate in the
>execution of common code (on ALL processors) as normal data parallel
>code.
>[The access restrictions  guarantee that the results will be consistent
> with pure data parallel execution. A processor group cannot be "invisibly"
> writing to a location being accessed by ALL or another processor group, and
> vice versa]

Right motivation.  But if processor groups can't write to locations read by
ALL, how is data going to flow from group to group?

>The data parallel code on the two processor
>groups will look something like this, after
>the task region is compiled.

Definitely "might" look something like this.  I expect many compilers,
especially those on scalable machines, to produce SPMD code with IF
statements (checking local data, like myproc()) about where the ON
directives are.

>2) No explicit control dependence constraints are required. Inside an ON
>   block, any variable being read (or used for control flow) cannot be written
>   by any other processor group - it can be only written by ALL processors,
>   in which case the control flow from the subgroup must also reach that point.
>
>   Outside an ON block, all processor groups execute all control flow (and
>   other) statements. If a subgroup skips a control construct because it is
>   not involved( i.e. its variables are not involved and there is no code
>   inside the scope of the control construct that is directed to execute
>   ON it) and continues to execute its next ON block, the constraints
>   ensure that it cannot write to a location that is used for managing control
>   flow.

In the following sequence, does P1 execute the GOTO?  It doesn't involve
any data mapped to P1, nor is it directed ON P1.

        !HPF$ DISTRIBUTE A1(BLOCK) ONTO P1
        !HPF$ DISTRIBUTE A2(BLOCK) ONTO P2

        !HPF$ TASK REGION
        IF (A2(2) > 0) THEN
                !HPF$ ON HOME(P2) BLOCK
                ... do something with A2 ...
                !HPF$ END BLOCK
                GOTO 100
        END IF
        !HPF$ ON HOME(P1) BLOCK
        ... do something with A1 ...
        !HPF$ END BLOCK
        100 CONTINUE
        !HPF$ END REGION

I think I know what you mean.  Probably just need to be a little more
careful about the execution model, in particular, what does "normal
data-parallel model" mean?

                                                Chuck

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

---

From: [email-masked]
Date: Thu, 14 Sep 95 15:12:39 -0400

Chuck,

(This refers to  the task parallelism proposal and Chuck's last email
about it, neither of which is included)

You point out some text on access restrictions that seems to be in 
error. I think the restrictions may be more subtle than they appear, 
but the text is what is intended. I will add a general motivation
section along the lines of the next paragraph in the next revision -
please take a look and mail again if you think something needs to be changed.

   TASKING MODEL: Subgroups ``normally'' read and write only to/from the
   variables that are mapped to them. The code in ALL has unrestricted
   access to all variables, and data is exchanged between subgroups by
   copying the variables of one subgroup to the variables of another
   subgroup in the ALL code.

   In some circumstances, a subgroup may want to access a variable NOT mapped
   to it (e.g. a common block). Such access is allowed, but it must not cause
   a  data dependence during the entire duration of the execution of the
   task region. (Even dependence between a subgroup and ALL are not allowed
   since that would imply that when ALL is executing no other subgroup
   can execute as there is no easy way for a compiler to figure out what
   variable a subgroup may access ). A sufficient condition for
   "no dependences" is that such accesses should only be to variables that 
   are ``read only'' in the task region, or ``read and written'' only by code 
   ON only one subgroup.

Other points are well taken and I will add corrections/clarifications in
the next revision.  Yes, the compiled code is just one way
to do it, and meant only for illustration of the task constructs.
Every processor executes control constructs in ALL unless the compiler
can determine that it is not necessary. In general, a GOTO is certainly
executed by everybody. The  "normal data-parallel model" is supposed to
mean that execution follows the normal HPF semantics (some say no such
thing exists :) but I am not going to fix that) without any notion of
task parallelism constraints.

Let me know if there are unresolved things or other comments.

jaspal