Subject: One more time

From: Rob Schreiber <[email-masked]>
Date: Tue, 1 Dec 92 09:28:09 PST

Dear fellow perfectionists:

I have made some editorial "improvements"  to the sequence/storage
chapter (okay, i know that you'll be the judges of that).   

In the draft that follows, removed material is set off by triple
square [[[bracelets]]] brackets, and added material {\bf such as this}
is in bold.   No need to print it -- there are only a few changes.
Just hunt for '[[[' and '{\bf' with your editor.

See you next week.  Rex, how cold is it there?

Rob

%  Edits by RSS Dec 1.
%sequence.tex

%Version of Oct. 23, 1992 - R. Swift, MasPar Computer Corporation, R.
%Schreiber, RIACS, and K. Kennedy, Rice University, M. Zosel, LLNL, M Hoffert, HP.

\chapter{Sequence and Storage Association\protect\footnote{Version of
Oct. 23, 1992 - R. Swift, MasPar Computer Corporation, R. Schreiber,
RIACS, and K. Kennedy, Rice University, M. Zosel, LLNL, M. Hoffert, HP.}}
\label{sequence}

\section{Introduction}

High Performance Fortran (HPF) allows the mapping of variables across
multiple processors in order to improve parallel performance.  FORTRAN
77 and Fortran 90 both specify relationships between the storage for
some data objects with COMMON and EQUIVALENCE, and the order of array
elements during association at procedure boundaries 
{\bf between actual and dummy arguments}.
[[[(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.  

{\bf Italics added.}
\begin{quotation}
{\em 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) section 14.6.3.1.

\end{quotation}
The model of storage
association is a single linearly addressed memory, based on the
traditional single address space, single memory unit architecture.
This model can cause severe inefficiencies on 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]]].

{\bf Italics added.}
\begin{quotation}
{\em 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) section 12.4.1.4.

\end{quotation}
As with storage association, sequence association 
is [[[based on]]] {\bf a natural concept only in systems with} 
a linearly addressed memory.

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

\section{Storage Association}

\subsection{Definitions}

\label{sequence-defs}

\begin{enumerate}

\item COMMON blocks are either {\it sequential}  or {\it nonsequential},  
as determined by either explicit directive or compiler 
default.  A sequential COMMON block has a single common 
block storage sequence. (5.5.2.1)

\item An {\it aggregate variable group} 
is a collection of variables whose storage
sequences are parts of a single storage sequence.

Variables associated by EQUIVALENCE statements 
or by a combination of EQUIVALENCE and COMMON statements 
form an aggregate variable group. The variables of a 
sequential COMMON block form a single aggregate variable 
group.

\item The {\it size} of an aggregate variable group is the number of storage 
units in the group's storage sequence (14.6.3.1).

\item If there is a member in an aggregate variable group 
whose storage sequence is totally associated (14.6.3.3) with 
the storage sequence of the aggregate variable group,  
that variable is called an {\it aggregate cover}.

\item  
\label{seq-var}
Variables are either {\it sequential} or {\it nonsequential}.
A variable is {\it sequential} if and only if any of the 
following holds:

\begin{enumerate}

\item it appears in a sequential COMMON block;

\item it is a member of an aggregate variable group;

\item it is an assumed-size array;

\item it is a component of a [[[sequence type (i.e. a]]] derived type with
the SEQUENCE attribute;

\item it is declared to be sequential in an HPF SEQUENCE directive;

\end{enumerate}

         A sequential variable can be storage associated or 
sequence associated;  nonsequential variables cannot.

\item A COMMON block contains a sequence of {\it components}.  Each 
component is either an aggregate 
variable group, or a variable that is not a member of any
aggregate variable group. 
Sequential COMMON blocks contain a single 
component. 
Nonsequential COMMON blocks may 
contain several components that may be
nonsequential or sequential variables or aggregate variable groups.

\item A variable is {\it explicitly mapped}
if it appears in an HPF
alignment or distribution directive within the scoping unit in which it is
declared;  otherwise it is {\it implicitly mapped}.

\end{enumerate}

\subsection{Examples of Definitions}

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

!Example 1:
EQUIVALENCE ( A(1), Z(1) )
!Four components: (A, B), C, D, E 
!Sizes are: 200, 100, 100, 100

!Example 2:
EQUIVALENCE ( B(100), Y(1) )
!Three components A, (B, C, D), E 
!Sizes are: 100, 300, 100

!Example 3:
EQUIVALENCE ( E(1), Y(1) )
!Five components: A, B, C, D, E 
!Sizes are: 100, 100, 100, 100, 150

!Example 4:
EQUIVALENCE ( A(51), X(1) ) ( B(100), Y(1) ) 
!Two components (A, B, C, D), E 
!Sizes are: 400, 100

!Example 5:
EQUIVALENCE ( A(51), X(1) ) ( C(80), Y(1) ) 
!Two components: (A, B), (C, D, E) 
!Sizes are: 200, 300

!Example 6:
EQUIVALENCE (Y(100), Z(1))
!  One aggregate variable group (Y, Z), not involving the COMMON block.
!  Size is 299

!Example 7:
CHPF$ SEQUENCE /FOO/
!  The COMMON has one component, the AVG consisting of A, B, C, D, and E
!  Size is 500
                                                             \EDOC
% 
% EQUIVALENCE ( A(1), Y(1) ) ( B(1), Y(51) ) 
% !An invalid EQUIVALENCE
\noindent
In Examples 1--6, common block /FOO/ is nonsequential.   Aggregate variable groups
are shown as components in parenthesess.  Aggregate covers are Z in Example 1 and
Y in Example 3.

\subsection {Storage Association Directives}

A SEQUENCE directive is defined to allow a user to declare explicitly that a
variable or a COMMON block is to be treated by the compiler as
sequential.    
(COMMON blocks are by default nonsequential.  Variables are
nonsequential unless Definition 5 applies.)

					\BNF
storage-association-directive \IS SEQUENCE [[::] association-name-list]

association-name              \IS   variable-name
                                             \OR /  common-block-name / 
					\FNB

\subsection {Storage Association Rules}

\begin{enumerate}
\item A {\it storage-association-directive} with an empty 
{\it association-name-list}  is treated as if it contained the name 
of all {\it association-name}s in the scoping unit.  

\item An aggregate cover may be explicitly mapped. If more 
than one aggregate cover exists for the aggregate variable 
group, only one may be {\bf explicitly} mapped.

\item The only sequential variables that may be explicitly mapped are scalar or 
one-dimensional variables.  Multi-dimensional sequential variables may 
not be {\bf explicitly} mapped.

\item No explicit mapping may be given for an 
assumed-size dummy argument array.

\item No explicit mapping may be given for a component of a user-defined type 
having the SEQUENCE attribute.

\item If a COMMON block is {\it nonsequential}, then all of the
following must hold:

\begin{enumerate}

\item every occurrence of the COMMON block has exactly the same number of
components with each corresponding component having a storage sequence
of exactly the same size;

\item if a component is a nonsequential variable in {\it any}  
occurrence of the COMMON block, then it must be 
nonsequential with identical  type, shape, and mapping 
attributes in {\it every}  occurrence of the COMMON block;

\item if a component is sequential and explicitly mapped
(either a variable or an aggregate variable group with 
an explicitly mapped aggregate cover) 
in any occurrence of the COMMON block, 
then it must be sequential and explicitly mapped with identical
and mapping attributes in {\it every}  
occurrence of the COMMON block.    In addition, the type and shape 
of the explicitly mapped variable must be identical in all occurrences.

\end{enumerate}

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

\end{enumerate}

\subsection{Storage Association Discussion}
Under these rules, variables in a COMMON block can be mapped as
long as the components of the COMMON block are the same in every scoping 
unit that declares
the COMMON block. Rule 2 also allows  variables involved in an
EQUIVALENCE statement to be mapped by the mechanism of declaring a
one-dimensional array to exactly cover the aggregate variable group and mapping
that array.

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
scoping units that use COMMON blocks with different aggregate
variable groups in different scoping units, it will be necessary to
insert the HPF SEQUENCE directive. This is an example of where a
correct FORTRAN 77 or Fortran 90 program will not necessarily
be correct, without modification, in HPF.

In order to protect the user and to facilitate portability of older
codes, two implementation options are strongly recommended. First,
every implementation should supply some mechanism to verify that the
type and shape of every mappable array and the sizes of
aggregate variable groups in a COMMON are the same in every
scoping unit if the COMMON is not declared to be sequential. 
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 unless declared
otherwise. 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 HPF
SEQUENCE directive to every COMMON block.

Since an HPF program is nonconforming if it specifies any mapping
that would cause storage units to be mapped onto more than one
abstract processor, this puts a constraint on the  sequential variables
and aggregate covers that can be mapped.  In particular, programs
[[[which might cause]]] {\bf that direct} 
double precision or complex arrays to be mapped
so [[[they]]] {\bf that array elements} 
are split because of some EQUIVALENCE statement {\bf or COMMON block
layout} are nonconforming. 

\subsection{Examples of Storage Association}

                                                             \CODE
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)

EQUIVALENCE ( A(1), Y(1) )
!Aggregate variable group is not mappable.
!Sizes are 200, 100, 100, 100.
	
EQUIVALENCE ( B(100), Y(1) ), ( B(1), ZZ(1) )
!Aggregate variable group is mappable only by mapping ZZ.
!ZZ is an aggregate cover for B, C, D, and Y.
!Sizes are 100, 300, 100.

EQUIVALENCE ( E(1), Y(1) )
!Aggregate variable group is mappable by mapping Y.
!Sizes are 100, 100, 100, 100, 150.

COMMON /TWO/ A(20, 40), E(10,10), G(10,100,1000), H(100), P(100)
REAL COVER(200)
EQUIVALENCE (COVER(1), H(1))
!HPF$	SEQUENCE A
!HPF$	ALIGN E ...
!HPF$	DISTRIBUTE COVER (CYCLIC(2))
                                                             \EDOC
\noindent
Here A is sequential and implicitly mapped, 
E is explicitly mapped, G is implicitly mapped, 
the aggregate cover  of the aggregate variable group (H, P) is explicitly mapped.
/TWO/ is a nonsequential COMMON block.   

  In another subprogram, the
following declarations may occur:

                                                             \CODE
COMMON /TWO/ A(800), E(10,10), G(10,100,1000), Z(200)
!HPF$   SEQUENCE A, Z
!HPF$	ALIGN E ...
!HPF$	DISTRIBUTE Z (CYCLIC(2))

                                                             \EDOC
\noindent
There are four components of the same size in both occurrences.  
Components one and four are sequential.   Components two and four are
explicitly mapped, with the same type, shape and mapping attributes.

The first component, A, must be
declared sequential in both occurrences because its shape is different.
It may not be explicitly mapped in either because it is not
one-dimensional or scalar in the first.  

E and G must agree in type and
shape.  E must have the same explicit mapping and G must have no
explicit mapping in both occurrences, since they are nonsequential
variables.  

The fourth component must have the same explicit mapping in both occurrences, 
and must be made sequential explicitly in the second.

\section{Argument Passing and Sequence Association}

For actual arguments in a procedure call, Fortran 90 allows an array element
(scalar) to be associated with a dummy argument that is an array.  
It furthermore allows the rank of a dummy argument to differ from the rank of
the corresponding actual array argument, in effect reshaping the actual via the
subroutine call.
Storage
sequence properties of Fortran  are used to identify the values of the dummy. 
This feature, carried over from Fortran 77, has been widely used to pass
starting addresses of subarrays, rows or columns of a larger array to
procedures.  For HPF arrays that are potentially mapped across processors,
this feature is not {\bf fully} supported.

\subsection{Sequence Association Rules}

\begin{enumerate}

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

\item  When an actual argument is an array
and the corresponding dummy argument  [[[which]]] differs from [[[that of]]] 
the actual
argument in shape, then the dummy must be declared sequential and the actual 
must be an entire, sequential array.

\item  A variable of [[[default]]] type character (scalar or array)
[[[variable]]] is nonsequential if it conforms to the requirements of
Definition~\ref{seq-var} of Section~\ref{sequence-defs}.  
[[[The size of a
nonsequential, explicit-length, character dummy argument must be the
same as the size of the actual argument.]]]
{\bf If the length of an explicit-length character dummy argument differs from the
length of the actual argument, then both the actual and dummy arguments must be
sequential.}

\end{enumerate}

\subsection{Discussion of Sequence Association}

Correct Fortran 77 (and hence Fortran 90) codes might require modification
in HPF.   Explicit HPF SEQUENCE directives may be 
needed in some cases where sequence association exists in order for 
arrays to be mappable.

When the rank of the dummy argument and its associated actual differ, the 
actual may not be an expression.
There is no HPF mechanism for declaring that
the value of an array-valued expression is sequential.   
In order to associate such an expression as an actual
with a dummy of different rank, the actual must first be assigned to 
a named array variable that is forced to be sequential according to
Definition~\ref{seq-var} of Section~\ref{sequence-defs}.

The ideal method for porting such codes will be to use an array section as the 
actual argument, which will allow both the  dummy and its associated 
actual `to be mappable.

Examples:
Given

                                                             \CODE
SUBROUTINE HOME (X)
DIMENSION X (20,10)
                                                             \EDOC
By rule 1
                                                             \CODE
CALL HOME (ET (2,1))
                                                             \EDOC
is legal only if X is declared sequential in HOME {\bf and ET is
sequential in the calling routine}.

Likewise, by rule 2
                                                             \CODE
CALL HOME (ET)
                                                             \EDOC
requires either that ET and X are both sequential arrays or that ET is 
dimensioned exactly the same as X.

Special consideration for CHARACTER:
Change of the length of character variables across a call, as in

                                                             \CODE
            CHARACTER (LEN=100) one_long_word
            CALL webster ( one_long_word )

            SUBROUTINE webster(  short_dictionary  )
            CHARACTER (LEN=5) short_dictionary ( 20 )
                                                             \EDOC

\noindent
is conceptually legal in Fortran 77 and Fortran 90.   It is allowed provided
both actual and dummy are sequential.   This may mean that !HPF$ 
SEQUENCE directives are needed.
%\end{document}