Click on the title below to go to the description of the corresponding
project, or just browse through them by moving down with your browser.
-
Topic: Specification
Title: Unified Modeling Language for System Level Specification
Mentor: Bassam Tabbara (tbassam@eecs.berkeley.edu)
Idea: The Unified Modeling Language (see J. Rumbaugh, I. Jacobson,
G. Booch, "The Unified Modeling Language Reference Manual") is
widely used notation for modeling software intensive systems. The purpose of
this project is to investigate the use of UML/StateCharts for system level
design by associating semantics consistent with to the network of Co-design
Finite State Machines (CFSMs) Globally Asynchronous Locally Synchronous (GALS)
model of computation. It is envisioned that this exploration will lead to
identifying a subset of UML (extended with StateCharts) that is able to
capture the static and dynamic nature of a design at a suitable abstraction
level (for now we will target a "flat" network of CFSMs, we can
elaborate the modeling and refinement later).
Implementation:
There are many available front-ends for UML specification and some C/C++/Java
code generation (e.g. Project Technology (http://www.projtech.com) have a UML +
StateCharts modeling specification GUI, as well as model code generation), the
goal is to use this front-end to get an intermediate format, to be interpreted
and mapped onto POLIS's design representation (CLIF/SHIFT), to enable
co-design (co-simulation and co-synthesis (C and VHDL code generation)) using
the POLIS engines. Recommended: 2 people
-
Topic: Software Cost Estimation, Compiler/Processor
Benchmarking
Title: High Level Software Cost Estimation for HW/SW Co-design
Mentor: Bassam Tabbara (tbassam@eecs.berkeley.edu)
Idea: Cost estimation is a crucial component in system-level
design where design trade-offs need to be explored and evaluated at the high
level. Modeling the target architecture enables a designer to make educated
design optimizations and explore suitable implementation choices without
needing to fully map every function variant onto every architectural variant.
In this project we extend the work of Suzuki (K. Suzuki, ASV, "Efficient
Software Performance Estimation Methods for Hardware/Software
Co-design", DAC 1996) by attempting to model cache and pipelining effects
at the high level (possibly by expanding the "marco-modeling"
approach of Suzuki).
Implementation: The first task would be to
model the ARM9 family of processors using benchmarking with the SDK’s
ARMulator, and incorporating this model into POLIS’s library. The next step
would be to leverage the cache modeling/pipelining of the ARMulator (profilers
are easily expandable), to see what sort of improvement can be added to the
macro-modeling approach of POLIS. The process can be done concurrently
(2nd person) for Hitachi’s SH-2 processor using Hitachi’s EDK and
toolset (Cygnus GNUpro tools can be used here as well). Recommended: 1
(ARM), 2 (Hitachi) people
-
Topic: Hardware/Software Co-simulation and Architectural
Modeling
Title: Hardware/Software Co-simulation and Architectural Modeling in VHDL
Mentor: Bassam Tabbara (tbassam@eecs.berkeley.edu)
Idea: Currently system level designs composed of mixed Hardware
(HW) and Software (SW) heterogeneous components are validated by methods that
have a biased architectural trade-off evaluation towards a pre-conceived
macro-architecture. This leads to costly design iteration until a desirable
implementation is found. In this project we plan to develop an architectural
modeling approach for system level HW/SW co-simulation. The current POLIS VHDL
system level co-simulation approach (see B. Tabbara "Fast
Hardware/Software Co-simulation Using VHDL models", DATE 99) is based on
the decomposition of the system into three classes of components, and using
timing estimates of the execution for performance simulation:
- Software CFSMs, synthesized by POLIS and executed on a single processor
under the control of a Real-Time Operating System (RTOS) also modeled in VHDL
- Hardware CFSMs, also synthesized by POLIS and communicating via a
standardized protocol (depth-1 buffer network) with the rest of the system
- Existing pieces of hardware/software IP, modeled in VHDL/C (behavioral or
RTL).
In this project we will expand on Tabbara’s approach by using VHDL to model
the target architecture itself, and then "map" the CFSM components
onto this architectural configuration.
Implementation: Look at
the basic elements of architectural modeling methods and languages (LISA
(DAC99 paper), nML, ISDL, etc..) and define a foundation basis for a
VHDL-based modeling language. Start by modeling communication primitives like
"busses", and "channels", and then move on to modeling
multiple processors, and multiple hardware partitions (e.g. multiple clock
domains). Recommended: 1 person.
-
Topic: Scheduling/Interfacing
Title: Interfacing POLIS to Mentor's VRTxoc RTOS
Mentor: Bassam Tabbara (tbassam@eecs.berkeley.edu)
Idea: Embedded systems are typically implemented as a set of
communicating components some of which are implemented in hardware and some of
which are implemented in software. Usually many software components share a
processor.
A real-time operating system (RTOS) is used to
enable sharing and provide a communication mechanism between components (see
Balarin, Jurecska, Tabbara, "Automatic Generation of a Real-Time
Operating System for Embedded Systems"). Commercial RTOSs are available
for many popular micro-controllers. Using them provides significant reduction
in design time and often leads to better structured and more maintainable
systems. However, since they have to be quite general, they are not efficient
enough for many applications, either in memory usage or in run times. Thus, it
is often the case that RTOSs are hand coded by an expert for a particular
application.This approach is obviously slow, expensive and error-prone.
Balarin et. al. have proposed an alternative where adequate interfaces to the
relevant RTOS services are automatically generated by the co-synthesis
engines.
Implementation: We will interface to Mentor's (http://www.mentor.com/embedded/downloads/index.html)
VRTXoc RTOS (Open Source Licensing), executive, and evaluate it, as well as
compare it to the POLIS automatically generated OS. We will use software
simulators (ARM, VxWorks (?)) for comparison once the task is complete.
Recommended: 2 people
-
Topic: Software estimation
Title: Software performance estimation via object code analysis
Mentor: Mihai Lazarescu (mihai@gandalf.polito.it) and
Luciano Lavagno (luciano@cadence.com)
Current techniques for software performance analysis, based on labeling
each basic block of the source code with an estimated execution time on a
given processor, are limited due to two factors:
- source code analysis [Suzuki and Sangiovanni DAC96] ignores compiler
effects (and is thus very imprecise),
- object code analysis [Lajolo and Lazarescu CODES99] must reconstruct the
functional behavior as well as the timing information (and is thus very risky,
because an error in the reconstruction may alter the functional behavior as
well, that is generally less acceptable than an error in performance
estimation).
An ideal approach would use the functional model written in high-level
language, and annotate it with timing information extracted from the optimized
object code. In this case, the problem is the correspondence between
source-level and object-level basic blocks. Loop unrolling and code motion may
alter significantly the program structure, and most compilers (with the
exception of gcc) avoid such optimizations when debugging (and hence source
backannotation) is required.
One possible solution to this dilemma is the use of volatile variables,
whose semantics in ANSI C is such that all assignments to them must be
performed exactly as written in the source code. Appropriately inserted
volatiles can become "markers" that allow one to establish a correspondence
between source and object code.
The goal of this project is to extend an existing object code analyzer (for
the MIPS processor), and allow it to back-annotate the source code using the
technique suggested above, or other ideas that may come up during the project
itself.
-
Topic: Performance analysis
Title: Automatic Abstraction for STARS
Mentor: Felice Balarin (felice@cadence.com)
Number of students: 2
STARS is a methodology for worst-case performance analysis of discrete
systems. It relies on performace model of systems components (e.g. CFSMs).
Recently, a procedure for automatic generation of these models have been
proposed for components with Boolean transition relation (represented by a
BDD). The goal of this project is to extend this approach to s-graphs and to
implement in POLIS. The generation procedure consists of writing a formula in
Presburger arithmetic using auxilary variables, and then existentially
quantifying those. and then projectingi. There is a lot of room for
improvements to this procedure: reducing the number of extra variables, early
quantification, using real arithmetic as approximation to integers ...
Researching these (and possibly others) is another goal of this project.
-
Topic: Simulation
Title: Fuzzy simulation in POLIS
Mentor: Claudio Passerone (alcor@polito.it) and Harry Hsieh (hahsieh@eecs.berkeley.edu)
Motivation:
We want to quantify the error in simulation due to the error in estimation
of execution time. The error in timing estimation takes on the form of an
"uncertainty interval". An event can be associated with a precise point in
time in the absence of uncertainty. To represent the timing uncertainty in
the occurrence of an event, the event is associated with a "start" and an
"end" denoting the boundary of the interval within which the event can occur
once and only once. Event with precise timing information is represented by
the simultaneous occurrence of the "start" and "end".
A CFSM with uncertainty in timing delay estimation can therefore produce
"fuzzy" event of this kind. A "fuzzy" event as input to some CFSM may have
any of the following three results: 1) Output and state changes are precise
in time. 2) Output and state changes are fuzzy in time 3) Output and state
changes can not be computed; uncertainty in timing lead to "functionally"
divergent behavior.
Problem Statement:
Given a particular implementation of a CFSM network, some precise timing
delay information for the OS/scheduler overhead, and "fuzzy" delay
information for the execution delay of the CFSMs, and some simulation
trace. We want to compute either a "fuzzy" output trace , or an error
message saying that an output can not be computed due to timing uncertainty
induced divergent behavior somewhere in the design.
The exact solution can be obtained through exhaustive simulation of all
combinations of uncertain timing behavior. Here, we want to compute the
solution conservatively, but only with a single run of the simulation. We
want to show that this approach is useful and not too conservative for the
examples.
-
Topic: System Synthesis
Title: Multiprocessor Synthesis for Polis
Mentor: Harry Hsieh (hahsieh@eecs.berkeley.edu)
Idea:
Current "polis architecture" for synthesis consists of only a single
processor and a single HW resource. The bus structure between the SW and HW
has the processor acting as master of the bus and HW (FPGA) hook to SW
through wires to the memory mapped registered or I/O port pins. The goal
is then to have full synthesis support for whatever the architecture
designer have in mind. This will involve finding a way to represent the
architecture we want to support, as well as synthesize the complete
hetergeneous design automatically.
Implement:
A preliminary step could be to restrict to architecture with multiple sw
resources and single hardware resource, and further assume all software clocks
are multiple of the hardware clocking to simply the interface timing.
The programming task will then be to call Polis once for each resource, and
merge the results. The second part of the project will be to improve upon
the theory and implementation to handle more general architectures.
-
Topic:
Title: Improving POLIS for the Intercom Design Project
Mentor: Marco Sgroi (sgroi@eecs.berkeley.edu) and Bassam Tabbara (tbassam@eecs.berkeley.edu)
The Intercom project (currently in progress at the Berkeley Wireless
Research Center) consists of designing a wireless portable device starting
from the high-level specification up to the final chip implementation.
POLIS is one of the tools that will be used to design the chip.
POLIS currently does not allow the designer to use user-defined
data-types, e.g. structures, that allow to specify and implement
efficiently multiple field messages and data packets. This limits the
effectiveness of Polis in designing communication chips.
This project will require the student to: 1) Extend the SHIFT/CLIF format
(internal Polis representation of the system) to include more complex
data-types, 2) Update the HW and SW synthesis routines so that they can
generate an implementation from the extended SHIFT/CLIF, 3) Test on the
real Intercom design the modifications done and therefore contribute to
the design of the chip.
Number of students: 1
-
Topic: Interface Synthesis
Title: Exploring implicit interface generation
Mentor: Roberto Passerone (roby@eecs.berkeley.edu)
In the current version of PIG, a tool for the automatic
generation of interfaces between incompatible protocols, a product machine is
generated and its transitions are explored in order to obtain a correct
interface. In the current implementation, the exploration is explicit in that
the transitions are enumerated one by one. An interesting project would be to
explore the possibility of generating the interface using implicit methods,
where the transition relation is handled as a signle object. This may
dramatically improve the performance of the algorithm, and also extends the
range of application.
Implementation:: It's hard to say how far this can go in a term
project. A plan on how to modify the algorithm and some examples of how it
would work (even done by hand) would be enough. An implementation of the
algorithm would be great. This requires some basic Java programming skills and
knowledge of BDD and implicit techniques.
For one or two people, depending on the degree of implementation.
-
Topic: Code Generation
Title: Sequential code generation for ECL
Mentor: Roberto Passerone (roby@eecs.berkeley.edu)
Number of students: 2
ECL is a reactive language that mixes features of C and Esterel to obtain
an easy to use, data and control oriented language. The current implementation
of the compiler takes the initial specification in ECL and generates Esterel
and C files which are later combined together using the Esterel compiler and
the C compiler. An alternative implementation might take the initial
specification and compile it directly into sequential code, thus bypassing the
Esterel compiler. Stephen Edwards presents one such approach for Esterel in
the paper Compiling Esterel
into sequential code.
Implementation:: The starting point would be the current public
domain version of the ECL compiler (called Jeckle) which already provides an
abstract syntax tree of the ECL program to start with. The student(s) is then
required to modify the parse tree in a form compatible to that outlined in
Edwards' paper, and implement the steps to compile the specification into C
code.
This should be for 2 people. Requires Java programming skills, some
knowledge of compilers.
-
Topic: Models of Computation
Title: Extending the CFSM model
Mentor: Marco Sgroi (sgroi@eecs.berkeley.edu) and
Luciano Lavagno (luciano@cadence.com)
Motivation:
In the current CFSM model, CFSMs communicate over channels with one-place
buffers and non-blocking write communication semantics. Lossless
communication can be enforced at the cost of significant overhead, in the
form of explicit request/acknowledgement events. This limits the
effectiveness in the design of multimedia and communication systems.
Idea:
The high cost of using Req./Ack. protocols suggests us to extend the CFSM
model so that it includes, among the other things, multiple-place buffers
to store events and decouple sender and receiver with reduced performance
losses. The extended CFSM model (ECFSM) should include also transitions
that consume multiple events in order to represent efficiently data
processing functions, such as encryption, CRC computations...
Implementation:
The project will consist of two parts. In the first part the student will
define and implement the ECFSM model within the POLIS tool (this will
require to modify the simulation and synthesis routines). In the
second part, the modifications will be tested on a real application
example.
-
Topic: Specification
Title: Reactive VHDL for System Level Specification of
Embedded Systems
Mentor: Bassam Tabbara (tbassam@eecs.berkeley.edu)
Number of students: 1-2
Idea:
The purpose of this project is to introduce VHDL as another
specification language input to POLIS in order to ease the transfer of
a wide range of current designs [1] into the formal methodology for
specification and synthesis of embedded systems. Currently POLIS
supports input from various input languages such as Esterel, and
Graphical FSMs. We propose to extend this by introducing a Reactive
VHDL specification language input to POLIS [2].
While the work of Passerone et. al. [4] extended Java by adding
synchronous language (e.g. Esterel) semantics and constructs, we
believe that the VHDL language is already quite comprehensive and is
adequate if the desired semantics are restricted to those of
Synchronous VHDL proposed by Baker in [3]. FSMD level VHDL with its
Discrete Event (DE) semantics can be adapted and interpreted as a
reactive specification language through the identification of a subset
of the language (more restricted than the Synchronous VHDL subset (to
be defined)), and a policy of use (to be defined as well), for
describing the CFSM reactive semantics, and a GALS composition model
for the system modules.
Implementation:
As a starting point the work of Baker [3], Passerone et. al. [4] in
specification, and Tabbara et. al. [5] in system modeling using VHDL
for hardware/software co-design need to be examined in order to
identify the suitable subset of VHDL and define the relevant reactive
semantics. VHDL grammar for lexical and semantic analysis is
public ally available. It can be used to translate the VHDL
specification into the POLIS internal design representation (CLIF or
SHIFT), or to devise other approaches for moving the design data from
the "front-end" VHDL into POLIS.
References:
[1] CAD Framework Initiative in collaboration with SEMATECH roadmap
at: http://www.cfi.org/roadmap
[2] Balarin et. al., "Hardware-Software Co-design: The POLIS Approach",
Kulwer, 1997.
[3] W. Baker. Application of the synchronous/reactive model to the
VHDL language. Technical report UCB/ERL M93/10, U.C. Berkeley,
1993
[4] C. Passerone, R. Passerone, C. Sansoe, J. Martin,
A. Sangiovanni-Vincentelli, P. McGeer Modeling Reactive Systems in
Java. CODES 1998.
[5] Bassam Tabbara, Enrica Filippi, Luciano Lavagno, Marco Sgroi,
Alberto Sangiovanni-Vincentelli, Fast Hardware-Software
Co-simulation Using VHDL Models, DATE 1999.
-
Topic: IP Characterization and Encapsulation
Title: A Methodology to Characterize Substrate Noise Currents Injected by Digital IP Cores
Mentor: Luca Carloni (lcarloni@eecs.berkeley.edu)
Number of students: 1
Motivation:
The task of a Systems-On-Chip (SoC) design team is to assemble a system
out of pre-designed components (IP cores) and out of quickly synthesizable
"custom" components. This task will be practically unfeasible unless each
component is designed to be almost ^Óinsensitive^Ô to its environment at every
level of abstraction (functional, communication, physical). The process of
"Physical Encapsulation of IP cores" involves the characterization of the
constraints which an IP component must satisfy to be sucessfully assembled on
a chip without affecting the behavior of other components.
Idea:
Most SoCs will be mixed-signal designs with both digital and analog circuitry
on the same die. For these designs the physical encapsulation of a digital IP
must involve also a characterization of the substrate noise currents, which
may affect the functionality of the analog parts. In [1],[2] "the SubWave
methodology" has been proposed to model digital substrate noise injection.
One of the main steps is to derive the set of substrate injection patterns for
each cell of the chosen standard-cell library. These patterns depend on the
cell functionality, its switching activity as well as on technology process
parameters. The goal of this project is to define a methodology to efficiently
derive all patterns for all cells of a given library
Implementation:
This project encompasses two research avenues.
- From a theoretical point of view the task is to define an analitical
model of the substrate injection of a generic standard-cell (a meta-model)
which takes into account statistical variations of the process parameters. If
one succeeds definining this meta-model, then it could be used to analitically
derive injection patterns for all individuals cells as well as to formally
prove the robustness of the overall SubWave methodology.
- From a practical point of view, the task is to define a framework to
automatically characterize the patterns of all cells in the library using a
circuit simulator (such as Spice). This framework could be the base of the
second generation of the SubWave design tool suite.
References:
[1] P. Miliozzi, L.P. Carloni, E. Charbon and A.L. Sangiovanni-Vincentelli.
SubWave: a Methodology for Modeling Digital Substrate Noise Injection in
Mixed-Signal ICs. Proceedings of the IEEE 1996 Custom Integrated Circuit
Conference.
[2] E. Charbon, P. Miliozzi, L.P. Carloni, A. Ferrari and A.L.
Sangiovanni-Vincentelli Modeling Digital Substrate Noise Injection in
Mixed-Signal ICs IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems, Vol. 18, No. 3, March 1999.
