% $Id: related_new.tex,v 1.20 2006/07/24 02:36:27 aporter Exp $

\section{Related Work}
\label{related}  

This section compares our work on reliable effects screening and
performance evaluation techniques in Skoll with other related research
efforts, including (1) applying {\em design-of-experiments (DOE)
testing} to software engineering, (2) large-scale testbed environments
for conducting experiments using heterogeneous hardware, OS, and
compiler platforms, (3) evaluating the performance of layered software
systems, and (4) feedback-based optimization techniques that use
empirical data and mathematical models to identify performance
bottlenecks.

\noindent
{\bf Applying DOE to software engineering.}  As far as we know, we are
the first to use screening designs to assess software performance.
The use of DoE theory within software engineering has focused mostly
on {\em interaction testing}, largely to compute and sometimes
generate minimal test suites that cover all combinations of specified
program inputs.  Mandl \cite{mandl} first used orthogonal arrays, a
special type of covering array in which all $t$-sets occur {\em
exactly} once, to test enumerated types in ADA compiler software.
This idea was extended by Brownlie {\em et al.}  \cite{oats} who
developed the orthogonal array testing system (OATS). They provided
empirical results to suggest that the use of orthogonal arrays is
effective in fault detection and provides good code coverage.

Dalal {\em et al.} \cite{dalal} argue that the testing of all pairwise
interactions in a software system finds a large percentage of the
existing faults. In further work, Burr {\em et al.} \cite{burr},
Dunietz {\em et al.}~\cite{dunietz} and Kuhn {\em et al.}~\cite{kuhn}
provide more empirical results to show that this type of test coverage
is effective. These studies focus on finding unknown faults in already
tested systems and equate covering arrays with code coverage
metrics. Yilmaz {\em et al.}~\cite{ca} used covering arrays as a
configuration space sampling technique to support the characterization
of failure-inducing option settings.

\noindent
{\bf Large-scale benchmarking testbeds.}  EMULab~\cite{White02} is a
testbed at the University of Utah that provides an environment for
experimental evaluation of networked systems.  EMULab provides tools
that researchers can use to configure the topology of their
experiments, {\em e.g.}, by modeling the underlying OS, hardware, and
communication links.  This topology is then mapped to $\sim$250
physical nodes that can be accessed via the Internet~\cite{EMULab:03}
.  The EMULab tools can generate script files that use the Network
Simulator (NS) (\url{www.isi.edu/nsnam/ns/}) syntax and semantics to
run the experiment.

The Skoll infrastructure provides a superset of EMULab that is not
limited by resources of a particular testbed, but instead can leverage
the vast end-user computer resources in the Skoll grid.  Moreover, the
Skoll's MDE-based tools described in Section~\ref{skolloverview} can
generate NS scripts to integrate our benchmarks with experiments in
EMULab.

\iffalse 
% Adam, not sure why the following two sections related to our work -
% andy 
\noindent
{\bf Software performance analysis techniques.}  These techniques
apply analytical and empirical models to analyze and estimate
performance of software using different parameters such as input
workloads, queue lengths and platform characteristics.  For example,
to estimate performance of layered architectures~\cite{Sharma:05}
applied Discrete Time Markov Chains to model the software system based
on parameters such as CPU and I/O requirements on a per layer basis.
A queuing network model is created from the requirement and is solved
to provide the architect with information, such as system bottlenecks.

The reliable effects screening process differs from
the~\cite{Sharma:05} approach by considering software configurations
and their interactions rather than a layered approach.  In our
approach, the configuration can be crosscutting {\em i.e.}, spanning
multiple layers.  Our approach also considers interactions between
configuration options, which enables architects to detect flows within
the system that affect QoS.
\fi

\noindent {\bf Feedback-driven optimization techniques.}  Traditional
feedback-driven optimization techniques can be divided into {\em
online}, {\em offline}, and {\em hybrid} analysis.  Offline analysis
has commonly been applied to program analysis to improve
compiler-generated code.  For example, the ATLAS~\cite{Padua:03}
numerical algebra library uses an empirical optimization engine to
decide the values of optimization parameters by generating different
program versions that are run on various hardware/OS platforms.  The
output from these runs are used to select parameter values that
provide the best performance.  Mathematical models are also used to
estimate optimization parameters based on the underlying architecture,
though empirical data is not fed into the models to refine it.

