% $Id: challenges.tex,v 1.5 2005/11/14 12:11:30 atif Exp $

\section {Addressing QA Challenges for Perfo\-rmance-inte\-nsive
Softwa\-re Systems} 
\label{challenges}

This section describes key QA challenges faced by developers of
performance-intensive software and describes how DCQA environments and
model-based software development techniques can help to resolve these
challenges.

\subsection{Challenge 1: Configuration Space Explosion in
Performance-intensive Software Sy\-stems}

\paragraph* {\bf Context}
Performance-inten\-sive software often provide fine-grai\-ned knobs to
tune QoS behavior so it can be optimized for particular run-time
contexts and application requirements.  For example, high-performance
web servers ({\em e.g.}, Apache), object request brokers ({\em e.g.},
TAO), and databases ({\em e.g.}, Oracle) have hundreds of options and
configuration parameters.  General-purpose, one-size-fits-all
solutions often have unacceptable QoS for performance-intensive
software systems.

\sqzpar\paragraph* {\bf Problem}
To support customizations demanded by users,
per\-for\-mance-inten\-sive software must run on many hardware and OS
platforms and typically have many options to configure the system at
compile- and/or run-time.  Highly configurable performance-intensive
software can therefore yield an explosion of the {\em software
configuration space}.  While the flexibility of many options and
configuration parameters promotes customization, it also creates many
potential system configurations, each of which deserves extensive QA.
As software configuration spaces increase in size and software
development resources decrease, it becomes infeasible to handle all QA
activities in-house since developers often lack all the hardware, OS,
and compiler platforms on which their reusable software artifacts will
run.

\sqzpar\paragraph* {\bf Solution approach $\rightarrow$ the Skoll DCQA
environment} To address the QA challenges caused by the explosion of
the software configuration space and the limitations of in-house QA
processes, we have developed the {\bf Skoll} environment to prototype
and evaluate tools necessary to perform ``around-the-world,
around-the-clock'' DCQA processes.  Our feedback-driven Skoll
environment includes languages for modeling system configurations and
their constraints, algorithms for scheduling and remotely executing
tasks, and analysis techniques for characterizing faults.  Skoll
divides QA processes into multiple subtasks that are intelligently and
continuously distributed to, and executed by, a grid of computing
resources contributed by end-users and distributed development teams
around the world.  The results of these executions are returned to
central collection sites where they are fused together to identify
defects and guide subsequent iterations of the DCQA process.

To support DCQA processes we have developed the following components
and services for use by Skoll QA process designers (a comprehensive
discussion appears in~\cite{Schmidt:04b}):

{$\bullet$\bf Configuration space model.} The cornerstone of Skoll is
its formal model of a QA process' configuration space, which captures
all valid configurations for QA subtasks.  This information is used in
planning the global QA process, for adapting the process dynamically,
and aiding in analyzing and interpreting results.

{$\bullet$\bf Intelligent Steering Agent.} A novel feature of Skoll is
its use of an {\em Intelligent Steering Agent} (ISA) to control the
global QA process by deciding which valid configuration to allocate to
each incoming Skoll client request.  For example, given the current
state of the global process including the results of previous QA
subtasks ({\em e.g.}, which configurations are known to have failed
tests), the configuration model, and metaheuristics ({\em e.g.},
nearest neighbor searching), the ISA will choose the next
configuration such that process goals ({\em e.g.}, evaluating
configurations in proportion to known usage distributions) will be
met.  After a valid configuration is chosen, the ISA packages the
corresponding QA subtask implementation into a {\em job
configuration}, which consists of the code artifacts, configuration
parameters, build instructions, and QA-specific code ({\em e.g.},
regression/\-performance tests) associated with a software project.

{$\bullet$\bf Adaptation strategies.} As QA subtasks are performed by
clients in the Skoll grid, their results are returned to the ISA,
which can learn from the incoming results. For example, when some
configurations prove to be faulty, the ISA can refocus resources on
other unexplored parts of the configuration space.  To support such
dynamic behavior, Skoll QA process designers can develop customized
{\it adaptation strategies} that monitor the global QA process state,
analyze it, and use the information to modify future subtask
assignments in ways that improve process performance.

