\section{Selector Performance}


At time $t_{now}$, a selector is choose the best host on which to
execute a a single node (the current node) of the activation tree
given a timing constraint $[t_{min},t_{max}]$.  An ideal selector will
pick one of the group of hosts for which $t_{min} \leq t_{map} +
t_{incomm} + t_{exec} + t_{outcomm} + t_{update} \leq t_{max} $.  If
all these values were known at $t_{now}$ or if they depended soley on
static information known at $t_{now}$, the choice would be easy.
However, both of the communication times ($t_{incomm}$ and
$t_{outcomm}$) as well as the execution time ($t_{exec}$) also depend
on dynamic properties such as available network bandwidths and
latencies, and on the load of the hosts.  In addition, the execution
time, because it includes the execution time of the whole subtree
rooted at the current node, depends strongly on the structure of the
activation tree, which we do not know until after this and all lower
level mapping decisions have been made.  In
Figure~\ref{fig:exectime_node} we refer to the sum of the execution
time of the children of the current node as $t_{execsubcalls}$.  

In the following, we examine a simplified problem.  We assume that
communication is free, and thus $t_{commin}=0$ and $t_{commout}=0$.
Further, we consider mapping only leaf nodes of activation trees,
which means that $t_{exec}$ does not depend on the execution times of
any children since $t_{execsubcalls}=0$.  We also elliminate the
mapping and update times ($t_{map}=0$ and $t_{update}$) to further
simplify the problem.  Elliminating these quantities for the leaf node
case is somewhat reasonable since almost every selector we study runs
very quickly relative to the nominal execution times we want to map.
The sole exception is the neural network selector which is
comparatively expensive.  Typical execution times for the selectors we
examine are given in table~\ref{tab:typical_selector_exec_times}.  The
static and dynamic elements of execution time are highly realistic due
to our trace-based simulation technique, as described in
Section~\ref{sec:trace_based_sim}.  To summarize, in this section we
are studying the performance of different selectors on mapping leaf
nodes onto realistic hosts with free communication ignoring the cost
of mapping.  A contribution of the thesis will be to address the full
problem.

Since the map primitive provides only best effort semantics so far as
meeting the timing constraints on any particular call, many
performance metrics are possible. The soft real time community has
produced several classes of metrics of increasing complexity.  FILL
THIS SPACE.  The metric we explore here is the percentage of calls the
selector maps that meet their timing constraints.

We want to understand how the structure of the program to be mapped
and the properties of the underlying compute infrastructure we are
running on affect the performance of the selectors.
Section~\ref{sec:structure_of_act_trees} discusses the structure of
activation trees from typical programs and
Section~\ref{sec:load_traces} discusses the properties of load on end
systems.  At present, we have only minimal data about the dynamic
properties of network environment.  

Since we currently can only map leaf nodes onto systems with zero cost
at this point, we only map
single node activation trees --- leaf procedures calls.  The program
properties we examine are the length and distribution of $t_nominal$,
the nominal execution time of a procedure.  The properties of the
computing infrastructure we studied are mean load and mean epoch
length

\subsection{Methodology}

The simulator described in Section~\ref{sec:simulator} was used to
explore the sensitivity of the selectors to characteristics of the
hosts and the programs.  

\subsection{Characteristics}

