\section{Formal description of problem}

\subsection{Introduction}

Consider a request which is handled by a sequence of operations that
conditionally issue subrequests.  This structure, a dynamically
unfolding activation tree, is very common.    

In a distributed computing
environment, 




  Further, consider that the user request is handled by
executing subrequests which can also be similarly assigned, on a
request-by-request basis to any of the hosts.  With this freedom,
comes the responsibility of mapping these requests to optimize some
criteria.    

This structure, an
activation tree, is fairly common in distributed computing.  

\subsection{The Static Mapping Problem}

\subsubsection{Activation+ Trees}

An activation tree is a tree $G=(V,E)$ where each vertex $v \in V$
represents the execution of computational procedures, and each edge $e
\in E$ encodes a ``calls'' relationship.  The vertices and edges are
enumerated as $v_1,v_2,...,v_k,...,v_{|V|}$ and
$e_1,e_2,...,e_k,...,e_{|E|}$, respectively.  Associated with each
vertex $v_k$ is an ordering $O_k$ on the edges (calls) that emanate
from it.  Figure~\ref{fig:act_tree} shows a code fragment (a) and its
corresponding activation tree (b).  

\begin{figure}
\label{fig:act_tree}
\begin{center}
\begin{tabular}{ccc}
\epsfxsize=2in \epsfbox{act_tree_code1.eps} & 
\epsfxsize=1in \epsfbox{act_tree_base1.eps} &
\epsfxsize=2in \epsfbox{act_tree_exp1.eps} \\
(a) & (b) & (c)
\end{tabular}
\end{center}
\caption{Activation Trees.  (a) Code.  (b) Activation Tree. (c)
Activation+ Tree.}
\end{figure}

Notice that the activation tree abstraction flattens the basic blocks
surrounding procedure a's procedure calls.  We can always consider the
blocks $a_1, a_2, a_3$ as procedure calls in an and of themselves.  In
effect, by doing this recursively down the activation tree, we arrive
at a different representation, the \actplus tree, where only leaf
nodes of the tree represent computations.  Figure~\ref{fig:act_tree}
(c) illustrates this.   An
in-order traversal of an \actplus tree, executing and executing each
vertex as it is encountered, is an execution of the tree.

Associated with each vertex $v_k$ in an \actplus tree is a probability
$p_k$ that that vertex will be executed.  This allows us to encode
conditionals as shown in Figure~\ref{fig:act_tree_cond}.  

\begin{figure}
\label{fig:act_tree_cond}
\begin{center}
\begin{tabular}{cc}
\epsfxsize=2in \epsfbox{cond_code1.eps} & 
\epsfxsize=2in \epsfbox{cond_tree1.eps} \\
(a) & (b) 
\end{tabular}
\end{center}
\caption{Activation+ Trees and Conditionals.  (a) Code.
(b). Activation+ Tree.}
\end{figure}
 
\subsubsection{Machines}

A node of an \actplus tree executes on a single machine.  There are
$N$ machines, numbered $0..N-1$.  

\subsubsection{Leaf Mapping Functions and PDFs}

For each node $v_k$ in an \actplus tree, $LEAF(v_k)$ is true if it is
a leaf node.  A {\em leaf mapping function}, $M=\lbrace (v_i,j) | v_i
\wedge V \in LEAF(v_i) \wedge j=0 \ldots N-1 \wedge v_i \mbox{is mapped to machine}
j \rbrace $ maps leaf nodes to machines that can execute them.  

Associated with each leaf node $v_i$ is a family of $N$ probability
density functions, $\lbrace f_{ij}(t) | i=0 \ldots N-1 \rbrace$, 
each of which describes how the time to execute $v_i$ mapped to
machine $j$ is distributed.   In particular, $\int_0^{t_0} f_{ij}(t) dt$
is the probability that node $v_i$ executes in $\leq t_0$ seconds when
mapped to machine $j$.  

Given the set of probability density functions $\lbrace f_{ij}
\rbrace$, $LEAF$, vertex execution probabilites $\lbrace p_k \rbrace$
and a leaf mapping function $M$, we can compute the pdf associated with each node on the tree as

\begin{equation}
f_i^M(t) = \left \{
\begin{array}{ll}
p_i f_{ij}(t)                                      & \mbox{if $LEAF(v_i)$} \\
\bigotimes_{v_k \in \mathit{CHILDREN}(v_i)}
                                  p_k f_k^M(t) & \mbox{if $\neg LEAF(v_i)$} 
\end{array} \right .
\end{equation}

where $\otimes$ is the convolution operator and
$\mathit{CHILDREN}(v_i)$ returns those nodes for which an edge
emanates from $v_i$.  

\subsubsection{The objective}

The objective is to maximize the probability that the time to execute
the activation tree, will be in a user or programmer specified range.
That is, we want to choose a mapping $M$ such that $P[t_0 \leq t \leq
t_1 | M]$ is maximum.

\subsubsection{Static Mapping Problem}

Given an \actplus tree $G$, the $LEAF$ function, and the execution
probabilities for the nodes $\lbrace p_k \rbrace$, the {\em static
mapping problem} is to determine the leaf mapping $M$ which maximizes
$P[t_0 \leq t \leq t_1 | M] = \int_{t_0}^{t_1} f_0^M(t)dt$ where
$f_0^M$ is the pdf computed for the root vertex of the tree.  

\subsection{Dynamic Mapping Problem}