% This is the second of the rts proposals.  I switched thesis topics
% from scheduling to the parallel run-time system.  This way, I hope
% to get my masters very soon.

\documentstyle[12pt]{article}
\input /bk/derek/tex/setup
\input /bk/derek/tex/macros
\input fig
\input illustrations

\def\illustrationfileprefix{/bk/derek/research/ms/pics/}

\begin{document}
\bibliographystyle{plain}
\pagestyle{empty}
%\markright{DRAFT: \today}

\begin{center}
{\bf Massachusetts Institute of Technology\\
Department of Electrical Engineering and Computer Science\\
}
\vspace{.5in}
{\bf Proposal for Thesis Research in Partial Fulfillment\\
of the Requirements for the Degree of \\
Master of Science}
\end{center}

\begin{flushleft}
Title: Activation Frame Memory Management for the Monsoon processor

Submitted by: 
\begin{tabular}{ll} 
Derek Chiou & {\makebox[2.5in]{\hrulefill}} \\
NE43-203    & (Signature of author) \\
\end{tabular}

Date of Submission: \today

Expected Date of Completion: Aug, 1991 

Laboratory where thesis will be done: Laboratory for Computer Science

Brief Statement of the Problem:\\ 

Multiprocessor architectures require some sophisticated, yet fast
memory management primitives to support procedure calls in high level
languages.  These primitives serve two intertwined purposes --
allocation of activation area, called a {\em context} or a {\em
frame}, for an iteration of a procedure, and, since a pointer to a
frame contains a processor number, distribution of work across the
nodes of the multiprocessor.  We will describe several implementations
of an activation frame memory management system, implement one of them
on the Monsoon dataflow multiprocessor, and analyze its
advantages and disadvantages with respect to execution overhead,
storage efficiency, and work distribution.

Supervisor Agreement:\\
The program outline in this proposal is adequate for a Master's
thesis.  The supplies and facilities required are available, and I am
willing to supervise the research and evaluate the thesis report.
\end{flushleft}

\begin{flushright}
\vspace{1in}
{\makebox[4in]{\hrulefill}}\\
Gregory M. Papadopoulos, Asst. Professor of EECS
\end{flushright}

\newpage
\pagestyle{plain}

\section{Background}


The Computation Structures Group at the Laboratory of Computer Science
of MIT, in cooperation with Motorola, is currently building Monsoon, a
multiprocessor dataflow machine\cite{Culler90}.  Monsoon is
intended to run programs written in Id\cite{Nikhil90}, a high level
declarative language which supports iteration, recursion, arrays and
higher-order functions.  Run-time system code needs to be implemented
so that we can utilize the machine with code produced by a compiler.
The goal of this thesis is to design, implement, test and characterize
such a run-time system.  Specifically, we will focus on the problem of
activation frame storage management.

\subsection{Activation frames}

One manages a computer's data memory as two distinct parts: the stack
area and the heap area.  The stack contains activation frames, one for
each invoked procedure\footnote{We use ``procedure'' a little loosely
here.  The codeblock associated with a frame might not actually be a
user procedure, nor does every user procedure invocation require a
frame.  This is for the compiler to decide.  We use procedure to
denote a compiler-defined block of code that has procedure calling
conventions wrapped around it.}. Activation frames contain procedural
variables and linkage pointers back to the previous procedure.  It is
important to note that the lifetime of a stack variable is equivalent
to the lifetime of the procedure invocation whose frame contains the
variable.  Heap area contains data that exists longer than the
lifetime of a single procedure or data that is very large.  Since the
focus of this thesis is on the management of activation frames, we
will not discuss heaps except in some rudimentary fashion to examine
the similarities between a parallel frame allocator and a sequential
heap allocator.

Virtually all language systems which support recursion call procedures
in the following way.  Note that the calling procedure is the one that
initiates all of the steps.

\begin{enumerate}
\item Allocate the frame.
\item Copy linkage pointers and any parameters that are to be passed
in the frame.
\item Run the called procedure, returning the results to the caller.
\item Return the frame.
\end{enumerate}

We will describe the way sequential computer systems perform steps one
and four and then show why parallel computer systems implementations of
steps one and four are more difficult and thus more interesting.

\subsubsection{Frame allocation on sequential computers}

The model of execution on a sequential computer makes allocating and
deallocating activation frames very easy.  Only one procedure may be
active at any time, and when a procedure returns, it must return to
its caller.  Thus, a simple stack of activation frames suffices as a
data structure for managing frames on a sequential computer.  

