\documentstyle{article}
\title{Functional Programming applied to real applications in Science
and Engineering}
\author{Case for Support}
\date{}
\begin{document}
\bibliographystyle{plain}
\maketitle
A submission to the Systems Architecture Committee of the SERC.

\section*{Purpose}

Many of the problems in scientific computing are conveniently
specified in a mathematical style; in addition, the computational
requirements are such that they are a fruitful application area for
the use of parallel processing. Functional languages have a distinctly
mathematical flavour; they also claim a number of advantages in
exploiting parallel machines.

This proposal is to investigate this relationship. Some work on the
problems has already been completed. Further work is planned, and
detailed work on parallelism will be undertaken.

The objectives are thus:

\begin{itemize}
\item To investigate further the expressive power of functional
languages for solving scientific programming problems.
\item To compare the merits of imperative and functional languages
applied to scientific algorithms.
\item To provide a demonstrator application.
\end{itemize}

\section*{Background}

The FAST (Functional Programming for Arrays of Transputers) Project
was funded by the SERC (GR/F 35081), and was a collaboration between
the University of Southampton and Imperial College, London. Meiko Ltd
of Bristol was the industrial uncle. It began in August 1989, and has
just finished in February of this year.

The objectives of the project were to investigate the technology to
exploit loosely-coupled multi-processors using functional languages.
The model for exploitation was to use a process description language
(Caliban \cite{Kel89}) to provide an abstraction that would allow
coarse-grain parallel processes to be specified conveniently. The
processes themselves were to be compiled from functional language
source using a compiler that performed extensive analysis. The
responsibility for the Caliban work was largely sited at Imperial
College \cite{Cox92}, and the sequential compiler largely at
Southampton \cite{Gla90,Har93}.

At Southampton a compiler was constructed which took a number of
possible functional language inputs (including interfacing to a
Haskell subset front end written at Imperial), and generated C as the
``machine code''. The C object code is combined with a run-time system
which thus provides an implementation that can be run on any Unix
workstation \cite{Wil91}.

The performance of both the compiler and the code compares well with
other functional language implementations currently available
\cite{Har92b}.


\subsection*{Scientific application work in FAST}

As part of the FAST project, a small number of applications were
planned to test the technology.  At Southampton it proved possible to
employ a researcher (Dr Bryan Carpenter) for a short time to explore
some applications.  Dr Carpenter has longstanding experience of
simulating models from high energy and condensed matter physics.  He has
been involved in many parallel machine projects for Prof Tony Hey, both
in design and benchmarking workpackages.

Three problems of increasing complexity were investigated: solution of
a partial differential equation by the relaxation method; Monte Carlo
simulation of a statistical mechanics (condensed matter) system; and a
similar simulation of a lattice gauge theory.  Below we comment on the
style of implementation that was developed.

The algorithms implemented were all formulated on grids.  The model of
computation in languages such as Fortran is to use an array of values
to represent the state of the computation.  An obvious approach in a
functional language would be to use stream of arrays, representing the
history of the computation.  In fact it proved more convenient to use
an equivalent representation, in which the elements of a single array
were lazy streams representing the history of each individual grid
site.  To convert between these representations, for example for
printing, it is easy to use the built-in higher order functions.  Thus
from the outset the algorithms began to exploit features such as
laziness that are unique to the chosen implementation language.

Representation as an array of streams had various advantages.

Firstly it is easy to see that such streams can be viewed as interacting
parallel processes, and this gives an excellent starting point from
which to investigate the parallel execution behaviour of the program.

Secondly, arrays in functional languages are not yet implemented as
efficiently as they might be. It turns out that the implementations
used are better able to optimise the ``array of streams'' model
than the ``stream of arrays'', because array-subscripting operations
are required less frequently.

Thirdly many parts of the algorithms can be clearly specified.
To try to give a flavour of this we consider a fragment of code from
the Poisson equation relaxation program.

