A polynomial-time algorithm for memory space reduction
Yonghong Song, Cheng Wang, Zhiyuan Li · 2005
Reducing memory-space requirement is important to many applications. For dataintensive applications, it may help avoid executing the program out-of-core. For highperformance computing, memory-space reduction may improve the cache hit rate as well as performance. For embedded systems, it can reduce the memory requirement, the memory latency and the energy consumption. This paper investigates program transformations which a compiler can use to reduce the memory space required for storing program data. In particular, the paper uses integer programming to model the problem of combining loop shifting, loop fusion and array contraction to minimize the data memory required to execute a collection of multi-level loop nests. The integer programming problem is then reduced to an equivalent network flow problem which can be solved in polynomial time. Key words: compilers, optimization, graph theory, network flow problem