% $Id: mes_process.tex,v 1.22 2005/12/05 20:31:30 skoll 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.  To detect such performance problems,
developers often run benchmarking regression tests periodically.  As
described in Section~\ref{intro}, however, in-house QA efforts can be
confounded by the enormous configuration and control space of
large-scale software systems, where time and resource constraints (and
often high change frequencies) se\-verely limit the number of
configurations that can be examined using in-house resources.

For example, our earlier experience with Skoll to
ACE+\-TAO~\cite{Schmidt:04b} found that only a small number of default
configurations are benchmarked routinely by the core development team,
who thus have a limited view of their software's QoS.  QoS
degradations not readily seen in these default configurations can
easily escape detection until systems based on ACE+TAO are fielded by
end-users.  This section describes how we address this problem by
using the MDD-based Skoll environment (Section~\ref{skolloverview}) to
develop and implement a new hybrid DCQA process called {\em reliable
effects screening}.  We also describe the formal foundations of this
process, which is based on {\em design-of-experiments (DoE) theory},
and give an example that illustrates key aspects of our approach.

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

Reliable effects screening is a technique we developed to rapidly
detect performance degradation across a large configuration space as a
result of system changes.  Our approach relies on a class of
experimental designs called {\em screening designs}~\cite{wu}, which
are highly economical and can reveal important {\em low order effects}
(such as those due to individual option settings, or due to specific
option pairs or triples) that strongly affect performance.  We call
these most influential option settings the ``important options.''

At a high level, applying the reliable effects screening process in
the Skoll DCQA environment involves the following steps:
\begin{enumerate}
\item {\em Compute} a formal experimental design based on the system's
configuration model.
\item {\em Execute} that experimental design across {\bf fielded} computing
resources in the Skoll DCQA 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 important options.
\item Conduct {\em supplementary analysis} again on {\bf fielded}
computing resources to check the basic assumptions underlying Step 1
and to confirm the results of Step 3.
\item {\em Estimate} overall performance on {\bf in-house} computing
resources 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}

The assumption behind this hybrid DCQA process is that the important
options are the ones that substantially affect performance, while the
remaining options are effectively ``noise.''  Evaluating all
combinations of just the important option settings ({\em i.e.}, the
``screening suite'') and randomizing the rest should therefore provide
a reasonable estimate of performance across the entire configuration
space.  If our assumption is true, benchmarking only the screening
suite will provide much the same information as benchmarking the
entire configuration and control space.  It will require a fraction of
the time and effort, however, since the screening suite is much
smaller than the entire configuration and control space.

%%%\vspace*{-0.2in}
\subsection{Technical Foundations of Screening Designs}
%%%\vspace*{-0.2in}

For the reliable effects screening process to work we must first
identify the important options, {\em i.e.}, the subset of options
whose settings account for a large portion of performance variation
across the system's configuration space.  One obvious approach is to
test every configuration exhaustively.  Since exhaustive testing is
infeasible for large-scale, highly-configurable, performance-intensive
systems, however, developers often do some kind of random or {\em ad
hoc} sampling based on their knowledge of the software.  Since our
experience indicates that these approaches can be
unreliable~\cite{Schmidt:04b,Schmidt:04k}, we therefore need an
approach that samples the configuration and control space, yet
produces reasonably precise and reliable estimates of overall
performance.
 
The approach we chose for this paper uses formally-de\-signed
experiments, called {\em screening designs}, which are highly
economical and whose primary purpose is to identify 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).  For instance, for certain
web servers developed using ACE~\cite{Schmidt:99m}, a $1^{st}$-order
effect might be that performance slows considerably when logging is
turned on; another might be that it also slows when few server threads
are used in the web servers.  A $2^{nd}$ order effect involves the
interaction of two options, {\em e.g.}, web server performance may
slow down when caching is turned off {\it and} the server performs
blocking reads.

There are many ways to compute screening designs (see
Section~\ref{related}).  The one we use is based on traditional
factorial designs.  Consider a {\em full} factorial design involving
$k$ binary factors that exhaustively tests all combinations of the
factors.  The design's run size (number of experimental observations)
is therefore $2^k$.  Although this quickly becomes expensive, it does
allow one to compute all $1^{st}$- through $k^{th}$-order effects.

To reduce computational costs, statisticians have developed {\em
fractional} factorial designs~\cite{box}.  These designs use only a
carefully selected fraction (such as $1/2$ or $1/4$) of a full
factorial design.  Although fractional factorial designs are more
economical, they give up the ability to measure some higher-order
effects because the way observations are chosen aliases the effects of
some lower-order interactions with some higher-order ones, {\em i.e.},
it lumps together certain high- and low-order effects.  This
conflation is justified on the assumption that high-order effects are
negligible.

Screening designs push this trade-off to an extreme, {\em e.g.}, at
their smallest, screening designs require only as many observations as
the number of effects one wishes to calculate ({\em i.e.}, $k$
observations to compute $k$, $1^{st}$-order effects).  Of course,
experimenters often want more than the minimum number of observations
to improve precision or to deal with noisy processes.  As before, this
is only possible because the design aliases some low-order with some
high-order effects.

