Subject: Storage/Sequence association proposal

From: [email-masked] (Richard Swift)
Date: Fri, 10 Apr 92 16:04:48 -0700

Here is the proposal from the hpff-F90 subgroup on storage and
	sequence association as refined at the March 31 meeting at NAS.

	I am distributing it to both the [email-masked] and 
	[email-masked] aliases in order to get wider 
	exposure before the April 22 meeting of the subgroup. Please 
	comment and help us clarify any problems so that a draft can 
	be distributed to the entire committee prior to the April meeting. 

	I would especially appreciate someone else developing examples 
	that could clarify any parts that anyone finds confusing or unclear.

	 				- Rick

	High Performance Fortran: Storage and Sequence Association Proposal 1.0

	Introduction

	High Performance Fortran proposes to distribute arrays across
	multiple processors in order to help achieve parallel execution
	performance improvements. Fortran specifies the persistence
	of arrays (via the SAVE attribute), 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.

	The SAVE attribute is not effected by data distribution; it is
	an orthogonal feature.

	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 arrays 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, and can cause large amounts of 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 whenever arrays are
	distributed, none of the properties of storage and sequence 
	association apply to such arrays.

	Proposal

	Definitions

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

	A sequential array is any array which has the properties of
	storage association and sequence association.

	A distributable array is any array which does not have the properties 
	of storage association or sequence association.

	A distributed array is any distributable array which has data
	distribution attributes.

	An explicitly distributed array is any distributable array which
	appears in any HPF data directive that specifies its data
	distribution attributes in the program unit it is declared in.

	An implicitly distributed array is any distributable array that does
	not derive its data distribution attributes from explicit HPF data 
	directives in the program unit it is declared in.

	A sequential COMMON block is any COMMON block which has the 
	properties of storage association and sequence association.

	A distributable COMMON block is any COMMON block which does not have 
	the properties of storage association or sequence association.

	End of Definitions

	An HPF program may contain both sequential arrays and distributed
	arrays.

	- Storage Association

	A distributable array may appear in COMMON statements, but not in
	EQUIVALENCE statements. 

	An array is a sequential array iff the array:
		- appears in an EQUIVALENCE statement, or
		- is an assumed size array, or
		- is a component of a sequenced type (i.e., a structure
			with the SEQUENCE attribute), or
		- appears in a SEQUENCE directive (or via a compiler option), or
		- has the type CHARACTER (because of the relationship
			between CHARACTER arrays and strings in dummy 
			arguments), or
		- appears in a sequential common block (guilt by association)

	An array in a sequential COMMON block may not appear in
	a data distribution directive.

	A COMMON block is a sequential COMMON block unless it can be
	determined to be distributable.

	A COMMON block is a distributable COMMON block if the COMMON block:
		- contains no scalars and no sequential arrays, and
		- contains only distributable arrays, and
		- contains the same sequence of arrays in each
			scoping unit in which the COMMON block is
			declared, where shape, type, and data
			distribution attributes of corresponding
			arrays of the sequence match.
	
	A COMMON block which appears as a distributable COMMON block in
	one program unit must not appear as a sequential COMMON block in
	another program unit of the same executable program.

	CHARACTER arrays may not be distributed.

	The result of an array-valued function is a distributable array, 
	never a sequential array. Thus ENTRY statements are illegal in 
	user written array valued functions. (Alternate ENTRY statements
	cause the results of functions to be storage-associated with
	each other.)

	For a COMMON block to be distributable, any data objects declared 
	in the COMMON block must be either distributable or distributed arrays.

	If one or more arrays in a COMMON block are distributable but
	not explicitly distributed, and the only other objects in the
	COMMON block are distributed arrays, then such arrays are
	implicitly distributed with default data distribution attributes.

	If one or more distributable arrays appear in a distributable
	COMMON block, then every program unit which declares that COMMON 
	block must declare the same number of distribute arrays in that 
	COMMON block. Corresponding arrays in each COMMON block declaration 
	must match in shape, type, and data distribution attributes.
	(Note the name of an array in COMMON is a local name, so they may
	be different in each COMMON declaration; however, all other
	attributes of the array must correspond.)

	- Sequence Association

	An assumed-size array may not be a distributed array, or 
	associated with a distributed array. 

	An array element designator as an actual argument may not
	be associated with a distributed dummy array.

	An array element designator of a distributable array may not
	be associated with a dummy array.

	End of Proposal

	Discussion

	By restricting the use of COMMON and EQUIVALENCE in this fashion, 
	Fortran code satisfying these rules is still Fortran 77 compatible. 
	Thus the restriction for users is how the language is used with HPF. 
	Many f77 programs will work; we are only specifying which ones will 
	not. These seem to be reasonable restrictions to impose, and 
	automatic tools to check COMMON and generate the allowable forms 
	are fairly straightforward.

	Note that these rules encourage users to utilize 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 (which is still Fortran 77 compatible).

	Rules of mixing scalars and arrays in COMMON could be written up 
	and made to work, as could complicated rules for mixing
	distributed and sequential arrays in the same COMMON block,
	but why bother? If we assume the user will rewrite applications
	(once only we hope) to use HPF, the simpler the rules to follow
	are the better. Making these rules more complicated to handle more
	cases is self-defeating in the long run; KISS. 

	In essence, this proposal provides for two kinds of COMMON: one
	with storage association, and one without. Compilers should be able 
	to distinguish the two without difficulty.

	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 (which happens still to be Fortran 77 standard 
	conforming). Eliminating the problem for distributed arrays is 
	better than trying to propagate storage association in HPF code.

	All the argument passing of Fortran 77 works fine as long as
	actual arguments and dummy arguments are sequential arrays.
	If either but not both are distributed arrays, the rules for
	matching them up will require some kind of redistribution of data.

	The standard also describes storage association in the
	result of functions containing multiple ENTRY statements. This
	is a minor point. For scalar valued functions, this is fine.
	In HPF the result of an array-valued function should always be 
	a distributed array, never a sequential array. Thus ENTRY statements 
	are effectively illegal in user written array valued functions.

	In the absence of explicit data distribution directives,
	any distributable array may be implicitly distributed array by default. 
	The distribution chosen is left to the processor. 

	CHARACTER arrays may not be distributed. Sequence association
	rules are especially ugly for CHARACTER. As a simplification to
	vendors, it is reasonable not to require them to implement
	a feature which is infrequently important. Note by adding such
	a restriction now, it is trivial to remove it later if you wish
	to, such as an added feature in your product.

	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 an array is distributed but without specifying the 
	distribution:

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

	To specify a COMMON block is distributed without specifying the
	distribution:

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

	To specify explicitly that an array is NOT distributable:

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

	To specify explicitly that a COMMON block is NOT distributable:

		Common /two/ e(100), f(10,10), g(10,100,1000)
	cHPF	Sequence :: / two /
	c	If the directive did not appear, /two/ would be
	c	distributable by default.

	In the following, e and f are explicitly distributed, but 
	g is implicitly distributed; two is a distributed 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
	distributed arrays be required? In general, this means some
	kind of redistribution across the call and back again.

	Pointer arrays in F90 have a lot of implementation similarity
	to the dynamic redistribution of allocatable arrays.
	The cost of referencing both constructs is complicated by
	not knowing at compile time where the data resides. Thus the
	most general case addressing must be used for distributed objects.
	Should pointer arrays not be supported by the base level of HPF?

