Minimizing memory requirements for chain-structured synchronous dataflow programs

This paper addresses trade-offs between the minimization of program memory and data memory requirements in the compilation of dataflow programs for multirate signal processing. Our techniques are specific to the synchronous dataflow (SDF) model of Lee and Messerschmitt (1987), which has been used extensively in software synthesis environments for DSP. We focus on programs that are represented as chain-structured SDF graphs. We show that there is an O(n ³) dynamic programming algorithm for determining a schedule that minimizes data memory usage among the set of schedules that minimize program memory usage. A practical example to illustrate the efficacy of this approach is given. Some extensions of this algorithm are also given; for example, we show that the algorithm applies to the more general class of well-ordered graphs