Abstracts for Edward A. Lee

The EECS Research Summary for 2003

Ptolemy II--Heterogeneous Concurrent Modeling and Design in Java

Adam Cataldo, Chris Chang, Elaine Cheong, Christopher Hylands1, Edward A. Lee2, Xiaojun Liu, Steve Neuendorffer, Claudius Ptolemaeus3, John Reekie4, Mary P. Stewart5, James Yeh, Yang Zhao, Haiyang Zheng, and Ye Zhou
(Professor Edward A. Lee)
Agilent Technologies, Cadence Design Systems, Defense Advanced Research Projects Agency (DARPA), Hitachi, Microelectronics Advanced Research Corporation (MARCO), National Semiconductor, and Philips

Ptolemy II [1] is a set of Java packages supporting heterogeneous, concurrent modeling, simulation, and design of component-based systems. The emphasis is on a clean, modular software architecture, divided into a set of coherent, comprehensible packages. The kernel package supports definition and manipulation of clustered hierarchical graphs, which are collections of entities and relations between those entities. The actor package extends the kernel so that entities have functionality and can communicate via the relations. The domains extend the actor package by imposing models of computation on the interaction between entities. Domains that have been created include:

The Ptolemy II software architecture supports interaction between domains (heterogeneous modeling). For example, FSM can be combined with CT to model hybrid systems.

Ptolemy II includes a number of support packages, such as

For more information about Ptolemy II, see .

Figure 1: Claudius Ptolemaeus

S. S. Bhattacharyya, E. Cheong, J. Davis II, M. Goel, C. Hylands, B. Kienhuis, E. A. Lee, J. Liu, X. Liu, L. Muliadi, S. Neuendorffer, J. Reekie, N. Smyth, J. Tsay, B. Vogel, W. Williams, Y. Xiong, and H. Zheng, Heterogeneous Concurrent Modeling and Design in Java, UC Berkeley Electronics Research Laboratory Memorandum No. UCB/ERL M02/23, August 2002.
4Postdoctoral Researcher

