Main Menu/ Search/ Help
Publications of the Ptolemy Group
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.
Two Complementary Heuristics for Translating Graphical DSP Programs into Minimum Memory Implementations

ERL Technical Report UCB/ERL M95/3, January 10, 1995.

by Shuvra S. Bhattacharyya, Praveen K. Murthy, and Edward A. Lee.

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]

  • APGAN and RPMC: Complementary Heuristics for Translating DSP Block Diagrams into Efficient Software Implementations

    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]

    [PS]

    ABSTRACT

    A shortened version of the above paper with certain proofs omitted. [31 pages]