\documentstyle[twocolumn,prog2]{article}
\include{psfig}
\include{caption2}
\pagestyle{empty}

%set dimensions of columns, gap between columns, and space between paragraphs
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.8in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.19in}
\setlength{\parindent}{1pc}

\makeatletter
%as Latex considers descenders in its calculation of interline spacing,
%to get 12 point spacing for normalsize text, must set it to 10 points
\def\@normalsize{\@setsize\normalsize{12pt}\xpt\@xpt
\abovedisplayskip 10pt plus2pt minus5pt\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus3pt\belowdisplayshortskip 6pt plus3pt
minus3pt\let\@listi\@listI} 

%need an 11 pt font size for subsection and abstract headings
\def\subsize{\@setsize\subsize{12pt}\xipt\@xipt}

%make section titles bold and 12 point, 2 blank lines before, 1 after
\def\section{\@startsection {section}{1}{\z@}{24pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\large\bf}}

%make subsection titles bold and 11 point, 1 blank line before, 1 after
\def\subsection{\@startsection {subsection}{2}{\z@}{12pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\subsize\bf}}
\makeatother

\begin{document}
\bibliographystyle{plain}

\date{}
\title{\Large\bf The Assign Parallel Program Generator\thanks{The complete version of this paper appears as Carnegie Mellon Technical Report CMU-CS-91-141. The research was supported in part by Defense Advanced Research Projects Agency (DOD) monitored by DARPA/CMO under Contract MDA972-90-C-0035, and in part by the Office of Naval Research, Air Force Office of Scientific Research, and Naval Ocean Systems Center under Contract N00014-90-J-1939.}}
\author{David R. O'Hallaron\\
School of Computer Science\\
Carnegie Mellon University\\
Pittsburgh, PA, 15213
}

\maketitle

%I don't know why I have to reset thispagesyle, but otherwise get page numbers
\thispagestyle{empty}

\subsection*{\centering Abstract}
{\em {\sc Assign} is a tool for building large--scale applications, in
particular signal processing applications, on distributed-memory
multicomputers.  The first target machine is iWarp, a multicomputer
system developed jointly by Intel Corporation and Carnegie Mellon
University. This paper gives a high-level introduction to {\sc Assign}
}.

\section{Introduction}
\label{sec:intro}
{\sc Assign} is a tool for building large--scale applications on
distributed--memory multicomputers.  The programming model is the
coarse-grained {\em flowgraph}, where nodes correspond to
coarse--grained sequential computations and directed edges correspond
to FIFO queues\cite{babb84,lee87}.  Given a flowgraph, {\sc Assign}
automatically generates a parallel program consisting of a C program
for each cell (processor) in the target machine.  Details such as
partitioning the flowgraph, placing and routing the partitioned
flowgraph, creating communication pathways, transferring data from
cell to cell, flow control, and balancing workload across processors
and communication pathways are all handled automatically.

{\sc Assign} is intended for applications that can be described with
static coarse-grained flowgraphs. In particular, it is designed for
large--scale digital signal processing (DSP) applications, which are
described very naturally using coarse-grained flowgraphs.

Aside from the obvious merits of automating machine--dependent
details, the primary virtues of {\sc Assign} include the hierarchical
nature of its flowgraphs, the ability to parameterize both flowgraphs
and individual signal processing operations, the ability to model and
compile large graphs with thousands of nodes, a flexible and
general--purpose mechanism for transferring data to and from the host,
and a minimum of run-time scheduling overhead. The primary limitation
is that it is suitable only for those applications that can be modeled
as static, coarsed-grained flowgraphs. 

The first target machine is the iWarp\cite{borkar88,borkar90}, a
multicomputer system developed jointly by the Intel Corporation and
Carnegie Mellon University. We are currently using {\sc Assign} to
generate working programs for the first 64-cell iWarp systems delivered
by Intel to Carnegie Mellon.

