1996 Research Summaries for the Ptolemy Project

Hierarchical Nesting of Esterel Modules in Dataflow Graphs

Researcher:Stephen A. Edwards
Advisor:Edward A. Lee
Sponsors:National Science Foundation Fellowship, ARPA and the US Air Force (under the RASSP program, contract F33615-93-C-1317) and the Ptolemy project.
Dataflow models have proven effective for representing digital signal processing systems, but they can be clumsy for applications that require substantial control flow. Synchronous/reactive languages, in particular Esterel [1], provide powerful control abstractions, and are well-suited to describing control-dominated systems. However, existing Esterel compilers need complete information about the system and must perform expensive, global consistency checks.

Esterel modules share certain properties with dataflow actors. They react to events at their inputs, and produce events on their outputs. But to maintain determinacy, dataflow actors have much tighter constraints on how they can interact with input and output signals. For example, they cannot test an input for the presence of an event. Ptolemy's Boolean Dataflow domain (described by Buck [2]) relies on these properties to efficiently compile a graph. Since Esterel modules are not guaranteed to obey these constraints, embedding Esterel efficiently within Boolean dataflow is nontrivial.

The objective of this project is to identify methods for efficiently embedding Esterel's semantics into Boolean Dataflow actors. Combining the two worlds will allow sophisticated control-flow to be specified and easily compiled in a dataflow environment well-suited to digital signal processor applications.

  1. Gerard Berry and Georges Gonthier, ``The Esterel synchronous programming language: design, semantics, implementation,'' Science of Computer Programming, 19(2):87-152, 1992.
  2. Joseph Tobin Buck, Scheduling Dynamic Dataflow Graphs with Bounded Memory using the Token Flow Model, Ph.D. thesis, University of California, Berkeley, 1993. (Also available as UCB/ERL M93/69)
Send comments to Stephen Anthony Edwards at sedwards@eecs.berkeley.edu.