\begin{figure}[hbpt]
\centering
\epsfig{file=figures/process_view.eps, height=3in, width=2in}
\bfcaption{An Example Skoll DCQA Process}
\label{processview}
\end{figure}
Skoll uses the components described above to perform DCQA processes as
shown in Figure~\ref{processview} and described below.

\noindent {\bf 1.} Developers create the configuration model and
adaptation strategies.  The ISA automatically translates the model
into planning operators.  Developers create the generic QA subtask
code that will be specialized when creating actual job configurations.

\noindent {\bf 2.} A {\em user} requests Skoll client software via a 
web-based registration process. The user receives the Skoll client
software and a configuration template.  If a user wants to change
certain configuration settings or constrain specific options he/she
can do so by modifying the configuration template.

\noindent {\bf 3.} A Skoll client periodically (or on-demand)
requests a job configuration from a Skoll server.

\noindent {\bf 4.}  The Skoll server queries its databases and the
user-provided configuration template to determine which configuration
option settings are fixed for that user and which must be set by the
ISA. It then packages this information as a planning goal and queries
the ISA. The ISA generates a plan, creates the job configuration and
returns it to the Skoll client.

\noindent {\bf 5.} A Skoll client invokes the job configuration and
returns the results to the Skoll server.

\noindent {\bf 6.} The Skoll server examines these results and invokes
all adaptation strategies. These update the ISA operators to adapt the
global process.

\noindent {\bf 7.} The Skoll server prepares a {\em virtual
scoreboard} (see \url{www.dre.vanderbilt.edu/scoreboard} for an
example) that summarizes subtask results and the current state of the
overall process.

{$\bullet$\bf Evaluating Skoll.}  The Skoll environment supports
DCQA tasks on a range of hardware/OS/compiler platforms.  The
adaptation strategies in Skoll allow QA processes to accurately
pinpoint the configuration space leading to compilation failures
across varied platforms.  This capability provides feedback to
developers by helping them identify how their changes impact software
quality.  In the initial Skoll~\cite{Schmidt:04b} prototype, however,
QA tasks were limited to testing the {\em functional correctness} of
software, {\em i.e.}, clean compilation and passing regression tests.

\subsection {Challenge 2: Evaluating the QoS of
Perfor\-mance-inten\-sive Softw\-are Syst\-ems} 
\label{challenge2}

\paragraph* {\bf Context}
Performance-intensive software systems run on a multitude of
hardware/OS/compiler platforms and provide fine grained knobs to tune
QoS behavior.

\sqzpar\paragraph* {\bf Problem}
To evaluate key QoS characteristics of perfor\-mance-inten\-sive
software, QA engineers today often handcraft individual QA tasks ({\em
e.g.}, benchmarking experiments) by writing (1) interface definitions
that model the data exchange format between clients and servers, (2)
component implementations in the target language, {\em e.g.}, C, C++,
Java, Ada etc., (3) client test applications that measure key
performance metrics, such as round-trip request latency, jitter, and
throughput, and (4) scaffolding code, such as scripts needed to
startup daemons, initialize the software infrastructure and
applications, run experiments, generate results, and tear down the
experiment.  Manually implementing these steps is tedious and
error-prone since each step may be repeated many times for every QA
experiment.  Further, in a handcrafted approach, QA engineers
visualize experiments via application source code, which provides an
excessively low level of abstraction.

\sqzpar\paragraph* {\bf Solution approach $\rightarrow$ the Benchmark
Generation Modeling Language (BGML)} BGML~\cite{Schmidt:04n} is a
model-driven benchmarking tool that allows component middleware QA
engineers to (1) visually model interaction scenarios between
configuration options and system components using domain-specific
building blocks, {\em i.e.}, capture software variability in
higher-level models rather than in lower-level source code, (2)
automate benchmarking code generation and reuse QA task code across
configurations, (3) generate control scripts to distribute and execute
the experiments to users around the world to monitor QoS performance
behavior in a wide range of execution contexts, and (4) enable
evaluation of multiple performance metrics, such as throughput,
latency, jitter, and other QoS criteria.  Below, we describe the key
elements of BGML that are relevant for this paper.