While this aliasing strategy and its underlying assumptions may seem
problematic, screening designs have been used extensively to
understand and improve products and processes developed in
manufacturing, engineering, and physical sciences~\cite{wu}.  Their
success stems largely from the ability to use them in an iterative,
``quick and dirty'' fashion, {\em i.e.}, to focus on major problem
sources, a few at a time, rather than trying to understand and fix all
problems simultaneously.  Since our objective with reliable effects
screening is also to produce a rough -- but reliable -- estimate of
overall performance (rather than an extremely precise measurement), we
conjecture that screening designs provide an adequate foundation for
our hybrid model-based DCQA processes.  Moreover, our process includes
steps to check these underlying assumptions during process execution.

%%%\vspace*{-0.2in}
\subsection{Screening Designs in Action}
\label{sd-action}
%%%\vspace*{-0.2in}

To show how screening designs are computed, we now present a
hypothetical example of a software system with 4 binary configuration
options, $A$ through $D$, each with binary settings \verb|+| and
\verb|-| and with no inter-option constraints.  Techniques exist to
handle both non-binary options and inter-option constraints, but for
this example we restrict ourselves to this simple case.  To compute a
specific screening design, developers must (1) decide how many
observations they can afford, (2) determine which effects they want to
analyze, and (3) select an aliasing strategy consistent with these
constraints.  In practice, screening designs are usually computed by
automated tools found in many statistical software
packages~\cite{sas}.

The configuration and control space for our sample system has
$2^{4}=16$ configurations.  The corresponding full factorial design
therefore involves 16 observations.  Each observation can require
discovering an appropriate and available hardware platform,
downloading a large code base, configuring and compiling the code
base, and executing the system for some period of time.  The total QA
costs can therefore be excessive, particularly when they are limited
to in-house testing resources.

For this example, we assume that our developers can afford to gather
only 8 observations, so the full factorial design would therefore be
unacceptable.  We also assume that our developers are mostly
interested in capturing the 4 $1^{st}$-order effects ({\em i.e.}, the
effect of each option by itself.)  Given this goal, the developers
decide to execute a screening design.
 
The first step in computing the screening design is to create a
$2^{3}$ full factorial design over 3 (arbitrarily selected) options,
in this case $A$, $B$, and $C$.  This design is shown in
Table~\ref{options}(a) with the binary option settings encoded as
(\verb|-|) or (\verb|+|).
\begin{table}[tbhp]
\centering
\begin{tabular}{cc}
\begin{minipage}[c]{0.20\textwidth}
  \centering
  \begin{tabular}{ccc}
\hline
    A & B & C \\
\hline\hline
    - & - & - \\
    + & - & - \\
    - & + & - \\
    + & + & - \\
    - & - & + \\
    + & - & + \\
    - & + & + \\
    + & + & + \\
\hline
  \end{tabular}
  \centerline{(a)}
\end{minipage}

&

\begin{minipage}[c]{0.20\textwidth}
  \centering
  \begin{tabular}{cccc}
    \hline
    A & B & C & D \\
    \hline\hline
    - & - & - & - \\
    + & - & - & + \\
    - & + & - & + \\
    + & + & - & - \\
    - & - & + & + \\
    + & - & + & - \\
    - & + & + & - \\
    + & + & + & + \\
    \hline
  \end{tabular}
  \centerline{(b)}
\end{minipage}
 
 
\end{tabular}
\caption{(a) $2^{3}$ design and (b) $2^{4-1}_{IV}$ design}
\label{options}
\end{table}
In practice, QA engineers use tools, such as our OCML DSML, to
generate the configurations in the appropriate format required by the
system under test.  We use this design as the starting point because
$2^{3} = 8$ is the maximum number of observations the developers can
afford to run.  Although this initial design is fine for 3 options it
cannot handle our developer's 4-option system because no settings have
been assigned to option $D$.  Since the developers have already
decided that a full factorial design is too expensive, they need a way
to ``stretch'' the current 3-option design to cover the 4$^{th}$
option, without biasing the data analysis.
 
Screening designs accomplish this ``stretching'' by leveraging the
following observations.  An experiment with $k$ observations provides
$k-1$ degrees of freedom.  When we analyze the experiment, we use up 1
degree of freedom for each effect we calculate.  Our current example
design thus has $2^{3} - 1 = 7$ degrees of freedom.  We will use up
$3$ degrees of freedom to estimate the $1^{st}$-order effects of $A$,
$B$, and $C$.  The remaining degrees of freedom would normally be used
to estimate the 3, $2^{nd}$-order and 1, $3^{rd}$-order effects.  In
this case, however, since we are only interested in the $1^{st}$ order
effects, screening designs instead are free to use the extra degrees
of freedom to estimate the effect of option $D$, {\em i.e.}, we can
(carefully, of course) add settings for option $D$ and still being
able to estimate the effect of option $D$, without going to a $2^4$
full factorial design.

