Main Menu/
Search/
Help
Keywords: Dataflow, Synchronous dataflow,
code generation for multiprocessor DSPs, graphical programming environments,
block diagram languages, compilers for DSPs,
optimizing memory requirements for DSPs, tools for rapid prototyping.
Joint Minimization of Code and Data for Synchronous Dataflow Programs,
in the Journal of Formal Methods in Systems Design, Vol. 11, No. 1, pp41-70,
July 1997.
by Praveen K. Murthy,
Shuvra S. Bhattacharyya, and
Edward A. Lee
![[PDF]](http://ptolemy.eecs
.berkeley.edu/papers/icons/PDF.gif)
![[PS]](http://ptolemy.eecs
.berkeley.edu/papers/icons/PS.gif)
ABSTRACT
This paper develops a dynamic programming algorithm for finding minimum
buffer size single appearance schedules for well-ordered graphs. The class
of R-schedules is defined and shown to always contain buffer-optimal
single appearance schedules. It is proven that the dynamic programming
algorithm can find an R-schedule that is buffer-optimal. Several extensions
are given to the basic algorithm to enable it to handle delays, a simple
form of buffer sharing, and to obtain optimal lexical orderings for
a given single appearance schedule for an acyclic graph. A practical
example of a well-ordered graph is presented to demonstrate the efficacy
of the approach. It is then shown that the problem of determining buffer-
optimal single appearnce schedules appears to be considerably more difficult
for acyclic graphs. A heuristic approach called recursive partitioning
by minimum cuts is developed and is tested on a large number of random
graphs. A practical example is also given to demonstrate its efficacy.
[42 pages]
The following is an earlier technical report from which the above journal
publication resulted.
Combined Code and Data Minimization for Synchronous Dataflow Programs,
UCB Tech. Memorandum UCB/ERL M94/93, November 29, 1994.
by Praveen K. Murthy,
Shuvra S. Bhattacharyya, and
Edward A. Lee