Polyhedral Techniques for Parametric Memory Requirement Estimation

PHILIPPE CLAUSS; DIEGO GARBERVETSKY; VINCENT LOECHNER; SVEN VERDOOLAEGE

Energy-Aware Memory Management for Embedded Multimedia Systems: A Computer-Aided Design Approach

Chapman & Hall / CRC Press

Año: 2011; p. 117 - 149

Memory requirement estimation is an important issue in the development of embedded systems, since memory directly influences performance, cost and power consumption. It is therefore crucial to have tools that automatically compute accurate estimates of the memory requirements of programs to bet- ter control the development process and avoid some catastrophic execution exceptions. Compute-intensive applications often spend most of their execution time in nested loops. The polyhedral model provides a powerful abstraction to reason about analyses and transformations on such loop nests by viewing an instance, or iteration, of each statement as an integer point in a polyhedron. From such a representation and a precise characterization of inter and intra-statement dependences, it is possible to analyze loop nests statically in a completely mathematical setting relying on machinery from linear algebra, integer linear programming and polynomial algebra. The analyses made on integer points in polyhedra correspond to effective quantitative characteristics of the original code such as the variable liveness or the amount of consumed memory. The polyhedral model is applicable to loop nests in which the data access functions and loop bounds are affine combinations of the enclosing loop indices and parameters. While a precise characterization of data dependences is feasible for programs with static control structures and affine references and loop bounds, codes with non-affine array access functions or code with dynamic control can also be handled, but either with conservative assumptions on some dependences, or with additional knowledge coming from developers, or from advanced profiling/modeling techniques. In this chapter, we present several techniques using the polyhedral model and providing automatic estimations of memory requirements in nested-loops programs.