From: "Marc Snir" <[email-masked]>
Date: Tue, 7 Jul 92 10:42:08 EDT

%IO.tex
%Snir
\documentstyle[11pt]{article}
\pagestyle{plain}
\pagenumbering{arabic}
\marginparwidth 0pt
\oddsidemargin  .25in
\evensidemargin  .25in
\marginparsep 0pt
\topmargin   -.5in
\textwidth 6in
\textheight  9.0in

\title{Proposal for IO}
\author{Marc Snir}
%\date{   }

\begin{document}

\maketitle

\section{Summary}

This document proposes to expand the mapping notation of HPF to include
files.  We try to achieve two purposes:
\begin{enumerate}
\item
Allow user control of file layout (file striping) across multiple IO devices.
\item
Allow one unformatted data transfer to access data that is stored across
multiple IO devices.
\end{enumerate}

We present in this document two alternative proposals to achieve these goals.
Both proposals allow to map files onto multiple (abstract) storage nodes.

The first proposal uses HPF align and distribute
mapping directives to allow the mapping of
consecutive file records onto nodes -- records are not split.  Regular
data transfers are now used to access these records, with one
extension: an unformatted data transfer may access more than one record.

The second proposal associates files with templates.  The template
specifies how each file record is distributed across storage nodes.
Align directives
can be further used to realign data items when they are transferred in
READ or WRITE statements.

Both proposals preserve the linear structure of files as sequences of
records.   The first proposal also preserves the order of data items on
sequential files, but may effect the way these items are split into records.
If unformatted data transfer operations are extended to allow for multiple
record
accesses, then the other I/O extensions can be ignored without affecting the
semantics of programs.  The second proposal may affect the order data
items are stored within records.

With both proposals, layout dependent internal file representations are likely
to be used, in order to enhance I/O performance.
It is expected that implementers
will provide tools to convert files, either online or offline, so that a file
created with one mapping (e.g. in a sequential program) can be
accessed with any other mapping (e.g., in a parallel program).

The mapping directives for files will
allow to achieve a better layout of files across multiple I/O devices
(file striping) and/or a better distribution of file caches.
Improved I/O rates via parallel I/O happen when the mapping of a
file matches the mapping of data in memory.

The two proposals are not entirely contradictory; it is possible to combine some
elements from both proposals.

Both proposals require the following restriction on Fortran 90 I/O:.
\begin{quote}
All values needed to determine which entity is specified by an item in an
input or output item list need to be
available before the data transfer operation occurs.
\end{quote}
Currently, they only need to be available before the item is processed.
E.g.,
\begin{verbatim}

READ (15) N, X(N)

\end{verbatim}
is legal Fortran 90 but illegal HPF (or would result in the old value of {\tt
N} be used to index into {\tt X}).

\begin{verbatim}

READ (15) N
READ (15) X(N)
\end{verbatim}
is legal Fortran HPF.

\section{First Proposal}

A Fortran file is a sequence of records.  We treat such file as a 1-D array of
records with LB=1 and infinite UB.  This array can be mapped to a (storage) node
arrangement in a manner analogous to the mapping of an array to a
(processor) node
arrangement.  Files are mapped using the same notation as for array
mapping.  The mapping defines a partition of the file, and each part is
associated with one abstract node.

The mapping of a file to a node arrangement can be
interpreted in two ways:
\begin{enumerate}
\item
The nodes may represent
(abstract) independent storage units, each storing a fixed part of the
file.
\item
The nodes may represent (abstract) independent file caches, with a fixed
association of each cache with a part of the file.
\end{enumerate}

In both cases the file is mapped onto
physical I/O devices so as to allow maximal concurrency for accesses
directed to distinct parts of the file.
If the second interpretation is used, then it is meaningful to align arrays
and files onto the same templates.

We introduce a new filemap object.  Filemaps are, essentially, named files.
They appear where an array names would
appear in a array mapping expression.   An actual file is associated with a
FILEMAP in an OPEN statement.  Filemaps are introduced because files are
not first class objects in FORTRAN (files are not declared).   Also, Filemaps
can have rank $>$ 1, giving more flexibility in the types of mappings that can
be specified.

The following diagram illustrates the mapping

\begin{verbatim}

                                   Node           Physical
File      Filemap     Template   arrangement    storage units  (or caches)
 _           _           _           _               _
