*banner
 

Partial Evaluation for Optimized Compilation of Actor-Oriented Models
Gang Zhou

Citation
Gang Zhou. "Partial Evaluation for Optimized Compilation of Actor-Oriented Models". PhD thesis, University of California, Berkeley, May, 2008.

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/.

Electronic downloads

Citation formats  
  • HTML
    Gang Zhou. <a
    href="http://chess.eecs.berkeley.edu/pubs/774.html"
    ><i>Partial Evaluation for Optimized Compilation of
    Actor-Oriented Models</i></a>, PhD thesis, 
    University of California, Berkeley, May, 2008.
  • Plain text
    Gang Zhou. "Partial Evaluation for Optimized
    Compilation of Actor-Oriented Models". PhD thesis, 
    University of California, Berkeley, May, 2008.
  • BibTeX
    @phdthesis{Zhou08_PartialEvaluationForOptimizedCompilationOfActorOriented,
        author = {Gang Zhou},
        title = {Partial Evaluation for Optimized Compilation of
                  Actor-Oriented Models},
        school = {University of California, Berkeley},
        month = {May},
        year = {2008},
        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/.},
        URL = {http://chess.eecs.berkeley.edu/pubs/774.html}
    }
    

Posted by Christopher Brooks on 13 Nov 2010.
Groups: ptolemy
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

You are not logged in 
©2002-2017 Chess