In this paper, we introduce {\sc Assign}. The emphasis is on
techniques for writing {\sc Assign} programs, rather than on the
details of the automatic mapping and code generation algorithms.
Section \ref{sec:overview} give an overview. Section
\ref{sec:flowgraphs} describes the underlying flowgraph model.
Sections \ref{sec:nodefunctions} and \ref{sec:graphgens} describe the
techniques for building Assign programs.  Section \ref{sec:previous}
discusses related work.  A more detailed discussion is given in 
\cite{ohallaron91b}.

\section{Overview}
\label{sec:overview}
\subsection{Flowgraphs}
The flowgraph is the underlying programming model for {\sc Assign}.
Under the guise of various names such as block
diagrams\cite{oppenheim83}, large-grained dataflow
graphs\cite{babb84}, synchronous dataflow graphs\cite{lee87}, and
signal flow graphs\cite{printz89}, flowgraphs have been used for years
in the literature and in practice to model DSP applications.

A flowgraph is a collection of {\em nodes} and directed {\em edges}.
Nodes represent computations and edges represent FIFO queues.  Each
node iterates an infinite number of times. Each iteration, the node
consumes some data items from each of its input edges, performs a
computation on the inputs, and produces some data items on each
of its output edges. The sizes of the inputs and outputs are indicated
by integer edge labels.

Figure \ref{fig:flowgraph} shows an example flowgraph for an
application that performs the same operations on two independent data
streams.  
\begin{figure*}[htb]
\centering
\fbox{
\psfig{figure=flowgraph.eps}
}
\caption{Example flowgraph. {\rm Edge labels denote the number of data items produced and consumed each time a node is invoked.}}
\label{fig:flowgraph}
\end{figure*}
The edge labels correspond to the number of data items
produced and consumed each time a node is invoked. For example, the
node labeled {\em fir} corresponds to an FIR filter that inputs 512
data items, performs a 2:1 downsampling operation, and outputs the
result. The FFT is invoked whenever 512 data points have arrived.
Thus, for each invocation of the FFT, there are two invocations of the
FIR filter.

{\sc Assign} flowgraphs are hierarchical.  A node in a graph can
correspond to a subgraph, so that graphs can be constructed
hierarchically out of smaller graphs. This is illustrated in Figure
\ref{fig:hierarchy}.
\begin{figure*}[htb]
\centering
\fbox{
\psfig{figure=hierarchy.eps}
}
\caption{The hierarchical nature of flowgraphs. {\rm Here we have a flowgraph model of a real sonar application. The graph consists of two nodes, where each node is itself a subgraph.}}
\label{fig:hierarchy}
\end{figure*}
The example is a real graph of a sonar adaptive beam interpolation
application implemented on iWarp using Assign. At the highest level,
the graph consists of two nodes, where each node corresponds to a
subgraph.

\subsection{Mapping Algorithm}
Assign uses the two-phase mapping algorithm shown in Figure 
\ref{fig:mappingalg}. 
\begin{figure*}[htb]
\centering
\fbox{
\psfig{figure=approach.eps}
}
\caption{The {\sc \bf Assign} mapping algorithm. {\rm The partitioning phase attempts to minimize the maximum load on any particular cell. The placement and routing phase attempts to minimize the number of flowgraph edges shared by any particular physical communication link.}}
\label{fig:mappingalg}
\end{figure*}
The first phase, partitioning, uses an extension of the chain mapping
methods developed in \cite{nicol91} to partition the $M$ nodes of the
flowgraph into at most $P$ blocks, where $P$ is the number of the
cells in the target machine. Since the throughput of the system is
bounded from above by the cell with the maximum load, the optimization
goal of this phase is to find a partition that minimizes the maximum
load on any particular cell.

There are several interesting aspects of the partitioning algorithm.
First, the load model for each cell incorporates communications cost,
and thus the optimal partition does not always use all of the cells.
Second, although the partitioning problem is intractable in general,
the extended chain method we are using is guaranteed to find an optimal
partition in polynomial time if the input flowgraph is a chain
\cite{nicol91}.