|_|-------->|_|-------->|_|-------->|_|------------>|_|

     OPEN        ALIGN    DISTRIBUTE   Implementation
                                         Dependent
\end{verbatim}

\subsection{Node Directive}

We suggest to replace the keyword {\tt PROCESSOR} with the keyword {\tt
NODE}, which is more neutral.  Node arrangements (ex processor arrangements) can
be targets both for file mappings and for array mappings.  Some implementations
may disallow the use of the same node arrangement name as a target both for
array mappings and for file mappings.  In such case an {\tt AFFINITY} directive,
that specifies affinity between io nodes and processor nodes, would be useful.
(Such directive would also be useful to specify affinity between nodes of
different arrangements, e.g. nodes in arrangements of different rank.)

The set of allowable
node arrangements that can be used to map files is implementation dependent --
however, a node arrangement with {\tt NUMBER-OF-IONODES} nodes is always
legal.

The mapping of nodes to
physical storage units is implementation dependent.

For example:

\begin{verbatim}

!HPF$ NODE :: D1(2,4), D2(2,2)
      PARAMETER(NOD=NUMBER-OF-IONODES())
!HPF$ NODE, DIMENSION(NOD) :: D3,D4

\end{verbatim}

\subsection{FILEMAP Directive}

A Fortran file is an infinite  one-dimensional array of records, with LB=1.
A filemap can be thought of as an assumed-size array of records.  This array
is associated with (one-dimensional) files,
using storage association rules.  The filemap name is
used to specify a mappings for files.  The association between a filemap name
and an actual file is effected by the OPEN statement.

A FILEMAP directive declares filemap names.  The syntax is

\begin{verbatim}

filemap-directive   is   FILEMAP [::] filemap-name ( assumed-size-spec )
                                      [, filemap-name (assumed-size-spec ) ] ...
               or  FILEMAP, DIMENSION ( assumed-size-spec ) :: filemap-name-list

\end{verbatim}

An {\it assumed-size-spec} is a specification of the form used for assumed sized
arrays:  All dimensions are specified, with the exception of the last, which is
assumed.  In our case, the last dimension is infinite.  Only
initialization expressions may occur  in this specification (including
expressions that depend on {\tt NUMBER-OF-IONODES}).

For example:

\begin{verbatim}

!HPF$ FILEMAP :: F1(2,4,*)
!HPF$ FILEMAP, DIMENSION(2,2,1:*) :: F2,F3

\end{verbatim}

A FILEMAP directive does not allocate space, neither in memory, nor on disk.

\subsection{File mapping}

ALIGN and DISTRIBUTE statements are used to map FILEMAPs onto nodes.
The syntax is identical to the syntax for processor mappings, with one
restriction:
Block distributions cannot be used for the last (infinite) dimension of
the filemap.

For example:

\begin{verbatim}

!HPF$ DISTRIBUTE (CYCLIC,CYCLIC,*) ONTO D2 :: F2,F3
!HPF$ DISTRIBUTE F1(*,BLOCK,CYCLIC(2)) ONTO D1
\end{verbatim}

Assume that {\tt F1, F2} are the filemaps and {\tt D1, D2} are the node
arrangements from the previous examples.

The first distribute statement
specifies the following mapping for successive records of a file associated with
{\tt F2} or {\tt F3}.

\begin{verbatim}

D2(1,1)         D2(1,2)

1 (1,1,1)       3 (1,2,1)
5 (1,1,2)       7 (1,2,2)
.               .
.               .
.               .

D2(2,1)          D2(2,2)

2 (2,1,1)        4 (2,2,1)
6 (2,1,2)        8 (2,2,2)
.                .
.                .

\end{verbatim}

The second distribute statement
specifies the following mapping for successive records of a file associated with
{\tt F1}.

\begin{verbatim}

D1(1,1)           D1(1,2)          D1(1,3)            D1(1,4)

 1 (1,1,1)       17                33                 49
 2 (2,1,1)       .                 .                  .
 3 (1,2,1)       .                 .                  .
 4 (2,2,1)       20                36                 52
 9 (1,1,2)       25                41                 57
10 (2,1,2)       .                 .                  .
11 (1,2,2)                         .                  .
12 (2,2,2)       28                44                 60
65               81                97                113
.                .                 .                  .
.                .                 .                  .

D1(2,1)            D1(2,2)         D1(2,3)            D1(2,4)

 5 (1,3,1)         21              37                 53
 6 (2,3,1)         .               .                  .
 7 (1,4,1)         .               .                  .
 8 (2,4,1)         24              40                 56
