Research activities
My research interest in general lies in applying mathematical theories
to the design of modern electronic and optical systems. My Ph.D work
is in logic design and synthesis for mixed hardware and software
systems. Below are the descriptions of a few research areas studied and
progress made.
Projects involved currently and in the past:
We believe the future of embedded system design lies in software, with
a platform-based design methodology based on two premises:
- using
standardized and domain specific architecture platforms to enable
hardware reuse and programmability;
- raising the abstraction level
of software designs with implementation code automatically generated
from application specific functional models.
By using standardized processors and moving intellectual properties
into software design, the methodology reduces hardware manufacturing
cost, increases flexibility of the design, and hence extends product
life cycle, and shortens time-to-market. However, software design in
such systems becomes extremely complex. High-level programming
paradigms using application specific functional models tackle this
problem by abstracting away implementation details. Our research
analyzes the problem of generating efficient implementation code from
computation models of a particular application domain.
We focus on control intensive embedded systems, for instance,
automobile engine, airplane, and network protocol controls. The
computation model used is a network of extended finite state machines
(EFSMs). An EFSM is a system with a finite state controller
interacting with an unbounded integer data-path. Each transition of
the controller is guarded by a predicate over the integer variables,
and is associated with an action function which updates the values of
the integer variables. High-level synchronous languages like Esterel,
StateFlow from Mathworks, or Statemate from I-Logix, can be used to
program in such models.
Our research is on the optimization of such EFSM networks for
software implementation on general purpose and application specific
architecture platforms. This includes sequential architecture
independent functional optimization, automatic code generation and
architectural support for efficient execution.
- High-level modeling and specifications
A number of high-level specifications languages have synchronous
semantics, and therefore can be modeled as communicating EFSMs,
e.g. Esterel, Mathworks StateFlow, State Chart, I-Logix Statemate,
etc. Part of the on-going research is to provide interpreters to
extract designs from these popular designs tools. A more interesting
and important problem, is for a specific application domain
e.g. communication protocols, designing a new model of computation and
communication, which can capture the fundamental tasks and
interactions performed in that application domain. This would contain
both control and data manipulations, not just FSMs, or data flow, or
Petri Nets.
- Software synthesis from EFSMs
Classic logic simulation techniques can be applied for generating fast
code for sequential logic network evaluation. This includes fast
functional evaluation and execution scheduling of individule nodes.
Our early work (CODES'01 PDF) compares
different method of generating implementation code (portable C code)
from logic functions, including multi-valued decision diagrams (MDD)
and sum-of-products (SOP). Recent work (DAC'03 PDF) defines a unified view of
all different simulation methods, based on generalized cofactoring
diagrams (GCD). Algorithms are studied to derive an optimal GCD for a
given multi-valued function, using an information theoretic measure.
We also look at different scheduling techniques for executing nodes in
an EFSM (DAC'02 PDF), including static,
dynamic and quasi-static.
- Software synthesis for a reconfigurable processor
For boosting performance, we study a particular class of architecture
platforms, which consists of a general purpose processor core,
augmented with a reconfigurable function unit (FPGA) inside its
data-path. The FPGA unit is configured at compile time and triggered
by special instructions during run time. This requires a clustering
method to identify regions of the original network that can be
implemented on FPGAs, and a Boolean matching method to maximally reuse
these special instructions. Some preliminary work can be found in
(CODES'02 PDF).
- Code generation issues for
embedded systems, a survey
The surveyed (2000) indicates that code generation for embedded systems
differs significantly from traditional techniques used for general
purpose computing, in that there are special requirements in terms of
power consumption, code size limitation, and real time
constraints. Related work is a project we did for advanced compiler
optimization class CS265: Macro instruction
synthesis for embedded processors (HTML).
- Control flow optimization for compilers using logic
In this brief paper (Techcon'00 PS),
we proposed an optimizing compiler flow, which applies multi-valued
optimization algorithms to optimize the control flow of target
software programs. The key issues are: (a) the construction of
MV-networks from the intermediate representation (IR) of the program
after front-end parser (SUIF); (b) the code generation from
MV-networks to final code (assembly/C).
Circuit designs can be naturally expressed in terms of multi-valued
logic. However circuits are rarely optimized at multi-valued logic
level before they are encoded into binary. This is due to the fact
that (a) there is no good multi-valued multi-level logic optimization
package available that has a complete suite of algorithms, (b) the
encoding problem is difficult for large circuits since it is hard to
estimate how an encoding decision ultimately affects the binary logic
optimizations to be applied afterwards.
Recently multi-valued logic optimization methods have been proposed
for high level implementation independent design synthesis (MVSIS), including
decomposition and extraction using algebraic techniques, and don't
care-based logic minimization (ISMVL'02
PDF). For hardware implementations, a final binary encoding is
essential. Given a minimized network of multiple-valued logic
functions, an optimal encoding transforms it into a compatible Boolean
network with a minimal cost increase.
- Multi-valued partial cares
The notion of don't cares used in binary logic is generalized to
multi-valued logic. It contains two types of flexibility: incomplete
specification and non-determinism. We generalize the computation of
observability don't cares (CODC) for multi-valued function nodes, and
propose algorithms to minimize a multi-valued logic network using
CODC's (ICCAD'00 PDF). This work
is also part of my Masters thesis
(ps.gz).
- Don't care generation from data-path
An EFSM contains both control logic and data-path, interacting with
each other. The data-path information can be utilized to generate
additional flexibility for the minimization of the control logic. This
involves first treating the data-path elements simply as black
boxes, then perform special don't care computation for multiplexers,
and finally interpreting the data computation using Presburger
arithmetic (ASP-DAC'03 PDF).
- Encoding for multi-valued logic networks
We developed an implicit encoding method (IWLS'01 PS) based on a BDD
representation of all encoding constraints. This encodes all
multi-valued variables in the logic network into binary and maintains
the optimality of the synthesis results.
- Network of PLAs
Network of PLAs have been studied as potential implementation platforms
with regularity that can control DSM noise effects and expediate the
synthesis process. MV logic networks are a natural abstraction from
PLAs. We are exploring technology dependent synthesis and clustering
techniques to support PLA implementations from MVSIS.
Multi-valued logic has successfully found its way into commercial
applications in high-density memory design, content addressable
memory, high-speed bus communications, and low power arithmetic
circuits, etc. One of the candidates for implementing multi-valued
logic is current-mode CMOS technology. It has been studied to have
low-power and high-speed advantages over voltage-mode circuits.
It has just four types of premitive devices:
- Current generators
- Current summators
- Current mirrors
- Threshold detectors
We study possible design flows and methodologies for generating
current-mode implementations directly from high-level multi-valued
synchronous specifications. The current work involves using Post
Algebra as an intermediate abstraction level, which can be efficiently
derived from the synchronous specification (Boolean Algebra) used in
MVSIS by a priority ordering (IWLS'01
PS). Then an technology mapping step from the Post algebra to the
current-mode devices (219B class
project PS). Stay tuned for future updates.