As mentioned earlier, the settings for option $D$ are chosen in such a
way that some effects are aliased with others.  Since the aliasing
process confounds/\-loses some information, the developers must
specify which effects can be aliased safely by choosing a desired {\em
resolution} for the screening design.  In resolution $R$ designs, no
effects involving $i$ factors are aliased with effects involving less
than $R-i$ factors.  Since our developers are only interested in
computing $1^{st}$-order effects, they choose a resolution IV design
where $1^{st}$-order effects will be aliased with $3^{rd}$-order or
higher effects and $2^{nd}$-order effects will be aliased with
$2^{nd}$-order or higher effects. Our developers, therefore, assume
that $3^{rd}$-order or higher effects are negligible and that they are
not interested in computing the $2^{nd}$-order effects.  If the
developers are unwilling to make these assumptions, then screening
designs may be inappropriate for them (or they may need to use the
screening designs in an iterative, exploratory fashion).

The final step in the process is to compute the specific values of
option $D$ consistent with the developers desire for a resolution IV
design.  To perform this computation a function called a {\em design
generator} must be determined to compute the setting of option $D$
based on the values of options $A$, $B$, and $C$.  In our hypothetical
example, automated tools chose $D=ABC$ as the design generator, which
means that for each observation, $D$'s setting is computed by
multiplying the settings for options $A$, $B$, and $C$ (think of
\verb|+| as 1 and \verb|-| as $-$1).  In general, there is no
closed-form solution for choosing a design generator and in some
situations none may exist.  For this paper we identified design
generators using the {\tt factex} function of the SAS/QC
package~\cite{sas}.  This search-based function examines numerous
possible design generators until an acceptable one is found (or until
the algorithm gives up if none can be found).
  
Table~\ref{options}(b) gives the final design, which is identified
uniquely as a $2^{4-1}_{IV}$ design with the design generator $D=ABC$.
The $2^{4-1}_{IV}$ designation means that the total number of options
is 4, that we will examine a $1/2$ ($2^{-1}=1/2$) fraction of the full
factorial design, and that the design is a resolution IV screening
design.

Design generators introduce aliases to the design.  For example, our
design generator $D=ABC$ aliases the effect of option $D$ with the
interaction effect of options $A$, $B$, and $C$.  The estimate of
option $D$'s effect thus includes the influence of $3^{rd}$-order
effect $ABC$, {\em i.e.}, at the end of the experiment, the collected
data cannot distinguish the effect of $D$ from the effect of $ABC$.
Note that $D=ABC$ is not the only valid aliasing structure for our
example design, it is just one of many that meet the design
requirements stated previously.
    
The aliasing relation of this design can also denoted by ${\bf
I}=ABCD$, which is called the {\it defining relation}.  ${\bf I}$
denotes the column of all \verb|+|'s ({\it i.e.,} the product of the
column $A$, $B$, $C$, and $D$ is all \verb|+|'s).  The aliases in a
design can be revealed by multiplying the effects by the defining
relation.

For example, in our resolution IV design, to find the alias for option
$A$, we multiply both sides of ${\bf I}=ABCD$ by $A$, {\em i.e.},
$A{\bf I}=AABCD$.  Since the product of column $A$ and ${\bf I}$
yields column $A$ itself ({\it i.e.,} \verb|-+|=\verb|-| and
\verb|++|=\verb|+|) and the product of the column $A$ by itself ($AA$)
gives ${\bf I}$ ({\it i.e.,} \verb|--|=\verb|+| and
\verb|++|=\verb|+|), we find out that the effect of option $A$ is
aliased with the interaction effect of option $B$, $C$, and $D$
($A=BCD$).  By following the same procedure, we can find all the
aliases for the $1^{st}$-order effects that are $A=BCD$, $B= ACD$,
$C=ABD$, and $D=ABC$.  Note that although all the $1^{st}$-order
effects are aliased, they are all aliased with $3^{rd}$-order effects,
which is consistent both with the assumption that $3^{rd}$-order
effects are negligible and with the definition of resolution IV
designs.  Understanding the aliasing patterns of our particular
screening design will later allow us to check whether the aliased
high-order effects are in fact negligible.
 
After defining the screening design, developers can execute it across
the Skoll grid.  For our purposes, each observation involves measuring
a developer-supplied benchmarking regression test while the system
runs in a particular configuration.  
%
% arvind: BGML MDD use.
QA engineers use benchmark generators such as our BGML DSML to generate
workload and benchmark code.
Once the data is collected we
analyze it to calculate the effects.  Since fractional factorial
designs are balanced and orthogonal designs ({\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.
 
Once the effects are computed, developers will want to determine which
of these effects are important and which are not.  There are several
ways to determine this, including using standard hypothesis testing.
This paper does 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.
  
% LocalWords:  perfor mance inten sive BGML Skoll DCQA QoS middleware's Burman
% LocalWords:  Plackett arvindk se verely middleware design's tradeoff factex
% LocalWords:  SAS cyilmaz de ly ccc cccc ABCD AABCD ACD ABD
