Subject: storage update

From: [email-masked] (Mary E Zosel)
Date: Mon, 24 Aug 92 16:13:43 -0700

Fortran 90 HPF group.
One of the things missing from the storage association proposal
was the syntax for the SEQUENCE, NOSEQUENCE directives.  I have
taken a crack at adding that part, as well as restoring a few
motivating remarks in the discussion session. See draft proposal
below - section II is modified.  I would be happy for someone
to suggest a better syntatic category name than association-name-list.

I believe that other edits were also in the process of happening at
the end of the meeting, but I do not have those.  I am hoping that
Rick and Maureen have the notes on those.

I have a latex version from David Loveman and will be making these
changes in that version, unless someone suggests better alternatives
or corrections.

Does anyone remember other changes that were needed for this
proposal? Did we convince ourselves that the keyword SEQUENCE was
ok for this directive - and does not conflict with the F90
keyword SEQUENCE?  Otherwise, we should use SEQUENTIAL and
NONSEQUENTIAL.

   -mary-

---------
revised proposal - text form -
--------
High Performance Fortran: Storage and Sequence-Association Proposal 1.4

        Modification:   Original ------- R. Swift: March, 1992.
                        Version 1.0 ---  R. Swift: April 10, 1992
                        Version 1.1 ---  R. Schreiber, R. Swift: May 8, 1992
                        Version 1.2 ---  R. Schreiber, R. Swift, K. Kennedy:
						 July 14, 1992
                                (Restricts concept of sequential COMMON, adds
                                aggregate components to nonsequential COMMON.
                                Liberalizes rules on distribution of sequential
					storage.)
                        Version 1.3 ----F90 Group modification
                                (Establish better terminology, additional
			     liberalization for locals, simplify text of prop.)
			Version 1.4 --- modified by M. Zosel: Aug. 24, 1992
				(Expand section with storage association
				 rules to include definition of syntax
				 and expand discussion.)

Introduction

High Performance Fortran (HPF) proposes to map variables across multiple
processors in order to help achieve parallel execution performance
improvements.  FORTRAN 77 and Fortran 90 both specify relationships between the
storage for some data elements (via COMMON and EQUIVALENCE), and the order of
array elements during association at procedure boundaries (via dummy array
arguments).  Otherwise, the location of data is not constrained by the
language.

COMMON and EQUIVALENCE statements constrain the alignment of different data
items based on the underlying model of storage units and storage sequences.
"Storage association is the association of two or more data objects that occurs
when two or more storage sequences share or are aligned with one or more
storage units." (Standard programming language Fortran ISO/IEC 1539:1991 (E)
page 247) The model of storage association is a single linearly addressed
memory, based on the traditional SISD processor.  It is easy to generate
examples where this model can cause gross inefficiencies for architectures
where storage for variables is mapped.

Sequence association refers to the order of array elements that Fortran
requires when an array expression or array element is associated with a dummy
array argument that has an explicit-shape or has an assumed-size.  "The rank
and shape of the actual argument need not agree with the rank and shape of the
dummy argument, " (ISO/IEC 1539:1991 (E) page 174) As with storage association,
sequence association is based on a linearly addressed memory;  it can cause
excessive overhead for mapped arrays.

As an aid to porting Fortran 77 codes, this proposal allows codes that rely on
sequence and storage association to be valid in HPF.  Some modification to
existing Fortran 77 codes *may* be necessary.

PROPOSAL

I.  Definitions

De-1.  An aggregate storage sequence consists of all the storage sequences in a
group of storage sequences that are associated together by EQUIVALENCE
statements or EQUIVALENCE and COMMON statements. A COMMON block explicitly
declared sequential has one aggregate storage sequence consisting of the entire
COMMON block.

De-2.  An aggregate variable group is a collection of variables whose storage
sequences are associated to an aggregate storage sequence.

De-3.  The size of an aggregate storage sequence is the number of storage units
in the storage sequence (as defined in 14.6.3.1 of the standard).