13 (1,3,2)         29              45                 61
14 (2,3,2)         .               .                  .
15 (1,4,2)         .               .                  .
16 (2,4,2)         32              48                 64
69                 85             101                117
.                  .               .                  .
.                  .               .                  .

\end{verbatim}

\subsection{OPEN statement}

A new connection specifier of the form {\tt FILEMAP = filemap-name}
associates a mapping
with the opened file.   If the file exists then the mapping must be one of the
mappings allowed for the file.  The set of allowed file mappings for an existing
file is implementation dependent, but always include the mapping under which
the file was created.  More generally, it will include any mapping where the
file is mapped onto the same storage node arrangement, and with the same
allocations of file records to storage nodes
(different mappings may
result in the same allocation of records to storage nodes).
One choice is to allow any mapping,  with possible degraded performance for
ill matched mappings; another choice is to remap an existing
file when it is opened with a new mapping, either offline or online.   Vendors
are expected to provide implementation dependent mechanisms to exercise such
choices.

The default mapping is implementation dependent.

Only external files can be mapped.

\subsection{Data Transfer Statements}

The optional parameter {\tt NUMREC = scalar-int-expr} is added to the {\tt
io-control-spec}.  This argument is valid only for unformatted data transfers,
and specifies the numbers of consecutive records accessed by the data transfer,
starting from the current record, for sequential access, or the record indicated
by the REC parameter, for direct access.  The default value for NUMREC
is 1.  (Alternative choices are 1 or number of storage storage nodes for
variable length records; and ``as many
as needed to match the length of the item list'', for fixed length records.)
Data transfers are executed following the
usual semantics of Fortran I/O, with successive values in the file matched to
successive elements in the input or output item list.  The number of records
specified by NUMREC is accessed.  The rules for padding, for end-of-record
exceptions and for file positioning are extended accordingly.

\subsection{Extensions}

We may want a {\tt REMAP} statement, to be used instead of the sequence
{\tt CLOSE ... OPEN}, in order to associate a new mapping to an existing
file.

We may want to extend the {\tt INQUIRE} statement to return  file mapping
information (alternatively, we may use the same query intrinsics used to query
array partitions).

A new intrinsics of the form {\tt INDEX(filemap-name, list-of-indices)} would be
handy, as it would allow to address random-access files as multidimentional
arrays.  E.g.

\begin{verbatim}

READ (7, REC = INDEX(F1,3,5) ) A
\end{verbatim}

Each data transfer operation specifies
an association between parts of the file and abstract processor nodes
where from (where to) the data in the record is transferred.
We may want to add additional directives to the OPEN statement to indicate that
this association fulfils certain restrictions for as long as the file is open.
\begin{itemize}
\item
Accesses to a file are {\em independent} if, in all data transfers,
each file part is associated with the same processor node.  An
{\tt INDEPENDENT} argument in the OPEN statement may be used to specify this
condition (which simplifies file caching).
\item
A data transfer is {\em aligned} if each file part is associated with a
unique processor node (is not split among two processor nodes).  We may
use an {\tt ALIGNED} argument in the OPEN statement to specify that all
data transfers are aligned.
(INDEPENDENT implies ALIGNED, but not vice versa).
\end{itemize}

\section{Second Proposal}

A Fortran file is considered to be a sequence of records, each partitioned
into {\em fields}.  While a file is open, the partition of records to
fields is specified using a template (one field per template element).  This
template is distributed onto a storage node arrangement.
The set of fields associated with template elements that map onto a node
form a {\em subrecord}.  This subrecord is mapped onto the corresponding
storage node.   Thus, the record is broken into subrecords, one per storage
node, and the subrecords are broken into fields.  The fields within a
subrecord (numbered in column major order) are not necessarily consecutive;
different subrecords may have different number of fields.

Storage nodes have the same role as in the first proposal.

When a data transfer occur, items on the
input or output list are associated with template elements and, thus,
record fields, using align statements.   An unformatted data transfer access
only one record.  Each subrecord of this record will contain parts of each
item in the input or output list.

The following diagram illustrates the mapping

\begin{verbatim}

                              storage         Physical
I/O item       Template        node      storage units (or caches)
    _              _             _               _
   |_|----------->|_|---------->|_|------------>|_|

         ALIGN       DISTRIBUTE   Implementation
       (per item)    (per file)     Dependent

