University of California, Berkeley
Electrical Engineering and Computer Sciences Department
Class Organization | Lectures | Discussions | Labs & Homework | Announcements | Additional Reference Materials | Projects

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

Lecture: Tues/Thurs: 11:00 - 12:30 pm
Discussion: Tues: 5:30 - 6:30 pm
Lab: Thurs: 4:00 - 6:00 pm
540A/B Cory Hall

Prerequisite:  There is no pre-requisite for this course, but some exposure to the basics of real-time embedded system and an inclination to formal reasoning is welcome.

  • No textbook required for this course.

  • Course Flier

  • Academic Dishonesty Policy
  • Lecturer:
    Professor Alberto L. Sangiovanni-Vincentelli
    515 Cory Hall
    Phone: (510) 642-4425

    Office Hours:
    Tues/Thurs: 12:30 - 1:30 pm,
    515 Cory Hall

    Teaching Assistant:
    Kelvin Lwin

    Office Hours:
    Tues.: 3:00 - 5:00 pm,
    545W Cory Hall

    Course Administrative Assistant:
    Therese George
    253 Cory Hall
    (510) 642-2384

    Welcome to EE249

    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.

    Back to top


    • Discussion time has been moved to 5:30 from 5:10 on Tuesdays.

    Back to top

    Class Organization:

  • Part 1: Introduction
  • Design complexity, example of embedded systems,traditional design flow, Platform-Based Design.

  • Part 2: Functional modeling, analysis and simulation
  • Introduction to models of computation. Finite State Machines and Co-Design Finite State Machines, Kahn Process Networks, Data Flow, Petri Nets, Hybrid Systems. Unified frameworks: the Tagged Signal Model, Agent Algebra.

  • Part 3: Architecture and performance abstraction
  • Definition of architecture, examples: distributed architecture, coordination, communication. Real time operating systems, scheduling of computation and communication.

  • Part 4: Mapping
  • Definition of mapping and synthesis. Software synthesis, quasi static scheduling. Behavioral synthesis. Communication Synthesis and communication-based design.

  • Part 5: Verification
  • Validation vs Simulation. Verification of hybrid system. Interface automata and assume guarantee reasoning.

  • Part 6: Applications
  • Automotive: car architecture, communication standards (CAN, FlexRay, AUTOSAR), scheduling and timing analysis.
    Building automation: Communication (BacNet, LonWorks, ZigBee). Applications to monitoring and security.

    Back to top


  • Introduction to EE249

  • Part 2: Methodology PBD

  • Part 3: Models of Compultation

  • Finite State Machines

  • Overview of the Ptolemy Project

  • Data Flow Models

  • Petri Nets

  • Tagged Signal Model

  • LabVIEW Overview, StateChart Module, Lab Exercises

  • Abstract Algebra

  • Metropolis Metamodel

  • Real-Time Operating Systems and Schedulability Analysis

  • Introduction to Controller Area Network, Using CAN

  • Design Methods and Tools for Real-Time Embedded Systems

  • Back to top


    Back to top

    Labs & Homework:

    Back to top

    Additional Reference Materials:

    Back to top


    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 (, Paolo Giusto (, Marco Di Natale (

      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 (, Alberto Speranzon (

      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 (

      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 (

      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: Analog/Mixed-Signal subsystems are important parts of embedded-system design. Their main purpose is to interface real world environments with digital circuitry. (eg. RF transceiver frontends, energy scavenging interface, sensor acquisition frontend, etc.) Although research efforts in the automation of analog circuit design have been around for the last few decades, it's adoption has not been wide-spread due to various issues. (eg. the presence of second-order effects, nonorthogonal design parameters, and complex device physics) Traditionally, analog circuit design always been dependent on heuristics, designers' experience, and trial-and-error approaches. To deal with the design difficulties of analog and mixed-signal systems, a platform-based design approach[1] has been developed. In APBD, we look at the problem from the system level, where the design space of a system is explored through refinements across multiple abstraction layers. The following projects are some open areas of research in APBD. [1]. De Bernardinis, F.; Sangiovanni Vincentelli, A., "A methodology for system-level analog design space exploration," Design, Automation and Test in Europe Conference and Exhibition, 2004. Proceedings , vol.1, no., pp. 676-677 Vol.1, 16-20 Feb. 2004

    • Equivalence Checking for Analog Platform-based Design (APBD)
      Recommended number of students: 2
      Mentors: Xuening Sun (, James Wu (

      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 (, James Wu (

      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 (, James Wu (

      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.

     Last updated 9/23/08