Lower bounds on memory requirements for statically scheduled DSP programs

Tracy C. Denk, Keshab K Parhi

Research output: Contribution to journalArticle

6 Citations (Scopus)

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 languageEnglish (US)
Pages (from-to)247-264
Number of pages18
JournalJournal of VLSI Signal Processing Systems for Signal, Image, and Video Technology
Volume12
Issue number3
DOIs
StatePublished - Jan 1 1996

Fingerprint

Digital signal processing
Signal Processing
Lower bound
Data storage equipment
Requirements
Memory Model
Scheduling
Schedule
Optimality System
Pipelining
Integer Linear Programming
System Design
Scheduling Problem
Optimality
Linear programming
Restriction
Minimise
Computing
Networks (circuits)

Cite this

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

In: Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology, Vol. 12, No. 3, 01.01.1996, p. 247-264.

Research output: Contribution to journalArticle

@article{c132ba0822904ebea3d59239a51eedfc,
title = "Lower bounds on memory requirements for statically scheduled DSP programs",
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.",
author = "Denk, {Tracy C.} and Parhi, {Keshab K}",
year = "1996",
month = "1",
day = "1",
doi = "10.1007/BF00924988",
language = "English (US)",
volume = "12",
pages = "247--264",
journal = "Journal of Signal Processing Systems",
issn = "1939-8018",
publisher = "Springer New York",
number = "3",

}

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 -