Subject: Journal of Development section on IO

From: Bob Knighten <[email-masked]>
Date: Mon, 19 Oct 92 01:55:31 PDT

Dave --

I took the Appendix (which was empty in the version I had) and added a section
on I/O to the Journal of Development chapter.  I am working blind at the
moment (i.e. I have not actually seen what the formatted text looks like), so
I would appreciate having you take a look to see if there are any format
errors.

-- Bob
==============================================================================
%appendixes.tex

%Version of October 16, 1992

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%journal_of_development.tex

\chapter{Journal of Development}
\label{journal}

%Version of October October 16, 1992 - Robert L. Knighten, Intel Corporation;
%Piyush Mehrota, ICASE; Marc Snir, International Business Machines Corporation

\section{Summary}

\footnote{Version of October 16, 1992 - Robert L. Knighten, Intel
  Corporation, Piyush Mehrota, ICASE, Marc Snir, IBM}

High Performance Fortran is primarily designed to obtain high
performance on massively parallel computers.  Such massively parallel
machines also need massively parallel I/O.

There are difficulties in getting high performance I/O:
\begin{itemize}

\item Efficient programs must avoid sequential bottlenecks from
  processors to file systems

\item Fortran specifies that a file appears in element storage order;
  this conflicts with striped files (for example, an array distributed
  by rows may be written to a file striped by columns).

\end{itemize}
  
In particular Fortran file organization has limits:
\begin{itemize}

\item Files have a sequential organization. (Even direct access files
  have records in sequential order, though they can be accessed out of
  order)
  
\item Fortran files are record oriented

\item Storage and sequence association are in force (when writing and
  then reading a file, for instance)
  
\item No specification of the physical organization is possible

\item No compatibility with other languages/machines is guaranteed

\end{itemize}

With these in mind there are two major approaches that have been
suggested:  
\begin{enumerate}

\item Define hints (annotations) that do not change file semantics, in
  the spirit of data distribution. (This gives some information to the
  compiler.)

\item Introduce parallel read/write operations that are not
  necessarily compatible with sequential ones.

\end{enumerate}

\subsection{Hints}

Two ideas have been advanced which use the idea of giving hints to the
compiler without changing the Fortran file semantics.

The first is based on the observation that although the distribution
of an array when it is written may be available to the compiler or
runtime system, the distribution into which that array will be read
cannot generally be known, even though the programmer may have this
knowledge.  So the proposal is to provide on a write a hint about how
the data will be read.  

\CODE
          DISTRIBUTE (CYCLIC) :: a
          !HPF$ IO_DISTRIBUTE * :: a
          WRITE a, b, c
          !HPF$ IO_DISTRIBUTE * :: b
\EDOC

When an array is written, it can be easily read back in the given
distribution. The annotation can be associated with either the
declaration or the write itself; in the first case it applies to all
writes of the array, while in the second it only applies to the one
statement.  The intent is that meta-data is kept in the file system to
record the "right" data layout. The advantages of this proposal
include notation and efficiency

The second proposal is to give hints about the physical layout (number
of spins, record length, striping function, etc.) of the file when it
is opened.

This uses the HPF array mapping mechanisms. (A file is a 1-dimensional
array of records.) The syntax needs a "name" for the file "template":
we suggest FILEMAP. The programmer can align/distribute FILEMAP (on
I/O nodes), associate FILEMAP with a file on OPEN, etc. There are
again no changes in semantics or file system.

\subsubsection{Mapping Files}

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}

\subsubsection{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:

\CODE
!HPF$ NODE :: D1(2,4), D2(2,2)
      PARAMETER(NOD=NUMBER_OF_IONODES())
!HPF$ NODE, DIMENSION(NOD) :: D3,D4

\EDOC

\subsubsection{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

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

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:

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

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

\subsubsection{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:

\CODE
!HPF$ DISTRIBUTE (CYCLIC,CYCLIC,*) ONTO D2 :: F2,F3
!HPF$ DISTRIBUTE F1(*,BLOCK,CYCLIC(2)) ONTO D1
\EDOC

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

\subsection{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.

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

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.

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

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

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

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 multi-dimensional arrays.  E.g.

\CODE
READ (7, REC = INDEX(F1,3,5) ) A
\EDOC

\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 fulfills 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.\ Mehrota and H.\ Zima,
  ``Concurrent File Operations in a High Performance Fortran.''
\end{thebibliography}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

%Revision history:
%August 2, 1992 - Original version of David Loveman, Digital Equipment
%	Corporation and Charles Koelbel, Rice University
%October 14, 1992 - RLK - Added a section on I/O to the Journal of
%Development chapter based on the proposal from Marc Snir, IBM, and Piyush
%Mehrota, ICASE.