% -*- LaTeX -*-
\documentstyle[12pt]{article}
\pagestyle{empty}
% Springer parameters
\textwidth=16cm
\textheight=23.5cm
%\topskip=1cm
\raggedbottom
\abovedisplayskip=3mm
\belowdisplayskip=3mm
\abovedisplayshortskip=0mm
\belowdisplayshortskip=2mm
\baselineskip=14pt
% fit it on page nicely
\topmargin=-1.3cm
\oddsidemargin=.3cm
\evensidemargin=.3cm
% make it look nice
\parskip=6pt
\begin{document}
\input{macros}
\title{Garbage Collection in MultiScheme\\(Preliminary Version)}
\author{James S.~Miller\\Brandeis University\\
Waltham, MA 02254-9110\\USA \and 
Barbara S.~Epstein\\Encore Computer Corp.\\
Marlboro, MA 01752-3089\\USA}
\date{}
\maketitle
% eliminate page number on first page
\thispagestyle{empty}
\begin{abstract}
On stock hardware, our garbage collector commonly takes under 4\% of a
system's time and less than 0.2 seconds at each occurrence.  It
provides an unsurpassed mechanism for reclaiming memory and processing
resources in a parallel system.  Furthermore, the elementary algorithm
is easily extended to a parallel implementation that achieves
significant performance improvement without slowing down the operation
of user programs.

The garbage collector is also an important component of the system
when investigating speculative computation.  The requirement that the
garbage collector recycle tasks that are no longer performing useful
work impacts not only the design of internal data structures, but also
affects the semantics of continuations in a parallel system.
\end{abstract}

\thanks{This research was supported in part by the Defense Advanced
Research Projects Agency and was monitored by the Office of Naval
Research under contract numbers N00014--83--K--0125,
N00014--84--K--0099, N00014--86--K--0180, and MDA903--84--C--0033.
Additional funds and resources were provided by BBN Advanced Computers
Inc., and the Hewlett-Packard Corporation.}
\maketitle
\pagenumbering{arabic}

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

On stock hardware, MIT Scheme's\cite{MITScheme} garbage collection
commonly takes under 4\% of a system's time and less than 0.2 seconds
at each occurrence.  It provides an unsurpassed mechanism for
reclaiming memory and processing resources in a parallel system.
Furthermore, the elementary algorithm is easily extended to a parallel
implementation in MultiScheme that achieves significant performance
improvement without slowing down the operation of user programs.

Our recent work is a direct extension of the work on parallel garbage
collection described by Courte\-manche\cite{MultiTrash} and
Miller\cite{MultiScheme}.  We report results achieved by a number of
researchers at BBN Advanced Computers, Inc., the Massachusetts
Institute of Technology, and Brandeis University.  Collectively, this
work has been directed at both the practical problems related to
achieving a high performance parallel garbage collector on stock
hardware (primarily the work of Rozas, Courtemanche, Miller, and
Johnson) and at exploring ways in which the garbage collector can
support novel uses of parallelism at the user level (Miller and
Epstein).

On some Lisp systems, garbage collection has been so slow that it has
forced users to turn to other implementation languages; this is
unfortunate, since an efficient algorithm has been well known for over
twenty years.  This compacting two-space algorithm, published in
1969\cite{MFY}, is described in Section~\ref{sect:serial} along with
some variations that improve performance in a serial implementation.
Creating a parallel variant of this algorithm is straightforward, but
tuning it to perform well is somewhat more difficult.
Section~\ref{sect:parallel} describes both the algorithm and some of
the performance issues that arise in actual practice.

An efficient garbage collector is an important goal in and of itself,
but by adding one new data type (the {\sf weak pair}) that provides a
link between the user and the garbage collector, we acquire an
entirely new kind of power.  The implementation of the weak pair is
simple (see Section~\ref{gc:low-level}) and forms the basis for a
number of interesting features:

\begin{itemize}
\item The system automatically discards tasks that are no longer
performing useful work.

\item Hash functions on arbitrary Scheme objects can be implemented
without forcing retention of the hashed objects.

\item We can create {\sf populations}\cite{T} to store sets of objects
without forcing retention of the objects.

\item The system can detect and correct an important set of common
errors (failure to release locks, close files, etc.).
\end{itemize}

