Fast memory footprint estimation based on maximal dependency vector calculation

ABSTRACT

In data dominated applications, loop transformations have a huge impact on the lifetime of array data and therefore on memory footprint. Since a locally optimal loop transformation may have a detrimental effect somewhere else, many alternative loop transformations need to be explored. Therefore, estimation of the memory footprint is essential, and this estimation has to be fast. This paper presents a fast array based memory footprint estimation technique based on counting of iteration nodes in an iteration domain constrained by a maximal lifetime. The maximal lifetime is defined by the Maximal Dependency Vector (MDV) of the array for a given execution ordering. We further present for the first time two approaches for calculation of the MDV: a general approach based on an ILP formulation and a novel vertexes approach when iteration domains are approximated by bounding boxes. Experiments on practical test vehicles demonstrate that the estimation based on our vertexes approach is extremely fast, on average two orders of magnitude faster than the compared approaches, while still keeping the accuracy high. This enables system-level data memory footprint exploration of many different alternative transformed program codes, within interactive time limits, and on realistic complex applications.

REFERENCES

• 1: Florin Balasa , Francky Catthoor , Hugo De Man, Background memory area estimation for multidimensional signal processing systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.2, p.157-172, June 1995 [doi>10.1109/92.386218 ]
• 2: F. Catthoor, K. Danckaert, K. Kulkarni, E. Brockmeyer, P. G. Kjeldsberg, T. V. Achteren, and T. Omnes. Data access and storage management for embedded programmable processors. Kluwer Academic Publ., Boston, MA, 2002. ISBN 0-7923-7689-7.
• 3: Alain Darte , Robert Schreiber , Gilles Villard, Lattice-Based Memory Allocation, IEEE Transactions on Computers, v.54 n.10, p.1242-1257, October 2005 [doi>10.1109/TC.2005.167]
• 4: Eddy de Greef , Francky Catthoor , Hugo de Man, Array Placement for Storage Size Reduction in Embedded Multimedia Systems, Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures and Processors, p.66, July 14-16, 1997
• 5: Catherine H. Gebotys , Mohamed I. Elmasry, Simultaneous scheduling and allocation for cost constrained optimal architectural synthesis, Proceedings of the 28th conference on ACM/IEEE design automation, p.2-7, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127609]
• 6: GLPK: GNU Linear Programming Kit, http://www.gnu.org/software/glpk/.
• 7: Peter Grun , Florin Balasa , Nikil Dutt, Memory size estimation for multimedia applications, Proceedings of the 6th international workshop on Hardware/software codesign, p.145-149, March 15-18, 1998, Seattle, Washington, United States
• 8: P. G. Kjeldsberg, F. Catthoor, and E. J. Aas. Data dependency size estimation for use in memory optimization. IEEE Trans. on Comp. Aided Design, 22(7):908--921, July 2003.
• 9: F. J. Kurdahi , A. C. Parker, REAL: a program for REgister ALlocation, Proceedings of the 24th ACM/IEEE conference on Design automation, p.210-215, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37920]
• 10: V. Loechner. Polylib: A library for manipulating parameterized polyhedra. Technical report.
• 11: Seong Y. Ohm , Fadi J. Kurdahi , Nikil Dutt, Comprehensive lower bound estimation from behavioral descriptions, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.182-187, November 06-10, 1994, San Jose, California, United States
• 12: William Pugh, The Omega test: a fast and practical integer programming algorithm for dependence analysis, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.4-13, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125848]
• 13: P. Vanbroekhoven, G. Janssens, M. Bruynooghe, H. Corporaal, and F. Catthoor. Transformation to dynamic single assignment using a simple data flow analysis. In Proc. 3rd Asian Symp. on Programming Languages and Systems (ASPLAS), volume 3780 of Lecture Notes on Comp. Sc., pages 330--346, Tsukuba, Japan, Nov. 2005.
• 14: Ingrid M. Verbauwhede , Chris J. Scheers , Jan M. Rabaey, Memory estimation for high level synthesis, Proceedings of the 31st annual conference on Design automation, p.143-148, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196313]
• 15: Ying Zhao , Sharad Malik, Exact memory size estimation for array computations without loop unrolling, Proceedings of the 36th ACM/IEEE conference on Design automation, p.811-816, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310074]
• 16: H. Zhu, I. I. Luican, and F. Balasa. Exact computation of stor-age requirements for multi- domensional signal processing applications. In 11th Proc. IEEE Asia and South Pacific Design Autom. Conf. (ASPDAC), Yokohamma, Japan, Jan. 2006.