Main Menu/Search/Help
PUBLICATIONS of the DSP DESIGN GROUP and the PTOLEMY PROJECT

Heuristics for Joint Code and Data Minimization in SDF Programs

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.

ABSTRACT

Dataflow has proven to be an attractive computational model for graphical DSP design environments that support the automatic conversion of hierarchical signal flow diagrams into implementations on programmable processors. The synchronous dataflow (SDF) model is particularly well-suited to dataflow- based graphical programming because its restricted semantics offer strong formal properties and significant compile-time predictability, while capturing the behavior of a large class of important signal processing applications. When synthesizing software for embedded signal processing applications, critical constraints arise due to the limited amounts of memory. In the following papers, we propose a solution to the problem of jointly optimizing the code and data size when converting SDF programs into software implementations. The abstracts for the individual papers describe the specific techniques developed in each paper.

Combined Code and Data Minimization for Synchronous Dataflow Programs,
UCB Tech. Memorandum UCB/ERL M94/93, November 29, 1994, and 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

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]
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.

ABSTRACT
A shortened version of the above paper with certain proofs omitted. [31 pages]
Converting Graphical DSP Programs into Memory-Constrained Software Prototypes,
6th IEEE International Workshop on Rapid Systems Prototyping, Chapel Hill, North Carolina, USA, June 7-9, 1995
by Shuvra S. Bhattacharyya, Praveen K. Murthy, and Edward A. Lee
ABSTRACT
A conference version of the 2nd paper above. This paper does not contain any proofs and contains only the description of the algorithms and results of the extensive experimental study done to compare the PGAN and RPMC heuristics. [7 pages]
Renesting single appearance schedules to minimize buffer memory
UCB/ERL Technical Memorandum UCB/ERL M95/43, Electronics Research Lab., UC Berkeley, CA 94720, April, 1 1995, also appears in 1995 IEEE Workshop on VLSI Signal Processing, Osaka, Japan, October 1995.
by Shuvra S. Bhattacharyya, Praveen K. Murthy, and Edward A. Lee
ABSTRACT
In prior work, it has been demonstrated that for graphical DSP programs based on the widely-used synchronous dataflow model, an important class of minimum code size implementations can be viewed as parenthesizations of lexical order ings of the computational blocks. Such a parenthesization corresponds to the hierarchy of loops in the software implementation. In this paper, we present a dynamic programming technique for constructing a parenthesization that minimizes data memory cost from a given lexical ordering of a synchronous dataflow graph. For graphs that do not contain delays on the edges, this technique always constructs a parenthesization that has minimum data memory cost from among all paren thesizations for the given lexical ordering. When delays are present, the technique may make refinements to the lexical ordering while it is computing the parenthesization, and the data mem ory cost of the result is guaranteed to be less than or equal to the data memory cost of all valid parenthesizations for the initial (input) lexical ordering.
Thus, our dynamic programming technique can be used to post-optimize the output for any algorithm that schedules SDF graphs into minimum code size loop hierarchies. On several practical examples, we demonstrate that significant improvement can be gained by such post-opti mization when applied to two scheduling techniques that have been developed earlier. That is, the result of each scheduling algorithm combined with the post-optimization often requires signifi cantly less data memory than the result of the scheduling algorithm without post-optimization. We also present an adaptation of our dynamic programming technique for post-optimizing an arbi trary (not necessarily minimum code size) schedule to optimally reduce the code size. [17 pages]