Subject: new common proposal

From: [email-masked] (Mary E Zosel)
Date: Mon, 20 Jul 92 13:45:20 -0700

f90 Group
Following is the proposal that Schreiber / Kennedy / Swift have been
working on to allow a more relaxed interpretation of the impact of
equivalence on distribution of common blocks. We will review this
proposal in the f90 meeting Thursday AM, so you may want to look
thru it beforehand.  In the minimum, there are a few typo's to fix.
It is possible that they will have a new version for us on Thursday -
  -mary-
----

From: Rob Schreiber <[email-masked]>
Subject: Sequence/storage Proposal

	High Performance Fortran: Storage and Sequence-Association Proposal 1.2

	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, 
                                         Ken Kennedy: July 14, 1992
			    (Restricts concept of sequential COMMON, adds
			    aggregate components to nonsequential COMMON.
			    Liberalizes rules on distribution of sequential
			    storage.)

	Introduction

	High Performance Fortran (HPF) proposes to distribute variables
	across multiple processors in order to help achieve parallel
	execution performance improvements.  Fortran 77 and 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 statments 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 distributed.

	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 is explicit-shaped
	or assumed-sized.  "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
	distributed arrays.

	Because of the large costs involved in supporting storage and
	sequence association on distributed-memory architectures, this
	proposal is based on the idea that neither sequence nor storage
	association applies to distributed applies.   Nevertheless, 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 *will* be
	necessary.

	PROPOSAL

	I.  Definitions

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

	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-2.  Common blocks are either sequential or nonsequential.

	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.

	De-3.  Data distribution attributes are alignment and processor
	distribution of scalars and array elements in a
	distributed-memory system.

	De-4.  A variable is distributable or nondistributable.

	Distributable variables are allowed to appear in HPF explicit
	distribution directives (EDD):  ALIGN, REALIGN, REALIGNABLE,
	DISTRIBUTE, REDISTRIBUTE, and REDISTRIBUTABLE.

	De-5.  An explicitly distributed variable is any distributable
	variable that appears in an HPF EDD that specifies its data
	distribution attributes in the program unit it is declared in.

	De-6.  An implicitly distributed variable is any distributable
	variable that does not derive its data distribution attributes
	from any HPF EDD in the program unit it is declared in.

	End of Definitions

	Discussion of Definitions.

	Every variable will have some distribution.   A programmer may
	indicate preferred distributions using directives only for
	distributable variables.

	An HPF program may contain both sequential and nonsequential
	variables and COMMON blocks.   It may contain distributable and
	nondistributable variables.

	As discussed in Rule St-3 (see Section II) A sequential
	variable may not be aligned nor may it be used to refer to its
	associated template in an align directive.   In most cases, a
	sequential variable may not occur in any EDD at all.   The one
	exception is that a sequential, one-dimensional local variable
	that is equivalenced to an aggregate distribution component of
	a COMMON block may occur in some restricted form of the
	distribution directives.

	There may be other reasons for restricting distributability.
	For example, TARGET variables may be nondistributable, but they
	do not, by virtue of the TARGET attribute, acquire sequence and
	storage association properties.

	A consequence of Rule St-1 (see Section II) is that sequential
	COMMON blocks contain only sequential variables; nonsequential
	COMMON blocks contain nonsequential and sequential variables.

	The compiler will insure that sequence and storage association
	operates correctly for sequential arrays and COMMON blocks by
	limiting the types of implicit distributions that are employed
	for them.

	The situation for COMMON blocks is then:

	----------------------------------------------------------------
	COMMON BLOCK 	|	Component 	|	Whole Block
			|	Variables	|
	----------------------------------------------------------------
			|			|   
	Sequential	|	Sequential,	|   COMMON blocks may not 
			|  not distributable	|   appear inb EDDs
	----------------------------------------------------------------
			|  Sequential		|
			|  aggregates and	|
	Nonsequential	|  nonsequential vbls;	|   May not appear in
			|  distributable	|   EDDs
	----------------------------------------------------------------

	The sequential and distributable attributes are not applicable to
        templates.

	End of Discussion of Definitions

	II.  Storage Association

	Rule St-1.   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 in a COMMON block;
	   c) it occurs in an EQUIVALENCE statement;
	   d) it is an assumed-size array;
	   e) it is a component of a sequenced type (i.e. a structure
              with the SEQUENCE attribute);
	   f) it is declared to be sequential in an HPF directive;

	Rule St-2.  A COMMON block is NONSEQUENTIAL if and only if *all*
	of the following hold:

           a) it is not explicitly declared sequential;

	   b) every instance of it has exactly the same number of
	   distribution components with exactly the same sequence of
	   lengths (see definitions below); and

	   c) the type, shape, and distribution attributes of any
	   explicitly distributed distribution component are the same
	   in every scoping unit in which the COMMON block occurs.

        Definition of "distribution components":

	A distribution component of a COMMON block is a sequence of
	consectutive component variables. A consective pair A, B of
	component variables are in the same distribution component if
	there is a local array variable X equivalenced to one or more
	component variables in such a way that, if the COMMON block
	were a FORTRAN 90 COMMON block, then one or more elements of
	both A and B would be storage associated with elements of X.

        A COMMON block explicitly declared sequential has one distribution 
        component, an aggregate consisting of the entire COMMON block.

