\section{\label{analysis}Program Analysis}


In this paper we consider only programs having an overall structure
that supports the continuous processing of streams of data. In
these programs each module
operates on data streams, produces
a data stream, and runs continuously during program execution.
The overall structure of such programs is an acyclic interconnection
of such modules. This is
in contrast to data parallel scientific codes for which the
original Paradigm compiler was designed. There the top level
program structure is a main loop in which the loop body is an
acyclic combination of code blocks that define array values,
as in the following program segment
\begin{verbatim}
  Z: array [real] :=
    for i in 1, n
      Y: real :=
        if i = 1|i = n
        then X[i]
        else 0.5 * ( X[i-1] + X[1+1] )
        end if
    returns array of Y
    end for
\end{verbatim}
This parallel expression in Sisal
defines an array value {\tt Z}, each (internal) element of which is the
average of the two adjacent elements of a given vector {\tt X}.
The conditional expression provides special
treatment of the end elements of {\tt Z}. All instances of the body
expression may be evaluated concurrently. In general, data parallel
code blocks may be nested ``for'' expressions that define multidimensional
arrays, and may include reduction operations that apply associative
operators over specified dimensions of the defined array.
In the Paradigm Compiler \cite{Dennis89}, programs
having this structure are analyzed and transformed into
data parallel programs for the CM-2 Connection Machine.


\subsection{Stream-Processing Programs}

The present study explores the prospects
for static analysis and mapping of continuous stream-processing
computations such as the optical surveillance problem. Thus
we envision a new version of the Paradigm Compiler that will
transform, and analyze such programs and generate machine code
for multiprocessor computers. Given a program that
is amenable to static resource management, the Analyze module
of the rebuilt Paradigm Compiler will provide program
descriptions that may be used to plan the mapping of the
program onto a parallel computer and to construct
code in the target machine language.

The job of program analysis has several parts:

\begin{enumerate}

\item
Identify the program modules (code blocks)

\item
Check the conditions that permit static mapping to
be used

\item
Extract parameters for each program module for use in
performance estimation

\item
Determine the relative computation rate for each module

\item
Construct a program description tree containing the
results of analysis

\end{enumerate}


\subsection{Program Transformation}

The identification step includes examining
recursive function definitions to determine whether
they are tail-recursions and have equivalent iterative
dataflow graphs. A method for doing this
has been given in \cite{Dennis95}.

In the absence of conditional expressions in their bodies,
the tail-recursive
function definitions express functions that process input
streams into output streams where the numbers of output
elements emitted is related to the number of input elements
absorbed as a ratio of integers, a rational number.
If the bodies of these function definitions contain
conditional expressions, it may be that the module does not
have a fixed ratio of output elements emitted to input elements
absorbed, and only a range of values for the ratio can be
determined through static analysis. Such situations appear
to be rare in practical signal processing
computations, for their existence would imply a non-uniform
sampling rate. In our example, the {\tt BaseRemove} function
contains a conditional, but yet has a fixed input/output ratio of unity.
Given these ratios (or bounds on relative rates) a rate (or range
of rates) can be calculated for every module.

Figure~\ref{filter-graph} illustrates the results of program transformation
performed by the compiler. It is a dataflow graph that
represents the continuous iterative processing of a stream
of data arrays by the {\tt TwoDimFilter} module. The {\bf Group}
operator at the top of the figure extracts successive groups of
three elements from the input stream. Each of these elements is a
$w$-element array. On the next cycle of operation, the selected
group starts with the element one position later in the input stream.
Between the square brackets is the conventional dataflow graph of
body of the {\bf ArrayProducer} code block. It is not presented
in fine-grain form to avoid confusing detail. The brackets themselves
represent the {\bf ForAll} code block that defines each array element of the
output stream.  The opening (top) bracket is labeled with the range
of indices for elements in the generated array.
The {\bf EmitStreamElement} operator simply
appends its input array onto the output stream.

