% $Id: new_mes.tex,v 1.8 2006/07/24 02:36:27 aporter Exp $
\section{Performance-Oriented Regression Testing}
%%%\vspace*{-0.2in}
\label{mes}
   
As software systems evolve, developers often run regression tests to
detect unintended functional side effects.  Developers of
perfor\-mance-inten\-sive systems must also detect unintended side
effects on end-to-end QoS.  A common way to detect these effects is to
run benchmarks when the system changes.  As described in
Section~\ref{intro}, however, these efforts can be confounded for
systems with many possible configurations because time and resource
constraints (and often high change frequencies) se\-verely limit the
number of configurations that can be examined using only in-house
resources.

For example, our earlier experiences applying Skoll to
ACE+\-TAO~\cite{Schmidt:04b} showed that ACE+TAO developers have a
limited view of their software's QoS since they routinely benchmark
only a small number of common configurations.  QoS degradations not
readily seen in these configurations, therefore, can and do escape
detection until systems based on ACE+TAO are fielded by
end-users~\cite{Schmidt:04b,Schmidt:04k}.  The key problem here is
that the ACE+TAO developers are benchmarking a small and
unrepresentative sample of system configurations, so their
extrapolations from this data are bound to be unreliable. 

To address this problem we have developed and evaluated the {\em
reliable effects screening} process, which uses ``design of
experiments'' theory~\cite{kola} 
% Done: Adam, Atif, can you please add a citation for DoE here?
to determine an appropriate subset of system configurations to
benchmark when the system changes.  This section describes how we
implemented the reliable effects screening process, applied it to
ACE+\-TAO+\-CIAO, and disscusses several process choices developers must
make when applying it.

%%%\vspace*{-0.2in}
\subsection{The Reliable Effects Screening Process}
%%%\vspace*{-0.2in}
\label{mse}

Reliable effects screening (RES) is a process we developed to detect
performance degradation rapidly across a large configuration space as
a system changes.  This process identifies a small subset of
``important'' configuration options that substantially affect
variation in performance.  Benchmarking a ``screening suite''
containing all combinations of these important option settings (with
other options assigned randomly) should therefore provide a reliable
estimate of performance across the entire configuration space at a
fraction of the cost and effort of exhaustive benchmarking.

At a high level the process involves the following steps:
\begin{enumerate}
\item {\em Compute} a formal experimental design based on the system's
QA task model.

\item {\em Execute} that experimental design across volunteered
computing resources in the Skoll computing grid by running and
measuring benchmarks on specific configurations dictated by the
experimental design devised in Step 1.

\item {\em Collect, analyze and display} the data so that developers
can identify the most important options, {\em i.e.}, the options that
affect performance most significantly.

\item Conduct {\em supplementary analysis} again on volunteered
computing resources to check the basic assumptions underlying Step 1
and to confirm the results of Step 3.

\item {\em Estimate} overall performance (in-house, if possible)
whenever the software changes by evaluating all combinations of the
important options (while randomizing all other options).

\item Frequently {\em recalibrate} the important options by restarting
the process since these effects can change over time, depending on how
rapidly the subject system changes.
\end{enumerate}

\subsection{Screening Designs Background}
% Adam, Atif, I feel like this subsection is hard to follow since it
% it long and seems to combine a bunch of topics without adequate
% substructure.  Could you please add some \noindent {\bf ...}
% subheadings to make it easier to follow?

The first step of reliable effects screening is to identify options
accounting for the most performance variation across the system's QA
task space.  We do this by executing and analyzing formally-de\-signed
experiments, called {\em screening designs}, which are described in
Kolarik~\cite{kola}, Wu and Hamada~\cite{wu}, or the NIST Engineering
Statistics Handbook
(\url{www.itl.nist.gov/div898/handbook/index.htm}). Screening designs
are highly economical plans for identifying important low-order
effects, {\em i.e.}, first-, second-, or third-order effects (where an
$n^{th}$-order effect is an effect caused by the simultaneous
interaction of $n$ factors).

To better understand screening designs, consider a full factorial
({\em i.e.}, exhaustive) experimental design involving $k$ independent
binary factors.  The design's run size (number of experimental
observations) is therefore $2^k$.  Although such designs allow all
$1^{st}$- through $k^{th}$-order effects to be computed, they quickly
become computationally expensive to run.  Screening designs, in
contrast, reduce costs by observing only a carefully selected subset
of a full factorial design.  The tradeoff is that they cannot compute
most higher-order effects because the selection of observations
aliases the effects of some lower-order interactions with some
higher-order ones, {\em i.e.}, it conflates certain high- and
low-order effects.

