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

A Hierarchical Multiprocessor Scheduling System for DSP Applications

Presented at the Twenty-Ninth Annual Asilomar Conference on Signals, Systems, and Computers
October 1995

José Luis Pino
Dept. of Electrical Engineering and Computer Sciences
University of California, Berkeley

Shuvra S. Bhattacharyya
Semiconductor Research Laboratory
Hitachi America, Ltd.

Edward A. Lee
Dept. of Electrical Engineering and Computer Sciences
University of California, Berkeley

Abstract

This paper discusses a hierarchical scheduling framework which reduces the complexity of scheduling synchronous dataflow (SDF) graphs onto multiple processors. The core of this framework is a clustering algorithm that decreases the number of nodes before expanding the SDF graph into a precedence directed acyclic graph (DAG). 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. We have developed the SDF composition theorem for testing if a clustering step is valid. The advantages of this framework are demonstrated with several practical, real-time examples.

Proceedings
Lecture Slides

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