\subsection{Validating Basic Assumptions} 
\label{validate}

To compute the important options, we used a resolution IV screening
design, which according to the definition given in Section~\ref{mes},
means that (1) we aliased some $1^{st}$-order effects with some
$3^{rd}$-order or higher effects and some $2^{nd}$-order effects with
other $2^{nd}$-order or higher effects, and (2) we assume that
$3^{rd}$-order or higher effects are negligible.  If these assumptions
do not hold however performance estimations will be incorrect. Therefore,
at this stage we perform two further analyses to validate these assumptions.
  
In the remainder of this section we analyze the data from our
$2_{IV}^{14-7}$, 128-run experiment.  We did this experiment because
it was the only one where we identified five important options rather
than two.  The analysis presented in this section is readily
applicable to any screening experiment.

\subsubsection{Breaking Aliases}
\label{break_section}

In the $2_{IV}^{14-7}$, 128-run experiment, we identified options $B$
and $J$ as being clearly important and options $C$, $F$, and $I$ as
being arguably important (see Table ~\ref{options1} for the list of
options).  In that design, some $1^{st}$-order effects were aliased
with some $3^{rd}$-order or higher effects.  Table~\ref{aliases} shows
the aliasing structure for the important options up to $4^{th}$-order
effects.
\begin{table}[t]
\centering
\begin{tabular}{c}
\hline
Partial Aliasing Structure\\
\hline\hline
B = ACH = CGKM = CKLN = DGHL = DHMN = EFHK = HIJK = ADEI = ADFJ\\
J = EFI = ACIK = BHIK = CDFH = DEGM = DELN = FGKN = FKLM = ABDF\\
C = ABH = ADMN = AIJK = BGKM = BKLN = DEHI = DFHJ = AEFK = ADGL\\
F = EIJ = BEHK = CDHJ = DGIM = DILN = GJKN = JKLM = ABDJ = ACEK\\
I = EFJ = ACJK = BHJK = CDEH = DFGM = DFLN = EGKN = EKLM = ABDE\\
\hline
\end{tabular}
\caption{Partial Aliasing Structure for the Important Option in the
  $2_{IV}^{14-7}$, 128-run Design}
\label{aliases}
\end{table}
Note that the complete aliasing structure for the important options
contains a total of 640 aliases.  
%The complete list of aliases can be
%computed using the defining relation discussed in
%Section~\ref{sd-action}.
  
Consider the alias $B=ACH$ for the important option $B$; the effect of
option $B$ is aliased with the interaction effect of options $A$, $C$,
and $H$. Since the experimental analysis cannot distinguish $B$ from
$ACH$, there is an ambiguity whether $B$ or $ACH$ is really
important. If $ACH$, not $B$, is the important effect then our
performance estimations would obviously suffer, as would the rest of
the aliases.  Ambiguities involving aliased effects for the important
options should therefore be resolved to ensure the reliability of the
performance estimations.
 
