|
Antimony
Ultra-fast Blue Noise Generation
Greg Humphreys
home page of Antimony
ampling distributions with blue noise characteristics
are widely used in computer graphics. Poisson-disc distributions are
known to have blue noise characteristics but have traditionally been
thought of as too expensive to generate and as an alternative many
techniques have been developed for approximating or tiling precomputed
such distributions. The Antimony project is exploring new, efficient
methods for the direct computation of true Poisson-disc distributions.
We have found a simple new algorithm for generating approximate
distributions that runs in linear time. We are analyzing the spectral
properties of these distributions and developing ways to further improve
their blue noise spectral characteristics. One key advantage of our
technique is that it permits a natural extension to support importance
sampling of a given density function, along with the use of the
resulting point set as a texture basis function.
Archsplit
Non-invasive Generation of Exploded Views
Greg Humphreys
home page of Archsplit
rchsplit is a system for interactively producing
exploded views of 3D architectural environments such as multi-story
buildings. These exploded views allow viewers to simultaneously see the
internal and external structures of such environments. To create an
exploded view, we analyze the geometry of the environment to locate
individual stories. We then use clipping planes and multipass rendering
to separately render each story of the environment in exploded
form. Archsplit operates at the graphics driver level and therefore can
be applied to existing OpenGL applications, such as first-person
multiplayer video games, without modification. The resulting
visualization allows users to understand the global structure of
architectural environments and to observe the actions of dynamic
characters and objects interacting within such environments.
Bioinformatics
Computational biology for the new millennium
Bill Pearson and Gabriel Robins
home page of Bioinformatics
e are addressing important problems in computational
biology, including the construction of evolutionary (phylogenetic) trees
over a given set of taxa (e.g., organisms, DNA molecules, etc.), where
the optimization objective entails the best-fit of tree topologies under
a least-squares or parsimony criteria. Another problem that we have
investigated is the primers selection problem, which arises in
polymerase chain reaction (PCR) experiments (i.e., DNA cloning). Here,
given a set of DNA strands and a cost criterion, our objective is to
find a minimal covering set of compatible DNA subsequences (primers)
having least cost, in the hope of discovering new proteins. We are also
researching the topographies of solution space landscapes, as well as
new heuristics for multiple sequence alignment.
Calamari
Localization in Large Wireless Sensor Fields
Kamin Whitehouse
home page of Calamari
ireless sensor networks consist of many small and
cheap computational nodes that can sense the environment, communicate
with neighboring nodes, and perform simple computations on sensor data.
They may be deployed outdoors in large sensor fields to help detect and
control the spread of wild fires, to detect and track enemy vehicles, or
for environmental monitoring and precision agriculture. In many such
application, each node requires location information to properly
interpret its own sensor data and to act according to its placement in
the world and in the network. Calamari is a system for providing each
node in a sensor field with its own location information. Multi-hop
sensor field localization is challenging because of the complex
interaction between ranging error, the localization algorithm, and the
actual network topology. Calamari predicts and explores these
interactions using empirical characterizations and trace-based
simulations.
Calibration
Macro-calibration in Sensor/Actuator Networks
Kamin Whitehouse
home page of Calibration
nstead of using a single highly-engineered sensor,
sensor networks monitor the world through hundreds of cheap
assembly-line components. Many such devices have poor factory
calibration and drift over time during use. Because sensor networks can
contain thousands of such sensors and can be influenced by the
environment, they must self-calibrate after deployment. Unfortunately,
pairing each sensor with an actuator to provide a known stimulus does
not solve this problem because the actuators must also be calibrated.
We developed a technique in which each node calibrates its sensor using
the actuators of all of its neighbors. This creates an over-constrained
system from which calibration coefficients can be inferred even in the
face of some noise from both the sensors and actuators. We demonstrated
the calibration technique on a 36-node testbed with microphones and
acoustic actuators.
Chromium
Scalable Interactive Graphics with Commodity Technology
Greg Humphreys
home page of Chromium
calable graphics systems are becoming increasingly
rarer, and remain an expensive luxury available only to a few
institutions. Commodity graphics technology, despite enjoying
capability increases that have continued to outpace Moore's law, tends
not to scale at all; that is, users cannot pay more money to achieve
higher performance. Our research attempts to bridge this gap by
allowing clusters of commodity graphics accelerators to behave as a
single logical graphics pipeline with a parallel interface. In contrast
to other approaches to this problem, we have focused on achieving our
goals only by manipulating streams of graphics command data. This means
that existing applications can very easily take advantage of the
underlying parallel graphics architecture, often without recompilation.
The current direction of this project is to view scalable visualization
as a remote service, much like a network-attached file system.
This way, an institution could install a large cluster to serve the
large-data visualization needs of an entire building, department, or
even a university. We believe that adding scalable visualization
services to a ubiquitous computing environment would represent a
substantial leap forward for smart spaces and the preferred computing
platform of the future.
CoCo
Continuous Compilation
Mary Lou Soffa and Jack Davidson
home page of CoCo
oday's challenge for program optimization research is
to develop new techniques and approaches that yield performance
improvements that go beyond today's small single digit improvements. In
this research, we address this challenge by investigating and developing
an innovative framework and system for continuously and adaptively
applying optimizations. Our system, the Continuous Compiler (CoCo),
applies optimizations both statically at compile-time and dynamically at
run-time using optimization plans developed at compile time and adapted
at run time. Rather than focusing on developing new optimization
algorithms (e.g., a new register allocation algorithm, a new loop
interchange algorithm) or improving existing optimizations (e.g., better
coloring heuristics, better placement algorithms), this project focuses
on understanding the interaction of existing optimizations and the
efficacy of static and dynamic optimizations. Using this knowledge along
with information about the application gathered by static analysis,
profile information and monitoring, CoCo determines how to apply a suite
of optimizations so that the optimizations work in concert to yield the
best improvements.
Collision Detection
Exploiting the Capture Effect for Collision Detection and Recovery
Kamin Whitehouse
home page of Collision Detection
esides complex techniques like CDMA, most wireless
MAC protocols today lose packets during collisions and cannot
differentiate between packet collisions and channel noise. Therefore,
they unnecessarily avoid simultaneous transmission even though many
radios exhibit the Capture Effect - the ability to correctly receive a
strong signal from one transmitter despite significant interference from
other transmitters. We developed a technique to exploit this effect to
cheaply detect and recover from packet collisions using only simple,
low-power radios that are commonly used in sensor networks. This
technique differentiates between collisions and channel noise, recovers
one of the packets entirely, and identifies the colliding transmitters.
This enables more aggressive MAC protocols that transmit concurrently
with neighbors; if a collision occurs, one of the packets will actually
get through and feedback can be used to request the lost packets and/or
to prevent future collisions. We demonstrated the collision detection
and recovery technique on a 28-node testbed, and experiments with new
MAC protocols yield 30% gains in bandwidth and latency.
ComponentOS
Component Based OSs for Embedded Systems
Jack Stankovic and Marty Humphrey
home page of ComponentOS
he use of component based software for constructing
and tailoring embedded systems has promise. However, most third party
components are too heavyweight and don't explicitly address time,
memory, reliability, power, cost, and other cross cutting constraints.
A key problem, and the one where most people have spent their energies,
is developing the components themselves without fully addressing how
they interact with other components or how they fit into a components
infrastructure. While significant work has been done in developing
components, less has been done with components suitable for embedded
systems. Our research in developing component based SOS for embedded
systems can be described in three key areas: developing and implementing
domain specific components and component infrastructures, developing
configuration tools to help in composition of embedded systems, and
non-functional analysis to assess, for example, real-time and fault
tolerance capabilities.
ControlWare
Feedback Performance Control in Software Services
Tarek Abdelzaher and Jack Stankovic
home page of ControlWare
oftware systems are becoming larger and more
complex. At the same time, they are being deployed in applications where
performance guarantees are required. Feedback control theory is a
promising technology for performance control in software systems. We are
developing solutions using feedback control for a variety of systems and
organizing the results in a manner that we hope establishes a theory and
practice of feedback control in computer systems. To this end we have
built ControlWare. ControlWare is a middleware QoS-control architecture
based on control theory. ControlWare allows the user to express QoS
specifications, maps these specifications into appropriate feedback
control loops, tunes the loop controllers analytically and connects the
loops to the right sensors and actuators such that the desired QoS is
achieved.
Computational Geometry
Where algorithms and geometry meet
Gabriel Robins
home page of Computational Geometry
e are addressing open practical issues in
computational geometry, an area that lies at the interface between the
fields of geometry and algorithms. Recent projects include devising new
algorithms with improved approximation ratios for the Group Steiner
problem in general graphs, as well as the development of a heuristic
with the currently best-known approximation bound for the general graph
Steiner tree problem. We have also formulated and addressed a new and
practical time-dependent variant of the classical Traveling Salesman
Problem, which led to a number of follow-up works. Other results
include upper and lower bounds on the maximum degree of minimum spanning
trees under various metrics, and efficient algorithms for pattern
recognition in point sets, which are applicable to landmine detection.
Our work is motivated and driven by real-world needs and applications.
Computer Vision
Robotics, planning, and Artificial Intelligence
Worthy Martin
home page of Computer Vision
e do theoretical and experimental research on
computer vision and image processing. Our goal is to develop real-time
vision architectures, including applications for visually guided mobile
robots. Our research agenda includes motion understanding, visual
tracking of moving objects, and perception-action systems. We have
several robots, a large set of image processing equipment, and an SGI
reality engine at our disposal. We are interested in a variety of
aspects of computer vision and image processing, with an emphasis on
real-time vision applications. Topics of current interest include
software for advanced vision systems, architectures and representational
structures for visually guided mobile robots, systems to facilitate the
use of pipelined image processors, visual tracking of moving objects,
and motion understanding.
Data Mining Meets Data Privacy
Privacy-Preserving Pattern Detection in Massive Dynamic Datasets
Nina Mishra
home page of Data Mining Meets Data Privacy
rganizations now collect massive quantities of data
about private citizens. On the one hand, there is a great need for
algorithms that unearth patterns in these datasets so that we can make
medical breakthroughs, scientific discoveries, catch terrorists, etc.
From a data mining viewpoint, the more private data that is revealed the
better the data mining. However, competing with the need for learning
patterns is the need for privacy where the less private data that is
revealed, the better privacy guarantees. This project seeks to resolve
the apparent contradiction: can we have both? I.e., can we have privacy
and homeland security, can we have privacy and design new drugs. By
formally defining privacy using cryptographic concepts, various
algorithms are being considered for understanding privacy and minability
including input perturbation, output perturbation, and secure
computation.
DDAM
Data-Driven Appearance Models for Computer Graphics
Jason Lawrence
home page of DDAM
ver the last decade, the computer graphics community
has witnessed a significant increase in the availability of measured (or
non-parametric) appearance data. Although directly using these
measurements to shade a surface can provide a level of realism that is
difficult to achieve with traditional analytic models, fully
incorporating non-parametric appearance data into a traditional computer
graphics pipeline still presents several research challenges. The goal
of this project is to develop new representations for non-parametric
appearance data that address some of these open research challenges. We
have designed representations that support both interactive rendering
and efficient sampling in the context of physically-based rendering. We
also investigate more general representations that allow a user to edit
the variation in a high-dimensional function while retaining its
fidelity to the original measurements.
Dependability
Reliable, Trusted and Maintainable software
John Knight, David Evans and Jack Davidson
home page of Dependability
ependability of a computing system is the ability to
deliver service that can justifiably be trusted. Dependability is the
system property that integrates such attributes as reliability,
availability, safety, security, and maintainability. We focus on
research issues related to software and architectures in high-value
systems - computing systems of extreme importance to society whose
failure would have a severe negative impact whether measured in terms of
time, money or loss of life. Our research interests encompass
safety-critical systems, such as medical devices, avionics, weapons
systems; critical infrastructures such as financial networks,
transportation systems, and power systems; and emergent grid computing
systems that increasingly play a strategically vital role in such
diverse industries as finance, health care, pharmaceuticals, and
aerospace. We work closely with industrial and governmental partners to
ensure research relevance. Past and current members of our group
continue to provide leadership in academia, industry, and the military.
DRPM
Power and Temperature Optimization of Storage Systems
Sudhanva Gurumurthi
home page of DRPM
enser and faster silicon integration has only
exacerbated the problem of moving data to and from the storage
subsystem. With applications getting larger and becoming more
data-centric, the I/O subsystem has become a compelling target of
optimization. We investigate how to manage power and temperature issues
in storage systems. We proposed the use of a novel disk drive design,
called "DRPM", where the disk can rotate at multiple speeds. This
allows a dynamic tradeoff power for performance at a finer granularity
rather what is done traditionally, i.e., either complete spindown where
no I/O is possible, or else full-speed operation. DRPM is now widely
researched by both the computer architecture and operating systems
communities. Our studies also indicate that DRPM is likely to become
one of the best solutions to effectively tackle temperature issues in
disk drives, especially as computers are moving into an era where disk
performance will increasingly rely on RPM rather than recording surface
density.
Eos
Aspect-Oriented Extension to C#
Kevin Sullivan
home page of Eos
he Eos project is an aspect-oriented extension to C#.
Eos improves upon the current aspect-oriented language model in three
dimensions. First, it generalizes aspect instantiation & advice weaving
model to eliminate the need for the work-arounds that are unavoidable
today when aspects are used to express integration concerns. Second it
generalizes the join point model. Third it eliminates the distinction
between class and aspect constructs in favor of a single conceptual
building block that combines the expressive capabilities of current
classes and aspects, significantly improving conceptual integrity and
uniformity in language design.
FASTA
Biological Sequence Comparison
Bill Pearson
home page of FASTA
apid concurrent development of molecular cloning
techniques, DNA sequencing methods, efficient sequence comparison
algorithms, and computer workstations has revolutionized the role of
biological sequence comparison in molecular biology. Sequence
comparison is now used routinely as the first characterization of a DNA
or protein sequence and is an essential part of the human genome
project. We developed FASTA, one of the first widely used programs for
searching protein and DNA sequence databases. Currently, we are
developing and testing sequence comparison methods that will allow us to
"push back" the evolutionary horizon - the distance at which related
protein sequence can be reliably detected - from the current 800-1,000
million years to more than 2,000 million years. We also use
genome-scale sequence comparison to identify potential "young" proteins
- proteins that emerged over the last 200-400 million years.
Feedback Control
Real-Time Scheduling
Jack Stankovic, Sang Son, Gang Tao and Tarek Abdelzaher
home page of Feedback Control
espite the significant body of results in real-time
scheduling, many real world problems are not easily supported. While
algorithms such as Earliest Deadline First, Rate Monotonic, and the
Spring scheduling algorithm can support sophisticated task set
characteristics (such as deadlines, precedence constraints, shared
resources, jitters, etc.), they are all open loop scheduling algorithms.
Open loop refers to the fact that once schedules are created they are
not adjusted based on continuous feedback. While open-loop scheduling
algorithms can perform well in static or dynamic systems in which the
workloads can be accurately modeled, they can perform poorly in
unpredictable dynamic systems. In this project we are developing a
theory and practice of feedback control real-time scheduling. Feedback
control real-time scheduling defines error terms for schedules, monitors
the error, and continuously adjusts the schedules to maintain stable
performance. We have developed a practical feedback control real-time
scheduling algorithm, FC-EDF, which is a starting point in the long-term
endeavor of creating of theory and practice of feedback control
scheduling. We are applying out results to applications such as web
servers, agile manufacturing, and defense systems.
Galileo
An Advanced Fault Tree Analysis Tool
Kevin Sullivan
home page of Galileo
he Galileo Fault Tree Analysis Tool is an
experimental system being built within our Package-Oriented Programming
(POP) project. Galileo supports advanced fault tree analysis
capabilities developed under the direction of Professor Joanne Bechta
Dugan. Specifically, Galileo supports Dugan's DIFtree analysis method.
Package-Oriented Programming is a research project investigating the
reuse and integration of very large-scale components. By very large, we
mean "on the order of a million lines of code equivalent." We are
exploring the use of shrink-wrapped software applications as massive
building blocks, because it appears that new package architectures are
sufficiently promising (but also lacking in certain essential ways) to
warrant considerable research attention. Key issues include the design
of mechanisms supporting restriction, specialization, extension and
integration of packages. Our research addresses several issues,
including (1) architectural styles for POP systems; (2) generalizing the
architectural approaches that appear to make POP a reasonably successful
approach to large-scale reuse and integration; and (3) investigating the
software development life-cycle for systems developed in the POP style.
Genesis
A Framework for Achieving Component Diversity
John Knight, David Evans, Jack Davidson and Anh Nguyen-Tuong
home page of Genesis
e seek to reproduce the genetic diversity found in
nature by deliberately and systematically introducing diversity in
software components. The hope is that while the phenotype of software
components will be similar (its functional behavior), its genotype will
contain enough variations to protect the population against a broad
class of diseases (attacks, aging). As our engine of software
diversity, we will use a systematic and comprehensive methodology based
on two fundamental and complementary approaches: design diversity and
data diversity, Design diversity is the creation of multiple
implementations of a given specification such that the different
implementations have different designs. Data diversity is the use of
multiple copies of a single implementation with each copy operating on
different input data but yielding the same desired results. In data
diversity, the different data streams are produced by a process known as
data re-expression. Each diversity approach will be applied
systematically at multiple levels of software representation to produce
a spectrum of techniques for the creation of diverse software
components.
GPU
General Purpose Computing on the GPU
Greg Humphreys
home page of GPU
n this project, we looked at the application of
graphics hardware to general-purpose numeric computing. Specifically, we
used programmable graphics hardware to create a system that is capable
of solving a variety of partial differential equations with complex
boundary conditions. Our system implements the multigrid method, a fast
and popular approach to solving large boundary value problems. We have
demonstrated the viability of this technique by using it to accelerate
three applications: simulation of heat transfer, modeling of fluid
mechanics, and tone mapping of high dynamic range images. We also
demonstrated that it is possible to cleanly map a state-of-the-art tone
mapping algorithm to the pixel processor. This allows an interactive
application to achieve higher levels of realism by rendering with
physically based, unclamped lighting values and high dynamic range
texture maps.
Graphics
The UVa Computer Graphics Group
Greg Humphreys and Jason Lawrence
home page of Graphics
he UVa Graphics Group is actively investigating a
number of exciting new research directions. Projects include: Chromium
- a scalable interactive graphics with commodity technology; building
multiagent behaviors based on learning from observation; dynamically
physical simulation of characters in graphical environments; scanning a
very high-resolution and accurate 3D model of Thomas Jefferson's home
Monticello; geometric simplification and perceptually-based level of
detail rendering; VDSLib - a free Software for view-dependent
simplification; and VLSIR - very large scale interactive rendering.
Grid Computing Group
Wide-Area Computing Across Multiple Administrative Domains
Marty Humphrey
home page of Grid Computing Group
rid Computing is wide-area computing across multiple
administrative domains. There are many issues that must be solved in
order to deliver a "Grid Computing Infrastructure". The issues our
research projects address include security, scheduling, programmability,
and usability. Current projects underway in our group include: the
design, Development, and Deployment of the Web Services Resource
Framework (WSRF) on the .NET Framework (WSRF.NET); the design and
Deployment of the University of Virginia Campus Grid (UVaCG); enhancing
Grid Security by Leveraging Authentication and Authorization
Infrastructures (through a partnership with the San Diego Supercomputing
Center); policy Management in Grids; dependable Grids; and delivering a
Scalable and Secure Programming Model for Grid Computing.
Hood
A Distributed Programming Abstraction
Kamin Whitehouse
home page of Hood
raditional distributed programming abstractions such
as shared memory are difficult to apply to sensor networks because of
the unreliable, low-bandwidth, geographically-constrained communication
model. Instead, many distributed sensor network algorithms are based on
the concept of a neighborhood, in which each node selects a set of
important neighbors and maintains state about them. However,
programmers must still implement neighborhoods in terms of their
component parts: messaging, data caching, and membership. We developed
an abstraction called Hood that unifies these fundamental concepts as a
distributed programming primitive for sensor networks. Using Hood, a
neighborhood can be defined by a set of criteria for choosing neighbors
and a set of variables to be shared, such as a one-hop neighborhood over
which light readings are shared, and a two-hop neighborhood over which
both locations and temperature are shared. Once the neighborhoods are
defined, Hood provides an interface to read the names and shared values
of each neighbor. Beneath this interface, Hood hides the complexity of
discovery and data sharing. This abstraction captures the common usage
of neighborhoods in many publicly available sensor network applications,
and was used to implement some of TinyOS's largest applications.
HotLeakage
A Software Model of Leakage
Kevin Skadron and Mircea Stan
home page of HotLeakage
otLeakage is a software model of leakage based on
BSIM3 technology data. It is publicly available on the web,
computationally very simple, can easily be integrated into popular
power-performance simulators like Wattch, can easily be extended to
accommodate other technology models, and can easily be used to model
leakage in a variety of structures (including caches, among others). It
extends the Butts-Sohi model and corrects several important sources of
inaccuracy. Our model is called HotLeakage because it includes the
exponential effects of temperature on leakage. Temperature effects are
important, because leakage current depends exponentially on temperature,
and future operating temperatures may exceed 100 degree C. HotLeakage
also includes the heretofore unmodeled effects of supply voltage, gate
leakage, and parameter variations. HotLeakage has circuit-level
accuracy because the parameters are derived from transistor-level
simulation (Cadence tools). Yet like simplicity is maintained by
deriving the necessary circuit-level model for individual cells, like
memory cells or decoder circuits, and then taking advantage of the
regularity of major structures to develop abstract models that can be
expressed in simple formulas similar to the Butts-Sohi model.
HotSpot
An Accurate and Fast Architectural Thermal Model
Kevin Skadron and Mircea Stan
home page of HotSpot
ith power density and hence cooling costs rising
exponentially, temperature-aware design has become a necessity.
Processor packaging is becoming a major expense, and for many chips can
no longer be designed for the worst case. Furthermore, simple estimates
of power dissipation are not a good proxy for direct measurement or
simulation of temperature. HotSpot is an accurate and fast thermal
model suitable for use in architectural studies. It is based on an
equivalent circuit of thermal resistances and capacitances that
correspond to microarchitecture blocks and essential aspects of the
thermal package. The model has been validated using finite element
simulation. HotSpot has a simple set of interfaces and hence can be
integrated with most power-performance simulators. The chief advantage
of HotSpot is that it is compatible with the kinds of power/performance
models used in the computer-architecture community, requiring no
detailed design or synthesis description. HotSpot makes it possible to
study thermal evolution over long periods of real, full-length
applications.
IPA
Inexpensive Program Analysis
David Evans
home page of IPA
espite considerable progress in program analysis
tools, typical software development processes make little use of
advanced analysis techniques, even when they are producing mission
critical software. Our group is exploring analysis approaches that
combine dynamic and static analysis techniques. We co-organized the
Workshop on Dynamic Analysis (25 May 2004 at ICSE). Software we
produced includes Splint, a tool for statically checking C programs for
security vulnerabilities and coding mistakes, and Perracotta, a dynamic
analysis tool for automatically inferring temporal properties of a
target program. With minimal effort, Splint can be used as a better
lint. If additional effort is invested adding annotations to programs,
Splint can perform stronger checking than can be done by any standard
lint. Perracotta takes the program's execution traces as input and
outputs a set of likely temporal properties. The properties can enhance
program understanding, be used to aid program evolution, or be used as
input properties for a model checker. We have investigated the mining
of temporal API rules from imperfect traces, the automatic inference of
temporal program properties, differential program analysis, statically
detecting likely buffer overflow vulnerabilities and dynamic memory
errors, and program evolution.
Info Tech
Information Technology for Mobile and Web Based Systems
Sang Son
home page of Info Tech
s computer technology becomes more integrated into
society, information management for human activities necessitates
computing that responds to requests in real-time. Many information
systems are now used to monitor and control appliances as well as large
complex systems which must have predictable and timely
behaviors. Millions of users will soon be carrying mobile computers that
access the Internet wirelessly. To support those users in applications
such as web-based information systems, e-commerce, and Internet
appliances, providing consistent data and transaction services in
real-time with acceptable quality and security will be a key
requirement. This project aims to design and evaluate models and
methodologies for developing robust and responsive information systems
for those new applications. Current research issues include timeliness
and predictability, adaptive QoS management, flexible security
paradigms, data consistency in mobile environments, and applying
real-time and information technology in web-based systems.
Intrusion Detection
Application Intrusion Detection Systems
Anita Jones
home page of Intrusion Detection
ince 1980, the intrusion detection community has
divided intruders into two categories (internal and external) based on
the intruder's access to a system. The proliferation of distributed
systems with complex networks has necessitated a reexamination of
intruder definitions. We defined a new category, the pseudo-internal
intruder. This new category encompasses intruders without user accounts
who circumvent the perimeter defenses of a modern distributed system and
attack the system via its network. Intrusion detection has
traditionally been performed at the operating system (OS) level, but OS
intrusion detection systems (IDS) are frequently insufficient to catch
internal intruders. We hypothesized that application specific IDS
(AppIDS) could use the semantics of the application to detect more
subtle, stealth-like attacks such as those carried out by internal
intruders. We developed two extensive case studies to explore what
opportunities exist for detecting intrusions at the application level,
how effectively an AppIDS can detect the intrusions, and the possibility
of cooperation between an AppIDS and an OS IDS to detect intrusions.
AppIDS can detect some intrusions that an OS IDS cannot thus increasing
the overall effectiveness in detecting intrusions.
Isoluminance
Isoluminant Color Selection for Non-Photorealistic Rendering
Jason Lawrence
home page of Isoluminance
e developed a color selection algorithm for
non-photorealistic rendering applications. The human visual system
processes luminance information in a scene separately from its
chrominance. By using colors that have similar luminance but vary in
color, skilled artists have exploited this property in order to create
perceptual tension in their work. We presented a method for
automatically selecting colors that exhibit this isoluminance property.
We apply this color selection algorithm to both existing and novel
non-photorealistic rendering image filters. We introduced a modified
pointillist and image-mosaic filter along with a new image filter
inspired by the work of the modern artist Chuck Close.
Isotach
Concurrency control without locks or barriers
Paul Reynolds
home page of Isotach
sotach systems are distributed or parallel computer
systems with special support for interprocess coordination. Isotach
systems provide low cost ordered message delivery distributed databases,
cache coherence in multiprocessors, distributed shared memory, parallel
production systems, and distributed control systems. Isotach systems
also provide support for fault-detection and check pointing. Isotach
systems provide these benefits by maintaining a logical time system that
enables processes to predict and control the logical time at which its
messages are received. This control is a powerful mechanism for
interprocess coordination in a parallel or distributed computation.
Jazz
Demand-Driven Structural Testing with Dynamic Instrumentation
Mary Lou Soffa
home page of Jazz
roducing reliable and robust software has become one
of the most important software development concerns in recent years.
Testing is a process by which software quality can be assured through
the collection of information. While testing can improve software
reliability, current tools typically are inflexible and have high
overheads, making it challenging to test large software projects. Jazz
is a new scalable and flexible framework for testing programs with a
novel demand-driven approach based on execution paths to implement test
coverage. This technique uses dynamic instrumentation on the binary
code that can be inserted and removed on-the-fly to keep performance and
memory overheads low. The Jazz software testing tool can do def-use,
branch, and node coverage tests in the Jikes Java research virtual
machine and just-in-time compiler. Jazz is a new and improved
implementation of the SoftTest framework.
JDelta
Testbed for Delta Compression Algorithms in Diverse Environments
Alfred Weaver
home page of JDelta
elta compression is the process of comparing two
files to produce a set of instructions that will convert one file into
the other. Storing or transmitting a delta file rather than the entire
new file can offer significant efficiency gains. However, the different
aspects of delta compression efficiency, like many problems in computer
science, can rest at different ends of a balance. There does not exist
a single delta compression algorithm that performs the best in every
environment because performance requirements may vary. In order for a
user of delta compression to choose the best algorithm for his
situation, he must have some understanding of the strengths and
weaknesses of the various delta compression algorithms available to him.
JDelta, a Java-based delta compression utility, has been designed and
implemented to both aid in this understanding, and to provide a
framework for the future development of new delta compression
techniques.
LAVA
Laboratory for Computer Architecture at Virginia
Kevin Skadron
home page of LAVA
rchitectural innovation is vital to continued
improvement in processor performance. Key to this is exploiting
instruction-level parallelism (ILP). Among the most important levers
are better branch prediction, more efficient memory hierarchies, and
better compilation. Unfortunately, most approaches entail substantial
complexity, usually at the cost of die size, power consumption, and
longer development times. Even in high-performance processors, these
problems constrain architectural innovations, and they are especially
important for embedded environments like hand-held devices. Reducing
complexity is therefore an important research question in its own right.
The LAVA group is exploring all these issues, especially branch
prediction, architecture/compiler synergies, and architecture for
embedded environments. Collaborating institutions include Princeton, U-Mass, and Utah. Because simulation is so
important to our work, the LAVA group is also exploring new ways to make
simulations fast and accurate. The LAVA Lab contains a large
suite of fast PCs for simulation-based architectural and
microarchitectural studies. For especially large projects, the LAVA
computers can be used in conjunction with the powerful Centurion system
operated by the Legion
project. We also have the opportunity to build real systems in
conjunction with the computer
engineering faculty and The
Center For Semicustom Integrated Systems.
Legion
World-Wide Virtual Computer
Andrew Grimshaw
home page of Legion
egion is an object-based, meta-systems software
project at the University of
Virginia. From the project's beginning in late 1993, the goal of
the Legion Group has been to create a highly usable, efficient, and
scalable system founded on solid principles. We have been guided by our
own work in object-oriented parallel processing, distributed computing,
and security, as well as by decades of research in distributed computing
systems. Our system addresses key issues such as scalability,
programming ease, fault tolerance, security, site autonomy, etc. Legion
is designed to support large degrees of parallelism in application code
and manage the complexities of the physical system for the user. The
first public release was made at Supercomputing '97, San Jose,
California, on November 17, 1997. Legion is an "open" system that has
been designed to allow and encourage third party development of
applications, run-time library implementations, and "core" system
components.
Lithium
Visualizing Competitive Behaviors in Multi-User Virtual Environments
Greg Humphreys
home page of Lithium
ithium is a system for enhancing observation of user
interactions in virtual environments. In particular, we focus on
analyzing behavior patterns in the popular team-based first-person
perspective game Return to Castle Wolfenstein: Enemy Territory. This
game belongs to a genre characterized by two moderate-sized teams
(usually 6 to 12 players each) competing over a set of objectives.
Lithium allows spectators to visualize global features, as opposed to
the limited local view that traditional spectating modes provide. We
also add overlay visualizations of semantic information related to the
action that might be important to a spectator in order to reduce the
information overload that plagues traditional overview visualizations.
These overlays can visualize non-obvious information such as player
distribution over time and areas of intense combat activity, and also
highlight important features like player paths, fire coverage, etc.
This added information allows spectators to identify important game
events more easily and reveals large-scale player behaviors that might
otherwise be overlooked.
Marionette
Embedded Wireless Debugging
Kamin Whitehouse
home page of Marionette
main challenge to developing applications for
wireless embedded systems is the lack of run-time visibility and
control. We developed a tool suite called Marionette which provides an
interpreter through which the network operator can remotely call the
node's functions, read and write its variables, and access its
enumerations and data structures. This interactive and scriptable
environment allows the developer to seamlessly trade off between between
writing application logic on the PC for simplicity and debugging or
writing it on the nodes for increased efficiency. This greatly eases
the development process, and was shown to reduce code size in existing
applications by up to 75%. Marionette is actively being used for
development on several testbeds of up to several hundred nodes.
Marionette builds upon earlier work on the Matlab/TinyOS development
environment, which has been in the main TinyOS distribution for years.
MaSTRI
Modeling and Simulation Technology Research Initiative
Paul Reynolds and David Brogan
home page of MaSTRI
he focus of the MaSTRI Project is the solution of
critical challenges that have inhibited or prevented the use of modeling
and simulation technology in otherwise practical settings. Critical
challenges include simulation reuse, multi-resolution modeling,
composability, interoperability, visualization, behavioral modeling and
integration of modeling and simulation (M&S) into training and
education. Our research is focused on the areas of simulation coercion
and simulation coercibility, which we collectively refer to as
COERCE. We observe that COERCE has direct application to the challenges
of simulation reuse and composability. COERCE can minimize problems
caused by differences between models of the same phenomenon at different
levels of resolution. In the area of simulation composability, COERCE
has the potential to increase flexibility of the components comprising a
simulation. So far, we have experienced considerable success in
coercing individual simulations that were not designed to be coerced,
and we are exploring how simulation coercion can become more automated
and be facilitated by developing simulations with the specific objective
of coercibility.
Medical Portal
Advancing Cyber Security with .NET
Alfred Weaver
home page of Medical Portal
he rapid worldwide deployment of the Internet and Web
is the enabler of a new generation of e-healthcare applications, but the
provision of a security architecture that can ensure the privacy and
security of sensitive healthcare data is still an open question. We are
using a web services approach to solve this problem. We authenticate
users using a variety of biometric (fingerprint, iris scan, signature
recognition) and digital (e-token, RFID, PIN generators) approaches; we
generate custom authentication tokens that provide not only
identification information but also a qualitative measure of the
trustworthiness of the identification technology. We built an
authorization rule engine that dynamically enforces data access
rights. We use strong encryption on all data transmissions (e.g.,
electronic prescriptions). Our current research challenge is in devising
ways to share trust across organizational boundaries; we are currently
experimenting with trust groups, attribute servers, and token exchange
servers are possible solutions.
MRRL
Memory Reference Reuse Latency
Kevin Skadron
home page of MRRL
emory Reference Reuse Latency (MRRL) is the distance
(in completed instructions) between consecutive references to some
memory location. By measuring the reuse latencies of each unique
address accessed by a benchmark, we are able to select a point to begin
cache and branch predictor warm up prior to each simulation sample
cluster. Cache and branch predictor warm up assures accurate simulation;
our delayed warm up technique achieves accurate simulation in less time
than modeling all cache and branch predictor interactions prior to each
sample cluster. MRRL works very well for sampled simulations, because
MRRL-driven warm up eliminates nonsampling bias just as well as
fullwarmup which models all pre-cluster instructions. MRRL exploits
temporal locality by modeling only those interactions that occur nearest
to the clusters, that are most likely to be relevant to the simulation
of the clusters, which gives MRRL its speed advantage.
Mutation Routing
Mobile-to-Mobile Routing in Distributed Applications
Kamin Whitehouse
home page of Mutation Routing
ne of the biggest challenges in a distributed
tracking application such as the Pursuer-Evader Game (PEG) is
mobile-mobile routing: routing from a source node to a destination while
both are changing location in the network topology. Mutation Routing is
an algorithm that finds a route once and then mutates it when nodes
move. The algorithm can be proven never to mutate to an inconsistent
state and, because mutation eliminates the need for control message and
new route discovery overhead, it increases the overall bandwidth on the
route. One disadvantage to this algorithm, however, is that routes can
mutate to sub-optimal, snake-like patterns. Mutation routing therefore
trades energy-efficiency and latency for higher bandwidth and
lightweight route maintenance. Our work investigates hybrid routing
algorithms that can choose the ideal operating point in this tradeoff.
NAE
National Academy of Engineering - "Telling Truth to Power"
William Wulf
home page of NAE
ne of our faculty members, William Wulf, is currently
President of the National Academy of
Engineering, and vice chair of the National Research Council, the
principal operating arm of the National Academies of Sciences and
Engineering. Founded in 1964, the National Academy of Engineering (NAE)
provides engineering leadership and research advice in service to the
nation, the public, and the scientific and engineering communities. The
NAE operates under the same congressional act of incorporation that
established the National Academy of
Sciences, signed in 1863 by President Lincoln. Under this charter
the NAE is directed "whenever called upon by any department or agency of
the government, to investigate, examine, experiment, and report upon any
subject of science or art." The NAE is a private, independent,
nonprofit institution. In addition to its role as advisor to the federal
government, the NAE also conducts independent studies to examine
important topics in engineering and technology. The NAE has more than
2,000 peer-elected members and foreign associates, senior professionals
in business, academia, and government who are among the world's most
accomplished engineers. They provide the leadership and expertise for
numerous projects focused on the relationships between engineering,
technology, and the quality of life.
Nancy's Pantry
Bringing Printed Materials to the Visually Impaired
Paul Reynolds
home page of Nancy's Pantry
onsider what it must be like to order a meal if you
can't read the menu. Or to learn the amount of your latest utility
bill. Or to select a can of your favorite soup off the shelf in your
pantry. If you're visually impaired, there's no affordable technology
in the marketplace to support you. However, the enabling technology
does exist! Project Nancy's Pantry is about bringing low cost access to
common, everyday printed materials: menus, soup cans, utility bills, bus
schedules, clothing -- the list really is nearly endless. A key
Requirement is low-cost production and low-cost use. We're exploring a
two-part technology. Our production technology of choice is a 2D (two
dimensional) barcode. Currently we're using pdf417 bar code, and the
web technology XML. Using a laser or optical scanner similar to the
checkout at most retailers, we can scan the barcodes and convert them to
a computer processable form. Our user technology of choice is a low
cost flexible processor, such as a PDA. Any device capable of general
purpose processing, and generation of audio, is sufficient. Ultimately
we envision a single PDA-like device that incorporates either laser or
optical scanning, and general purpose processing. Such devices exist in
a limited part of the commercial sector. We aim to bring them into the
consumer sector.
NEST
Networked Embedded Systems Technology for Wireless Sensor Networks
Jack Stankovic, Tarek Abdelzaher, Sang Son and Gang Tao
home page of NEST
ireless sensor networks have emerged as a new
information gathering paradigm based on the decentralized collaboration
of a large number of sensing/computation/actuation nodes. This project
develops middleware and programming paradigms for wireless sensor
networks. We have key innovations in real-time routing, packet
aggregation, localization, asynchronous multicast, power management,
group management and programming paradigms. Work is continuing in all
these areas as well as on new topics including wireless sensor network
event services, swarm computing, extreme scaling and robustness. Our
work utilizes both simulation and a physical testbed of 120 Berkeley
motes. This project is funded by DARPA, a MURI and NSF.
N-Variant Systems Framework
Software System Protection Framework
John Knight, David Evans, Jack Davidson, Anh Nguyen-Tuong and Jonathan Rowanhill
home page of N-Variant Systems Framework
e propose a new approach to software service
protection that is based on software system structures which combine
monitoring software and tailored program diversity. The resulting
systems have two valuable properties that cannot be achieved with
previous vulnerability-masking approaches: (1) their effectiveness does
not depend on keeping secrets from adversaries; and (2) we can construct
proofs that a system cannot be compromised by a class of attacks, no
matter what vulnerabilities exist in the server program. The first
property means that adversaries can have complete knowledge about the
structure and software of our systems without compromising their
security. Thus, insider snooping cannot defeat our vulnerability
protection against outsider initiated attacks, and probing or guessing
attacks that have been shown effective against previously proposed
diversity techniques pose no threat to our system. The second property
means that there can be a high level of assurance in the coverage of
vulnerabilities in the system based on formal arguments and depend only
on clearly stated assumptions about components of our system structure,
but place no constraints on properties of the protected software
service. An instantiation of our idea is the N-Variant System
Framework, which provides a general mechanism for detecting and
preventing classes of attacks on vulnerable servers. Our approach
provides provable security that does not rely on secrets.
PDO
Profit-Driven Optimization
Mary Lou Soffa
home page of PDO
lthough optimizations have been applied for a number
of years to improve the performance of software, problems that have been
long-standing remain, which include knowing what optimizations to apply
and how to apply them. To systematically tackle these problems, we need
to understand the properties of optimizations. In our current research,
we are investigating the profitability property, which is useful for
determining the benefit of applying an optimization. Due to the high
cost of applying optimizations and then experimentally evaluating their
profitability, we use an analytic model framework for predicting the
profitability of optimizations. We target both loop and scalar
optimizations. In particular, we have described framework instances for
several classic loop optimizations. More recently, we have developed
framework instances for scalar optimizations, such as Partial Redundancy
Elimination (PRE) and Loop Invariant Code Motion (LICM). We have
implemented our framework in the MachSUIF compiler to explore the
effectiveness our analytic models. Experiments with both loop and scalar
optimizations shows that the approach can very accurately predict the
profitability of optimizations, with low compile-time overhead. By
predicting the profitability using models, we can selectively apply
optimizations. The model-based approach does not require tuning of
parameters used in heuristic approaches and works well across different
code contexts and optimizations.
Perracotta
Program Dynamic Temporal Analysis
David Evans
home page of Perracotta
erracotta is a dynamic analysis tool for
automatically inferring temporal properties of a target program. It
takes the program's execution traces as input and outputs a set of
temporal properties it likely has. We address several key challenges to
make our dynamic analysis effective. First, we propose a hierarchy of
templates to capture commonly occurred properties. Perracotta uses a
scalable statistical inference algorithm that can handle imperfect
traces, several heuristics for selecting interesting temporal
properties, and a chaining method for constructing larger finite state
machines out of a group of small ones. To evaluate whether such
property patterns are useful, we apply Perracotta to help program
evolution by inferring temporal properties for several versions of a
program, then compare the inferred properties across versions. We also
use Perracotta to support program verification. We applied Perracotta
to infer temporal rules for the Microsoft Windows kernel APIs, and found
numerous previously undetected bugs in Windows.
Perspective Warp
Improved Two-Pass Resampling Algorithms
Jason Lawrence
home page of Perspective Warp
rom classical texture mapping to photo-mosaics,
warping images according to a perspective projection is a key operation
in many computer graphics algorithms. Working with Microsoft's Graphics
Device Interface (GDI+) group, we implemented Catmull and Smith's
two-pass resampling algorithm that computes perspective projections of
images in scanline order. Although they present an elegant technique
for decomposing a general perspective transformation into two simplified
1d reconstruction passes, their approach is limited by how the algorithm
selects the order of these passes. We better quantified the types of
errors present in this decomposition, and demonstrated that in many
important cases, using our new selection criteria improves the output
image quality.
Physicrypt
Physical Cryptography and Security
David Evans
home page of Physicrypt
omputing is moving into the real world. Instead of
performing computations in protected beige boxes with narrow interfaces
to the real world, the majority of future computing will be done by
devices (such as nodes in sensor networks) that interact with the real
world in rich and dynamic ways. Our research explores how this trend
impacts security. We consider ways to use properties of the physical
world in which computing devices are deployed to improve security. A
related project, Swarm Computing, considers how the new computing
environment impacts programming, and what biology can reach us about
security. We have explored topics such as .NET security and the lessons
learned and missed from Java, mobile sensor networks, using directional
antennas to prevent wormhole attacks, the perception and reality of
election security, authentication for remote voting, secure aggregation
for wireless networks, and security issues and requirements for
Internet-scale publish-subscribe systems.
PIE
Personalized Information Environments
James French and Andrew Grimshaw
home page of PIE
he number and volume of information resources is
enormous and growing exponentially. The level of care taken in the
preparation of information for on-line publication varies greatly.
Access to the information is often poor and even awareness of the
existence of specific data is becoming increasingly difficult.
Organizational strategies provided by information publishers are
publisher-centric or designed to meet the needs of a specific user
group. Tools are needed that will enable users to create personal
collections of information resources of interest to them. It will be
necessary to cull tens of thousands of resources for those of specific
interest; it will also be necessary to continuously monitor available
resources to detect new useful sources or to decide that others are no
longer of interest. Efficient search strategies are required to support
the discovery of resources and to search and fuse information gleaned
from those resources. We are developing new techniques aimed at
constructing a user-customized Personalized Information Environment
(PIE) that can be tailored to the needs of specific users. The
techniques developed will be based on: distributed search over
restricted search spaces; virtual information repositories; and a novel
system architecture. In addition to user control over information
access, our architecture provides for user anonymity and secure access
to resources.
PRMES
Profit and Resource Management for Embedded Systems
Mary Lou Soffa
home page of PRMES
ontinuous Compilation has a number of benefits and
uses for embedded software. It is particularly well suited for enabling
software malleability, meeting multiple design constraints that change
at run-time, and managing system resources. In this sub-project, we are
developing novel solutions to these problems and applying our work with
Continuous Compilation to embedded software. We are developing novel
analytic models of machine resources, code optimizations, and program
code that can be used to better meet performance/cost goals for embedded
systems. The models can be used to quickly explore different
optimization decisions (e.g., optimization configuration, interactions,
etc.) to select the optimizations that best meet an objective function.
Unlike other work, such as iterative compilation and experimentally
based searches, our approach does not require execution feedback to
evaluate whether an optimization is beneficial. Hence, the approach is
extremely fast and can determine the benefit of an optimization much
quicker than existing approaches. Dynamic code translation can be used
to effectively manage embedded system resources. We have developed
techniques for instruction code compression/decompression in a purely
software based framework. Such an approach is more flexible than a
hardware based solution because it allows the compressor and
decompressor to be changed. Unlike other software approaches, our
technique decompresses only instructions that are very likely to
execute, which helps to reduce the run-time overhead of
decompression. We have developed a technique, called partial image
compression, that substantially reduces code image size using only a
modest run-time decompression overhead.
Qsilver
Flexible Simulation Framework for Graphics Architectures
Kevin Skadron and David Luebke
home page of Qsilver
Silver is a multipurpose tool for analysis of the
performance characteristics of computer graphics hardware and software.
Qsilver is a highly configurable micro-architectural simulator of the
GPU that uses the Chromium system's ability to intercept and redirect an
OpenGL stream. The simulator produces an annotated trace of graphics
commands using Chromium, then runs the trace through a cycle-timer model
to evaluate time-dependent behaviors of the various functional units.
Qsilver can be used to analyze performance bottlenecks in existing
architecture, to explore new GPU microarchitectures, and to model power
and leakage properties. One innovation of this tool is the use of
dynamic voltage scaling across multiple clock domains to achieve
significant energy savings at almost negligible performance cost.
Semantic Streams
A Framework for Composable Semantic Interpretation of Sensor Data
Kamin Whitehouse
home page of Semantic Streams
ne of the largest remaining obstacles to the
widespread use of sensor networks is the interpretation of the sensor
data; users must be able to query for high-level facts about the world,
not just raw ADC readings. Our Semantic Streams framework allows users
to pose declarative queries for semantic values, such as "the speeds of
vehicles near the entrance of the parking garage." The system combines
logical inference with AI planning techniques to compose a sequence of
inference units, which are stream operators that perform a minimal
amount of sensor fusion or interpretation on incoming event streams and
incorporate newly inferred semantic values into outgoing event streams.
Both the sensor network and the inference units are logically described
in Prolog and the system can reason about which sensors to use and
whether the inference units are being used in an appropriate world
context. Typically, multiple combinations of sensors and inference
units can answer the same query, so users can also declare QoS
constraints in CLP(R) notation to choose between logically equivalent
inference graphs, e.g., "the confidence of the speed estimates should be
greater than 90%" or "I want to minimize the total number of radio
messages".
Software Quality
Reliability and Error-Prevention
Westley Weimer
home page of Software Quality
ur research interests lie in advancing software
quality by using both static and dynamic programming language
approaches. We are particularly concerned with automatic or
minimally-guided techniques that can scale and be applied easily to
large, existing programs. We believe that finding bugs is insufficient,
and we also work to help programmers address defects and understand
error reports. We are also interested in designing languages and
language features to help prevent errors. We use concepts from other
areas of computer science to help address software quality problems, and
succeeded in combining elements of databases, systems, and machine
learning. We add programming language support for more robust
error-handling via first-class compensation stacks. It also uses
specification mining techniques to automatically infer important
resources and safety policies in the presence of run-time errors.
STILT
System for Terrorism Intervention and Large-scale Teamwork
John Knight, David Evans and Jack Davidson
home page of STILT
n the event of an attack or disaster, the
effectiveness of communication will have great impact on effectiveness
of response. Information, such as what areas have been affected and the
level of damage, must be quickly distributed to the people and systems
who will then use it to formulate effective response. All individuals
that will enact this response must then be notified quickly that the
event has occurred and directed as to the action (or inaction) they must
take. Feedback is then collected from the responders to assess the
implementation of response. This type of control loop is currently
difficult to enact even within a single jurisdiction, and nearly
infeasible at the regional or national scale. The intent of our System
for Terrorism Intervention and Large-scale Teamwork (STILT) is to
provide a mechanism for enacting such a control loop. The system is
primarily focused around detecting and responding to
geographically-distributed, coordinated terrorist attacks. However, the
system is general enough that it can be applied to any emergency
response situation. Our central premise is that a system that can
correlate distributed attacks and precisely target response commands and
information to relevant parties will help prevent subsequent attacks,
decrease the impact of successful subsequent attacks, and increase
response effectiveness.
Strata
A Reconfigurable and Retargetable Software Dynamic Translator
Mary Lou Soffa
home page of Strata
espite the many uses of software dynamic translation
and the lively state of research on SDT, building SDT systems remains a
significant challenge. In this project, to address the difficulty of
building software dynamic translators and to promote research into novel
uses of SDT. We are developing an SDT implementation infrastructure
called Strata. Strata provides a common framework in which researchers
can build dynamic translators. Strata uses several novel techniques to
reduce the cost of dynamic code translation, including partial inlining,
indirect branch translation caching, fast returns, instruction trace
formation, and fragment linking. To gather run-time information, Strata
has facilities for dynamic instrumentation. Because instrumentation can
be very expensive, Strata uses several novel optimizations that target
instrumentation overhead, including instrumentation probe coalescing,
partial context switches, code specialization and payload partial
inlining.
Surface Deformations
A Painting Interface for Geometric Modeling
Jason Lawrence
home page of Surface Deformations
esigning effective user interfaces for modeling 3d
geometry has been a longstanding challenge in computer graphics. This
task is complicated by the fact that we often attempt to specify 3d
positions and directions with purely 2d input devices. To address this
challenge, we developed a modeling interface that combines interactive
manipulation and physical simulation. Instead of modifying the surface
directly, the user specifies physical properties of the surface (i.e
velocity) using a 3d painting interface. The user then interactively
simulates the resulting surface motion until the desired deformation is
achieved. Our work enabled the creation of several models using this
interface, and was honored with a best paper award.
TDB
A Transparent Debugger for Dynamically Translated Code
Mary Lou Soffa
home page of TDB
oftware dynamic translation (SDT) has received much
attention due to compelling applications of the technology, including
software security checking, binary translation, and dynamic
optimization. In this project, we are developing new debugging
techniques for applications executing with SDTs. Our techniques use
novel dynamic code mappings to create the illusion that the source
program is being debugged, while allow the SDT system to modify the
executing code. We are targeting a number of SDT applications,
including dynamic binary translation, dynamic code optimization, code
security checking, reliable software systems, computer architecture
simulation, and dynamic instrumentation. We have built a prototype
debugger, called TDB, that integrates a SDT system, Strata, with a
widely used debugger, gdb. Our prototype can handle many types of code
modifications applied by SDTs, including the basic translations applied,
overhead reduction transformations, and dynamic instrumentation. The
basic dynamic translations include generating a new instruction,
inserting multiple instructions for a single program statement during
translation, ignoring and not generating instructions for a program
statement, deletion (flushing) of previously translated instructions,
and the duplication of program instructions in the translated code. We
are also considering several overhead reduction transformations,
including instruction trace formation, conditional branch linking,
indirect branch translation caching, partial inlining of unconditional
branches and calls, and fast return handling. Finally, we are
considering the effect of insertion and removal of instrumentation in
the translated code.
TJC
Scalable Robust Visualization of Large Trees
Greg Humphreys
home page of TJC
he TreeJuxtaposer system allowed visual comparison of
large trees with guaranteed visibility of landmarks and Focus+Context
navigation. While that system allowed exploration and comparison of
larger datasets than previous work, it was limited to a single tree of
775,000 nodes by a large memory footprint. In this project, we designed
and implemented two scalable, robust solutions to these limitations: TJC
and TJC-Q. TJC is a system that supports browsing trees up to 15 million
nodes by exploiting leading-edge graphics hardware while TJC-Q allows
browsing trees up to 5 million nodes on commodity platforms. Both of
these systems use a fast new algorithm for drawing and culling and
benefit from a complete redesign of all data structures for more
efficient memory usage and reduced preprocessing time.
Tortola
Hardware-Software Symbiosis
Kim Hazelwood and Greg Humphreys
home page of Tortola
odern computer systems designers must consider many
more factors than just raw performance. Thermal output, power
consumption, reliability, testing, and security are quickly becoming
first-order concerns. Until recently, the vast majority of research
efforts in optimizing computer systems have targeted a single logical
"layer" in isolation: application code, operating systems, virtual
machines, microarchitecture, or circuits. However, we feel that we are
reaching the limits of the solutions than we can provide by targeting a
single layer in isolation. We also feel that there is an important class
of computing challenges that is better suited for more holistic
approaches. The Tortola project is exploring of a symbiotic relationship
between a virtual machine and the host microarchitecture to solve future
challenges in the areas of power, reliability, security, and
performance. In general, we attack challenges that would work well using
more "reactive" techniques, whereby the hardware can detect a problem,
and the virtual machine can use its global knowledge about the program
to correct the problem.
VCGR
Virginia Center for Grid Research
Andrew Grimshaw
home page of VCGR
he Virginia Center for Grid Research is dedicated to
performing research and solving issues surrounding the operation,
deployment, and use of large distributed data and computing systems.
Our overriding objective is to advance the science and application of
grid computing so that it is more useful and readily available to those
end users that can benefit from its power. Our goal is not to simply
solve a few pieces of the overall grid computing puzzle (which is an
important, part to be sure), but to also promote the use of grid
computing systems to improve the capabilities of other areas of science
and to perform research and share information and ideas. The scope of
our charter covers a wide spectrum of activities including pure computer
science/engineering research, grid system development and deployment,
grid research community interaction, development of standards, and end
user collaboration and outreach. We have created the Global Bio Grid
(GBG) to facilitate several research efforts in the biological and
medical fields at various institutions. We plan to identify and solve
key research issues; demonstrate, evangelize, and educate user
communities on the usefulness of grid systems; improve the ease of use
of systems and work with end users and solicit their feedback; and
increase the reach of grid systems.
VEST
Virginia Embedded Systems Toolkit
Jack Stankovic
home page of VEST
EST (Virginia Embedded Systems Toolkit) is an
integrated environment for constructing and analyzing component based
embedded and real-time systems. Generally speaking, the VEST
environment is designed to help designers select or create passive
components (collection of functions, classes, HW, etc), compose them
into a system/product, map the passive components onto runtime (active)
structures such as threads, map threads onto specific hardware, and
perform dependency checks and non-functional analyzes to offer as many
guarantees as possible along many dimensions including real-time
performance, and reliability.
VLSI CAD
Physical Design and Layout
James Cohoon and Gabriel Robins
home page of VLSI CAD
ecent trends in deep-submicron Very Large Scale
Integrated (VLSI) circuit technology have resulted in new requirements
for circuit layout algorithms. Much of our research centers on new
formulations which capture performance and density criteria in
computer-aided design (CAD). Our results include near-optimal
approximation algorithms for computationally intractable problems as
minimum-cost Steiner tree routing, low-skew clock routing, cost-radius
tradeoffs, bounded-density trees, circuit probe testing, Elmore-based
routing constructions, multi-port terminal routing, and new metal-fill
formulations for manufacturing yield enhancement. Our methods address
not only traditional and leading-edge integrated circuit technologies,
but also newer design styles such as field-programmable gate arrays
(FPGAs) and multi-chip modules. We are also investigating other topics
in discrete algorithms, combinatorial optimization, and computational
geometry.
Willow
Survivability Architecture for Information Systems
John Knight
home page of Willow
he Willow system is designed to support the
survivability of large distributed information systems. As part of its
approach, Willow deals broadly with their faults, applying fault
avoidance by disabling vulnerable network elements intentionally when a
threat is detected or predicted, fault elimination by replacing system
software elements when faults are discovered, and fault tolerance by
reconfiguring the system if non-maskable damage occurs. The reactive
component of Willow supplements the usual information system fabric with
a comprehensive fault-tolerance mechanism referred to as a survivability
architecture or information survivability control system. The key to the
architecture is a powerful reconfiguration mechanism that is combined
with a general control loop structure in which network state is sensed,
analyzed, and required changes effected. The main challenges Willow
overcomes are those of scalability and complexity.
WSN
Wireless Sensors Networks
Jack Stankovic and Sang Son
home page of WSN
t is now possible to develop large numbers of small
smart components that combine computing power, wireless communication
capabilities, and specialized sensors and actuators. These components
or nodes may be deployed in thousands to achieve a common mission. They
may be used to monitor poorly accessible or dangerous environments such
as the ocean floor, neighborhoods of volcanic activities, hostile
territories (e.g., behind enemy lines), disaster areas, and nuclearly
active fields. They may also be deployed to accomplish interactive
tasks such as finding and detonating enemy mines, looking for survivors
of natural disasters, or containing and isolating oil spills to protect
a nearby coastline. These wireless sensor devices are also useful for
environmental monitoring, medical applications and smart homes or
buildings. Our work includes developing MAC and routing layer
solutions, group management based on novel "enough" semantics, analysis
and implementation techniques for achieving aggregate behavior, novel
data services protocols including sensor net querying capabilities,
development of a sophisticated event service for WSN, protocols for
power management, protocols for computer security, and developing new
paradigms for sensor net programming. We are working with a testbed of
MICA and XSM motes to investigate detection, tracking and classification
with power management capabilities.