Partial Evaluation for Optimized Compilation of Actor-oriented Models

The Ptolemy project advocates an actor-oriented approach for embedded system design, where actors are concurrent components (we use “actor” and “component” interchangeably in this context) that communicate through ports and interact according to a common pattern of interaction. Ptolemy II is a software lab for experimenting with multiple concurrency formalisms for embedded system design. Many features in Ptolemy II contribute to the ease of its use as a rapid prototyping environment. In particular, modular components make systems more flexible and extensible. Different compositions of the same components can implement different functionality. However, component designs are often slower than purpose-built code. The cost of inter-component communication through the interface introduces overhead, and generic components are highly parameterized for the reusability and thus less efficient.

To regain the efficiency for the implementation, the users could write big, coarse-grained components to reduce inter-component communication, and write highly specialized components rather than general ones. These solutions come at the cost of flexibility and extensibility and are therefore not acceptable. There would be no problem, however, if the whole process can be automated and partial evaluation [1] is the mechanism for doing that. In the past partial evaluation has been mostly used for general purpose software. Recently partial evaluation has begun to see its use in the embedded world, e.g, see [2]. In our research partial evaluation is used as a code generation technique, which is really a compilation technique for transforming an actor-oriented model into the target code while preserving the model’s semantics. However, compared with traditional compiler optimization, partial evaluation for embedded software works at the component level and heavily leverages the domain-specific knowledge. Through model analysis, the tool can discover data type, buffer size, parameter value, model structure and model execution schedule, and then partially (pre)evaluate all the known information to reach a very efficient implementation. The end result is that the benefit offered by the high level abstraction comes with (almost) no performance penalty.

A prototype has been realized and will be shipped with the release of Ptolemy II 6.0 in Fall 2006. We are working to improve the system and further explore additional optimization opportunities.

[1] Neil D. Jones, Carsten K. Gomard, and Peter Sestoft. Partial Evaluation and Automatic Program Generation. Prentice-Hall, June 1993.

[2] Kohler E, Morris R, Benjie Chen, "Programming language optimizations for modular router configurations," ACM. SIGPLAN Notices, vol.37, no.10, Oct. 2002, pp. 251-63.

Last updated 09/29/06