A Hierarchical Multiprocessor Scheduling Framework for Synchronous Dataflow Graphs

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

EECS Department
University of California, Berkeley
Technical Report No. UCB/ERL M95/36
May 1995

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/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},
    Institution = {EECS Department, University of California, Berkeley},
    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