\begin{figure}[t]
\begin{center}
\illustrationx{filter-graph}{3.2in}
\end{center}
\caption{\label{filter-graph}Transformed program module for
the {\tt TwoDimFilter} function.}
\end{figure}

We assume that the usual architecture-independent optimization
steps---constant folding, common subexpression
elimination,etc.---have been
performed.
Also, and this is especially important in signal processing
applications, shift operations are used to implement multiplication
by known constants whenever this is more efficient (although this
depends on the detailed design of the arithmetic units of the
processor).


\subsection{The Program Description Tree}

The objective of program transformation and analysis is to
provide information on which the choice of a good mapping
of program modules and data structures onto
a target multiprocessor may be made. We represent the
results of analysis as a {\em program description tree} or PDT.
Each node of the PDT corresponds to a syntactic element of the
program analyzed. The node types include
{\bf Graph} nodes that represent acyclic interconnections of
primitive operators and code blocks, and node types that
represent the several kinds of code blocks. A {\bf ForAll} node
describes a code block that determines an array value each
time it is executed. A {\bf StreamProducer} node describes a code block
that produces an endless stream of simple scalar elements, and
an {\bf ArrayProducer} node describes a code block
that produces an endless stream of array values. The nodes of the PDT
contain data type information and the index ranges for constructed
arrays. {\bf Graph} nodes contain counts of operators of various
kinds, and could also contain information about degree of
parallelism such as the critical path length of the graph.


\subsection{Analysis of the Example}

The optical surveillance program satisfies the conditions
for static mapping. Each recursive function definition is
tail-recursive and may be transformed into an iterative
dataflow graph with a fixed memory requirement for each
top-level invocation. Moreover, each of the resulting
transformed modules maps one or more input streams into
an output data stream, and the program in entirety is
an acyclic composition of these modules, as specified
by the top-level function {\tt Process}. The program
description tree for the optical surveillance example
is shown in Figure~\ref{descr-tree}.

\begin{figure*}[t]
\begin{center}
\illustrationx{descr-tree}{5.5in}
\end{center}

\caption{\label{descr-tree}Program
    description tree for the signal processing example.}
\end{figure*}


\subsection{Computation Rate and Load Estimate}

The program description tree contains sufficient information
to determine the relative computation rate for
each program module, and the approximate fraction of the
total computation load each module is responsible for.
These data are calculated for the optical surveillance problem
in Table~\ref{load-table}. We (arbitrarily) take the processing
of one array of data by {\tt TwoDimFilter} (or by {\tt PeakDetect})
as the basic {\em compute cycle} of the computation. For each
program module, the table shows the number of operations performed
in each execution of a module, the width of the
data stream processed by the module, and the number of instances
of execution of the module for one compute cycle. These yield the
operation count per cycle and the load fraction for each module.
These data are used in Section~\ref{performance} to estimate the
computation rate and latency for selected mappings of the example.

\begin{table*}[tb]
\begin{center}
\begin{tabular}{|lrrccrr|}
\hline
Module       & Rate  & Operations & Width  & Count &  Total   &  Fraction\\
\hline
\hline
BaseRemove   &   4   &   6        &    1   & nw    &   49152  & 0.353 \\
\hline
SpikeAdapt   &   1   &  39        &    n   & w     &   79872  & 0.574 \\
\hline
Nyquist      &   1   &   3        &    0   & w     &     768  & 0.006 \\
\hline
TwoDimFilter &   1   &  11        &  w-2   & 1     &    2794  & 0.020 \\
\hline
PeakDetect   &   1   &  26        &  w-4   & 1     &    6552  & 0.047 \\
\hline
\hline
Total        &       &            &        &       &  139138  & 1.000 \\
\hline
\end{tabular}
\end{center}
\caption{\label{load-table}Calculation of load fraction for each
   program module from data in the program description tree. The total
   operations and load fractions are calculated for $w = 256$ and
   $n = 8$.}
\end{table*}
