\section{An Example: Optical Surveillance}

The computation we have chosen to illustrate the proposed
mapping strategy is derived from a collection of procedures
for processing information from a sky-scanning optical
surveillance device
and detecting objects in its field of view. The application has
similarities to radar signal processing. There are many sensors,
several for each line of the scanned image. These
signals are conditioned, smoothed and down-sampled before
a two-dimensional filter is used
to suppress unimportant detail. A peak detection
algorithm identifies points in the image that should be
analyzed further as potential objects to be reported.
A bock diagram of the computation is shown in Figure~\ref{process-diag}.

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

\illustrationx{composition}{6in}

\end{center}
\caption{\label{process-diag}Structure of the optical surveillance
   data processing algorithms.}
\end{figure*}

Each module in the diagram may be characterized as a function that
transforms a stream of input data into a stream of output
data. Hence it is natural to specify them using a language (Sisal)
that includes streams as standard data types and supports
analytic and constructive operations on streams.

In Sisal a {\em stream} is a sequence of values
which may be infinite (unending).
A stream of integers is a natural representation for a
signal that has been converted into digital form.
Interconnecting modules that process streams of data is a
powerful means for combining program parts to build larger
modules and is well matched to the
needs of signal processing tasks. Thus the combination of
processing modules shown in Figure~\ref{process-diag} may
be expressed in Sisal as the composition of functions in
Figure~\ref{composition}. The Sisal code for the five
component functions is given in the appendix of this paper.

\begin{figure}[tb]\small
\begin{verbatim}
%Type Declarations

type Signal = stream [integer];
type ImageStream = array [ stream [integer] ];
type DataStream = stream [ array [ integer ] ];
type MarkStream = array [ stream [boolean] ];

%The Top-Level Function

function Process (
   D: DataStream;
   w: integer;
   n: integer
   returns MarkStream )

   let
      R := for i in 1, w
      returns array of
         let S := for j in 1,n
            returns array of
               BaseRemove (D[i,j])
         Nyquist ( SpikeAdapt ( S[i], n ) )
      end for
   in
      PeakDetect ( TwoDimFilter ( R, w ) )
   end let

end function
\end{verbatim}
\caption{\label{composition}Type declarations and the
principal function {\tt Process} for the optical surveillance
computation, written in Sisal as a composition of
stream-processing functions.}
\end{figure}

This use of function composition for signal processing
has been discussed in~\cite{Dennis95}, where we showed
how to transform tail-recursive functions on streams
into non-recursive dataflow graphs that may be executed
efficiently by suitable fine-grain parallel
computers~\cite{DennisGao94,Dennis91}
%% [Also DCC Report to NASA, 1989.]
The use of dataflow graphs as a natural means for specifying
signal processing applications has also been studied in~\cite{HoLeeMes88},
and the idea of compiling signal processing programs from
block diagrams was described as early as~\cite{KellyLocVys61}.

From this example we see that complete signal processing tasks
may take the form of a
set of processing modules, each generating a stream of values
that is passed to other modules for further processing. Thus
the overall computation may be described by a directed acyclic
graph in which the nodes are stream processing modules such
as those we have presented, and each link indicates
a producer/consumer relationship between a pair of
modules. It is well-known that such interconnections of
modules may lead to deadlock if the graph contains (undirected) cycles,
and the temporary storage
for stream elements in each link is bounded in capacity. Given
the structure of stream processing programs expressible
in Sisal, a compiler can detect these situations and warn the
user of the deadlock possibility.
