\section{Implementation of Id on *T} 
\label{implementation}

*T is a parallel, distributed-memory machine~\cite{*T}.  The *T
architecture extends a basic RISC instruction set with low-overhead,
user-mode communication and synchronization primitives.  In this
paper, we use a simulator for a machine based on the 88110MP
processor.  The 88110MP is Motorola's superscalar RISC processor
extended with an on-chip message and synchronization unit (MSU).  On
this machine, messages consist of 4 to 24 32-bit words. A full-sized
message may be composed from data present in general-purpose registers
and sent in 6 instructions.

*T runs a Unix-like operating system.  A parallel job running on *T
consists of a separate process, or {\em player\/}, on each
processor.  These players have independent virtual address spaces, but
may refer to a global 64-bit address space through the MSU by using
split-phase transactions.

In the rest of this section, we present some details of the
implementation of Id on *T and of performing distributed garbage
collection on this machine.

\subsection{Microthread Scheduling on *T}

The 88110MP MSU provides hardware support for scheduling {\em
microthreads\/}.  A microthread is a compiler-defined thread,
described by an instruction pointer (IP) and a frame pointer (FP).  A
microthread, by definition, executes to completion once it has been
invoked.  It may send messages or fork other microthreads that are
deposited in a stack of ready-to-run microthreads.

Messages always contain a microthread descriptor as the first two
words of payload.  Normally, messages are handled by invoking the
microthread described within the message, so these microthreads are
termed {\em message handlers\/}.

A microthread's last operation is to schedule the next microthread of
the highest priority. The MSU provides a {\tt sched} instruction that
returns the IP,FP of the next microthread to be run in a 64-bit
register pair. The highest priority microthread is selected from a
simple priority queue consisting of incoming message handlers, the
microthread stack, and several microthread registers.  Message
handlers have higher priority than computation microthreads.

%%The scheduler operates by selecting the highest priority microthread
%%%descriptor from a simple priority queue:
%%%\begin{center}
%%%\begin{tabular}{|ll|}\hline
%%%priority & name \\ \hline
%%%0 (high) & UTDR0 \\ \hline
%%%1 & OVERFLOW\_UTD \\ \hline
%%%2 & RXQ.Head.Handler \\ \hline
%%%3 & UTDR3 \\ \hline
%%%4 & UTDR4 \\ \hline
%%%5 & UTS.Head \\ \hline 
%%%6 & UNDERFLOW\_UTDR \\ \hline
%%%7 & UTDR6 \\ \hline
%%%8 & UTDR7 \\ \hline
%%%\end{tabular}
%%%\end{center}
%%%Each of the UTDR's is activated by a {\tt stut} instruction which writes a
%%%microthread descriptor.  The UTS is an on-chip microthread stack cache.
%%%Microthreads which are forked are pushed on this stack.  The overflow and
%%%underflow handlers are enabled when the on-chip microthreads stack
%%%overflows or underflows.  The RXQ is the queue of messages in the network
%%%receiver.  This priority is activated whenever there is a message in the
%%%queue.

\subsection{Layout of Memory}

The memory of an Id process on *T is divided into six areas that are
themselves distributed or replicated across the nodes:
\begin{center}
\begin{tabular}{|l|l|}\hline
\multicolumn{1}{|c|}{\cbx{Memory Area}} & 
\multicolumn{1}{c|}{\cbx{Type}} \\ \hline
 Code & replicated \\ 
 Static Data & replicated \\ 
 C Stack & distributed \\
 Frame & distributed \\ 
 Heap & distributed \\
 Presence Bits & distributed \\
\hline
\end{tabular}
\end{center}

The code and static data areas are replicated --- each node gets a copy of
the whole program and all of its constants.  Each node also has a stack
that is used for calling into C procedures from Id.  The Id run-time system 
is implemented in C and may also use the C stack. 

%%%  These C procedures are well-behaved and always restore the stack-pointer
%%% to its original state when they return.

The frame area contains the activation frames for each Id procedure
that is invoked.  When a procedure is invoked, the run-time system
chooses a processor on which to allocate the frame, then sends a
message to that processor, which allocates a frame in its own frame
area.

The heap area contains all of the heap-allocated Id objects. In our
implementation of Id on *T, all scalar objects and pointers to heap objects
are 64 bits in size.  Furthermore, these pointers are always aligned on
8-byte boundaries when stored in memory.  Each 64-bit word in the heap has
an associated 2-bit presence value in the presence-bit area.  These
presence bits are used to implement Id's non-strict array, I-structure, and
M-structure operations.

Our compiler and run-time system never store a pointer to the interior
of an object in a frame-slot or another Id object.  Therefore, a
pointer found within a frame or a heap object always points to the
head of the {\em active area\/} of the object. The active area of the
object is actually preceded in memory by some information managed by
the run-time system including the object's size (used for
deallocation) and the time when it was allocated (in instruction
cycles --- for statistics collection).

\subsection{Garbage Collection on *T}

Garbage collection on *T can be initiated either by request from the
Id program or by the run-time system when one of the processors finds
out that it is running out of heap storage.  Our current policy is to
initiate garbage collection when the allocated storage on a node
reaches a specified fraction (say, 0.75) of its total storage.

