Distributed Filaments: Efficient Fine-Grain Parallelism on
a Cluster of Workstations
Vincent W. Freeh, David K. Lowenthal, Gregory R. Andrews
Abstract
A fine-grain parallel program is one in which processes are typically
small, ranging from a few to a few hundred instructions. Fine-grain
parallelism arises naturally in many situations, such as iterative
grid computations, recursive fork/join programs, the bodies of
parallel FOR loops, and the implicit parallelism in functional or
dataflow languages. It is useful both to describe massively parallel
computations and as a target for code generation by compilers.
However, fine-grain parallelism has long been thought to be
inefficient due to the overheads of process creation, context
switching, and synchronization. This paper describes a software
kernel, Distributed Filaments (DF), that implements fine-grain
parallelism both portably and efficiently on a workstation cluster.
DF runs on existing, off-the-shelf hardware and software. It has a
simple interface, so it it easy to use. DF achieves efficiency by
using stateless threads on each node, overlapping communication and
computation, employing a new reliable datagram communication protocol,
and automatically balancing the work generated by fork/joing
computations.
Download the full text of this paper in
POSTSCRIPT (217,230 bytes) form.
To Become a USENIX Member, please see our
Membership Information.