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
1995
http://www.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},
URL = {http://www.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://www.eecs.berkeley.edu/Pubs/TechRpts/1995/2770.html %F Pino:M95/36