The first of these features, the garbage collection of useless tasks,
was suggested as long ago as 1977\cite{IncrementalGC}, but in a more
restricted setting.  In a system supporting Halstead's {\tt future}
construct\cite{Multilisp}, the system's data structures be carefully
constructed from weak pairs in order to garbage collect tasks.  As
part of this structuring, MultiScheme separates the notion of a {\sf
task} (an active computational entity, similar to an {\sf
actor}\cite{Actors}) from a {\sf continuation} (the actor's script).
This separation is {\em not} arbitrary, and Section~\ref{gc:root}
provides the rationale, based on a requirement that tasks be
automatically garbage collected.  The section also discusses the
slightly thorny issue of choosing a root for garbage collection that
simultaneously retains tasks of interest to the user and discards
tasks that are actively but uselessly computing.

We close (Section~\ref{sect:speculative}) with a discussion of a form
of parallel processing, called {\sf speculative computation}, that
becomes viable with the effective garbage collection of tasks.
Speculative computation uses ``spare'' computational power to
effectively explore a range of options, some of which may not be
essential to the problem at hand.  We have extended MultiScheme to
provide a notion of task priority as a means for controlling the
scheduling of computational resources.  In addition to merely using
the priority when choosing the next task, MultiScheme dynamically
modifies priorities as a program runs.  In conjunction with the
garbage collection of tasks this prevents a useless task from hogging
resources, while preventing deadlocks from the premature removal of a
useful task.

\section{A Serial Two-Space Collector}
\label{sect:serial}

The basic garbage collection algorithm used in MultiScheme is the
well-known\cite{MFY} two space compacting algorithm of Minsky,
Fenichel, and Yochelson (for a simple but complete description and
implementation see \cite{SAIOCP}).  The algorithm works by copying all
of active memory, compacted and relocated, into a new region of
memory.  We position a {\sf scan} pointer at the start of the new area
of memory, copy the root of the garbage collection from old space to
new space, and position a {\sf free} pointer to the word after the
root (i.e.~to the first free location in the new area of memory).
Then we repeatedly {\sf relocate} the object to which {\tt scan}
points, advancing {\tt scan} to the next object after each relocation.
(Recall that {\tt scan} always points into the new part of memory, and
hence at a copy of some object from the old space.)  Relocating an
object is easy:

\begin{itemize}
\item If the object isn't a pointer, it is left unchanged.
Fixnums\cite{SchemeStandard}, for example, just cause the {\tt scan}
pointer to be incremented.  For long objects consisting of non-pointer
(binary) data (eg.~strings, long integers, or machine language code),
there is a header word indicating how far the {\tt scan} pointer is to
be advanced to skip over the data.

\item If the object is a pointer, it will point into the old address
space.  Under most circumstances, the object to which it points is
copied into the new space and {\tt free} is advanced past the copy.
The original version (in old space) is modified so that its first word
contains a {\sf forwarding pointer} to the newly created copy. (A
forwarding pointer is sometimes called a {\sf broken heart}.)

\item If the object we want to relocate is a pointer, but the first
word of the object it points to is a forwarding pointer, the object
has already been copied into new space.  The forwarding pointer
specifies where the copy is; rather than make another copy the
pointer we are relocating is made to point to the existing copy.
\end{itemize}

This process of relocating objects repeats until {\tt scan} meets {\tt
free}, at which time all the contents of the old memory that can be
referenced have been relocated into the new area of memory.  By
copying into a spare heap the same size as the active one we are
assured that all of the active memory can be copied, and the algorithm
will terminate.  A proof of correctness is based on noting the
invariant that memory between the start of new space and the current
value of {\tt scan} contains pointers only to copies of objects (in
the new space), memory between {\tt scan} and {\tt free} contains
copies of active objects, and memory beyond {\tt free} is not
referenced.

Readers familiar with Baker's incremental garbage
collector\cite{IncrementalGC} or the more recent
generation-based\cite{GenerationGC} garbage collectors will also find
this algorithm familiar, since it forms the basis of all of these
techniques.  The two space collector has a running time proportional
to the amount of memory in active use, unlike the more familiar {\sf
mark-sweep} garbage collector that takes time proportional to the
maximum size of the heap.

\subsection{Static Spaces Improve Performance}

This garbage collector is quite efficient, since the code fits in most
instruction caches and memory reference to the new space is highly
localized.  Unfortunately, a simple implementation will scan and copy
large quantities of memory that are permanently needed by the system.
This is a well-understood problem that has prompted the implementation
of ``generational'' garbage collectors\cite{GenerationGC}.

MIT's CScheme system (on which ours is based) takes an intermediate
approach.  It provides two static areas of memory, known as the pure
and constant areas.  The {\sf pure} area contains only non-pointer
objects and immutable pointers into the static areas --- thus its
contents are never modified by garbage collection and it need not be
scanned.  The {\sf constant} area contains arbitrary (including
mutable) objects; while this area must be scanned in order to relocate
objects to which it points, the contents of the area are never copied.

The user has the ability to move arbitrary objects into either of
these two areas, and moving an object recursively moves all objects to
which the initial one points.  It is important to guarantee that
objects in the pure area never point into the heap.  This is done by
moving those subcomponents that can be mutated by operations internal
to the Scheme system into the constant area instead of the pure area.
The user-visible mutation operations (eg.~{\tt set-car!}, {\tt
set-cdr!}, and {\tt vector-set!}) specifically test for mutation of
objects in the pure area and produce an error rather than store a
pointer to the heap into the pure area .  Users can intercept this
error in order to move the object from the pure area into the constant
area and then perform the mutation.

These two areas provide a degree of flexibility that users can exploit
to cut down the amount of time taken to perform a garbage collection.
By moving immutable objects (such as large data structures constructed
at load time or by initialization procedures) into the pure area,
these objects are neither scanned nor copied at garbage collection
time.  They are also removed from the heap itself, so the frequency of
garbage collection is reduced.  Mutable objects can be moved to
constant space, where they will be scanned but not copied.  Again,
objects in constant space do not occupy space on the heap and decrease
the frequency of garbage collections.

As an example of the usefulness of the pure and constant areas,
consider the runtime system which is written in Scheme.  The majority
of the code and its data structures are moved into one or the other of
the static areas when Scheme is initially bootstrapped.  The result is
dramatic --- we often observe a factor of 7 improvement in the speed
of garbage collection over the same system without the code moved into
the static area.  This number falls as the running program generates
active data on the heap since the speed of a garbage collection is
determined by the amount of active storage.

The implementation of these areas is a very simple variant on the
previous algorithm.  We add a new ``circumstance'' under which an
object isn't copied: if it is located in either the pure or constant
area.  In addition, before copying the root of the garbage collection
to new space, we place the {\tt scan} pointer at the beginning of the
constant area and the {\tt free} pointer at the start of the new heap
space.  We then scan all of constant space. This will copy into the
new space any objects referenced from the constant area (recall that
the pure space has no such references). The root is then copied into
new space wherever {\tt free} points, and the algorithm proceeds as
above.

There are two additional factors that arise as a consequence of
compilation:

\begin{enumerate}
\item Interpretation of a program causes large quantities of data
structure to be {\tt cons}ed for passing arguments (i.e.~to create
environments or closures).  A great deal of the compiler's analysis is
specifically aimed at reducing the need for these data structures.  A
good compiler can eliminate the vast majority of this {\tt cons}ing by
making use of registers and a stack.  One brief test based on MIT's
compiler indicated that compiling a program reduced the {\tt cons}ing
to 44\% of the amount performed by an interpreted version of the
program. By compiling both the program and the runtime system
procedures it called, the reduction was to 12\% of the original
amount.  The pretty printer, a {\tt cons} intensive program, was used
for this test, so these results are extremely encouraging.

\item In MIT's system an interpreted program consists of list
structure, while a compiled program is largely binary data.  While the
compiled code is sometimes as much as 30\% larger than the interpreted
version, only about 28\% of the compiled code is scanned by the
garbage collector.  For simplicity (see \cite{first-class-env})
compiled code isn't placed in the pure area.  Overall, the entire MIT
runtime system requires about twice the amount of storage to be
scanned when it is compiled as when it is interpreted.  There is
reason to believe, however, that this particular program has an
anomolously large amount of scanned code.  Several other large
programs exhibit much smaller expansion.
\end{enumerate}

These two factors tend to act in opposite directions.  The first
dramatically reduces the frequency of garbage collection without
noticeably changing the time required for an individual garbage
collection pass.  The second increases the time required for each
individual pass, but doesn't alter the frequency of the passes.  In
practice we find that our system with a compiled runtime and no user
code takes 0.85 seconds for a garbage collection pass on our
HP9000/320 system based on a 16MHz Motorola 68020.  The same system
when interpreted requires only 0.58 seconds -- a factor of 1.4
degradation imposed by compiling the system.  On the other hand, the
compiled system may garbage collect only one-half as often as the
interpreted system.  Just to get a sense of the balance between these
two factors, we tried a very simple test program.  The system spent
2\% of its time garbage collecting with an interpreted runtime system
and 4\% when the runtime system was compiled.  Clearly, other test
programs would change this balance.

\section{A Parallel Garbage Collection Algorithm}
\label{sect:parallel}

Despite the efficiency of the two-space collector on simple programs,
many programs generate large active data structures on the heap and
consequently undergo large numbers of relatively slow garbage
collections.  The CScheme compiler itself can spend as much as 70\% of
its time garbage collecting when processing a large program with a
small heap size.  One solution, of course, is to increase the heap
size thereby reducing the frequency of garbage collections. This does
nothing to speed up an individual garbage collection pass, and may
degrade performance on a virtual memory system.

Fortunately, the garbage collection algorithm itself is easily
modified to operate in parallel. MultiScheme contains an
implementation of such a parallel garbage collector, and it provides
an interesting case study in practical parallel algorithm design.  An
initial parallel implementation was proposed by
Miller\cite{MultiScheme} and subsequently implemented, described, and
measured by Courtemanche\cite{MultiTrash}.  The basic idea is to
divide the work of scanning the new space equitably between the
processors.

A garbage collection is initiated by a processor that has noticed the
need for more space.  It alerts the other processors and starts a
barrier synchronization that is complete when all other processors
agree to stop running user code and begin the garbage collection phase
(see \cite{multischeme-ijpp} for MultiScheme's support of garbage
collection initiation).  Each processor is responsible for scanning
part of the constant space and copying part of the garbage collection
root, then begins scanning part of the data copied into the new heap
space.  The partitioning of constant space occurs every time an object
is moved into either pure or constant space so it need not be
recomputed when the garbage collection starts.  The root of the
garbage collection includes the processor-private stack areas used by
the Scheme interpreters; each such stack is scanned by its associated
processor\footnote{For architectural reasons, the MultiScheme
implementation on the BBN Butterfly makes a copy of all compiled code
in each interpreter's local memory.  In addition to its stack, each
processor scans its own copy of this code area.}.  The remainder of
the root is shared by all of the processors, and is scanned by the
processor that initiated the garbage collection.

This initial scanning causes some objects to be copied into the new
heap space, and the algorithm must continue by scanning these objects.
This raises two problems: how did the scanning (which occurs in
parallel on all of the processors) manage to copy objects into a
single shared heap area without interspersing their contents and
destroying their integrity?  Furthermore, how can we divide the work
of scanning these copied objects?  In Courtemanche's collector this
was accomplished by dividing the heap space into fixed-sized {\sf
consing partitions} when the system first starts.  At garbage
collection time, each processor grabs one of these partitions as an
{\sf output partition}, used as the destination for objects copied
while it is scanning.  Whenever copying an object would over-fill the
partition, it is {\sf released} to a queue of filled partitions that
will eventually be scanned and a new output partition is taken from
the new heap space.  When the initial scan phase concludes, all
processors enter a loop that attempts to dequeue and scan a filled
partition.  If no partition is available from the queue, the current
output partition is scanned instead.  The algorithm completes when
there are no partitions on the queue and all processors have finished
scanning their own output partitions.

\subsection{Static Memory Allocation}

Courtemanche's system was based on pre-allocating heap space to
specific processors.  That is, when the system was booted the memory
was divided into fixed sized regions and each processor was allocated
one region to be used solely by that processor as a heap.  This gave
the system convenient control over the binding of processors to the
memory that they used for space allocation.  It allowed for
co-locality of a processor and its heap\footnote{On the Butterfly,
MultiScheme deliberately didn't aim for co-locality.  Instead, it
tried to randomly distribute memory references across the Butterfly
switch.}, but at the expense of increasing garbage collection
frequency when the processors allocated space at different rates.
That is, if only one processor actively allocated heap space it would
require a garbage collection as soon as it filled up its own heap.

There is an obvious solution to this problem of uneven space
allocation, but at the cost of losing some control over locality.  The
current implementation of Butterfly Scheme\cite{BBNScheme} dynamically
allocates memory to processors.  It continues to statically divide the
memory between the processors, but maintains a globally visible data
structure that indicates the amount of each partition that is in
actual use.  At system initialization (and after each garbage
collection) each processor grabs a fixed quantum of memory from its
own partition.  As it needs to allocate memory it does so by using
part of this initial quantum.  When it runs out of space it goes back
to the global data structure to see if its partition has sufficient
space to fulfill the request; if so, it bites off another chunk of its
own partition and continues running.  Otherwise it checks all of the
other processors' partitions.  Only if no space is available on {\em
any} processor does it initiate a garbage collection.