The history of a site depends on the history of its neighbours.
For the simple case of Jacobi relaxation, the new value at a site
is calculated from the values of the neighbouring sites in
the previous generation.  In more general schemes, such as Gauss-Seidel,
the new value at a site is calculated as a combination of the previous
and the latest generations.  This can be implemented by colouring the
sites to indicate which generation should be used.  The function for
updating site $i$ is passed a stream representing the history of
neighbouring site $j$, to which we apply the function

\begin{verbatim}
         if colour j < colour i then tail else id
\end{verbatim}

This expression returns either the function $tail$ or $id$, depending
on the relative colours of the sites.  Its effect on the stream
is to either look one place forward in the history, if
necessary, by taking the tail of the stream, or to leave the
stream unchanged by applying the identity function.
This is the only change needed to go from the Jacobi update
to the Gauss-Seidel update, with its more complex data dependencies.

The other major advantage observed was the level of abstraction
facilitated by the language, and the opportunites for code reuse
engendered.  The problems under consideration have similar structures,
but the geometries and local update vary.  Careful consideration was given
to the handling of the lattices to ensure the right level of
abstraction.  This care in separating the geometry was well rewarded.
The update operations are not concerned with, and make
almost no reference to, the geometry.  Thus the first and second
applications mentioned above shared geometry modules, but had different
local update code, whereas the second and third applications had
different geometry modules but shared the local update code.

\subsection*{Related work}

Recently exciting claims have been made for performance ``parity''
between certain functional languages (specifically SISAL) and
Fortran \cite{Can}.  SISAL is an applicative language designed for
scientific and numerical programming.  It imports imperative-style
constructs for expressing iteration and array construction, and
apparently successfully exploits these features to generate code
competitive with imperative languages.  We have done some preliminary
experimentation with SISAL, and the results have been promising.

Other work on scientific applications of functional language, including
our FAST work and work in the Flare project, has concentrated on
the advantages of high-level declarative languages, such as Haskell,
rather then absolute performance.

SISAL (high performance, limited expressiveness) and Haskell (high
expressiveness, limited performance) represent two extremes of the
functional programming spectrum.  Recently there have been some moves
to bring these camps together in a ``parallel Haskell'' effort \cite{Arv}.

% I don't know whether we can really cite this---all I have is a
% usenet posting:
% 
%   ``pH: a parallel Haskell'',  Arvind, Lennart Augusston, Jamey
%   Hicks, Rishiyur Nikhil,  Simon Peyton-Jones, Joe Stoy,
%   John Williams.
%
% It has all these names on, but I get the impression it's really just
% Arvind trying to sell Id under a different syntax.  Maybe I'm too
% cynical.

\subsection*{Research experience}

Mr Hugh Glaser has been researching into functional language systems
for more than 10 years. He is a Senior Lecturer in the Department of
Electronics and Computer Science at the University of Southampton.
Previously he was a Research Fellow at Imperial College, where he was
Project Director of the Imperial team on the Alvey Flagship Project,
under Prof John Darlington and Prof Mike Reeve.  He has also been
involved in other parallel programming research projects, including the
programming environments workpackage of the Genesis ESPRIT project. He
is currently funded under GR/H19439 (Distributed Prolog Execution.)

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 number of projects, including the development
of the parallel benchmark suite for the Genesis project.

Dr Bryan Carpenter is a theoretical physicist by training, and worked
as a Research Fellow at Edinburgh and DESY in Hamburg. Since then he
has worked in Computational Physics, and has been involved in the
Supernode, Genesis and Puma projects in turn.

\section*{Programme}

\subsection*{1. Further research}

It is proposed to build on the FAST work on scientific applications
described above, and extend it in a couple of directions.

\subsubsection*{Stream parallelism}

The implementation model used has an obvious direct mapping to a
parallel machine.  However, to obtain useful acceleration a number of
issues will need to be resolved, the most obvious of which is the
question of granularity.