Stacks are very easy to implement.  Conceptually, one keeps a base of
current frame pointer and a top of stack pointer\footnote{Turns out a
little hack can reduce this to one pointer, the top of stack.  When
you use an activation frame, however, you use it from the top of stack
{\em down}, but you allocate activation frames {\em up.}} and enforces
some calling convention which puts the linkage to previous activation
frames in an easy to find location (generally, the base of the
activation frame.)  Code to maintain the stack can be inlined into
each procedure, since it is simply a matter of incrementing or
decrementing the stack and base of current frame pointers.  Thus, the
allocating and deallocating frames, steps one and four of the calling
scheme described in the previous section can be implemented by one
instruction (add or subtract) for each pointer, plus optional
instructions to check for overflow.

\subsubsection{The problem for parallel computers}

\begin{fig}{heapstackpar}{A Tree of Parallel Activation Frames}
\illustration{heapstackpar}
\end{fig}

The sequential computing paradigm gives us frame allocation and
deallocation basically for free, since there is a definite pattern of
procedural calls allowing us to implement frames on a stack.  We are
not so fortunate in parallel computing.  Since a procedure may have
multiple outstanding calls to other procedures, we wind up with a {\em
tree} of activation frames.  

Let us examine an example of a parallel tree of frames which is given
in Figure~\ref{heapstackpar}.  Think of the figure as a snapshot of
all allocated frames at a specific point in time.  $R$ is the initial
procedure called by the user.  At this point in time, $R$ has
outstanding calls to $T$, $U$, and another instance of $R$ (the first
instance of $R$ had recursively called itself -- thus, two instances
of $R$ exist.)  $T$ has called $X$, and $U$ has called $Y$ and $Z$.
The second instance of $R$ has called $T$, $V$, and $W$. 
%{\bf but $b$ and $c$ will still return before $a$.  Perhaps
%we can take advantage of this?}

Parallel computation relaxes the constraints of when a procedure must
return. For example, knowing the order in which $Y$ and $Z$ were
called will not, in general, tell us anything about which procedure
will return first.  Parallel frame allocation is a mix between stack
and heap allocation on a sequential computer.  A full implementation
of a parallel frame manager would essentially be a heap manager,
including all of the associated complexity.  We simplify the problem
by restricting the number of different sizes a frame can be to allow
the frame allocator to run much more quickly. This constraint greatly
simplifies the code of our frame manager, thus increasing its speed.
Steps one and four of the frame usage algorithm for this model of
parallel computation, therefore, is considerably more involved than
the correspnding steps for a sequential computer.

Monsoon takes the position that a single frame must exist on a single
processor.  Thus, work is divided between processors at a procedural
level.  The frame allocator will, therefore, partition work across
processors by how it handles requests for frames.  We consider load
distribution/balancing as an important part of frame allocation.


\section{Thesis}

We propose to design, write, test and instrument a useful frame
manager that will run on the Monsoon multiprocessor.  Statistics on
the performance of the manager with respect to execution overhead,
storage efficiency and work distribution will be reported.
Suggestions for future work will be discussed.

\subsection{Monsoon hardware}

The run-time system will be written for Monsoon\cite{Papadopoulos88},
a multithreaded processor designed to be a building block for a
parallel computer.  Each of the eight pipeline stages of Monsoon are
independent from one another.  Thus, a thread\footnote{It is difficult
to define ``thread''.  We mean a stream of instructions that execute
sequentially without interruption.  Interruptions come from operations
with non-deterministic latency that have not returned in time for the
next instruction in the sequence to execute when it should.} may only
execute one out of eight cycles, since the next instruction is not
executed until the previous one comes out of the pipeline.  Because of
this, critical sections are especially expensive -- we can only
process a locked resource one out of every eight cycles.

Threads in Monsoon are given some extra resources.  There are twenty four
registers in Monsoon, three associated with each of the eight possible
running threads.  Also, if a supervisor call is made, the supervisor call
thread is given a small ephemeral frame which it can use as a normal
procedure uses a frame.  Note that each set of three registers and an
ephemeral frame are associated with a specific value of $(clock-tick$ 
mod eight).  Thus, a thread that wants to use the ephemeral state cannot
lose its place in the pipeline, or it will lose its state.  To keep
its place in the pipeline, threads must use a special class of
instructions that recirculate exactly one token and that do not do any
synchronization which might require the pipeline to bubble.

All threaded code on Monsoon must be written in {\tt
MONASM}\cite{Traub90}, our assembly language, since our compiler
currently does not produce threaded code.  Writing in {\tt MONASM}
also allows us to hand-tune the code to run as quickly as possible.

Monsoon has a strong advantage as an experimental machine -- its
instruction set is redefinable using a lookup table loaded with
``microcode'' which maps opcodes to control lines for the processor.
Several instructions were written to support run-time system code.
Some of the important ones are {\tt stake}, {\tt plt} and {\tt plp}.
{\tt stake} (spinning take) checks a location to see if it is present.
If the location is present, it will set the location to be empty and
send the value to the next instruction.  If the location is not
present, the {\tt stake} instruction will execute again.  {\tt plt}
(processor local take) takes (reads and sets presence bits to zero) a
value from local memory and maintains a thread, while {\tt plp}
(processor local put) puts
(writes and sets presence state to present) the value it is passed
into the location it is passed.  Note that {\tt plp} only has a single
form right now, which accounts for some inefficiencies in our code.