\end{verbatim}

\subsection{Node Directive}

Same is in previous proposal.

\subsection{IO Templates}

IO templates are used to specify a partition of file records into
fields and a distribution of these fields onto storage nodes.
These templates are declared using the keyword {\tt IOTEMPLATE}.  They are
distributed onto storage node arrangements as regular templates would be.

\subsection{OPEN statement}

A new connection specifier of the form {\tt IOTEMPLATE =
node-arrangement-name} associates a template
with the opened file.  Only external files may be so associated.  For an
existing file, the template distribution and the underlying storage node
arrangement must be included in the (implementation
dependent) set of allowable distributions and arrangements for
this file. This set includes
any template distributed onto the same storage node
arrangement.

Suppose that a file is created with template T1 and next opened
with template T2, where both templates are distributed onto the same node
arrangement.  The file presents in both cases the same sequence of records,
with the same partition of records into subrecords.  However, each access may
specify a different partition of subrecords into fields and a different
numbering of the fields.

A template cannot be redistributed while it is associated with an open file.

\subsection{Unformatted Data Transfer Statements}

Arrays can be mapped onto io templates using ALIGN
directives.  The alignment of an array onto an
io template does not affect its storage; it only affects
the way
this array is transferred from or to a file that is associated with this io
template.  An array can be simultaneously aligned with
several distinct io templates; each alignment controls data
transfers to/from files that are associated with the corresponding io
template.

The execution of a WRITE statement creates one partitioned record,
as described below:
\begin{enumerate}
\item
A copy of each item in the output item list is created, realigned and
redistributed according to the mapping specification for this item at the data
transfer statement.
\item
This copy is stored on the file, with each item stored in the
corresponding fields.  Successive items in the output item
list are stored in succession.
\end{enumerate}

The execution of a READ statement transfers the content of one partitioned
record
into the variables in the input item list, reversing the previous process.

Example

\begin{verbatim}

!HPF$ NODE :: D(2)
!HPF$ IOTEMPLATE, DISTRIBUTE(*, CYCLIC) ONTO D :: T1(2,4)
!HPF$ TEMPLATE, DISTRIBUTE(BLOCK, *) ONTO D :: T2(4,2)
       REAL A(2,4), B(2,4)
!HPF$  ALIGN WITH T1 :: A, B
!HPF$  ALIGN WITH T2(I,J) :: A(J,I), B(J,I)
       OPEN(UNIT = 15, FILE = 'IN', IOTEMPLATE = T1)
       OPEN(UNIT = 16, FILE = 'OUT', IOTEMPLATE = T2)
       READ (15) A, B
       WRITE (16) A, B

\end{verbatim}

First record of file IN:

\begin{verbatim}

subrecord 1: 11 21 31 41 51 61 71 81

subrecord 2: 12 22 32 42 52 62 72 82

\end{verbatim}

Values assigned to arrays A and B by READ operation

\begin{verbatim}

A(1,1) = 11    A(1,2) = 12   A(1,3) = 31    A(1,4) = 32
A(2,1) = 21    A(2,2) = 22   A(2,3) = 41    A(2,4) = 42

B(1,1) = 51    B(1,2) = 52   B(1,3) = 71    B(1,4) = 72
B(2,1) = 61    B(2,2) = 62   B(2,3) = 81    B(2,4) = 82

\end{verbatim}

First record of file OUT after program execution:

\begin{verbatim}

subrecord 1: 11 12 21 22 51 52 61 62

subrecord 2: 31 32 41 42 71 72 81 82

\end{verbatim}

It might be reasonable (but inelegant) to restrict the syntax of
of HPF mapping directives that apply to ionode arrangements (e.g., prohibit the
use of explicit indices in ALIGN directives).

Example:

\begin{verbatim}

!HPF$ NODE, DIMENSION(2) :: D
!HPF$ IOTEMPLATE, DISTRIBUTE ONTO D :: T1(2)
!HPF$ IOTEMPLATE, DISTRIBUTE ONTO D :: T2(2)
       REAL A(2)
!HPF$  ALIGN A WITH T1
!HPF$  ALIGN A(*) WITH T2
       OPEN(UNIT = 15, FILE = 'IN', IOTEMPLATE = T1)
       OPEN(UNIT = 16, FILE = 'OUT', IOTEMPLATE = T2)
       READ (15) A
       WRITE (16) A

\end{verbatim}

First record of file IN before execution:

