Automatic tiling of iterative stencil loops

ABSTRACT

Iterative stencil loops are used in scientific programs to implement relaxation methods for numerical simulation and signal processing. Such loops iteratively modify the same array elements over different time steps, which presents opportunities for the compiler to improve the temporal data locality through loop tiling. This article presents a compiler framework for automatic tiling of iterative stencil loops, with the objective of improving the cache performance. The article first presents a technique which allows loop tiling to satisfy data dependences in spite of the difficulty created by imperfectly nested inner loops. It does so by skewing the inner loops over the time steps and by applying a uniform skew factor to all loops at the same nesting level. Based on a memory cost analysis, the article shows that the skew factor must be minimized at every loop level in order to minimize cache misses. A graph-theoretical algorithm, which takes polynomial time, is presented to determine the minimum skew factor. Furthermore, the memory-cost analysis derives the tile size which minimizes capacity misses. Given the tile size, an efficient and general <i>array-padding</i> scheme is applied to remove conflict misses. Experiments were conducted on 16 test programs and preliminary results showed an average speedup of 1.58 and a maximum speedup of 5.06 across those test programs.

REFERENCES

• 1: Admas, J. C. 1999. MUDPACK: Multigrid Software for Elliptic Partial Differential Equations. Available on line at http://www.scd.ucar.edu/css/software/mudpack/.
• 2: 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]
• 3: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 4: Vicki H. Allan , Reese B. Jones , Randall M. Lee , Stephen J. Allan, Software pipelining, ACM Computing Surveys (CSUR), v.27 n.3, p.367-432, Sept. 1995 [doi>10.1145/212094.212131]
• 5: Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
• 6: Andersen, B. S., Gustavson, F. G., Wasniewski, J., and Yalamov, P. Y. 1999. Recursive formulation of some dense linear algebra algorithms. In Proceedings of the SIAM Conference on Parallel Processing for Scientific Computing (San Antonio, TX).
• 7: 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
• 8: David F. Bacon , Jyh-Herng Chow , Dz-ching R. Ju , Kalyan Muthukumar , Vivek Sarkar, A compiler framework for restructuring data declarations to enhance cache and TLB effectiveness, Proceedings of the 1994 conference of the Centre for Advanced Studies on Collaborative research, p.3, October 31-November 03, 1994, Toronto, Ontario, Canada
• 9: William Blume , Rudolf Eigenmann, Nonlinear and Symbolic Data Dependence Testing, IEEE Transactions on Parallel and Distributed Systems, v.9 n.12, p.1180-1194, December 1998 [doi>10.1109/71.737695]
• 10: Boulet, P., Dongarra, J., Robert, Y., and Vivien, F. 1999. Static tiling for heterogeneous computing platforms. Parall. Comput. 25, 547--568.
• 11: P. Briggs , K. D. Cooper , K. Kennedy , L. Torczon, Coloring heuristics for register allocation, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.275-284, June 19-23, 1989, Portland, Oregon, United States
• 12: Doug Burger , James R. Goodman , Alain Kägi, Memory bandwidth limitations of future microprocessors, Proceedings of the 23rd annual international symposium on Computer architecture, p.78-89, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 13: Jacqueline Chame , Sungdo Moon, A tile selection algorithm for data locality and cache interference, Proceedings of the 13th international conference on Supercomputing, p.492-499, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305245]
• 14: Siddhartha Chatterjee , Vibhor V. Jain , Alvin R. Lebeck , Shyam Mundhra , Mithuna Thottethodi, Nonlinear array layouts for hierarchical memory systems, Proceedings of the 13th international conference on Supercomputing, p.444-453, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305231]
• 15: Siddhartha Chatterjee , Alvin R. Lebeck , Praveen K. Patnala , Mithuna Thottethodi, Recursive array layouts and fast parallel matrix multiplication, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.222-231, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305645]
• 16: D. Cociorva , J. W. Wilkins , C. Lam , G. Baumgartner , J. Ramanujam , P. Sadayappan, Loop optimization for a class of memory-constrained computations, Proceedings of the 15th international conference on Supercomputing, p.103-113, June 2001, Sorrento, Italy [doi>10.1145/377792.377814]
• 17: 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
• 18: Collard, J.-F. 1994. Space-time transformation of while-loops using speculative execution. In Proceedings of the Scalable High Performance Computing Conference (Knoxville, TN). 429--436.
• 19: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 20: Chen Ding , Ken Kennedy, Improving Effective Bandwidth through Compiler Enhancement of Global Cache Reuse, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.38, April 23-27, 2001
• 21: 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
• 22: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 23: 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
• 24: 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
• 25: Haghighat, M. R. 1990. Symbolic dependence analysis for high performance parallelizing compilers. Ph.D. dissertation. Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL.
• 26: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 27: Guohua Jin , John Mellor-Crummey , Robert Fowler, Increasing temporal locality with skewing and recursive blocking, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.43-43, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582077]
• 28: M. Kandemir , A. Choudhary , P. Banerjee , J. Ramanujam, A Matrix-Based Approach to the Global Locality Optimization Problem, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.306, October 12-18, 1998
• 29: 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]
• 30: 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
• 31: 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
• 32: Induprakas Kodukula , Keshav Pingali, Transformations for imperfectly nested loops, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.12-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369051]
• 33: 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
• 34: 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]
• 35: Matula, D. and Beck, L. 1981. Smallest-last ordering and clustering and graph coloring algorithms. Tech. rep. TR CSE 8104. Department of Computer Science and Engineering, Southern Methodist University, Dallas, TX.
• 36: 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, December 1998 [doi>10.1023/A:1018782528453]
• 37: Trung N. Nguyen , Zhiyuan Li, Interprocedural analysis for loop scheduling and data allocation, Parallel Computing, v.24 n.3-4, p.477-504, May, 1998 [doi>10.1016/S0167-8191(98)00022-2]
• 38: Object-Oriented Scientific Computing. 2001. Blitz++. Object-Oriented Scientific Computing, Available online at http://www.oonumerics.org/blitz/benchmarks/.
• 39: 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]
• 40: Preeti Ranjan Panda , Hiroshi Nakamura , Nikil D. Dutt , Alexandru Nicolau, Augmenting Loop Tiling with Data Alignment for Improved Cache Performance, IEEE Transactions on Computers, v.48 n.2, p.142-149, February 1999 [doi>10.1109/12.752655]
• 41: Neungsoo Park , Bo Hong , Viktor K. Prasanna, Analysis of Memory Hierarchy Performance of Block Data Layout, Proceedings of the 2002 International Conference on Parallel Processing (ICPP'02), p.35, August 18-21, 2002
• 42: William Pugh, A practical algorithm for exact array dependence analysis, Communications of the ACM, v.35 n.8, p.102-114, Aug. 1992 [doi>10.1145/135226.135233]
• 43: William Pugh , Evan Rosser, Iteration Space Slicing for Locality, Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing, p.164-184, August 04-06, 1999
• 44: William Pugh , Evan Rosser , Tatiana Shpeisman, Exploiting monotone convergence functions in parallel programs, University of Maryland at College Park, College Park, MD, 1996
• 45: Gabriel Rivera , Chau-Wen Tseng, A Comparison of Compiler Tiling Algorithms, Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'99, p.168-182, March 22-28, 1999
• 46: Gabriel Rivera , Chau-Wen Tseng, Tiling optimizations for 3D scientific computations, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.32-es, November 04-10, 2000, Dallas, Texas, United States
• 47: Evan Jenkins Rosser , William W. Pugh, Fine-grained analysis of array computations, 1998
• 48: Vivek Sarkar, Loop Transformations for Hierarchical Parallelism and Locality, Selected Papers from the 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, p.57-74, May 28-30, 1998
• 49: 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
• 50: Yonghong Song , Rong Xu , Cheng Wang , Zhiyuan Li, Data locality enhancement by memory reduction, Proceedings of the 15th international conference on Supercomputing, p.50-64, June 2001, Sorrento, Italy [doi>10.1145/377792.377806]
• 51: 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
• 52: O. Temam , C. Fricker , W. Jalby, Cache interference phenomena, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.261-271, May 16-20, 1994, Nashville, Tennessee, United States
• 53: David S. Wise , Jeremy D. Frens , Yuhong Gu , Gregory A. Alexander, Language support for Morton-order matrices, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.24-33, June 2001, Snowbird, Utah, United States
• 54: Michael Edward Wolf, Improving locality and parallelism in nested loops, Stanford University, Stanford, CA, 1992
• 55: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 56: David Wonnacott, Achieving Scalable Locality with Time Skewing, International Journal of Parallel Programming, v.30 n.3, p.181-221, June 2002 [doi>10.1023/A:1015460304860]
• 57: Jingling Xue, Loop tiling for parallelism, Kluwer Academic Publishers, Norwell, MA, 2000

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, Performance

Keywords:
Caches, loop transformations, optimizing compilers