De-4.  Variables (including scalars and arrays of all types, including derived
types) are either sequential or nonsequential.

        A variable is sequential if and only if *any* of the  following holds:

                a) it appears in a sequential COMMON block;
                b) it is a member of an aggregate variable group;
                c) it is an assumed-size array;
                d) it is a component of a sequenced type (i.e. a derived type
		    with the SEQUENCE attribute);
                e) it is declared to be sequential in an HPF directive;

        Sequential variables have the properties of storage association and
	sequence association.

        Nonsequential variables do not have the properties of storage 
	association and sequence association.

De-5: A COMMON block contains a sequence of components. Each component is a
variable that does not appear in any EQUIVALENCE statement or it is an
aggregate variable group.

        COMMON blocks are either sequential or nonsequential.

        A COMMON block is nonsequential if and only if *all* of the following
	hold:
                a) it is not explicitly declared sequential in any program unit
			in which it appears;
                b) every instance of the COMMON block has exactly the same 
		number of components with each corresponding component having a 
		storage sequence of exactly the same size; and
                c) the type, shape, and mapping attributes of any explicitly
		mapped variable aggregate variable group are the same
                in every program unit in which the COMMON block occurs.

        A sequential COMMON block has the properties of storage association and
	sequence association throughout its extent.

        A nonsequential COMMON block does not have the properties of storage
	association or sequence association globally. There may be, however,
	aggregates within the COMMON block, created by EQUIVALENCEs,
 	that do have these properties.

Note that sequential COMMON blocks contain only sequential variables;
nonsequential COMMON blocks contain nonsequential and sequential variables.

De-6.  A variable is mappable or nonmappable. A variable is mappable if it
*may* appear in an HPF alignment and distribution directive,  otherwise it is
nonmappable.

De-7.  A mappable variable is explicitly mapped if it appears in an HPF
alignment and distribution directive within the program unit in which it is
declared,  otherwise it is implicitly mapped.

End of Definitions

Examples:

	IMPLICIT REAL (A-Z)
	COMMON /FOO/ A(100), B(100), C(100), D(100), E(100) 
	DIMENSION X(100), Y(150)

Ex 1: EQUIVALENCE ( A(1), Y(1) )
	Four aggregate variable groups: (A, B), C, D, E 
	Sizes are: 200, 100, 100, 100

Ex 2: EQUIVALENCE ( B(100), Y(1) )
	Three aggregate variable groups A, (B, C, D), E 
	Sizes are: 100, 300, 100

Ex 3: EQUIVALENCE ( E(1), Y(1) )
	Five aggregate variable groups: A, B, C, D, E 
	Sizes are: 100, 100, 100, 100, 150

Ex 4: EQUIVALENCE ( A(51), X(1) ) ( B(100), Y(1) ) 
	Two aggregate variable groups (A, B, C, D), E 
	Sizes are: 400, 100

Ex 5: EQUIVALENCE ( A(51), X(1) ) ( C(80), Y(1) ) 
	Two aggregate variable groups: (A, B), (C, D, E) 
	Sizes are: 200, 300

Ex 6: EQUIVALENCE ( A(1), Y(1) ) ( B(1), Y(51) ) 
	An invalid EQUIVALENCE

II.  Storage Association

II.1 Storage Association Directives

Two directives are defined to allow a user to declare explicitly that a
variable or a common block is to be treated by the compiler as
sequential or nonsequential.  

storage-association-directive is SEQUENCE[::] association-name-list
			      or NOSEQUENCE [::] association-name-list

association-name              is  variable-name
                              or / common-block-name /

II.2 Storage Association Rules
Rule St-1.  A nonsequential array variable is mappable.  A variable in an
aggregate variable group is mappable if its storage sequence is totally
associated with the aggregate storage sequence of the group. Only one variable
in an aggregate variable group may be explicitly mapped.

Rule St-2.  The result variable of an array-valued function that is not an
intrinsic is a nonsequential array.  It may not appear in any HPF SEQUENCE
directive.

II.3 Storage Association Discussion

