\section{Basic Block Partitioning}
\label{section:basic}

In this section, we consider the problem of partitioning {\em basic
blocks}, that is, blocks whose operator nodes 
are all primitive operators\footnote{Nodes corresponding to constants
and their edges can be deleted from a basic block -- they do not
affect partitioning.} -- they do not contain conditionals and
calls to user-defined
functions. It is useful to study this restricted version
of the problem, as the techniques developed to partition
basic blocks can be extended to partition more general blocks.
Note that we consider only acyclic basic blocks, as we have
made the assumption that there are no cycles involving primitive
nodes in our inputs.

\subsection{Correctness of Basic Block Partitioning}
In section~\ref{section:partitioning}, we have defined the general
notion of correctness of a partitioning. For basic blocks, it
is possible to simplify the correctness criterion to 
simple conditions on the structure of the partitioned basic block.

Note that partitioning does not
distinguish one primitive operator (say $+$) from  another (say $*$) --
correctness of a partitioning depends on whether a value is 
computed at all, and not whether a different value is computed by
a block. In some sense, 
we can consider all primitive operators to be ``equivalent''.
As a basic block consists only of primitive operators, two basic
blocks differ only in their {\em structure}, \ie, the way
the operators are connected together. A partitioning is correct
if it preserves the structure of a basic block, as seen by
a context. Clearly, it should not introduce any cycles in the partitioned
block -- that would destroy the acyclicity property and cause
a deadlock in the block. Also, a context ``looks at'' only
the inputs and outputs of a basic block -- thus input-output
connectivity should be maintained. It turns out that these conditions
are sufficient to ensure the correctness of a partitioning of a 
basic block. These conditions are formalized in the theorem below (see the appendix for the proof).

\begin{theorem} [Basic Block Correctness]
\label{theorem:basic}
Let $b$ be a basic block and $b_Q$ its partitioned version.
$Q$ is a correct partitioning of $b$ iff acyclicity and 
input-output connectivity are preserved. That is,
\begin{enumerate}
\item{$b_Q$ is acyclic.}
\item{Let $i$ be an input of $b$ and $o$ an output of $b$. Then,
$i$ is connected to $o$ in $b$ iff it is connected to $o$ in $b_Q$.}
\end{enumerate}
\end{theorem}

Using  this theorem, we can now design algorithms 
to partition basic blocks. It is sufficient to prove that our
algorithms preserve the two conditions of the above theorem; that
is enough to guarantee the correctness of our partitioning algorithms.

\subsection{Demand and Tolerance Sets}
\begin{myfig*}{figure:sets}{Figure (a) shows the demand sets of each node of the given
basic block. Figure (b) shows its tolerance sets. Figure (c) shows
the partitions and reduced graph obtained by both algorithm 1 and algorithm 2.
The partitions are optimal for this example.}
\illustration{fig4}[\hsize]
\vspace{-4ex}
\end{myfig*}

In this section, we describe the properties of {\em demand} and {\em tolerance} sets that can be computed
for each node in a basic block. These sets are useful in designing
a partitioning algorithm as the correctness property can be 
formulated in terms of these sets. Moreover, they can be efficiently
computed for any basic block.

\begin{definition} [Demand Sets]
In a block $b$, the {\em demand} set of a node is the set of outputs
that depend on that node. Demand sets can be computed by the
following (backward) propagation algorithm on basic block.
\begin{eqnarray*}
Demand(o) & = & \{o\}, \mbox{if $o$ is an output node}\\
Demand(n) & = & \bigcup_{(n,m) \in b} Demand(m), \mbox{otherwise} 
\end{eqnarray*}
\end{definition}
Demand sets for a basic block are show in figure~\ref{figure:sets}.

\begin{definition} [Tolerance Sets]
In a block $b$, an output $o$ {\em tolerates} a node $n$ iff edge $(n,o)$
can be added to $b$ without affecting input-output connectivity. The
{\em tolerance set} of a node $n$ is the set of outputs that tolerate $n$.
Tolerance sets can be computed by the following (forward) propagation
algorithm on basic block graphs.
\begin{eqnarray*}
Tolerance(i) & = & Demand(i), \mbox{if $i$ is an input node}\\
Tolerance(n) & = & \bigcap_{(m,n) \in b} Tolerance(m), \mbox{otherwise}
\end{eqnarray*}
\end{definition}
Clearly, the tolerance set of an input node contains
at least its demand set; adding edges from an input node to any
node in its demand set will not affect input-output
connectivity. Also, no other output can be in the tolerance set of an
input -- that would add a connection where none existed. Thus, the 
tolerance set of an input node is exactly its demand set. Similarly, it
can be argued that the a node $o$ tolerates $n$ iff $o$ tolerates
all of $n$'s parents. Thus, the tolerance set of a node is the intersection
of the tolerance sets of its parents. Tolerance sets for a basic block are
shown in figure~\ref{figure:sets}.

Using the definitions of demand and tolerance sets, we can design
a simple algorithm that computes the demand sets in a backward
pass and then performs a forward pass to compute the tolerance sets.
The algorithm runs in $O(N^2)$ time and space, 
where $N$ is the number of nodes in the basic block.

\subsection{Algorithms for Basic Block Partitioning}
In this section, we design two algorithms for partitioning
based on demand and tolerance sets. The basic idea behind the
algorithms is to preserve input-output connectivity of the basic
block, thus ensuring correctness.

