Exact memory size estimation for array computations

This paper presents a new algorithm fur exact estimation of the minimum mem ory size required by programs dealing with array computations. Based on par ametric partitioning of the iteration space and Formalized live variable an alysis, our algorithm transforms the minimum memory size estimation into an equivalent problem: integer point counting fur intersection/union of mappi ngs of parameterized polytopes. A heuristics was then proposed to solve the counting problem. Experimental results show that the algorithm achieves th e exactness traditionally associated with totally unrolling loops while exp loiting educed computation complexity by preserving the original loop struc ture.