Estimating and reducing the memory requirements of signal processing codes for embedded systems

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.