More information (http://ptolemy.eecs.berkeley.edu/ptolemyII) or

Send mail to the author : (eal@eecs.berkeley.edu)

Soft Walls: Modifying Flight Control Systems to Limit the Flight Space of Commercial Aircraft.

Adam Cataldo, Xiaojun Liu, and Zhongning Chen1
(Professor Edward A. Lee)

The Soft Walls project is a technological response to the September 11, 2001 tragedy [1]. The project goal is to design an aircraft control system to enforce government-mandated no-fly zones. The no-fly zones will include major cities, government centers, military installations, chemical and nuclear plants, and critical infrastructure centers. As an aircraft approaches a no-fly zone, the flight control system will force the aircraft away, giving the pilot a sensation of an external force. The no-fly zone boundaries are called Soft Walls, because aircraft are gently diverted as they approach these zones.

In the future, all aircraft are likely to use fly-by-wire systems, where pilot controls are mediated by computers, rather than being mechanically or hydraulically connected to the aircraft control surfaces. We are designing our control system for such fly-by-wire aircraft. The aircraft will carry a three-dimensional model of the earth’s surface, augmented with the no-fly zones. The model will change only when the no-fly zones change. One of our design principles is to give the pilot as much control as possible, subject to the constraint that the aircraft can never enter the no-fly zone.

We have developed a control algorithm for a two-dimensional infinite wall [2]. This algorithm uses a simplified model of the aircraft dynamics and adds a bias to the pilot's control as the aircraft gets near the no-fly zone. The bias is increased and decreased gradually, and the algorithm is provably safe, that is, the aircraft can never enter the no-fly zone. Our next goal is to find a control algorithm which works for any convex, two-dimensional no-fly zone.

E. A. Lee, Soft Walls: Modifying Flight Control Systems to Limit the Flight Space of Commercial Aircraft, UC Berkeley Electronics Research Laboratory Memorandum No. UCB/ERL M001/31, September 2001.
J. A. Cataldo, E. A. Lee, and X. Liu, Preliminary Version of a Two-Dimensional Technical Specification for Softwalls, UC Berkeley Electronics Research Laboratory Memorandum No. UCB/ERL M02/9, April 2002.
1Undergraduate (EECS)

More information (http://www.cs.berkeley.edu/~acataldo/) or

Send mail to the author : (acataldo@eecs.berkeley.edu)

Ptplot--A Java 2D Signal Plotter

Christopher Hylands1
(Professor Edward A. Lee)

Ptplot is a set of two-dimensional signal plotter components written in Java with the following properties:

Figure 1: Screen shot of Ptplot

More information (http://ptolemy.eecs.berkeley.edu/java/ptplot) or

Send mail to the author : (cxh@eecs.berkeley.edu)

TinyGALS: A Programming Model for Event-driven Embedded Systems

Elaine Cheong and Jie Liu1
(Professor Edward A. Lee)

Networked embedded systems such as wireless sensor networks are usually designed to be event-driven so that they are reactive and power-efficient. Programming embedded systems with multiple reactive tasks is difficult due to the complex nature of managing the concurrency of execution threads and consistency of shared states.

We have designed a globally asynchronous and locally synchronous model, called TinyGALS, for programming event-driven embedded systems [1]. Software components are composed locally through synchronous method calls to form modules, and asynchronous message passing is used between modules to separate the flow of control. In addition, we have designed a guarded yet synchronous model, TinyGUYS, which allows thread-safe sharing of a global state by multiple modules without explicitly passing messages. Our notions of synchrony and asynchrony, which are consistent with the usage of these terms in distributed programming paradigms, refer to whether the software flow of control is immediately transferred to a component.

With this highly structured programming model, all asynchronous message-passing code and module-triggering mechanisms can be automatically generated from a high-level specification. The programming model and code generation facilities have been implemented for a wireless sensor network platform known as the Berkeley motes. TinyOS is an event-based operating system for these networked sensors being developed by the group of Professor David Culler. Our implementation of TinyGALS uses the component model provided by TinyOS, which has an interface abstraction that is consistent with synchronous method calls. The TinyGALS code generator is designed to work with preexisting TinyOS components, thus enabling code reuse.

We are currently working on formalizing the dynamic properties of TinyGALS, as well as developing a more robust implementation for communication and scheduling. TinyGALS is currently intended for running on a single node. We later plan to extend the TinyGALS model to multiple nodes for distributed multi-tasking.

E. Cheong, J. Liebman, J. Liu, and F. Zhao, "TinyGALS: A Programming Model for Event-driven Embedded Systems," Proc. ACM Symp. Applied Computing, Melbourne, FL, March 2003.
1Palo Alto Research Center (PARC)

Send mail to the author : (celaine@eecs.berkeley.edu)

Lightweight Component Models for Embedded Systems

H. John Reekie1
(Professor Edward A. Lee)
Agilent Technologies, Cadence Design Systems, California MICRO, DARPA, Hitachi, MARCO/DARPA Gigascale Silicon Research Center, National Science Foundation, National Semiconductor, and Philips

We are exploring the concept of software component [1] in the context of embedded and real-time systems. Although the term "component" is used in many different ways, the term is coming to have an established meaning in software design and implementation, and we follow the emerging usage of this term. Intuitively, a software component is a piece of software that can be "plugged into" some other piece of software.

In the Ptolemy Project, we have been exploring systems modeling using actors and models of computation for some time [2]. Actor-oriented software design is a natural choice for embedded systems components, and we believe that software component models specifically designed for embedded systems offer promise for improving the ability to "bridge the gap" from systems modeling efforts to implementation. We have proposed two lightweight component models, deliberately making different design choices so that we can explore this design space [3].

The first model, Actif, is being developed as a model suitable for implementation in native binary formats. It has a separate executable and interface, and a controller that is synthesized from the component interfaces. We believe that Actif, although it will take longer to develop suitable infrastructure support, will prove to be a more powerful tool for building reliable real-time systems. The second model, Compact, is being developed as a lightweight framework for execution of components in Java. Its primary aim is to provide a means by which components developed by different authors can be executed in more than one execution framework, again developed by different authors.

We are presently exploring the use of interface automata [4] to abstract and compose Actif actors. Moving forward, we expect to work on implementation of these component models.

C. Szyperski, Component Software: Beyond Object-Oriented Programming, Addison-Wesley, 1998.
The Ptolemy project: http://ptolemy.eecs.berkeley.edu.
H. J. Reekie and E. A. Lee, Lightweight Component Models for Embedded Systems, UC Berkeley Electronics Research Laboratory, Memorandum No. UCB/ERL M02/30, October 2002.
L. de Alfaro and T. A. Henzinger, "Interface Automata," Proc. Symp. Foundations of Software Engineering, ACM Press, 2001.
1Postdoctoral Researcher

More information (http://ptolemy.eecs.berkeley.edu/~johnr/) or

Send mail to the author : (johnr@eecs.berkeley.edu)

Study of Synchronous Dataflow

Haiyang Zheng
(Professor Edward A. Lee)

The purpose of this project is to study some properties of synchronous dataflow (SDF) including the abstractions of actors and the composibility of SDF models. In a SDF model, actors have static firing rules: they consume and produce a fixed number of tokens in each firing. The token consumption and production rates of an actor are the abstraction of the actor. Based on this abstraction, an efficient, static schedule can be solved with the balance equations between actors. An important constraint about the firing rules of SDF is that an actor can't fire unless all its inputs have enough tokens. Sometimes this constraint is too conservative in that some executable models fail to find the executable schedules [1,2]. This is because the SDF abstraction of the actors isn't sufficient.

This project aims to find a sufficient abstraction with the exposure of the internals of actors. The basic idea is to separate the computation and communication of an actor, and to abstract the communication part. The abstraction focuses on what conditions the actor affects in the environment. The schedule based on this abstraction reflects the computation of actors better than the general SDF schedule. This abstraction can be regarded as a refinement of the SDF abstraction.

This abstraction can be used to study the composibility of SDF models. A composite SDF model has several SDF models embedded inside. The SDF abstraction of this composite model is based on the solution of the balance equations between the actors inside. This abstraction indicates the requirement for the composite model to restore its original state. It also abstracts away some of the internal communication behaviors, which is valuable in the schedulability study of the composition of SDF models. Our new abstraction catches the communication part and the schedulability analysis can be done without flattening the composite models.

T. M. Parks, J. L. Pino, and E. A. Lee, "A Comparison of Synchronous and Cycle-Static Dataflow," Proc. Signals, Systems and Computers Conf., Vol. 1, 1996.
G. Bilsen, M. Engels, R. Lauwereins, and J. A. Peperstraete, "Cyclo-static Dataflow," IEEE Trans. Signal Processing, Vol. 44, No. 2, February 1996.

Send mail to the author : (hyzheng@eecs.berkeley.edu)

CAL: A Novel Actor Language

Joern Janneck1, Chris Chang, and Yang Zhao
(Professor Edward A. Lee)

The concept of actors was first introduced by Carl Hewitt as a means of modeling distributed knowledge-based algorithms. Actors have since then become widely used.

CAL is a small domain-specific language for writing down the functionality of actors–specifically including their ports, parameters, typing constraints, and firing rules. It is designed to be embedded in an environment providing necessary infrastructure, such as data types, operations, and function libraries. The goal is to provide a concise high-level description of actors by providing statically analyzable information about the behavior of an actor, such as production and consumption rates, to facilitate scheduling, composition, and static checking of actor networks.

Current work includes:
(1) using program transformation techniques for manipulating CAL actor specifications, and compositions of CAL actors;
(2) generating executable code from an actor description, in order to simulate or eventually implement an actor on some target platform;
(3) scheduling;
(4) compatibility checking between connected actors; and
(5) CAL language developing and changing.

1Postdoctoral Researcher

Send mail to the author : (cbc@eecs.berkeley.edu)

Copernicus: Generating Code from Polymorphic Components and Heterogenous Models

Stephen Neuendorffer and Christopher Hylands1
(Professor Edward A. Lee)
Ptolemy Project

The high level of abstraction possible in component-based modeling offers many advantages, such as simulation speed, the strength of formal models of computation, etc. However, the fundamental weakness of high-level modeling is the difficulty of actual implementation. Traditionally the easiest way to get high performance has been to translate the model by hand into a low-level implementation language. Automatic code generation from the model is sometimes possible by assembling the component specifications, but only with serious performance penalties.

These penalties come from several sources:

  1. A component in the modeling environment is inevitably built to be easy to design with. Components can often accept a variety of data types (type-polymorphism), can be used in a variety of control or communication models (domain-polymorphism), can be configured with different parameters (operational-polymorphism), and can be used in any environment (context-polymorphism). This flexibility directly conflicts with the goals of most optimized implementations.
  2. A model consists of components, their ports, and the connections between those ports. The model of computation assocatied with a model determines how connected components communicate and control their execution. In some cases the boundaries of components correspond to physical boundaries of the implemented system. For example, there might be one component for each physical processor that is connected to a system bus. However, the boundaries of components often have no physical importance in a system. They are specified arbitrarily by the system designer, specified because of the social structure of the group designing the model, or because of the availability of reusable components. Simple code generation strategies blindly preserve the structure of the model, which can result in unnecessary overhead.
At some level, these problems can be ameliorated using traditional code generation strategies. If a component is too flexible to generate good code, then it can be replaced with a specialized hand-written version. If there is unnecessary structure in the model, then change the model so that the structure is removed. However, these solutions conflict directly with good engineering practice and greatly complicate the implementation procedure.

We are developing a code generation strategy that attempts to handle these difficulties automatically. The key idea is that we combine code generation from a model with compilation of the code for individual actors. We call this strategy co-compilation. This strategy directly addresses the difficulties above. We parse the code for an actor and specialize it according to its use in a particular model (the types, the particular domain, the values of parameters, and the connections that have been made to it). We can also perform cross-actor optimizations to eliminate or reorganize the structure of a model.

Co-compilation also offers a straightforward path to code generation from heterogenous models that contain different communication and control strategies organized in a hierarchical structure. We anticipate being able to generate code for a model at one level of the hierarchy and then use the generated code as a component at a higher level of the hierarchy. This can result in reduced overhead as well, since a system designer is not limited to a single model of computation.

We have implemented this code-generation strategy as the Copernicus package, which is part of Ptolemy II. Copernicus parses the Java bytecode for actors, optimizes it, combines it with code generation from the model, and outputs Java bytecode. The resulting generated code is currently useful for high-speed compiled code simulation. We are currently exploring how to generate code for embedded architectures and for FPGAs.


More information (http://www.eecs.berkeley.edu) or

Send mail to the author : (neuendor@eecs.berkeley.edu)

An Actor-Oriented Framework for Distributed Software Systems

Xiaojun Liu and Yang Zhao
(Professor Edward A. Lee)

A large number of embedded systems applications require the coordination of physically distributed components or networked embedded sub-systems. Distributing system components across a network can improve the robustness of a system and simplify its architecture by allowing components to run concurrently and independently. However, designing and implementing these systems can be complex and difficult.

In recent years, several middleware technologies, such as the Common Object Request Broker Architecture (CORBA) and the Distributed Component Object Model (DCOM), have been introduced. They are based on object-oriented APIs that offer a level of abstraction and facilitate distributed systems development, but their programming models are too liberal to analyze their formal properties. It is difficult to port an application developed using one particular middleware technology to another.

In this project, we are interested in developing a framework for distributed software systems based on the Ptolemy II actor-oriented infrastructure. We will explore the design of common actor interfaces on top of today’s object-oriented middleware--actor components that comply with such interfaces can be deployed in different middleware environments. We will also explore the concept of models of computation in distributed systems and adapt the current Ptolemy II execution model to distributed architectures. By doing so, it will be possible to provide guarantees on the behavior of the distributed systems, rather than having properties emerge as a by-product of a specific middleware implementation.

Send mail to the author : (liuxj@eecs.berkeley.edu)

Component-based Design for Wireless Networked Systems

Ye Zhou
(Professor Edward A. Lee)
National Semiconductor

In this project, we are trying to provide a solution to support different cellular-network standards, namely GSM and 3G standards of WCDMA, TD-SCDMA, and CDMA2000. Our approach is to use an actor-oriented system-on-chip (SoC) architecture, where a number of small DSP cores are developed to support various programmable functions. The idea behind this is to develop a hardware platform for wireless communications, which can be used to derive various SoC products by changing only the software.

We begin with looking into the RAKE receiver, as it is the key part of CDMA systems. We also focus on two standards first: WCDMA and TD-SCDMA, which appear to be quite popular and promising in research and marketing. The work is planned to progress in the following steps: (1) the study starts with system functional analysis, where we explore a shared block-diagram between the two standards; (2) we will then develop some adaptive algorithms and analyze the system complexity; (3) based on these previous works, we are able to come up with decisions on system architecture and software/hardware partition, and at each step, different levels of simulations are involved to support our ideas; and (4) eventually, the architecture is designed to be at a fairly optimal point, considering the tradeoff among factors such as power, speed, flexibility, etc.

This wireless communications project is conducted in cooperation with National Semiconductor.

Send mail to the author : (zhouye@eecs.berkeley.edu)