EECS 290n
Contents

Home
Overview
Logistics
Technology

Lectures
Calendar
Assignments
Study group
Project

Reading
References
Resources

Project

• Project presentations in 2004
• Project presentations in 2002

A project is required for this course. A typical project will have an experimental component (software) backed by a paper describing the principles being investigated. For the experimental component, students are encouraged to use a common technology base in order to maximize the effectiveness of interaction within the group. Specifically, the technology base upon which students will be expected to build is:

• The Java programming language.
• The Ptolemy II framework.
• The Eclipse integrated development environment.

The paper component will be expected to be conference quality, with appropriately chosen and cited references to the literature. Papers must be scholarly, meaning that they describe original work, critically assess both the advantages and disadvantes of that work, and compare that work to other published work.

Papers should be no more than four pages in length, two column format, as given by the Latex template. Students are required to submit an extended abstract for review by other students in the class. The extended abstract should follow the same format as the paper, but can be shorter.

Below is an evolving list of project suggestions:

1. Evaluate and compare distributed models of computation, including at least Chandy & Misra style distributed discrete events (the Ptolemy II DDE domain), distributed process networks (the Thales implementation of a Ptolemy II DPN domain), and ad-hoc interactions of independently executing Ptolemy II models, using for example sockets or CORBA for communication.
2. Implement a distributed discrete-event modeling mechanism like that in Croquet, which uses replicated models with time-warp-like backtracking.
3. Build a library of actors and design patterns for distributed health management of Ptolemy II models. The initial application will be to the display case outside 337 Cory Hall, which runs (largely untrusted) Ptolemy II models as demos. One or more other Ptolemy II models, running on other machines, will interact with the models running in the display case to monitor their health (liveness, memory usage) and repair the models when necessary.
4. Design an Eclipse plug-in supporting actor definition for actor-oriented designs. This project should leverage the Eclipse representation of Java code to, for example, perform static analysis of the actor code to determine and/or enforce certain dataflow styles (e.g., to ensure that inputs to the actor are consumed). Alternatively, the plug-in could serve as a syntax-directed editor that is aware of the structure of actor-oriented models and of coding conventions.
5. Study the problem of security in distributed actor-oriented models and implement a security toolkit for building secure distributed models. This project can leverage the security actors in Ptolemy II, which provide basic mechanisms for encryption and authentication.
6. Integrate a model-checking tool with the Ptolemy II FSM domain, or an appropriate specialization of that domain. This project should consider the applicability of the model checking strategy when concurrent FSMs are combined according to one or more concurrent models of computation.
7. Construct a model-based refactoring tool for actor-oriented designs. This tool would require a formal description of a refactoring operation (such as addition or removal of hierarchy) and would use that description to guide execution of the refactoring operation. (cf. reference Alexander Wisspeintner's work in Manfred Broy's group at TU Munich).
8. Perform a study of the role of higher-order components in actor-oriented design, and devise a coherent library of basic operations that are required for expressiveness. This work can leverage various higher-order components that have been implemented in Ptolemy II, but should identify gaps in the capabilities and then fill those gaps, and should identify higher-order components that operate at the abstract syntax level and distinguish from those that depend on semantics. (cf. Reekie)
9. Adapt and apply code generation from Ptolemy II models to a real-time problem, using for example the IBM JVM on a Sharp Zorus to implement a real-time system. Examples could include a robot arm controller.
10. Design a mechanism for defining actors in an actor-oriented framework in a low-level language such as C or nesC. This project could, for example, define an Eclipse plug-in supporting syntax-directed editing where the interface between the low-level code and the framework is generated code. This could be used, for example, with the Giotto domain in Ptolemy II to build hard-real-time programs.
11. Construct a Metropolis domain in Ptolemy II. This would use Metropolis component definitions, channel definitions, and quantity managers, ideally unchanged, and would provide a visual syntax coupled with a code generator that interfaces to the Metropolis release.
12. Several concurrent models of computation require hierarchical combination with finite state machines (as in the Ptolemy II FSM domain) to express modal behavior (e.g. Giotto, SDF, CT). In principle, FSMs can be easily translated to efficient C code, but the ease of doing this depends on the expression language used for expressing guards and actions associated with transitions. This project will construct a code generator for the Ptolemy II FSM domain that can produce C code or Java code.
13. In principle, actor-oriented models can have more flexible hierarchies where an actor interface is used in a model but multiple implementations can be substituted. These multiple implementations might be selected to vary the level of abstraction of the model or to optimize against certain criteria. This project will implement a mechanism in Ptolemy II that supports subtitution of multiple implementations for an interface. (cf. Vanderbilt's DESERT project).
14. TOSSIM is a heterogeneous simulator supporting discrete-event simulation of a wireless sensor network together with execution of nesC/TinyOS programs for the sensor nodes. This project will study the strengths and weaknesses of this combination by integrating TOSSIM with the Ptolemy II "ptinyos" domain, a preliminary capability that generates code in nesC for TinyOS programs.
15. Click is a framework for designing network routers that function as an extension of the Linux kernel. This project will build a Click code generator in Ptolemy II and study performance properties for networking applications.
16. With the certification by European aviation authorities of SCADE for use in safety critical aircraft control software, synchronous languages have been getting more attention recently. This project will develop a deeper understanding of the issues by constructing a Lustre-like clock calculus for the Ptolemy II SR domain (Lustre is the language underlying SCADE).
17. A variant of the previous project will define a set of actors in the SR domain that represent Lustre primitives plus FSMs and construct a code generator that produces Lustre from SR models in Ptolemy II.
18. Define models in Ptolemy II for autonomous vehicles (rolling or flying) and their interaction with 3-D terrain models. This will follow principles similar to the wireless sensor network modeling in Ptolemy II, but interactions between components will be through 3-D geometry models and the laws of physics.
19. Explore visual syntaxes for xGiotto programs. xGiotto is a language with principles similar to Giotto and the Ptolemy II TM (timed multitasking) domain.
20. Explore a restricted form of hybrid systems where discrete behavior is given exclusively by periodically scheduled actions and mode switching between actions, as in the Giotto language. The objective is to re-examine the basic expressiveness and decidability results of hybrid systems to see whether the restriction to periodic discrete actions strengthens the formal properties, and to explore the expressiveness of the model by constructing examples using a combination of the CT (continuous time) and Giotto domains in Ptolemy II.
21. Compare actor definitions languages Cal (from Berkeley) and StreamIT (from MIT) for use in dataflow models (such as Ptolemy II SDF, DDF, and PN). One possible outcome might be a variant of these languages, for example one with a friendlier syntax that combines the strengths of the two languages.
22. Visual syntaxes for actor-oriented models have a certain appeal for pedagogy, but many people feel that visual syntaxes will never scale sufficiently to be able to deal with complex designs. This project will explore textual syntaxes that are compact, readable, and capable of expressing (at least) the Ptolemy II abstract syntax for actor-oriented models.
23. The theory of control systems has a rich set of formal analysis techniques for continuous-time feedback systems. This project will develop analysis tools that apply that theory to Ptolemy II models in the CT domain to perform, for example, stability or robustness analyses.
24. Models of computation like Giotto, xGiotto, and Timed Multitasking (the TM domain in Ptolemy II) manage a single shared resource, the CPU, sharing it accross several real-time tasks. The purpose of this project is to devise a software architecture that augments this with mechanisms for sharing multiple resources, and for performing timed simulation of the resource sharing, formal analysis of the schedulability of the shared resources, or both.
25. Boolean Dataflow (BDF) offers a rich formal analysis of consistency of models. This can be used for verification by specifying safety conditions in terms of consistency. This project will formulate some verification questions this way and will apply implementations of BDF to these.

The following project suggestions come from Steve Neuendorffer:

26. Memory management for dataflow models of computation. Dataflow models of computation expose a significant amount of concurrency in system design by reducing shared state between parts of a system. Dataflow components exchange messages with immutable values, in order to ensure that side effects do not have unintended consequences. Unfortunately, implementing this semantics in a single processor system often results in undesirable dynamic memory allocation for large components. In particular, algorithms such as the Fast Fourier Transform, cannot be easily implemented 'in-place'. There are some techniques known as region-based memory allocation that statically analyze a program (or dataflow) graph to understand when memory can be reused. Come up with a scheme for applying these techniques to dataflow models that address the desire to safely implement algorithms such as the FFT without allocating extra memory. Prototype in Ptolemy II.
27. Reconfiguration constraints in higher-order dataflow models. Generic system-level models are often parameterized in order to increase reusability and configurability. Run-time parameter reconfiguration is a powerful tool for leveraging parameterization. However, while some parameters can be reconfigured at any time, other parameters must be reconfigured at specific execution points, or not reconfigured at all because of their meaning in a model. Currently, Ptolemy II includes a system for analyzing reconfiguration to determine if safety constraints are satfisfied which relies on a 'statically structured' model. However, many interesting models are not statically structured, such as those with mobile components that are 'plugged-in' at run-time. While we should not expect arbitrarily restructured models to be statically analyzable, statically structured models with mobile components can probably be analyzed under certain constraints. Figure out what those constraints should be and implement a combined static/runtime analysis system for quickly checking the reconfiguration constraints of a mobile component when it is plugged in.
28. Optimal Synchronous Reactive scheduling for decision problems. Signal classification is an interesting signal processing problem. One approach to this problem to model it as a decision problem, where many complex signal processing operations are performed on an incoming signal and a decision function is applied to the result. In most cases, this decision function is nonstrict: A decision can often be made using only some of the signal processing operations. When writing C code, a programmer would usually be forced into deciding which signal processing operations should be performed first for a given decision function, and 'breaking out' when enough information has been determined to make a decision. However, given the statistics of incoming signals, different orders of operation can have vastly different expected execution times. Using Synchronous Reactive models, it is possible to model this situation without explicitly deciding the order of the signal processing operations. Based on expected statistics of incoming signals and signal processing computation times and a particular decision function, determine a scheduling algorithm that finds minimum expected execution time before a decision is made. How does the problem change if multiple signal processing algorithms can be computed simultaneously?