Single Appearance Schedules for Synchronous Dataflow Programs

S.S. Bhattacharyya, S. Ha and Edward A. Lee

EECS Department
University of California, Berkeley
Technical Report No. UCB/ERL M93/4
January 1993

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/ERL-93-4.pdf

Synchronous Dataflow (SDF) provides block-diagram semantics that are well-suited to compiling multirate signal processing algorithms onto programmable signal processors. A key to this match is the ability to cleanly express iteration without overspecifying the execution order of blocks, thereby allowing efficient schedules to be constructed. Due to limited program memory, it is often desirable to translate the iteration in an SDF graph into groups of repetitive firing patterns so that loops can be constructed in the target code. This paper establishes fundamental topological relationships between iteration and looping in SDF graphs, and presents a hierarchical clustering strategy that probably synthesizes the most compact nested loop structure for a large class of applications.

BibTeX citation:

@techreport{Bhattacharyya:M93/4,
    Author = {Bhattacharyya, S.S. and Ha, S. and Lee, Edward A.},
    Title = {Single Appearance Schedules for Synchronous Dataflow Programs},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1993},
    Month = {Jan},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/2265.html},
    Number = {UCB/ERL M93/4},
    Abstract = {Synchronous Dataflow (SDF) provides block-diagram semantics that are well-suited to compiling multirate signal processing algorithms onto programmable signal processors. A key to this match is the ability to cleanly express iteration without overspecifying the execution order of blocks, thereby allowing efficient schedules to be constructed. Due to limited program memory, it is often desirable to translate the iteration in an SDF graph into groups of repetitive firing patterns so that loops can be constructed in the target code. This paper establishes fundamental topological relationships between iteration and looping in SDF graphs, and presents a hierarchical clustering strategy that probably synthesizes the most compact nested loop structure for a large class of applications.}
}

EndNote citation:

%0 Report
%A Bhattacharyya, S.S.
%A Ha, S.
%A Lee, Edward A.
%T Single Appearance Schedules for Synchronous Dataflow Programs
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/ERL M93/4
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/2265.html
%F Bhattacharyya:M93/4