Even with this change, however, a hidden penalty arises when the
processors have vastly different amounts of memory on their heaps.
The cost of searching through the global data structure to find a
processor whose consing partition has sufficient space is
significantly higher than the cost of merely allocating space from the
processor's own consing partition.  Both Courtemanche's system and the
current BBN Scheme system try to alleviate this problem by having the
garbage collector divide the active memory equally among the
processors' heaps.  They do this by subdividing each of the consing
partitions into multiple {\sf heaplets}.  At the start of a garbage
collection, each processor takes the first heaplet from its own
consing partition to use as its output partition.  The remaining
heaplets are considered to be organized in a spiral consisting of the
lowest remaining heaplets in all of the consing partitions, then the
next higher heaplets, and so on.  When a processor fills its output
partition it takes the next available heaplet in the spiral for its
new output partition.  At the end of a garbage collection, therefore,
all of the processors' consing partitions are filled to roughly the
same extent -- they differ by no more than one in the number of filled
heaplets in the partition.

This does, however, lead to a phenomenon that Courtemanche called {\sf
partition wastage} (sic).  At the end of a garbage collection each
processor will use as its {\tt free} pointer the {\tt free} pointer of
the highest heaplet used during the garbage collection from its
partition.  The portion of memory that is free in any other heaplets
within the partition is thus wasted -- Courtemanche's partition
wastage.  His measurements show that, as might be expected, partition
wastage rises linearly with the number of processors in the system.

\subsection{Dynamic Memory Allocation}

In addition to the partition wastage problem there is another problem
with the memory allocation systems described above.  As the number of
processors grows, the consing partition must shrink unless the virtual
address space grows proportionately.  And here we encounter a problem
with current architectures: they support 32 bit pointers to byte
addresses but have no data type bits.  Even on today's commercial
parallel processors this is barely sufficient: a 512 processor machine
with a mere 4 megabytes per node requires 31 bits to address all of
the available memory.  This is a particularly severe problem in a Lisp
system that uses a two space collector since it will use half the
address space for each of the two semi-spaces.

But the practical limits are considerably smaller.  The current
implementation of MultiScheme (using 8 bits for type codes) has a
maximum heap size of 4 megapointers. On a 128 processor machine this
means that the individual consing partition is only 32K pointers, and
from this we must take space for the static and program areas.  One
well-known problem of a two-space collector is that it divides this
small amount of space in half by dividing the heap into two parts.
Minsky's original implementation did not suffer from this problem: his
second space was allocated on the magnetic drum.  BBN Butterfly Scheme
uses a similar technique -- the second space is allocated in virtual
memory that isn't accessible through ordinary Scheme pointers because
it lies outside of the 4 megapointer reference range.  At the end of
the garbage collection this inaccessible memory is copied back down
into the Scheme heap.  Since the Butterfly typically has far more
physical memory than is available in a single shared virtual address
space, this mechanism tends to keep both the old and new space in
physical memory.  As a result the copy operation is relatively fast.
It can be even faster under an operating system like Mach, where it
can be replaced by a set of page map operation that use the virtual
memory hardware instead of performing memory operations.

