Improving the Java memory model using CRF

ABSTRACT

This paper describes alternative memory semantics for Java programs using an enriched version of the Commit/Reconcile/Fence (CRF) memory model [16]. It outlines a set of reasonable practices for safe multithreaded programming in Java. Our semantics allow a number of optimizations such as load reordering that are currently prohibited. Simple thread-local algebraic rules express the effects of optimizations at the source or bytecode level. The rules focus on reordering source-level operations; they yield a simple dependency analysis algorithm for Java. An instruction-by-instruction translation of Java memory operations into CRF operations captures thread interactions precisely. The fine-grained synchronization of CRF means the algebraic rules are easily derived from the translation. CRF can be mapped directly to a modern architecture, and is thus a suitable target for optimizing memory coherence during code generation.

REFERENCES

• 1: 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]
• 2: Arvind , Alejandro Caro , Jan-Willem Maessen , Shail Aditya, A Multithreaded Substrate and Compilation Model for the Implicity Parallel Language pH, Proceedings of the 9th International Workshop on Languages and Compilers for Parallel Computing, p.519-533, August 08-10, 1996
• 3: Robert D. Blumofe , Matteo Frigo , Christopher F. Joerg , Charles E. Leiserson , Keith H. Randall, Dag-Consistent Distributed Shared Memory, Proceedings of the 10th International Parallel Processing Symposium, p.132-141, April 15-19, 1996
• 4: Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
• 5: G. R. Gao and V. Sarkar. Location Consistency -- A New Memory Model and Cache Coherence Protocol. Technical Memo 16, CAPSL Laboratory, Department of Electrical and Computer Engineering, University of Delaware, Feb. 1998.
• 6: Kourosh Gharachorloo, Memory consistency models for shared-memory multiprocessors, Stanford University, Stanford, CA, 1996
• 7: A. Gontmakher and A. Schuster. Java consistency: Non-operational characterizations for java memory behavior. Technion/CS Technical Report CS0922, Computer Science Department, Technion, Nov. 1997.
• 8: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 9: Java memory model mailing list.
• 10: L. Lamport. How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. IEEE Transactions on Computers, C-28(9):690-691, Sept. 1979.
• 11: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 12: Cathy May , Ed Silha , Rick Simpson , Hank Warren , CORPORATE International Business Machines, Inc., The PowerPC architecture: a specification for a new family of RISC processors, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994
• 13: 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]
• 14: John H. Reppy, Concurrent programming in ML, Cambridge University Press, New York, NY, 1999
• 15: Xiaowei Shen , Arvind, Design and verification of adaptive cache coherence protocols, 2000
• 16: Xiaowei Shen , Arvind , Larry Rudolph, Commit-reconcile & fences (CRF): a new memory model for architects and compiler writers, Proceedings of the 26th annual international symposium on Computer architecture, p.150-161, May 01-04, 1999, Atlanta, Georgia, United States
• 17: Richard L. Sites , Richard T. Witek, Alpha AXP architecture reference manual (2nd ed.), Digital Press, Newton, MA, 1995
• 18: CORPORATE SPARC International, Inc., The SPARC architecture manual (version 9), Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 19: John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.187-206, November 01-05, 1999, Denver, Colorado, United States

INDEX TERMS

Primary Classification:
  D. Software

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.0 General
          Subjects: Standards
      D.3.2 Language Classifications

          Nouns: Java

General Terms:
Design, Languages, Performance, Standardization, Theory

Keywords:
Java, commit/reconcile/fence, compilation, memory models