Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

   

2008 Research Summary

Partial Evaluation for Optimized Compilation of Actor-Oriented Models

View Current Project Information

Man-Kit Leung, Gang Zhou, Christopher Brooks and Edward A. Lee

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 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 could be automated; partial evaluation [1] is a 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 [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.

[1]
N. D. Jones, C. K. Gomard, and P. Sestoft, Partial Evaluation and Automatic Program Generation, Prentice-Hall, June 1993.
[2]
E. Kohler, R. Morris, and B. Chen, "Programming Language Optimizations for Modular Router Configurations," ACM SIGPLAN Notices, Vol. 37, No. 10, October 2002, pp. 251-263.