Despite this, any reasonable initial quantum taken by all processors
from their 32K pointer consing partition virtually guarantees that the
system is constantly garbage collecting.  Worse yet, no vectors can be
allocated that exceed the length of a processor's consing partition
since no processor will ever have this much free space.  The problem
is quite dramatic.

Consider the following (uninteresting) program:

\vskip-\lastskip\begin{scheme}
(define (test)
  (define (loop n name)
    (if (= n 0)
        'done
        (begin (vector-cons 100000 'junk) ; Make a large (garbage) vector
               (write name)               ; Show who's working
               (loop (- n 1) name)))))    ; Loop around again
  (for-each touch                         ; Start and wait for 6 tasks
            (list (future (loop 10 'a)) $\dots$ (future (loop 10 'f)))))
\end{scheme}\vskip-\lastskip

\noindent This program has six tasks (named {\tt a} through {\tt f})
regardless of the number of processors used to run the program.
Running on a machine with a maximal heap size of 2.6 megapointers we
would expect this to require three garbage collections since it
allocates (and discards) 6 megapointers of memory.  Using ten
processors this is precisely the observed result.  Increasing this to
twenty processors, however, caused in excess of 60 garbage
collections!  The reason, upon investigation, turned out to be that
the size of a consing partition with twenty processors was just under
100K pointers.  Thus each attempt to {\tt vector-cons} caused a
garbage collection\footnote{The observant reader may point out that
the algorithm described here would, in fact, prevent the system from
ever allocating a vector of 100K elements.  In fact, the BBN
implementation has a special case for handling allocation of large
objects that allows this case to succeed once at the end of each
garbage collection.}!

The solution is again simple, and was implemented by Kirk Johnson and
Jim Miller.  In this solution there is a single global {\tt free}
pointer used by all processors to allocate large chunks of heap space.
When a processor runs out of room in its current heap, it allocates a
new chunk using the global pointer.  It then allocates smaller amounts
as required during execution.  When a processor needs to allocate a
chunk that exceeds the upper limit of the actual shared heap it uses a
privately allocated ``emergency area'' instead and immediately
requests a garbage collection.

This mechanism both reduces the frequency of garbage collections when
the load on the system is unbalanced, and entirely eliminates the
partition wastage.  The implementation has proven efficient, provided
that the ``chunks'' are large enough to reduce contention for the
global {\tt free} pointer.

\subsection{Performance Bottlenecks}

Courtemanche showed that his algorithm achieved linear speed-up to
five processors, but then performance remained constant.  He
identified two specific problems with his garbage collection mechanism
that accounted for this phenomenon: inadequate partitioning of the
constant space, and processor starvation.  The first was the result of
an apparently harmless simplification of the partitioning algorithm
for constant space, and was easily repaired.

Processor starvation is more serious. Courtemanche attributes it to a
lack of active storage available for scanning. As the number of
processors increases there is no work for the additional processors to
perform.  Ultimately, as the number of processors becomes very large
they generate contention just trying to locate scanning to be
performed and the system, in fact, slows down.  This problem was the
subject of recent work at BBN by Guillermo Rozas.  Rozas examined the
sources of contention and processor idle time during garbage
collection.  He identified eight different problem areas:

\begin{enumerate}
\item % (1) Flip
Idle time waiting for the initial synchronization barrier.  This
barrier is required to guarantee that all processors have stopped
allocating space on the heap and ``flipped'' into the new space.

\item % (2) Push and Pop
Contention for the data structure used to allocate partitions to be
scanned.

\item % (3) Memory Lock
Contention for the data structure used to allocate output partitions.

\item % (4) forwarding pointer
Contention for moving a single object.  This occurs when two (or more)
processors are actively scanning memory and both need to move the same
object into new space.

\item % (5) Idle
Idle time because no partition is available to be scanned.  This
occurs when other processors are still scanning memory, since they
might cause a new partition to be available at a later time.

\item % (6) Consing
Idle time waiting for the synchronization barrier indicating
termination of the scanning operation.

\item % (7) Master, Copy
Idle time waiting for the synchronization barrier indicating that all
post-scanning operations have been completed.

\item % (8) Done
Idle time waiting for the processor that initiated the garbage
collection to complete Scheme level code needed by the system to
complete the garbage collection cycle.
\end{enumerate}

Of these, by far the least common is the conflict between multiple
processors for moving the same object.  In fact, to lessen the impact
of this problem to a completely negligible level we carefully arrange
to store the forwarding pointer in old space {\em before} the copy
operation begins.  Thus, another processor will see a completed
relocation as early as possible.  The location in old space that holds
the forwarding pointer is used as a lock to guarantee the atomicity of
the copy operation.

The remaining seven items occur often and can be a source of
significant performance degradation as the number of processors grows.
To help eliminate the contention generated by using a simple spin
to detect synchronization or lock release, Rozas added a set of
tunable delays.  By making some of the delays proportional to the
number of interpreters, the contention is reduced at the cost of a
lengthened minimum delay.

% \marginpar{Measurements?}

\section{Garbage Collection of Tasks}
\label{sect:tasks}

MultiScheme's model of parallelism, based on the {\tt future}, is
directly inherited from Halstead's Multilisp\cite{Multilisp}. A {\tt
future} is composed of two parts: a {\sf task} representing work to be
performed and a {\sf placeholder} representing a value being computed
by one or more tasks.  Tasks are created for the explicit purpose of
calculating a value, and each of these values allows for the
synchronization of the task computing the value (producer) and any
tasks that need the value to continue their own computation
(consumers).  We refer to this as {\sf value-oriented parallelism} as
opposed to the more common task-oriented parallelism generally found
in parallel versions of languages like {\sc c}, {\sc pascal}, and {\sc
fortran}.

\begin{jsmfig}
\vskip-\lastskip\begin{scheme}
(define (make-tree f low high)
  (let ((delta (- high low)))
    (if (zero? delta)
        (f low)
        (let* ((interval (if (even? delta) delta (- delta 1)))
               (mid-point (+ low (/ interval 2))))
          (cons (future (make-tree low mid-point))
                (future (make-tree (+ mid-point 1) high)))))))

(define (search tree value) $\dots$)

(search (make-tree square 1 10) x)     ; {\em For some value} x
\end{scheme}\vskip-\lastskip
\caption{Parallel Tree Search\label{fig:tree-search}}
\end{jsmfig}

Because placeholders act just as the values they represent, the
synchronization supported by MultiScheme is highly dynamic and
resembles the mechanisms used in dataflow computation models.  Storing
a placeholder in a widely visible data structure is a reasonable (and
common) activity, even in a side-effect free program like the one in
Figure~\ref{fig:tree-search}. In this example, {\tt tree} is probably
{\em not} fully constructed when the call to {\tt search} starts.
Thus, the code within {\tt search} must be responsible for
synchronizing with the tasks that are creating the tree.  This
synchronization is dynamic, since the tasks have not even been created
before the search commences.