Examples:

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

Ex 1: Four distribution components: (A, B), C, D, E 
EQUIVALENCE ( A(1), Y(1) )

Ex 2: Three distribution components: A (B, C, D), E 
EQUIVALENCE ( B(100), Y(1) )

Ex 3: Five distribution components: A, B, C, D, E 
EQUIVALENCE ( E(1), Y(1) )

Ex 4: Two distribution components: (A, B, C, D), E 
EQUIVALENCE ( A(51), X(1) ) ( B(100), Y(1) ) 

Ex 5: Two distribution components: (A, B), (C, D, E) 
EQUIVALENCE ( A(51), X(1) ) ( C(80), Y(1) ) 

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

	A distribution component may consist of a single variable that
	is not storage associated with any local.  All other
	distribution components are "aggregates".  An aggregate
	consists of one or more variables that occur in consecutive
	positions in the COMMON block, and any two adjacent such
	variables are storage associated with some local.

        Definition of "Length" of an aggregate: 

	Let the members of the aggregate have lengths L1, ..., Lk. The
	position in the aggregate of the ith element of the jth
	variable is i + (L1 + ... + L(j-1)).    The length of the
	aggregate will usually be (L1 + ... + Lk).   If, however, an
	equivalenced local runs past the last element of Ak (which
	would have to be the last variable in the COMMON block) or the
	first element of A1 (which would have to be the first variable
	in the COMMON block), the length may be increased by the amount
	by which the local extends past the end of the COMMON block.
	(This occurs in Example 3, below.)

Examples:

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

Ex 1: Lengths are 200, 100, 100, 100
EQUIVALENCE ( A(1), Y(1) )

Ex 2: Lengths are 100, 300, 100
EQUIVALENCE ( B(100), Y(1) )

Ex 3: Lengths are 100, 100, 100, 100, 150
EQUIVALENCE ( E(1), Y(1) )

Ex 4: Lengths are 400, 100
EQUIVALENCE ( A(51), X(1) ) ( B(100), Y(1) ) 

	Rule St-3.   A sequential variable may not appear in an HPF
	ALIGN, REALIGN, or REALIGNABLE directive.  The name of a scalar
	or a one-dimensional sequential local variable, equivalenced
        to an aggregate distribution component of a COMMON block and
        having the same length as the aggregate,  *may* be used to refer
	to the associated template in a DISTRIBUTE, REDISTRIBUTE, or
	REDISTRIBUTABLE directive.  (See discussion below for more
	information.)   A multidimensional sequential variable may not
	appear in any EDD.   A sequential variable whose length is smaller
        than the length of the aggregate to which it belongs may not appear
	in any EDD.

Discussion of Rule St-3:

	A nonsequential array variable in a nonsequential COMMON is
	fully distributable.

	An aggregate in a nonsequential COMMON is a sequential data object.
	It is distributable (with restrictions due to its sequential attribute)
	if there exists a one-dimensional array variable equivalenced to some
	variable in the aggregate, which variable has length exactly equal to
	the length of the whole aggregate.  In this case the entire aggregate
	can be distributed by distributing this one-dimensional variable.

	The scheme described here permits any aggregate in a nonsequential
	COMMON to be distributed by the mechanism of declaring a local,
	one-dimensional variable to exacly cover the aggregate in storage.

Examples:

