Partial Evaluation for Optimized Compilation of Actor-Oriented Models
Gang Zhou
EECS Department, University of California, Berkeley
Technical Report No. UCB/EECS-2008-53
May 16, 2008
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-53.pdf
One major achievement of traditional computer science is systematically abstracting away the physical world. The Von Neumann model provides a universal abstraction for sequential computation. The concept is so simple and powerful for transformational systems (vs. reactive systems) that any traditional program can run regardless of underlying platform ---- whether it is a supercomputer or a desktop. Embedded software systems, however, engage the physical world. Time, concurrency, liveness, continuums and reactivity must be remarried to computation. In order to reason about these properties, a programming model must be able to express these properties directly.
The traditional techniques for doing concurrent programming on top of sequential programming languages like C use threads complemented with synchronization mechanisms like semaphores and mutual exclusion locks. These methods are at best retrofits to the fundamentally sequential formalism and are hard to understand, difficult to debug, brittle and error-prone.
Actor-oriented design presents a high level abstraction for composing concurrent components. There is a rich variety of concurrency formalisms that span the whole spectrum from most expressive to most analyzable. In particular, I will focus on one particular model of computation called heterochronous dataflow (HDF) which strikes a nice balance between expressiveness and analyzability.
However, high level abstraction often introduces overhead and results in slower systems. In component based design, generic components are highly parameterized for reusability and thus are less efficient. The well-defined interface between components results in flexible composition but increases the cost of inter-component communication through the interface.
In the second part of this thesis, I will address the problem of generating an efficient implementation from a high level specification. I use partial evaluation as an optimized compilation technique for actor-oriented models. Compared with traditional compiler optimization, partial evaluation for embedded software works at the component level and heavily leverages domain-specific knowledge. Through model analysis---the counterpart of binding-time analysis in the use of partial evaluation for general purpose software, the tool can discover the static parts in the model including data types, buffer sizes, parameter values, model structures and execution schedules, etc. and then exploit the already known information to reach a very efficient implementation. I use a helper-based mechanism, which leads to flexible and extensible code generation framework. The end result is that the benefit offered by high level abstraction comes with (almost) no performance penalty.
The code generation framework described in this dissertation has been released in open source as part of Ptolemy II and can be downloaded from http://ptolemy.org/.
Advisors: Edward A. Lee
BibTeX citation:
@phdthesis{Zhou:EECS-2008-53,
Author= {Zhou, Gang},
Title= {Partial Evaluation for Optimized Compilation of Actor-Oriented Models},
School= {EECS Department, University of California, Berkeley},
Year= {2008},
Month= {May},
Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-53.html},
Number= {UCB/EECS-2008-53},
Abstract= {One major achievement of traditional computer science is systematically abstracting away the physical world. The Von Neumann model provides a universal abstraction for sequential computation. The concept is so simple and powerful for transformational systems (vs. reactive systems) that any traditional program can run regardless of underlying platform ---- whether it is a supercomputer or a desktop. Embedded software systems, however, engage the physical world. Time, concurrency, liveness, continuums and reactivity must be remarried to computation. In order to reason about these properties, a programming model must be able to express these properties directly.
The traditional techniques for doing concurrent programming on top of sequential programming languages like C use threads complemented with synchronization mechanisms like semaphores and mutual exclusion locks. These methods are at best retrofits to the fundamentally sequential formalism and are hard to understand, difficult to debug, brittle and error-prone.
Actor-oriented design presents a high level abstraction for composing concurrent components. There is a rich variety of concurrency formalisms that span the whole spectrum from most expressive to most analyzable. In particular, I will focus on one particular model of computation called heterochronous dataflow (HDF) which strikes a nice balance between expressiveness and analyzability.
However, high level abstraction often introduces overhead and results in slower systems. In component based design, generic components are highly parameterized for reusability and thus are less efficient. The well-defined interface between components results in flexible composition but increases the cost of inter-component communication through the interface.
In the second part of this thesis, I will address the problem of generating an efficient implementation from a high level specification. I use partial evaluation as an optimized compilation technique for actor-oriented models. Compared with traditional compiler optimization, partial evaluation for embedded software works at the component level and heavily leverages domain-specific knowledge. Through model analysis---the counterpart of binding-time analysis in the use of partial evaluation for general purpose software, the tool can discover the static parts in the model including data types, buffer sizes, parameter values, model structures and execution schedules, etc. and then exploit the already known information to reach a very efficient implementation. I use a helper-based mechanism, which leads to flexible and extensible code generation framework. The end result is that the benefit offered by high level abstraction comes with (almost) no performance penalty.
The code generation framework described in this dissertation has been released in open source as part of Ptolemy II and can be downloaded from http://ptolemy.org/.},
}
EndNote citation:
%0 Thesis %A Zhou, Gang %T Partial Evaluation for Optimized Compilation of Actor-Oriented Models %I EECS Department, University of California, Berkeley %D 2008 %8 May 16 %@ UCB/EECS-2008-53 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-53.html %F Zhou:EECS-2008-53