Home Page

Contents

  • Introduction
    • Ptolemy
    • Ptides
    • Model Transformation
  • Google Summer of Code 2008
    • Contact
    • Instructions for Student Applicants
    • Project Ideas

Introduction

Ptolemy

The Ptolemy project studies modeling, simulation, and design of concurrent, real-time, embedded systems. The focus is on assembly of concurrent components. The key underlying principle in the project is the use of well-defined models of computation that govern the interaction between components. A major problem area being addressed is the use of heterogeneous mixtures of models of computation. A software system called Ptolemy II is being constructed in Java. Ptolemy II differs from other commonly used graphical block-diagram languages in that they typically support only one model of computation. In addition, Ptolemy II is a more open architecture in that its infrastructure is open source, and the interfaces to the core mechanisms in the software are published and documented.

Ptides

The Programming temporally integrated distributed embedded systems (PTIDES) concurrency model uses discrete-event models as programming specifications for distributed real-time systems and extends discrete-event models with the capability of mapping certain events to physical time. We use model time to define execution semantics and add constraints that bind certain model time events to physical time. We limit the relationship of model time to physical time to only those circumstances where this relationship is needed. This approach enables an execution model that permits out of order processing of events without sacrificing determinacy and without requiring backtracking.

Model Transformation

The model transformation technique based on graph rewriting helps to systematically modify and manage complex actor-based models. A transformation rule specifies a "atomic" transformation that can be applied to a model with a part of it matching to the pattern of the transformation rule. By combining transformation rules in a Ptolemy model, more complicated transformation can be created. Applications of model transformation include but are not limited to model optimization and simplification, design reuse, behavior-preserving conversion between formalisms, etc.

Google Summer of Code 2008

Contact

A preferred means of communication with us during the application period would be the PtolemyGSoC group at Google Groups. That way, everyone can benefit from the discussion.
http://groups.google.com/group/ptolemygsoc
If you really need to send a private message to us, please email mentors Slobodan Matic (slobicus.matic@gmail.com) or Thomas Feng (ucbfeng@gmail.com).

Instructions for Student Applicants

We do not use a specific application template for this program. However, this is what we will be looking for in an application:
  • Summary of your previous programming projects (open-source/class/research).
  • Summary of your university-level education.
  • What interests you about our projects? What would you like to learn or improve?
  • What other activities (exams, vacation, etc.) you plan for the summer? How much of your time you think you can devote to project per week, per day?

Project Ideas

Project Idea 1

The best code developers are typically users first. Select a discrete-event system or application of your choice and model it in Ptolemy. In discrete-event models, the components interact via signals that consist of time-stamped events. Here are some ideas: in Ptolemy, Timing Paradox or Wireless Networks, and from the web, Sound Processing or Algorithmic Trading. Start with Ptolemy Tutorial. Think about using Discrete-Event, Modal or Distributed Discrete-Event models of computation.
We are currently building Ptides model of computation for Real-time and Distributed systems based on the discrete-event model. A preliminary version will be available during summer. Build Ptides components that are not yet supported. Start with Ptolemy Design Document(Vol.3, Chap.1,4,7). Some ideas include implementing and testing different event schedulers or modeling standard networking components within Ptides. The created models will both test the infrastructure and user interfaces of Ptides and serve as examples for other models.
  • Further Reading: Real-Time Computing, Ptides
  • Skills: Block-diagram language (e.g. Matlab) or Java [recommended]
  • Level: Beginning - Advanced
  • Benefits to the Student: Model and study properties of a system of interest. Get to know and build upon Ptolemy infrastructure. Learn to use source version control systems.
  • Benefits to the Community: Expand open computational models and open-architecture design frameworks.
  • Comments: More than one student.

Project Idea 2

There are a lot of open-source discrete-event simulation frameworks. Much less work has been done in adapting these models as an execution platform for embedded software. Such a platform has to take into account real-time interaction with the environment. In this project a student could adapt the current implementation of Ptolemy Discrete-Event or Ptides simulation frameworks. This project will not address the distributed aspects of Ptides models. The student would program in Java and test on Red Hat Enterprise Linux. We plan to experiment with the Realtime component of the Red Hat MRG framework. If standard Java programming model is used, the student will have access to the IBM WebSphere Real Time platform that performs automatic garbage collection. Other approaches could use more difficult programming models according to the Real-Time Specification for Java. Debug using Eclipse based Tuning Fork visualization tool. Test on a simple discrete-event application of interest.
  • Further Reading: MRG Realtime, RTSJ, Ptides (from slide 32)
  • Skills: Java [required]
  • Level: Intermediate
  • Benefits to the Student: Learn high-level real-time programming in Java. Learn about discrete-event model semantics and implementation. Learn to use source version control systems.
  • Benefits to the Community: Advance real-time programming under Java and Linux.
  • Comments: Visit to UC Berkeley recommended.