IMPLICIT DOUBLE PRECISION (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: Lengths are 200, 100, 100, 100
a) Aggregate not distributable
EQUIVALENCE ( A(1), Y(1) )
b) Aggregate distributable by distributing Z
EQUIVALENCE ( A(1), Y(1) )
EQUIVALENCE ( A(1), Z(1) )

Ex 2: Lengths are 100, 300, 100
a) Aggrgate not distributable
EQUIVALENCE ( B(100), Y(1) )
b) Aggregate distributable by distributing ZZ
EQUIVALENCE ( B(100), Y(1) )
EQUIVALENCE ( B(1), ZZ(1) )

Ex 3: Lengths are 100, 100, 100, 100, 150
Aggregate distributable by distributing Y
EQUIVALENCE ( E(1), Y(1) )

Ex 4: Lengths are 200, 300
a) Aggregates not distributable
EQUIVALENCE ( A(51), X(1) ) ( C(80), Y(1) ) 
b) Aggregates distributable by distributing Z and ZZ
EQUIVALENCE ( A(51), X(1) ) ( C(80), Y(1) ) 
EQUIVALENCE ( A(1), Z(1) ) ( C(1), ZZ(1) ) 

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

	End of Storage Association

	Discussion of Storage Association

	A nonsequential COMMON block is a global collection of
	aggregates and nonsequential variables.    The shape and type
	of these must match in all occurrences of the COMMON block.

	A COMMON block that appears as a nonsequential COMMON block in
	one program unit must not appear as a sequential COMMON block
	in another program unit of the same executable program.   When
	two occurrences of the same COMMON block have distribution
	components that differ in number, type, or shape, then it is up
	to the programmer to make all occurrences of the COMMON block
	appear to be sequential.

        In practice there is no difference between:

               COMMON /LINEAR_STORE/ A(100), B(200)
          !HPF SEQUENCE /LINEAR_STORE/

        and

               COMMON /LINEAR_STORE/ A(100), B(200)
               REAL X(300)
               EQUIVALENCE (X(1), A(1))

	and it should be permissible to have these two different declarations
        in different subprograms.    If  X  is explicitly distributed, however,
        then the program is not standard conforming.   In other words, absent an
        explcit distribution for  X,  the implicit distribution of the aggregate
        (A, B) in the second example should be the same as the implicit
        distribution of /LINEAR_STORE/ in the first.   The following third
        declaration is also allowed:

               COMMON /LINEAR_STORE/ A(100), B(200)
          !HPF SEQUENCE /LINEAR_STORE/
               REAL X(300)
               EQUIVALENCE (X(1), A(1))

	A variable in a sequential COMMON block is nondistributable and
	may not appear in an EDD.   A local one-dimensional array
        equivalenced so that it covers the whole COMMON block may occur
	in a DISTRIBUTE directives, but may not be REDISTRIBUTABLE.

	A compiler option (S option) will be provided to make any
	COMMON block with no explicitly distributed component a
	sequential COMMON.   An alternate option (D option) will
        be provided to make any COMMON block with no sequential
	component a nonsequential COMMON.   The standard does
	not specify either as the default.

	There may well be additional restrictions on distributability,
	but these are not related to storage or sequence association.
	For example, it may be determined that POINTER or TARGET
	variables may not be explicitly distributed.  This will *not*
	imply that variables with the pointer or target attributes are
	sequential.   Thus,

	   COMMON /TRIO/  A(100), B, C
	   POINTER, ARRAY(:) :: B
	   REAL(200,3), TARGET :: C

	TRIO may be a nonsequential COMMON block, some of whose
	components may not be allowed in EDDs.

	Character variables *may* be distributed.  See Rule Se-2 below
	for restrictions.

	End of Discussion of Storage Association

	III. Sequence Association

	Rule Se-1.   When an array element or the name of an
	assumed-size array is used as an actual argument, the
	associated dummy argument must be a scalar or a sequential
	array.

	An array-element designator of a nonsequential array may not
	be associated with a dummy array argument.

	Rule Se-2.   A character (scalar or array) variable is
	nonsequential if it conforms to the requirements of Rule
	St-1.   The length of a nonsequential, explicit-length,
	character dummy argument must be the same as the length of the
	actual argument.

	End of Sequence Association

	Discussion of Sequence Association

	Change of the length of character variables across a call, as in

	    character (len=100) one_long_word
	    call webster( one_long_word )

	    subroutine webster(  short_dictionary  )
	    character (len=5) short_dictionary( 20 )

	is legal in Fortran 77 and Fortran 90.   It is allowed provided
        both actual and dummy are sequential.   This may mean that 
        that SEQUENCE directives are needed.

	Correct Fortran 77 (and henced Fortran 90) codes will require
	modification according to this proposal.   Explicit sequential
	directives will be needed in some cases where sequence
	association is required.

	The ideal method for porting such codes will be to use an array
	section in the call statement, which will allow both the actual
	and dummy arrays to be distributable.

	An alternative would have had all dummy arrays sequential
	unless explicitly distributed or made nonsequential by
	directive, as well as all arrays of which an element appears as
	an actual argument.   We hold that this is too conservative and
	makes it easy to live with bad old code and difficult to write
	good new code.

	Another alternative would have allowed sequence association
	with nonsequential explicit-shape dummy arrays; at runtime the
	program would detect that an array element was used as the
	actual argument, and would copy the data into a distributed
	temporary (if INTENT is not OUT) and copy the data back on
	return (if INTENT is not IN).  This, however, requires that all
	the dimensions of the explicit-shape dummy match those of the
	calling routine's array, which will in general cause more data
	to be copied than is operated on.  Consider this Fortran 77
	code.

	SUBROUTINE SWAPROWS(A, LDA, B, LDB, DIM2)
	REAL A(LDA, DIM2), B(LDB, DIM2)