The second phase, placement and routing, places the partition blocks
from the first phase on the cells of the target array, and routes any
exposed edges through the cells of the array. The optimization goal of
this phase is to minimize the number of flowgraph edges shared by any
particular physical communications link.  The placement and routing
algorithm is borrowed directly from \cite{menzilcioglu89}.

The interesting aspect of the placement and routing phase is the
simple and beautiful correspondence between exposed graph edges and
iWarp pathways.  Each pathway is set up once when the program is
loaded, and data flow through intermediate cells transparently, with
no effect on any computations on the intermediate cells.

\subsection{System Overview}
{\sc Assign} is a front-end to the existing tools supplied by the
vendor of a parallel machine. For example, an overview of {\sc
Assign}'s place in the iWarp tool chain is shown in Figure
\ref{fig:system}.

\begin{figure*}[htb]
\centering
\fbox{
\psfig{figure=system.eps}
}
\caption{{\sc \bf Assign} system overview. {\rm {\sc Assign} is a front-end to existing tools. Programs can be compiled onto a parallel computer or a Unix host.}}
\label{fig:system}
\end{figure*}

Flowgraphs are created by running a C program called a {\em graph
generator}, which uses a library of {\sc Assign} functions to build
and emit a flowgraph on the standard output.

{\sc Assign} inputs the flowgraph produced by the graph generator
along with a collection of {\em state structures}, which, as we shall
see, are arbitrary user--defined C structures that can be used to
parameterize an application and hold internal state.  On the command
line, the user can specify such options as the number of cells to be
compiled onto, an optimization level that controls the quality and
running time of the mapping algorithm, and the {\em arbitrary} 2D
topology of the target iWarp array.

The output of Assign is a C program that will, at the discretion of
the user, be compiled to run on either the Unix workstation or the
iWarp array. 

\subsection{Programming Overview}

The process of programming applications using {\sc Assign} is
determined largely by (1) the ability to compile flowgraphs onto either
the host Unix workstation or the attached parallel computer, and (2)
the hierarchical nature of the flowgraphs.  The ability to compile
onto the workstation allows us to do most of our testing and debugging
on the workstation rather on the parallel machine.  The hierarchical
nature of flowgraphs allows us to build applications in a sequence of
incremental steps (See Figure \ref{fig:programming}):
\begin{figure*}[htb]
\centering
\psfig{figure=programming.eps}
\caption{Typical process of programming {\sc \bf Assign} applications. {\rm Notice that the system is constructed incrementally and that most of the work is done on the Unix workstation.}}
\label{fig:programming}
\end{figure*}
\paragraph{\bf Step 1: Write node functions.} 
These are sequential C functions, instances of which will correspond
to nodes in the flowgraph. Each of these functions can be tested
independently on the Unix workstation.
\paragraph{\bf Step 2: Generate and test subgraphs.}
{\sc Assign} flowgraphs are hierarchical, meaning that graphs can be
formed by composing smaller subgraphs. Typically, we independently
generate and test a collection of smaller subgraphs on the Unix
workstation, using the node functions developed in the previous step.
As we shall see, flowgraphs are generated by writing and running a C
program called a {\em graph generator}.
\paragraph{\bf Step 3: Combine and test subgraphs.}
Once we are satisfied that each of the subgraphs is producing correct
results, we combine them, {\em without change}, to form the final
graph. The testing of the final graph can be performed entirely on the
Unix workstation.
\paragraph{\bf Step 4: Run final graph on parallel machine.}
When we are satisfied that the final graph is producing correct
results, we can recompile the graph, {\em without change}, and then
run it on the parallel machine. It is important to note that most of
the program development is done on the Unix workstation and not on
the parallel machine.

\section{Flowgraphs}
\label{sec:flowgraphs}

