Improving cache performance in dynamic applications through data and computation reorganization at run time

ABSTRACT

With the rapid improvement of processor speed, performance of the memory hierarchy has become the principal bottleneck for most applications. A number of compiler transformations have been developed to improve data reuse in cache and registers, thus reducing the total number of direct memory accesses in a program. Until now, however, most data reuse transformations have been static---applied only at compile time. As a result, these transformations cannot be used to optimize irregular and dynamic applications, in which the data layout and data access patterns remain unknown until run time and may even change during the computation.In this paper, we explore ways to achieve better data reuse in irregular and dynamic applications by building on the inspector-executor method used by Saltz for run-time parallelization. In particular, we present and evaluate a dynamic approach for improving both computation and data locality in irregular programs. Our results demonstrate that run-time program transformations can substantially improve computation and data locality and, despite the complexity and cost involved, a compiler can automate such transformations, eliminating much of the associated run-time overhead.

REFERENCES

• 1: W. Abu-Sufah, D. Kuck, and D. Lawrie. On the performance enhancement of paging systems through program analysis and transformations. IEEE Transactions on Computers, C-30(5):341- 356, May 1981.
• 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: 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
• 4: Brad Calder , Chandra Krintz , Simmi John , Todd Austin, Cache-conscious data placement, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.139-149, October 02-07, 1998, San Jose, California, United States
• 5: 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
• 6: John B. Carter , Wilson C. Hsieh , Mark R. Swanson , Lixin Zhang , Erik Brunvand , Al Davis , Chen-Chi Kuo , Ravindra Kuramkote , Michael Parker , Lambert Schaelicke , Leigh Stoller , Terry Tateyama, Memory System Support for Irregular Applications, Selected Papers from the 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, p.17-26, May 28-30, 1998
• 7: Rohit Chandra , Ding-Kai Chen , Robert Cox , Dror E. Maydan , Nenad Nedeljkovic , Jennifer M. Anderson, Data distribution support on distributed shared memory multiprocessors, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.334-345, June 16-18, 1997, Las Vegas, Nevada, United States
• 8: Michał Cierniak , Wei Li, Unifying data and control transformations for distributed shared-memory machines, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.205-217, June 18-21, 1995, La Jolla, California, United States
• 9: R. Das, D. Mavriplis, J. Saltz, S. Gupta, and R. Ponnusamy. The design and implementation of a parallel unstructured euler solver using software primitives. In Proceedings of the 30th Aerospace Science Meeting, Reno, Navada, January 1992.
• 10: 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 ]
• 11: C. Ding. Improving effective bandwidth on machines with complex memory hierarchy. Thesis Proposal, Rice University, November 1998.
• 12: D. Gannon , W. Jalby , K. Gallivan, Strategies for cache and local memory management by global program transformation, Proceedings of the 1st International Conference on Supercomputing, p.229-254, March 1988, Athens, Greece
• 13: H. Han , C.-W. Tseng, Improving Compiler and Run-Time Support for Adaptive Irregular Codes, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.393, October 12-18, 1998
• 14: P. Havlak , K. Kennedy, An Implementation of Interprocedural Bounded Regular Section Analysis, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.350-360, July 1991 [doi>10.1109/71.86110 ]
• 15: Tor E. Jeremiassen , Susan J. Eggers, Reducing false sharing on shared memory multiprocessors through compile time data transformations, ACM SIGPLAN Notices, v.30 n.8, p.179-188, Aug. 1995
• 16: David G. Kirkpatrick , Pavol Hell, On the completeness of a generalized matching problem, Proceedings of the tenth annual ACM symposium on Theory of computing, p.240-245, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804353]
• 17: 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]
• 18: j. Mellor-Crummey, D. Whalley, and K. Kennedy. Improving memory hierarchy performance for irregular applications. Technical Report TR 99-336, Department of Computer Science, Rice University, Feburary 1999.
• 19: Matthew L. Seidl , Benjamin G. Zorn, Segregating heap objects by reference behavior and lifetime, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.12-23, October 02-07, 1998, San Jose, California, United States
• 20: Khalid Omar Thabit, Cache management by the compiler, 1982
• 21: Karen A. Tomko , Santosh G. Abraham, Data and program restructuring of irregular applications for cache-coherent multiprocessor, Proceedings of the 8th international conference on Supercomputing, p.214-225, July 11-15, 1994, Manchester, England [doi>10.1145/181181.181351]
• 22: 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

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments; Compilers

General Terms:
Algorithms, Design, Experimentation, Languages, Measurement, Performance, Theory