Computation of the Minimum Data Storage for Multi-Dimensional Signal Processing

The amount of the data storage in signal processing systems, whose behavior is described by loop-organized algorithmic specifications, has an important impact on the overall energy consumption, chip area, as well as system performance. This paper presents a non-scalar approach for computing the minimum storage requirements in high-level procedural specifications, where the main data structures are multi-dimensional arrays. This methodology uses both algebraic techniques specific to the data-flow analysis used in modern compilers and, also, more recent advances in the theory of polyhedra. In contrast with all the previous works which are only estimation methods, this approach can perform the exact computation of the minimum data storage even for applications with numerous loop nests and complex array references.