Precise data locality optimization of nested loops

Abstract : A significant source for enhancing application performance and for reducing power consumption in embedded processor applications is to improve the usage of the memory hierarchy. In this paper, a temporal and spatial locality optimization framework of nested loops is proposed, driven by parameterized cost functions. The considered loops can be imperfectly nested. New data layouts are propagated through the connected references and through the loop nests as constraints for optimizing the next connected reference in the same nest or in the other ones. Unlike many existing methods, special attention is paid to TLB (Translation Lookaside Buffer) effectiveness since TLB misses can take from tens to hundreds of processor cycles. Our approach only considers active data, that is, array elements that are actually accessed by a loop, in order to prevent useless memory loads and take advantage of storage compression and temporal locality. Moreover, the same data transformation is not necessarily applied to a whole array. Depending on the referenced data subsets, the transformation can result in different data layouts for a same array. This can significantly improve the performance since a priori incompatible references can be simultaneously optimized. Finally, the process does not only consider the innermost loop level but all levels. Hence, large strides when control returns to the enclosing loop are avoided in several cases, and better optimization is provided in the case of a small index range of the innermost loop.
Type de document :
Article dans une revue
Journal of Supercomputing, Springer Verlag, 2002, 21 (1), pp.37-76. 〈10.1023/A:1013535431127〉
Liste complète des métadonnées
Contributeur : Vincent Loechner <>
Soumis le : mercredi 10 novembre 2010 - 15:49:01
Dernière modification le : jeudi 11 janvier 2018 - 06:22:09




Vincent Loechner, Benoit Meister, Philippe Clauss. Precise data locality optimization of nested loops. Journal of Supercomputing, Springer Verlag, 2002, 21 (1), pp.37-76. 〈10.1023/A:1013535431127〉. 〈inria-00534831〉



Consultations de la notice