Project Idea 3

An idea for this project would be to implement efficient event queue structures and the scheduler for real-time processing of events. A higher goal would be to implement the event scheduler for the Ptides model of concurrency currently being studied in the Ptolemy group. However, this project will not address the distributed character of Ptides systems. Some information about the Java software architecture of the event queue used within the Ptolemy can be found in (Vol.2, Chap.1). First implementation attempts during the summer would not be as difficult. In this project we will program in C most likely using Red Hat Enterprise Linux. We plan to experiment with the Realtime component of the Red Hat MRG framework. The event scheduler will use high resolution timer infrastructure and should result in tight integration with the Linux task scheduler. Other approaches may build upon recent open-source real-time projects, such as S.Ha.R.K.: Soft Hard Real-Time Kernel (e.g. for dynamic priority schedulers) or OCERA: Open Components for Embedded Real-time Applications (e.g. for resource reservation). Time permitting, test the implementation on a sound synthesis/processing application.
  • Further Reading: MRG Realtime, Linux: Process Scheduling, Calendar queues
  • Skills: C [required]
  • Level: Intermediate - Advanced
  • Benefits to the Student: Learn to program in real-time variants of Linux. Learn about discrete-event model semantics and implementation. Learn to use source version control systems.
  • Benefits to the Community: Expand the space of open-source real-time Linux frameworks and applications.
  • Comments: Visit to UC Berkeley recommended. High importance to us.

Project Idea 4

The number of distributed event processing applications is increasing. Start with the discussion of related implementation problems for a distributed discrete-event (DDE) example. Ptolemy also comes with the DDE domain. The objective of this project is to build infrastructure for distributed event processing that will subsequently be used in other projects. A student could implement discrete-event simulator distributed over locally connected servers. S/he would program in C or C++ most likely using Red Hat Enterprise Linux. We plan to experiment with the Messaging component of the Red Hat MRG framework that implements open standard protocol AMQP. The other approach in a similar setting could build upon recent open-source projects such as DREAM: Distributed Real-time Embedded Analysis Method. Another interesting idea with research potential would be to build an efficient simulator on a multi-core processor. This approach could leverage related enhancements of 2.6 Linux kernels. Test on a simple distributed discrete-event application of interest.
  • Further Reading: Parallel Discrete Event Simulation, Multi-Core and Linux
  • Skills: C or C++ [required]
  • Level: Intermediate - Advanced
  • Benefits to the Student: Learn to program distributed and/or parallel applications. Learn about discrete-event model semantics and implementation. Learn to use source version control systems.
  • Benefits to the Community: Increase the efficiency of open-source parallel discrete-event simulation/execution platforms.
  • Comments: More than one student. Visit recommended. Research potential.

Project Idea 5

  • Wikipedia Keywords: Discrete-Event, Code Generation
  • Mentors: Man-Kit Leung / Slobodan Matic
  • Title: C Code Generation for DE or Ptides Models
  • Technical Details:
The Ptolemy group is developing a code generator that uses template files to build C code from Ptolemy models. The current template effort synthesizes C code from certain Ptolemy II models (SDF, FSM and HDF). Our approach defines "helper" classes associated with Ptolemy II actors (i.e. model components) that define the C code implementation for actors.
In this project we would like to build the same feature for the DE models. In the first iteration all models could use the same (manually written) event scheduler and user would provide C code functionality for all actors. More efficient implementations will have to reduce the overhead introduced by high level abstraction of models. To address this we use partial evaluation as an optimized compilation technique for actor-oriented models. For more details see Ptolemy Design Document (Vol.2, Chap.7).
Test the implementation on simple demo models with a limited actor library. This project may lead to code generation for real-time Ptides models and other research efforts.
  • Further Reading: VIPTOS, A Retargetable Optimizing Java-to-C Compiler for Embedded Systems
  • Skills: Java, C [required]
  • Level: Intermediate - Advanced
  • Benefits to the Student: Learn compilation and code generation techniques for graphical block-oriented languages. Learn about discrete-event model semantics and implementation. Learn to use source version control systems.
  • Benefits to the Community: Broaden the space of open-source C code generators from higher level languages.
  • Comments: Research potential.

