% -*- Mode: LaTeX -*-

\section{Barriers under Eager Evaluation}
\label{sec:uses}

\subsection{Barrier Specification}

\ibx{Barriers} provide a mechanism to detect the termination of a set
of parallel activities enclosed within a control region. A barrier is
specified in Id using three or more dashes (\tbx{---}) creating two
sub-regions within a given control region --- one above the barrier
called the \ibx{pre-region} and the other below the barrier called the
\ibx{post-region} (see \fig{scope} (b)).  Intuitively, no computation
within the post-region is allowed to proceed until all computations
within the pre-region have terminated.\footnote{Actually, all we care
about is that the {\em effect\/} (computed values and side-effects) of
the post-region is not visible from outside until the pre-region has
completely terminated.} The termination of control regions must also
respect their nesting, making the barriers {\em hyper-strict\/}, \ie,
the entire computation subtree spawned from the tasks within a
pre-region must terminate before any computation in the post-region is
allowed to proceed.

Id also provides the ability to delimit the scope of a control region
to an arbitrary subset of the parallel tasks at hand.  Unlike
data-parallel computation where all barriers are global, barriers in
Id may be localized to a specified set of parallel activities by
grouping those activities in parentheses. This is also illustrated in
the example shown in \fig{scope} (b).  The activities \tbx{(f1 x)},
and \tbx{(f3 z)} are initiated in parallel because the post-region of
the barrier excludes the activity \tbx{(f3 z)} using parentheses. The
activity \tbx{(f2 y)} is initiated upon termination of \tbx{(f1 x)} as
prescribed by the barrier.  The entire block terminates when all the
activities within all sub-regions inside it have terminated.  The
power and usefulness of barriers in Id stem from the fact that the
granularity of the regions being sequentialized is completely under
user control.

\fig{scope} illustrates another important point: the partitioning
of parallel computation in Id into control regions is completely
static and textual.  The user always has a clear picture of which
computations will evaluate and under what circumstances.  This is
possible only under eager evaluation. Under lazy evaluation, even if
some computations are explicitly sequentialized or scheduled using
barriers, it is not clear whether they will ever evaluate until
something demands their value: there is no natural notion of control
region as a group of concurrent activities.

\subsection{The Uses of Barriers}

In this section we describe the various uses of barriers under the
parallel execution model discussed in \sec{eager}.

\subsubsection*{Controlling Parallelism}

 As shown in \fig{model}, the eager evaluation strategy unfolds the
parallel computation into a tree of activation frames. In some
``embarrassingly parallel'' computations, the potential parallelism is
limited not by the data-dependencies but purely by the size of the
available frame or heap memory in the machine. An unrestricted
unfolding of the activation tree may cause the machine to run out of
memory very quickly. In such cases, it is important to ``throttle''
the parallelism to match the available resources. Barriers allow the
programmer (or the compiler) to control the parallelism by
sequentializing some parallel activities. For instance, a single
barrier in the example below reduces the exponential resource
requirement of the \tbx{fib} function to a linear requirement
proportional to the size of the problem. Of course, it also reduces
the parallelism accordingly.

\begin{myexample}{ex:fib}
def fib n = if n < 2 then n
            else \{ x = fib (n-1);
                   ---
                   y = fib (n-2);
                  in x+y \};
\end{myexample}

\subsubsection*{Controlling Frame Storage}

Sometimes a group of activities that are initiated simultaneously may
not exhibit a lot of parallelism because of pre-existing
data-dependencies among them. But under eager evaluation, all the
initiated activities can grab memory resources and hold on to them for
a long time without doing any useful work.  Barriers help in
scheduling the activities in the appropriate partial order so that the
overall resource requirement is reduced. This behavior is illustrated by
the following example.

\begin{myexample}{ex:repeat}
def fold1 f z nil = z
 |  fold1 f z (x:xs) = fold1 f (f z x) xs;
\vsp
def fold2 f z nil = z
 |  fold2 f z (x:xs) = \{ y = f z x;
                         ---
                        in fold2 f y xs \};
\end{myexample}

Assuming that \tbx{f} is a strict function, both \tbx{fold1} and
\tbx{fold2} shown above fold \tbx{f} on a given list of elements from
left to right.  Because of eager evaluation, the \tbx{fold1} function
rapidly expands into a sequence of frames each of which spawns a child
frame to compute the application \tbx{(f z x)}.  Thus it could
use up to $O(n)$ frames for an $n$-element list even if we optimized
\tbx{fold1} for tail-calls.  On the other hand, the \tbx{fold2}
function waits for each child application to finish before moving on
to the next list element, and so it uses at most two frames during
the entire computation. Note that unlike the case of the \tbx{fib}
function in \ex{fib}, no parallelism is lost by inserting this barrier
since the computation is already sequential.