Since the heap is shared globally, all processors must participate in a
global garbage collection. Therefore, when one processor decides to do
garbage collection, all other processors are informed about it.  Currently,
we have implemented a simple stop-and-collect garbage collection scheme.

First, the processors drain all messages out of the network because
the messages may carry live pointers to heap objects.  As messages are
drained from the network, their handlers are invoked.  Our message
handlers can modify memory locations or fork other microthreads, but
they cannot send messages.  We can handle all messages and eventually
reach quiescence, as long as we do not run any threads scheduled by
the message handlers.  Since we invoke message handlers as the network
drains, there are no queues of messages to consider as part of the
root-set during garbage collection.

Once the network is drained, all processors synchronize and then
initiate the mark phase. In this phase, all live and reachable objects
are marked according to one of the object identification techniques
starting from the distributed root set of activation frames currently
in use. This process requires global communication among processors to
mark objects distributed across the machine. After global marking is
completed on all nodes, the processors synchronize again and then each
processor begins a local sweep phase. A final synchronization is
performed after sweeping is completed on all nodes, and then the Id
threads are allowed to resume computation.

\subsubsection{Type-Reconstructed Garbage Collection}
\label{trgc}
The mark phase of the Type-Reconstructed Garbage Collection (TRGC)
follows the compiler-directed object identification scheme described
in the last section. Currently, we have only implemented the
interpreted marking scheme with full type reconstruction. During the
mark phase, the frame memory of each processor is traversed locally to
find the activation frames that belong to the current dynamic call
tree. Each activation frame that is currently in use is
type-reconstructed and then its contents are searched for heap objects
to be marked using their reconstructed types. The type-reconstruction
of a frame may be overlapped with marking of objects in another frame,
so the overall cost of type-reconstructed marking is a combination of
the two.

\subsubsection{Conservative Garbage Collection}
\label{cgc}
%%%
%%% @Article(boehm88a,
%%%   Author = {Boehm, H.-J. and Weiser, M.},
%%%   Title = {Garbage Collection in an Uncooperative Environment},
%%%   Journal = {Software: Practice and Experience},
%%%   Year = 1988,
%%%   Volume = 18,
%%%   Pages = {807-820},
%%%   Month = sep
%%% )

The mark phase of the Conservative Garbage Collection
(CGC)~\cite{Boehm88a} requires no source type information.
Conservative garbage collectors use a simple, conservative test to
determine whether a value in a frame or a heap object is a pointer to
another object.  Since pointers are identified conservatively, CGC may
assume that there are live references to an object when there are
none, therefore some objects may remain uncollected. Also, CGC cannot
compact or copy objects because conservatively identified pointers
cannot be updated.  Finally, CGC has no knowledge of the source types,
therefore it must examine every slot of every reachable object and
no short-circuiting based on scalar-type information is possible.

In our system, the conservative pointer test is implemented as
follows. CGC tests each 64-bit value to see if it is aligned to a
64-bit boundary and if it points within the heap area.  Then, it
checks to see if the value points to the head of a heap object. This
is a very simple test because in our compilation model, actual
pointers never point to the interior of objects.  Furthermore, the
run-time system marks the head of each allocated object with a special
presence-bit pattern.  Therefore, CGC simply checks for this pattern
at the head of the current value.  If this test succeeds then the
value is considered to be a pointer and the object is marked.  This
test may mark some objects that are not actually reachable because a
value in memory happens to look like a pointer to that object.
However, the test is guaranteed to mark only actual heap objects.

%%%
%%% \subsection{Type-Tagged Garbage Collection}
%%%
%%% We wanted to use basically the same object representations in our
%%% type-tagged garbage collector as with our other two garbage
%%% collectors.  Therefore we chose to keep type-bits in an area parallel
%%% to the value bits, similarly to the storage of presence-bits for heap
%%% object.  In fact, we extend the number of bits kept in the presence
%%% area by one to indicate whether the value-bits represent a pointer.
%%%
%%% We take a similar approach to tagging values in an activation frame.
%%% We pack the type-bits for the frame slots into a bit vector stored in
%%% the frame after the frame slots. These type-bits, either in the
%%% bit-vector in the frame or stored with the presence-bits of the heap,
%%% are updated whenever the corresponding value is updated. This update
%%% cost must be taken into account in computing the overall cost of
%%% type-tagged garbage collection.
%%%
%%% [The type-tagged garbage collector is not implemented yet, so no
%%% performance numbers yet.]

\subsubsection{Compiler-Directed Storage Reclamation}
\label{cdsr}
For comparison purposes, we have also implemented the explicit,
compiler-directed storage reclamation scheme (CDSR) \cite{Hicks93}
within the same compiler and run-time system framework. In this
scheme, no separate garbage collection needs to be performed: the
compiler inserts code to deallocate an object when it can determine
the object to be garbage.  This analysis has a substantial
compile-time cost and also a small run-time synchronization cost that
is somewhat difficult to separate from the cost of the Id application.
Also, the static analysis may not be able to reclaim all the garbage
that is generated by the program.  So, we present this scheme only to
compare its relative storage management efficiency to that of the
garbage collected schemes.  It is also possible to simultaneously use
the explicit storage management scheme to get most of the large
objects along with a garbage collector that catches the smaller,
harder to analyze objects.  We believe that a mixed approach would
yield better performance than either scheme on its own.
