Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Compositionality in Synchronous Data Flow: Modular Code Generation from Hierarchical SDF Graphs

Stavros Tripakis, Dai Bui, Bert Rodiers and Edward A. Lee

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2009-143
October 20, 2009

http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-143.pdf

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 deadlocks. Motivated by the need for incremental and modular code generation from hierarchical SDF models, we introduce in this paper DSSF profiles. This model 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 tradeoffs can be explored when synthesizing such profiles, in terms of modularity (keeping the size of the generated DSSF profile small) versus reusability (preserving information necessary to avoid deadlocks) as well as algorithmic complexity. We show that our method guarantees maximal reusability and report on a prototype implementation.


BibTeX citation:

@techreport{Tripakis:EECS-2009-143,
    Author = {Tripakis, Stavros and Bui, Dai and Rodiers, Bert and Lee, Edward A.},
    Title = {Compositionality in Synchronous Data Flow: Modular Code Generation from Hierarchical SDF Graphs},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2009},
    Month = {Oct},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-143.html},
    Number = {UCB/EECS-2009-143},
    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 deadlocks. Motivated by the need for incremental and modular code generation from hierarchical SDF models, we introduce in this paper DSSF profiles. This model 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 tradeoffs can be explored when synthesizing such profiles, in terms of modularity (keeping the size of the generated DSSF profile small) versus reusability (preserving information necessary to avoid deadlocks) as well as algorithmic complexity. We show that our method guarantees maximal reusability and report on a prototype implementation.}
}

EndNote citation:

%0 Report
%A Tripakis, Stavros
%A Bui, Dai
%A Rodiers, Bert
%A Lee, Edward A.
%T Compositionality in Synchronous Data Flow: Modular Code Generation from Hierarchical SDF Graphs
%I EECS Department, University of California, Berkeley
%D 2009
%8 October 20
%@ UCB/EECS-2009-143
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-143.html
%F Tripakis:EECS-2009-143