% $Id: experiments_new.tex,v 1.33 2006/07/16 22:03:43 atif Exp $
\section{Feasibility Study}
%%%\vspace*{-0.2in}
\label{experiment}
  
This section describes a feasibility study that assesses the
implementation cost and the effectiveness of the reliable effects
screening process described in Section~\ref{mes} on a suite of large,
performance-intensive software frameworks.

%%%\vspace*{-0.15in}
\subsection{Experimental Design}
\label{design}
%%%\vspace*{-0.15in}

\noindent{\bf Hypotheses.}  Our feasibility study explores the
following three hypotheses: 
\begin{enumerate}
\item Our MDE-based Skoll environment cost-effectively supports the
definition, implementation, and execution of our reliable effects
screening process described in Section~\ref{mes}.
\item The screening designs used in the reliable effects screening
correctly identifies a small subset of options whose effect on
performance is important.
\item Exhaustively examining just the options identified by the
screening design gives performance data that (a) is representative of
the system's performance across the entire configuration space, but
less costly to obtain and (b) is more representative than a
similarly-sized random sample.
\end{enumerate} 

%%%\vspace*{-0.15in}
\noindent{\bf Subject applications.}  The experimental subject
applications for this study were based on three open-source software
frameworks for performance-intensive systems: ACE v5.4 + TAO v1.4 +
CIAO v0.4, which can be downloaded via \url{www.dre.vanderbilt.edu}.
ACE provides reusable C++ wrapper facades and framework components
that implements core concurrency and distribution
patterns~\cite{Schmidt:00a} for distributed real-time and embedded
(DRE) systems.  TAO is a highly configurable Real-time CORBA Object
Request Broker (ORB) built atop ACE to meet the demanding QoS
requirements of DRE systems.  CIAO extends TAO to support components,
which enables developers to declaratively provision QoS policies
end-to-end when assembling DRE systems.

ACE+\-TAO+\-CIAO are ideal subjects for our feasibility study since
they share many characteristics with other highly configurable
performance-intensive systems.  For example, they collectively have
over 2M+ lines of source code, functional regression tests, and
performance benchmarks contained in $\sim$4,500 files that average
over 300 CVS commits per week by dozens of developers around the
world.  They also run on a wide range of OS platforms, including all
variants of Windows, most versions of UNIX, and many real-time
operating systems, such as LynxOS and VxWorks.

\noindent{\bf Application scenario.}  Due to recent changes made to
the ACE message queuing strategy, the developers of ACE+\-TAO+\-CIAO
were concerned with measuring two performance criteria: (1) the
latency for each request and (2) total message throughput
(events\-/second) between the ACE+\-TAO+\-CIAO client and server.  For
this version of ACE+\-TAO+\-CIAO, the developers identified 14 binary
run-time options they felt affected latency and throughput.  The
entire configuration space therefore has $2^{14}=16,384$ different
configurations.  To save space, we refer to these options by their one
letter indices, A-N (see Table~\ref{options1} for more details on the
mapping of letters to options).

