\section{\label{future-work-sec}Future Work}

An area that needs to be explored further, which will unquestionably
constitute the bulk of future research, is that of global data
structures. Since global memory accesses typically involve
communication, it is necessary to split threads at the boundary of
remote memory accesses. As a consequence, it will be hard to scale
applications with frequent global memory references on architectures
such as the CM-5.

Two key issues need to be addressed to enable efficient implementations.
First, data structures need to be evenly distributed across all processing
elements and second, they need to be aligned with the computation. Data
structures and computational threads can be aligned either by moving the
data structure, as done by architectures based on globally coherent
caches \cite{ksr}\cite{dash90a}, 
or by moving the computation. Our preliminary results show
that we need to use both techniques to achieve efficient solutions.
However, no general solution has yet surfaced.

Although the distribution and alignment of data structures will undoubtedly
interfere with the scheduling of computational threads, we excluded these
issues in order to obtain a clean and simple execution model, thereby
clarifying the issues of dynamic execution. We believe that this
simplicity will make it easier to identify and to integrate additional
scheduling mechanisms targeted to address the alignment problem. 

\section{\label{conclusion-sec}Conclusions}

%%We believe that the performance of any parallel program must scale
%%over the performance of the best sequential program to be truly
The performance of any parallel program must scale over the
performance of the best sequential program to be truly 
practical. 
Because of the high costs of dynamic scheduling and network
communication in current message-passing architectures, this goal
becomes a serious challenge when programming applications with
unstructured parallelism.

Barring revolutionary hardware solutions, we have argued that there
are effective solutions in software to (a) lengthen sequential threads
in order to offset the costs of dynamic scheduling, and to (b)
preserve the locality of computations to reduce the network traffic.
We believe that these solutions have not yet been effectively explored
by message passing extensions to conventional languages, nor by
higher level parallel languages, because their level of abstraction is
either too low or too high to enable the programmer to effectively
tune an application toward these key optimizations.

The parallel continuation passing model presented in this paper
represents an attempt to bridge this gap. The model can either serve
as a compilation target for a higher level language, or it can be used
directly in conjunction with a sequential language, such as C. In the
latter case it comes as a simple extension, providing the essential
structures needed to synchronize computational threads and to optimize
scheduling decisions. Although it could be argued that PCM is
difficult to program because of its explicit continuation-passing
style, we found it often the case that a program just has a small
kernel that needs to be parallelized, leaving the rest of the program
in its original sequential form (see the ray-tracing example).
Moreover, such a parallelization always increases the granularity of
the sequential threads, resulting in more efficient parallel programs. 

As the outcome of experimenting with PCM, we identified two scheduling
policies of general use, increasing the efficiency of parallel applications
based on a dynamic execution model.
First, the tail-call mechanism gives the programmer the flexibility to
glue short threads into longer ones. Tail-calls will undoubtedly
become extremely important for finer grained  parallel computation, as
has been shown for the Fibonacci example. 
Second, a work stealing scheduling policy enables almost-all-local
computation, resulting in linear and near-linear speedups of the
ray-tracing and protein-folding examples. Since work stealing
is often the determining factor in whether or not a parallel
application executes efficiently, we built this mechanism into the PCM
runtime system as the default scheduling policy. 