{$\bullet$\bf Syntactic elements in BGML.}  The BGML metamodel
defines a modeling paradigm that allows the specification of QoS
configurations, parameters, and constraints. To allow variation in
data exchange, BGML can model a subset of OMG's IDL interface. To
quantify various performance characteristics, it also models QoS
metrics such as latency, throughput and jitter.  The BGML modeling
language consists of the following building blocks based on a
QoS-enabled implementation of the CORBA Component Model(CCM)
middleware:\footnote{We focus on CORBA and CCM in our work on BGML
since it is currently the most suitable standards-compliant
QoS-enabled middleware for performance-intensive software.  As the QoS
capabilities of other middleware platforms mature we plan to support
them, as well.}

\sqztiny
\begin{itemize}\crunchlist
\item {\bf Object}, which in CORBA is an implementation entity that
consists of an identity, an interface, and an implementation.

\item {\bf Component}, which in CCM are implementation entities that
collaborate with each other via {\em ports}, which are explained
below.

\item {\bf Server}, which export CORBA objects and/or components to clients.

\item {\bf Client}, which is the program entity that invokes an
operation on an object or component implementation.

\end{itemize}

The motivation for developing these building blocks is to enable QA
engineers to model the following four possible interaction scenarios
in the context of CORBA and CCM: (1) a CORBA server interacting with a
CORBA client, (2) a CORBA server interacting with a CCM component
(playing the role of the client) , (3) a CCM component (playing role
of server) interacting with a CORBA client, and (4) a CCM component
interacting with another CCM component (playing both client and server
roles).  CCM also provides component assemblies that are hierarchical
collection of interacting components. In BGML, an assembly is
considered as a virtual entity that is realized by explicitly modeling
the nesting of components.

BGML defines {\em ports}, which are well-defined interaction points
through with CCM components in BGML communicate with each other. The
following ports are supported in BGML:
\sqztiny
\begin{itemize}\crunchlist

\item {\bf
  Facets}, which define an interface that provides point-to-point method
  invocations from other components. Components and servers provide
  facets for other components/clients to communicate with.

\item 
{\bf Receptacles}, which define an interface that accepts
point-to-point method invocations from other components.

\item 
{\bf Event sources}, which define a mechanism for exchanging typed
messages with one or more components. 

\item 
{\bf Event sinks}, which are recipients of messages generated from
event sources.
\end {itemize}
\sqztiny
\noindent The use of ports in BGML allows QA engineers to model
point-to-point (via facet receptacle interconnection) and
point-to-multi point (via event-source event-sink interaction)
communication.

In BGML, the data exchanged between the between different interaction
entities is represented using CORBA's Interface Definition Language
(IDL), including:
\sqztiny
\begin {itemize}\crunchlist
\item 
{\bf Interfaces}, which represent the type of data exchanged between
communicating entities. In BGML, each interface contains a set of
operations.

\item {\bf Operations}, which have the following attributes associated
with it: (1) {\em argument type}, specifies the type of input, (2)
{\em operation name}, name for this operation and (3) {\em return
type}, specifies type for return argument.

\item 
{\bf EventTypes}, which represent the typed messages that event
sources and sinks exchange. Each EventType has an operation name and
identifier associated with it.
\end{itemize}
\sqztiny
\noindent Allowing QA engineers to model IDL data types facilitates
synthesis of IDL files from the models directly, freeing them from the
need to (1) handcraft IDL files and (2) understand the relatively low
level syntax of the IDL language.

In addition to building blocks required to model the experiment, BGML
provides constructs to observe QoS metrics in the experiment modeled.
BGML currently supports associating QoS parameters with EventTypes and
on a per operation basis with IDL interfaces. The metrics that can be
gathered via BGML include:
\sqztiny
\begin {itemize}\crunchlist
\item {\bf Latency}, which for a given operation/event computes the
  mean roundtrip time at the client.

\item 
{\bf Throughput}, which for a given operation/event computes the mean
number of invocations completed per second at the client.

\item 
{\bf Jitter}, which for a given operation/event computes the variance
in the latency measures (jitter is always associated with a latency or
throughput metric).
\end{itemize}

\noindent Each metric described above has two attributes: (1) {\em
warmup iterations}, which indicates the number of iterations the
operation under test will be invoked before start of actual
measurement and (2) {\em sample space}, which indicates the number of
sample points that will be collected to determine each metric value.
Latency, throughput, and jitter metrics represent commonly used
rubrics for comparing the QoS of performance-intensive software
systems. By providing these building blocks, QA engineers can visually
represent the metric they want to observe in the experiment and
synthesize the code from the models directly.

