\section{The Map primitive}

The \MAP primitive allows the programmer to place a lower and upper
bound on the execution time of an activation tree.  The structure of
the activation tree is not known a priori - the tree is formed during
execution.  A \MAP implementation provides a best effort service that
tries to meet the timing constraints by dynamically mapping each node
of the activation tree as the tree unfolds.  The number of times the
constraints are met over the course of executing a program (i.e., over
many activation trees) in a particular computation environment
quantifies the performance of a \MAP implementation.  

\subsection{Restrictions on the activation tree to be mapped}

We allow only finite-size activation trees where each node returns
only to its parent.  \verb.Setjmp./\verb.longjump. and exceptions are
not permitted.  Further, each call (node) must be expressible in terms
of data movement to the selected call site, local execution on this
data, which may include further calls, and data movement away from the
call site.  Notice that data movement includes not just the arguments
to the call, but also any static data or object state that the call
will read or modify.  However, any call that requires access to data
that may change due external forces, such as C volatile variables,
cannot be mapped.  In the present document, we restrict ourselves to
single node activation trees - leaf procedures.

\subsection{Timing constraints}

At time $t_{now}$, executing \MAP \verb.foo(). $[t_{min}, t_{max}]$.,
attempts to execute the activation tree whose root node is a call to
the procedure \verb.foo(). so that the tree finishes after $t_{min}$
seconds from $t_{now}$ and before $t_{max}$ seconds from $t_{now}$.
$t_{now} + t_{min}$ is the "later" time - execution should not complete
before this time, while $t_{now}+ t_{max}$ is the "sooner" time - execution
should complete before this time.  This is illustrated in
Figure~\ref{fig:timingconstraints}.

\begin{figure}
\epsfxsize=4in
\centerline{
\epsfbox{timing_constraints.epsf}
}
\label{fig:timingconstraints}
\caption{The timing constraints}
\end{figure}

\subsection{Performance metric}

The form of the Map primitive's is that of a real-time request with
the activation tree being the task and $t_{now} + t_{min}$ being the
deadline.  In a hard real-time system, the performance metric for such
a system is a simple binary value - if all Maps succeed the system is
successful and if any fail it is unsuccessful.  However, Map provides
a best effort service, which means that failure to meet a timing
constraint does not equate to total overall failure.  Indeed, we can
quantify the performance of a Map implementation in many different
ways.  The metric we use here is the percentage of Map requests that a
Map implementation succeeds in satisfying over the course of a
program's execution.


\subsection{Assumptions}

We assume that a primitive exists that will allow us to execute a
procedure call on any node on the system.  Such a capability may be
provided by some sort of DSM, RPC, or RMI mechanism.  We intend to use
the RMI mechanism in the LDOS distributed object system for evaluation
purposes.

\subsection{Execution time of an activation tree}

The execution time of an activation tree depends on how the \MAP
implementation chooses to assign its nodes to hosts in the system.
These choices will affect the time spent communicating into,
executing, and communicating out of each node.  We define the
execution time of an activation tree to be the execution time of its
root node.

\subsection{Execution time of a node}

The time to execute an activation tree node is the time to map,
transfer data, and execute the call it represents and the time to
execute all its children. Thus, the time to execute and activation
tree is the time to execute its root node.  The time spent executing a
node consists of $t_{map}$, the time to map it to a host;
$t_{incomm}$, the time to communicate data to the call site where it
will be executed; $t_{exec}$, the time to execute the node and all of
the its children; $t_{outcomm}$, the time to communicate data out of
the call site; and $t_{update}$, the time to inform the \MAP
implementation of the success or failure of its mapping decision.  If
the time constraints are met, then there is a positive slack time,
$t_{slack}$, before the deadline.

 
\begin{figure}
\epsfxsize=4in
\centerline{
\epsfbox{exec_time_node.epsf}
}
\caption{The execution time of an activation tree node}
\label{fig:exectimenode}
\end{figure}

\begin{figure}
\epsfxsize=4in
\centerline{
\epsfbox{exec_time_leaf.epsf}
}
\caption{The execution time of an activation tree leaf node}
\label{fig:exectimeleafnode}
\end{figure}
 
The execution time for the node, $t_{exec}$, has three components.
The first is a static component, $t_{execstatic}$, which depends on
the host on which the node is being executed, and the nominal
execution time of the node, $t_{execnominal}$.  The nominal execution
time is the execution time of the node on the slowest host in the
system under conditions of no load.  The second component,
$t_{execdynamic}$, represents the extra time it takes to execute the
node given the load conditions on the host is has been assigned to.
The final component, $t_{subcalls}$ is the time needed to execute all
the children of the node. Figure~\ref{fig:exectimenode} shows these
values and their relationship to the timing constraints graphically.

\subsection{Execution time of a leaf node}

In the case of a leaf node there is no $t_{subcalls}$ component to
$t_{exec}$ and we can relate the static and dynamic components to the
hosts and the load.  Figure~\ref{fig:exectimeleafnode} illustrates the
execution time of a leaf node.  Let $t_{execnominal}$ be the execution
time of the node on the slowest host in the system and $\beta$ be
the speedup of the host over that slowest host in the system.  If the
host is twice as fast, $\beta=2$.  The static component of the
execution time, $t_{execstatic}$ is then
\begin{equation}
t_{execstatic} = \frac{t_{execnominal}}{\beta}
\end{equation}
The dynamic component of the execution time, $t_{execdynamic}$ is
 related to the load on the host and $t_{execstatic}$ by 
\begin{equation}
\int_{t_{now}+t_{map}+t_{incomm}}^{t_{now}+t_{map}+t_{incomm}+t_{execstatic}+t_{execdynamic}} \frac{1}{1+load(t)} dt = t_{execstatic}
\end{equation}
and it is related to the nominal execution time, $t_{execnominal}$, and $\beta$ by
\begin{equation}
\int_{t_{now}+t_{map}+t_{incomm}}^{t_{now}+t_{map}+t_{incomm}+t_{exec}} \frac{\beta}{1+load(t)} dt = t_{execnominal}
\end{equation}