Compiler techniques for high performance sequentially consistent java programs

ABSTRACT

The rise of Java, C#, and other explicitly parallel languages has increased the importance of compiling for different software memory models. This paper describes co-operating escape, thread structure, and delay set analyses that enable high performance for sequentially consistent programs.We compare the performance of a set of Java programs compiled for sequential consistency (SC) with the performance of the same programs compiled for weak consistency. For SC, we observe a slowdown of 10% on average for an architecture based on the Intel Xeon processor, and 26% on average for an architecture based on the IBM Power3.

REFERENCES

• 1: The Java Grande Forum multi-threaded benchmarks. URL: http://www.epcc.ed.ac.uk/javagrande/threads/contents.html.
• 2: Sarita V. Adve , Kourosh Gharachorloo, Shared Memory Consistency Models: A Tutorial, Computer, v.29 n.12, p.66-76, December 1996 [doi>10.1109/2.546611]
• 3: B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
• 4: David Callahan , Jaspal Sublok, Static analysis of low-level synchronization, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.100-111, May 05-06, 1988, Madison, Wisconsin, United States
• 5: Wei-Yu Chen, Arvind Krishnamurthy, and Katherine Yelick. Polynomial-time algorithms for enforcing sequential consistency in SPMD programs with arrays. In Sixteenth Annual Workshop on Languages and Compilers for Parallel Computing, October 2003.
• 6: The Standard Performance Evaluation Corporation. SPEC JVM Client98 suite. 1998. URL: http://www.specbench.org/jvm98/jvm98.
• 7: The Standard Performance Evaluation Corporation. SPEC JBB 2000 benchmark. 2000. URL: http://www.specbench.org/jbb2000.
• 8: Evelyn Duesterwald , Mary Lou Soffa, Concurrency analysis in the presence of procedures using a data-flow framework, Proceedings of the symposium on Testing, analysis, and verification, p.36-48, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120811]
• 9: Xing Fang , Jaejin Lee , Samuel P. Midkiff, Automatic fence insertion for shared memory multiprocessing, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782854]
• 10: Chris Gniady , Babak Falsafi , T. N. Vijaykumar, Is SC + ILP = RC?, Proceedings of the 26th annual international symposium on Computer architecture, p.162-171, May 01-04, 1999, Atlanta, Georgia, United States
• 11: Stephen J. Hartley, Concurrent programming: the Java programming language, Oxford University Press, Inc., New York, NY, 1998
• 12: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 13: Mark D. Hill, Multiprocessors Should Support Simple Memory-Consistency Models, Computer, v.31 n.8, p.28-34, August 1998 [doi>10.1109/2.707614]
• 14: JavaMemoryModel. Java memory model mailing list. 2003. www.cs.umd.edu/~pugh/java/memoryModel.
• 15: Arvind Krishnamurthy , Katherine A. Yelick, Optimizing Parallel SPMD Programs, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.331-345, August 08-10, 1994
• 16: Arvind Krishnamurthy , Katherine Yelick, Analyses and optimizations for shared address space programs, Journal of Parallel and Distributed Computing, v.38 n.2, p.130-144, Nov. 1, 1996 [doi>10.1006/jpdc.1996.0136]
• 17: Leslie Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, C-28(9):690--691, September 1979.
• 18: Doug Lea. Concurrency utilities package, precursor to Java specification request (JSR) 166: Concurrency utilities. gee.cs.oswego.edu/dl/concurrency-interest .
• 19: Doug Lea , Douglas Lea, Concurrent Programming in Java. Second Edition: Design Principles and Patterns, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 20: Jaejin Lee , David A. Padua, Hiding Relaxed Memory Consistency with Compilers, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.111, October 15-19, 2000
• 21: Ben Liblit, Alex Aiken, and Katherine Yelick. Type systems for distributed data sharing. In Proceedings of the Tenth International Static Analysis Symposium, 2003.
• 22: Stephen P. Masticola , Barbara G. Ryder, Non-concurrency analysis, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.129-138, May 19-22, 1993, San Diego, California, United States
• 23: Samuel P. Midkiff, Dependence Analysis in Parallel Loops with i±k Subscripts, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.331-345, August 10-12, 1995
• 24: S. Midkiff and D. Padua. Issues in the compile-time optimization of parallel programs. In Proceedings of the 1990 International Conference on Parallel Processing, Vol. II, pages 105--113, August 1990.
• 25: Samuel P. Midkiff , David A. Padua , Ron Cytron, Compiling programs with user parallelism, Selected papers of the second workshop on Languages and compilers for parallel computing, p.402-422, May 1990, Urbana, Illinois, United States
• 26: Gleb Naumovich , George S. Avrunin , Lori A. Clarke, An efficient algorithm for computing MHP information for concurrent Java programs, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.338-354, September 06-10, 1999, Toulouse, France
• 27: William Pugh, Fixing the Java memory model, Proceedings of the ACM 1999 conference on Java Grande, p.89-98, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304106]
• 28: Parthasarathy Ranganathan , Vijay S. Pai , Sarita V. Adve, Using speculative retirement and larger instruction windows to narrow the performance gap between memory consistency models, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.199-210, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258512]
• 29: Dennis Shasha , Marc Snir, Efficient and correct execution of parallel programs that share memory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.2, p.282-312, April 1988 [doi>10.1145/42190.42277]
• 30: Zehra Noman Sura , David Padua, Analyzing threads for shared memory consistency, University of Illinois at Urbana-Champaign, Champaign, IL, 2004
• 31: Christoph von Praun. Efficient computation of communicator variables for programs with unstructured parallelism. In Seventeenth Annual Workshop on Languages and Compilers for Parallel Computing, September 2004.
• 32: K. Yelick, L. Semenzato, G. Pike, C. Miyamoto, B. Liblit, A. Krishnamurthy, P. Hilfinger, S. Graham, D. Gay, P. Colella, and A. Aiken. Titanium: A high-performance Java dialect. In ACM 1998 Workshop on Java for High-Performance Network Computing. ACM SIGPLAN, 1998.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Experimentation, Languages, Performance

Keywords:
java, memory consistency, multithread, synchronization