\begin{verbatim}

subrecord 1: 1

subrecord 2: 2

\end{verbatim}

Values assigned to array A

\begin{verbatim}

A(1) = 1  A(2) = 2

\end{verbatim}

First record of file OUT after execution:

\begin{verbatim}

subrecord 1: 1 2

subrecord 2: 1 2

\end{verbatim}

Example:

\begin{verbatim}

!HPF$ NODE, DIMENSION(2,2) :: D
!HPF$ IOTEMPLATE, DISTRIBUTE ONTO D :: T(2,2)
       REAL A(1,1), B(2,1), C(2,2)
       DATA A, B, C / 11, 21, 22, 31, 32, 33, 34 /
!HPF$  ALIGN WITH T :: A, B, C
       OPEN(UNIT = 16, FILE = 'OUT', IOTEMPLATE = T)
       WRITE (16) A, B, C

\end{verbatim}

First record of file OUT after execution:

\begin{verbatim}

subrecord 1 :   11 21  31

subrecord 2 :      22  32

subrecord 3 :          33

subrecord 4 :          32

\end{verbatim}

Note that subrecords need not have the same length.

\subsubsection{Extensions}

\paragraph{}

As the previous example shows, it is convenient to allow the alignment of an
array of lower rank onto a template of higher rank, assuming additional
implicit dimensions, each with extent one.  Then, the following program would
have the same outcome as the previous one.

\begin{verbatim}

!HPF$ NODE, DIMENSION(2,2) :: D
!HPF$ IOTEMPLATE, DISTRIBUTE ONTO D :: T(2,2)
       REAL A, B(2), C(2,2)
       DATA A, B, C / 11, 21, 22, 31, 32, 33, 34 /
!HPF$  ALIGN WITH T :: A, B, C
       OPEN(UNIT = 16, FILE = 'OUT', IOTEMPLATE = T)
       WRITE (16) A, B, C

\end{verbatim}

We adopt this extension for alignment statements.
\paragraph{}

An implied alignment of the form obtained by a statement
{\tt ALIGN item WITH template}
is assumed for all
items that have not been explicitly aligned.  This require that items have rank
equal or lower than the rank of the template and, for each dimension, extent
equal of lower than the extent of the template in this dimension.
Thus, in the last example, the ALIGN directive can be dropped with no change in
the outcome.
\paragraph{}

An {\em io-implied-do-object} is treated as an array subsection.
Thus
\begin{verbatim}

(B(I,3), I=1,4,2)

\end{verbatim}
is handled as an array of rank one (or higher);

\begin{verbatim}

(B(I,J), C(I), I=1,10), J=1,10)

\end{verbatim}
is handled as an array of rank two (or higher); each entry X(I,J) of this array
consists of a pair of values (B(I,J), C(I)).

Example:

\begin{verbatim}

!HPF$ IONODE, DIMENSION(2,2) :: D
!HPF$ TEMPLATE, DISTRIBUTE ONTO D :: T(2,2)
       REAL A(2),B(2),C(2,2)
       DATA A, B, C / 11, 21, 22, 31, 32, 33, 34 /
       OPEN(UNIT = 16, FILE = 'OUT', IONODE = D2)
       WRITE (16) A, A+3, (B(I), 99, C(I,J), I = 1, 2), J = 1, 2)
       WRITE (16) A, (B(I), 99, C(I,J), J = 1, 2), I = 1, 2)

\end{verbatim}

First record of file OUT after execution:

\begin{verbatim}

subrecord 1 :   11 14 21 99 31

subrecord 2 :         22 99 32

subrecord 3 :         21 99 33

subrecord 4 :         22 99 34

\end{verbatim}

Second record of file OUT after execution:

\begin{verbatim}

subrecord 1 :   11 21 99 31

subrecord 2 :      21 99 33

subrecord 3 :      22 99 32

subrecord 4 :      22 99 34

\end{verbatim}

\paragraph{}

It is convenient to allow alignment directives for items in the input or output
item list to appear in data transfer statements.   The notation will be
elaborated in the next release (if any) of this document.  (Since the alignment
is to the template associated with the file, there is no need to explicitly
name the template.  On the other hand, for the sake of sanity, it is desirable
to avoid align dummies.)

\section{Acknowledgement}

First proposal based on ideas of P. Corbett and S. Baylor.

Second proposal based on ideas of E. Ekanadham and Y. Baransky.

\end{document}