Compile-time composition of run-time data and iteration reorderings

ABSTRACT

Many important applications, such as those using sparse data structures, have memory reference patterns that are unknown at compile-time. Prior work has developed run-time reorderings of data and computation that enhance locality in such applications.This paper presents a compile-time framework that allows the explicit composition of run-time data and iteration-reordering transformations. Our framework builds on the iteration-reordering framework of Kelly and Pugh to represent the effects of a given composition. To motivate our extension, we show that new compositions of run-time reordering transformations can result in better performance on three benchmarks.We show how to express a number of run-time data and iteration-reordering transformations that focus on improving data locality. We also describe the space of possible run-time reordering transformations and how existing transformations fit within it. Since sparse tiling techniques are included in our framework, they become more generally applicable, both to a larger class of applications, and in their composition with other reordering transformations. Finally, within the presented framework data need be remapped only once at runtime for a given composition thus exhibiting one example of overhead reductions the framework can express.

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: Memory Hierarchy Management for Iterative Graph Structures, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.298, March 30-April 03, 1998
• 3: Steve Carr , Kathryn S. McKinley , Chau-Wen Tseng, Compiler optimizations for improving data locality, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.252-262, October 05-07, 1994, San Jose, California, United States
• 4: E. Cuthill , J. McKee, Reducing the bandwidth of sparse symmetric matrices, Proceedings of the 1969 24th national conference, p.157-172, August 26-28, 1969 [doi>10.1145/800195.805928]
• 5: R. Das, D. Mavriplis, J. Saltz, S. Gupta, and R. Ponnusamy. The design and implementation of a parallel unstructured Euler solver using software primitives, AIAA-92-0562. In Proceedings of the 30th Aerospace Sciences Meeting, 1992.
• 6: Raja Das , Mustafa Uysal , Joel Saltz , Yuan-Shin Hwang, Communication optimizations for irregular scientific computations on distributed memory architectures, Journal of Parallel and Distributed Computing, v.22 n.3, p.462-478, Sept. 1994 [doi>10.1006/jpdc.1994.1104]
• 7: Chen Ding , Ken Kennedy, Improving cache performance in dynamic applications through data and computation reorganization at run time, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.229-241, May 01-04, 1999, Atlanta, Georgia, United States
• 8: Chen Ding , Ken Kennedy, Inter-array Data Regrouping, Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing, p.149-163, August 04-06, 1999
• 9: C. C. Douglas, J. Hu, M. Kowarschik, U. Rüde, and C. Weiss. Cache Optimization for Structured and Unstructured Grid Multigrid. Electronic Transaction on Numerical Analysis, 10:21--40, February 2000.
• 10: Brian Grant , Markus Mock , Matthai Philipose , Craig Chambers , Susan J. Eggers, DyC: an expressive annotation-directed dynamic compiler for C, Theoretical Computer Science, v.248 n.1-2, p.147-199, October 2000 [doi>10.1016/S0304-3975(00)00051-7]
• 11: E. Gutiérrez , R. Asenjo , O. Plata , E. L. Zapata, Automatic parallelization of irregular applications, Parallel Computing, v.26 n.13-14, p.1709-1738, Dec., 2000 [doi>10.1016/S0167-8191(00)00052-1]
• 12: Hwansoo Han , Chau-Wen Tseng, A Comparison of Locality Transformations for Irregular Codes, Selected Papers from the 5th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, p.70-84, May 25-27, 2000
• 13: Eun-Jin Im , Katherine A. Yelick, Optimizing Sparse Matrix Computations for Register Reuse in SPARSITY, Proceedings of the International Conference on Computational Sciences-Part I, p.127-136, May 28-30, 2001
• 14: 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
• 15: Wayne Kelly , William Pugh, Finding Legal Reordering Transformations Using Mappings, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.107-124, August 08-10, 1994
• 16: Wayne Kelly , William Pugh, A unifying framework for iteration reordering transformations, University of Maryland at College Park, College Park, MD, 1995
• 17: 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]
• 18: Wei Li , Keshav Pingali, A singular loop transformation framework based on non-singular matrices, International Journal of Parallel Programming, v.22 n.2, p.183-205, April 1994 [doi>10.1007/BF02577874]
• 19: Lee-Chung Lu, A unified framework for systematic loop transformations, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.28-38, April 21-24, 1991, Williamsburg, Virginia, United States
• 20: John Mellor-Crummey , David Whalley , Ken Kennedy, Improving memory hierarchy performance for irregular applications, Proceedings of the 13th international conference on Supercomputing, p.425-433, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305228]
• 21: Nicholas Mitchell , Larry Carter , Jeanne Ferrante, Localizing Non-Affine Array References, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.192, October 12-16, 1999
• 22: Nick Mitchell , Larry Carter , Jeanne Ferrante, A Modal Model of Memory, Proceedings of the International Conference on Computational Sciences-Part I, p.81-96, May 28-30, 2001
• 23: William Pugh , David Wonnacott, Nonlinear array dependence analysis, University of Maryland at College Park, College Park, MD, 1994
• 24: 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
• 25: Lawrence Rauchwerger , Nancy M. Amato , David A. Padua, Run-time methods for parallelizing partially parallel loops, Proceedings of the 9th international conference on Supercomputing, p.137-146, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224553]
• 26: Silvius Rus , Lawrence Rauchwerger , Jay Hoeflinger, Hybrid analysis: static & dynamic memory reference analysis, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514229]
• 27: Vivek Sarkar , Radhika Thekkath, A general framework for iteration-reordering loop transformations, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.175-187, June 15-19, 1992, San Francisco, California, United States
• 28: Jaswinder Pal Singh , Chris Holt , Takashi Totsuka , Anoop Gupta , John Hennessy, Load balancing and data locality in adaptive hierarchical N-body methods: Barnes-Hut, fast multipole, and radiosity, Journal of Parallel and Distributed Computing, v.27 n.2, p.118-141, June 1995 [doi>10.1006/jpdc.1995.1077]
• 29: Michelle Mills Strout , Larry Carter , Jeanne Ferrante, Rescheduling for Locality in Sparse Matrix Computations, Proceedings of the International Conference on Computational Sciences-Part I, p.137-148, May 28-30, 2001
• 30: M. M. Strout, L. Carter, J. Ferrante, J. Freeman, and B. Kreaseck. Combining performance aspects of irregular gauss-seidel via sparse tiling. In Proceedings of the 15th Workshop on Languages and Compilers for Parallel Computing (LCPC), July 2002.
• 31: William Thies , Frédéric Vivien , Jeffrey Sheldon , Saman Amarasinghe, A unified framework for schedule and storage optimization, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.232-242, June 2001, Snowbird, Utah, United States
• 32: 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
• 33: H. Yu, F. Dang, and L. Rauchwerger. Parallel reductions: An application of adaptive algorithm selection. In Proceedings of the 15th Workshop on Languages and Compilers for Parallel Computing (LCPC), July 2002.

INDEX TERMS

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

General Terms:
Experimentation, Performance

Keywords:
data remapping, inspector/executor, iteration reordering, optimization, run-time transformations, sparse tiling