Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2009 Research Summary

PTIDES: Programming Temporally Integrated Distributed Embedded Systems

View Current Project Information

Yang Zhao1, Slobodan Matic, Thomas Huining Feng, Jia Zou and Edward A. Lee

Center for Hybrid and Embedded Software Systems (CHESS), National Science Foundation 0720882, National Science Foundation 0720841, California MICRO, Agilent Technologies, Robert Bosch GmBH, HSBC, Lockheed-Martin ATL, National Instruments, Toyota, Army Research Office W911NF-07-2-0019 and Air Force Office of Scientific Research FA9550-06-0312

The Programming Temporally Integrated Distributed Embedded Systems (PTIDES) project focuses on developing programming models for real-time distributed systems and studying algorithms that can statically check whether a model meets the given deadline requirements over a network of distributed systems.

This programming model exploits time synchronization protocols such as NTP and IEEE 1588, which provide a global notion of physical time in distributed systems. PTIDES uses discrete-event (DE) models as programming specifications for distributed real-time systems. In the DE model of computation, software components communicate via time-stamped events. We refer to the values of the time stamps as “model time.” In [1], we use model time to define execution semantics and add constraints that bind certain model time events to physical time. We limit the relationship between model time and physical time to those circumstances where this relationship is needed, and provide an execution model that permits out of order processing of events without sacrificing determinacy and without requiring backtracking.

A simulation environment and a run time system have been implemented to experiment with PTIDES systems. The simulation environment [2] uses the Ptolemy II framework to model PTIDES systems and simulate those using worst case execution assumptions. Schedulers for different platform characteristics are studied.

A backtracking mechanism [3] has been implemented, not to ensure the processing order of time-stamped events as in the Time Warp approach, but to tolerate failures in the execution, such as failure in upstream components to meet deadlines and unexpected hardward errors.

The PTIDES run-time environment is built on top of Flexotasks [4], which is an actor-based platform that provides real-time properties through its specialized Java Virtual Machine. PTIDES with Flexotask enable users to write applications in a high-level language such as Java, while guaranteeing the applications' real-time behavior. An integration between PTIDES and traditional real-time scheduling methods such as earliest-deadline-first has also been made to study the connection between PTIDES and real-time scheduling schemes previously achieved in the community.

In this effort we also address event processing performance with respect to other distributed discrete event approaches that can be applied in a similar setting. In particular, we compare PTIDES with more classical conservative distributed discrete-event implementations with respect to event processing rates and feasibility of real-time constraints. Conservative methods (known as Chandy and Misra methods) use null messages between distributed platforms for notification that it is safe to advance model time. This produces considerable network traffic when low end-to-end latency is needed. In this work we demonstrate how this can be avoided using our PTIDES programming model. The procedure is experimentally evaluated on a distributed setup with standard software and networking components.

A key challenge is to provide schedulability analysis for the PTIDES programming model, which would allow for a static analysis of the deployability of a given application. Our current research includes improving the simulation environment and execution platform to explore the PTIDES programming model and to define the schedulability analysis given a set of resources as well as timing requirements.

Y. Zhao, J. Liu, and E. A. Lee, "A Programming Model for Time-Synchronized Distributed Real-Time Systems," Proceedings of the 13th IEEE Real-Time and Embedded Technology and Applications Symposium, Bellevue, WA, April 2007.
P. Derler, T. H. Feng, E. A. Lee, S. Matic, H. D. Patel, Y. Zhao, and J. Zou, "PTIDES: A Programming Model for Distributed Real-Time Embedded Systems," UC Berkeley EECS Technical Report No. EECS-2008-72, May 2008.
T. H. Feng and E. A. Lee, "Real-Time Distributed Discrete-Event Execution with Fault Tolerance," Proceedings of the 14th IEEE Real-Time and Embedded Technology and Applications Symposium, St. Louis, MO, April 2008.
J. Auerbach, D. F. Bacon, R. Guerraoui, J. H. Spring, and J. Vitek, "Flexible Task Graphs: A Unified Restricted Thread Programming Model for Java," SIGPLAN Notices, Vol. 43, No. 7, June 2008.