\begin{table}[ht]
\centering
\caption{Some ACE+TAO Options}
%%%\resizebox{!}{0.89in}
{\begin{tabular}{clcl} \hline {\bf Option Index} & { \bf Option Name} &
{ \bf Option Settings} & {\bf Option Description}\\
%{\bf Index} & { \bf Name} & { \bf Settings} \\
\hline\hline
{ A} & {ReactorThreadQueue} & {\{FIFO, LIFO\}} & {Order in which incoming requests} \\
      &                     &                  & {are processed in the ORB Reactor}\\
{ B} & {ClientConnectionHandler} & {\{RW, MT\}} & {Client side connection handler}  \\
{ C} & {ReactorMaskSignals} & {\{0, 1\}} & {Enable/disable signals } \\
     &                      &            & {during request processing}\\
{ D} & {ConnectionPurgingStrategy} & {\{LRU, LFU\}} & {ORB connection purging strategy}\\
{ E} & {ConnectionCachePurgePercent} & {\{10, 40\}} & {\% of the ORB connection cache purged}\\
{ F} & {ConnectionCacheLock} & {\{thread, null\}} & {Enable/disable locking of}\\
     &                       &                    & {the ORB connection cache}\\

{ G} & {CorbaObjectLock} & {\{thread, null\}} & {Enable/disable locking while}\\
     &                   &                    & {synchronizing object state}\\

{ H} & {ObjectKeyTableLock} & {\{thread, null\}} & {Type of lock to be used }\\
     &                      &                    & {within ORB for retrieving}\\
     &                      &                    & {object keys} \\

{ I} & {InputCDRAllocator} & {\{thread, null\}} & {Enable/disble locking during}\\
     &                     &                    & {creating CDR streams}\\ 

{ J} & {Concurrency} & {\{reactive,} & {ORB concurrency}\\
     &               & {thread-per-connect\}} & {reactive or thread per connection}\\
{ K} & {ActiveObjectMapSize} & {\{32, 128\}} & {Map size for holding objects}\\

{ L} & {UseridPolicyDemuxStrategy} & {\{linear, dynamic\}} & {Demultiplexing strategy} \\
     &                             &                       & {when user-id policy is used}\\

{ M} & {SystemPolicyDemuxStrategy} & {\{linear, dynamic\}} & {Demultiplexing strategy} \\
    &                              &                       & {when system id policy is used}\\

{ N} & {UniquePolicyRevDemuxStrategy} & {\{linear, dynamic\}} & {Specify the 
reverse demultiplexing} \\
     &                                &                       & {lookup strategy to be} \\
     &                                &                       & {used with the unique id policy}\\

\hline
\end{tabular}}
%%%\vspace{-0.25in}
%%%\vspace{-0.25in}
\label{options1}
\end{table}

\noindent{\bf Using MDE tools to model experiment scenario.}  To ease
experiment creation and generation, we used the Skoll MDE tools to
compose the experiment visually.  In particular, we used BGML to
generate the platform-specific benchmarking code needed to evaluate
the QoS of the ACE+\-TAO+\-CIAO software framework configurations.
Figure~\ref{fig:bgmluse} shows how we used BGML to model the
benchmark.
\begin{figure}[hptb]
\centerline{\epsfxsize=9cm
\epsffile{figures/BGML-Task-Specification.eps}}
\caption{Using BGML to Generate Benchmarking Code}
\label{fig:bgmluse}
\end{figure}
For the experiment, we modeled the operation exchanged between the
client and server using BGML's operation element.  We then associated
this element with BGML's latency metric to compute the end-to-end
measurements for our experiments.  The number of warm up iterations
and the data type exchanged between client and server were all set as
attributes to the operation and latency elements provided by BGML.  As
shown in the figure, BGML code generators generated the benchmarking
code to measure and capture the latency for our experiment.

Another step in designing our experiment involved modeling the
ACE+\-TAO+\-CIAO framework configurations.  We used the OCML MDE tool
to ensure that the configuration were both syntactically and
semantically valid, as shown in Figure~\ref{fig:ocmluse}.
\begin{figure}[h]
\centerline{\epsfxsize=8cm
\epsffile{figures/OCML-Experiment-Config.eps}}
\caption{Using OCML to Capture Experiment Configuration}
\label{fig:ocmluse}
\end{figure}
As shown in the figure, OCML was used to enter the ACE+TAO+CIAO
configurations we wanted to measure.  OCML's constraint checker first
validated the configurations we modeled, while the code generator
produced the framework configuration files. 

%%%\vspace*{-0.15in}
\noindent{\bf Experimental process.}  Our experimental process used
Skoll's MDE tools to implement the reliable effects screening process
and evaluate our three hypotheses above.  We executed the reliable
effects screening process across a prototype Skoll grid of dual
processor Xeon machines running Red Hat 2.4.21 with 1GB of memory in
the real-time scheduling class.  The experimental tasks involved
running a benchmark application in a particular system configuration,
which evaluated performance for the application scenario outlined
above. The benchmark created an ACE+\-TAO+\-CIAO client and server and
then measured message latency and overall throughput between the
client and the server.