Which effects are conflated depends on the design's {\em
resolution}. In resolution $R$ designs, no effects involving $i$
factors are aliased with effects involving less than $R-i$
factors. For instance, a resolution III design is useful to evaluate
``clear'' (no two aliased together) $1^{st}$-order effects, where all higher effects
are negligible.  Here all $1^{st}$-order effects will be clear, but
they may be aliased with $2^{nd}$- or higher-order effects.  This
conflation is justified only if the high-order effects are indeed
negligible.  If these assumptions are patently unreasonable, then a
higher resolution may be needed.


In practice, statistical packages are used to compute specific
screening designs. We used the SAS/QC~\cite{sas} package in this work,
but many other packages, such as MINITAB and SPSS, are also
applicable.  these packages will produce a screening design, assuming
one can be found, given the following
application-specific information: (1) a list of options and their
settings, (2) a maximum run size, and (3) the design's resolution.

% Done: Adam, Atif, yikes, the term ``configuration model'' comes out of the
% blue here!  Can you please provide a smoother transition from the
% previous paragraph(s) to this one?
Since we already build our QA task model graphically using Skoll's MDE
tools (see Section~\ref{skolloverview}), we can just use a translator
to convert it into the list of options and settings expected by our
statistical package.  The second and third items are interwined and
must be chosen by developers.  In particular, higher resolution designs
will yield more accurate estimates (assuming some higher-level effects
exist), but require more observations.  It is also often advisable to
run more than the minimum number of observations needed for a given
resolution to improve precision or to deal with noisy
processes. Developers must balance these competing forces.

% Adam, Atif, this might be a good place to add a new \noindent {\bf
% ... } subheading so that it would be easier for readers to follow
% the structure of the subsection?!

\subsection{Computing a Screening Design}

To demonstrate these choices, consider a hypothetical software system
with 4 independent binary configuration options, $A$ through $D$, each
with binary settings \verb|+| and \verb|-|.  A full factorial design
for this system involves 16 ($2^4$) observations.  We assume that our
developers can only afford to gather 8 observations. With so few
observations, there is no design with clear $1^{st}$- and
$2^{nd}$-order effects.  Developers must therefore either allow more
observations or limit themselves to capturing only the 4
$1^{st}$-order effects, {\em i.e.}, the effect of each option by
itself.  We assume they choose to stay with a run size of 8 and to use
a resolution IV design.

Given these choices, the developers generate one acceptable design
using a statistical package. The design (which appears in
Table~\ref{options}) is identified uniquely as a $2^{4-1}_{IV}$
design, which means that the total number of options is 4, that they
will observe a $1/2$ ($2^{-1}=1/2$) fraction of the full factorial
design, and that the design is a resolution IV screening design. 
\begin{table}[tbhp]
\centering
  \begin{tabular}{cccc}
    \hline
    A & B & C & D \\
    \hline\hline
    - & - & - & - \\
    + & - & - & + \\
    - & + & - & + \\
    + & + & - & - \\
    - & - & + & + \\
    + & - & + & - \\
    - & + & + & - \\
    + & + & + & + \\
    \hline
\end{tabular}
\caption{$2^{4-1}_{IV}$ Design (Binary Option Settings are Encoded as (-) or (+))}
\label{options}
\end{table}
The design tool also outputs the aliasing structure $D=ABC$. We can
see this aliasing in Table~\ref{options} where the setting of option
$D$ is the product of the settings of options $A$, $B$ and $C$ (think
of \verb|+| as 1 and \verb|-| as $-$1).  This dependence explains why
the effect of option $D$ cannot be untangled from the interaction
effect of options $A$, $B$, and $C$.

\subsection{Executing and Analyzing Screening Designs}

After defining the screening design, developers will execute it across
the computing resources comprising the Skoll grid.  In our later
feasibility studies, each experimental observation involves measuring
a developer-supplied benchmark program while the system runs in a
particular configuration.  Our QA engineers use BGML to generate
workload and benchmark code.  Once the data is collected we analyze it
to calculate the effects.  Since our screening designs are balanced
and orthogonal by construction ({\it i.e.}, no bias in the observed
data), the effect calculations are simple.  For binary options (with
settings \verb|-| or \verb|+|), the effect of option $A$, $ME(A)$, is
%%%\vspace*{-0.1in}
\begin{align}
ME(A) = z(A-) - z(A+)
\label{effect1}
\end{align}
where $z(A-)$ and $z(A+)$ are the mean values of the observed data
over all runs where option $A$ is (\verb|-|) and where option $A$ is
(\verb|+|), respectively.
 
