\documentstyle[11pt,fullpage,cmu-titlepage,prog]{cmu-art}
\include{psfig}
\include{caption}

\title{The {\sc Assign} Parallel Program Generator}

\author{David R. O'Hallaron}

\disclaimer{Sponsored in part by DARPA, Information Science and 
Technology Office, under the title "Research on Parallel Computing",
ARPA Order No. 7330, issued 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 Oceans Systems Center
under Contract N00014-90-J-1939.  The views and conclusions contained
in this document are those of the author and should not be interpreted
as representing the official policies, either expressed or implied, of
DARPA, ONR, AFOSR, NOSC, or the U.S. government. }


\date{May 1, 1991}
\trnumber{CMU-CS-91-141}

\keywords{multicomputers, flowgraphs, mapping, signal processing}


\abstract{
{\sc Assign} is a tool for building large--scale applications, in
particular signal processing applications, on distributed-memory
multicomputers. The programming model is the familiar coarse-grained
flowgraph, where nodes correspond to computations and directed
edges correspond to FIFO queues.  Given a flowgraph description of an
application, {\sc Assign} compiles the flowgraph onto the processors
of a distributed--memory parallel computer, automatically handling
such details as partitioning the flowgraph and placing and routing the
partitioned flowgraph. The first target machine is iWarp, a multicomputer
system developed jointly by Intel and Carnegie Mellon. 
}

\citationinfo{
A shorter version of this report appears in the {\em Proceedings of the
6th Annual Distributed Memory Computing Conference}, April 29 -- May 1,
1991, Portland, OR. 
}

\begin{document}
\bibliographystyle{plain}
\maketitle

\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 for {\sc Assign} is the
iWarp\cite{borkar88,borkar90}, a multicomputer system developed
jointly by Carnegie Mellon University and Intel Corporation. We are
currently using {\sc Assign} to generate working programs on 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.  The appendix gives numerous examples.

\section{Overview}
\label{sec:overview}
In this section, we summarize the flowgraph programming model, the
mapping algorithm, how {\sc Assign} fits into existing systems, and
how we build applications. Later sections provide more details.

\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
\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 have the important property of being
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{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.

\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. This feature allows us to test flowgraphs on the
workstation, generating code for the iWarp only when we are confident
that the graph is producing correct results.

Just to make things concrete, here are the commands we would use to
generate, compile, and run a flowgraph called {\tt example.graph}.
First, we write a graph generator called {\tt example-gen.c},
then compile and run it to generate the flowgraph in file {\tt
example.graph}.
\begin{prog}
	% make example-gen
	% example-gen > example.graph
\end{prog}
Next we compile the flowgraph using {\sc Assign}.
\begin{prog}
	% assign example
\end{prog}
Next we compile and link the output of {\sc Assign} using the 
C compiler and linker supplied by Intel. The makefile for doing
this, {\tt example-make}, is generated by {\sc Assign}.
\begin{prog}
	% make -f example-make
\end{prog}
Finally, we run the flowgraph on the iWarp array by executing a shell
script, called {\tt go}, produced by the makefile in the previous
step.
\begin{prog}
	% go
\end{prog}

\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).

\subsection{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. 

\subsection{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.

\subsection{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).

\subsection{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.

\subsection{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.  Each port in a node is bound to at most one edge.
We refer to a queue bound to input port $k$ as {\em input queue} $k$.
Similarly, we refer to a queue bound to output port $k$ as {\em output
queue} $k$.  The two ports bound to an edge must have the same type.  The
queue corresponding to an edge may be initialized with an arbitrary
number of zeros.

\subsection{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
(such as airborne ASW\cite{printz89}) with multiple sampling rates and
redundant computations.

\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 and in the process
accumulate a small set of simple primitives that can be used in a wide
variety of applications.

\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. An example of a
realistic primitive that uses the state structure is in Section
\ref{sec:examplesfft}. The example is an $n$-point complex FFT that uses 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.
The 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}
The output function is invoked each time an {\tt incr} sink node
writes to its output ports.
\begin{prog}
	incr_out(outp, sp)
	float *outp;
	struct incr_state *sp;
	{
		int i;

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

\subsection{Dynamic Initializers}
Another simple but useful primitive splits an input vector of length
{\tt in} into two output vectors of length {\tt out1} and {\tt out2}.
Given the following state structure definition
\begin{prog}
	struct split_state {
		int in;
		int out1;
		int out2;
	};
\end{prog}
the primitive can be written as 
\begin{prog}
	split(inp, outp1, outp2, sp)
	float *inp, *outp1, *outp2;
	struct split_state *sp;
	{
		int i;

		for (i=0; i<sp->out1; i++)
			*outp1++ = *inp++;
		for (i=0; i<sp->out2; i++)
			*outp2++ = *inp++;
	}
\end{prog}
The dual to the {\tt split} primitive is the join primitive, which
appends one input vector to another input vector and places the
result in an output vector.
\begin{prog}
	struct join_state {
		int in1;
		int in2;
		int out;
	};
\end{prog}
\begin{prog}
	join(inp1, inp2, outp, sp)
	float *inp1, *inp2, *outp;
	struct join_state *sp;
	{
		int i;

		for (i=0; i<sp->in1; i++)
			*outp++ = *inp1++;
		for (i=0; i<sp->in2; i++)
			*outp++ = *inp2++;
	}
\end{prog}
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 a {\tt split} node, for example, we might 
statically initialize the size of the input vector, and then dynamically 
determine where the vector will be split.
\begin{prog}
	split_init(sp)
	struct split_state *sp;
	{
		sp->out1 = sp->out2 = sp->in/2;
	}
\end{prog}
A more substantive example can be found in Appendix \ref{sec:examplesfft},
where the complex coefficients for an $n$-point complex FFT are
precomputed and stored in the state structure for use in all
subsequent invocations of the FFT.

\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.  For example, functions can be used as an
abstraction mechanism to create subgraphs, iteration can be used to
generate iterative constructs like pipelines, and recursive functions
can be used to create recursive constructs such as fan--out fan--in
trees.

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. For example,
sonar adaptive beam interpolation (ABI) is characterized entirely by
the number of beams and the number of frequencies. It was not difficult
for us to write a graph generator that generates arbitrary ABI
flowgraphs.  Whenever we want to create a different sized ABI program
on iWarp, we simply change a couple of constants and recompile the new
graph.

Yet another advantage is that a procedural interface based on C is
portable across a wide variety of personal computers and workstations
and familiar to many programmers.

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.

\subsection{Creating Empty Graphs}
\begin{prog}
	GRAPH *alloc_graph(name);
	char *name;
\end{prog}
{\tt Alloc\_graph} returns a pointer to empty flowgraph {\tt name}.

\subsection{Associating Files With a Graph}
\begin{prog}
	void add_src_file(gp, name)
	GRAPH *gp;
	char *name;
\end{prog}
\begin{prog}
	void add_inc_file(gp, name)
	GRAPH *gp;
	char *name;
\end{prog}

{\tt Add\_src\_file} adds source file {\tt name} to a list of source
files associated with graph {\tt gp}. Each node function must be
contained in some source file.  Similarly, {\tt add\_inc\_file} adds
include file {\tt name} to a list of include files associated with
graph {\tt gp}. Each state structure definition required by the graph
must be contained in some include file.

\subsection{Adding Nodes to a Graph}
\begin{prog}
	NODE *add_node(gp, name, prim, weight)
	GRAPH *gp;
	char *name, *prim;
	int weight;
\end{prog}
{\tt Add\_node} adds atom {\tt name}, with primitive function {\tt
prim} and execution weight {\tt weight} to graph {\tt gp} and returns
a pointer to the node that can used in subsequent calls to {\tt
add\_in\_port}, {\tt add\_out\_port}, and {\tt add\_edge}.
\begin{prog}
	NODE *add_graph_node(gp, gnp)
	GRAPH *gp, *gnp;
\end{prog}
{\tt Add\_graph\_node} adds the subgraph node {\tt gnp} to graph {\tt
gp}.  The resulting subgraph node gets the name of subgraph {\tt gnp},
the input ports of subgraph {\tt gnp}'s source node, and the output
ports of subgraph {\tt gnp}'s sink node.
\begin{prog}
	add_in_port(np, name, type, consume_amt)
	NODE *np;
	char *name;
	int type, consume_amt;
\end{prog}

\begin{prog}
	add_out_port(np, name, type, produce_amt)
	NODE *np;
	char *name;
	int type, produce_amt;
\end{prog}
{\tt Add\_in\_port} adds input port {\tt name} with type {\tt type},
and consume amount {\tt consume\_amt} to node {\tt np}.  {\tt
Add\_out\_port} adds output port {\tt name} with type {\tt type}, and
produce amount {\tt produce\_amt} to node {\tt np}. Valid {\tt type}s
are {\tt INT}, {\tt FLOAT}, {\tt DOUBLE}, {\tt COMPLEX}, {\tt
COMPLEX\_INT}, and {\tt COMPLEX\_DOUBLE}.
\begin{prog}
	add_state(np, state, ilist, init)
	NODE *np;
	char *state, *ilist, *init;
\end{prog}
{\tt Add\_state} associates a state structure with node {\tt np}. The
structure is defined by the tag name {\tt state}, initialized at
compile time by the static initializer list {\tt ilist}, and
initialized at runtime by the dynamic initializer function {\tt init}.
If {\tt ilist} is {\tt NULL}, then {\sc Assign} assumes there is no
static initializer list, and similarly for {\tt init}.
\begin{prog}
	add_io(np, input, output)
	NODE *np;
	char *input, *output;
\end{prog}
{\tt Add\_io} associates input function {\tt input} and output
function {\tt output} with node {\tt np}.  If {\tt input} is {\tt
NULL}, then {\sc Assign} assumes there is no input function, and
similarly for {\tt output}.

\subsection{Adding Edges to a Graph}
\begin{prog}
	add_edge(gp, out_np, out_port, in_np, in_port, initq)
	GRAPH *gp;
	NODE *out_np;
	char *out_port;
	NODE *in_np;
	char *in_port;
	int initq;
\end{prog}
{\tt Add\_edge} adds an edge to graph {\tt gp} that connects output port {\tt out\_port}
of node {\tt out\_np} to input port {\tt in\_port} of node {\tt in\_np}. The queue
corresponding to the edge is initialized with {\tt initq} zeros (delay elements).

\subsection{Outputting Graphs}
\begin{prog}
	emit_graph(gp)
	GRAPH *gp;
\end{prog}
\begin{prog}
	print_graph(gp)
	GRAPH *gp;
\end{prog}

{\tt Emit\_graph} sends an ASCII representation of the flowgraph to
the standard output. The output of this function is the input to {\sc Assign}.
{\tt Print\_graph} sends a more readable ASCII representation of the flowgraph
to the standard output, listing each node, its input and output ports, and
its attributes. For example,
\begin{prog}
	Node split1
		prim = split, weight = 1000
		state = split_state, init = split_init, ilist = 48,16,32
		Input ports:
			left <- split0.right : FLOAT, cons = 48 
		Output ports:
			down -> incr1.left : FLOAT, prod = 16
			right -> split2.left : FLOAT, prod = 32
\end{prog}
Here we have a node called {\tt split1}. {\tt split} is the associated
primitive with an execution weight of 1000 clocks. There is a state
structure associated with this node that is defined by the tag {\tt
split\_state}. There is a dynamic initializer functions called {\tt
split\_init()} that is called before the graph executes.  The first
three elements of the state structure are initialized at compile time
by the C structure initializer list {\tt 48,16,32}.

The node has 1 input port ({\tt left}) and two output ports ({\tt
down} and {\tt right}). Input port {\tt left} is connected by an edge
from node {\tt split0}, port {\tt right}, and has a consume amount of
48 {\tt FLOAT}s.  Ouput port {\tt down} is connected by an edge to
node {\tt incr1}, port {\tt left}, and has a produce amount of 16 {\tt
FLOAT}s.  Similarly for output port {\tt right}.

\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}.
Peter Lieu wrote the iWarp code generator.  Jim Wheeler was the first
user and made many helpful suggestions.  Harry Printz developed the
algorithm for normalizing execution rates.  Onat Menzilcioglu and
Siang Song wrote the original placement and routing code.  Robert Cohn
wrote the FT Warp simulator used to test earlier versions. Susan
Hinrichs patiently answered questions about iWarp software. Thomas Gross,
Jon Webb, and Paul Wiley made helpful suggestions.

\newpage

\appendix 
\section{Examples}
\label{sec:examples}
The appendix gives a number of examples of {\sc Assign} programs using
the node functions and state structures developed in Section
\ref{sec:nodefunctions}.  The aim is to develop some useful graph
structures and to illustrate the general way we develop {\sc Assign}
programs.


\subsection{incr16}
The simplest {\sc Assign} flowgraph has a single node and no edges, as
in Figure \ref{fig:incr16}.
\begin{figure}[ht]
\setlength{\unitlength}{0.2in}
\thicklines
\scriptsize
\begin{center}
\begin{picture}(10,2)(0,0)
\put(5,1){\circle{2}}
\put(5,1){\makebox(0,0){incr16}}
\end{picture}
\end{center}
\caption{The {\tt incr16} graph.}
\label{fig:incr16}
\end{figure}

To generate this graph, we start with a simple function that 
adds an {\tt incr16} node to a graph and returns a pointer to that node.
\begin{prog}
	NODE *incr16_node(gp, name)
	GRAPH *gp;
	char *name;
	{
		NODE *np;

		np = add_node(gp, name, "incr", 16);
		add_in_port(np, "in", FLOAT, 16);
		add_out_port(np, "out", FLOAT, sample_size);
		add_io(np, "incr_in", "incr_out");
		return(np);
	}
\end{prog}
The complete graph generator is of the form.
\begin{prog}
	#include <stdio.h>
	#include <assign.h>

	NODE *incr16_node();

	main()
	{
		GRAPH *gp = alloc_graph("incr_graph");

		add_src_file(gp, "incr.c");
		incr16_node(gp, "incr");
		emit_graph(gp);
	}
\end{prog}

\newpage

\subsection{incr}
We can generalize the {\tt incr16} graph by using the 
{\tt incr} primitive from Section \ref{sec:nodefunctions}.
The following function adds an {\tt incr} node to a graph
and returns a pointer to that node.
\begin{prog}
	NODE *incr_node(gp, name, weight, sample_size)
	GRAPH *gp;
	char *name;
	int weight, sample_size;
	{
		NODE *np;
		char ilist[32];

		np = add_node(gp, name, "incr", sample_size);
		add_in_port(np, "in", FLOAT, sample_size);
		add_out_port(np, "out", FLOAT, sample_size);
		sprintf(ilist, "%d", sample_size);
		add_state(np, "incr_state", ilist, "incr_init");
		add_io(np, "incr_in", "incr_out");
		return(np);
	}
\end{prog}

\newpage

\subsection{pipe}
This section we describe a general technique for creating pipelines of
the type shown in Figure \ref{fig:pipe}. This graph models the common
computation where a sequence of operations are performed on a single
data stream.

\begin{figure}[ht]
\setlength{\unitlength}{0.2in}
\thicklines
\scriptsize
\begin{center}
\begin{picture}(22,4)(0,0)
\put(5,1){\circle{2}}
\put(9,1){\circle{2}}
\put(13,1){\circle{2}}
\put(17,1){\circle{2}}
\put(6,1){\vector(1,0){2}}
\put(10,1){\vector(1,0){2}}
\put(14,1){\vector(1,0){2}}
\put(5,1){\makebox(0,0){incr0}}
\put(9,1){\makebox(0,0){incr1}}
\put(13,1){\makebox(0,0){incr2}}
\put(17,1){\makebox(0,0){incr3}}
\end{picture}
\end{center}
\caption{The {\tt pipe} graph.}
\label{fig:pipe}
\end{figure}

We start with a function that calls {\tt incr\_node} to create a pipeline
of {\tt incr} nodes and returns a pointer to the resulting graph.
\begin{prog}
	GRAPH *incr_pipe(len, name, weight, size)
	int len;
	char *name;
	int weight, size;
	{ 
		GRAPH *gp = alloc_graph(name);
		NODE *prev, *curr;
		char s[32];
		int i;
  
		add_src_file(gp, "incr.c");
		add_inc_file(gp, "incr.h");

		prev = incr_node(gp, "incr0", weight, size);
		for (i=1; i<len; i++) {
			sprintf(s, "incr%d", i);
			curr = incr_node(gp, s, weight, size);
			add_edge(gp, prev, "out", curr, "in", 0);
			prev = curr;
		}
		return(gp);
	}
\end{prog}
To emit the pipe in Figure \ref{fig:pipe}, we would write
\begin{prog}
	emit_graph(incr_pipe(4, ``pipe'', 100, 16));
\end{prog}

\newpage

\subsection{trellis}
One of the properties of the current implementation of {\sc Assign}
for iWarp is that communication resources are allocated statically and
persist for the duration of the program. In particular, when we map a
graph to an iWarp array, each edge that spans two cells is implemented
as a statically allocated iWarp pathway. The advantage of this
approach is efficient communication between cells, typically one clock
between cells in the absence of link contention. The disadvantage is
that an iWarp cell can only support a small (currently 20) number of
pathways at any point in time.  Thus, a node with many input or output
edges forces {\sc Assign} to place that node and all of its adjacent
nodes on the same cell. The bottom line is that graphs with high
degree, while valid flowgraphs, may end up using only a small number
of the available iWarp cells.

This situation typically arises when there are a large number of
operations to be performed in parallel on separate data streams. For
example, suppose we want to distribute each row of an $n \times m$
matrix to one of $n$ FFT nodes and then collect the resulting vectors
to form a new $n \times m$ matrix. Rather than using single nodes ---
each with $n$ input or output edges --- to distribute and collect the
rows, we recommend using either a {\em trellis}, which is described
in this section, or a {\em fan}, which is described in the next section.

Figure \ref{fig:trellis} gives an example of a trellis with $n=4$ 
{\tt incr} nodes, each of which operates on a vector of $m$ data items.
\begin{figure}[ht]
\thicklines
\setlength{\unitlength}{0.2in}
\scriptsize
\begin{center}
\begin{picture}(15,11)(0,0)
\put(2,10){\circle{2}}
\put(2,10){\makebox(0,0){split0}}
\put(2,6){\circle{2}}
\put(2,6){\makebox(0,0){incr0}}
\put(6,10){\circle{2}}
\put(6,10){\makebox(0,0){split1}}
\put(6,6){\circle{2}}
\put(6,6){\makebox(0,0){incr1}}
\put(6,2){\circle{2}}
\put(6,2){\makebox(0,0){join1}}
\put(10,10){\circle{2}}
\put(10,10){\makebox(0,0){split2}}
\put(10,6){\circle{2}}
\put(10,6){\makebox(0,0){incr2}}
\put(10,2){\circle{2}}
\put(10,2){\makebox(0,0){join2}}
\put(14,6){\circle{2}}
\put(14,6){\makebox(0,0){incr3}}
\put(14,2){\circle{2}}
\put(14,2){\makebox(0,0){join3}}

\put(2,9){\vector(0,-1){2}}
\put(2,5){\line(0,-1){3}}

\put(6,9){\vector(0,-1){2}}
\put(6,5){\vector(0,-1){2}}

\put(10,9){\vector(0,-1){2}}
\put(10,5){\vector(0,-1){2}}

\put(14,10){\vector(0,-1){3}}
\put(14,5){\vector(0,-1){2}}

\put(3,10){\vector(1,0){2}}
\put(7,10){\vector(1,0){2}}
\put(11,10){\line(1,0){3}}

\put(2,2){\line(1,0){3}}
\put(7,2){\vector(1,0){2}}
\put(11,2){\vector(1,0){2}}

\put(4,10.2){\makebox(0,0)[b]{$3m$}}
\put(8,10.2){\makebox(0,0)[b]{$2m$}}
\put(12,10.2){\makebox(0,0)[b]{$m$}}

\put(4,1.8){\makebox(0,0)[t]{$m$}}
\put(8,1.8){\makebox(0,0)[t]{$2m$}}
\put(12,1.8){\makebox(0,0)[t]{$3m$}}

\put(2.2,8){\makebox(0,0)[l]{$m$}}
\put(6.2,8){\makebox(0,0)[l]{$m$}}
\put(10.2,8){\makebox(0,0)[l]{$m$}}

\put(6.2,4){\makebox(0,0)[l]{$m$}}
\put(10.2,4){\makebox(0,0)[l]{$m$}}
\put(14.2,4){\makebox(0,0)[l]{$m$}}
\end{picture}
\end{center}
\caption{The {\tt trellis} graph.}
\label{fig:trellis}
\end{figure}
Each {\tt split} node peels off the first $m$ data items, passes these
$m$ data items to an {\tt incr} node, and passes the rest of its input
onto the next {\tt split} node. Each {\tt join} node appends the
output of an {\tt incr} node to its input and passes the result to the
next {\tt join} node. Note that a trellis is a coarse--grained version
of the {\sc Apply} {\tt GETROW/PUTROW} model\cite{hamey89}.

These functions create instances of {\tt split} and {\tt join} nodes.
\begin{prog}
	NODE *split_node(gp, name, weight, in, out1, out2) 
	GRAPH *gp;
	char *name;
	int weight;
	int in, out1, out2;
	{
		NODE *np;

		np = add_node(gp, name, "split", weight);

		add_in_port(np, "left", FLOAT, in);
		add_out_port(np, "down", FLOAT, out1);
		add_out_port(np, "right", FLOAT, out2);

		sprintf(s, "%d,%d,%d", in, out1, out2);
		add_state(np, "split_state", s, NULL);

		add_io(np, "split_in", "split_out");
		return(np);
	}
\end{prog}

\begin{prog}
	NODE *join_node(gp, name, weight, in1, in2, out) 
	GRAPH *gp;
	char *name;
	int weight;
	int in1, in2, out;
	{
		NODE *np;

		np = add_node(gp, name, "join", weight);
		add_in_port(np, "left", FLOAT, in1);
		add_in_port(np, "up", FLOAT, in2);
		add_out_port(np, "right", FLOAT, out);
		sprintf(s, "%d,%d,%d", in1, in2, out);
		add_state(np, "join_state", s, NULL);
		add_io(np, "join_in", "join_out");
		return(np);
	}
\end{prog}
This function creates a trellis of $n$ {\tt incr} nodes. 
We assume there are constants WEIGHT and SIZE that give the
execution weight and sample size of an {\tt incr} node.

\begin{prog}
	GRAPH *trellis(n, name)
	int n;
	char *name;
	{
		GRAPH *gp;
		NODE *prev_split_np, *prev_join_np;
		NODE *split_np, *join_np, *incr_np;
		int i, len;

		gp = alloc_graph(name);

		add_src_file(gp, "incr.c");
		add_inc_file(gp, "incr.h");
		add_src_file(gp, "split.c");
		add_inc_file(gp, "split.h");
		add_src_file(gp, "join.c");
		add_inc_file(gp, "join.h");

		if (n == 1) {
			incr_node(gp, "incr0", WEIGHT, SIZE);
			return(gp);
		}

		len = SIZE*n;
		prev_split_np = split_node(gp, "split0", WEIGHT, len, SIZE, len-SIZE);
		prev_join_np = incr_node(gp, "incr0", WEIGHT, SIZE);
		add_edge(gp, prev_split_np, "down", prev_join_np, "left", 0); 
  
		for (i=1; i<n-1; i++) {
			len = (n-i)*SIZE;
			sprintf(s, "split%d", i);
			split_np = split_node(gp, s, WEIGHT, len, SIZE, len-SIZE);
			sprintf(s, "incr%d", i);
			incr_np = incr_node(gp, s, WEIGHT, SIZE);
			sprintf(s, "join%d", i);
			join_np = join_node(gp, s, SIZE, i*SIZE, SIZE, i*SIZE+SIZE);

			add_edge(gp, split_np, "down", incr_np, "left", 0);
			add_edge(gp, incr_np, "right", join_np, "up", 0);
			add_edge(gp, prev_split_np, "right", split_np, "left", 0);
			add_edge(gp, prev_join_np, "right", join_np, "left", 0);

			prev_split_np = split_np;
			prev_join_np = join_np;
		}
		sprintf(s, "incr%d", n-1);
		incr_np = incr_node(gp, s, WEIGHT, SIZE);
		sprintf(s, "join%d", n-1);
		join_np = join_node(gp, s, SIZE, (n-1)*SIZE, SIZE, n*SIZE);

		add_edge(gp, incr_np, "right", join_np, "up", 0);
		add_edge(gp, prev_split_np, "right", incr_np, "left", 0);
		add_edge(gp, prev_join_np, "right", join_np, "left", 0);

		return(gp);
	}
\end{prog}
To generate the trellis in Figure \ref{fig:trellis}, we would write
\begin{prog}
	emit_graph(trellis(4, ``trellis''));
\end{prog}


\newpage

\subsection{fan}
An alternative to the trellis is the {\em fan} shown in Figure \ref{fig:fan}.
We start with a recursive function that returns fans of size $n =
2^k$. We assume there is a function {\tt pwr2(k)} that returns $2^k$,
and we assume there are constants WEIGHT and SIZE that give the
execution weight and sample size of an {\tt incr} node.
\begin{figure}[ht]
\thicklines
\setlength{\unitlength}{0.2in}
\scriptsize
\begin{center}
\begin{picture}(25,15)(0,0)
\put(5,7){\circle{2}}
\put(9,3){\circle{2}}
\put(9,11){\circle{2}}
\put(13,13){\circle{2}}
\put(13,9){\circle{2}}
\put(13,5){\circle{2}}
\put(13,1){\circle{2}}
\put(17,11){\circle{2}}
\put(17,3){\circle{2}}
\put(21,7){\circle{2}}
\put(5.8,7.8){\vector(1,1){2.4}}
\put(5.8,6.2){\vector(1,-1){2.4}}
\put(9.9,11.5){\vector(2,1){2.2}}
\put(9.9,10.5){\vector(2,-1){2.2}}
\put(9.9,3.5){\vector(2,1){2.2}}
\put(9.9,2.5){\vector(2,-1){2.2}}
\put(13.9,12.5){\vector(2,-1){2.2}}
\put(13.9,9.5){\vector(2,1){2.2}}
\put(13.9,4.5){\vector(2,-1){2.2}}
\put(13.9,1.5){\vector(2,1){2.2}}
\put(17.8,10.2){\vector(1,-1){2.4}}
\put(17.8,3.8){\vector(1,1){2.4}}
\put(5,7){\makebox(0,0){split}}
\put(9,3){\makebox(0,0){split}}
\put(9,11){\makebox(0,0){split}}
\put(13,1){\makebox(0,0){incr}}
\put(13,5){\makebox(0,0){incr}}
\put(13,9){\makebox(0,0){incr}}
\put(13,13){\makebox(0,0){incr}}
\put(17,3){\makebox(0,0){join}}
\put(17,11){\makebox(0,0){join}}
\put(21,7){\makebox(0,0){join}}
\put(6.8,9.2){\makebox(0,0)[b]{$2m$}}
\put(6.8,4.2){\makebox(0,0)[b]{$2m$}}
\put(11,12.2){\makebox(0,0)[b]{$m$}}
\put(11,9.2){\makebox(0,0)[b]{$m$}}
\put(11,4.2){\makebox(0,0)[b]{$m$}}
\put(11,1.2){\makebox(0,0)[b]{$m$}}
\put(15,12.2){\makebox(0,0)[b]{$m$}}
\put(15,9.2){\makebox(0,0)[b]{$m$}}
\put(15,4.2){\makebox(0,0)[b]{$m$}}
\put(15,1.2){\makebox(0,0)[b]{$m$}}
\put(19.2,9.2){\makebox(0,0)[b]{$2m$}}
\put(19.2,4.2){\makebox(0,0)[b]{$2m$}}
\end{picture}
\end{center}
\caption{The {\tt fan} graph.}
\label{fig:fan}
\end{figure}
\begin{prog}
	GRAPH *fan2(k, name)
	int k;
	char *name;
	{
		GRAPH *gp, *fan1_gp, *fan2_gp;
		NODE *split_np, *join_np, *fan1_np, *fan2_np;
		int size, i;

		sprintf(s, "fan%d_%s", pwr2(k), name);
		gp = alloc_graph(s);

		add_src_file(gp, "incr.c");
		add_inc_file(gp, "incr.h");
		add_src_file(gp, "join.c");
		add_inc_file(gp, "join.h");
		add_src_file(gp, "split.c");
		add_inc_file(gp, "split.h");

		if (k == 0) {
			incr_node(gp, "incr", WEIGHT, SIZE);
			return(gp);
		}

		size = SIZE*pwr2(k-1);
		split_np = split_node(gp, "split", 100, size*2, size, size);

		fan1_gp = fan2(k-1, "1");
		fan2_gp = fan2(k-1, "2");
		fan1_np = add_graph_node(gp, fan1_gp);
		fan2_np = add_graph_node(gp, fan2_gp);

		join_np = join_node(gp, "join", size, size, size, size*2);

		add_edge(gp, split_np, "down", fan1_np, "left", 0);
		add_edge(gp, split_np, "right", fan2_np, "left", 0);
		add_edge(gp, fan1_np, "right", join_np, "left", 0);
		add_edge(gp, fan2_np, "right", join_np, "up", 0);

		return(gp);
	}  
\end{prog}
We can use the {\tt fan2} function to create arbitrary sized fans. The
idea is based on the fact that an integer $n$ can always be expressed
as the sum of integers which are powers of 2. For example, $7=4+2+1$. 
\begin{prog}
	GRAPH *fan(n, name)
	int n;
	char *name;
	{
		int m, k; /* n=(m=2^k)+r */
		int in1, in2;

		GRAPH *gp, *fan_gp, *fan2_gp;
		NODE *split_np, *join_np, *fan_np, *fan2_np;
  
		if (n == 0)
			return(NULL);

		/* find the largest k such that 2^k = m <= n */
		for (k=0,m=1; m<<1 <= n; m<<=1, k++)
			; 

		/* build fans of size 2^k and n - 2^k */
		fan2_gp = fan2(k, "1");
		if (!(fan_gp = fan(n-m, "2"))) {
			return(fan2_gp);
		}
		else {
			gp = alloc_graph(sprintf(s, "fan%d_%s", n, name));
			in1 = SIZE * m;
			in2 = SIZE * (n-m);
			split_np = split_node(gp, "split", 100, in1 + in2, in1, in2);
			fan2_np = add_graph_node(gp, fan2_gp);
			fan_np = add_graph_node(gp, fan_gp);
			join_np =  join_node(gp, "join", in2, in1, in2, in1 + in2);
			add_edge(gp, split_np, "down", fan2_np, "left", 0);
			add_edge(gp, split_np, "right", fan_np, "left", 0);
			add_edge(gp, fan2_np, "right", join_np, "left", 0);
			add_edge(gp, fan_np, "right", join_np, "up", 0);

			add_src_file(gp, "incr.c");
			add_inc_file(gp, "incr.h");
			add_src_file(gp, "join.c");
			add_inc_file(gp, "join.h");
			add_src_file(gp, "split.c");
			add_inc_file(gp, "split.h");

			return(gp);
		}
	}

\end{prog}
To generate the fan in Figure \ref{fig:fan}, we would write
\begin{prog}
	emit_graph(fan(4, ``fan''));
\end{prog}

\newpage

\subsection{fft}
\label{sec:examplesfft}
We conclude with an example of a realistic {\sc Assign} primitive, an
$n$ point complex FFT. 
We start by defining the 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 initialize the size of the FFT when the node
is created, and then dynamically precompute the complex coefficients
using the following dynamic initializer.
\begin{prog}
void fft_init(sp)
struct fft_state *sp;
{
  int n, mmax, m, j, istep, i, cnt;
  double wtemp, wr, wpr, wpi, wi, theta;
  
  cnt = 0;
  n = (sp->n)<<1;
  mmax = 2;
  while (n > mmax) { 
    istep = 2*mmax;
    theta = M_2_PI / (sp->isign*mmax);
    wtemp = sin(0.5*theta);
    wpr = -2.0*wtemp*wtemp;
    wpi = sin(theta);
    wr = 1.0;
    wi = 0.0;
    sp->wp[cnt].r = wr;
    sp->wp[cnt].i = wi;
    cnt++;
    for (m=0; m<mmax-1; m+=2) { 
      wr = (wtemp=wr)*wpr - wi*wpi + wr;
      wi = wi*wpr + wtemp*wpi + wi;
      sp->wp[cnt].r = wr;
      sp->wp[cnt].i = wi;
      cnt++;
    }
    mmax = istep;
  }
}
\end{prog}
The following FFT primitive uses the precomputed coefficients to 
compute an $n$ point complex DFT.
\begin{prog}
	void fft(inp, outp, sp)
	complex *inp, *outp;
	struct fft_state *sp;
	{
		int i, j=0, m, istep;
		int n = sp->n, isign = sp->isign, mmax = 1;
		complex *wp = sp->wp-1, temp;

		/* sort input into bit reversed order */
		for (i=0; i<n; i++) { 
			if (j > i)
				SWAP(inp[i], inp[j]);
			m = n >> 1;
			while (m >= 1 && j >= m) {
				j -= m; 
				m >>= 1;
			}
			j += m;
		}

		/* perform the FFT on the bit reversed input */
		while (n > mmax) { 
			istep = 2*mmax;
			wp++;
			for (m=0; m<mmax; m++) { 
				for (i=m; i<n; i += istep) {
					j = i + mmax;
					temp.r = (*wp).r * inp[j].r - (*wp).i * inp[j].i;
					temp.i = (*wp).r * inp[j].i + (*wp).i * inp[j].r;
					inp[j].r = inp[i].r - temp.r;
					inp[j].i = inp[i].i - temp.i;
					inp[i].r += temp.r;
					inp[i].i += temp.i;
				}
				wp++;
			}
			mmax = istep;
		}

		for (i=0; i<n; i++) {
			(outp)->r = (inp)->r;
			(outp++)->i = (inp++)->i;
		}
	}
\end{prog}

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