In our experiment, the client sent 300K requests to the server.  After
each request the client waited for a response from the server and
recorded the latency measure in microseconds.  At the end of 300K
requests, the client computed the throughput in terms of number of
requests served per second.  We then analyzed the resulting data to
evaluate our hypotheses.  Section~\ref{conclusions} describes the
limitations with our current experimental process.

\subsection{The Full Data Set}

To provide a baseline for evaluating our approach, we first generated
and analyzed performance data for all 16,000+ valid configurations of
ACE+\-TAO+\-CIAO.\footnote{We would not do this step in practice since
it required about two days of CPU time, which would be prohibitively
expensive in most production software development environments with
scores of such experiments running daily.}  We refer to these
configurations as the ``full suite'' and the performance data as the
``full data set.''

We examined the effect of each option and judged whether they had
important effects on performance. Figure~\ref{full_hp} plots the
effect of each of the 14 ACE+\-TAO+\-CIAO options on latency and
throughput across the full data set. We see that options $B$ and $J$
are clearly important, whereas options $I$, $C$, and $F$ are arguably
important.  The remaining options are not important.
\begin{figure}[htpb]
%\begin{center}
\begin{tabular}{ll}
  \begin{minipage}[t]{0.5\textwidth}
    \centering
\epsfig{file=figures/effects/full_latency_1.eps, scale=0.40}
  \end{minipage}
&
  \begin{minipage}[t]{0.5\textwidth}
    \centering
\epsfig{file=figures/effects/full_throughput_1.eps, scale=0.40}
  \end{minipage}
\end{tabular}
\caption{Option Effects Based on Full Data}
\label{full_hp}
\end{figure}

%%%\vspace*{-0.15in}
\subsection{Evaluating Screening Designs}
%%%\vspace*{-0.15in}
\label{step1}

We now walk through the steps involved in conducting the reliable
effects screening process, to see whether the remotely executed
screening designs can correctly identify the same important options
discovered in the full data set.

To perform these steps, we calculated and executed several different
resolution IV screening designs of differing run sizes. The
specifications for these designs appear in the Appendix.  The first
set of designs examined all 14 options using increasingly larger run
sizes (32, 64, or 128 observations) to identify only important
$1^{st}$-order effects.  We refer to these screening designs as
$Scr_{32}$, $Scr_{64}$ and $Scr_{128}$, respectively.  We also
calculated and executed a second set of designs that attempted to
capture important $1^{st}$- and $2^{nd}$-order effects.

\begin{figure*}[t]
\begin{tabular}{lll}
 
  \begin{minipage}[t]{0.29\textwidth}
    \centering
   \epsfig{file=figures/effects/screenIV32_latency_1.eps, scale=0.35}
  \end{minipage}

&

  \begin{minipage}[t]{0.29\textwidth}
    \centering
   \epsfig{file=figures/effects/screenIV64_latency_1.eps, scale=0.35}
  \end{minipage}

&

  \begin{minipage}[t]{0.29\textwidth}
    \centering
   \epsfig{file=figures/effects/screenIV128_latency_1.eps, scale=0.35}
  \end{minipage}

\end{tabular}
\caption{Option Effects Based on Screening Designs}
\label{s32}
\end{figure*}

Figure~\ref{s32} shows the half-normal probability plots obtained from
our first set of screening designs.  The figures show that all
screening designs correctly identify options $B$ and $J$ as being
important.  $Scr_{128}$ also identifies the possibly important effect
of options $C$, $I$, and $F$.  Due to space considerations in the
paper we only present data on latency (throughput analysis showed
identical results unless otherwise stated).

\begin{figure}[ht]
\begin{center}
\begin{tabular}{c}
   \epsfig{file=figures/effects/full_latency_2.eps, scale=0.40}
%%%\vspace*{-0.2in} 
\\
%   \centerline{(a)}
   \epsfig{file=figures/effects/screenVI2048_latency_2.eps, scale=0.40}
%   \centerline{(b)}
\end{tabular}
\end{center}
%%%\vspace*{-0.25in}
\caption{Pairwise Effects Based on Full and Screening Suite}
\label{cmp32}
%%%\vspace*{-0.25in}
\end{figure}

