Dynamic hot data stream prefetching for general-purpose programs

ABSTRACT

Prefetching data ahead of use has the potential to tolerate the grow ing processor-memory performance gap by overlapping long latency memory accesses with useful computation. While sophisti cated prefetching techniques have been automated for limited domains, such as scientific codes that access dense arrays in loop nests, a similar level of success has eluded general-purpose pro grams, especially pointer-chasing codes written in languages such as C and C++. We address this problem by describing, implementing and evaluating a dynamic prefetching scheme. Our technique runs on stock hardware, is completely automatic, and works for general-purpose programs, including pointer-chasing codes written in weakly-typed languages, such as C and C++. It operates in three phases. First, the profiling phase gathers a temporal data reference profile from a running program with low-overhead. Next, the profiling is turned off and a fast analysis algorithm extracts hot data streams, which are data reference sequences that frequently repeat in the same order, from the temporal profile. Then, the system dynamically injects code at appropriate program points to detect and prefetch these hot data streams. Finally, the process enters the hibernation phase where no profiling or analysis is performed, and the program continues to execute with the added prefetch instructions. At the end of the hibernation phase, the program is de-optimized to remove the inserted checks and prefetch instructions, and control returns to the profiling phase. For long-running programs, this profile, analyze and optimize, hibernate, cycle will repeat multiple times. Our initial results from applying dynamic prefetching are promising, indicating overall execution time improvements of 5.19% for several memory-performance-limited SPECint2000 benchmarks running their largest (ref) inputs.

REFERENCES