The parallel tree search of Figure~\ref{fig:tree-search} raises
another problem in addition to that of dynamic synchronization.  If
the function {\tt f} is hard to compute, we should abort the building
of sub-trees as soon as the correct value has been located by the {\tt
search} procedure.  This problem is well-known in serial computing,
and has led to lazy evaluation and the stream-based model of
computation.  But a parallel system, unfortunately, gains its speed
advantage from eager evaluation.  One way out of this dilemma is to
remove tasks from the system as soon as they are known to be unneeded,
an approach suggested by Hewitt and Baker in
\cite{IncrementalGC}.  Another commonly proposed alternative (often in
conjunction with a construct like Common Lisp's {\tt catch}) is to kill
tasks when they become useless.  These two approaches strongly
resemble the same two options for memory allocation -- garbage
collection vs.~explicit release.

Just as prematurely releasing memory in an explicit memory management
system causes problems arising from dangling pointers,
deliberate``task homicide'' can result in unexpected and undesirable
premature reclamation of tasks.  The dangling pointer problem of
memory allocation has its direct analog in a form of deadlock in the
parallel processor system.  Imagine that we modify the program of
Figure~\ref{fig:tree-search} by adding the following code:
\vskip-\lastskip\begin{scheme}
(let ((tree (make-tree 2 20)))
  (if (search tree 3)
      '(FOUND 3)
      (search tree 27)))
\end{scheme}\vskip-\lastskip
Recall that {\tt make-tree} creates the tree using parallel tasks, and
thus the call to {\tt (search tree 3)} may begin before the tree is
fully constructed.  If {\tt search} kills off ``useless'' tasks ---
those constructing parts of the tree that the search didn't have to
examine --- then the subsequent {\tt (search tree 27)} may well try to
search a part of the tree that has not been constructed and whose
tasks have been killed by the earlier search.  The program deadlocks.

While MultiScheme provides procedures to kill
tasks\cite{multischeme-ijpp}, their use is generally discouraged.
Instead, the standard mechanisms for creating tasks (the {\tt future}
construct and the ones described below for speculative computation)
interact with the garbage collector to provide automatic reclamation
of unneeded tasks.  In order to perform this reclamation, MultiScheme
requires mechanisms to reference tasks without preventing their
reclamation and to identify tasks that must continue to run.  The
former is supported by {\sf weak pairs}, discussed in
Section~\ref{gc:low-level}.  The latter is handled by our choice of
task-related data structures and the root of garbage collection, as
discussed in Section~\ref{gc:root}.

\subsection{Low-Level Support}
\label{gc:low-level}

The MultiScheme system incorporates two modifications originally
intended to support the garbage collection of tasks.  Both have since
been merged into the sequential implementation of Scheme, since they
provide useful services beyond their original design goal.

The first modification is the addition of a new data type, the {\sf
weak pair}.  This resembles a standard cons cell\footnote{For purely
aesthetic reasons, the standard operations for use with cons cells do
not operate on weak pairs.  A separate set of operations ({\tt
weak-car}, etc.) are provided instead.}, but with the property that
the car of the cell reverts to {\tt '()} if there are no references to
the object in the car other than through the cars of weak pairs.
Support for these objects\footnote{Objects similar to the weak pair
may exist in other Lisp systems. But the authors are unaware of any
implementation descriptions elsewhere in the literature.} is easily
implemented in a two-space garbage collector, since it provides space
for four pointers at garbage collection time for each pair that is
retained (the original two in old space, plus two more in new space).
These are used as follows:

\begin{enumerate}
\item One old space pointer is used as usual to contain a forwarding
pointer indicating the new location of the cell.

\item The second old space pointer would ordinarily be unused.  It is
used to store the original car of the cell.

\item One new space pointer is used as usual to contain a copy of the
cdr of the cell.

\item The second new space pointer allows each processor to maintain a
list, headed by the processor-private variable {\tt weak-list}, of all
the weak pairs copied by this processor into new space during the
garbage collection.  The type code on this cell indicates that it does
{\em not} contain a pointer to be traced by the garbage collector when
it is subsequently scanned.
\end{enumerate}

At the end of the garbage collection, the cdrs of the weak pairs in
new space are correct.  The cars, however, must be located and
corrected.  This is done in parallel, by having each processor follow
the chain of weak pairs headed by its {\tt weak-list} variable.  For
each cell, the original car (still available in old space, cell 2) is
examined.  If the type code indicates a non-pointer, or the address
indicates an object in pure or constant space, the new car is just the
same as the old car.  Otherwise, the object originally stored in the
car is examined to see if a forwarding pointer is present: if so, the
new car becomes a pointer to the relocated object; if not, the new car
is set to {\tt '()}.

There are three things worth noticing about this algorithm. First, it
is performed in parallel by having each processor responsible for
updating the weak pairs that it copied during the regular scan phase.
Second, it does {\em not} itself allocate memory, and hence can be
safely performed during the garbage collection operation.  Finally, it
must have access to both old and new space, and hence is best
considered a part of the garbage collection operation itself rather
than as a Scheme procedure that must run immediately after the garbage
collection is complete.

The weak pair mechanism has proven quite useful.  It is a convenient
base on which to implement the {\sf weak set} (formerly {\sf
population}) abstraction of {\sc t}\cite{T} and the object hash tables
of MIT Scheme\cite{MITScheme}.  These, in turn, provide the mechanism
upon which to build a variety of user conveniences including the
automatic closing of files reclaimed through garbage collection.

A second mechanism, {\sf precious objects}, has been proposed to
augment the weak pair, and is only now beginning to be explored.  The
goal of the weak pair mechanism is to allow the garbage collector to
reclaim certain objects despite references to them.  By contrast,
precious objects allow the garbage collector to report its {\em
desire} to reclaim certain objects without actually reclaiming them.
Precious objects are implemented by allowing the user to designate an
additional root for garbage collection, called the {\sf precious
object list}.  The garbage collector first performs its normal
operations without considering this list.  After the collection is
complete (either before or after handling weak pairs, depending on the
desired interaction between the two features), the precious object
list is scanned and split in two: one list contains those objects that
are ``alive'' (i.e.~those containing a forwarding pointer indicating
that they were relocated, plus those in constant space and non-pointer
objects) and the other list contains those that would otherwise be
reclaimed.  This second list is then used as the root to commence
another garbage collection pass --- thus preserving the precious
objects.  This list is made available to users after the garbage
collection.

Precious objects can form the base of a number of user services,
including the automatic release of resources when they are no longer
in use.  This is very important for catching and reporting certain
user errors (eg.~forgetting to release a lock).  It is also useful for
interfacing with external services.  The MIT Scheme interface to the X
Windows package, for example, will use this mechanism to release
resources in the X server when a Scheme program ceases to need them.

The precious objects mechanism is desirable but it has not yet been
exploited since it can be mimicked using the (pre-existing) weak pair
mechanism.  MIT Scheme, for example, automatically calls the Unix {\tt
close} operation when all references to a file (through the {\tt port}
data objects) are lost.  This is done by building a weak list of all
the ports in the system.  After each garbage collection, this list is
scanned for entries whose {\tt car} has become {\tt '()} indicating
that the port is no longer in use.  A parallel list is also maintained
containing the information needed to locate the actual operating
system resource that must be released, and the appropriate call to
{\tt close} is issued.  The entry is then spliced out of both lists.
This trick, providing parallel structures for user-accessible and
system internal data structures, allows any system with weak pairs to
mimic a system with precious objects (albeit in a slightly inelegant
manner).

\subsection{System Issues}
\label{gc:root}

Garbage collection of tasks seems easy once we have made the small
changes to the garbage collector that provide the weak pair mechanism.
We need only arrange the system's data structures to use a carefully
chosen combination of ordinary and weak pairs.  We examine every
pointer to a task and ask whether it provides a reason to retain the
task (in which case it must be an ordinary cons cell) or if it is for
purely internal uses (and is implemented with a weak pair).

MultiScheme's value-oriented parallelism leads directly to one kind of
reference: when a value becomes available, all of the tasks that are
waiting for its value must be reactivated.  The connection from the
placeholder receiving the value to the tasks that are activated when
it arrives is maintained using weak pairs.  This allows the garbage
collector to reclaim tasks whose computation has been halted awaiting
the arrival of a value.  Two issues, however, remain: how do we
reclaim tasks that are {\em not} waiting for values (for example,
tasks that are useless but are in an infinite loop), and what prevents
all tasks from being garbage collected?

These questions force us to consider carefully the nature of the graph
traversed by the garbage collector.  We must examine both the edges of
the graph and the root used to locate the ``useful'' portion of the
graph.  Let us begin by assuming that we can choose an appropriate set
of root tasks and memory objects, thus concentrating on the
construction of the graph itself.  Since we have adopted a
value-oriented approach we make the flow of a data value through the
graph the dominant consideration.  That is, we retain a task only if
it is computing a value that is still needed by the on-going
computation.  In terms of MultiScheme, this means that we require a
task precisely when the placeholder for the value it is computing is
required --- the graph must have an edge connecting each placeholder
with the task\footnote{When we discuss speculative computation in
Section~\ref{sect:speculative} we will see that there may be multiple
tasks computing the value of a single placeholder.  Thus, there may be
multiple edges emanating from a single placeholder.} computing its
value.  At first glance, this seems simple enough: when we encounter a
{\tt future} we create a placeholder and a task and simply make the
placeholder reference the corresponding task.  In fact, MultiScheme
has a slot, called the {\sf motivated task}\cite{multischeme-ijpp}, in
the placeholder for just this purpose.

But MultiScheme inherits from Scheme the ability to reify a
continuation into a procedure by using {\tt
call-with-current-continuation}\cite{R3RS}.  What is the nature of the
continuation for a task newly created by {\tt future}?  Clearly, when
the task completes its computation it must store the computed value in
the appropriate placeholder and stop execution.  But what, exactly, is
the ``appropriate placeholder''?  There are two equally legitimate
possibilities, hinging critically on the desired relationship between
a continuation and a task:

\begin{enumerate} \item The continuation for a newly created task has
a specific placeholder built into it.  In this model, the {\em
continuation} contains the information connecting a task with a
placeholder.  The user can be completely unaware of the existence of
tasks. The only role tasks play is as structures internal to the
scheduling of the system itself.

\item The continuation for a newly created task stores the computed
value into whatever placeholder is associated with the task that is
executing.  Thus the {\em task} (not the continuation) contains the
information linking a task to a placeholder.
\end{enumerate}

To make the difference clearer, we can write the Scheme procedure
used to implement the {\tt future} macro for each interpretation.
Assume the transformation:
\vskip-\lastskip\begin{scheme}
(future $exp$) $\leadsto$ (spawn-task (lambda () $exp$))
\end{scheme}\vskip-\lastskip
In our first interpretation the code would be roughly:
\vskip-\lastskip\begin{scheme}
(define (spawn-task thunk)
  (let ((placeholder (make-placeholder)))
    (make-task             ; {\sf Task holds continuation only}
      (lambda (value)      ; {\sf Continuation}
        (determine! placeholder value)))
    placeholder))          ; {\sf Value of {\tt future}}
\end{scheme}\vskip-\lastskip
In our second, we would use:
\vskip-\lastskip\begin{scheme}
(define (spawn-task thunk)
  (let ((placeholder (make-placeholder)))
    (make-task placeholder ; {\sf Task holds placeholder (its {\tt goal}), too}
      (lambda (value)      ; {\sf Continuation}
        (determine! (task.goal (current-task))
                    value)))
    placeholder))          ; {\sf Value of {\tt future}}
\end{scheme}\vskip-\lastskip
The difference in code, clearly, is minor.  But the impact on the
semantics of both continuations and tasks is major, as is the impact
on the garbage collection of tasks.  We can see the difference in
semantics clearly by considering the interaction with MultiScheme
shown in Figure~\ref{fig:interact}.
\begin{jsmfig}
\begin{scheme}
(define cont '())
(define value-1 '())
(define value-2 
  (future (call-with-current-continuation
           (lambda (continuation)
             (set!~cont continuation)
             (let loop-forever () (loop-forever))))))))
; {\sf Wait for {\tt cont} to have a non-null value}
(set!~value-1 (future (cont 'STOP)))

; {\sf What are the values of {\tt value-1} and {\tt value-2}?}
\end{scheme}
\caption{The Semantics of a Task\label{fig:interact}}
\end{jsmfig}
Consider our first semantics.  In this case, when {\tt (define value-2
$\dots$)} is evaluated, {\tt value-2} receives a placeholder as its
value. The continuation for the newly created task explicitly
references this particular placeholder.  After exporting this
continuation to the variable {\tt cont} the task goes into an infinite
loop (hopefully to be reclaimed by the garbage collector).

When {\tt (set!~value-1 $\dots$)} is evaluated, a second task and
placeholder are created.  But this new task calls the continuation
created for the original task (stored in {\tt cont}).  Since this
continuation explicitly references the particular placeholder stored
in {\tt value-2}, the termination of the task causes {\tt value-2} to
have the value {\tt STOP}. {\tt Value-1} contains a placeholder, but
it will never receive a value.

The situation is similar in the second semantics, but the result is
very different.  Neither continuation references a specific
placeholder.  Instead they both look to the task that is executing at
the time the continuation is invoked in order to locate the
placeholder.  It is the {\em second} task that ultimately calls the
task termination continuation, and that task was created with the
intention of supplying a value to the placeholder stored in {\tt
value-1}. Thus it is {\tt value-1} that receives the value {\tt STOP}
and {\tt value-2} will never receive a value.

From a language design point of view, either semantics can be
defended.  There is perhaps a slight preference for the first
semantics, since extending this choice allows us to build a
MultiScheme variant that supports the equivalent of {\sf
or-parallelism} in {\sc prolog}.  Extension in this direction requires
that the act of supplying a value to a placeholder {\em not} allow the
placeholder to be replaced by the value.  Instead it must remain to
record the tasks that have used the value so that a new value arriving
later will cause the same tasks to be resumed again --- the familiar
forking of processes when multiple values are available at a choice
point.

From the system design point of view, however, there is a marked
advantage to the second semantics related directly to our desire to
garbage collect tasks.  By making the task an explicit object and the
repository for the placeholder that will receive a value, we make the
user responsible for maintaining the information needed to correctly
reclaim tasks.  When a task is created with a placeholder as its {\sf
goal}, we add the task to the list of {\sf motivated tasks} that is
part of the placeholder data structure.  This information is
essentially static --- initialized when a task is created and not
subsequently modified.

By contrast, the first semantics requires this information to be
updated whenever a task invokes a continuation.  By itself, this
change is minor; but the ramifications are severe.  Since we cannot
predict the behavior of an arbitrary task, we must assume that it
might invoke {\em any} continuation that is visible to it.  Since this
invocation would lead to supplying a value for the placeholder
associated with the continuation, we must assume that {\em any} task
might be responsible for computing the value of {\em any} (visible)
placeholder.  But this means that we can never reclaim a task!  For
this reason, we have chosen to promote the task to a user-visible
object.  The resulting system has three independent components related
to parallelism:

\begin{description}
\item[{\bf Placeholder}]\mbox{}\\
The representative of a value not yet computed.  These are essentially
invisible to the computation, but provide the value synchronization of
the underlying model of parallelism.

\item[{\bf Continuation}]\mbox{}\\
The representation of work to be performed.  At any time a computation
can create a procedure representing the work it has remaining (by
calling {\tt call-with-cur\-rent-con\-ti\-nu\-a\-tion}).

\item[{\bf Task}]\mbox{}\\
The representation of an active computational agent, similar in spirit
(but not detail) to an actor.  A task has a placeholder whose value it
is computing, and a continuation (the actor's script) representing the
work it is performing to compute that value.
\end{description}

We now understand how to construct the edges of the graph traced by
the garbage collector. Every placeholder has an edge (called the {\sf
motivated task}) connecting it to the task that is computing its
value.  The connections indicating the tasks that must be awakened
when a value has been computed, however, are {\em not} edges of the
graph traversed by the garbage collector.

There are two obvious choices for the root of garbage collection.  We
could either use all tasks active at the time of garbage collection or
use those reachable from the global naming environment.  Both of these
have defects: the former fails to reclaim useless tasks that are in
infinite loops (and hence always running when a GC begins), and the
latter fails to retain tasks spawned by user input.  Our solution is
relatively simple and seems to work well in practice.  The garbage
collector uses as its root $\dots$

\begin{enumerate}
\item $\dots$ the global naming environment.  This is essential in any
case, and serves to retain any processes calculating globally visible
data structures.

\item $\dots$ the stack of any task running with a reduced interrupt
mask at the time of the garbage collection.  Tasks that are in a
critical section change interrupt levels to lock out user interrupts.
This root serves to prevent them from being reclaimed until the
critical section is complete.

\item $\dots$ the set of tasks representing active read--eval--print
({\tt rep}) loops.  Each invocation of a rep loop creates a new task
and this set of tasks is maintained in a global variable.  Thus, this
is really handled through the use of the global naming environment.
\end{enumerate}

\section{Speculative Computation}
\label{sect:speculative}

The ability to garbage collect tasks allows us the freedom to explore
uses of parallelism in which we do not know {\sl a priori} that the
tasks we are creating are necessary --- an area known as {\sf
speculative computation}.  Based on the mechanism used to gain
performance, we distinguish two kinds of speculative computation: {\sf
eager evaluation} and {\sf multiple approaches},

In eager evaluation, we gain speed by overlapping the execution of an
essential task with that of one or more other tasks, and use the value
of the essential task (when it is finally computed) to determine which
of the other tasks is valid.  This approach arises from a natural
desire to evaluate the predicate of an {\tt if} statement concurrently
with both the consequent and the alternative. The performance
improvement is determined by the difficulty of computing the
predicate.  It is easy to define a {\tt speculative-if} macro that
provides precisely this power:
\vskip-\lastskip\begin{scheme}
(speculative-if $predicate$ $consequent$ $alternative$) $\leadsto$
(let ((conseq (future $consequent$))
      (alt (future $alternative$)))
  (if $predicate$ (touch conseq) (touch alt)))
\end{scheme}\vskip-\lastskip

For some problems, the appropriate predicate to use with eager
evaluation is essentially ``use whichever one computes an answer
fastest.''  For example, problems involving complicated searches (such
as those arising naturally in artificial intelligence and theorem
proving) tend to have this characteristic.  For these kinds of
problems it may be productive to devote processing power to following
several alternative problem solving strategies, in the hopes that at
least one of them will ultimately provide a viable solution.  We refer
to this as {\sf multiple approach speculation}, and it is accessible
to MultiScheme users through the procedures {\tt disjoin} and {\tt
await-first}\cite{multischeme-ijpp}.

In both cases, of course, we must worry about possible side-effects
that might lead to non-determinism or errors in one of the speculative
branches of the computation.  Because the garbage collector will
remove any tasks that aren't working toward a useful goal, however, we
needn't worry about explicitly killing ``competitive'' branches once
one of them is resolved.  On the other hand, there is no reason to
squander processing resources if this can be easily avoided.  We have
implemented an intermediate solution\cite{Epstein} to this dilemma by
adding priorities to MultiScheme tasks and using a timer to cause task
preemption.

The model of process scheduling described in \cite{multischeme-ijpp}
is based on an undifferentiated pool of tasks from which some
architecture-dependent mechanism (encapsulated in the procedure {\tt
get-work}) selects tasks to run.  We have modified this model to allow
the user to specify a priority for a task and we require {\tt
get-work} to choose a higher priority task before any lower priority
tasks that may be available.  By combining this with a timer interrupt
mechanism that forces tasks to relinquish the processor after a finite
interval, we provide a service that over time causes higher priority
tasks to take precedence over lower priority tasks.

Using this basic mechanism we have added two higher-level features,
called {\sf promotion} and {\sf downgrading}.  Promotion occurs when a
task must suspend execution while waiting for the value of a
placeholder to be computed.  Since this task can do no further work
until the value of the placeholder is known, we promote the priority
of the tasks that are computing the value of the placeholder to that
of the waiting task.  If these tasks are waiting for some other
placeholder's value, then the tasks computing that value must be
promoted as well, and so on.  The act of {\tt touch}ing a placeholder
(i.e.~waiting for its value to be computed) thus causes the tree of
tasks rooted at the placeholder and generated by the {\sf motivated
task} and {\sf waiting for} slots to be promoted to the maximum of
their current priority and the priority of the task that performed the
touch.

Downgrading operates similarly, but ``in reverse.''  When the
placeholder created by a call to {\tt disjoin} receives a value
(because one of the multiple problem solving approaches has yielded a
value), the priorities of any sibling tasks (i.e.~tasks whose values
were alternatives to the one that has succeeded in computing a value)
are lowered to a very small value.  This change in priority is also
propagated down the tree of tasks in the same way.  With this in
mind, we can rewrite our earlier {\tt speculative-if} macro:
\vskip-\lastskip\begin{scheme}
(speculative-if $predicate$ $consequent$ $alternative$) $\leadsto$
(let ((conseq (future $consequent$ (speculative-priority)))
      (alt (future $alternative$ (speculative-priority))))
  (if $predicate$
      (begin
        (reduce-priority alt (ultra-low-priority))
        (touch conseq))
      (begin
        (reduce-priority conseq (ultra-low-priority))
        (touch alt))))
\end{scheme}\vskip-\lastskip

The details of the propagation mechanism are of some interest, and are
described in detail in \cite{Epstein}.  In essence, we try to maintain
an invariant that a task's priority must be at least as high as the
priority of any task waiting for the value it is computing.  A change
in priority is propagated down this tree until either a task is found
that is actively computing (i.e.~we reach a leaf of the tree), {\bf or}
we encounter a task whose priority already violates this invariant,
{\bf or} modifying the task's priority would violate the invariant.

\subsection{Toy Example: A Rule-Based System}
\label{sect:rules}

To demonstrate the speculative computation mechanisms we will examine
a simplified interpreter for a rule-based system.  The example is
based on a program originally developed for teaching an introductory
undergraduate course in signal processing\cite{algebra}.  It is a
rule-based expression simplifier supplying enough power to handle a
set of rules for simple symbolic algebra.  Like most rule interpreters
it consists of a pattern matcher, a rule firing mechanism, and a
control structure component.  Both the pattern matcher and the control
structure can utilize speculative parallelism, but for simplicity this
example deals only with the control structure.  For a more complete
description of the other components of the system, see \cite{algebra}
and \cite{MultiScheme}.
\vfill
The rule interpreter has an inner loop that takes an expression and
tries to match it against all of the rules.  If a rule matches the
expression, the rule firing mechanism is invoked to produce a modified
(presumably simpler) expression.  If no rule matches, then the
expression is already in its simplest form.  The problem we are
attempting to solve, then, is converting the sequential control
structure of ``multiple solution techniques augmented with a default
result'' into a corresponding speculative (parallel) control
structure.  In doing so, we will assume that rules may be fired {\em
in any order} that terminates and will still arrive at a correct final
result --- the only restriction is that we will not ``give up'' on
simplifying an expression until all rules have failed to simplify it.
This assumption is {\em not} valid in general for rule sets and poses
an important practical limitation to the solution described here.
\vfill
The primitive mechanisms available for speculative computation
directly from MultiScheme ({\tt disjoin} and {\tt await-first})
provide the ability to wait for any one of a set of placeholders to
receive a value.  The problem we have here, however, is more complex.
We must detect the case in which none of the standard solution
approaches provides a result (i.e.~none of the rules match) and
provide a default behavior.  We must code the rule matcher in a way
that allows this to be detected, and we have chosen a rather simple
but perhaps inelegant technique: the rule matcher returns a specific
result indicating failure and we loop until either a match succeeds or
all matches fail.  This is packaged together in the following
procedure:
\vfill
\begin{scheme}
(define (fail) fail)
(define (first-value placeholders default-value)
  (define (failed? object)
    (and (not (placeholder? object))     ; {\sf Has a value, and...}
         (eq? object fail))              ; {\sf the value is a failure}
  (if (null? placeholders)
      default-value                      ; {\sf No alternative}
      (let ((result (await-first placeholders)))
        (if (failed? result)
            (first-value                 ; {\sf Failed: try again}
             (filter-out failed? placeholders) default-value)
            result))))                   ; {\sf Success}
\end{scheme}
\vfill
With this procedure, we can rewrite the sequential control structure
component:
\newpage
\begin{scheme}
(define (scan rules expression)
  (if (null? rules)
      expression
      (match-rule (car rules)
                  expression
                  (lambda () (scan (cdr rules))))))
\end{scheme}\vskip-\lastskip
into the speculative parallel version:
\vskip-\lastskip\begin{scheme}
(define (scan rules expression)
  (first-value
    (map (lambda (rule) (future (match-rule rule expression fail))
         rules))
    expression))
\end{scheme}\vskip-\lastskip

If we are able to estimate the likelihood of success for any given
rule (either statically or dynamically), we can consider supplying a
priority with each rule.  The only change that is needed to {\tt scan}
is to add this priority to the {\tt future} expression:
\vskip-\lastskip\begin{scheme}
(future (match-rule rule expression fail)
        (calculate-priority rule))
\end{scheme}\vskip-\lastskip
MultiScheme then attempts to schedule the matching tasks for the rules
on a priority basis.

\section{Conclusions and Future Work}

We are happy with the performance of our garbage collector on stock
serial hardware; with improvements in hardware performance we
anticipate achieving garbage collection in ``the blink of an
eye\footnote{Psychologists put this figure of merit --- the maximum
amount of time that can elapse without altering the perception of
effective control --- at 0.05 seconds.}'' Since garbage collection
need not interfere with either data collection or control signalling,
a serial Lisp system using this collector can be seriously considered
for use in hard real-time systems.

Unfortunately, the parallel implementation does not perform as well.
This is due in part to the technological lag between serial processors
used in inexpensive desktop workstations and those in current parallel
processors.  Presumably this will change with time.  Also, the
contention generated during parallel garbage collection remains
significant.  We plan to complete a set of measurements (currently
underway) aimed at quantifying this contention with the goal of tuning
the garbage collector as a function of the number of processors
available.

Our initial work in taking these measurements has shown us the
difficulties involved in both gathering statistics and visualizing
them.  We are using a standard set of tools available on the BBN
Butterfly, and by practical experience are gaining insight into their
uses and limitations.  We plan to capitalize on this experience by
generating a similar set of tools within the MultiScheme environment.
We expect to provide a dynamic (rather than our current
post-mortem\cite{BLUI}) visualization tool, triggered by a measurement
task that runs periodically in the spirit of Clamen's original
work\cite{Clamen}.

Our work on measuring the garbage collector raises another issue that
has long been a concern.  Having a substantial program of genuine
practical interest provides tremendous motivation and the insight
needed to develop tools appropriate to the problem at hand.  Our
interest in the garbage collector has helped spur the development of
tools for visualization of parallel programs written in {\sc c} (since
that is the implementation language for the garbage collector itself).
By developing a high performance Lisp environment on a parallel
processor, we hope to attract implementors of one or more major Lisp
applications.  In conjunction with these implementors, we will have
both the necessary resources and (more importantly) the necessary
motivation and experience to capitalize on the technological base
provided by parallel processors.


\bibliographystyle{jsm}
\bibliography{area}

\end{document}
