EE249 Homepage, Fall 2008

This class presents approaches to the new system science based on theories, methods and tools that were in part developed at the Berkeley Center for Hybrid and Embedded Software Systems (CHESS) and the Giga-scale System Research Center (GSRC) where heterogeneity, concurrency, multiple levels of abstraction play an important role and where a set of correct-by-construction refinement techniques are introduced as a way of reducing substantially design time and errors. Real-life applications including car electronics and building automation are used to illustrate system-level design methodologies and tools.

Below is a list of projects. The order in which they are listed does not reflect any kind of priority. You should:
1) Select a project that you are interested in from the list below
2) Contact the project mentor(s) and go talk to her/him/them
3) Find a project-mate (optional) and give a name to your team (maximum 2 persons, some projects might have suggested number of students listed. You can also find your project-mate first then look for project together.)
4) Contact your TA with the team name, team members and project title

Stochastic Timing Analysis for Hierarchical Shared Resources
Mentors: Haibo Zeng (zenghb@eecs.berkeley.edu), Paolo Giusto (paolo.giusto@gm.com), Marco Di Natale (marco@sssup.it)

Suggested Number of Students: 2

Project Description: Timing analysis is necessary for real-time embedded systems to provide timing performance information and a good insight for architecture explorations. In many embedded systems, a schedulable object may need to access multiple hierarchical resources to finish its execution/transmission. For example, in CAN message systems, a message first needs to occupy the TxObject (assuming it is not preemptible once it is there) in CAN controllers, then try to compete the CAN bus with other messages. In order to be transmitted, a CAN message needs two levels of resources: first TxObject, then CAN bus.

As previous work, [1] presents an interesting work of analyzing task response times of periodic real-time systems which is on preemptive schedulers. [2] extends the work in [1] to objects periodicially scheduled with jitter on non-preemptive scheduler, and calculate the Controller Are Networks (CAN) message latency distribution, while assuming the TxObjects in CAN controller are preemptible.

This project requires the student to extend the work in [1] and [2] to take into consideration multiple resources. To validate the stochastic analysis, a simulation engine also needs to be built up.

Required Knowledge: Markov chain

[1] J. Diaz, D. Garcia, K. Kim, C-G Lee, L LoBello, J Lopez, S Min and O Mirabella, Stochastic analysis of periodic real-time systems, In Proc. of the 23rd IEEE Real-Time Systems Symposium, December 2002.

[2] Haibo Zeng, Paolo Giusto, Marco Di Natale, Alberto Sangiovanni-Vincentelli, Stochastic Analysis of Controller Area Network Message Latencies. Submitted to DATE 2009
Peer-to-peer estimation of time varying linear systems
Mentors: Carlo Fischione (fischion@eecs.berkeley.edu), Alberto Speranzon (alberto.speranzon@gmail.com)

Monitoring physical variables is a typical task performed by wireless sensor networks (WSNs). Accurate estimation of these variables is needed for many applications, spanning from traffic control, industrial manufacturing automation, environment monitoring, to security systems. However, nodes of WSNs are strongly constrained platforms where energy supply is scarce, processing power and communication functionalities are limited. The consequence is that sensed data are affected by bias and noise, and transmission is subject to interference, which results in corrupted data (packet loss). Estimation algorithms must be designed to cope with these adverse conditions, while offering high accuracy.

There are two main estimation strategies for WSNs. A traditional approach consists in letting nodes sense the environment and then report data to a central unit, which extracts the desired physical variable and sends the estimate to each local node for local action. However, this approach has strong limitations: large amount of communication resources (radio power, bandwidth, routing, etc.) have to be managed for the transmission of information from nodes to the central unit and vice versa, which reduces the nodes' lifetime. An alternative approach enables each node to locally produce accurate estimates taking advantage of data exchanged with only neighboring nodes by peer-to-peer communication. Indeed, wireless communication makes it natural to exploit cooperative strategies, as it has been already used for coding and ransmission. The challenge of this estimation is that local processing must be carefully designed to avoid heavy computations and spreading of local errors throughout the network.

The aim of this project is the design and analysis of a peer-to-peer estimation algorithm for real time-varying linear signal. Specifically, it is assumed that such a signal is jointly tracked by the nodes of a WSN, in which each node computes an estimate as a weighted sum of its own and its neighbors' measurements and estimates. The goal of the project is the design of an estimator that features three characteristics: it should be robust to packet losses, it should not rely on a model of the signal to track, and it should use filter coefficients that adapt to the changing network topology caused by packet losses. Performance of the algorithm should be analytically characterized. A simulation of the algorithm should also be produced by using the ns2 environment (preferred) or Matlab.

[1] A. Speranzon, C. Fischione, K. H. Johansson, A. Sangiovanni-Vincentelli, ``A Distributed Minimum Variance Estimator for Sensor Networks'', IEEE Journal on Selected Areas in Communications, special issue on Control and Communications, Vol. 26, N. 4, pp. 609--621, May 2008.

[2] C. Fischione, A. Speranzon, K. H. Johansson, A. Sangiovanni-Vincentelli, ``Distributed Estimation over Wireless Sensor Networks with Packet Losses'', submitted.
Transaction level performance modeling of bit-level communication
Mentor: Felice Balarin, Cadence (felice@cadence.com)

