\section{Mapping Plans and Strategies}

In this section we discuss reasonable choices for
mapping continuous processing applications to multiprocessor
computers, and discuss the problem of finding the
best mapping plan.


\subsection{Mapping Plans}

In contrast to data parallel scientific computing, the strategy of
letting one program code block at a time utilize the whole machine
appears to be a poor choice for continuous processing applications.
Rather, in many cases the best approach is to structure
the machine code so all program modules are executing concurrently at
a rate the meets exactly the computation requirement\footnote{In
current practice, a single processor is often multiplexed among
program modules for different stages of processing, but because
coarse-grain processing must be used to attain economical performance
with conventional processors,
large buffers for intermediate data must be used and high latency of
results occurs. With multiprocessing, assigning different modules to
distinct processors will usually yield better resource utilization.}.


Given an estimate of the load to be handled by each code module,
we must decide how many processing elements should be
actively executing each module.
For each program module, two reasonable mapping possibilities are apparent:

\begin{enumerate}

\item
{\bf Allocate:} Assign to the program module the exact number of processing elements
needed to achieve the overall computation rate the module requires.

\item
{\bf Distribute:} Spread the computation load of the module uniformly over all
processing elements

\end{enumerate}

The choice between the {\bf allocate} and {\bf distribute} strategies
may be made independently for each module, but
those processing elements dedicated to program modules for which
the {\bf allocate} strategy is chosen are not in the set over which
the work of the remaining modules may be spread.
Which choices lead to better performance depends on the relative
amounts of inter-module communication and intra-module communication,
and on how well the loads match up with processing element capacities.

Note that if the computation rate demanded by some program module
requires the performance of several processing elements, then the
program module must offer sufficient opportunities for
concurrency that the processing elements can be fully utilized.
Otherwise the computation is not feasible on the target
multiprocessor.

Where the input of a module is an array of streams, a plan
in which the modules producing the individual streams
are executed by the same processing element as that assigned
to the corresponding part of the array-processing module
is likely to perform better by avoiding some communication cost.

An advantage of assigning a limited number of processors to
chosen modules is that it is then not necessary to load
all program modules into (or make them accessible from)
every processor.

In data parallel scientific computation, a major issue is aligning
the distribution of various data arrays so as to minimize
communication. In continuous processing computations, this issue
has less impact. On the other hand, it is beneficial to distribute
the work of the {\tt TwoDimFilter} and {\tt PeakDetect} modules
over processing elements in aligned fashion.


\subsection{Mapping Plans}

On the basis of the above considerations we propose the following
class of mapping plans for continuous processing programs:
A {\em mapping plan} is a specification for each node of the
program description tree as to whether execution of the program
section described by the subtree is to be evenly distributed over
all processing elements ({\bf distribute}), or is to be executed by
a group of dedicated processing elements ({\bf allocate}) sized to
accommodate the estimated load of that program section.

Table~\ref{mapping-plans} gives three reasonable proposals for
mapping the optical surveillance computation. Under Plan A, the
work of each of the five modules is distributed over all processing
elements. This choice is attractive because
it eliminates all inter-processor communication except
that due to boundary exchange in algorithms {\tt TwoDimFilter} and
{\tt PeakDetect}. In Plan B, a group of processors is dedicated to
the work of algorithms {\tt TwoDimFilter} and
{\tt PeakDetect}, but these are both distributed across the group
to avoid communication costs for passing data from {\tt TwoDimFilter}
to {\tt PeakDetect}. The relative merits of these plans are discussed
in the following section.



\subsection{Finding the Optimal Mapping Plan}

Given a mapping plan and characteristics of the target
multiprocessor including the number of processing elements, it
is straightforward to estimate performance parameters
for a mapping plan. Given the total operation count,
the number of processors, and their speed, the rate of
computation may be estimated. The costs of process
synchronization may be approximated from characteristics of the
target architecture and program structure information in
the description tree. The mapping plan induces a communication
load from which it can be estimated whether the computation
is compute bound or communication bound.

Thus the following approach should help find the optimum
mapping plan:

\begin{enumerate}

\item
Determine computation rates and load parameters for each node of the graph.

\item
Generate several plausible mapping plans based on the given
program description tree and estimates
of performance parameters.

\item
Evaluate each proposed mapping plan by constructing target
machine code and determining accurate processor and
communication loads

\item
Select the best mapping plan for the user's objective.

\item
Construct the final machine code.


\end{enumerate}

\begin{table*}[tb]
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|}
\hline
Module & BaseRemove & SpikeAdapt & Nyquist & TwoDimFilter & PeakDetect  \\  
\hline
\hline
Plan A & \multicolumn{5}{c|}{\bf distribute} \\
\hline
\hline
Plan B & \multicolumn{5}{c|}{\bf allocate}   \\
         \cline{2-6}
       & \multicolumn{3}{c|}{\bf distribute}
       & \multicolumn{2}{c|}{\bf distribute} \\
\hline
\hline
Plan C &  \multicolumn{5}{c|}{\bf allocate}  \\
         \cline{2-6}
       & \multicolumn{3}{c|}{\bf distribute}
       & \multicolumn{1}{c|}{\bf distribute}
       & \multicolumn{1}{c|}{\bf distribute} \\
\hline
\end{tabular}
\end{center}
\caption{\label{mapping-plans}Three mapping plans for the optical
   surveillance problem.}
\end{table*}