{$\bullet$\bf Semantic elements in BGML.}  BGML uses the following
three modeling abstractions to help QA engineers compose benchmarking
experiments:
\sqztiny
\begin{itemize}\crunchlist
\item {\bf Containment relation.}  Every component and server can
  export facets to communicate with clients.  Similarly, components
  can also provide event-sources for multi-point communication. Clients
  and components playing role of a client can interact with the exported
  facets/event sources via receptacle and event sinks.  BGML uses the
  containment relation to depict {\em ports}. 

\item {\bf Association relation.}  Facets provide or realize an IDL
  interface. In BGML, this is modeled using an association relation,
  wherein each facet element is connected to an IDL interface.
  Similarly, event sources publish EventTypes that are modeled using
  this relation. A Facet/Event-Source in one component communicates
  with a Receptacle/Event-Sink in another component.  This
  communication is modeled by associating, {\em i.e.}, connecting the
  facet with the receptacle. Similarly, QoS metrics are associated
  with IDL operations using association relationship.

\item {\bf Reference association.}  All dependency information in BGML
  is modeled using references. For example, a receptacle communicating
  with a facet is dependent on the interface exported by the
  facet. Associating any other interface will be flagged as a
  typesystem violation by BGML.
\end{itemize}

{$\bullet$\bf BGML generative tools.}  The BGML model interpreter
parses the model and synthesizes the code required to benchmark the
modeled configuration.  The BGML model interpreter includes the
following code generation engines:
\sqztiny
\begin{itemize}\crunchlist
\item {\bf Benchmark code engine}, which generates source code to run an
  experiment. The generated code includes header and implementation
  files to execute and profile the applications and to summarize the
  results.  This engine relies on the {\em metrics aspects} in which
  end-user specify the metrics to be collected during the experiment.

\item {\bf IDL engine}, which generates the IDL files forming the contract
  between the client and the server.  These files are compiled by the
  CORBA and/or CCM IDL compiler to generate the ``glue-code'' needed
  by the benchmarking infrastructure.  This engine relies on the {\em
  configuration aspect} in which end-users specify the data exchanged
  between the communication entities.

\item {\bf Script engine}, which generates the script files used to run the
  experiment in an automated manner. In particular, the scripts start
  and stop the server/client, pass parameters, and display the
  experimentation results.  This engine is associated with the {\em
  interconnection} aspect in which component interactions are
  specified.
\end{itemize}

\noindent Each of entities described above have attributes, {\em e.g.},
the number of threads in a component, that are specified in the
building blocks as attributes.

{$\bullet$\bf Evaluating BGML.}  BGML helps improve the productivity
of QA engineers by resolving the accidental complexity of handcrafting
tedious and error-prone source code.  For each experiment, the BGML
tool generates close to 90\%~\cite{Schmidt:04n} of the required IDL,
configuration and implementation files.  Since it is a generative
tool, BGML only reduces the cost of constructing benchmarking
experiment for various configurations.  In its original form, however,
it did not provide information on the consequences of configuration
option on QoS behavior on varied hardware/OS/compiler platforms.

\subsection {Challenge 3: Assessing QoS of Performan\-ce-intensive
Software Across Large Configuration Spaces} 
\label{challenge3}

\paragraph* {\bf Context}
As developers create and modify their perfor\-mance-inten\-sive
software systems, they often conduct benchmarking experiments to
identify when changes negatively affect performance. Due to time and
resource constraints, however, these experiments are typically
executed on a very small number of default configurations.  While this
provides some data, it leaves substantial portions of the entire
configuration space unevaluated, allowing performance problems to
escape detection until the software is fielded.  To close this gap,
developers of perfor\-mance-inten\-sive software could use the BGML
modeling language together with the Skoll DCQA environment to gather a
much wider sampling of performance data.

\sqzpar\paragraph* {\bf Problem}
Although Skoll and BGML provide an infrastructure for performing
large-scale QA, the configuration spaces of perfor\-mance-inten\-sive
software systems are often so large that brute force processes are
still infeasible. For example, the ACE+TAO systems have $\sim$500
configuration options, with over $2^{500}$ potential combinations.  To
be effective for highly configurable performance-intensive software
systems, therefore, DCQA processes must generally include some type of
{\em adaptation strategy} to efficiently navigate large configuration
spaces.

