Main Menu/Search/Help
PUBLICATIONS of the DSP DESIGN GROUP and the PTOLEMY PROJECT

A Hierarchical Multiprocessor Scheduling Framework for Synchronous Dataflow Graphs

José Luis Pino, Shuvra S. Bhattacharyya and Edward A. Lee
UCB/ERL M95/36, May 30, 1995

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.

A quicktime movie(38K) is available to illustrate the SDF composition theorem precedence shift conditions.

On the left side of the movie, an SDF graph is shown where the number of delays are changing on some of the arcs. On the right side of the movie, the corresponding precedence graph is shown.

The SDF arc on which the delays are depicted in red is being tested for deadlock using the precedence shift conditions. If the current number of delays yields a deadlock, the corresponding cycle in the precedence graph is highlighted in red.

Send comments to José Luis Pino at pino@eecs.berkeley.edu.