Two Complementary Heuristics for Translating Graphical DSP Programs into Minimum Memory Implementations
Technical Memorandum UCB/ERL M95/3
Electronics Research Laboratory, Berkeley, CA 94720 January 10, 1995.
| Published Version |
ABSTRACT
In this paper, we develop another heuristic for computing minimum buffer single appearance schedule. It is a customization to acyclic graphs of a bottom-up technique, called pairwise grouping of adjacent nodes (PGAN), that was proposed earlier for general SDF graphs. We show that our customization to acyclic graphs significantly reduces the complexity of the general PGAN algorithm, and we present a formal study of our modified PGAN technique that rigorously establishes its optimality for a certain class of applications. We present the results of an extensive experimental investigation on the performance of our modified PGAN technique and the top-down RPMC approach developed in the previous paper and on the trade-offs between them. Based on these results, we conclude that these two techniques complement each other, and thus, they should both be incorporated into SDF-based software implementation environments in which the minimization of memory requirements is important. [63 pages]
Design Automation for Embedded Systems Journal, Vol. 2, No. 1, pp33-60, January 1997.
by Shuvra S. Bhattacharyya, Praveen K. Murthy, and Edward A. Lee.
![[PDF]](http://ptolemy.eecs.berkeley.edu/image/PDF.gif){kind=small}
ABSTRACT
A shortened version of the above paper with certain proofs omitted. [31 pages]