\subsection{Run-time systems for Monsoon}

\subsection{A simple RTS for Monsoon}

\begin{fig}{fig: oricode}{Free-list Get and Return Context}
\small
{\centering {\bf GetContext}}\\
\begin{verbatim}
stake [FREE_LIST]        ; spin take on the head of free list
jf    v, EMPTY_FREE_LIST ; jump to empty_free_list if free list is empty
mov   v, [*CONTEXT]      ; put context into location in local frame
plt   v                  ; get the pointer to the next frame
mov   v, [FREE_LIST]     ; put the new free list back
\end{verbatim}

{\centering {\bf ReturnContext}}\\
\begin{verbatim}
stake [FREE_LIST]        ; spin take on the free list
mov   v, [*FREE_LIST]    ; put the free list head into a local location
mov   [*CONTEXT], v      ; get the pointer to the returning context
plp   v, [*FREE_LIST]    ; put the former head of the free list 
                         ; into first location of returning context
mov   [*CONTEXT], v      ; get the pointer to the returning context
mov   v, [FREE_LIST]     ; push the free list back
\end{verbatim}
\normalsize
\end{fig}

We wrote a simple run time system based on a free-list to bootstrap
Monsoon and to do preliminary software development.  The code for {\tt
GetContext} and {\tt ReturnContext} is shown in Figure~\ref{fig:
oricode}.  {\tt GetContext} spin-takes on the global location
{\tt FREE\_LIST}.  Once it has the free-list, it checks if there are
any available frames by checking if the list is empty.  If a frame is on
the free list, {\tt GetContext} puts a pointer to that free frame into
slot {\tt *CONTEXT} in its ephemeral frame (the * means that the assembler
will allocate a local frame slot to the location).  {\tt GetContext}
then reads ({\tt plt}) the first slot in the gotten frame which
contains a pointer to the next frame $n$ in the list.  The pointer to
$n$ is then written back into the {\tt FREE\_LIST} position.  Some code
which saves the return address and some other important information is
omitted for clarity.

{\tt ReturnContext} is similar, in that it obviously supports the same
protocol.  It spin-takes the free-list, links the returned context
onto the free-list and writes back the free-list\footnote{Notice how
we have to wrangle the location and the data to be put around since
{\tt plp} has only one form.  Something to work on.}.  

From the code, it is easy to see that our simple run-time system has
fixed sized frames.  This turns out to be a problem since all frames
must be as large as the largest frame that might ever be needed in a
specific run.  When we first started, our compiler would generate
frames that were close to 1000 frame slots large -- now, due to some
advanced compiler work, our frames are upper bounded to under 300.
Many procedures use far fewer frame slots and it would be a
significant advantage to have at least some ability to allocate
different sized frames.

This run-time system, though simple, is rather inefficient since there
is only one global lock on the free-list.  In programs with a lot of
function calls (we use {\tt nfib} because of the number of function
calls it makes), the free-list allocation scheme consumes 22\% or more
of all cycles just spinning on the free-list.  Another problem with
the free-list allocator is that it does not permit frames to be on
other processors.  Since the run-time system must be a critical
section, the code cannot make non-local fetches, and thus the simple
free-list, where the pointer to the next frame is encoded into the
previous frame, would not be implementable.



\subsection{Better Monsoon Run-time Systems}

Two parallel run-time systems have been suggested by members of our
research group.  One tries to minimize synchronization while the other
is designed to permit multiple frame sizes.

\subsection{Fast synchronization}

Young\cite{Young90RTS} proposed an extremely fast run-time system that
takes advantage of the ephemeral frames.  He builds a data structure
called a ``block'' each of which contains a constant number of
pointers to frames.  A full block and an empty block is associated
with each ephemeral frame.  When a allocate or deallocate frame thread
enters the pipeline, the ephemeral frame associated with it services
the call by returning a frame found in the full block or would put a
returned frame into the empty block.

The scheme also includes two global queues: a full block queue and an
empty block queue.  Each queue is large enough to contain pointers to
all the blocks.  Thus, when an ephemeral frame's block becomes
full/empty, it is put onto the full/empty queue and an empty/full
block is extracted from the other queue to replace the one returned to
the queues.  When a queue empties out, the queues are swapped.

