TY - JOUR
T1 - Estimating and reducing the memory requirements of signal processing codes for embedded systems
AU - Ramanujam, J.
AU - Hong, Jinpyo
AU - Kandemir, Mahmut
AU - Narayan, Ashish
AU - Agarwal, Ankush
N1 - Funding Information:
Manuscript received December 28, 2001; revised May 12, 2003. This work was supported in part by NSF Young Investigator Award 9457768 and by the National Science Foundation under Grants 0073800, 0093082, and 0103693. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Chaitali Chakrabarti. J. Ramanujam and A. Agarwal are with the Louisiana State University, Baton Rouge, LA 70803 USA (e-mail: [email protected]; [email protected]). J. Hong is with the University of Memphis, Memphis, TN 38152 USA (e-mail: [email protected]). M. Kandemir is with the Pennsylvania State University, University Park, PA 16802 USA (e-mail: [email protected]). A. Narayan is with Dow Jones and Company, Princeton NJ 08543 USA (e-mail: [email protected]). Digital Object Identifier 10.1109/TSP.2005.855086
PY - 2006/1
Y1 - 2006/1
N2 - Most embedded systems have limited amount of memory. In contrast, the memory requirements of the digital signal processing (DSP) and video processing codes (in nested loops, in particular) running on embedded systems is significant. This paper addresses the problem of estimating and reducing the amount of memory needed for transfers of data in embedded systems. First, the problem of estimating the region associated with a statement or the set of elements referenced by a statement during the execution of nested loops is analyzed. For a fixed execution ordering, a quantitative analysis of the number of elements referenced is presented; exact expressions for uniformly generated references and a close upper and lower bound for nonuniformly generated references are derived. Second, in addition to presenting an algorithm that computes the total memory required, this paper also discusses the effect of transformations (that change the execution ordering) on the lifetimes of array variables, i.e., the time between the first and last accesses to a given array location. The term maximum window size is introduced, and quantitative expressions are derived to compute the maximum window size. A detailed analysis of the effect of unimodular transformations on data locality, including the calculation of the maximum window size, is presented.
AB - Most embedded systems have limited amount of memory. In contrast, the memory requirements of the digital signal processing (DSP) and video processing codes (in nested loops, in particular) running on embedded systems is significant. This paper addresses the problem of estimating and reducing the amount of memory needed for transfers of data in embedded systems. First, the problem of estimating the region associated with a statement or the set of elements referenced by a statement during the execution of nested loops is analyzed. For a fixed execution ordering, a quantitative analysis of the number of elements referenced is presented; exact expressions for uniformly generated references and a close upper and lower bound for nonuniformly generated references are derived. Second, in addition to presenting an algorithm that computes the total memory required, this paper also discusses the effect of transformations (that change the execution ordering) on the lifetimes of array variables, i.e., the time between the first and last accesses to a given array location. The term maximum window size is introduced, and quantitative expressions are derived to compute the maximum window size. A detailed analysis of the effect of unimodular transformations on data locality, including the calculation of the maximum window size, is presented.
UR - http://www.scopus.com/inward/record.url?scp=30344458784&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=30344458784&partnerID=8YFLogxK
U2 - 10.1109/TSP.2005.855086
DO - 10.1109/TSP.2005.855086
M3 - Article
AN - SCOPUS:30344458784
SN - 1053-587X
VL - 54
SP - 286
EP - 294
JO - IEEE Transactions on Signal Processing
JF - IEEE Transactions on Signal Processing
IS - 1
ER -