To resolve the ambiguity in this experiment, we first formally modeled
the important effects and their 640 aliases by the following linear
model:
\begin{align}
\centering
\begin{array}{r l}
y & =  
\beta_0+\beta_{B}x_{B}+\beta_{J}x_{J}+\beta_{C}x_{C}+\beta_{F}x_{F}+\beta_{I}x_{I}\\
& +\beta_{ACH}x_{A}x_{C}x_{H}+\beta_{i}x_{i},\;\; \forall i \in S
- \{ACH\}
\label{bigmodel}
\end{array}
\end{align}
where $S$ is the set of all 640 aliased effects, $\beta_0$ is the
intercept term, $x_{B} = -1, 1$ according to the level of option B
(the definitions for the other $x$'s are similar), $\beta$'s are the
model coefficients, etc.  

Note that since the $1^{st}$-order effects other than $B$, $J$, $C$,
$F$, and $I$ are negligible (Section~\ref{step1}), we excluded them
from the model.  We then augmented our 128-run screening experiment
using the D-optimal design approach. This search-based technique
determined an appropriate design  which required benchmarking an
additional 2,328 configurations. We then collected the results and
analyzed them together with the results of the original screening
experiments.
 
Figure~\ref{breaking_aliases}(a) plots the Type III sum of squares for
the factorial effects.  In this figure, the effects are ordered in
descending order.  Due to space limitations, only the top 10 effects
are given.  The higher the sum of squares, the more important the
effects are.
\begin{figure*}[thpb]
\begin{tabular}{lll}
 
  \begin{minipage}[t]{0.46\textwidth}
    \centering
   \epsfig{file=figures/pareto_all.eps, scale=0.50}
   \centerline{(a)}
  \end{minipage}

&

  \begin{minipage}[t]{0.48\textwidth}
    \centering 
   \epsfig{file=figures/pareto_only3way.eps, scale=0.50}
   \centerline{(b)}
  \end{minipage}

\end{tabular} 
\caption{(a) Complete Dealiasing Experiment and (b) Up to and Including
  $3^{rd}$-order Effects Dealiasing Experiment.}
\label{breaking_aliases}
\end{figure*}
As can be seen from this figure, options $B$, $J$, $C$, $F$, and $I$
are important, while the higher-order interactions to which
they are aliased are not, {\em i.e.}, the low-order effect explains roughly 10
times the variance of its higher-order alias.  Further statistical
analysis also showed that these options are statistically significant
at 99.99\% confidence level or better.

Although this analysis confirmed our earlier results, it required
benchmarking an additional 2,000+ configuration, which in large-scale
systems might too expensive.  To further reduce costs, one might
forego a complete dealiasing of important options, dealiasing them up
to a certain level of order ({\it e.g.,} up to $3^{rd}$-order or
$4^{th}$-order effects), or dealiasing only suspected aliases based on
developer's domain knowledge.

To see how much savings partial dealising might yield, we repeated the
evaluation process, dealiasing the important options only up to and
including $3^{rd}$-order effects, which required only 64 additional
configurations.  As can be seen in Figure~\ref{breaking_aliases}(b),
in this particular example, we were able to reach the same conclusions
as the complete dealiasing experiment.  
\iffalse
In general, the cost reduction
techniques given above are not as reliable as the complete dealiasing
approach, so care must be taken in the analysis and interpretation of
these experiments.
\fi
 
\subsubsection{Checking for Higher-Order Effects}
\label{higher-order}

\begin{figure}[t]
\centering 
\epsfig{file=figures/pareto_all2n3way.eps, scale=0.50}
\caption{Looking for Higher-order Effects Upto and Including
  $3^{rd}$-order Effects.}
\label{higher_effect}
\end{figure}
 
As described earlier in this Section, our second assumption was that
monitoring only $1^{st}$-order effects was sufficient for our subject
frameworks.  Below, we investigate the validity of that assumption.
Without loss of generality, we will look for important effects up to
and including $3^{rd}$-order effects.  Developers can choose up to
which level to examine, keeping in mind that as the level increases,
the number of observations needed converges to exhaustive testing.

Just as in Section~\ref{break_section}, we augmented the
$2_{IV}^{14-7}$, 128-run experiment using the D-optimality criterion.
this time, however, our generalized linear model consisted of all the
$1^{st}$-, $2^{nd}$-, and $3^{rd}$-order effects.  This design
required only an additional 381 configurations.
Figure~\ref{higher_effect} shows the results of this study.  We
identified the top 6 effects: $B$, $J$, $F$, $I$, $BJ$, and $C$, as
statistically significant at 99.9\% confidence level or better.  Among
these important options we have only one interaction effect: $BJ$.
Since this interaction involves only options that are already
considered important by themselves, we conclude that monitoring only
first-order effects was sufficient for our subject frameworks.

The results presented above suggest that screening designs can detect
important options at a small fraction of the cost of exhaustive
testing and that techniques exist to economically check key
assumptions underlying the technique.  The smaller the effect,
however, the larger the run size needed to identify it.  Developers
should therefore be cautious when dealing with options that appear to
have an important, but relatively small effect, as they may actually
be seeing normal variation ($Scr_{32}$ and $Scr_{64}$ both have
examples of this).
 
% LocalWords:  px ip SAS Skoll optex glm ACH CGKM CKLN DGHL DHMN EFHK HIJK ADEI
% LocalWords:  ADFJ EFI ACIK BHIK CDFH DEGM DELN FGKN FKLM ABDF ABH ADMN AIJK
% LocalWords:  BGKM BKLN DEHI DFHJ AEFK ADGL EIJ BEHK CDHJ DGIM DILN GJKN JKLM
% LocalWords:  ABDJ ACEK EFJ ACJK BHJK CDEH DFGM DFLN EGKN EKLM ABDE dealiasing
% LocalWords:  dealiased lll BJ
