Research Summary: Update 8/2007
The focus of our research since my transition to
UCSD from
UCI in 2002 has been on issues related to synthesis and operational
efficiency in embedded systems. Continuing with that momentum we
completed
and released a set of tools within a parallelizing high-level
synthesis framework, called SPARK. To date, SPARK has seen
4000+
downloads and sports an active user community, including its
non-exclusive
license by UCSD. We also made limited
progress in formal capture and component compositions for system level
models
of embedded systems, their validation through formal verification and
multi-processor
simulations. Operational efficiency, measured in terms of energy
efficiency
across processing and communications was the centerpiece of work in our
published literature during this period. This included our work on
coordinated
multi-radio interfaces, best demonstration award for a radio platform
at the
IPSN conference, optimized slowdown/shutdown of processors and radios
on such
platforms.
Beginning 2006, our attention has shifted towards
exploration of
spatial things in embedded systems: use of location in
modeling,
programming and in improving operational efficiency (for computation,
energy). The focus of this effort is on the capture,
modeling and treatment of spatial information in embedded systems. The
overall vision is centered on enhancing the
scope of embedded systems design from real-time to real-location.
Currently, spatial reasoning in computing system is
primarily treated as nothing more than an expression of concurrency,
e.g., Pi
calculus and ambient logic. We believe we can go much further than the
confines
of what logical inferencing can do in concurrent programming.
Accordingly, we
have structured our research in this area along three lines:
Improved real-time localization: this work
currently
led by Thomas Weng is focused on improving the accuracy of
satellite-base localization to dm-scales in real-time through
innovations in
GPS augmentation by improve ephemeris, carrier-phase analyses. As a
proof of
concept Thomas is building an enhanced network-based localization
server (ENLS)
that leverages IPv6 for an improved infrastructure for infospatial
addressing
in embedded systems. This work straddles the boundary between GIS,
radio
communications and networking. We are working with researchers at MPL
and SOPAC
at SIO.
Improved use of real-space information in task
scheduling: this work led by Ryo Sugihara is focused on modeling
of spatial constraints, in the context of data collection by mobile
nodes in
sensor network applications, in optimizing operational efficiency in
embedded
systems.
Improved capture and use of spatial information
in
embedded programming: this is ongoing work in collaboration with
R. K.
Shyamsundar of IBM and TIFR and Amin Vahdat. As an exploration, Amin
and I
worked with Chalermak Intagonwiwat, to formulate the problem of
spatially-aware resource allocation and programming. Since that
collaboration,
my work has evolved into programming support for spatial operations: We
have worked on defining a new set of observables
related to spatial information (proximity, enclosure etc) that a
programmer
can use to model behaviors that evolve over space.
Research Summary: 2002
My research can be broadly classified into two categories: (a) those
relating to our work on design automation, algorithms and techniques
for efficient synthesis of digital circuits, system-on-a-chip and
embedded systems; and (b) those relating to work on system
architectures and design techniques. I have organized these endeavors
into close nit projects: BALBOA, SPARK, AMRM,
PADS and OSDPM. You can find a project to these project websites on my
home
page: http://www.ics.uci.edu/~rgupta
(the website is in transition to http://www-cse.ucsd.edu/~gupta
but most links must work).
Recent Research Accomplishments:
- Delayed Evaluated Expressions (DEE): One of the
problems in
modeling system-on-chip (SOC) is the efficiency of detailed design
descriptions as discrete-event models. Often such models are built
using languages such as VHDL or Verilog where detailed discrete-event
simulations are often bogged
down by excessive event handling. To address this issue, we developed a
method
to define event structures using functions that include an
handler
to allow a process or procedure to force evaluation of a function at a
later
time (related to the time of generation of event) without resorting to
interpretation
of signal assignments (as is commonly done in popular HDLs). This
allows
for specification of DES event systems without altering the semantics
of
the underlying language and results in significantly faster system
simulations.
The results of this research have been used to build the Scenic language
that was the precursor of the emerging SystemC standard (www.systemc.org). While SystemC
itself
is an ongoing OSCI effort, my research work in this area continues in
the
form of BALBOA project (http://www.ics.uci.edu/~balboa)
on the type inferencing and automatic wrapper generation techniques for
component
composition.
- Speculative Code Motions and other parallelizing code
transformations for improved high-level synthesis. This work is
detailed under the SPARK project
(http://www.ics.uci.edu/~spark).
While it builds upon ongoing themes (actually, really beaten up
problems)
in highlevel synthesis and compilers, we developed code transformation
and
motion techniques (and fit them into a flow) that aggressively
transform
the control-intensive (nested loops and conditionals) block
descriptions
into synthesized circuits that compare well to (really well designed)
circuits
blocks (at Intel). Here is an
example
design. This work also received a best
paper award.
- Timing analysis for process graphs: this was done under
RADHA
and RATAN projects where we developed techniques for efficient timing
constraint analysis (rate derivation and analysis) for embedded
systems. There are two
essential problems in doing this analysis: how does one estimate the
actual
time of execution of system parts (including software components) and
once
such an estimate is given, how does one determine if a given set of
constraints
are satisfied, and if these are not satisfied, what can a designer do
to
make this constraints satisfiable? There are two prominent results: (a)
computation
of a close bound on the average rate of execution for a process in a
network
of concurrently interacting processes; and (b) efficient algorithm for
MCM
computation using process graphs. The process model is very
general:
it allows both AND- and OR- causal dependencies between processes. This
work
allows the system designer to interactively specify constraints,
identify
and debug constraint violations. To help the designer eliminate
constraint
violations, the tool also identifies use of pipelined components based
on
the notion of critical cycles in the process graph. The
critical cycle
analysis is based on computation of maximum cycle-mean (MCM) from
the process graph. Since the timing analysis and constraint debugging
relies
heavily on the efficiency of the MCM computation, we have produced an
efficient
algorithm for this computation. The prior state-of-the-art in MCM
computation
was a version of the algorithm due to Karp published in 1978. The Dasdan-Gupta
algorithm improves the behavior of the algorithm from Theta(nm) to
linear
time for sparse graphs for the same space complexity using an unfolding
transformation on process graphs. This work was published in IEEE
Transactions on CAD in
October 1998 and has already led to incorporation of this algorithm in
a
range of very diverse applications such as iteration bound of a
data-flow graph for DSP, performance analysis of synchronous and
asynchronous systems.
- Performance Modeling of Dynamic Power Management in Embedded
Systems: recently we have been looking into quantitative measures
for determination of effectiveness of power management policies applied
in the embedded systems. It is often difficult to determine how good a
system level power management policy is without running a large number
of simulations across various usage
scenarios. We improved on competitive ratio bounds by developing
methods
to compute probabilistic CR bounds using computational learning
methods.
Based on these bounds, we developed the PLEA (probabilistic
lower
envelope algorithm) for DPM that has been implemented in real OS as a
new
service that enables scheduling in presence of multiple shutdown and
multiple
active states along with Dynamic Speed Scaling. This has been published
in
SODA and ACM TECS (upcoming).
- Adaptive Memory Hierarchy: we have architected,
designed and
built into working board-level platform an adaptive memory hierarchy
that
changes the choice of cache memory assists (caches, buffers), their
parameteric choices, cache memory configuration and policies
(replacement) based on an
application behavior. Details on this project are available on the AMRM
website
(http://www.ics.uci.edu/~amrm).
One interesting aspect of this adaptation is that we have demonstrated
that
adaptation actually simplified memory system architecture (by replacing
a
large number of bells and whistles in a traditional cache memory). Ask
us
about it!
Research Leadership:
Pointers