Signal Assignment to Hierarchical Memory Organizations for Embedded Multidimensional Signal Processing Systems

The storage requirements of the array-dominated and loop-organized algorithmic specifications running on embedded systems can be significant. Employing a data memory space much larger than needed has negative consequences on the energy consumption, latency, and chip area. Finding an optimized storage of the usually large arrays from these algorithmic specifications is an essential task of memory allocation. This paper proposes an efficient algorithm for mapping multidimensional arrays to the data memory. Similarly to [1], it computes bounding windows for live elements in the index space of arrays, but this algorithm is several times faster. More important, since this algorithm works not only for entire arrays, but also parts of arrays - like, for instance, array references or, more general, sets of array elements represented by lattices [2], this signal-to-memory mapping technique can be also applied in hierarchical memory architectures.

I. Introduction

Many signal processing systems, particularly in the multimedia and telecom domains, are synthesized to execute mainly data-dominated applications. Their behavior is described in a high-level programming language, where the code is typically organized in sequences of loop nests having as boundaries (usually affine) functions of loop iterators, conditional instructions where the arguments may be data-dependent and/or data-independent (relational and/or logic expressions of affine functions of loop iterators). The data structures are multidimensional arrays; the indices of the array references are affine functions of loop iterators. The specifications with these characteristics are often called affine specifications [3].