Using these rules, arrays in COMMON blocks can be be mapped as
long as the components of the COMMON block, as defined by any
EQUIVALENCE statements are the same in every program unit that declares
the COMMON block. Rule St-1 further allows  variables involved in an
EQUIVALENCE statement to be mapped by the mechanism of declaring a 
variable to exactly conver the aggregate variable group and mapping 
that variable.

As the examples below illustrate, there are many ways to use
EQUIVALENCE with COMMON blocks that impact mappability of the
variables in subtle ways. In order to allow maximum optimization
for performance, the default for variables is to consider them
mappable. In order to get correct separate compilation for 
subprograms that use COMMON blocks with different aggregate
components in different subprograms, it will be necessary to
insert the SEQUENCE directive. This is an example of where a
correct FORTRAN 77 or Fortran 90 program will not necessarily
be correct, without modication, in HPF.

In order to protect the user and to facilite portability of older
codes, two implementation options are strongly recommended. First,
every implementation should suppy some mechanism to verify that
the aggregate variable groups in COMMON are the same across every
subprogram if the COMMON contains mapped arrays. This same check
should also verify that identical mappings have been selected for
the variables in COMMON.  Implementations without interprocedural
information can use a link-time check. The second implementation
option recommended is a global mechanism to declare that all
COMMON blocks for a given compilation should be considered
sequential. The purpose of this feature is to permit
compilation of large old libraries or  subprograms where storage
association is known to exist without requiring that the
code be modified to apply the SEQUENCE directive to every
COMMON block.

II.4 Storage Association Examples:
(NB - these examples have been cleaned up in the latex version)

IMPLICIT REAL (A-Z)
COMMON /FOO/ A(100), B(100), C(100), D(100), E(100) 
DIMENSION X(100), Y(150), Z(200), ZZ(300)

Ex 1: EQUIVALENCE ( A(1), Y(1) )
	Aggregate is not mappable.
	Sizes are 200, 100, 100, 100.
	
Ex 2: EQUIVALENCE ( A(1), Y(1) ),  ( A(1), Z(1) )
	First aggregate is mappable only by mapping Z.
	Sizes are 200, 100, 100, 100.

Ex 3: EQUIVALENCE ( B(100), Y(1) ), ( B(1), ZZ(1) )
	Second aggregate is mappable only by mapping Z.
	Sizes are 100, 300, 100.

Ex 4: EQUIVALENCE ( E(1), Y(1) )
	Aggregate is mappable by mapping Y.
	Sizes are 100, 100, 100, 100, 150.

Ex 5: EQUIVALENCE ( A(51), X(1) ) ( C(80), Y(1) ) 
	Aggregates are not mappable.
	Sizes are 200, 300.

Ex 6: EQUIVALENCE ( A(51), X(1) ) ( C(80), Y(1) ) 
	   EQUIVALENCE ( A(1), Z(1) ) ( C(1), ZZ(1) )
	Aggregates are mappable by mapping Z and ZZ.
	Sizes are 200, 300 .

Ex 7:  SUBROUTINE one(a,b,n,c)
	     DIMENSION a(100), b(N), c(:), d(1000)
	!HPF   NOSEQUENCE :: a,b,c,d
To specify variables are nonsequential, but without an providing an explicit
mapping.

Ex 8:   DIMENSION a(100), b(N), c(:), d(1000)
	!HPF	SEQUENCE :: a,b,c,d
	To specify explicitly that a variable is sequential.

Ex 9:   COMMON /two/ e(100), f(10,10), g(10,100,1000)
	!HPF	NOSEQUENCE :: /two/
To specify a COMMON block is nonsequential.

Ex 10:   	COMMON /two/ e(10,10),  g(10,100,1000), h(100), p(100)
		REAL cover(200)
		EQUIVALENCE (cover(1), h(1))
	!HPF	ALIGN e ...
	!HPF	DISTRIBUTE  cover (CYCLIC(2))
Here e is explicitly mapped, g is implicitly mapped, and the aggregate (h, p)
is explicitly mapped.  and /two/ is a nonsequential COMMON block: