ABSTRACT
Contents 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.2 The Memory Size Computation Problem: A Brief Overview . . . . . . . . . 71 3.3 Computation of the Minimum Data Storage
for Affine Specifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.3.1 Definitions and concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.3.2 The index space of an array reference . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.4 Operations with Linearly Bounded Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3.4.1 The intersection of two linearly bounded lattices . . . . . . . . . . . . . 82 3.4.2 The difference of two linearly bounded lattices . . . . . . . . . . . . . . . . 83 3.4.3 Decomposition of array references into disjoint linearly
bounded lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 3.4.4 Computation of the lattice size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.5 Computation of the Minimum Data Storage . . . . . . . . . . . . . . . . . . . . . . . . . 98 3.5.1 The flow of the algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 3.5.2 Handling array references with delays . . . . . . . . . . . . . . . . . . . . . . . .103 3.5.3 Computation of the maximum iterator vector of an
array element . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .104 3.6 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .105 3.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .111 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .111
In the earlier days of digital system design, memory was expensive, so researchers focused on memory size optimization. Nowadays, the cost per memory bit is very low due to the progress of the semiconductor technology and the consequent increase of the level of integration. Gradually, the memory size optimization decreased in direct importance, while performance and power consumption became the key challenges. Memory may become a bottleneck-both in terms of energy and performance-for data-intensive embedded applications in areas like multimedia and multidimensional signal processing due to the impact of data storage and transfer versus data processing [1-3].