C  LDA and LDB specified to allow proper addressing of elements of rows
	REAL TEMP(DIM2)
!HPF	ALIGN TEMP(I) WITH A(1,I)

	TEMP  = A(1,:)
	A(1,:) = B(1,:)
	B(1,:) = TEMP
	RETURN
	END

	REAL A(1000, 300), B(500, 300)
	CALL SWAPROWS( A(10,1), 1000, B(20,1), 500, 300)

	The alternate proposal here causes *all* of A and B to be
	copied.  This is not viable, and the Fortran 77 style used here
	needs to be modified.

	End of Discussion of Sequence Association

	END OF PROPOSAL

	Discussion

	Many uses of COMMON blocks do not require storage association;
	they are an artifact of having no other way to achieve global
	data prior to Fortran 90.  These rules result in a one-time
	cost of straightening out the COMMON blocks into an admittedly
	restricted style.

	By restricting the use of COMMON and EQUIVALENCE in this
	fashion, Fortran code satisfying these rules is Fortran 90
	compatible.  Many F77 programs will work; we are only
	specifying which ones will not.  Automatic tools to check
	COMMON and generate the allowable forms are fairly
	straightforward.

	Note that these rules encourage users to utilize MODULEs or the
	same COMMON block declaration statements in multiple program
	units via the INCLUDE statement.  Thus the straightforward use
	of HPF data distribution facilities should also help to improve
	the maintainability and reliability of the code.

	Note that the rules of data objects in Modules are simple compared
	to COMMON, since Modules entail comparatively few storage association 
	problems (Equivalence and ENTRY).

	Examples:

	The syntax is illustrative, but the ability to specify each of 
	these attributes is needed.  (The SEQUENCE keyword is derived from 
	the Fortran 90 attribute.)

	To specify a variable is nonsequential but without specifying a 
	distribution:

		subroutine one(a,b,n,c)
		dimension a(100), b(N), c(:), d(1000)
	cHPF	NOSEQUENCE :: a,b,c,d

	To specify explicitly that a variable is sequential:

		dimension a(100), b(N), c(:), d(1000)
	cHPF	SEQUENCE :: a,b,c,d

	To specify a COMMON block is nonsequential:

		Common /two/ e(100), f(10,10), g(10,100,1000)
	cHPF	NOSEQUENCE :: /two/

	To specify explicitly that a COMMON block is sequential:

		Common /two/ e(100), f(10,10), g(10,100,1000)
	cHPF	SEQUENCE :: / two /
	c	If the directive did not appear, /two/ could be
	c	nonsequential by default, depending on the compiler 
        c       (S/D) option.

	In the following, e is explicitly distributed, g is implicitly
        distributred, and the aggregate (h, p) is explicitly distributed.
	/two/ is a nonsequential COMMON block:

                Common /two/ e(10,10),  g(10,100,1000), h(100), p(100)
                real hp(200)
                equivalence (hp(1), h(1))
	cHPF	ALIGN e ...
	cHPF	DISTRIBUTE hp CYCLIC(2)