\documentstyle{csart}

% {{{  newcommands
\newcommand{\bct}{\begin{center} \begin{tabular}}
\newcommand{\ect}{\end{tabular}  \end{center}}
\newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\bq}{\begin{quote}}
\newcommand{\eq}{\end{quote}}
\newcommand{\bt}{\begin{tabbing}}
\newcommand{\et}{\end{tabbing}}

% }}}

\begin{document}

% {{{  \title{{Efficient translation of High Performance Fortran \\
{\centering \Large \bf Efficient translation of High Performance Fortran \\
	for distributed memory architectures}	\\[\baselineskip]
{\centering \Large \bf Case for support \\}
% }}}

% {{{  \section*{Purpose}
\section*{Purpose}

% {{{  intro

The recently published High Performance Fortran (HPF) language standard is
expected to have a major impact on the future of parallel computing,
especially on distributed-memory MIMD machines.  It is based on a simple
and familiar programming language, offers wide portability, a simple
migration method for existing Fortran codes, and the promise of high
performance.  There is every chance, therefore, that it will rapidly
become the preferred language for scientific and engineering
applications of parallel computers.

Until now, the lack of a programming language with these desirable
features has been a major factor behind the slow take-up of distributed
memory architectures.  Despite their high performance and cost
effectiveness---demonstrated across a range of important
applications---the development cost of application software targetting
specialised architectures too often outweighs any inherent
price-performance advantage of the hardware.

% }}}

% {{{  problems

Looking ahead some years, there is no obvious reason why HPF compilers
should not produce code competitive with hand-crafted message-passing
code.  It has been argued that an HPF compiler can actually do better
because, for example, it can target low-level machine instructions, and
statically allocate message buffers (rather than going through
message-passing portability layers).  However, early HPF compilation
systems are unlikely to generate such efficient code.  HPF-like systems
are in their infancy, and there has been relatively little study
of optimisation issues.  Research is urgently needed into efficient
implementation of the complex HPF semantics.

% }}}

% {{{  aims of this proposal

The aim of this project is therefore to investigate HPF 
compiler optimisation, particularly in the following areas:
\bi
% {{{  calculation placement

	\item To develop methods to determine optimal placement of
sub-expression calculation, to supersede the widely-used, very
crude, ``owner-computes'' heuristic.

% }}}

% {{{  organising comms 

	\item To investigate the relative merits of various mooted
schemes for organising data communications in HPF-like languages.

%	\item To investigate the relative merits of various mooted
%schemes for organising data communications in array expressions and
%assignments  (and assignments in DO-loops and FORALL), and to develop
%criteria for selecting the optimal one in particular circumstances.
%
%	\item To explore the feasibility and utility of an ``onion
%skin'' approach to managing the communications introduced by HPF
%compilation, based on a layered run-time library.  Successive
%optimisation phases ``in-line'' and simplify the run-time library calls
%wherever appropriate static information is available, introducing calls
%to the next layer of the library.

% }}}

	\item To implement the fruits of this research within a 
Subset HPF compilation system currently under development by our 
group, and evaluate the performance gains from these optimisations.

% {{{  comparison with Forge 90

	\item To compare our Subset HPF system with the Distributed
Memory Paralleliser and HPF compiler in the `Forge~90' system,
widely considered to represent the state-of-the-art in
Fortran parallelisation for distributed-memory systems.

% }}}
\ei

Our Subset HPF compilation system will generate Fortran~90 output
with calls to a communication library.  We plan to make this freely 
available to the research community.

NAG Ltd, who market a successful Fortran~90 compiler, will act as 
``heavy uncle'' for this project.  They will allow us to use relevant 
parts of their Fortran~90 compiler and run-time library source code, 
and provide other assistance.  Subject to the negotiation
of suitable terms, they will distribute our system together 
with their Fortran~90 compiler as a complete Subset HPF compilation 
system.

% }}}

% }}}

% {{{  \section*{Background} -- sort of ok, maybe
\section*{Background}

% {{{  background to HPF

\subsection*{\em High Performance Fortran}

In the last year the High Performance Fortran Forum (HPFF), a
coalition of many leading industrial and academic groups in the field
of parallel processing, has established the High Performance Fortran
(HPF) informal standard.  This is a set of extensions to Fortran~90 supporting
data-parallel computations on multi-processor architectures
\cite{hpf,hpf2}.  In particular, HPF includes directives for specifying (at
various levels of abstraction) how program data should be distributed
over virtual or actual processor memories.  The standard is supported
by most parallel computer manufacturers, and several vendors have
already announced HPF products.  An official subset of HPF has been
defined to facilitate early implementations.  It is expected that the
first true ``Subset HPF'' compilers, implemented as translators to
Fortran plus message-passing, will appear at the end of 1993 or start
of 1994.

% }}}

% {{{  deficiencies in state-of-art

HPF was developed to simplify the programming of multi-processor
architectures, especially distributed-memory MIMD systems.  It is based
on recent research into the transformation of ordinary sequential
languages, suitably annotated with data distribution declarations, into
distributed memory message-passing programs (e.g.
\cite{kali,fort-d,f90-d,c-star,pandore-c,vienna-fort,adapt-tech}).

Research implementations of these systems have been developed and
demonstrate the feasibility of such transformations.  However, current
transformation schemes are somewhat limited.  As yet there has been
little work on optimisation issues for such systems---work to date has
concentrated on initial implementation.

% }}}

\subsection*{Southampton Involvement with HPF}

% {{{  ADAPT

Since 1989 Dr.\ John Merlin has been involved in research
and development on a system called ADAPT (``Array Distribution Automatic
Parallelisation Tool'') for automatically transforming Fortran~90,
supplemented by data distribution declarations, into code for 
distributed memory message-passing architectures \cite{adapt}.  
The system generates a standard Fortran program to run on the individual
nodes of the target machine, which calls a run-time library to perform
data communications.

% }}}

% {{{  D-F90 & contributions to HPF

The input language for the ADAPT system, ``Distributed Fortran~90'', may
be regarded (with Fortran~D and Vienna Fortran) as a precursor of
HPF.

Southampton has had a significant input into, and influence on,
the development of HPF, through an active involvement in the HPFF.  Our
contributions to the language include the PURE procedure mechanism,
which allows suitably constrained procedures to be invoked
concurrently, providing useful scope for MIMD parallelism in an otherwise
predominantly SIMD programming model.

% }}}

% {{{  out Subset HPF compiler work, & NAG

This year we have undertaken to modify the ADAPT system into a Subset
HPF compiler (or rather a translator from Subset HPF to Fortran~90 plus
calls to a communications library).  This is a joint project involving
Dr.\ Merlin, who is modifying the ADAPT translator, and Dr.\ Bryan
Carpenter, who is developing the associated run-time system.

Limited attention is being paid to optimisation issues in the first
version of the system.
%As part of the work in progress Dr.\ Carpenter
%has been conducting experiments on heuristics for determining
%alignment of expression temporaries (closely related to the question of
%``calculation placement'') in general FORALL statements.  This
%is non-trivial because of the generality of the data access patterns
%allowed there.  These heuristics are being encoded in Prolog for
%prototyping and debugging.


% }}}

% {{{  \subsection*{Research experience}
\subsection*{Research experience}

Prof.\ Tony Hey is the Professor of Computation at the University
of Southampton and chairman of the Parallel Applications Centre
(PAC) at Southampton.  He has been a leading researcher in parallel
computing for many years, being the initiator, with Dr.\ David May
of INMOS, of the Esprit Supernode project which delivered the T800
transputer.  He has since been involved in a wide range of projects in
concurrent computation.  Recently he was a co-author of a proposal 
which formed the basis for the Message Passing Interface (MPI)
in the U.S.A., which aims to provide a standard for message-passing.

Dr.\ Bryan Carpenter and Dr.\ John Merlin have both been members of the
Concurrent Computation Group for several years, initially involved in
programming large-scale scientific applications in occam for transputer
arrays.  Dr.\ Merlin is the architect of ADAPT.  He has been a
participant in an Esprit-funded European working group on high level
languages for distributed memory architectures.  More recently he was
actively involved with HPFF, made various contributions to HPF
language, and authored sections of the language definition document.  He
is currently employed by the Esprit CAMAS project.  Dr.\ Carpenter has
been involved in the Supernode, Genesis and PUMA projects.  In the
latter he developed an Array Communications Library for implementing
data-parallel applications on transputer arrays.  The collective
operations it implemented have influenced the design of ADLIB, the
run-time library of ADAPT.

% }}}

\subsection*{\em Numerical Algorithms Group}

NAG Ltd, who are well known for their numerical libraries
and more recently for developing the first full Fortran~90 compiler 
(which translates Fortran~90 to C), have taken an interest 
in this work and are giving us technical support.  If our compiler
is suitable, they plan to distribute it together with their
Fortran~90 compiler as a Subset HPF compilation system.
They will act in the r\^{o}le of ``heavy uncle'' for this research
proposal, as we shall describe later.

% }}}

% {{{  \section*{Programme} -- sort of ok
\section*{Programme}

HPF is a very high level language, in the sense that a simple-looking
operation may translate to rather complicated target code.  {\em
Efficient} compilation is highly non-trivial.  For example, even given
the clues from program-variable distribution directives, there are
often many candidate choices for the localisation of individual
computations (``calculation placement'').  A bad choice may lead to
excessive communication or poor load balancing.

This project aims to advance the state-of-the-art in HPF translation
schemes.  Two principle areas demanding investigation are:
\begin{enumerate}
\item Effective strategies for the placement of calculation, and
\item Efficient schemes for managing communication, and minimising
      associated data copying.
\end{enumerate}
These two aspects are logically somewhat independent.  The first
defines what communications will be needed.  The second, given a
required pattern of communication, concentrates on achieving that
pattern efficiently.

% {{{  \subsection*{Calculation Placement}
\subsection*{Calculation Placement}

Placement of calculation cannot be prescribed by directives in the HPF
standard (proposals to allow this were rejected).  In simple cases this
placement will be obvious---for example where all of the operands of an
individual computation are program variables held on the same processor
(as determined by the placement directives).  Things are rarely this
simple, and in general a compiler will need an effective strategy for
making the placement.

To allocate computation to processors, many current HPF-like prototype
systems use a simple heuristic called the ``owner-computes'' rule,
whereby the expression in an assignment statement is evaluated by the
processor that ``owns'' the assignment variable, after the operands
have been sent there.  In many cases, where an expression is
not the right hand side of a simple assignment statement, the strategy
provides no guidance.  Where it is applicable it may be far from optimal
in terms of communication, temporary storage requirements, and
processor utilisation.

Some research into this problem has concentrated on techniques for
finding truly optimal placements for subexpressions, under some
simplifying assumptions about language features and communication
costs.  An alternative approach is to develop heuristics which
yield ``intuitive'' placements.  Although these may not be optimal,
they are unlikely to be very bad.

We will investigate these strategies.  There are two issues to be taken
into account.  Firstly the resulting code must be reasonably close to
optimal; secondly, the placement strategy should not be so expensive as
to make compilation time prohibitive---optimisation problems such as
this are prone to exponential time complexity.  We have performed some 
preliminary experiments on placement heuristics encoded in Prolog
for prototyping---probably a production compiler would have to be faster.

% }}}

\subsection*{Communication Management}

% {{{  \subsubsection*{Data communication schemes}

We will investigate (in particular) two important aspects.

\subsubsection*{\em Loop splitting}

    In many cases, especially with problems involving some ``locality
of reference'' (e.g.\ local updates in grid problems), array assignments
and DO-loops can profitably be split into parts operating on local data
and parts involving communication.  This may facilitate overlapping of
communication and computation, and make calculations on internal data
simpler.

For example, suppose that arrays $A$ and $B$ are identically aligned;
consider the following array assignment:
\begin{verbatim}
  A (1:N-1) = B (0:N-2) + B (2:N)
\end{verbatim}
This is typically parallelised by placing
a segment of the assignment index range (or DO-loop index range) 
on each processor.  Communication is required at the edges of these 
segments.  Two basic strategies are to use collective shifts to make 
two copies of the $B$ array, or just to copy the data on the edges from 
the adjacent processors.  In the latter case the edge data can be copied 
into an ``overlap area'' made by declaring the locally held array segment 
to be sufficiently large to accommodate the off-processor data,
or the communicated data can be copied to separately allocated
temporary storage.

Which of these assorted schemes is optimal depends on a number of
circumstances, including system parameters such as calculation and
communication costs, the availability of temporary storage, and how
much information about the assignment is statically available.  We
propose to develop criteria to select the best candidate by context.

% }}}

% {{{  \subsubsection*{Layered run-time communication library}
\subsubsection*{\em In-lining of layered communication library}

In certain places in HPF code (for example, in subprograms, when data
has ``transcriptive'' mapping) almost no information is statically
available concerning the whereabouts of particular array elements.  In
this case data is accessed by very high-level run-time libraries, with
a large performance penalty.

At the opposite extreme, on sufficiently simple code an optimising
compiler may be able to go straight to low level communication
instructions (below the level of standard message passing interfaces).

An attractive way to define the HPF translation scheme is to start
from a layered run-time system, with general data access and collective
communication near the top level.  Some representation of this run-time
system---which may differ between platforms---is available to the compiler
(ideally in a data-base apart from the translator itself).
Code is initially translated to employ top-level calls.  In successive
optimization passes, calls to the run-time library are ``in-lined'' to
give calls to the next layer of the library, whenever appropriate static
information is available about the actual arguments.  The resulting
code is simplified where the static context permits.

We propose to explore the feasibility and utility of this
modular ``onion-skin'' approach to optimising communication.
% }}}

% {{{  \subsection*{Implementation and evaluation}
\subsection*{Implementation and evaluation}

These optimisations will be implemented and evaluated within a Subset
HPF compiler that is currently under development (see ``Background'').

Finally, we will compare our Subset HPF system with the Distributed
Memory Paralleliser and HPF compiler in the `Forge~90' system, which
is widely regarded as representing the state-of-the-art in
the parallelisation of Fortran for distributed-memory computers.

% }}}
% }}}

% {{{  \section*{Resources} -- sort of ok
\section*{Resources}

We have requested funding for two named individuals, Dr.\ John Merlin
and Dr.\ Bryan Carpenter, whose research backgrounds are detailed 
elsewhere in this proposal.  Their experience and abilities are
ideal for the proposed research.

The funds requested for travel allow for visits to our industrial 
collaborators NAG Ltd, for visits to other UK establishments 
who are active in HPF research and development,
and for attendance at suitable HPF meetings and workshops in the UK.
We have also requested travel funds for each researcher to attend
two selected overseas conferences or workshops per year.
In particular we wish to be represented at the specialist `Compilers for
Parallel Computers' workshops in Europe, which attract most of the leading
researchers in this field and which we have attended since their inception,
as well as selected conferences (e.g.\ Supercomputing) and HPF workshops.
Finally, we have requested funds for one visit to Hans Zima's group at
the ACPC in Vienna, and one U.S.\ trip to visit the groups at
Rice and Syracuse Universities (and possibly other ``centres of 
excellence'').  These are widely regarded as among the
leading research groups in the field of Fortran parallelisation, and
we have established close contacts with them which will be beneficial 
to maintain.

Two workstations have been requested for the personal use of the
researchers.

Funds have also been requested for a 1-user licence for the 
`Forge~90' Distributed Memory Paralleliser and run-time library 
for the Meiko CS-2.  This will enable us to compare our Subset HPF system
with what is widely regarded as the current state-of-the-art technology
for parallelising Fortran for distributed-memory.

% }}}

% {{{  \section*{Applications, collaboration and exploitation}
\section*{Applications, collaboration and exploitation}

The aim of this proposed project is to advance the state-of-the-art in
the optimisation of High Performance Fortran for distributed memory 
parallel architectures, workstation networks, etc, and will thereby 
promote the use of HPF and of such architectures.

We plan to make the Subset HPF translator and communications
library that we produce freely available to the research community.
The communications library will also be usable separately from the 
Subset HPF system, and will be well-documented to facilitate this.
The system will be designed to retain portability as far as possible, 
since the translator will target a standard high-level language
(Fortran~90), and the associated communications library will use a
public domain message-passing system (e.g.\ PVM) allowing execution 
on workstation networks as well as parallel supercomputers.

NAG Ltd will act as ``heavy uncle'' for this project.  They will allow 
us to use relevant parts of their Fortran~90 compiler and run-time 
library source code, will make any necessary modifications to their 
Fortran~90 compiler to handle the output of the Subset HPF system, 
and will also provide technical input and assistance with 
porting, testing and evaluation.  Subject to the negotiation of suitable
commercial terms, they plan to distribute the Subset HPF system together 
with their Fortran~90 compiler as a complete Subset HPF compilation system 
generating C code.
% }}}

% {{{  refs
\begin{thebibliography}{99}

% {{{  \bibitem[And90]{pandore-c}
\bibitem[And90]{pandore-c}
F.~Andr\'{e}, J.-L.~Pazat and H.~Thomas.
PANDORE: a system to manage data distribution, 
{\em Proc.\ Int.\ Conf.\ on Supercomputing}, 380-88, June 1990.

% }}}
% {{{  \bibitem[Chap92]{vienna-fort}
\bibitem[Chap92]{vienna-fort}
B.~Chapman, P.~Mehrotra and H.~Zima.
Programming in Vienna Fortran.
{\em Scientific Programming\/} \underline{1}(1), August 1992.

% }}}
% {{{  \bibitem[Fox91]{fort-d}
\bibitem[Fox91]{fort-d}
G.~Fox et al.
Fortran D Language Specification.
Technical report COMP TR90-141, 
Dept.\ of Comp.\ Sci., Rice Univ., Houston, TX, April 1991.

% }}}
% {{{  \bibitem[HPFF93]{hpf}
\bibitem[HPFF93]{hpf}
High Performance Fortran Forum.
High Performance Fortran Language Specification.
{\em Sci.\ Prog.\/}, \underline{2} (1), Aug.\ 1993.

\bibitem[Mer93]{hpf2}
J.H.~Merlin and A.J.G.~Hey.
An introduction to High Performance Fortran.
To appear in {\em Sci.\ Prog.\/}, \underline{2} (2), end of 1993.

% }}}
% {{{  \bibitem[Hat90]{c-star}
\bibitem[Hat90]{c-star}
P.J.~Hatcher et al.
A production quality C$^{\ast}$ compiler for a hypercube multicomputer.
Report from Parallel Computing Lab., Dept.\ of Comp.\ Sci., Univ.\ of 
New Hampshire, Durham, NH 03824, U.S.A.

% }}}
% {{{  \bibitem[Koe90]{kali}
\bibitem[Koe90]{kali}
C.~Koelbel, P.~Mehrotra and J.~Van~Rosendale.
Supporting shared data structures on distributed memory architectures,
{\em Proc.\ 2nd ACM SIGPLAN Symposium on Principles and Practice of
Parallel Programming}, pp 177-86, March 1990.

% }}}
% {{{  \bibitem[Mer91]{adapt}
\bibitem[Mer91]{adapt}
J.H.~Merlin.
ADAPTing Fortran~90 array programs for distributed memory architectures.
{\em Proc.\ 1st Int.\ Conf.\ of the ACPC\/}, Salzburg, Sept.\ 1991.

% }}}
% {{{  \bibitem[Mer92]{adapt-tech}
\bibitem[Mer92]{adapt-tech}
J.H.~Merlin.
Techniques for the Automatic Parallelisation of `Distributed Fortran~90'.
Technical report SNARC 92-02, 
Dept.\ of Electronics and Comp.\ Science, Univ.\ of Southampton, 
November 1991.

% }}}
% {{{  \bibitem[Wu91]{f90-d}
\bibitem[Wu91]{f90-d}
M.-Y.~Wu and G.~Fox.
Fortran 90 D compiler for distributed memory {MIMD} parallel
computers.
Report SCCS-88b, Syracuse Center for Comp.\ Sci, Syracuse
Univ., Syracuse, New York, July 1991.

% }}}
% {{{  \bibitem[ZBG88]{superb}
\bibitem[ZBG88]{superb}
H.~Zima, H.-J.~Bast and M.~Gerndt. 
SUPERB, a tool for semi-automatic MIMD / SIMD parallelisation, 
{\em Parallel Computing}, \underline{6}, 1-18, 1988.

% }}}

\end{thebibliography}
% }}}

\end{document}



