From: "Marc Snir" <[email-masked]>
Date: Mon, 31 Aug 92 13:42:27 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 I/O devices.
\item
Allow efficient transfer of distributed arrays to/from
striped files, with no sequential bottlenecks.
\end{enumerate}

To achieve the first goal,
we propose to allow HPF
mapping directives to control the association of
consecutive file records to I/O nodes.
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.
These directives control the physical layout of sequential files, but do not
alter the logical organization of sequential files.
Regular
data transfers can be used to access these records.  The semantics of
Fortran 90 I/O operations is left unchanged, and the representation of data on
the file does not depend on its distribution, or the distribution of the
arrays that were written onto it.

To achieve the second goal,
we propose to add
parallel I/O operations that allow to optimize the transfer distributed arrays
onto striped files.  The representation of data written using a parallel
I/O operation may be different from the data representation resulting from a
a sequential write, and may depend on
the file mapping and the mapping of the arrays that were written on it.
In particular, an array
transfered in one parallel write operation may be split into multiple
records, stored on distinct I/O nodes.
Data written with a parallel write operation can be read back with a
parallel read operation, onto a similarly distributed array.  However data
written with a parallel write cannot be read back with a sequential write,
and data written with a sequential write cannot be read with a parallel
read.

The two proposals are independent:  parallel read/writes can be directed to
any file, and files distributed onto multiple I/O nodes can be accessed via
sequential reads/writes.  High performance I/O will be achieved when
parallel reads and writes are used to access distributed files, and the
distribution of the file matches the distribution of the I/O items in
memory (or when the compiler can translate a sequential I/O operation into
an equivalent parallel I/O operation).

The second part of our proposal borrows some
features form the parallel I/O proposal of Viena Fortran \cite{vienaio}.
Unlike them, we do not propose to distinguish parallel files from sequential
files.

\section{File mapping}

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.

Implementations may restrict the use of the FILEMAP connection specifier to
files that are open for direct access (i.e., fixed size record files).

\section{Parallel Data Transfer}

The READ, WRITE, CLOSE, INQUIRE, BACKSPACE, ENDFILE, REWIND statements can be
used to access distributed files; there are no changes in the syntax or
semantics of these statements.

PREAD and PWRITE statements are
added to allow efficient input or output of distributed arrays.
The PREAD and PWRITE statements have the same syntax as unformatted
I/O statements with READ or WRITE, respectively; they are semantically
different.  The data representation created on a file by a PWRITE statement
may be different from the data representation that obtains if PWRITE is
replaced by WRITE.  In particular,
whereas an unformatted WRITE statement will create
a single record (stored on one I/O node), a PWRITE
statement may create multiple records, possibly on multiple I/O nodes.
Whereas an unformatted READ statement
accesses a unique record, a PREAD statement may access multiple records.

If a a PWRITE statement was used to write a list of output items on a file, then
a PREAD that starts at the same point in the file, and has a compatible list of
input items, will return the values that were written.   Two lists of items are
compatible if the corresponding items in each list occupy the same number of
storage units and have compatible mappings (informally, if the distribution of
entries onto abstract processors is the same).

Examples

The program below exchanges the values of arrays {\tt A} and {\tt B}.  The
exchange is legal because the arrays are compatible.

\begin{verbatim}

REAL, DIMENSION(1000,1000) :: A, B
ALIGN A WITH B
...
OPEN(UNIT = 15, ACTION = READWRITE)
PWRITE (UNIT = 15) A, B
REWIND (UNIT = 15)
PREAD (UNIT = 15) B, A
\end{verbatim}

The behavior of the program below is undefined.  More than one record
could have been created by the PWRITE statement, so that the BACKSPACE
statement does not necessarily return the file position to where it was before
PWRITE executed.

\begin{verbatim}

REAL, DIMENSION(1000,1000) :: A, B
ALIGN A WITH B
...
OPEN(UNIT = 15, ACTION = READWRITE)
PWRITE (UNIT = 15) A, B
BACKSPACE (UNIT = 15)
PREAD (UNIT = 15) B, A
\end{verbatim}

The behavior of the program below is undefined, since the two arrays {\tt A} and
{\tt B} don't have compatible distributions.

\begin{verbatim}

REAL, DIMENSION(1000,1000) :: A, B
DISTRIBUTE A(BLOCK,BLOCK)
DISTRIBUTE B(CYCLIC, CYCLIC)
...
OPEN(UNIT = 15, ACTION = READWRITE)
PWRITE (UNIT = 15) A, B
REWIND (UNIT = 15)
PREAD (UNIT = 15) B, A
\end{verbatim}

Data written by a WRITE statement cannot be read with PREAD, and data
written with PWRITE cannot be read with READ, or by a PREAD that does not
start at exactly the same point in the file  (otherwise the program outcome
is undefined).

PREAD and PWRITE can be used both for sequential access and for direct
access.  In the later case, the REC specifier indicates the position in the
file where from the transfer starts.  It is still the case that a transfer
may involve several records.

\subsection{restrictions}

The following restrictions allow for a simpler, more efficient
implementation of parallel I/O.  We may either put them in the language, or
list them as recommended programming style.

\begin{enumerate}
\item
Items in the item list of a PREAD or PWRITE statements
are restricted to be variables (no io-implied-do).
[Compilers may want to relax this rule, by considering an io-implied-do as
being an operation that defines a new variable, akin
to an array section, with a
distribution induced by the distribution of the variables appearing in the
implied-do-loop.]
\item
All values needed to determine which entities are specified by a parallel
I/O item list need be specified before the I/O statement.  That is, we
prohibit a statement of the form {\tt PREAD (...) N, A(1:N)}.
\end{enumerate}

\subsection{Extensions}
\begin{itemize}
\item
We may want to
write an array with a layout that is suited to the mapping of the array
that will appear in the input item list, rather than suited to the mapping of
the array in the output list.  To achieve this, we need to add align/distribute
information as part of the PWRITE statement.
\item
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.
\item
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).
\item
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}
\item
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}
\end{itemize}
\begin{thebibliography}{xxx}
\bibitem{vienaio}
P.\ Brezany, M.\ Gernt, P.\ Mehotra and H.\ Zima, ``Concurrent File Operations
in a High Performance Fortran.''
\end{thebibliography}
\end{document}