\section{\label{scheduler-sec} Scheduling PCM Threads on a Multiprocessor}

This section introduces a cost model for the PCM to motivate the work stealing
scheduling system which we implemented to schedule PCM threads on the CM-5 
parallel processor. All communication mechanisms required to implement the
work stealer and the inter-thread communication have been built using a version of
Active Messages~\cite{strata}. 
 
\begin{figure}[htbp]
\centerline{\psfigure{anatomy}{5in}}
\caption{\label{thread-anatomy}Anatomy of a PCM Thread}
\end{figure}

As Figure~\ref{thread-anatomy} illustrates, we will equate useful computation with
what a sequential program would have to do and classify everything else, such as
communication, synchronization, and dynamic scheduling as additional overhead. The
goal of this classification is to study the factors that determine the efficiency
of a parallel computation with respect to its sequential counterpart. 

To simplify the analysis, we will ignore the effect of idles and assume that each
processing element is either executing a thread or one of the overhead tasks
depicted in Figure~\ref{thread-anatomy}. Under this assumption we can reduce the
analysis to that of an average thread. The corresponding efficiency,
$\epsilon$, defined as the fraction of the overall execution time actually spent
executing the useful computation, can then be calculated using
equation~(\ref{efficiency-total}).

There are three important ratios in the equation, reflecting the effects of
tail-recursions ($\pi_1$), global send arguments ($\pi_2$) and closure migration
($\pi_3$) on the overall efficiency.  $\pi_1$ equals the fraction of threads not using
the tail-call mechanism, $\pi_2$ equals the fraction of arguments that have to be sent
across the interconnection network and $\pi_3$ equals the fraction closures that
migrate from one processing element to another, as a result of the work stealing
scheduler. $R_{t}$ defines the average run length of a PCM thread and $k$ defines the
threads arity.

\begin{description} 
\item[Make Closure ($M_c$):] At thread creation time, a closure must be allocated
and initialized. Both closure allocation and initialization are constant and do
not depend on the actual closure size ($M_c$ $\approx$ 10 cycles).

\item[Send Local Argument ($S_{l}$):] Local send arguments are fairly cheap and
reduce to simple memory-to-memory transfer plus an additional check to see whether
the closure becomes ready for execution ($S_{l}$) $\approx$ 10 cycles).

\item[Send Global Argument ($S_{l} + \pi_{2} \cdot T_{a}$ ):] For arguments that
must be sent across the network, we have to add an additional overhead factor
$T_a$ ($\approx$ 100 cycles)\footnote{The transfer cost include both the sending
and receiving overhead.} to the constant costs of $S_{l}$ to account for the
transfer costs.

\item[Post closure ($P_{c} + \pi_{3} \cdot T_{c}$):] After receiving all of its
arguments a closure is posted and becomes subject to dynamic scheduling ($P_{c}$
$\approx$ 10). If migrated to a remote processing element, additional transfer
costs of $T_{c}$ ($\approx$ 500 cycles for a closure consisting of eight words)
need to be charged in addition to constant cost $P_{t}$, reflecting the local
posting.

\item[Schedule closure ($S_{c}$):] The costs for transferring control to the
thread at the beginning of its execution and back to the scheduler after its
termination are $S_{c}$ ($\approx$ 15 cycles).
\end{description}
%%%%%
\begin{equation}
 \epsilon = \frac{R_{t}}{\pi_{1}\cdot (M_{c} + k\cdot (S_{l} + \pi_{2} \cdot T_{a})
+ (P_{c} + \pi_{3} \cdot T_{c}) + S_{c}) + R_{t}} \\
\label{efficiency-total}
\end{equation} 
%%%

With the communication costs $T_a$ and $T_c$ ranging in the hundreds of cycles, it
becomes imperative to reduce both $\pi_2$ and $\pi_3$ in order to avoid
disappointing efficiencies.  $\pi_1$, on the other hand, cannot be reduced to
arbitrarily small values, thus the only remaining alternative to amortize the
non-transfer related overhead is to increase the thread run length $R_t$.  

\begin{equation}
\epsilon = \frac{R_{t}}{\underbrace{M_{c} + P_{c} + S_{c} + k\cdot
S_{l}}_{schedule\;\;dependent} + \underbrace{\pi_{2}\cdot T_{a} \cdot k
+  \pi_{3}\cdot T_{c})}_{schedule\;\; independent} + R_{t}}
\label{efficiency-red}
\end{equation}

To illustrate the effect of $\pi_2$ and $\pi_3$ on the overall efficiency, we
transformed equation(\ref{efficiency-total}) into equation(\ref{efficiency-red}),
seperating schedule dependent and schedule independent costs and
Figure~\ref{eff-local} shows the resulting execution efficiency as a function of  
$\pi_2$ and $\pi_3$. For simplicity, we turned off the tail-call mechanism, which
results into a value for $\pi_1$ equal to one, and set $\pi_2$ equal to $\pi_3$.
In fact, for most computations we can expect $\pi_2$ and $\pi_3$ to be fairly
dependent -- higher migration frequencies will cleary force more of the arguments
to be sent global. 
\begin{figure}[htbp]
\centerline{\psfigure{eff-local}{4.5in}}
\caption{\label{eff-local}execution efficiency ($\epsilon$) versus fraction of local
global operations ($\pi_{2}$)} 
\end{figure}

\subsection{Implementation}

To achieve minimal values for $\pi_2$ we have adopted a lazy scheduling policy known as
{\em work stealing}. In such a system, closures are always scheduled locally per
default, and will only be transferred across the network upon explicit requests
initiated by starving processors.

Each processing element maintains a local queue of full closures, called the {\em
ready queue}. When a closure becomes full, it is posted to its local ready queue. The
local scheduler communicates with schedulers on other processing elements, and may
later schedule the closure to execute locally, or may migrate it to another processing
element. It is worth pointing out at this point that the actual schedule chosen is not
going to affect the result of the computation. It will, however, have a significant
impact on the efficiency  of the computation. 

In our current implementation, a computation executes locally using a depth-first
scheduling policy. This heuristic can be expected to result in lower resource
requirements for most computations when compared with a breadth-first policy.
Steal requests, on the other hand, will always be served using a breadth-first
policy (see Figure~\ref{commcost}).  Such a steal policy can be expected to result
in significantly reduced steal frequencies for computations, such as recursions.
For examples, both examples considered in the remainder of this paper typically
migrated less than one percent of all dynamically created closures, as annotated
in Figure~\ref{commcost}. In addition, recent theoretical results described
in~\cite{blumofe94} show that breadth-first stealing achieves linear speedup in
the presence of modest parallel slackness.
