Exact memory size estimation for array computations
- 1 October 2000
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Very Large Scale Integration (VLSI) Systems
- Vol. 8 (5) , 517-521
- https://doi.org/10.1109/92.894155
Abstract
This paper presents a new algorithm for exact estimation of the minimum memory size required by programs dealing with array computations. Based on parametric partitioning of the iteration space and formalized live variable analysis, our algorithm transforms the minimum memory size estimation into an equivalent problem: integer point counting for intersection/union of mappings of parameterized polytopes. A heuristics was then proposed to solve the counting problem. Experimental results show that the algorithm achieves the exactness traditionally associated with totally unrolling loops while exploiting reduced computation complexity by preserving the original loop structure.Keywords
This publication has 9 references indexed in Scilit:
- Simultaneous reference allocation in code generation for dual data memory bank ASIPsACM Transactions on Design Automation of Electronic Systems, 2000
- Memory size estimation for multimedia applicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1998
- Handling memory cache policy with integer points countingsPublished by Springer Nature ,1997
- Counting solutions to linear and nonlinear constraints through Ehrhart polynomialsPublished by Association for Computing Machinery (ACM) ,1996
- Background memory area estimation for multidimensional signal processing systemsIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1995
- Loop parallelization in the polytope modelPublished by Springer Nature ,1993
- REAL: a program for REgister ALlocationPublished by Association for Computing Machinery (ACM) ,1987
- Automated Synthesis of Data Paths in Digital SystemsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1986
- Register allocation via coloringComputer Languages, 1981