---

From: [email-masked]
Date: Tue, 21 Apr 92 10:52:45 -0400

> 	sequence association as refined at the March 31 meeting at NAS. ...

Basically, I think the proposal is very clear and well thought out.  I do have
a couple of comments on a few detailed points, however, that I thought I ought

> 	implicitly distributed with default data distribution attributes.

As I commented previously to hpff-distribute in another context, I feel that
the HPF proposal shouldn't imply that there are any kind of
implementation-wide "default data distribution attributes."  An implementation
might well have such a set of defaults, but it should also be allowed to use
different "defaults" in different cases, however it might be able to determine
would be best.  It should even, in my opinion, be allowed to use different
mappings at different times for the same object, if no explicit distribution
is specified, whenever that seems like the way to generate the most efficient
program.

In other words, any time that no explicit distribution attributes are
specified, the compiler has free license to optimize the program in any way it
wants, as long as the semantics of the program are preserved.

> 	kind of redistribution across the call and back again.

I would say yes, and since all proposals being considered by hpff-distribute
have the potential for argument redistribution across calls, I don't think it
would be revolutionary to allow such redistribution here.  And I predict that
not allowing such redistribution would create a significant nuisance for
programs that use sequential arrays.

> 	Should pointer arrays not be supported by the base level of HPF?

In Digital's proposal to the January HPFF meeting, we proposed that it would
be illegal to specify any alignment or distribution for objects with the
POINTER or TARGET attributes.  This approach avoided a bunch of questions
about whether the distribution attributes of pointers would have to match those
of the pointer's targets, etc., and it wasn't clear to us whether using
pointers to point to explicitly distributed objects was going to be a very
important capability anyhow.  The proposal would allow a compiler that has a
simple default mapping for objects without explicit distribution attributes to
just use those defaults for pointers and their targets, while leaving the door
open for cleverer compilers to do cleverer things some day.     -Bert