\sqzpar\paragraph* {\bf Solution $\rightarrow$ Applying Experimental Design
Theory for Configuration Space Reduction}

In the remainder of this section we present a new DCQA process, called
{\em main effects screening}.  The aim of this process is to
efficiently improve the visibility of developers into the QoS of
performance-intensive software across large configuration spaces.  As
described below, we have integrated BGML and Skoll to instantiate and
execute the process.

As software systems change, developers often run regression tests to
detect unintended functional side effects. In addition to
functionality, developers of perfor\-mance-inten\-sive systems must
also be wary of unintended effects on QoS.  They will therefore
periodically run performance benchmarking tests to detect such
problems.  As described in Section~\ref{intro}, however, QA efforts
can be confounded in highly configurable systems due to the enormous
configuration space.  Moreover, time and resource constraints (and
high change frequencies) severely limit the number of configurations
that can be examined.  For example, in our earlier experience with
ACE+TAO~\cite{Schmidt:04b}, only a small number of default
configurations are benchmarked routinely.  As a result, ACE+TAO
developers get a {\em very} limited view of their middleware's QoS and
problems not readily seen in the single default configuration can
escape detection until system based on ACE+TAO are fielded.

To address these problems, we developed the {\em main effects
screening} DCQA process, which is performed in the following two
phases:

{\bf $\bullet$ Phase 1.} We execute a large-scale, formally-designed
experiment across the Skoll grid. As part of this experiment, we run
benchmarks on a wide-ranging, but sparsely distributed, set of
configurations. These configurations are selected using a class of
experimental designs called {\em screening designs}~\cite{wu}, which
are highly economical and can reveal individual options that
significantly affect performance (colloquially, these are referred to
as first-order or ``main'' effects). These designs are economical
since they are not intended to detect high-order interaction effects
({\em i.e.}, significant interactions between, {\em e.g.}, five
different options).  The choice of significance level at which to
separate significant from non-significant options can be set by QA
process engineers.

{\bf $\bullet$ Phase 2.} Once we have identified the main effects, we
only focus on them, effectively reducing the configuration space to
just these few options.  The process continues executing using only
in-house resources. Each time the system changes, we exhaustively
benchmark all combinations of the first-order options, while using
default (or random) settings for the remaining options.  Our intent is
that by focusing only on the first-order options, we can greatly
reduce the configuration space, while at the same time capture a much
more complete picture of the system's QoS.  This data is plotted and
maintained on the system's build scoreboard ({\em e.g.},
\url{www.dre.vanderbilt.edu/Stats}).  Since the main effects might
change over time, the process can be restarted periodically to
recalibrate the main effects options.

Although the details of computing a screening design are beyond the
scope of this paper, we give a simple example to help introduce key
terminology and concepts.  We will assume our example system has 5
binary configuration options A, B, C, D, and E.  The configuration
space thus has 32 ($2^{5}$) configurations and the example screening
design will involve only 8 configurations.  We begin by creating a
$2^{(3)}$ full-factorial design for options A, B, and C. This starting
point ensures that the main effects will not be confounded with each
other, which is referred to as a resolution
%III design (See Section~\ref{screening} for more details).
III design.

Since all the options are binary, we encode their settings as either
(-) for the first setting or (+) for the second setting. Non-binary
options can be handled as well, but the design is more complicated.
At this point, our initial design is as follows:

\begin{verbatim}
A - + - + - + - +
B - - + + - - + +
C - - - - + + + +
\end{verbatim}

This design includes only three options. To compute the settings of
the fourth option, we select a design generator, indicated 4=12, to
generate the settings of the fourth option. The number on the left
side of the design generator equation gives the row that will be
generated, while the right side indicates {\em how} that row will be
generated. In this particular case, therefore, the fourth row (for D)
will be generated by multiplying rows 1 and 2 {\em i.e.}, each entry
in the row for D is the same as the product of the corresponding
entries in the rows for A and B. We generate row E similarly, using
design generator 5=23 and the final design matrix is as follows:

