*banner
 

Compositionality in Synchronous Data Flow: Modular Code Generation from Hierarchical SDF Graphs
Stavros Tripakis, Dai Bui, Bert Rodiers, Edward A. Lee

Citation
Stavros Tripakis, Dai Bui, Bert Rodiers, Edward A. Lee. "Compositionality in Synchronous Data Flow: Modular Code Generation from Hierarchical SDF Graphs". ACM Transactions on Embedded Computing Systems, 12(3), March 2013; This work was supported in part by the Center for Hybrid and Embedded Software Systems (CHESS) at UC Berkeley, which receives support from the National Science Foundation (NSF awards \#0720882 (CSR-EHS: PRET), \#0931843 (CPS: Large: ActionWebs), and \#1035672 (CPS: Medium: Ptides)), the Naval Research Laboratory (NRL \#N0013-12-1-G015), and the following companies: Bosch, National Instruments, and Toyota.

Abstract
Hierarchical SDF models are not compositional: a composite SDF actor cannot be represented as an atomic SDF actor without loss of information that can lead to rate inconsistency or deadlock. Motivated by the need for incremental and modular code generation from hierarchical SDF models, we introduce in this paper DSSF profiles. DSSF (Deterministic SDF with Shared FIFOs) forms a compositional abstraction of composite actors that can be used for modular compilation. We provide algorithms for automatic synthesis of non monolithic DSSF profiles of composite actors given DSSF profiles of their sub-actors. We show how different trade-offs can be explored when synthesizing such profiles, in terms of compactness (keeping the size of the generated DSSF profile small) versus reusability (maintaining necessary information to preserve rate consistency and deadlock-absence) as well as algorithmic complexity. We show that our method guarantees maximal reusability and report on a prototype implementation.

Electronic downloads

Citation formats  
  • HTML
    Stavros Tripakis, Dai Bui, Bert Rodiers, Edward A. Lee.
    <a
    href="http://chess.eecs.berkeley.edu/pubs/986.html"
    >Compositionality in Synchronous Data Flow: Modular Code
    Generation from Hierarchical SDF Graphs</a>,
    <i>ACM Transactions on Embedded Computing
    Systems</i>, 12(3), March 2013; This work was
    supported in part by the Center for Hybrid and Embedded
    Software Systems (CHESS) at UC Berkeley, which receives
    support from the National Science Foundation (NSF awards
    \#0720882 (CSR-EHS: PRET), \#0931843 (CPS: Large:
    ActionWebs), and \#1035672 (CPS: Medium: Ptides)), the Naval
    Research Laboratory (NRL \#N0013-12-1-G015), and the
    following companies: Bosch, National Instruments, and Toyota.
  • Plain text
    Stavros Tripakis, Dai Bui, Bert Rodiers, Edward A. Lee.
    "Compositionality in Synchronous Data Flow: Modular
    Code Generation from Hierarchical SDF Graphs".
    <i>ACM Transactions on Embedded Computing
    Systems</i>, 12(3), March 2013; This work was
    supported in part by the Center for Hybrid and Embedded
    Software Systems (CHESS) at UC Berkeley, which receives
    support from the National Science Foundation (NSF awards
    \#0720882 (CSR-EHS: PRET), \#0931843 (CPS: Large:
    ActionWebs), and \#1035672 (CPS: Medium: Ptides)), the Naval
    Research Laboratory (NRL \#N0013-12-1-G015), and the
    following companies: Bosch, National Instruments, and Toyota.
  • BibTeX
    @article{TripakisBuiRodiersLee13_CompositionalityInSynchronousDataFlowModularCodeGeneration,
        author = {Stavros Tripakis and Dai Bui and Bert Rodiers and
                  Edward A. Lee},
        title = {Compositionality in Synchronous Data Flow: Modular
                  Code Generation from Hierarchical SDF Graphs},
        journal = {ACM Transactions on Embedded Computing Systems},
        volume = {12},
        number = {3},
        month = {March},
        year = {2013},
        note = {This work was supported in part by the Center for
                  Hybrid and Embedded Software Systems (CHESS) at UC
                  Berkeley, which receives support from the National
                  Science Foundation (NSF awards \#0720882 (CSR-EHS:
                  PRET), \#0931843 (CPS: Large: ActionWebs), and
                  \#1035672 (CPS: Medium: Ptides)), the Naval
                  Research Laboratory (NRL \#N0013-12-1-G015), and
                  the following companies: Bosch, National
                  Instruments, and Toyota.},
        abstract = {Hierarchical SDF models are not compositional: a
                  composite SDF actor cannot be represented as an
                  atomic SDF actor without loss of information that
                  can lead to rate inconsistency or deadlock.
                  Motivated by the need for incremental and modular
                  code generation from hierarchical SDF models, we
                  introduce in this paper DSSF profiles. DSSF
                  (Deterministic SDF with Shared FIFOs) forms a
                  compositional abstraction of composite actors that
                  can be used for modular compilation. We provide
                  algorithms for automatic synthesis of non
                  monolithic DSSF profiles of composite actors given
                  DSSF profiles of their sub-actors. We show how
                  different trade-offs can be explored when
                  synthesizing such profiles, in terms of
                  compactness (keeping the size of the generated
                  DSSF profile small) versus reusability
                  (maintaining necessary information to preserve
                  rate consistency and deadlock-absence) as well as
                  algorithmic complexity. We show that our method
                  guarantees maximal reusability and report on a
                  prototype implementation.},
        URL = {http://chess.eecs.berkeley.edu/pubs/986.html}
    }
    

Posted by Stavros Tripakis on 22 Apr 2013.
Groups: actionwebs
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.

©2002-2018 Chess