1996 Research Summaries for the Ptolemy Project
An Adobe Acrobat PDF version of this
summary is available.
Hierarchical Static Scheduling of Dataflow Graphs onto Multiple
Processors
| Researcher: | José Luis Pino
|
|---|
| Advisor: | Edward A. Lee
|
|---|
| Sponsors: | AT&T Bell Labs Fellowship, ARPA(RASSP) F33615-93-C-1317 and the Ptolemy Project |
|---|
The goal of this project is to reduce the complexity of scheduling
synchronous dataflow (SDF) [1] graphs
onto multiple processors. SDF semantics have proven to be useful in
describing multirate digital signal processing algorithms. Furthermore,
compile-time scheduling is possible from SDF block diagram descriptions.
Many synchronous dataflow schedulers are available for both uniprocessor
and multiprocessor architectures. Those for uniprocessor systems optimize
for costs such as code and buffer memory usage while multiprocessor
schedulers optimize the makespan of the application.
We are implementing a scheduling framework that can make use of
heterogeneous schedulers. The core of this framework is a clustering
technique that reduces the number of actors before expanding the SDF graph
into an directed acyclic graph [2]. 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.
This framework has been tested on a number of practical applications
detailed in [2] and [3]. One of the applications, a 4-QAM
modem, is shown in figure 1. For this modem, the use of our framework
realized a 90x speedup in scheduling time with an 60x reduction of memory
usage.
- E. A. Lee and D. G. Messerschmitt, ``Synchronous data flow,''
Proceedings of the IEEE, vol. 75, no. 9, 1987, p. 1235-1245.
- J. L. Pino, S.S. Bhattacharyya and E. A. Lee, A Hierarchical
Multiprocessor Scheduling Framework for Synchronous Dataflow Graphs,
UCB/ERL M95/36, May 30, 1995.
- J. L. Pino, S. S. Bhattacharyya and E. A. Lee, ``A Hierarchical
Multiprocessor Scheduling System for DSP Applications,'' Proc. IEEE
Asilomar Conference on Signals, Systems, and Computers, Pacific
Grove, CA, Oct. 29 - Nov. 1, 1995.
Send comments to
José Luis Pino
at pino@eecs.berkeley.edu.