\subsubsection*{Controlling Heap Storage}

Barriers are also useful for scheduling the automatic (or
programmer-specified) deallocation of heap resources once they are no
longer in use. This strategy may be used to manage the heap without
paying any extra overhead for garbage collection, as shown in the
following example. While traversing a large data structure we keep a
local notebook which is released at the end of the traversal.

\begin{myexample}{ex:note}
def compute graph =
 \{ note = make\_notebook ();
   result = traverse graph note;
   ---
   @release note;
  in result \};
\end{myexample}

\subsubsection*{Sequentializing Side-Effects}

Barriers may be used in parallel M-Structure computations for
scheduling side-effects in the desired partial order.  Under eager
evaluation, all side-effects present within a block are initiated in
parallel. Therefore, a barrier may be required to ensure proper
interleaving of \tbx{M-take} (read-and-lock) and \tbx{M-put}
(write-and-unlock) operations.  For instance, a barrier is necessary
in the following example to ensure that the mutable array slot is
taken before the new value is put back, because there is no explicit
data-dependency to control the order otherwise:\footnote{In Id, {\em
M-take} and {\em M-put} operations are represented using a slightly
modified array indexing syntax {\tt a![i]}.  Indexed expressions on
the right-hand-side of a binding are {\em take\/} operations while
those on the left-hand-side are {\em put\/} operations.}

\begin{myexample}{ex:replace}
def replace a i v = 
  \{ x = a![i];
    ---
    a![i] = v;
   in x \};
\end{myexample}

Barriers provide the ability to detect the combined termination of a
group of parallel update operations without sequentializing them
completely. A classic example of this sort is the construction of a
histogram:

\begin{myexample}{ex:hist}
def histogram xs n = 
  \{ a = marray (1,n);
    \{ for i <- 1 to n do
        a![i] = 0; \};
    \_ = accum a xs;
    ---
   in a \};
\vsp
def accum a nil = ()
 |  accum a (x:xs) = 
  \{ i = hash x (bounds a);
    a![i] = a![i]+1;
    \_ = accum a xs; \};
\end{myexample}

The \tbx{accum} function is allowed to unfold automatically,
accumulating the frequencies in parallel into the histogram array
\tbx{a} using M-Structure operations. No sequentialization is imposed
over the accumulations, but the barrier in the function
\tbx{histogram} guarantees that all the accumulations have terminated
before the histogram array is returned. Note that the barrier ensures
that all the computations above the barrier have terminated before
returning the array, although actually we are interested only in the
termination of all side-effects on the array itself.

\subsubsection*{Controlling Access to Shared External State}

Barriers are also useful in managing activities that share a common
external resource or state. Shared peripheral devices, I/O streams,
and protected kernel data-structures may constitute some of the
external state that user programs may need to control or gain access
to. Most functional languages allow only implicit control of such
computation \via monads, continuations, abstract datatypes, or state
transformers \cite{Hudak93,Launchbury94,PeytonJones93}. On the other
hand, in Id such objects are represented explicitly using M-Structures
and access to them is controlled using locks and barriers that provide
mutual exclusion and explicit sequentialization as necessary. For
instance, currently there exist two I/O libraries in Id, sequential
I/O \cite{Berkeley-io} and threaded I/O \cite{Id90.1}, both of which
crucially rely on barriers for proper sequentialization.

\subsection{Syntactic Properties of Barriers}

The definition of barriers in terms of \ibx{pre} and \ibx{post}
regions suggests that the following syntactic properties for barriers
should hold under any reasonable semantics:

\begin{property}[Eliminating Redundant Barriers] Given a statement
group $S^{\sibx{par}}$, we have
\[ \begin{array}{l}
(\; \tbx{---} \\ \; S^{\sibx{par}})
\end{array} \equiv 
\begin{array}{l}
(S^{\sibx{par}} \\ \tbx{---} \; ) 
\end{array} \equiv S^{\sibx{par}} \]
\end{property}

\begin{property}[Associativity of Barriers] Given statement groups
$S_{1}^{\sibx{par}}$, $S_{2}^{\sibx{par}}$, and $S_{3}^{\sibx{par}}$,
we have
\[\begin{array}{l}
  ((S_{1}^{\sibx{par}} \\ \;\;\tbx{---} \\ \;\;S_{2}^{\sibx{par}}) \\
\;\tbx{---} \\ \;S_{3}^{\sibx{par}})
\end{array} \hm \equiv \hm 
\begin{array}{l}
  (S_{1}^{\sibx{par}} \\ \;\tbx{---} \\ \;(S_{2}^{\sibx{par}} \\
\;\;\tbx{---} \\ \;\;S_{3}^{\sibx{par}}))
\end{array}\]
\end{property}
