A Hierarchical Multiprocessor Scheduling Framework for Synchronous Dataflow Graphs

J.L. Pino and S.S. Bhattacharyya and Edward A. Lee

EECS Department, University of California, Berkeley

Technical Report No. UCB/ERL M95/36

1995

This publication is archived. It is kept only for reference purposes, so it is no longer being updated and may not meet accessibility standards. If you need this content in a different format, please email webteam@eecs.berkeley.edu.

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/Archive/ERL-95-36.pdf

This paper discusses a hierarchical scheduling framework to reduce the complexity of scheduling synchronous dataflow (SDF) graphs onto multiple processors. The core of this framework is a clustering algorithm that reduces the number of nodes before expanding the SDF graph into a precedence DAG (directed acyclic graph). The internals of the clusters are then scheduled with uniprocessor SDF schedulers which can optimize for memory usage. The clustering is done in such a manner as to leave ample parallelism exposed for the multiprocessor scheduler. The advantages of this framework are demonstrated with several practical, real-time examples.

BibTeX citation:

@techreport{Pino:M95/36,
    Author= {Pino, J.L. and Bhattacharyya, S.S. and Lee, Edward A.},
    Title= {A Hierarchical Multiprocessor Scheduling Framework for Synchronous Dataflow Graphs},
    Year= {1995},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/2770.html},
    Number= {UCB/ERL M95/36},
    Abstract= {This paper discusses a hierarchical scheduling framework to reduce the complexity of scheduling synchronous dataflow (SDF) graphs onto multiple processors. The core of this framework is a clustering algorithm that reduces the number of nodes before expanding the SDF graph into a precedence DAG (directed acyclic graph). The internals of the clusters are then scheduled with uniprocessor SDF schedulers which can optimize for memory usage. The clustering is done in such a manner as to leave ample parallelism exposed for the multiprocessor scheduler. The advantages of this framework are demonstrated with several practical, real-time examples.},
}

EndNote citation:

%0 Report
%A Pino, J.L. 
%A Bhattacharyya, S.S. 
%A Lee, Edward A. 
%T A Hierarchical Multiprocessor Scheduling Framework for Synchronous Dataflow Graphs
%I EECS Department, University of California, Berkeley
%D 1995
%@ UCB/ERL M95/36
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/2770.html
%F Pino:M95/36