\subsection{Higher-Order Effects}
\label{extensions}
 
The Resolution IV design only calculates clear $1^{st}$-order effects,
which appears to work well for our subject application and scenario,
but might not be sufficient for other situations.  Figure~\ref{cmp32}
shows the effects of all pairs of options based on the full data set
and the same effects captured via a Resolution VI screening design
using 2,048 observations.  From the figure we see several things: (1)
the screening design correctly identifies the 5 most important
pairwise interactions at $1/8^{th}$ the cost of exhaustive testing and
(2) the most important interaction effects involve only options that
are already considered important by themselves, which supports the
belief that monitoring only first-order effects will be sufficient for
our subject frameworks.

\input{validation}

%%% has problems with footnote getting crunched.
%%%\vspace*{-0.15in}
\subsection{Estimating Performance with Screening Suites}
%%%\vspace*{-0.15in}
\label{step2}

Our experiments thus far have identified a small set of important
options.  We now evaluate whether benchmarking all combinations of
these most important options can be used to estimate performance
quickly across the entire configuration space we are studying.  The
estimates are generated by examining all combinations of the most
important options, while randomizing the settings of the unimportant
options.

In the Section~\ref{step1}, we determined that options $B$ and $J$
were clearly important and that options $C$, $I$, and $F$ were
arguably important.  Developers therefore made the estimates based on
benchmarking either 4 (all combinations of options $B$ and $J$) or 32
(all combinations of options $B$, $J$, $C$, $I$, and $F$)
configurations.  We refer to the set of 4 configurations as the
``top-2 screening suite'' and the set of 32 configurations as the
``top-5 screening suite.''

Figure~\ref{qq} shows the distributions of latency for the full suite
vs. the top-5 screening suite and for the full suite vs. the top-2
screening suite.
\begin{figure*}[thpb]
\begin{center}
\begin{tabular}{cc}
   \epsfig{file=figures/effects/qq_4cmp.eps, scale=0.40}
%%%\vspace*{-0.2in} 
&
%   \centerline{(a)}
   \epsfig{file=figures/effects/qq_32cmp.eps, scale=0.40}
%   \centerline{(b)}
\end{tabular}
\end{center}
%%%\vspace*{-0.25in}
\caption{Q-Q plots for the Top-2 and Top-5 Screening Suites}
%%%\vspace*{-0.25in} 
\label{qq}
\end{figure*}
The distributions of the top-5 and top-2 screening suites closely
track the overall performance data.  Such plots, called
quantile-quantile (Q-Q) plots, are used to see how well two data
distributions correlate by plotting the quantiles of the first data
set against the quantiles of the second data set.  If the two sets
share the same distribution, the points should fall approximately on
the $x=y$ line.

We also performed Mann-Whitney non-parametric
tests~\cite{BHH:Statistics} to determine whether each set of screening
data (top-2 and top-5 suites) appears to come from the same
distribution as the full data.  In both cases we were unable to reject
the null hypothesis that the top-2 and top-5 screening suite data come
from the same distribution as the full suite data.  These results
suggest that the screening suites computed at Step 4 of the reliable
effects screening process (Section~\ref{mes}) can be used to estimate
overall performance in-house at extremely low time/effort, {\em i.e.},
running 4 benchmarks takes 40 seconds, running 32 takes 5 minutes,
running 16,000+ takes two days of CPU time.

%%%\vspace*{-0.15in}
\subsection{Screening Suites vs. Random Sampling}
\label{random}
%%%\vspace*{-0.15in}

Another question we addressed is whether our reliable effects
screening process was better than other low-cost estimation processes.
In particular, we compared the latency distributions of several random
samples of 4 configurations to that of the top-2 screening suite found
by our process.  The results of this test are summarized in
Figure~\ref{cmp4}.
\begin{figure}[thbp]
\centering
	  \epsfig{file=figures/effects/lavg_r_vs_s_4.eps, scale=0.45}
