An access regularity criterion and regularity improvement heuristics for data transfer optimization by global loop transformations
Sven Verdoolaege, Koen Danckaert, Francky Catthoor, Maurice Bruynooghe, Gerda Janssens · Lirias · 2003
Abstract Power consumption for typical embedded multi-media applications is dominated by the storage of and the access to the large multi-dimensional arrays they manipulate. It is now well known that a design methodology for reducing power consumption and improving system performance should apply global loop transformations for increasing locality and regularity of code. Instead of trying to solve a single linear programming problem, which has been proved unfeasible for real world (multi-media) applications, the problem is better divided into several steps. Earlier work used a polyhedral model with a placement step mapping individual polytopes to a common iteration space and an ordering step. For handling even larger applications with tens of loop nests that should be optimized together, this paper proposes to extend that approach by splitting the placement step into two substeps, the first linearly transforming the polytopes and optimizing for regularity and the second optimizing locality while assigning them an offset in the common iteration space. The main contribution is in proposing an automatable regularity improvement criterion. Improving regularity is beneficial for both power and performance because it enables an even better locality of access. We conclude with some preliminary results.