% -*- Mode: LaTeX -*-

\section{Introduction}
\label{sec:intro}

Data-parallel programming models, as embodied in *Lisp and CM-Fortran,
identify well-defined computation and communication phases that are
separated by barriers to ensure proper synchronization among the
various parallel activities. Some parallel machines like the CM5 and
Cray T3D even provide such barrier support in hardware.  In this
paper we study the use and implementation of barriers under a more
general, multi-threaded, MIMD programming model, in which
barriers need to be localized to specified subsets of
parallel tasks in order to provide fine-grain control over
synchronization and resource usage.

Our study is in the context of Id \cite{Id90.1} and pH \cite{pH-doc},
which are non-strict, implicitly-parallel, functional languages
extended with I-Structures \cite{Arvind89} and M-Structures
\cite{Barth91}. Barriers were introduced in Id to provide partial
sequencing of M-Structure operations.  However, their semantics were
not given precisely at that stage \cite{Barth92}.  Subsequently, pH
was designed to follow the precise definition of Haskell
\cite{Haskell90} combined with the eager evaluation model and the
non-functional extensions of Id. This prompted a formalization of
barrier semantics for both Id and pH. The first such attempt was made
in \cite{Stoy94}, both in terms of CSP \cite{Hoare85} and (for the
functional layer) denotationally.  This paper presents a different
formalization in terms of graph rewriting systems previously used to
describe the semantics of Id \cite{Ariola94}.

The rest of the paper is organized as follows. In \sec{eager}, we
discuss some important characteristics of non-strict, eager
computations. We describe the fully parallel evaluation model of Id
and pH, differentiating between the \ibx{result} and the
\ibx{termination} of an eager computation, and introduce the concept
of control regions.  In \sec{uses}, we introduce barriers informally
and present several examples of their use in controlling parallelism,
managing program resources, and providing fine-grain control over
scheduling of side-effects.

In \sec{kernel}, we describe the formal framework for barrier
semantics by introducing a simple kernel language with parallel
reduction semantics and a weak head-normal form operator (\lbx{W}).
In \sec{dataflow}, we describe the concept of termination and propose
the first semantics for barriers based on a purely eager, dataflow
graph execution model. This is sufficient for both resource
management and side-effect control, although it turns out to be a
little fragile with respect to program transformations.  \sec{frag}
highlights these shortcomings and identifies some ways to fix them.
In \sec{alter}, we present the second semantics for barriers,
attempting to overcome some of these shortcomings by mixing eager
evaluation with lazy identifier referencing.  Finally, \sec{conclude}
presents the summary and directions for future work.
