Subject: hpff-task: Proposal for task parallelism

From: [email-masked]
Date: Tue, 12 Sep 95 12:08:25 EDT

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

Jaspal and Bwolen
----------------------------------------------------------------------------
Assumptions of functionality available from related features:

1) A way to group processors into subgroups P1, P2, P3 and distribute
   variables onto them, i.e. a1, a2, a3.

2) An ON construct  that directs execution on groups of processors
   P1, P2, P3 etc. for a block of code.

PROPOSAL:

A "task region" is a single entry, single exit region
delimited by (say) TASK REGION  .... END TASK REGION.
A task region can have blocks of code that are directed
to execute ON a processor subgroup. All other code executes
on all available processors, referred to as ALL.

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.

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.

[There are no other access constraints: Code  executing on ALL processors
 has unrestricted  access to all variable locations. A code block directed
 to execute ON a subgroup P has unrestricted access to all variable locations
 mapped to P]

An I/O operation in a code section directed to execute ON a subgroup
may not ``interfere'' with an I/O operation in a code section not
explicitly directed to execute on that subgroup. The interference 
of I/O operations is detailed in Section 4.4 (INDEPENDENT).

For a subroutine call inside an ON block, "all available processors"
are processors in the corresponding subgroup. This is the number that is
used for mapping the parameters of the subroutine. [This part will
become more specific after the syntax etc. of creating subgroups is
decided. There should probably be a system inquiry function for the
number of processors in the current subgroup, if NUMBER_OF_PROCESSORS()
is supposed to return the total number of processors for the program]

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]

Following is one model for accessing variables in a task region:

Accesses to variables owned by other processors is cooperative, i.e.
the owner sends the value, and the user receives it, with one exception -
when code ON a subgroup has to access a variable not mapped to it, it
use a remote fetch/deposit. (It can also cache remote locations locally in
the subgroup for the duration of the execution of the task region since 
computation not ON that  subgroup cannot access it)

EXAMPLE: 2DFFT

Sequential:

      real, dimension(n,n) :: a1, a2

      do while(.true.)
          read (unit = iu, end = 100) a1
          call rowfft(a1)
          a2 = a1
          call colfft(a2)
          write (unit = ou) a2
          cycle
100       continue
          exit
      enddo

Pipelined Data/Task Parallel HPF

	real dimension(n,n) :: a1,a2
        boolean done1
!hpf$   disjoint processor groups P1, P2 (Syntax TBA)
!hpf$   distribute a1(block,*) onto P1
!hpf$   distribute a2(*,block) onto P2
!hpf$   distribute done1 onto P1
                 
!hpf$   TASK REGION
        done1 = .false.
        do while (.true.)
!hpf$       ON HOME(P1) BLOCK 
              read (unit = iu,end=100) a1
              call rowfft(a1)
              goto 101
    100       done1 = .true.
    101       continue
!hpf$       END BLOCK
            
            if (done1) exit
            a2 = a1

!hpf$       ON HOME(P2) BLOCK
               call colfft(a2)
               write(unit = ou) a2
!hpf$       END BLOCK
        enddo
!hpf$   END TASK REGION

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

Processor Group P1:

	real dimension(n,n) :: a1
!hpf$   distribute a1(block,*)
        boolean done1

	done1 = .false.
	do while (.true.)
           read (unit = iu,end=100) a1
           call rowfft(a1)
           goto 101
    100    done1 = .true.
    101    continue
           _send(done1,P2)
           if (done1) exit
	   _send(a1,P2)
	enddo

Processor group P2:

	real dimension(n,n) :: a2
!hpf$   distribute a2(*,block)
        boolean local_done1

	do while (.true.)
           _receive(local_done1,P1)
          if (local_done1) exit 
          _receive(a2,P1)
          call colfft(a2)
          write(unit = ou) a2
	enddo

 COMMENTS:
 
1) The main difference with the simple parallel section/region,
   (or using an INDEPENDENT do loop to achieve parallel sections),
   is that  task regions presented can have code that executes on  ALL
   processors also. If it has no such code, it is similar to parallel
   section/region. However, allowing other code makes this construct more
   general, and implicitly allows pipelining in particular. At the same 
   time, existence of code in ALL can constrain parallelism due to data
   dependence, and in the worst case no task parallelism may exist.

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.
   
---------------------------------------------------------------------------
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: Piyush Mehrotra <[email-masked]>
Date: Mon, 18 Sep 1995 22:36:52 -0400 (EDT)

I would like to propose an extension to Chuck's on-clause proposal
as follows:

simple-on-directive  IS  ON HOME ( home-expr ) [, LOCAL [ (local-var-list)] ]

That is the local-var-list on the LOCAL is optional with the semantics
that if the keyword LOCAL appears with no variable list, then
the programmer is asserting the fact that if the on-block (including 
any procedure calls) is executed on the specified set of processor(s),
all its references will be confined to the set of processor(s) 
and will not access any data outside this set.

Given this extension to the on-clause, I would like to
ask Jaspal if this solves his TASK region issue without introducing
any new syntax. It certainly seems to solve his pipeline problem as
follows:
        real dimension(n,n) :: a1,a2
        boolean done1
!hpf$   disjoint processor groups P1, P2 (Syntax TBA)
!hpf$   distribute a1(block,*) onto P1
!hpf$   distribute a2(*,block) onto P2
!hpf$   distribute done1 onto P1
                 
        done1 = .false.
        do while (.true.)
!hpf$       ON HOME(P1), LOCAL, BLOCK
              read (unit = iu,end=100) a1
              call rowfft(a1)
              goto 101
    100       done1 = .true.
    101       continue
!hpf$       END BLOCK
            
            if (done1) exit
            a2 = a1

!hpf$       ON HOME(P2), LOCAL, BLOCK
               call colfft(a2)
               write(unit = ou) a2
!hpf$       END BLOCK
        enddo

Thus the LOCAL clause without the local var list will imply
at least a part of what I understand Jaspal was proposing with 
his TASK regions.  This proposal does not allow an on-block with 
a LOCAL keyword to access data mapped onto another processor subset.
Question is how important is that?

	- Piyush