The ``array of streams'' model gives a very fine granularity, with
probably unacceptable overheads.  On the other hand the ``stream of
arrays'' model gives very coarse granularity---{\em no} explicit
process parallelism!

Compromise will be required, and some trade offs will need to be
incorporated into the framework.

\subsubsection*{Grid geometry}

In the earlier work some promising techniques were developed for
handling grid geometries in an abstract way, based on generalised
Haskell arrays incorporating ``topological'' information.

The problems studied so far had relatively simple geometries; they are
regular and static. There are other, more general, algorithms that
fit into the same general paradigm, but which are irregular or
dynamic.  A dynamic algorithm such as Multigrid, for example, will fit
naturally into the framework already provided.  The approach to lattice
topology adopted in the earlier work may be generalised to incorporate
``simplicial maps'' for moving between grids.

Such algorithms will be investigated, and our geometric techniqes
will be extended to encompass them.

\subsection*{2. Comparative Review of programming languages}

In addition to these research avenues, we will undertake to produce a
couple of more concrete outputs.

Firstly, we want to evaluate the merits and demerits of functional
programming in the scientific domain, and do this in as systematic a
way as possible.  This will involve selecting a set of kernel
algorithms, and a representative set of target languages.

The kernels will be short (less than 100 lines, say) and as varied as
possible.  For selection as a kernel, an algorithm should be either
\begin{description}
\item{a)}
representative---the kernels should include algorithms widely used in
scientific programming---or
\item{b)}
``interesting''.  We will try to include algorithms which, for example,
involve non-trivial patterns of array update when coded imperatively.
\end{description}
Promising application domains from which to extract these kernels
include
\begin{itemize}
\item Monte Carlo simulations (eg, from condensed matter physics).
\item Advanced PDE solvers (eg, multigrid).
\item Finite element methods.
\item Computational fluid dynamics.
\end{itemize}

Each algorithm will be encoded in the target set of languages.  This
set will presumably include Fortran 90, SISAL, a more conventional
eager functional language such as SML, and Haskell.  The idea is to
choose a spectrum of languages from the traditional imperative to the pure
functional.

The objectives will be
\begin{enumerate}
\item
To isolate any real problems that might exist in putting typical
array-oriented problems into functional languages.  Is there any
important lack of expressiveness?
\item
To explore the advantages of functional languages for this kind of
programming.  Some researchers have reported that laziness is not
particularly useful in scientific programming.  Our experience has
been that it can be used effectively, but we need further evidence.
\item
Although we do not wish to emphasize absolute performance unduly at
this stage, the suite will be useful for benchmarking.
\end{enumerate}

\subsection*{3. Full scale demonstrator application}

Secondly we will produce one full-scale demonstrator application, taken
from one of the domains mentioned above.  This will be coded in a
functional language, probably Haskell.  The intention is that the
program should be capable, in principle at least, of producing useful
scientific data.  It should have at least the same IO facilities as a
typical scientific application coded in an imperative language.  The
demonstrator application will have an interactive graphical interface.

\section*{Resources}

We have requested funding for a named individual, Dr Bryan Carpenter,
whose research experience is detailed elsewhere in this proposal.
His experience and abilities are ideal for the proposed research, and
it is because of the quality of Dr Carpenter's work that this
application is being made.

A high performance workstation has been requested which will provide
the development platform for the software. This will enable Dr
Carpenter to experiment with applications that require both
significant compilation costs and are computationally intensive.

Some consumables associated with the project have been identified,
such as magnetic media for archiving, as well as the costs of
connecting the workstation to the network.

\section*{Applications, Collaboration and Exploitation}

There are no collaboration or exploitation agreements in place,
although the successful completion of the project will
result in a system that can exploit state of the art parallel hardware
to good effect.  Since all the results will be in the public domain,
however, direct commercial exploitation is inappropriate.

\bibliography{../refs}

\end{document}