Project Idea 6

Compute WCET as the maximum execution time on all the execution paths of an actor, assuming that the WCET of atomic operations used by the actor, such as library function calls, is given. Use jCute to discover all feasible execution paths of the actor's fire() method, which is invoked on each firing. Combine the information obtained by separately analyzing each path with a max-plus algebra to produce the WCET of a firing of the actor.
  • Further Reading: jCute - A execution path analysis tool for Java, Max-plus algebra
  • Skills: Java [required]
  • Level: Intermediate
  • Benefits to the Student: Learn to use an automatic path exploration tool, and learn program analysis with path exploration.
  • Benefits to the Community: Provide a mechanism to automatically analyze WCET for certain kind of structured Java code, which is essential to real-time guarantees.

Project Idea 7

  • Wikipedia Keywords: Model Transformation, Subgraph Isomorphism Problem
  • Mentors: Christopher Brooks / Thomas Feng
  • Title: An extension to the current model transformation tool in the Ptolemy framework to support imprecise matching to the user-defined graph pattern.
  • Technical Details:
It is very useful to specify a pattern that allows structural variance in it, such as a one that matches a variable number of interconnected nodes. The current implementation does not support this because the number of nodes must be known and fixed at design time. The student will develop a visual syntax for the pattern designer to specify this variance in the structure. The student will also extend the model transformation tool to perform pattern matching on this kind of specifications, and apply transformation on the matched model parts.
  • Further Reading: Model Transformation in Ptolemy
  • Skills: Java [required]
  • Level: Intermediate
  • Benefits to the Student: Learn the basic techniques for model transformation and graph rewriting. Creatively develop a useful algorithm.
  • Benefits to the Community: Develop a more flexible pattern matching algorithm for graph rewriting.
  • Comments: Research potential.

Project Idea 8

  • Wikipedia Keywords: Model Transformation, Subclassing, Actor Model
  • Mentors: Christopher Brooks / Thomas Feng
  • Title: Bring the concept of object-oriented programming (OOP) to the modeling world with actor-oriented subclassing.
  • Technical Details:
Model transformation based on graph transformation is a well-studied technique. However, it is creative to apply this technique to effectively reuse model designs in the sense of subclassing. Often times, a previous design needs to be slightly modified before it can be used in a new context. If the desired modification affects the structure of the design, then model transformation is a powerful backend to rely on. The student will extend the current implementation of model subclassing (which does not take advantage of model transformation) and implement extra checks to ensure properties to be preserved by a subclass model obtained by transformation. Example properties that the student will work on include input/output interface, expected data types of the input/output, behavioral properties expressed with interface automata, etc.

Project Idea 9

  • Wikipedia Keywords: Static Code Analysis
  • Mentors: Man-kit Leung / Hiren Patel
  • Title: An environment for program analysis on C programs generated from the Ptolemy Code Generation Framework.
  • Technical Details:
Traditional embedded programming almost always uses C as an entry language. This however, is tedious and difficult to implement correctly when applications mandate a certain degree of concurrency. As a result, the Ptolemy framework provides higher-level models of computation that aid in better managing the concurrency inherent in embedded system applications. It also provides a code generation framework to C from the Process Network and Synchronous Data Flow models of computation. Since these models of computation are untimed, no notion of time is inserted into the generated C code. However, many embedded systems have real-time requirements that need to be met. For eventual implementation on a platform, it is necessary to do program analysis on the generated C code to estimate execution bounds for real-time embedded systems. We'll focus on a potential SPARC v8 based architecture that will serve as a target platform for code generation from the Ptolemy Framework
  • Further Reading:
  • Skills: C [required], Static analysis experience [helpful]
  • Level: Advanced
  • Benefits to the Student: Extend understanding of program analysis on source compiled by GCC.
  • Benefits to the Community: Extension for Ptolemy's code generation framework for providing execution bounds for particular instruction set architectures for model-based embedded programming.
  • Comments: Research potential.