Hosts and computing environments exhibit many different
characteristics.  Similarly, the structure of activation trees can be
characterized in many ways.  We want to determine how each of these
characteristics affect selector performance, and which characteristics
have the greatest effect.  Of course, the space formed by the cross
product of these characteristics is impossibly large to cover fully.
Instead of attempting this Herculean task, we will restrict ourselves
to the most important, obvious, and seemingly pertinent
characteristics of the measurements we have actually collected (see
Section~\ref{sec:load_traces}.  

To characterize the load traces we shall use to synthesize the
execution times, we shall use the mean load and the mean epoch length.
Recall from Section~\ref{sec:load_traces} that classifying load traces
by these two characteristics provide does a nice job of separating
hosts, in particular the hosts of the PSC cluster. For most of our
evaluation, we concentrated on the PSC alpha supercluster hosts since
the traces for these machines show the most variation in the mean load
and mean epoch length characteristics.  

Since we currently ignore communication time, there are no network
characteristics to vary.

The current system is limited to mapping only leaf nodes, so we we are
restricted in the program characteristics we can vary.  There are two
that we use.  The first is the nominal execution time of the node.
The second is the distribution of nominal execution time for the
node.  

These four characteristics are summarized in
table~\ref{tab:characteristics}.  We will sample the space formed by
the cross product of mean load, mean epoch length, and nominal
execution and leave the effect of different distributions of the
nominal execution time to a separate analysis.

\begin{table}
\begin{center}
\begin{tabular}{ccc}
\begin{tabular}{|c|}
\hline
Host \\
Characteristics  \\
\hline 
Mean Load        \\
Mean Epoch Length \\
\hline
\end{tabular}
&
\begin{tabular}{|c|}
\hline
Network \\
Characteristcs \\
\hline 
none \\
\\
\hline
\end{tabular}
&
\begin{tabular}{|c|}
\hline
Program \\
Characteristics \\
\hline
Nominal execution time \\
Distribution of nom. exec. time.\\
\hline
\end{tabular}

\end{tabular}
\label{tab:characteristcs}
\caption{Host, Network, and Program characteristics}
\end{center}
\end{table}

\subsection{Sampling the space}

In order to evaluate the effect of the host and program
characteristics on the performance of selectors, we need to synthesize
compute environments for each combination of characeristics.
Table~\ref{tab:host_groups} shows the compute environments we shall
examine and Figure~\ref{fig:host_groups} shows which hosts are
chosen.  The name of each combination encodes the combination.  The
digit encodes the number of hosts in the group, and the first letter
encodes whether the mean load is (S)mall, (M)ixed, or (L)arge, while the
second letter encodes whether the mean epoch length is (S)hort,
(M)ixed, or (L)ong.  Small means that all the hosts in the group have
mean loads of around 0.2, while large means that they have mean loads
of roughly 1.1, and mixed indicates roughly half have 0.2 loads and
half have 1.1 loads.  Similarly, short means that all the hosts in the
group have mean epochs lengths around 250 seconds, while long means
they have mean epoch lengths around 450 seconds, and mixed indicates a
roughly even mixture of the two.

Notice that we vary epoch length and mean load catagorically.  This is
because we have a limited number of traces from which to start.  Also
note that we are missing three combinations because we have no trace
data from which to synthesize the combinations.  

We shall examine nominal execution times of 50ms, 100ms, 500ms, 5s,
10s, 20s, 30s, and one minute.  There are 48 combinations of the load
categories, epoch length categories, and nominal execution times.  We
examined the performance of the 10 active selectors on these 48
combinations and also the performance possible by choosing to always
run on each individual host.

\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
 & \multicolumn{3}{c}{Load Catagory} \\
\hline
Epoch Category & Small & Mixed & Large \\
\hline
Short          &  5SS  &  9MS  & 4LS \\
Mixed          &  9SM  &  8MM  &    \\  
Long           &  4SL  &       &    \\
\hline
\end{tabular}
\label{tab:host_groups}
\caption{Test configurations for PSC hosts}
\end{center}
\end{table}

\begin{figure}
\centerline{
\epsfxsize=4in
\epsfbox{machine_groups.epsf}
}
\label{fig:host_groups}
\caption{Test configurations for PSC hosts}
\end{figure}


\subsection{Effect of varying nominal time}

\landscape
\begin{figure}
\begin{tabular}{ccc}
\epsfxsize=2.6in
\epsfbox{effect_of_nom_time_5SS.epsf}
&
\epsfxsize=2.6in
\epsfbox{effect_of_nom_time_9MS.epsf}
&
\epsfxsize=2.6in
\epsfbox{effect_of_nom_time_4LS.epsf}
\\
\epsfxsize=2.6in
\epsfbox{effect_of_nom_time_9SM.epsf}
&
\epsfxsize=2.6in
\epsfbox{effect_of_nom_time_8MM.epsf}
&
\\
\epsfxsize=2.6in
\epsfbox{effect_of_nom_time_4SL.epsf}
&
&
\tiny
\begin{tabular}[b]{c}
\epsfxsize=2.6in
\epsfbox{legend.epsf}
\\
\begin{tabular}[b]{|c|c|c|c|}
\hline
 & \multicolumn{3}{c|}{Load Catagory} \\
\hline
Epoch Category & Small & Mixed & Large \\
\hline
Short          &  5SS  &  9MS  & 4LS \\
Mixed          &  9SM  &  8MM  &    \\  
Long           &  4SL  &       &    \\
\hline
\end{tabular}
\end{tabular}
\normalsize
\\
\end{tabular}
\label{fig:effect_of_nom_time}
\caption{The effect of varying nominal execution time}
\end{figure}
\endlandscape

\subsection{Effect of Timing Constraint Slack}

\landscape
\begin{figure}
\begin{tabular}{ccc}
\epsfxsize=2.6in
\epsfbox{effect_of_constraint_100ms_5SS.epsf}
&
\epsfxsize=2.6in
\epsfbox{effect_of_constraint_100ms_9MS.epsf}
&
\epsfxsize=2.6in
\epsfbox{effect_of_constraint_100ms_4LS.epsf}
\\
\epsfxsize=2.6in
\epsfbox{effect_of_constraint_100ms_9SM.epsf}
&
\epsfxsize=2.6in
\epsfbox{effect_of_constraint_100ms_8MM.epsf}
&
\\
\epsfxsize=2.6in
\epsfbox{effect_of_constraint_100ms_4SL.epsf}
&
&
\tiny
\begin{tabular}[b]{c}
\epsfxsize=2.6in
\epsfbox{legend.epsf}
\\
\begin{tabular}[b]{|c|c|c|c|}
\hline
 & \multicolumn{3}{c|}{Load Catagory} \\
\hline
Epoch Category & Small & Mixed & Large \\
\hline
Short          &  5SS  &  9MS  & 4LS \\
Mixed          &  9SM  &  8MM  &    \\  
Long           &  4SL  &       &    \\
\hline
\end{tabular}
\end{tabular}
\normalsize
\\
\end{tabular}
\label{fig:effect_of_constraint_100ms}
\caption{The effect of different timing constraints.  In each case,
$t_{nominal}=100ms$ and the constraint is $[0,t_{max}]$ where
$t_{max}$ varies from 100ms to 300ms.}
\end{figure}
\endlandscape





%\begin{figure}
%\epsfxsize=4in
%\centerline{\epsfbox{effect_of_nom_time_5SS.epsf} }
%\label{fig:effect_of_nom_time_5SS}
%\caption{The effect of varying nominal execution time -- 5SS}
%\end{figure}

%\begin{figure}
%\epsfxsize=4in
%\centerline{\epsfbox{effect_of_nom_time_9MS.epsf} }
%\label{fig:effect_of_nom_time_9MS}
%\caption{The effect of varying nominal execution time -- 9MS}
%\end{figure}

%\begin{figure}
%\epsfxsize=4in
%\centerline{\epsfbox{effect_of_nom_time_4LS.epsf} }
%\label{fig:effect_of_nom_time_4LS}
%\caption{The effect of varying nominal execution time -- 4LS}
%\end{figure}

%\begin{figure}
%\epsfxsize=4in
%\centerline{\epsfbox{effect_of_nom_time_9SM.epsf} }
%\label{fig:effect_of_nom_time_9SM}
%\caption{The effect of varying nominal execution time -- 9SM}
%\end{figure}

%\begin{figure}
%\epsfxsize=4in
%\centerline{\epsfbox{effect_of_nom_time_8MM.epsf} }
%\label{fig:effect_of_nom_time_8MM}
%\caption{The effect of varying nominal execution time -- 8MM}
%\end{figure}

%\begin{figure}
%\epsfxsize=4in
%\centerline{\epsfbox{effect_of_nom_time_4SL.epsf} }
%\label{fig:effect_of_nom_time_4SL}
%\caption{The effect of varying nominal execution time -- 4SL}
%\end{figure}


\subsection{The effect of varying load}

%\begin{figure}
%\centerline{
%\begin{tabular}{c}
%\epsfxsize=4in
%\epsfbox{effect_of_load_small_epoch.epsf} \\
%5SS 9MS 4LS \\
%\epsfxsize=4in
%\epsfbox{effect_of_load_mixed_epoch.epsf} \\
%9SM 8MM  \\
%\end{tabular}
%}
%\label{fig:effect_of_load}
%\caption{The effect of varying load}
%\end{figure}

\subsection{The effect of mean epoch length}

%\begin{figure}
%\centerline{
%\begin{tabular}{c}
%\epsfxsize=4in
%\epsfbox{effect_of_epoch_small_load.epsf} \\
%5SS 9SM 4SL \\
%\epsfxsize=4in
%\epsfbox{effect_of_epoch_mixed_load.epsf} \\
%9MS 8MM \\
%\end{tabular}
%}
%\label{fig:effect_of_epoch}
%\caption{The effect of varying epoch length}
%\end{figure}

\subsection{The effect of varying nominal execution time distributions}

%\begin{figure}
%\epsfxsize=4in
%\centerline{\epsfbox{effect_of_varying_tnominal_5SS.epsf} }
%\label{fig:effect_of_varying_tnominal_5SS}
%\caption{The effect of varying nominal execution time -- 5SS}
%\end{figure}

%\begin{figure}
%\epsfxsize=4in
%\centerline{\epsfbox{effect_of_varying_tnominal_9MS.epsf} }
%\label{fig:effect_of_varying_tnominal_9MS}
%\caption{The effect of varying nominal execution time -- 9MS}
%\end{figure}

%\begin{figure}
%\epsfxsize=4in
%\centerline{\epsfbox{effect_of_varying_tnominal_4LS.epsf} }
%\label{fig:effect_of_varying_tnominal_4LS}
%\caption{The effect of varying nominal execution time -- 4LS}
%\end{figure}

%\begin{figure}
%\epsfxsize=4in
%\centerline{\epsfbox{effect_of_varying_tnominal_9SM.epsf} }
%\label{fig:effect_of_varying_tnominal_9SM}
%\caption{The effect of varying nominal execution time -- 9SM}
%\end{figure}

%\begin{figure}
%\epsfxsize=4in
%\centerline{\epsfbox{effect_of_varying_tnominal_8MM.epsf} }
%\label{fig:effect_of_varying_tnominal_8MM}
%\caption{The effect of varying nominal execution time -- 8MM}
%\end{figure}

%\begin{figure}
%\epsfxsize=4in
%\centerline{\epsfbox{effect_of_varying_tnominal_4SL.epsf} }
%\label{fig:effect_of_varying_tnominal_4SL}
%\caption{The effect of varying nominal execution time -- 4SL}
%\end{figure}


\landscape
\begin{figure}
\begin{tabular}{ccc}
\epsfxsize=2.6in
\epsfbox{effect_of_varying_tnominal_5SS.epsf}
&
\epsfxsize=2.6in
\epsfbox{effect_of_varying_tnominal_9MS.epsf}
&
\epsfxsize=2.6in
\epsfbox{effect_of_varying_tnominal_4LS.epsf}
\\
\epsfxsize=2.6in
\epsfbox{effect_of_varying_tnominal_9SM.epsf}
&
\epsfxsize=2.6in
\epsfbox{effect_of_varying_tnominal_8MM.epsf}
&
\\
\epsfxsize=2.6in
\epsfbox{effect_of_varying_tnominal_4SL.epsf}
&
&
\tiny
\begin{tabular}[b]{c}
\epsfxsize=2.6in
\epsfbox{legend.epsf}
\\
\begin{tabular}[b]{|c|c|c|c|}
\hline
 & \multicolumn{3}{c|}{Load Catagory} \\
\hline
Epoch Category & Small & Mixed & Large \\
\hline
Short          &  5SS  &  9MS  & 4LS \\
Mixed          &  9SM  &  8MM  &    \\  
Long           &  4SL  &       &    \\
\hline
\end{tabular}
\end{tabular}
\normalsize
\\
\end{tabular}
\label{fig:effect_of_constraint_100ms}
\caption{The effect of different timing constraints.  In each case,
$t_{nominal}=100ms$ and the constraint is $[0,t_{max}]$ where
$t_{max}$ varies from 100ms to 300ms.}
\end{figure}
\endlandscape