\begin{verbatim}
A - + - + - + - +
B - - + + - - + +
C - - - - + + + +
D + - - + + - - +
E + + - - - - + +
\end{verbatim}

%Since the column for C is used for estimating the main-effect of factor
%C and and also for the interaction of A and B, we say that the factor
%main-effect C is aliased with the interaction effect effect A and B.

To analyze the data, we must calculate the main-effect of each option.
In our simple example, the main-effect of option A, ME(A), is ME(A) =
z(A-) - z(A+), where z(A-) and z(A+) are the mean values of the
observed variable over all runs when A is (-) and when A is (+),
respectively.

\subsection{Putting It All Together}

\iffalse
The initial prototype of Skoll allows the QA engineer to monitor
functional correctness of software across a wide range of
platforms. However, using Skoll the QA engineer cannot run DCQA tasks
to know how combinations of configuration options affect QoS behavior
on varied platforms.  Similarly, the initial prototype of BGML tool
allows the QA engineer to compose experiments that measure QoS
behavior for various interaction scenarios. However, BGML does not
allow the QA engineer to know how the various interaction scenarios
affect QoS characteristics across varied platforms. Further, the BGML
tool is currently used to generate benchmarking experiments on a small
number of default configurations.  The motivation for this being,
ACE+TAO software provides $\sim$ 500 command line options and testing
every combination would lead to constraints on time and resources. The
main problem with this approach is that it leaves nearly all of the
possible configurations untested, thereby allowing performance
problems to escape detection until their software is fielded.

Performance intensive software have a wide range of configuration
options.  For example, ACE+TAO software has $\sim$ 500 command line
options.  As these systems evolve developers often conduct
benchmarking experiments in hopes of identifying changes the
negatively affect performance. Due to time and resource constraints,
however, these experiments are typically executed on a small number of
default configurations.  The main problem with this approach is that
it leaves nearly all of the possible configurations untested, thereby
allowing performance problems to escape detection until their software
is fielded.


\paragraph* {\bf Solution $\rightarrow$ Experimental designs
for configuration space reduction}

We have developed a two phase solution to address the aforementioned
challenges. In the first phase, we have enhanced Skoll to leverage BGML's
generative capabilities to construct benchmarking experiments that capture
QoS behavior across a wide range of platforms. Figure~\ref {fig:ccmskoll}
presents an overview of how we have integrated BGML with the existing Skoll
infrastructure.
\fi

Figure~\ref {fig:ccmskoll} presents an overview of how we have
integrated BGML with the existing Skoll prototype to support the {\em
main effects screening} DCQA process described in
Section~\ref{challenge3}.
\begin{figure}[htpb]
\vspace{0in}
\centerline{\epsfxsize=7cm
\epsffile{figures/CCMPerfSkoll.eps}}
\bfcaption{Skoll QA Process View with BGML Enhancements}
\label{fig:ccmskoll}
\vspace{0.1in}
\end{figure}
Below we describe the enhanced Skoll QA process, referencing the steps
shown in the figure.

\noindent {\bf A} A QA engineer defines a test configuration
using BGML models.  The necessary experimentation details are captured
in the models, {\em e.g.}, the configuration options examined during
main effects screening, the IDL interface exchanged between the client and the
server, and the benchmark metric performed by the experiment.

\noindent {\bf B \& C} The QA engineer then uses BGML to
interpret the model.  The paradigm interpreter parses the modeled
CORBA middleware configuration options and generates the required
configuration files to configure the underlying CORBA middleware.  The
BGML para\-digm interpreter then generates the required benchmarking
code, {\em i.e.}, IDL files, the required header and source files, and
necessary script files to run the experiment.  Steps A, B, and C also
generate internal files used by Skoll.

\noindent {\bf D} When users register with the Skoll
infrastructure they obtain the Skoll client software and configuration
template. This step happens in concert with Step 2, 3, and 4 of the
Skoll process.

\noindent {\bf E \& F} Clients execute steps in the 
main effects screening experiment
and return the result to the Skoll server, which updates its internal
database. When prompted by developers, Skoll displays execution
results using an on demand scoreboard. This scoreboard displays graphs
and charts for QoS metrics, {\em e.g.}, performance graphs, latency
measures and foot-print metrics.  Steps E and F correspond to steps 5,
6, and 7 of the Skoll process.