A {\em flowgraph} is a (possibly cyclic)
multidigraph consisting of a collection of {\em nodes} and directed
{\em edges}.\footnote{A multidigraph is a directed graph where multiple edges
are allowed between the same pair of nodes.}  Nodes represent
computations and edges represent FIFO queues.  Each node iterates an
infinite number of times. Each iteration, the node consumes some data
items from each of its input edges, performs a computation on the
inputs, and produces a vector of data items on each of its output
edges. The sizes of the inputs and outputs are indicated by integer
edge labels.  A flowgraph has exactly one {\em source node} (i.e., a
node with no input edges) and exactly one {\em sink node} (i.e., a
node with no output edges).

\paragraph{Nodes.} 
A node is either an {\em atom} or a {\em subgraph node}.  An atom
corresponds to a coarse--grained sequential task such as an FFT or FIR
filter. A subgraph node corresponds to a flowgraph.  Thus, flowgraphs
are hierarchical entities that can be constructed out of instances of
smaller flowgraphs. 

\paragraph{Ports.} 
Each node has a (possibly empty) list of {\em input ports}
and a (possibly empty) list of {\em output ports}. 
Associated with each input port $k$ is a name, a scalar type (int,
float, double, or complex), and an integer {\em consume amount},
$c_k$. Associated with each output port $k$ is a name, a type and an
integer {\em produce amount}, $p_k$.  We will explain the meaning of
the consume and produce amounts later in this section when we
discuss node execution rules.

\paragraph{Node Functions.}
Each node in a graph is associated with a collection of {\em node
functions}, which are C functions that control
the computation performed by a node. There are three types of
node functions: {\em primitives}, {\em dynamic initializer functions},
and {\em input/output functions}.

\paragraph{Primitives.}
Each atom must be associated with a {\em primitive}. A primitive is a
user-written C function that follows {\sc
Assign}'s calling convention. The argument list for a primitive
consists of a (possibly empty) list of pointers to input vectors,
followed by a (possibly empty) list of pointers to output vectors,
followed by an optional pointer to a state structure.  Typical
primitives are FFT's and FIR filters.

\paragraph{Input and Output Functions.}
An atomic source node must have an associated {\em input function}, which is
a user--written C function that returns an input vector of length
$c_k$ for each inport port $k$.  Similarly, an atomic sink node must have an
associated {\em output function} that outputs a vector of length $p_k$
for each output port $k$.  The input and output functions provide a
general-purpose mechanism for handling data transfers between a host
computer and a graph.  {\sc Assign} makes no assumptions about the 
format of the input and output data on the host. 

\paragraph{State Structures and Their Initializers.}
An atom may have internal state in the form of an optional {\em state
structure}, which is an arbitrary C structure.  A pointer to the state
structure is passed to a primitive each time it is invoked.  The
primitive can freely inspect and modify the state structure. State
structures can be initialized at compile time with a {\em static
initializer} and/or at run time with a {\em dynamic initializer}.  A
static initializer is an arbitrary C structure initializer list. A
dynamic initializer is an arbitrary C function that is called once
at run time before the primitive is invoked.

State structures and their initializers provide a general--purpose
mechanism for passing arbitrary parameters to primitives. Examples of
state structure elements include the sizes of the input and output
vectors, precomputed coefficients that are a function of the input size
(e.g, FFT twiddle factors), and dynamic internal state that must be
retained from invocation to invocation, (e.g., previous outputs of an
IIR filter).

\paragraph{Execution Weight.}
Each atom has an {\em execution weight}, which is the estimated number
of cycles consumed by one invocation of its primitive. The execution
weight does not affect the semantics of the flowgraph.  Rather, it is
a hint supplied by the user to help {\sc Assign} balance the workload
across the cells of the iWarp array.

\paragraph{Edges.}
An edge binds an output port on one node to the input port of another
node. Each edge corresponds to a FIFO queue with exactly one writer
and one reader. 

\paragraph{Graph Execution Rules.}
Each atom executes according to the following rules: Initially, the atom
calls an optional dynamic initializer. This is followed by a (possibly
infinite) sequence of the following steps:

\begin{enumerate}
\item Remove $c_k$ data items from each input port $k$. If this is a 
source node, the data for each input port is received via an
invocation of the input function. Otherwise, the data for each port
$k$ comes from input queue $k$. 

\item Invoke the associated primitive using as inputs the $c_k$ data items
consumed from each input port $k$.

\item Write $p_k$ data items to each output port $k$.
If this is a sink node, the data written to the port is
passed to the output function, which sends the data to the host
computer. Otherwise, data written to the output port $k$ is deposited in
output queue $k$.
\end{enumerate}
Each atom executes independently according to the atom 
execution rules; each graph node executes the corresponding
subgraph, with the input edges of the graph node bound to the input
ports of the subgraph's source node and the output edges of the node
bound to the output ports of the subgraph's sink node.

The flowgraph model we have described in this section is equivalent to
the synchronous dataflow model of Lee and Messerschmitt
\cite{lee87}.  It is sufficiently powerful to model real applications
with multiple sampling rates and redundant computations\cite{printz89}.

\section{Writing Node Functions}
\label{sec:nodefunctions}

Typically, the first step in building an {\sc Assign} application is
writing the appropriate node functions. These functions (primitives,
dynamic initializers, input/output functions) can be placed in a
single file or separate files according to taste.  In this section, we
describe techniques for writing node functions.

\subsection{Primitives}
The simplest {\sc Assign} primitive has no input or output arguments.
\begin{prog}
	hello()
	{
		printf(``hello, world\n'');	
	}
\end{prog}
A somewhat more useful primitive inputs a vector of 16 {\tt floats},
increments each element of the vector, and places the result in an
output vector. 
\begin{prog}
	incr16(inp, outp)
	float *inp, *outp;
	{
		int i;

		for (i=0; i<16; i++)
			*outp++ = (*inp++) + 1;
	}	
\end{prog}
Notice that the argument list is a list of {\em input arguments}
followed by a list of {\em output arguments}.  Each input and output
argument is a pointer to a vector of either {\tt int}, {\tt float},
{\tt double}, {\tt complex}, {\tt complex\_int}, or {\tt
complex\_double}, where the complex types are defined by
\begin{prog}
	typedef struct {float r, i} complex;
	typedef struct {int r, i} complex_int;
	typedef struct {double r, i} complex_double;
\end{prog}

\subsection{State Structures}
Of course, a primitive like {\tt incr16} would be a lot more useful if
it worked on vectors of any size. Fortunately, {\sc Assign} provides a
mechanism called the {\em state structure} for writing such
general--purpose primitives. To use a state structure in a primitive,
we define the structure in an include file
\begin{prog}
	struct incr_state {
		int size;
	};
\end{prog}
Note that each state structure must be defined in some {\tt .h}
include file. Then we add a state structure argument to the end of the
argument list.
\begin{prog}
	incr(inp, outp, sp)
	float *inp, *outp;
	struct incr_state *sp; 
	{
		int i;

		for (i=0; i < sp->size; i++)
			*outp++ = (*inp++) + 1;
	}
\end{prog}
When the graph is created, each {\tt incr} node will be allocated
a {\em distinct} state structure defined by the tag {\tt incr\_state}.
Thus, a graph might contain many {\tt incr} nodes, each using the
identical {\tt incr} primitive to operate on different sized input
vectors.

Much of the power of the state structure derives from the fact that
the fields are arbitrarily defined by the user. For example, an
$n$-point complex FFT can use the state structure to hold the size of
the input vector and a collection of dynamically precomputed complex
coefficients.

\subsection{Input and Output Functions}
If we ever plan to associate {\tt incr} with a source or sink node,
then we must write input and output functions for that node so that it
can transfer data to or from the host computer.  We typically place
these functions in the same file as the primitive.  For example, this
input function is invoked each time an {\tt incr} source node reads
its input ports.
\begin{prog}
	incr_in(inp, sp)
	float *inp;
	struct incr_state *sp;
	{
		int i;

		for (i=0; i<sp->size; i++)
			scanf("%f", &(inp[i]));
	}
