Lower bounds on memory requirements for statically scheduled DSP programs

Tracy C. Denk, Keshab K. Parhi

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


This paper presents novel techniques for computing the minimum number of memory locations in statically scheduled digital signal processing (DSP) programs. Two related problems are considered. In the first problem, we compute the minimum number of memory locations required for a scheduled program assuming that no circuit transformations (such as pipelining and retiming) are to be performed after scheduling. For this problem, we consider memory minimization for the operation-constrained, processor-constrained and unconstrained memory models which represent various restrictions on how data can be allocated to memory. Then we consider the second problem, where memory minimization for a scheduled program is considered simultaneously with retiming using a variation of the retiming problem referred to as the minimum physical storage location (MPSL) retiming. While both problems consider memory minimization for scheduled programs, the second problem minimizes memory using retiming whereas the first problem performs no retiming. The scheduling results obtained from the MARS design system are used to compare memory requirements in the context of both of these problems. Our experiments show that MARS performs an optimal retiming for the schedule it generates. These memory requirements are then compared with an integer linear programming solution to the scheduling problem which is optimal under the unconstrained memory model. It is concluded that the schedule obtained by the MARS system achieves optimality or near-optimality with respect to register minimization.

Original languageEnglish (US)
Pages (from-to)247-264
Number of pages18
JournalJournal of VLSI Signal Processing Systems for Signal, Image, and Video Technology
Issue number3
StatePublished - Jan 1 1996


Dive into the research topics of 'Lower bounds on memory requirements for statically scheduled DSP programs'. Together they form a unique fingerprint.

Cite this