Optimizing inter-nest data locality

ABSTRACT

By examining data reuse patterns of four array-intensive embedded applications, we found that these codes exhibit a significant amount of inter-nest reuse (i. e., the data reuse that occurs between different nests). While traditional compiler techniques that target array-intensive applications can exploit intra-nest data reuse, there has not been much success in the past in taking advantage of internest data reuse. In this paper, we present a compiler strategy that optimizes inter-nest reuse using loop (iteration space) transformations. Our approach captures the impact of execution of a nest on cache contents using an abstraction called footprint vector. Then, it transforms a given nest such that the new (transformed) access pattern reuses the data left in cache by the previous nest in the code. In optimizing inter-nest locality, our approach also tries to achieve good intra-nest locality. Our simulation results indicate large performance improvements. In particular, inter-nest loop optimization generates competitive results with intra-nest loop and data optimizations.

REFERENCES

• 1: Nawaaz Ahmed , Nikolay Mateev , Keshav Pingali, Synthesizing transformations for locality enhancement of imperfectly-nested loop nests, Proceedings of the 14th international conference on Supercomputing, p.141-152, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335245]
• 2: S. P. Amarasinghe, J. M. Anderson, M. S. Lam, and C. W. Tseng. The SUIF compiler for scalable parallel machines. In Proc. the Seventh SIAM Conf. on Parallel Proc. for Scientific Computing, February, 1995.
• 3: Koen Danckaert , Chidamber Kulkarni , Erik Brockmeyer , Per Gunnar Kjeldsbert , Francky Catthoor, Storage Management Programmable Process, Kluwer Academic Publishers, Norwell, MA, 2002
• 4: Francky Catthoor , Eddy de Greef , Sven Suytack, Custom Memory Management Methodology: Exploration of Memory Organisation for Embedded Multimedia System Design, Kluwer Academic Publishers, Norwell, MA, 1998
• 5: M. Kandemir , A. Choudhary , J. Ramanujam , P. Banerjee, Improving locality using loop and data transformations in an integrated framework, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.285-297, November 1998, Dallas, Texas, United States
• 6: Wayne Kelly , Vadim Maslov , William Pugh , Evan Rosser , Tatiana Shpeisman , David Wonnacott, The Omega Library interface guide, University of Maryland at College Park, College Park, MD, 1995
• 7: Wei Li, Compiling for numa parallel machines, Cornell University, Ithaca, NY, 1993
• 8: Kathryn S. McKinley , Olivier Temam, A quantitative analysis of loop nest locality, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.94-104, October 01-04, 1996, Cambridge, Massachusetts, United States
• 9: M. F. P. O'Boyle , P. M. W. Knijnenburg, Non-singular data transformations: definition, validity and applications, Proceedings of the 11th international conference on Supercomputing, p.309-316, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263655]
• 10: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
• 11: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Optimization

General Terms:
Design, Experimentation, Performance

Keywords:
array-intensive codes, cache locality, data reuse, embedded applications, inter-nest optimization