\end{prog}

\subsection{Dynamic Initializers}
As we learned in the previous section, some or all of the elements
of the state structure can be initialized {\em statically} when a 
a node is created or {\em dynamically} at run time before the graph is
executed. We will learn how to statically initialize state structures
in the next section. To dynamically initialize a state structure, we
provide a C function. For example, given the following state structure,
\begin{prog}
	struct fft_state {
		int n;            /* number of complex points */
		int isign;        /* 1 is fft, -1 is ifft */
		complex wp[MAXN]; /* twiddle factors */
	};
\end{prog}
we might use a dynamic initializer of the following form to 
precompute the twiddle factors of an $n$-point complex FFT.
\begin{prog}
	void fft_init(sp)
	struct fft_state *sp;
	{
		...
	}
\end{prog}

\section{Writing Graph Generators}
\label{sec:graphgens}

Once a collection of node functions is assembled, the next step 
is to create a flowgraph using a graph generator. A graph generator
is a C program that uses a library of {\sc Assign} functions to
emit a flowgraph on the standard output.

For the initial implementation of {\sc Assign} we have chosen to
provide a procedural interface rather than a visual interface. Each
approach has its advantages and disadvantages.  The chief advantage of
the procedural approach is that we can exploit the tremendous
expressive power of C, including iteration, conditionals, functions,
and recursion.  This expressive power is extremely helpful for
generating large graphs with hundreds or thousands of nodes.  Another
key advantage is that command line arguments and manifest constants
can be used to parameterize the graph generator, so that one graph
generator can produce an entire family of graphs.  

The main disadvantage of the procedural approach is that people tend
to think of flowgraphs as graphical objects. We are investigating
existing visual interfaces, and if we are able to find a system with
enough expressive power to handle large parameterized graphs, it will
not be difficult to replace the existing interface.

The library of graph generator functions provided by {\sc Assign}
includes functions that create an empty graph, associate source and
include files with a graph, add an atomic node to a graph, add a graph
node to a graph, add input and output ports to a node, add a state
structure to a node, add input and output functions to a node, add an
edge to a graph, and emit a graph on the standard output.  Complete
descriptions of these functions, as well as numerous examples, can be
found in \cite{ohallaron91b}.

\section{Related Work}
\label{sec:previous}

{\sc Assign} continues the tradition of building parallel program
generators for restricted classes of applications. Examples of program
generators for image processing, matrix computations, and nested loop
computations can be found in \cite{hamey87,tseng89,ribas90},
respectively.

The flowgraph model has been studied extensively. Some seminal theory
on scheduling flowgraphs and an extensive survey of previous results
can be found in \cite{lee87}.

Several systems for compiling flowgraph descriptions of signal
processing applications have been developed in recent years, including
Gabriel\cite{lee89} at Berkeley and ZC\cite{printz89} at Carnegie
Mellon. Gabriel is a task--level parallel program generator that
was originally designed to generate code on single
processor systems or small shared memory parallel systems. However,
there has been recent work to extend it to distributed--memory
systems\cite{sih90} as well. The ZC system is designed to compile
flowgraphs onto linear systolic arrays like the Warp computer
\cite{annaratone87e}. Unlike {\sc Assign} or Gabriel, where nodes
correspond to sequential tasks, ZC allows for nodes to correspond
to parallel tasks.

\section*{Acknowledgements}
A number of people contributed to the development of {\sc Assign}.
Many thanks to Peter Lieu, Jim Wheeler, Harry Printz, Onat Menzilcioglu,
Siang Song, Robert Cohn, Susan Hinrichs, Thomas Gross,
Jon Webb, and Paul Wiley.

\bibliography{/usr/droh/bib/defs,/usr/droh/bib/refs,/usr/droh/bib/me}
\end{document}
