\section{Static Mapping}

The problem of implementing programs written in high level
languages on parallel computers may be approached in two
fundamental ways according to the philosophy of managing
processing and memory resources. One may strive to implement
a very general model of parallel computing and implement it
by a suitable combination of architectural features and run-time
services so that all scheduling and memory allocation decisions
are performed during program execution. This general approach
is exemplified by the Monsoon mutiprocessor \cite{PapadopoulosCul90},
but the mechanisms
have not evolved to the level of efficiency required to
attract practical usage. The second approach is based on making
most memory management decisions at compile time. This can yield
very efficient exploitation of multiprocessors built of
conventional processors for computations having
a suitable regular structure. This second approach has been the basis
for the development of the data parallel model and its implementation
in such work as the Thinking Machines Fortran compiler,
\cite{Sabot92} the definition of High Performance Fortran and
advanced work in Prof. Kennedy's group at Rice University.

The data parallel approach can also be followed for programs
expressed in functional programming languages with significant
advantages. It is simpler to identify the program blocks that
are suitable for data parallel implementation, and the global program
analysis needed to determine optimum alignment and mapping for
the arrays of a program is more readily accomplished.
This is because functional language programs do not make use
of side effects, and each use of any data definition is
readily identified. This has been done
in the Paradigm compiler~\cite{Dennis89} designed and built by the author for
the Sisal language and targeted for the CM-2 Connection
Machine.


\subsection{Compiler Structure}

The Paradigm compiler was designed to identify
the principal data structures 
constructed by a program through global compile-time
analysis, and to map these structures onto the processing
elements of the target machine. The structure of the
compiler is shown in Figure~\ref{compiler-struct}.
It consists of a conventional Front End that parses and checks
source language modules, an Analyze module that  identifies
code blocks in the program, and a Code Constructor that
implements each code block on the basis of mapping specifications
derived with optional advice from the user \cite{Dennis88,Dennis89}.

\begin{figure}[tb]
\begin{center}

\illustrationx{compiler-struct}{3.2in}

\end{center}
\caption{\label{compiler-struct}Structure of the Paradigm
   compiler.}
\end{figure}

Our goal requires some
departure from the typical structure of programming language
support systems. Efficient machine code programs for large-scale
parallel computers can be generated only if the compiler is able
to consider the entire collection of program modules involved
in a job in making decisions regarding how the computation
should be mapped onto the target machine. This implies that
the linking of program modules should be accomplished prior
to the compiler's analysis and optimization decisions.
A second change is more fundamental: instead of carrying
out optimization as a sequence of independent steps, each
of which supposedly leads to an ``improvement'' of the code,
we perform an analysis of the given code, determine the best
mapping strategy, then synthesize machine code according to
the specified mapping.

The Sisal functional programming language \cite{McGrawEtAl85} is particularly
attractive for implementing this approach. The
absence of global variables and
the clear differentiation of arguments and results
of function modules in the Sisal language make it easy
for a compiler to analyze source programs and identify
the parts of the code that define the major data structures.
We call these parts of the source language program {\em code blocks}.

The data structures appropriate for scientific computation
are large multi-dimensional arrays of
numerical data. Each code block defines an array value and
represents a computation that may be spread over the
processing elements of the machine according to a chosen
assignment (or mapping) of array elements to processing
elements. This is the essence of data parallel computation.
The parallel iteration expression of the Sisal language provides
a convenient  high level notation for writing data
parallel algorithms.


\subsection{Application to High Performance Signal/Image Processing}

Another area that can exploit massively parallel computation
is high performance signal and image processing. In these
applications large amounts of parallelism exist, but
it takes different forms: (1) producer/consumer concurrency: the
possibility of executing two program modules concurrently when
one (the {\em consumer}) processes a stream of data generated by the
other (the {\em producer});
and (2) Simultaneous application of several instances of
functions. The use of stream data types plays a central role
in expressing such computations in a high level form that
permits automatic analysis. The rest of the paper is devoted to
describing this process, illustrating its application to
a practical signal processing problem, and studying the performance
achievable for two multiprocessor architectures.
