From: [email-masked] (C.A. Thole)
Date: Sat, 18 Jul 92 21:51:06 GMT

A Proposal for MIMD Support in HPF
         Clemens-August Thole, GMD I1.T, D-5205 St. Augustin
                        [email-masked]
 
                     Version of June 22, 1992

[1] Abstract

This proposal tries to supply sufficient language support in order 
to deal with loosely sysnchronous programs, some of which have been 
identified in my "A vote for explicit MIMD support".
This is a proposal for the support of MIMD parallelism, which extends
the proposal for !HPF$ INDEPENDENT by Guy Steele. It is more oriented
towards the CRAY - MPP Fortran Programming Model and the PCF proposal. 
The fine-grain synchronization of PCF is not proposed for implementation.
Instead of the CRAY-mechanims for assigning work to processors an 
extension of the ON-clause is used.
Due to the lack of fine-grain synchronization the constructs can be executed
on SIMD or sequential architectures just by ignoring the additional information.

[2] Summary of the current situation of MIMD support as part of HPF

According to the Chuck Koelbel's mail (CRPC) dated March 20th "Working Group 4 -
Issues for discussion" MIMD-support is a topic for discussion within working
group 4. 

Dave Loveman (DEC) has produced a document on FORALL statements (...) which
summarizes the discussion. Marc Snir proposed some extensions. These
constructs allow to describe SIMD extensions in an extended way compared
to array assignments. 

A topic for working papers is the interface of HPF Fortran to program units
which execute in SPMD mode. Proposals for "Local Subroutines" have been made
by Guy Steele (Proposal for local program units in HPF, 25.03.92) and
Marc Snir (Proposal for Local Routines, 16.06.92). Both proposals
define local subroutines as program units, which are executed by all
processors independent of each other. Each processor has only access
to the data contained in its local memory. Parts of distributed data objects
can be accessed and updated by calls to a special library. Any message-passing
library might be used for synchronization and communication.
This approach does not really integrate MIMD-support into HPF programming.

The MPP Fortran proposal by Douglas M. Pase, Tom MacDonald, Andrew Meltzer (CRAY)
contained the following features in order to support integrated MIMD features:
   -  parallel directive
   -  shared loops 
   -  private variables
   -  barrier synchronization
   -  no-barrier directive for removing synchronization
   -  locks, events, critical sections and atomic update
   -  functions, to examine the mapping of data objects.

Steele's "Proposal for loops in HPF" (02.04.92) included a proposal for a 
directive "!HPF$ INDEPENDENT( integer_variable_list)", which specifies
for the next set of nested loops, that the loops with the specified
loop variables can be executed independent from each other.

Chuck Koelbel gave an overview on different styles for parallel loops
in "Parallel Loops Position Paper". No specific proposal was made.

Min-You Wu "Proposal for FORALL, May 1992" extended Guy Steele's 
"!HPF$INDEPENDENT" proposal to use the directive in a block style.

Clemens-August Thole "A vote for explicit MIMD support" contains 3 examples
from different application areas, which seem to require MIMD support for
efficient execution. 

Summary:

In contrast to FORALL extensions MIMD support is currently not well-established
as part of HPF Fortran. The examples in "A vote for explicit MIMD support"
show clearly the need for such features. Local subroutines do not fulfill
the requirements because they force to use a distributed memory programming model,
which should not be necessary in most cases.

With the exception of parallel sections all interesting features
are contained in the MPP-proposal. I would like to split the discussion
on specifying parallelism, synchronization and mapping into three different
topics. Furthermore I would like to see corresponding features to be expessed
in the style of of the current X3H5 proposal, if possible, in order to
be in line with upcoming standards.

[3] Proposal for MIMD support

In order to support the spezification of MIMD-type of parallelism the following
features are taken from the "Fortran 77 Binding of X3H5 Model for 
Parallel Programming Constructs": 

    -   PARALLEL DO construct/directive
    -   PARALLEL SECTIONS worksharing construct/directive
    -   NEW statement/directive

These constructs are not used with PCF like options for mapping or 
sysnchronisation but are combined with the ON clause for mapping operations
onto the parallel architecture. 

[3.1] PARALLEL DO

Explicit Syntax

The PARALLEL DO construct is used to specify parallelism amoung the 
iterations of a block of code. The PARALLEL DO construct has the same
syntax as a DO statement. For an directive approach the directive
!HPF$ PARALLEL can be used in front of a do statement.
After the PARALLEL DO statement a new-declaration may be inserted.

A PARALLEL DO construct might be nested with other parallel constructs. 

Interpretation

The PARALLEL DO is used to specify parallel execution of the iterations of
a block of code. Each iteration of a PARALLEL DO is an independent unit
of work. The iterations of PARALLEL DO must be data independent. Iterations
are data independent if the storage sequence accociated with each variable
are array element that is assigned a value by each iteration is not referenced
by any other iteration. 

A program is not HPF conforming, if for any iteration a statement is executed,
which causes a transfer of control out of the block defined by the PARALLEL
DO construct. 

The value of the loop index of a PARALLEL DO is undefined outside the scope
of the PARALLEL DO construct. 

[3.2] PARALLEL SECTIONS

The parallel sections construct is used to specify parallelism among sections
of code.

Explicit Syntax

        !HPF$ PARALLEL SECTIONS
        !HPF$ SECTION
        !HPF$ END PARALLEL SECTIONS

structured as

        !HPF$ PARALLEL SECTIONS
        [new-declaration-stmt-list]
        [section-block]
        [section-block-list]
        !HPF$ END PARALLEL SECTIONS
   
where [section-block] is

        !HPF$ SECTION
        [execution-part]

Interpretation

The parallel sections construct is used to specify parallelism among sections
of code. Each section of the code is an independent unit of work. A program
is not standard conforming if during the execution of any parallel sections
construct a transfer of control out of the blocks defined by the Parallel
Sections construct is performed. 
In a standard conforming program the sections of code shall be data 
independent. Sections are data independent if the storage sequence accociated 
with each variable are array element that is assigned a value by each section
is not referenced by any other section. 

[3.3] Data scoping

Data objects, which are local to a subroutine, are different between 
distinct units of work, even if the execute the same subroutine.

[3.4] NEW statement/directive

The NEW statement/directive allows the user to generate new instances of 
objects with the same name as an object, which can currently be referenced.

Explicit Syntax

A [new-declaration-stmt] is

       !HPF$ NEW variable-name-list

Coding rules

A [varable-name] shall not be 
-    the name of an assumed size array, dummy argument, common block, function
     or entry point
-    of type character with an assumed length
-    specified in a SAVE of DATA statement
-    associated with any object that is shared for this parallel construct.

Interpretation
 
Listing a variable on a NEW statement causes the object to be explicitly
private for the parallel construct. For each unit of work of the parallel 
construct a new instance of the object is created and referenced with the
specific name.