If required, $2^{nd}$-order effects can be calculated in a similar
way.  The interaction effect of options $A$ and $B$, $INT(A, B)$ is:
%%%\vspace*{-0.1in}
\begin{align}
INT(A, B) &= 1/2 \{ME(B|A+) - ME(B|A-)\} \\
&= 1/2 \{ME(A|B+) - ME(A|B-)\}
\label{effect2}
\end{align}
Here $ME(B|A+)$ is called the {\em conditional effect} of $B$ at the
\verb|+| level of $A$.  The effect of one factor ({\em e.g.}, $B$)
therefore depends on the level of the other factor ({\em e.g.}, $A$).
Similar equations exist for higher order effects and for designs with
non-binary options. See Wu and Hamada~\cite{wu} for further details.
 
Once the effects are computed, developers will want to determine which
of them are important and which are not.  There are several ways to
determine this, including using standard hypothesis testing.  We do
not use formal hypothesis tests primarily because they require strong
assumptions about the standard deviation of the experimental samples.
Instead, we display the effects graphically and let developers use
their expert judgment to decide which effects they consider
important. While this approach has some downsides (see
Section~\ref{conclusions}), even with traditional tests for
statistical significance, experimenters must still judge for
themselves whether a significant effect has any practical importance.

Our graphical analysis uses {\em half-normal probability plots}, which
show each option's effect a\-gainst their corresponding coordinates on
% Adam, why are the subscripts for these thetas outside of the bars. I
% am not familiar with the notation so I am just curious - andy
the half-normal probability scale.  If $|\theta|_{1} \le |\theta|_{2}
\le ... \le |\theta|_{I}$ are the ordered set of effect estimations,
the half-normal plot then consists of the points
%%%\vspace*{-0.15in}
\begin{align}
 (\Phi^{-1}(0.5 + 0.5[i-0.5]/I), |\theta|_{i})\;for\;i=1,...,I
\end{align}
where $\Phi$ is the cumulative distribution function of a standard
normal random variable.

The rationale behind half-normal plots is that unimportant options
will have effects whose distribution is normal and centered near 0.
Important effects will also be normally distributed, but with means
different from 0.\footnote{Since the effects are averages over
numerous observations, the central limit theorem guarantees
normality.}  Options whose effects deviate substantially from 0 should
therefore be considered important.  If no effects are important, the
resulting plot will show a set of points on an approximate line near
$y=0$.

\subsection{Conduction Supplementary Analysis}

At this point developers have a candidate set of important
options. One potential problem, however, is that we arrived at these
options by making the following assumptions:
  
\begin{enumerate}
\item The low-order effects identified as being important 
  really are; while the higher-order effects they are aliased to are
  not.

\item Monitoring only low-order effects is sufficient to produce
reliable estimates. 
\end{enumerate}

Since these are only assumptions, it is important to check them before
proceeding since the reliability of our results will be severely
compromised if they do not hold.  We therefore validate these
assumptions using two types of follow-up experiments:
\begin{enumerate}
\item We first examine additional configurations to disambiguate any
effects aliased to our purported low-level important options.

\item We then examine additional configurations to look for other
higher-order effects.
\end{enumerate}
In these follow-up experiments we rely on another class of efficient
experimental designs called {\it D-optimal designs}~\cite{d-optimal},
which are again computer-aided designs.  Given a configuration space
and a model the experimenter wishes to fit, a D-optimal design uses
search-based computer algorithms ({\it e.g.}, hill climbing or
simulated annealing) to select a set of configurations that satisfy a
particular optimality criterion.  Unlike more common fractional
factorial designs, therefore, the size of D-optimal designs need not
be a perfect fraction of full factorial designs.  D-optimal designs
are preferable to standard classical designs when (1) the standard
designs require more observations than can be tested with available
time and resources and (2) the configuration space is heavily
constrained ({\it i.e.,} when not all the configurations are valid).
Both factors are frequently present in modern software systems. Full
details of D-optimail designs are beyond the scope of this paper, but
can be found in books and articles (See Kolarik~\cite{kola} and
Mitchell~\cite{d-optimal}).

Based on the results of this D-optimal design analysis, developers may
modify the set of important options. At this point developers have a
working set of important options that they can use to create a
screening suite of configurations to benchmark whenever the system
changes.