What effect does merging two nodes (say $n$ and $m$) have
on the connectivity of the basic block? For input-output connectivity,
this is equivalent to adding edges in the block from node $m$
to each output connected to $n$ and vice-versa. 
By definition of tolerance, this preserves
the connectivity if each output connected to $n$ tolerates node $m$,
that is, $Demand(n)$ $\subseteq$ $Tolerance(m)$ and vice-versa.
Algorithm 1 (shown in figure~\ref{figure:algorithm-1}) 
uses this condition to identify nodes that can
be merged and partitions the basic block. 

\begin{myfig}{figure:algorithm-1}{Algorithm 1 for Basic Block Partitioning}
\noindent{\bf Algorithm 1}\\
Given a basic block $b$:
\begin{enumerate}
\item{Compute demand and tolerance sets for each node of $b$.}
\item{Compute an (undirected) graph $G_{merge}$ as follows:
\begin{enumerate}
\item{The nodes of $G_{merge}$ are the nodes of $b$.}
\item{An edge $(n,m)$ is in $G_{merge}$ iff 
$Demand(n)$ $\subseteq$ $Tolerance(m)$ and $Demand(m)$ $\subseteq$
$Tolerance(n)$.
}
\end{enumerate}}
\item{Do
\begin{enumerate}
\item{Let $C$ be a maximal clique\footnotemark
 of $G_{merge}$. Merge nodes in $C$
into a single partition.}
\item{Form the reduced basic block. Recompute demand sets, tolerance
sets, and $G_{merge}$ for the new basic block.}
\end{enumerate}
until the partitions do not change.}
\end{enumerate}
\end{myfig}

\footnotetext{A {\em clique} of
a graph is a set of nodes that are all adjacent to each other. A
maximal clique is one to which no other node can be added without
destroying the clique property.}

The idea in algorithm 1 is to construct an auxiliary (undirected) graph, with
the nodes corresponding to the operators in the block. An
edge between two nodes 
indicates that the two nodes can be merged (using the condition
given above). A clique in the graph identifies a set of nodes
such that a node in the clique can be merged with any other node -- thus,
yielding a partition of the
block. This process is repeated on the reduced basic block until
no more partitions can be formed.
It is clear that algorithm 1 preserves input-output connectivity. 
It also preserves acyclicity, see the proof sketch of theorem~\ref{theorem:correctness-algorithm-1} in the appendix for details. Figure~\ref{figure:sets}
also shows the partitions obtained by algorithm 1 on a basic block.

Algorithm 1 generates the largest possible threads if instead of merging
maximal cliques, it merged {\em maximum} cliques. However, it is
well known that finding the maximum clique in a general graph is
NP-hard \cite{Garey79}. The best known algorithm for this problem
takes exponential time in the size of the input graph. Do the graphs we construct ($G_{merge}$) have any special structure that
can be exploited to give a more efficient algorithm? Unfortunately, the
answer is no. It is possible to show that finding an optimal partitioning
(either minimum
number of partitions or largest size partitions) is NP-hard \cite{Coorg94}.

Assuming that we are content with maximal cliques, we 
can estimate the complexity of the algorithm as follows.
The complexity is dominated by the loop in step 3, which merges
partitions at each step. The number of such steps is $O(N)$. In each
iteration, we compute the maximal clique and recompute $G_{merge}$. 
For finding a maximal clique, a simple greedy algorithm can be designed which
runs in $O(N^2)$ time. Also, a clever recomputation of the new graph
$G_{merge}$ that makes use of its older version takes $O(N^2)$ time.
Thus, the overall time complexity is $O(N^3)$. 

It is possible to design a simpler algorithm for basic
block partitioning. This algorithm
detects only a subset of possible merges in the block and merges
them into a single partition. Thus, it may not be able to detect
all the partitions that could be formed.
However, it does not require the
construction of the auxiliary graph ($G_{merge}$) and can be
implemented more efficiently. Algorithm 2 (shown in figure~\ref{figure:algorithm-2}) is based on the idea that merging nodes with the same
demand and tolerance sets produces correct partitions.

\begin{myfig}{figure:algorithm-2}{Algorithm 2 for Basic Block Partitioning}
\noindent{\bf Algorithm 2}\\
Given a basic block $b$:
\begin{enumerate}
\item{Compute demand and tolerance sets for each node of $b$.}
\item{Do
\begin{enumerate}
\item{Merge nodes with the same demand set into a single partition.
Recompute tolerance sets from reduced graph.}
\item{Merge nodes with the same tolerance set into a single partition.
Recompute demand sets from reduced graph.}
\end{enumerate}
until the partitions do not change.}
\end{enumerate}
\end{myfig}

Clearly, merging nodes with the same demand set preserves input-output
connectivity; merging nodes $m$ and $n$ has the effect
of introducing edges from $m$ to the demand set of $n$, and this
will have no effect on input-output connectivity as every node in
the demand set of $n$ is already connected to $m$. Similarly, using
the properties of tolerance sets, it can be argued that merging
nodes with the same tolerance sets also preserves input-output
connectivity. 

The worst-case complexity of algorithm 2 is the same as that of algorithm
1 ($O(N^3)$). However, it has been observed in practice \cite{Schauser94a} that a similar algorithm converges very fast -- the loop in step 2 executes only
a few $(< 4)$ iterations. Thus, it may have a practical advantage over 
algorithm 1. For the basic block in figure~\ref{figure:sets}, algorithm 2
also generates the same partitions generated by algorithm 1.
An implementation may use a mix of the two algorithms present in
this section to derive large partitions while keeping the complexity
of the algorithm low. One simple strategy is to run algorithm 2 first
and then run algorithm 1 on the reduced graph.








