Automatic fence insertion for shared memory multiprocessing

ABSTRACT

In general, the hardware memory consistency model in a multiprocessor system is not identical to the memory model at the programming language level. Consequently, the programming language memory model must be mapped onto the hardware memory model. Memory fence instructions can be inserted by the compiler where needed to accomplish this mapping. We have developed and implemented several fence insertion and optimization algorithms in our Pensieve compiler project. We present the different fence insertion optimization techniques that were used in this system to guarantee sequential consistency at the language level, and compare them using performance data. Our techniques target two hardware relaxed memory consistency models provided by SMPs based on IBM Power 3 and Intel Pentium 4. Our fence insertion optimization shows up to 17.2% and 32.7% performance improvement on average, with the IBM PowerPC and Intel Pentium 4 (Xeon) multiprocessors respectively.

REFERENCES

• 1: Sarita V. Adve , Mark D. Hill, Weak ordering—a new definition, Proceedings of the 17th annual international symposium on Computer Architecture, p.2-14, May 28-31, 1990, Seattle, Washington, United States
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: Andrew W. Appel, Modern compiler implementation in Java, Cambridge University Press, New York, NY, 1997
• 4: Apple Computer, IBM, and Motorola. PowerPC Microprocessor Common Hardware Reference Platform. Morgan Kaufmann Publishers, Inc., 1995.
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: Intel Corporation, 2002. The IA-32 Intel® Architecture Software Developer's Manual.
• 7: M. Dubois , C. Scheurich , F. Briggs, Memory access buffering in multiprocessors, Proceedings of the 13th annual international symposium on Computer architecture, p.434-442, June 02-05, 1986, Tokyo, Japan
• 8: Xing Fang. Inserting fences to guarantee sequential consistency. Master's thesis, Department of Computer Science and Engineering, Michigan State University, August 2002. Technical Report MSU-CSE-02-27.
• 9: Michael R. Garey and David S. Johnson. Computers and Intractability. W. H. Freeman and Company, 1979.
• 10: Kourosh Gharachorloo , Daniel Lenoski , James Laudon , Phillip Gibbons , Anoop Gupta , John Hennessy, Memory consistency and event ordering in scalable shared-memory multiprocessors, Proceedings of the 17th annual international symposium on Computer Architecture, p.15-26, May 28-31, 1990, Seattle, Washington, United States
• 11: James R. Goodman. Cache consistency and sequential consistency. Technical Report CS-TR-91-1006, Department of Computer Science, University of Wisconsin, February 1991.
• 12: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 13: Leslie Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, C-28(9):690--691, September 1979.
• 14: Jaejin Lee, Compilation Techniques for Explicitly Parallel Programs, University of Illinois at Urbana-Champaign, Champaign, IL, 1999
• 15: 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
• 16: Jaejin Lee , David A. Padua, Hiding Relaxed Memory Consistency with a Compiler, IEEE Transactions on Computers, v.50 n.8, p.824-833, August 2001 [doi>10.1109/12.947002]
• 17: Zhiyuan Li , Walid Abu-Sufah, A technique for reducing synchronization overhead in large scale multiprocessors, Proceedings of the 12th annual international symposium on Computer architecture, p.284-291, June 17-19, 1985, Boston, Massachusetts, United States
• 18: Zhiyuan Li and Walid Abu-sufah. On reducing data synchronization in multiprocessed loops. IEEE Transactions on Computers, C-36(1):105--109, January 1987.
• 19: Samuel P. Midkiff and David A. Padua. Compiler generated synchronization for do loops. In the 1986 International Conference on Parallel Processing, pages 19--22, August 1986.
• 20: S. P. Midkiff , D. A. Padua, Compiler algorithms for synchronization, IEEE Transactions on Computers, v.36 n.12, p.1485-1495, Dec. 1987 [doi>10.1109/TC.1987.5009499]
• 21: 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]
• 22: 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]
• 23: Zehra Sura, Chi-Leung Wong, Xing Fang, Jaejin Lee, Samuel P. Midkiff, and David Padua. Automatic implementation of programming language consistency models. In Proceedings of The 15th International Workshop on Languages and Compilers for Parallel Computing (LCPC), July 2002.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

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

General Terms:
Languages, Performance

Keywords:
Java, compilers, consistency models