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




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