Needless to say, this scheme is fairly complicated, and is pretty
difficult to write efficiently in {\tt MONASM}.  This scheme has been
implemented and has been shown to require essentially no
synchronization overhead.  Though the number of instructions executed
increases by some small fraction due to more instructions run within
the run-time system, the critical path decreases some 20\% from the
simple free-list RTS when running programs that call a lot of
procedures ({\tt nfib}.)  That percentage decreases a lot when running more
normal programs, however.

There are two main flaws to Young's run-time system.  The first is
that there is a possibility of starvation when there are contexts
still available.  Since each ephemeral frame has its own private
block of frames, if the ephemeral frame that is associated with an
allocate request is out of frames and the global full queue is out of
blocks, then the request cannot be satisfied even though there are
ephemeral frames that might contain allocable contexts.  A lot of
extra frames (some 127 per processor if blocks are size eight) are
needed to guarantee that the system will not halt due to a perceived lack
of frames.

The second problem is that it is difficult to have different sized
frames.  Currently our ephemeral frames are 32 words big -- any
additional pointers will eat up that space.  Of course, we could
enlarge the ephemeral frames, but still the problem of false
starvation exists and would become worse if we have different frame
sizes to deal with. Also, the complexity of the RTS would become that
much greater.

\subsection{A Multiple Frame Size RTS}

A compromise RTS that we have been examining is one based on a single
queue for each frame size.  This run-time system can be written in
such a way as to minimize synchronization (perhaps not as much as
Young's, but pretty close), maintain a small number of instructions
and permit multiple frame sizes.  

The basic scheme for this RTS is a single queue for each frame size.
That queue has associated with it 2 pointers, a head and a tail.  We
can detect the size of frame a codeblock needs by examining some state
passed to the frame allocator (we wrote a new instruction to examine
that state.)  The allocator/deallocator reads the desired frame size
and dispatches accordingly.

This RTS is still more complicated than the simple free-list RTS,
which increases the number of instructions executed and the critical
path, but due to clever coding we have reduced the synchronization
costs dramatically.  We feel that running real applications with
different frame sizes, we should see some significant improvement.
This run-time system will be the basis of the thesis.

\subsection{Load distribution and parallelism}

As noted earlier, load distribution is an important part of frame
allocation.  Load distribution is the partitioning of work to
different processors and is a significant problem for parallel
machines.  The thinking in our group for a long time has been that we
expose so much parallelism that a simple and approximately random
load distribution scheme, though it might be somewhat unbalanced,
should be able to keep all processors reasonably busy.

We plan on interleaving frames of different processors to
each frame allocator.  Since our current compiler convention will
return frames to the processor that allocated it, once a frame is
assigned to a processor, it will always belong to that processor.  

We will measure the performance of the simple scheme for load
balancing, to see if the performance is acceptable.  Acceptable
performance, at a very high level, is the percentage of idles on all
of the processors.  If the maximum percentage of idles is close to the
number of idles for a single processor, the load distribution is
clearly acceptable.  If the maximum percentage of idles for a parallel
Monsoon is significantly greater than the percentage of idles for a
sequential Monsoon, we must examine the amount of available work
(parallelism) there is in the compiled algorithm.  If there is enough
work, the load distribution is clearly at fault and would need to be
improved.  A better way to check if the load distribution is working
is by looking at idle profiles of each processor and seeing if one
processor is ever doing much more work than other processors.  If the
simple load distribution algorithm does not work, we will have a better
idea of how to improve it after looking at the data.

\section{Schedule}

My schedule is as follows.

\begin{tabular}{|p{4in}|l|l|}
\hline
Task  			& Expected & Actual \\\hline
\hline
Write Fast Synchronization RTS & Mar 91 & Mar 91      \\\hline
Debug Fast Synchronization RTS on MINT (single PE) & Apr 91 & Apr 91 \\\hline
Write Multiple Frame Size RTS & May 91  & May 91      \\\hline
Debug Multiple Frame Size RTS on MINT & May 91 & May 91 \\\hline
Debug Multiple Frame Size RTS on hardware & Jun 91  &    \\\hline
Characterize load balancing   & Jul 91  &             \\\hline
Write thesis		      & Aug 91  &             \\\hline
\end{tabular}

Both the fast synchronization and multiple frame size frame allocators
have been implemented and tested on MINT\cite{Beckerle90}, an
instruction-level simulator for Monsoon.  Currently I am
characterizing the latter and have produced encouraging results.  I
hope to do a lot of experimentation on the Monsoon hardware.  The
hardware is not yet stable, but we expect it to improve soon.

The work to be done is characterization of the frame allocator which
will include collecting statistics telling us how much time is spent
in the allocator in comparison to the total run time and examining
the load distribution and the efficiency of the multiple frame sizes.
Statistics will be produced for all of the major benchmarks developed
by our group.  Suggestions for future improvements will be developed
during the characterization time and when writing the actual thesis.

\bibliography{short-abbrevs,kt}

\end{document}