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

• http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-53.html

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