Data locality enhancement by memory reduction

ABSTRACT

In this paper, we propose memory reduction as a new approach to data locality enhancement. Under this approach, we use the compiler to reduce the size of the data repeatedly referenced in a collection of nested loops. Between their reuses, the data will more likely remain in higher-speed memory devices, such as the cache. Specifically, we present an optimal algorithm to combine loop shifting, loop fusion and array contraction to reduce the temporary array storage required to execute a collection of loops. When applied to 20 benchmark programs, our technique reduces the memory requirement, counting both the data and the code, by 51% on average. The transformed programs gain a speedup of 1.40 on average, due to the reduced footprint and, consequently, the improved data locality.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: Mokhtar S. Bazaraa , John J. Jarvis , Hanif D. Sherali, Linear programming and network flows (2nd ed.), John Wiley & Sons, Inc., New York, NY, 1990
• 3: David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
• 4: Béatrice Creusillet , Francois Irigoin, Interprocedural array region analyses, International Journal of Parallel Programming, v.24 n.6, p.513-546, Dec. 1996
• 5: Alain Darte, On the Complexity of Loop Fusion, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.149, October 12-16, 1999
• 6: Chen Ding , Ken Kennedy, Improving effective bandwidth through compiler enhancement of global and dynamic cache reuse, 2000
• 7: Jeanne Ferrante , Vivek Sarkar , W. Thrash, On Estimating and Enhancing Cache Effectiveness, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.328-343, August 07-09, 1991
• 8: Antoine Fraboulet , Guillaume Huard , Anne Mignotte, Loop Alignment for Memory Accesses Optimization, Proceedings of the 12th international symposium on System synthesis, p.71, November 01-04, 1999
• 9: Dennis Gannon , William Jalby , Kyle Gallivan, Strategies for cache and local memory management by global program transformation, Journal of Parallel and Distributed Computing, v.5 n.5, p.587-616, October 1988 [doi>10.1016/0743-7315(88)90014-7]
• 10: Guang R. Gao , R. Olsen , Vivek Sarkar , Radhika Thekkath, Collective Loop Fusion for Array Contraction, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.281-295, August 03-05, 1992
• 11: T. Gross , P. Steenkiste, Structured dataflow analysis for arrays and its use in an optimizing complier, Software—Practice & Experience, v.20 n.2, p.133-155, February 1990 [doi>10.1002/spe.4380200203]
• 12: Junjie Gu , Zhiyuan Li , Gyungho Lee, Experience with efficient array data flow analysis for array privatization, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.157-167, June 18-21, 1997, Las Vegas, Nevada, United States
• 13: Ken Kennedy , Kathryn S. McKinley, Maximizing Loop Parallelism and Improving Data Locality via Loop Fusion and Distribution, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.301-320, August 12-14, 1993
• 14: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 15: Chi-Chung Lam , Daniel Cociorva , Gerald Baumgartner , P. Sadayappan, Optimization of Memory Usage Requirement for a Class of Loops Implementing Multi-dimensional Integrals, Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing, p.350-364, August 04-06, 1999
• 16: C. Leiserson and J. Saxe. Retiming synchronous circuitry. Algorithmica, 6:5-35, 1991.
• 17: E. Christopher Lewis , Calvin Lin , Lawrence Snyder, The implementation and evaluation of fusion and contraction in array languages, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.50-59, June 17-19, 1998, Montreal, Quebec, Canada
• 18: Naraig Manjikian , Tarek S. Abdelrahman, Fusion of Loops for Parallelism and Locality, IEEE Transactions on Parallel and Distributed Systems, v.8 n.2, p.193-209, February 1997 [doi>10.1109/71.577265]
• 19: Dror E. Maydan , Saman P. Amarasinghe , Monica S. Lam, Array-data flow analysis and its use in array privatization, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.2-15, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158515]
• 20: A. G. Mohamed, G. C. Fox, G. von Laszewski, M. Parashar, T. Haupt, K. Mills, Y.-H. Lu, N.-T. Lin, and N.-K. Yeh. Applications benchmark set for fortran-d and high performance fortran. Technical Report CRPS-TR92260, Center for Research on Parallel Computation, Rice University, June 1992.
• 21: J. Rice and J. Jing. Problems to test parallel and vector languages. Technical Report CSD-TR-1016, Department of Computer Science, Purdue University, 1990.
• 22: Vivek Sarkar, Optimized unrolling of nested loops, Proceedings of the 14th international conference on Supercomputing, p.153-166, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335246]
• 23: Vivek Sarkar , Guang R. Gao, Optimization of array accesses by collective loop transformations, Proceedings of the 5th international conference on Supercomputing, p.194-205, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109077]
• 24: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 25: S. K. Singhai and K. S. McKinley. A parameterized loop fusion algorithm for improving parallelism and cache locality. The Computer Journal, 40(6), 1997.
• 26: Yonghong Song , Zhiyuan Li, New tiling techniques to improve cache temporal locality, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.215-228, May 01-04, 1999, Atlanta, Georgia, United States
• 27: Y. Song, R. Xu, C. Wang, and Z. Li. Performance enhancement by memory reduction. Technical Report CSD-TR-00-016, Department of Computer Science, Purdue University, 2000. Also available at http://www.cs.purdue.edu/homes/songyh/academic.html.
• 28: Michelle Mills Strout , Larry Carter , Jeanne Ferrante , Beth Simon, Schedule-independent storage mapping for loops, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.24-33, October 02-07, 1998, San Jose, California, United States
• 29: Michael Edward Wolf, Improving locality and parallelism in nested loops, Stanford University, Stanford, CA, 1992
• 30: 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:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

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

General Terms:
Languages

Keywords:
array contraction, data locality, loop fusion, loop shifting