%%%	   \vspace*{-0.15in}
\caption{Latency Distribution from Full, Top-2, and Random Suites}
%%%\vspace*{-0.25in}
\label {cmp4}
\end{figure}
These box plots show the distributions of latency metric obtained from
exhaustive testing, top-2 screening suite testing, and random testing.
These graphs suggest the obvious weakness of random sampling, {\em
i.e.}, while sampling distributions tend toward the overall
distribution as the sample size grows, individual small samples may
show wildly different distributions.

%%%\vspace*{-0.15in}
\subsection{Dealing with Evolving Systems}
\label{inpractice}
%%%\vspace*{-0.15in}

The primary goal of reliable effects screening is to detect
performance degradations in evolving systems {\em quickly}.  So far,
we have not addressed whether -- or for how long -- screening suites
remain useful as a system evolves.  To better understand this issue,
we measured latency on the top-2 screening suite, once a day, using
CVS snapshots of ACE+\-TAO+\-CIAO.  We used historical snapshots for
two reasons: (1) the versions are from the time period for which we
already calculated the effects and (2) developer testing and
in-the-field usage data have already been collected and analyzed for
this time period (see \url{www.dre.vanderbilt.edu/Stats}), allowing us
to assess the system's performance without having to test all
configurations for each system change exhaustively.

Figure~\ref{evolve} depicts the data distributions for the top-2
screening suites broken down by date (higher latency measures are
worse).
\begin{figure}[tbhp]
\centering
	  \epsfig{file=figures/effects/latency_screening.eps, scale=0.45}
%%%	   \vspace*{-0.15in}
\caption{Performance Estimates Across Time}
%%%\vspace*{-0.25in}
	\label{evolve}
\end{figure}
We see that the distributions were stable the first two days, crept up
somewhat for days 3 through 5, and then shot up the $6^{th}$ day
(12/14/03). They were brought back under control for several more
days, but then moved up again on the last day.  Developer records and
problem reports indicate that problems were not noticed until
12/14/03.

Another interesting finding was that the limited in-house testing
conducted by the ACE+\-TAO+\-CIAO developers measured a performance
drop of only around 5\% on 12/14/03. In contrast, our screening
process showed a much more dramatic drop -- closer to 50\%. Further
analysis by ACE+\-TAO+\-CIAO developers showed that their unsystematic
testing failed to evaluate configurations where the degradation was
much more pronounced.

Taken together, our results suggest that benchmarking only all
combinations of the important options identified in steps 1--4 of the
reliable effects screning process gives much the same information as
benchmarking the entire configuration space, but at a substantially
reduced cost.

% LocalWords:  DCQA Skoll QoS middleware ORBReactorThreadQueue RW LRU LFU CCM
% LocalWords:  ORBClientConnectionHandler ORBReactorMaskSignals ORBConcurrency
% LocalWords:  ORBConnectionPurgingStrategy ORBConnectionCachePurgePercentage
% LocalWords:  ORBConnectionCacheLock ORBCorbaObjectLock ORBObjectKeyTableLock
% LocalWords:  ORBInputCDRAllocator ORBActiveObjectMapSize CORBA ClassiX LynxOS
% LocalWords:  ORBUseridPolicyDemuxStrategy ORBSystemidPolicyDemuxStrategy Xeon
% LocalWords:  ORBUniqueidPolicyReverseDemuxStrategy VxWorks ABD ACD BCE BDE
% LocalWords:  ANOVA TODO ACDE ABF ACDF ACEF ADEF ABDE ABDF ACDG ABEFG BCDEFG
  
% LocalWords:  aporter ReactorThreadQueue ClientConnectionHandler lll CVS Scr
% LocalWords:  ReactorMaskSignals ConnectionPurgingStrategy ConnectionCacheLock
% LocalWords:  ConnectionCachePurgePercent CorbaObjectLock ObjectKeyTableLock
% LocalWords:  InputCDRAllocator ActiveObjectMapSize UseridPolicyDemuxStrategy
% LocalWords:  SystemPolicyDemuxStrategy UnqPolicyRevDemuxStrategy Skoll's
% LocalWords:  gainst analyses
