\documentstyle[twoside,11pt]{article}

\pagestyle{myheadings}
\sloppy
\footheight=-.60in
\headheight=0in
\textwidth=5.50in
\topmargin=-.20in
\oddsidemargin=0.5in
\evensidemargin=0.5in

\itemsep=.05in
\topsep=.05in
\parsep=.05in
\parskip=.10in
\textheight=9in

\newcounter{dofigures}  \setcounter{dofigures}{0}
\newcounter{dotables}        \setcounter{dotables}{0}
\newcommand{\havefigures}{\setcounter{dofigures}{1}}
\newcommand{\havetables} {\setcounter{dotables}{1}}

\newcommand{\cccdocid}[5]{
  \bibliographystyle{alpha}
% ******************** Title Page ********************
  \vspace*{.5in}
  \centerline{\Large \bf {#1}}
  \vspace*{.02in}
  \centerline{{#2}}
  \vspace*{.02in}
  \centerline{{#3}}
  \vspace*{.02in}
  \centerline{{#4}}
  \vspace*{.02in}
  \centerline{{#5}}
  \vspace*{.5in}

  % ******************** List of Figures ********************
  % Note: Remove the following line if there are no figures
%  \ifodd\value{dofigures} \listoffigures \newpage \fi
%  \ifodd\value{dotables}  \listoftables  \newpage \fi
%  \markboth{#1} {#3}
%  \pagenumbering{arabic}
  }

% ******************** Special macros ********************
%\catcode`^^Z=9                % Make TeX ignore IBMPC EOF character

\newcommand{\ital}[1]{{\it #1}}
\newcommand{\type}[1]{{\tt #1}}
\newcommand{\bold}[1]{{\bf #1}}
\newcommand{\dfn}[1]{{\it #1}\index{#1}}
\newcommand{\comment}[1]{}

\def\fineprint{\relax}
\def\stopfine{\relax}


\newcommand{\beginprog}{\begin{tabbing}
xxxx\=xxxx\=xxxx\=xxxx\=xxxx\=xxxx\=xxxx\=xxxx\=xxxx\=xxxx\=\kill
}
\newcommand{\tb}{\>\tt}
\newcommand{\finprog}{\end{tabbing}}
\newcommand{\progtxt}[1]{``{\tt #1}''}
\newcounter{save_enum}
\newcommand{\hilite}[1]{ \item {\bf #1\\} }
\newcommand{\morelater}{\centerline{$\ldots$\ital{Fill this in later}$\ldots$}}


% ******************** Start of Document ********************
\begin{document}

\cccdocid
  {Kernel HPF}
  {Ver 2.0}
  {Andrew Meltzer}
  {Cray Research, Inc.}
  {August, 1995}

\begin{abstract}

HPF contains many directives which offer ease of use, but
the excessive overhead associated with these directives can severely
compromise performance on one or more (even all for some combination
of features) distributed memory parallel computers.
This report identifies a kernel of HPF which performs well across many
platforms.  It is an implementors view and may not contain all of the
features all applications developers desire, but all of the features
which are provided enhance performance.

\end{abstract}

\section{Introduction}

HPF contains many directives which offer ease of use, but
the excessive overhead associated with these directives can severely
compromise performance on one or more (even all for some combination
of features) distributed memory parallel computers.
Kernel HPF is a high performance subset of HPF.  The features chosen
for the Kernel HPF subset were selected for the following reasons
\begin{itemize}
\item They allow high-performance across all platforms.
\item On no platform are there performance ``surprises,''  Few, if any, 
      combinations
      of Kernel HPF features unexpectedly lead the user into low-performance 
      circumstances although it is still possible for application
      programmers to write low-performance codes and for vendors to 
      provide low-performance implementations.
\item They are easily understood.
\item They are commonly used.
\item They are valuable for all platforms.
\end{itemize}

Kernel HPF limits the directives from HPF
to a core subset that can be shown to be high performance across a broad 
spectrum of machines.   

Items are taken from throughout the entire HPF specification, Kernel HPF 
does not limit itself to selections from Subset HPF.

The set of features chosen for Kernel HPF are not a randomly
selected set of the available features.  They are chosen based on
the above constraints.  They are also chosen to
simplify the HPF model by reducing the variety of mappings to
only those most commonly used and to simplify
the model by removing a level of abstraction.

The first part of this paper describes each feature and its Kernel HPF
definition along with a rationale.
Part two of this paper steps through the HPF specification, describing 
the changes to the features of each section.

With the proposed changes to full HPF that allow all remappings to be
done by the caller, an extrinsic environment is no longer necessary for
the kernel because the calling conventions will be the same.  It is
recommended that HPF\_KERNEL subroutines be distinguished by a 
\begin{verbatim}
        CHPF$   HPF_KERNEL
\end{verbatim}
directive.  This directive indicates that the subroutine which follows
is a Kernel HPF subroutine.


\section{Kernel HPF Features}

This section describes each of the features of Kernel HPF in detail
and gives a rationale for the inclusion or exclusion of each. 

\subsection{The \type {DISTRIBUTE} Directive}

The {\type {DISTRIBUTE}} directive remains mostly intact, only a few pieces
of functionality have been removed.
\subsubsection{Distribution Formats}

Kernel HPF includes only the {\type {BLOCK}} distribution.  It does
not include the {\type {CYCLIC}}, {\type {CYCLIC(N)}}, or {\type {BLOCK(N)}}
distributions.  The effort to determine the locations of the elements
in an array with the {\type {BLOCK}} distribution is much less than the
other distributions.

%Kernel HPF includes {\type {BLOCK}}, {\type {CYCLIC}}, and 
%{\type {CYCLIC(N)}} distributions.  It does not include {\type {BLOCK(N)}}
%distributions.

%{\em{Rationale}}:
%\begin{itemize}
%\item  {\type {BLOCK}} is the most common and useful distribution in common
%       practice.  It is also the most straightforward to implement efficiently.
%\item  {\type {CYCLIC}} is the next most common distribution.  It allows
%       maximal load balancing.
%\item  {\type {CYCLIC(N)}} allows the user to tune the 
%       communicaton/load-balance ratio for particular applications and 
%       particular architectures.  It is very important when fine-tuning
%       for performance.
%\item  {\type {BLOCK(N)}} is difficult to implement efficiently  and 
%       it is unclear how a high-performance application could effectively
%       exploit this feature.
%\end{itemize}

There is some sentiment that the kernel should contain more distribution
types, for example that the {\type {CYCLIC(N)}} distribution be added.

\subsection{\type {DYNAMIC} Distributions}

{\type The {DYNAMIC}} attribute is disallowed in Kernel HPF.

\subsubsection{On-Processor Dimensions}
The ``*'' syntax is included in the {\type {DISTRIBUTE}} directive 
{\em {dist-format-clause}} to indicate on-processor dimensions.

{\em {Rationale}}: This is a convenient technique for increasing locality of
reference, a goal for most high performance codes.  It can be accomplished
efficiently with reasonable compiler effort.


\subsection{The \type {PROCESSORS} Directive}

The {\type {PROCESSORS}} directive is part of Kernel HPF without change.

{\em {Rationale}}: The processors directive is an important way to
indicate the equivalence of mappings.  While most implementations
will probably map arrays with identical distributions and alignments
the same, portability requires that the {\type {PROCESSORS}} directive
be made available.  

The directive is also perhaps the only way to fine-tune multidimensional
distributions.


\subsection{The \type {ALIGN} Directive}

In Kernel HPF the {\type {ALIGN}} directive is restricted to
alignments that are direct;  there may be no offsets or strides
within an  {\type {ALIGN}}.  Replication and collapsing of dimensions
are also disallowed.  In alignment expressions the dimensions may
not be permuted, for example:

\begin{verbatim}

        !HPF$ ALIGN A(I,J) WITH B(J,I)  ! Not allowed in Kernel

\end{verbatim}

{\em {Rationale}}: While these measures initially appear to be 
draconian restrictions on programmability, almost all of the useful
functionality provided by these features is available through other
means which are more straightforward to optimize.  Adding strides to the 
{\type {ALIGN}} directive, among other things, greatly complicates 
the addressing, probably ends up wasting space, and increases the 
amount of information which must
be passed across subroutine boundaries. 

If the {\type {CYCLIC(N)}} distribution is accepted as part of the
kernel, almost everything that one wants to do with strided alignments 
can be done by varying the block size.  In both of the following
examples the elements of {\type A} are aligned with the even elements
of {\type B}.

    {\em {Example 1a}}
\begin{verbatim}
                DIMENSION A(128), B(256)
        CHPF$   DISTRIBUTE B(CYCLIC(16))
        CHPF$   ALIGN A(I) WITH B(2*I)  ! Disallowed in Kernel
\end{verbatim}

    {\em {Example 1b}}
\begin{verbatim}
                DIMENSION A(128), B(256)
        CHPF$   PROCESSORS P(32)
        CHPF$   DISTRIBUTE A(CYCLIC(8)) ONTO P
        CHPF$   DISTRIBUTE B(CYCLIC(16)) ONTO P
\end{verbatim}

It has been noted however, that the vast majority of codes do not require
this functionality so its lack of inclusion into the HPF kernel would not
be overly restrictive.

Offsets are not allowed in the {\type {ALIGN}} directive of Kernel HPF.  The 
effect of offsets can be
generally be achieved by changing the bounds of arrays (although this
may be implementation dependent, it is not reaching all that far.)
The following two examples will create the same alignment.

    {\em {Example 2a}}
\begin{verbatim}
                DIMENSION A(1:100), B(0:99)
        CHPF$   PROCESSORS P(32)
        CHPF$   DISTRIBUTE B(BLOCK) ONTO P
        CHPF$   ALIGN A(I) WITH B(I-1)  ! Disallowed in Kernel
\end{verbatim}

    {\em {Example 2b}}
\begin{verbatim}
                DIMENSION A(1:100), B(0:99)
        CHPF$   PROCESSORS P(32)
        CHPF$   DISTRIBUTE A(BLOCK) ONTO P
        CHPF$   DISTRIBUTE B(BLOCK) ONTO P
\end{verbatim}

Collapsing of dimensions is disallowed because it can be accomplished 
with the {\type {DISTRIBUTE}} directive.  

Replication is not available with these restrictions, but Kernel HPF
is not meant to solve all problems.  Unfortunately to achieve the
goal of adding replication, a whole lot of unwanted baggage would
also be required.   It may be possible to add some syntax to explicitly
recommend replication but it should not be done through the {\type {ALIGN}}
directive.

\subsection{The {\type {TEMPLATE}} Directive}

The template in a {\type {TEMPLATE}} directive must have the same rank 
and extents as the arrays aligned to it.  This, in 
essence, reduces the the functionality of templates to a convenient
way of specifying that different (identically dimensioned) arrays are 
to be distributed identically.  

{\em {Rationale}}: Mis-use of templates is probably the easiest way
to turn a high performance code into a low performance one, and it
is likely that different compilers will optimize different parts
of the complexities of templates due to underlying hardware performance
considerations. Even when a user finds a complicated template layout
to be high performance on one platform it will probably not be high
performance, or even moderately high performance, on all platforms.

Also, nearly all of the high-performance features of templates
are available through other mechanisms.


\subsection{The {\type {FORALL}} Statement and Construct}

These are included in Kernel HPF.

{\em {Rationale}}: {\type {FORALL}} is a powerful and expressive way
to code parallelism.  It is true that not all {\type {FORALL}} 
statements and/or constructs can be fully parallelized, but because
of their general value and because they will be part of Fortran 95,
they are included in Kernel HPF.

\subsection{{\type {PURE}} Functions and Subroutines}

These are included in Kernel HPF.

{\em {Rationale}}: {\type {PURE}} functions can do no harm, and allow
an increased level of expressiveness.  They simplify the job for
the compiler and are part of Fortran 95.

\subsection{The {\type {INDEPENDENT}} Directive}

The {\type {INDEPENDENT}} directive is included in Kernel HPF.

{\em {Rationale}}: Directives such as {\type {INDEPENDENT}} have shown
their worth historically across a broad variety of platforms.  This
directive simplifies the analysis the compiler must do and can inform
the compiler about optimizations that it may do that otherwise
are expensive or impossible to deduce.   {\type {INDEPENDENT}} allows 
an increased level
of optimization.

\subsection{Extrinsics and {\type {HPF\_LOCAL}} and {\type {HPF\_SERIAL}} }

The general purpose extrinsic mechanism, {\type {HPF\_LOCAL}} and 
{\type {HPF\_SERIAL}} are all included in Kernel HPF.

{\em {Rationale}}: These allow a program to get at the highest 
performing features of a particular architecture.


\subsection{Library}

All of the HPF library routines are in Kernel HPF.  

{\em {Rationale}}: The intrinsics provide fast, architecture specific
versions of many very important parallel functions.  To achieve a
similar level of performance for these functions a user would have
to write non-portable code.


\subsection{The {\type {INHERIT}} Directive}

The  {\type {INHERIT}} directive is not part of Kernel HPF.

{\em {Rationale}}:  The usefulness of {\type {INHERIT}} is greatly
limited by the rest of the restrictions placed on Kernel HPF.  It
still has some use when passing, for example, array sections with
strides but the additional mechanisms that would have to be added
elsewhere to handle this case do not justify its inclusion.

\subsection{Subroutine Interfaces}

In Kernel HPF explicit interfaces are required for any subroutine
which remaps data.
Dummy arguments from actual argument array sections cannot be 
mapped ``{\type {DISTRIBUTE * ONTO *}}.'' Non-unit
strides may be specified when passing array sections as actual
arguments.

Assumed shape explicitly mapped dummies are
allowed in Kernel HPF, but explicit interfaces must be included where
they are used. Assumed shape dummies may use any mapping syntax.
The results of array valued functions may be explicitly mapped.  Assumed
size arrays are not allowed in the Kernel.

To be exact, an explicit interface is required in each of the following
cases:
\begin{itemize}
\item A parameter is passed transcriptively or with the inherit attribute.
\item The mapping of the dummy argument is not the same as the mapping of
      the actual argument.
\end{itemize}



{\em {Rationale}}: Much better control of the remapping can be achieved
if the explicit interface is available and much less code to check
mappings and remap upon entry is necessary.


\section{HPF Specification by Section}
\subsection{Sections 1 and 2. Overview and Terms and Concepts}

No changes are needed here for Kernel HPF.

\subsection{Section 3. Data Alignment and Distribution Directives}

This section contains much of the substance of the HPF specification:
the data alignment and distribution directives.  Kernel HPF severely
limits these directives to only those where high
performance across a broad spectrum of machines can be expected.

The most restrictions are placed on alignment and templates.  Alignments
cannot be permuted, nor can they be offset.  Templates must be identical
in rank and size to the arrays aligned to them.

\subsection{Section 3.1 Model}

The Kernel HPF model is a
small subset of the HPF model; this subset is so restricted that a
simpler semantic model could have been used. On page 21 of the HPF
specification the model is graphically displayed as a four-level mapping
from ``arrays or other objects'' to ``group of aligned objects'' to ``abstract
processors as a user-declared cartesian mesh'' and finally to ``physical
processors''  In Kernel HPF this model is simplified to three levels by
severly restricting the usefulness of templates.


\subsection{Section 3.2. Syntax of Data Alignment and Distribution Directives}

None of the keywords {\type {REALIGN}}, {\type {REDISTRIBUTE}, 
{\type {INHERIT}, or {\type {DYNAMIC}} are
part of Kernel HPF. With this exception,
section 3.2 correctly describes the syntax of the data alignment and
distribution directives of Kernel HPF.

\subsection{Section 3.3 {\type {DISTRIBUTE}} and {\type {REDISTRIBUTE}} Directives}

\type {REDISTRIBUTE} and {\type {DYNAMIC}} are not part of Kernel HPF.

\type {BLOCK} is available in Kernel HPF. 

Collapsing of dimensions can only be
achieved through distribution, not alignment.  See the following
section for details of the restriction.  The `*' syntax
is recognized by Kernel HPF and indicates that the 
dimension is on-processor.

\subsection{Section 3.4 {\type {ALIGN}} and {\type {REALIGN}}}

{\type {REALIGN}} is not part of in Kernel HPF
The {\type {ALIGN}} directive itself is very
restricted.  The following are additional rules placed on the {\type {ALIGN}}
directive

\begin{itemize}
\item   Alignments must be direct, i.e., there can be no offsets
        specified.      For example the following is correct code:

                {\type {CHPF\$           ALIGN A(I,J) WITH B(I,J)}}

         But the following is not:

                {\type {CHPF\$           ALIGN A(I,J) WITH B(I+1,J)}}

\item   The {\em {align-subscript-use}} in the HPF syntax rules should be
        replaced with {\em {align-dummy}}.

\item   Dimensions may not be permuted.

\item   The {\em {alignee}} and the {\em {align-target}} of 
        the {\type {ALIGN}} directive must have the same rank and extents.

\item   A `*' is not allowed in either the align-spec or the alignee.
\end{itemize}

\subsection{Section 3.5. {\type {DYNAMIC}} Directive}

The {\type {DYNAMIC}} Directive is not part of Kernel HPF.

\subsection{Section 3.6. Allocatable Arrays and Pointers}

Allocatable arrays and pointers in Kernel HPF may be explicitly mapped.

\subsection{Section 3.7. {\type {PROCESSORS}} Directive}

The {\type {PROCESSORS}} directive is allowed.

\subsection{Section 3.8. {\type {TEMPLATE}} Directive}

Templates may only be the shape (rank and extent for each dimension) of
the arrays aligned to them. This restriction, in conjunction with the
restrictions on alignment make moot almost all of the examples in
Section 3.8. The restrictions placed on templates are so severe, in
fact, that they reduce the usefulness of templates to a syntactically
convenient way of mapping many identical arrays in a similar fashion.

\subsection{Section 3.9. {\type {INHERIT}} Directive}

The {\type {INHERIT}} directive is not part of Kernel HPF. 

\subsection{Section 3.10 Alignment, Distribution, and Subprogram Interfaces}

Kernel HPF requires interface blocks for any arguments that are re-mapped.
This allows the caller to re-map data only when necessary, greatly 
simplifying (and consequently speeding up) the subroutine call interface.

Arbitrary array sections may be passed, but must have an explicit
interface and cannot be mapped ``{\type {DISTRIBUTE * ONTO *.}}'' Non-unit
strides may be specified when passing array sections as actual
arguments.

Kernel HPF retains the distinctions and all of the syntax relating to
transcriptive, prescriptive and descriptive mappings in full HPF.

The results of array valued functions may be explicitly mapped.

\subsection{Section 4. Data Parallel Statements and Directives}

\subsection{Section 4.1 and 4.2. The {\type {FORALL}} Statement and Construct}

The {\type {FORALL}} statement and the {\type {FORALL}} construct are part
of Kernel HPF.

\subsection{Section 4.3. Pure Procedures}

Pure procedures and functions are part of Kernel HPF.  


\subsection{Section 4.4. The {\type {INDEPENDENT}} Directive}

The {\type {INDEPENDENT}} directive is part of Kernel HPF.  The {\type {NEW}}
clause is also part of Kernel HPF. 

\subsection{Section 5. Intrinsic and Library Procedures}

Kernel HPF should contain all intrinsic and library procedures.  

\subsection{Section 7. Storage and Sequence Association}

There is no storage or sequence association in Kernel HPF.

\end{document}
