Subject: Stor. assoc.

From: Rob Schreiber <[email-masked]>
Date: Tue, 12 May 92 10:29:23 PDT

Rick Swift and I have been working for a couple of weeks to improve
the last draft of the storage/sequence association proposal, based
on our discussions at the April meeting and the comments made by
the full committee.

Key changes:

1.  It is simplified along the lines we discussed at the group meeting

2.  The possibility that pointers, for example, might not be allowed
in data distribution directives leads us to the conclusion that there
are sequential and nonsequential variables and common, and that
there are distributable and nondistributable variables, and that
sequential variables are nondistributable.   We hope this is clear
in the proposal -- let us know if it is or isnt.

3.  Sequence association will require sequential variables in both th
caller and the called routines, and this may require modification to
existing Fortran 77 codes.   Better, we felt, than making variables sequential
by default.

4.  We dont take a position on Meltzer's proposal, which is, in our
new terminology, to allow sequential common blocks to be distributable (as a
whole).

	High Performance Fortran: Storage and Sequence-Association Proposal 1.1

	Modification:   Original ------- R. Swift: March, 1992.
			Version 1.0 ---  R. Swift: April 10, 1992
			Version 1.1 ---  R. Schreiber, R. Swift: May 8, 1992

	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.

	A nonsequential COMMON block does not have the properties of
	storage association or sequence association.

	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, 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) ALL SEQUENTIAL
	VARIABLES ARE NONDISTRIBUTABLE.   The converse may not be
	true.  For example, TARGET variables may be nondistributable,
	but they do not, by virtue of the TARGET attribute, acquire
	sequence and storage association properties.  There are,
	therefore, three and only three kinds of variable:  Sequential
	nondistributable,  nonsequential nondistributable, and
	nonsequential distributable.

	A consequence of Rule St-1 (see Section II) is that sequential
	COMMON blocks contain only sequential variables and nonsequential
	COMMON block contain only nonsequential 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	|
	----------------------------------------------------------------
			|			|   TBD:
	Sequential	|	Sequential,	|   May or may not be
			|  not distributable	|   permitted in EDDs
	----------------------------------------------------------------
			|			|
	Nonsequential	|  Nonsequential,	|   May not appear in
			|  may be distributable	|   EDDs
	----------------------------------------------------------------

	The sequential and distributable attributes are not applicable to
        templates.

	Although it is in the province of WG2/3, we recommend *against*
	requiring that an HPF implementation allow sequential COMMOM
	blocks to appear in EDDs.   This may well be a pessimization
	tool on many architectures, so if provided, it is better left
	as a vendor-specific extension.

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

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

	    a) none of its components is a sequential variable;
	    b) it is not declared sequential in an HPF directive;
	    c) it contains the same number of variables in each scoping
	      unit in which the COMMON block is declared, where the
	      shape and type [and explicit data distribution
	      attributes] of corresponding variables of the sequence
	      match.

	Rule St-3.   A sequential variable may not appear in an HPF ALIGN, 
	REALIGN, DISTRIBUTE, REDISTRIBUTE, or REDISTRIBUTABLE directive.
	(See discussion below for more information.)

	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
	nonsequential variables.    The shape and type of these
	variables must match in all occurrences of the COMMON block.
	Whether the distribution attributes need to be identical (no
	explicit distribution or alignment being one of the
	possibilities) is a problem for Group 2/3.

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

	While it is the province of WG 2/3 to decide this, we believe
	that any explicitly distributed arrays in a nonsequential
	COMMON should be required to have identical, static
	distributions.  If not, any subroutine call could cause a
	redistribution of all arrays in nonsequential COMMON.  The
	same argument leads to the conclusion that global, explicitly
	distributed arrays in MODULES should not be REDISTRIBUTABLE.

	By virtue of Rules St-1(e), and Rule St-3, a variable in a
	sequential COMMON block is nondistributable and may not appear
	in an EDD.

	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)
CHPF	ALIGN TEMP(I) WITH A(1,I)

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

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

	The alternate proposal here causes *all* of A to be copied.
	This is not viable, and the Fortran 77 style used here needs to
	be modified.  (The example is nonstandard due to aliasing, but
	typical nevertheless; the same point applies to codes that are
	legal.)

	End of Discussion of Sequence Association

	END OF PROPOSAL

	Discussion

	Much of the use of COMMON blocks doesn't really care about
	storage association; it's 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.

	Rules for mixing nonsequential and sequential variables in the
	same COMMON block could be made to work, but we doubt that this
	would be good practice.  If we assume the user will rewrite
	applications once to use HPF, the simpler the rules to follow
	are the better.

	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 and f are explicitly distributed, but 
	g is implicitly distributed; two is a nonsequential COMMON block:

                Common /two/ e(100), f(10,10), g(10,100,1000)
	cHPF	ALIGN e ...
	cHPF	ALIGN f ...

	Issues:

	Should argument association between sequential arrays and
	nonsequential arrays be required? In general, this means some
	kind of redistribution across the call and back again.

	If so, redistribution of the dummy can not have a
	redistribution of the actual as a side effect.   We view this
	as the correct approach (WG 2/3) in any case.