### Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 247-264 |

Number of pages | 18 |

Journal | Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology |

Volume | 12 |

Issue number | 3 |

DOIs | |

State | Published - Jan 1 1996 |

### Fingerprint

### Cite this

**Lower bounds on memory requirements for statically scheduled DSP programs.** / Denk, Tracy C.; Parhi, Keshab K.

Research output: Contribution to journal › Article

*Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology*, vol. 12, no. 3, pp. 247-264. https://doi.org/10.1007/BF00924988

}

TY - JOUR

T1 - Lower bounds on memory requirements for statically scheduled DSP programs

AU - Denk, Tracy C.

AU - Parhi, Keshab K

PY - 1996/1/1

Y1 - 1996/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=0030173561&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030173561&partnerID=8YFLogxK

U2 - 10.1007/BF00924988

DO - 10.1007/BF00924988

M3 - Article

VL - 12

SP - 247

EP - 264

JO - Journal of Signal Processing Systems

JF - Journal of Signal Processing Systems

SN - 1939-8018

IS - 3

ER -