Loop optimization for a class of memory-constrained computations

ABSTRACT

Compute-intensive multi-dimensional summations that involve products of several arrays arise in the modeling of electronic structure of materials. Sometimes several alternative formulations of a computation, representing different space-time trade-offs, are possible. By computing and storing some intermediate arrays, reduction of the number of arithmetic operations is possible, but the size of intermediate temporary arrays may be prohibitively large. Loop fusion can be applied to reduce memory requirements, but that could impede effective tiling to minimize memory access costs. This paper develops an integrated model combining loop tiling for enhancing data reuse, and loop fusion for reduction of memory for intermediate temporary arrays. An algorithm is presented that addresses the selection of tile sizes and choice of loops for fusion, with the objective of minimizing cache misses while keeping the total memory usage within a given limit. Experimental results are reported that demonstrate the effectiveness of the combined loop tiling and fusion transformations performed by using the developed framework.

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: Jennifer M. Anderson , Saman P. Amarasinghe , Monica S. Lam, Data and computation transformations for multiprocessors, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.166-178, July 19-21, 1995, Santa Barbara, California, United States
• 3: W. Aulbur. Parallel Implementation of Quasiparticle Calculations of Semiconductors and Insulators, Ph.D. Dissertation, Ohio State University, Columbus, OH, October 1996.
• 4: K. L. Bak, P. Jorgensen, J. Olsen, W. Klopper. Accuracy of atomization energies and reaction enthalpies in standard and extrapolated electronic wave function/basis set calculations. J. Chem. Phys., Vol. 112, pp. 9229-9242, 2000.
• 5: L. Carter, J. Ferrante and S. F. Hummel. Efficient Parallelism via Hierarchical Tiling. Proceedings of the Seventh SIAM Conference on Parallel Processing for Scientific Computing, Philadelphia, PA, February 1995.
• 6: Siddhartha Chatterjee , John R. Gilbert , Robert Schreiber , Shang-Hua Teng, Optimal evaluation of array expressions on massively parallel machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.1, p.123-156, Jan. 1995 [doi>10.1145/200994.201004]
• 7: Siddhartha Chatterjee , John R. Gilbert , Robert Schreiber , Shang-Hua Teng, Automatic array alignment in data-parallel programs, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.16-28, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158517]
• 8: Stephanie Coleman , Kathryn S. McKinley, Tile size selection using cache organization and data layout, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.279-290, June 18-21, 1995, La Jolla, California, United States
• 9: T. H. Dunning, Jr. A roadmap for the calculation of molecular binding energies. J. Phys. Chem. A, 2000 (in press).
• 10: J. Foresman and A. Frisch. Exploring Chemistry with Electronic Structure Methods: A Guide to Using Gaussian, Second Edition. Gaussian, Inc., Pittsburgh, PA, 1996.
• 11: 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
• 12: Somnath Ghosh , Margaret Martonosi , Sharad Malik, Precise miss analysis for program transformations with caches of arbitrary associativity, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.228-239, October 02-07, 1998, San Jose, California, United States
• 13: High Performance Computational Chemistry Group. NWChem, A computational chemistry package for parallel computers, Version 3.3, 1999. Pacific Northwest National Laboratory, Richland, WA 99352.
• 14: Karin Högstedt , Larry Carter , Jeanne Ferrante, Determining the idle time of a tiling, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.160-173, January 15-17, 1997, Paris, France [doi>10.1145/263699.263716]
• 15: M. S. Hybertsen and S. G. Louie. Electronic Correlation in Semiconductors and Insulators: Band Gaps and Quasiparticle Energies. Phys. Rev. B, 34, 5390 (1986).
• 16: Ken Kennedy , Kathryn S. McKinley, Optimizing for parallelism and data locality, Proceedings of the 6th international conference on Supercomputing, p.323-334, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143427]
• 17: 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
• 18: Ken Kennedy, Fast greedy weighted fusion, Proceedings of the 14th international conference on Supercomputing, p.131-140, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335244]
• 19: Induprakas Kodukula , Nawaaz Ahmed , Keshav Pingali, Data-centric multi-level blocking, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.346-357, June 16-18, 1997, Las Vegas, Nevada, United States
• 20: Induprakas Kodukula , Keshav Pingali , Robert Cox , Dror Maydan, An experimental evaluation of tiling and shackling for memory hierarchy management, Proceedings of the 13th international conference on Supercomputing, p.482-491, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305243]
• 21: Chi Chung Lam , Ponnuswamy Sadayappan, Performance optimization of a class of loops implementing multidimensional integrals, 1999
• 22: 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
• 23: Chi-Chung Lam , Daniel Cociorva , Gerald Baumgartner , P. Sadayappan, Memory-Optimal Evaluation of Expression Trees Involving Large Objects, Proceedings of the 6th International Conference on High Performance Computing, p.103-110, December 17-20, 1999
• 24: Chi-Chung Lam , P. Sadayappan , Rephael Wenger, Optimal Reordering and Mapping of a Class of Nested-Loops for Parallel Execution, Proceedings of the 9th International Workshop on Languages and Compilers for Parallel Computing, p.315-329, August 08-10, 1996
• 25: C. Lam, P. Sadayappan and R. Wenger. On Optimizing a Class of Multi-Dimensional Loops with Reductions for Parallel Execution. Parallel Processing Letters, Vol. 7 No. 2, pp. 157-168, 1997.
• 26: C. Lam, P. Sadayappan and R. Wenger. Optimization of a Class of Multi-Dimensional Integrals on Parallel Machines. Proceedings of the Eighth SIAM Conference on Parallel Processing for Scientific Computing, Minneapolis, MN, March 1997.
• 27: Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
• 28: T. J. Lee and G. E. Scuseria. Achieving chemical accuracy with coupled cluster theory. In S. R. Langhoff (Ed.), Quantum Mechanical Electronic Structure Calculations with Chemical Accuracy, pp. 47-109, Kluwer Academic, 1997.
• 29: Wei Li, Compiling for numa parallel machines, Cornell University, Ithaca, NY, 1993
• 30: Wei Li, Compiler cache optimizations for banded matrix problems, Proceedings of the 9th international conference on Supercomputing, p.21-30, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224541]
• 31: J. M. L. Martin. In P. v. R. Schleyer, P. R. Schreiner, N. L. Allinger, T. Clark, J. Gasteiger, P. Kollman, H. F. Schaefer III (Eds.), Encyclopedia of Computational Chemistry. Wiley & Sons, Berne (Switzerland). Vol. 1, pp. 115-128, 1998.
• 32: Kathryn S. McKinley, A Compiler Optimization Algorithm for Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.9 n.8, p.769-787, August 1998 [doi>10.1109/71.706049]
• 33: Kathryn S. McKinley , Steve Carr , Chau-Wen Tseng, Improving data locality with loop transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.424-453, July 1996 [doi>10.1145/233561.233564]
• 34: Nicholas Mitchell , Karin Högstedt , Larry Carter , Jeanne Ferrante, Quantifying the multi-level nature of tiling interactions, International Journal of Parallel Programming, v.26 n.6, p.641-670, Dec. 1998 [doi>10.1023/A:1018782528453]
• 35: Juan J. Navarro , Toni Juan , Tomás Lang, MOB forms: a class of multilevel block algorithms for dense linear algebra operations, Proceedings of the 8th international conference on Supercomputing, p.354-363, July 11-15, 1994, Manchester, England [doi>10.1145/181181.181561]
• 36: K. A. Peterson and T. H. Dunning, Jr. (1997). The CO molecule: Role of basis set and correlation treatment in the calculation of molecular properties. J. Molec. Struct. (Theochem), Vol. 400, pp. 93-117.
• 37: Gabriel Rivera , Chau-Wen Tseng, Data transformations for eliminating conflict misses, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.38-49, June 17-19, 1998, Montreal, Quebec, Canada
• 38: Gabriel Rivera , Chau-Wen Tseng, Eliminating conflict misses for high performance architectures, Proceedings of the 12th international conference on Supercomputing, p.353-360, July 1998, Melbourne, Australia [doi>10.1145/277830.277917]
• 39: H. N. Rojas, R. W. Godby and R. J. Needs. Space-Time Method for Ab-Initio Calculations of Self-Energies and Dielectric Response Functions of Solids. Phys. Rev. Lett., 74, 1827, (1995).
• 40: Michael W. Schmidt , Kim K. Baldridge , Jerry A. Boatz , Steven T. Elbert , Mark S. Gordon , Jan H. Jensen , Shiro Koseki , Nikita Matsunaga , Kiet A. Nguyen , Shujun Su , Theresa L. Windus , Michel Dupuis , John A. Montgomery, Jr., General atomic and molecular electronic structure system, Journal of Computational Chemistry, v.14 n.11, p.1347-1363, Nov. 1993 [doi>10.1002/jcc.540141112]
• 41: S. Singhai and K. S. McKinley. Loop Fusion for Parallelism and Locality. Mid-Atlantic States Student Workshop on Programming Languages and Systems, MASPLAS '96, April 1996.
• 42: S. Singhai and K. S. McKinley. A Parameterized Loop Fusion Algorithm for Improving Parallelism and Cache Locality. The Computer Journal, 40(6):340-355, 1997.
• 43: 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
• 44: J. F. Stanton, J. Gauss, J. D. Watts, M. Nooijen, N. Oliphant, S. A. Perera, P. G. Szalay, W. J. Lauderdale, S. A. Kucharski, S. R. Gwaltney, S. Beck, A. Balkov' a, D. E. Bernholdt, K. K. Baeck, P. Rozyczko, H. Sekino, C. Hober, and R. J. Bartlett. ACES II, a software product of the Quantum Theory Project, University of Florida. Integral packages included are VMOL (J. Alml of and P. R. Taylor); VPROPS (P. Taylor) ABACUS; (T. Helgaker, H. J. Aa. Jensen, P. Jorgensen, J. Olsen, and P. R. Taylor).
• 45: 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
• 46: Michael E. Wolf , Dror E. Maydan , Ding-Kai Chen, Combining loop transformations considering caches and scheduling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.274-286, December 02-04, 1996, Paris, France
• 47: 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:
  C. Computer Systems Organization

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

General Terms:
Algorithms, Design, Theory