System design often starts with a transaction level model that can simulates milions of cycles per second, and ends with RTL model that can simulate only thousands. One critical step in this process is the communication refinement to bit level so that HW interfaces can be defined. Such a refinement introduces many details in the model and often slows the simulation speed by more than an order of magnitude. On the other hand, the time spent in this communication is crucial to determine overall system performance.

The goal of this project is to explore modeling approaches where the performance impact of bit-level communication can be annotated onto the transaction level model. Evaluating these annotations should impose only a small overhead on transaction level simulations time, and yet it should represent the cost of communication as accurately as possible. Initially these annotations should be created manually on a representative example. The second phase is to consider automatically generating such annotations within the Cadence C-to-Silicon Compiler environment.
Modular translation of Simulink to SystemC
Mentor: Stavros Tripakis, Research Scientist (tripakis@cadence.com)

iSimulink is a wide-spread design and simulation environment used in the embedded system domain. It allows to model systems using a graphical block-diagram notation with discrete and continuous-time semantics, and to simulate them. SystemC is a discrete-event based modeling language implemented on C++, and extensively used for simulation of HW and SW systems.

The objective of this project is to bridge the two modeling languages by developing a method, algorithms and tool for the automatic translation of Simulink to SystemC. The main motivation is to understand the issues involved in trying to bridge heterogeneous models of computation. As a bonus, the student will also gain experience working with these two modeling languages and corresponding paradigms.

The project will focus on the discrete-time part of Simulink, which has mostly synchronous semantics. Continuous-time will be studied if time permits.

The project will focus on a modular translation. This means that Simulink sub-blocks must be translated independently into SystemC components (modules). Then the translation of a composite Simulink block X can be described as the composition of the translations of the sub-blocks of X.

As time permits, the student will implement the method on a prototype tool. He/she will also experiment, for instance, running simulations and measuring performance improvement/degradation between the original Simulink model and the resulting SystemC model.

Prerequisites: The student must have access to the Matlab/Simulink environment. Cadence labs will not provide such access. Access to the publicly available OSCI SystemC distribution will be also ensured by the student.

Background:

Equivalence Checking for Analog Platform-based Design (APBD)
Recommended number of students: 2
Mentors: Xuening Sun (xuening@eecs.berkeley.edu), James Wu (jameswu@eecs.berkeley.edu)

iThe preservation of system functionality across abstraction layers is still verified using a simulation-based approach, which becomes extremely time consuming if we need to check multiple designs that may satisfy the same functional requirements of the system. In this project, an investigation into formal equivalence checking across different abstraction layers will be conducted. Specifically, it's important to check that refinements of a high-level system model preserves the specified system functionalities.

In addition to a good grasp of the models of computation learned in the class, it would be ideal for the student to have some knowledge of integrated circuit design and equivalence checking.

Expected deliverables:
1. A proposed model of AMS circuit blocks for functional equivalence checking.
2. A new algorithm for AMS equivalence checking.
3. An example for demonstration.
Automatic generation of Analog Constraint Graphs in APBD
Recommended number of students: 1
Mentors: Xuening Sun (xuening@eecs.berkeley.edu), James Wu (jameswu@eecs.berkeley.edu)

A vital part of APBD is the generation of library components, which represent the performance feasibility space of circuit components. Since we do not want to exhaustively simulate all circuit components, Analog Constraint Graphs (ACG)[1] are used to constrain the simulation space for efficient exploration. Currently, ACGs are manually generated, which are relatively user unfriendly. In order for APBD to become widely adopted, we must ease designer efforts by automating the performance model generation process. In this project, the student should a generic procedure for automatic ACG generation of any analog circuit components. It would be ideal for the student to have a good knowledge of integrated circuit design and programming/algorithms.

Expected deliverables:
1. A representation for circuit schematic for ACG generation.
2. A set of scripts/algorithms for ACG generation.
3. Demonstration on several components. (eg. OTA, LNA, mixer, etc.).

[1] De Bernardinis, F. and Sangiovanni Vincentelli, A. 2005. Efficient analog platform characterization through analog constraint graphs. In Proceedings of the 2005 IEEE/ACM international Conference on Computer-Aided Design
Modeling of Analog/Mixed-Signal (AMS) circuit components
Recommended number of students: 2
Mentors: Xuening Sun (xuening@eecs.berkeley.edu), James Wu (jameswu@eecs.berkeley.edu)

Modeling is a key part of system-level design, especially in PBD where accurate information must be preserved through various abstraction levels. This can be quite challenging for AMS components , especially in deep-submicron technologies. The perfect model must accurately capture all non-ideal physical effects, without having to rely on exhaustive simulation. In addition, the model must be constructed/analyzed without requiring much computational resources. In this project, students will conduct a survey of existing AMS modeling techniques and hopefully improve upon existing methods to come up with a novel modeling technique to be used in APBD.

Required Knowledge: It would be ideal for the student to have a good knowledge of integrated circuit design and classification methods.

Expected deliverables:
1. A survey/analysis of existing AMS modeling techniques.
2. Propose a new circuit modeling technique/structure for use in APBD. Model should be accurate, compact, and useable in various platform levels.
3. Demonstration on sample circuit.

EE249, Fall 2008
Design of Embedded Systems: Models, Validation and Synthesis

Announcements:

Class Organization:

Lectures:

Discussions:

Labs & Homework:

Additional Reference Materials:

Projects:

EE249, Fall 2008 Design of Embedded Systems: Models, Validation and Synthesis