• 1: Murali Annavaram , Jignesh M. Patel , Edward S. Davidson, Data prefetching by dependence graph precomputation, Proceedings of the 28th annual international symposium on Computer architecture, p.52-61, June 30-July 04, 2001, Göteborg, Sweden
• 2: Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.47-65, October 2000, Minneapolis, Minnesota, United States
• 3: Matthew Arnold , Barbara G. Ryder, A framework for reducing the cost of instrumented code, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.168-179, June 2001, Snowbird, Utah, United States
• 4: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 5: Brendon Cahoon , Kathryn S. McKinley, Data Flow Analysis for Software Prefetching Linked Data Structures in Java, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.280-291, September 08-12, 2001
• 6: M. Charney, and A. Reeves. "Generalized correlation based hardware prefetching." Tech report EE-CEG-95-1, Cornell University, 1995
• 7: Tien-Fu Chen , Jean-Loup Baer, Reducing memory latency via non-blocking and prefetching caches, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.51-61, October 12-15, 1992, Boston, Massachusetts, United States
• 8: Trishul M. Chilimbi, Efficient representations and abstractions for quantifying and exploiting data reference locality, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.191-202, June 2001, Snowbird, Utah, United States
• 9: Trishul M. Chilimbi , James R. Larus, Using generational garbage collection to implement cache-conscious data placement, Proceedings of the 1st international symposium on Memory management, p.37-48, October 17-19, 1998, Vancouver, British Columbia, Canada
• 10: Trishul M. Chilimbi, On the Stability of Temporal Data Reference Profiles, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.151, September 08-12, 2001
• 11: Michał Cierniak , Guei-Yuan Lueh , James M. Stichnoth, Practicing JUDO: Java under dynamic optimizations, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.13-26, June 18-21, 2000, Vancouver, British Columbia, Canada
• 12: Robert Cooksey , Dennis Colarelli , Dirk Grunwald, Content-Based Prefetching: Initial Results, Revised Papers from the Second International Workshop on Intelligent Memory Systems, p.33-55, November 12, 2000
• 13: D. Deaver, R. Gorton, and N. Rubin, "Wiggins/Redstone: An online program specializer.", In Hot Chips, 1999
• 14: Timothy L. Harris, Dynamic adaptive pre-tenuring, Proceedings of the 2nd international symposium on Memory management, p.127-136, October 15-16, 2000, Minneapolis, Minnesota, United States
• 15: M. Hirzel and T. Chilimbi. " Bursty Tracing: A Framework for Low-Overhead Temporal Profiling", In Workshop on Feed¿back-Directed and Dynamic Optimizations (FDDO), 2001
• 16: Doug Joseph , Dirk Grunwald, Prefetching using Markov predictors, Proceedings of the 24th annual international symposium on Computer architecture, p.252-263, June 01-04, 1997, Denver, Colorado, United States
• 17: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 18: M. Karlsson, F. Dahlgren, and P. Stenstrom. "A Prefetching Technique for Irregular Accesses to Linked Data Structures, In High Performance Computer Architectures (HPCA), 1999
• 19: Thomas Kistler , Michael Franz, Automated data-member layout of heap objects to improve memory-hierarchy performance, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.3, p.490-505, May 2000 [doi>10.1145/353926.353937]
• 20: Alexander C. Klaiber , Henry M. Levy, An architecture for software-controlled data prefetching, Proceedings of the 18th annual international symposium on Computer architecture, p.43-53, May 27-30, 1991, Toronto, Ontario, Canada
• 21: James R. Larus, Whole program paths, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.259-269, May 01-04, 1999, Atlanta, Georgia, United States
• 22: Chi-Keung Luk , Todd C. Mowry, Compiler-based prefetching for recursive data structures, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.222-233, October 01-04, 1996, Cambridge, Massachusetts, United States
• 23: Craig G. Nevill-Manning , Ian H. Witten, Linear-Time, Incremental Hierarchy Inference for Compression, Proceedings of the Conference on Data Compression, p.3, March 25-27, 1997
• 24: Todd C. Mowry , Monica S. Lam , Anoop Gupta, Design and evaluation of a compiler algorithm for prefetching, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.62-73, October 12-15, 1992, Boston, Massachusetts, United States
• 25: M. Paleczny, C. Vick, and C. Click. "The Java HotSpot server compiler.", In USENIX Java Virtual Machine Research and Technology Symposium (JVM), 2001
• 26: Amir Roth , Andreas Moshovos , Gurindar S. Sohi, Dependence based prefetching for linked data structures, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.115-126, October 02-07, 1998, San Jose, California, United States
• 27: Amir Roth , Gurindar S. Sohi, Effective jump-pointer prefetching for linked data structures, Proceedings of the 26th annual international symposium on Computer architecture, p.111-121, May 01-04, 1999, Atlanta, Georgia, United States
• 28: Shai Rubin , Rastislav Bodík , Trishul Chilimbi, An efficient profile-analysis framework for data-layout optimizations, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.140-153, January 16-18, 2002, Portland, Oregon
• 29: Rafael H. Saavedra , Daeyeon Park, Improving the Effectiveness of Software Prefetching with Adaptive Execution, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.68, October 20-23, 1996
• 30: Timothy Sherwood , Brad Calder, Automated design of finite state machine predictors for customized processors, Proceedings of the 28th annual international symposium on Computer architecture, p.86-97, June 30-July 04, 2001, Göteborg, Sweden
• 31: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• 32: A. Srivastava, A. Edwards, and H. Vo. "Vulcan: Binary trans¿formation in a distributed environment.", In Microsoft Re¿search Tech Report, MSR-TR-2001-50, 2001
• 33: Artour Stoutchinin , José N. Amaral , Guang R. Gao , James C. Dehnert , Suneel Jain , Alban Douillet, Speculative Prefetching of Induction Pointers, Proceedings of the 10th International Conference on Compiler Construction, p.289-303, April 02-06, 2001
• 34: D. Ung, and C. Cifuentes."Opimising hot paths in a dynamic binary translator."In Workshop on Binary Translation, 2000
• 35: Steven P. Vanderwiel , David J. Lilja, Data prefetch mechanisms, ACM Computing Surveys (CSUR), v.32 n.2, p.174-199, June 2000 [doi>10.1145/358923.358939]

INDEX TERMS

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

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

General Terms:
Measurement, Performance

Keywords:
data reference profiling, dynamic optimization, dynamic profiling, memory performance optimization, prefetching, temporal profiling