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

Alberto Sangiovanni-Vincentelli

This course is about the design of embedded real-time systems. Embedded real-time sytems are pervasive in today's world. The methodology used for the design of these devices is still based on principles and tools that are not adequate for the complexity of the applications being developed today. The most important characteristic of these systems is the massive use of programmable components to achieve the design goals. Today, the dominant part of the design effort for embedded system is software. Real-time and power dissipation constraints make embedded software design particularly difficult since traditional abstraction for software do not include physical quantities. The choice of the architecture of the implementation is another essential characteristic of embedded system design. The implementation platform should be selected to support the application of interest optimizing a set of conflicting criteria that include flexibility, scalability, design time, manufacturing cost and reliability.
In this course, we will present the principles of a methodology that favors design re-use, formal verification, software design and optimized architecture selection. The basic tenet of the methodology is orthogonalization of concerns, and, in particular, separation of function and architecture, computation and communication. This methodology called platform-based design will be presented as a paradigm that incorporates these principles and spans the entire design process, from system-level specification to detailed circuit implementation.

• We will place particular emphasis on the analysis and optimization of the highest levels of abstraction of the design where all the important algorithmic and architectural decisions are taken. The notion of behavior will be analyzed and the role of non-determinism in specification will be explained. We will present the basic models of computations that are needed to represent the behavior of most designs: Finite-State Machines, Synchronous Languages, Data Flow Networks, Petri Nets, Discrete Event Systems. We will outline the use of a unified framework to compare the different models of computation and a unifying theory to allow the composition of different models of computation to describe a complete system. We will introduce the Ptolemy and Metropolis environments for analysis and simulation of heterogeneous specifications.
• We will introduce the notion of "architecture" as an interconnection of building blocks that are capable of carrying out computation. "Optimal" architecture choice will be presented as the selection of a particular set of computational blocks in a "library" of available components, and of their interconnection. The evaluation of the quality of a selected architecture is based on a "mapping" process of behavior to the computation blocks, including programmable components. The mapping process should be accompanied by an estimate of the performance of the design once mapped onto the architecture. Communication representation will be illustrated. The representation of architectures in the Metropolis and Mescal environments will be presented.
• Embedded software design will be considered as part of the mapping process. In this context, we will review the approaches followed to estimate physical quantities such as time and power for embedded software. We will present scheduling as a way of mapping concurrent processes in a resource limited architecture and we will address the characteristics of real-time operating systems. We will review code generation techniques used in widely used industrial tools such as Real Time Workshop and Target Link. We will present software synthesis approaches that exploit the mathematical properties of the design. We will also address the problem of synthesizing communication structures given the system level requirements.
• The different coordination policies used at different levels of abstraction will be introduced with particular emphasis on the de-synchronization paradigm where a synchronous specification is mapped onto an asynchronous implementation that is guaranteed functionally equivalent to the specification.
• Application examples taken from the multi-media and the automotive industrial sectors will be used throughout the course to illustrate the techniques presented in the course.

The course is graded on assignments and on a final project. Given the link to present research activities we expect a number of projects will eventually be published in Conference Proceedings. We will devote the afternoon sessions of the course to the presentation of important papers in the literature. The quality of class presentation on the papers is expected to be part of the grade. There are no pre-requisite for this course but it is preferable to have had some exposure to the basics of real-time embedded systems. At the end of the course the student will have an understanding of the system-level design issues in the areas of specification, validation and HW/SW implementation. Moreover, the student will gain experience on actual system designs through graded laboratories dealing with realistic design examples and case studies. During lab sessions, students will use and analyze various design tools including: Ptolemy, Metropolis, Co-ware, Seamless, Xilinx Virtex FPGA and Anadigm FPAA.