Stride prefetching by dynamically inspecting objects

ABSTRACT

Software prefetching is a promising technique to hide cache miss latencies, but it remains challenging to effectively prefetch pointer-based data structures because obtaining the memory address to be prefetched requires pointer dereferences. The recently proposed stride prefetching overcomes this problem, but it only exploits inter-iteration stride patterns and relies on an off-line profiling method.We propose a new algorithm for stride prefetching which is intended for use in a dynamic compiler. We exploit both inter- and intra-iteration stride patterns, which we discover using an ultra-lightweight profiling technique, called object inspection. This is a kind of partial interpretation that only a dynamic compiler can perform. During the compilation of a method, the dynamic compiler gathers the profile information by partially interpreting the method using the actual values of parameters and causing no side effects.We evaluated an implementation of our prefetching algorithm in a production-level Java just-in time compiler. The results show that the algorithm achieved up to an 18.9% and 25.1% speedup in industry-standard benchmarks on the Pentium 4 and the Athlon MP, respectively, while it increased the compilation time by less than 3.0%.

REFERENCES

• 1: Advanced Micro Devices, Inc. AMD Athlon Processor x86 Code Optimization Guide, Aug. 2001. Document Number 22007J.
• 2: 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
• 3: David Callahan , Ken Kennedy , Allan Porterfield, Software prefetching, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.40-52, April 08-11, 1991, Santa Clara, California, United States
• 4: Trishul M. Chilimbi , Martin Hirzel, Dynamic hot data stream prefetching for general-purpose programs, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 5: Sylvia Dieckmann , Urs Hölzle, A Study of the Allocation Behavior of the SPECjvm98 Java Benchmark, Proceedings of the 13th European Conference on Object-Oriented Programming, p.92-115, June 14-18, 1999
• 6: R. Dimpsey , R. Arora , K. Kuiper, Java server performance: a case study of building efficient, scalable Jvms, IBM Systems Journal, v.39 n.1, p.151-174, January 2000
• 7: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 8: Intel Corporation. Intel Itanium Architecture Software Developer's Manual Volume 3: Instruction Set Reference, 2001. Revision 2.0, Document Number 245319-003.
• 9: Intel Corporation. Intel Pentium 4 Processor Optimization Reference Manual, 2001. Document Number 248966.
• 10: Intel Corporation. VTune Performance Analyzer. http://www.intel.com/software/products/vtune, 2002.
• 11: Kazuaki Ishizaki , Motohiro Kawahito , Toshiaki Yasue , Mikio Takeuchi , Takeshi Ogasawara , Toshio Suganuma , Tamiya Onodera , Hideaki Komatsu , Toshio Nakatani, Design, implementation, and evaluation of optimizations in a just-in-time compiler, Proceedings of the ACM 1999 conference on Java Grande, p.119-128, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304111]
• 12: Java Grande Benchmarking Project. Java Grande Forum Benchmark Suite, Version 2.0. http://www.epcc.ed.ac.uk/javagrande, 1999.
• 13: 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
• 14: 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
• 15: Chi-Keung Luk , Todd C. Mowry, Automatic Compiler-Inserted Prefetching for Pointer-Based Applications, IEEE Transactions on Computers, v.48 n.2, p.134-141, February 1999 [doi>10.1109/12.752654]
• 16: 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
• 17: Proc. of the ACM SIGPLAN Conference on Programming Language Design and Implementation, June 2002.
• 18: Yefim Shuf , Mauricio J. Serrano , Manish Gupta , Jaswinder Pal Singh, Characterizing the memory behavior of Java workloads: a structured view and opportunities for optimizations, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.194-205, June 2001, Cambridge, Massachusetts, United States
• 19: CORPORATE SPARC International, Inc., The SPARC architecture manual (version 9), Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 20: Standard Performance Evaluation Corporation (SPEC). JVM Client98 (SPECjvm98). http://www.spec.org/osg/jvm98, 1998.
• 21: 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
• 22: T. Suganuma , T. Ogasawara , M. Takeuchi , T. Yasue , M. Kawahito , K. Ishizaki , H. Komatsu , T. Nakatani, Overview of the IBM Java just-in-time compiler, IBM Systems Journal, v.39 n.1, p.175-193, January 2000
• 23: Youfeng Wu, Efficient discovery of regular stride patterns in irregular programs and its use in compiler prefetching, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 24: Youfeng Wu , Mauricio J. Serrano , Rakesh Krishnaiyer , Wei Li , Jesse Fang, Value-Profile Guided Stride Prefetching for Irregular Code, Proceedings of the 11th International Conference on Compiler Construction, p.307-324, April 08-12, 2002

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: Memory management (garbage collection); Optimization; Compilers

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
Java just-in-time compiler, object inspection, stride prefetching