Like ATLAS, Skoll's MDE tools use an optimization engine to
configure/\-customize software parameters in accordance to available
OS platform characteristics (such as the type of threading,
synchronization, and demultiplexing mechanisms) and characteristics of
the underlying hardware (such as the type of CPU, amount of main
memory, and size of cache).  This information can be used to select
optimal configurations ahead of time that maximize QoS behavior.
 
Online analysis is commonly used for feedback control to adapt QoS
behaviors based on dynamic measures. An example of online analysis is
the ControlWare middleware~\cite{zhang:02}, which uses feedback
control theory by analyzing the architecture and modeling it as a
feedback control loop.  Actuators and sensors then monitor the system
and affect server resource allocation.  Real-time scheduling based on
feedback loops has also been applied to Real-time CORBA
middleware~\cite{Lu-FCS:02} to automatically adjust the rate of remote
operation invocation transparently to an application.

Though online analysis enables systems to adapt at run-time, the
optimal set of QoS features are not determined at system
initialization.  Using the MDE tools, QoS behavior and performance
bottlenecks on various hardware and software configurations can be
determined offline and then fed into the models to generate optimal
QoS characteristics at model construction time.  Moreover, dynamic
adaptation can incur considerable overhead from system monitoring and
adaptation, which may be unacceptable for performance-intensive DRE
systems.
  
Hybrid analysis combines aspects of offline and online analysis.  For
example, the continuous compilation strategy~\cite{Childers:03}
constantly monitors and improves application code using code
optimization techniques.  These optimizations are applied in four
phases including (1) {\em static analysis}, in which information from
training runs is used to estimate and predict optimization plans, (2)
{\em dynamic optimization}, in which monitors apply code
transformations at run-time to adapt program behavior, (3) {\em
offline adaptation}, in which optimization plans are actually improved
using actual execution, and (4) {\em recompilation}, where the
optimization plans are regenerated.

Skoll's MDE-based strategy enhances conventional hybrid analysis by
tabulating platform-specific and platform-independent information
separately using the Skoll framework.  In particular, Skoll does not
incur the overhead of system monitoring since behavior does not change
at run-time.  New platform-specific information obtained can be fed
back into the models to optimize QoS measures.
   
\noindent {\bf Generative Benchmarking Techniques.}  There have been a
several initiatives that use generative techniques similar to our
approach for generating test-cases and benchmarking for performance
evaluation.  The ForeSight~\cite{LiuY:02} tool uses empirical
benchmarking engine to capture QoS information for COTS based
component middleware system. The results are used to build
mathematical models to predict performance. This is achieved using a
three pronged approach of (1) create a performance profile of how
components in a middleware affect performance, (2) construct a
reasoning framework to understand architectural trade-offs, {\em
i.e.}, know how different QoS attributes interact with one another and
(3) feed this configuration information into generic performance
models to predict the configuration settings required to maximize
performance.

The SoftArch/MTE~\cite{Grundy:01} tool provides a framework for system
architects to provide higher level abstraction of the system
specifying system characteristics such as middleware, database
technology, and client requests. The tool then generates an
implementation of the system along with the performance tests that
measure system characteristics. These results are then displayed back,
{\em i.e.}, annotated in the high level diagrams, using tools such as
Microsoft Excel, which allows architects to refine the design for
system deployment.

Our MDE approach closely relates to the aforementioned approaches.
Both the ForeSight and SoftArch tools, however, lack DCQA environments
to help capture QoS variations accurately on a range of varied
hardware, OS, and compiler platforms. Rather than using generic
mathematical models to predict performance, MDD tools use a
feedback-driven approach~\cite{Schmidt:04k}, wherein the DCQA
environment is used to empirically evaluate the QoS characteristics
offline. This information can then be used to provide QA engineers
with accurate system information.  Moreover, platform- and
application-specific optimization techniques~\cite{Schmidt:05w} can
then be applied to maximize QoS characteristics of the system.
