Renesting Single Appearance Schedules to Minimize Buffer Memory

Minimizing memory requirements for program and data are critical objectives when synthesizing software for embedded DSP applications. 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 orderings 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 parenthesizations 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 memory 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 fo