Synchronization optimizations for efficient execution on multi-cores

ABSTRACT

Multi-cores are becoming ubiquitous as exemplified by Sun's Niagra-2, Intel's Nehalem and AMD's Sau Paulo octal cores. The number of cores per chip is expected to rise in foreseeable future, as evidenced by the recently announced Intel's 80-core Teraflops Research Chip. Exploiting the parallelism of multicores necessitates concurrent software. One way to parallelize programs, not amenable to auto-parallelization, is via explicit synchronization. The placement of the synchronization primitives has a large bearing on how much thread-level parallelism (TLP) can be achieved. In this paper, we propose novel predication-based and other adjunct synchronization optimizations which facilitate exploitation on higher level of TLP than what can be achieved using the state-of-the-art. We demonstrate the efficacy of our techniques, on a real machine, using real codes, specifically, from the industry-standard SPEC CPU benchmarks and other widely used open source codes such as PostgreSQL. Our results show that the proposed techniques yield significantly higher levels of TLP than the state-of-the-art.

REFERENCES

• 1: S. F. Lundstrom and G. H. Barnes. A controllable MIMD architectures. In Proceedings of the 1980 International Conference on Parallel Processing, pages 19--27, St. Charles, IL, August 1980.
• 2: Utpal K. Banerjee, Dependence Analysis, Kluwer Academic Publishers, Norwell, MA, 1996
• 3: Alexandru Nicolau , Guangqiang Li , Arun Kejariwal, Techniques for efficient placement of synchronization primitives, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
• 4: OpenMP Specification, version 2.5. http://www.openmp.org/drupal/mp-documents/spec25.pdf.
• 5: SPEC CPU Benchmarks. http://www.spec.org/benchmarks.html.
• 6: PostgreSQL. http://www.postgresql.org/.
• 7: Arun Kejariwal , Xinmin Tian , Wei Li , Milind Girkar , Sergey Kozhukhov , Hideki Saito , Utpal Banerjee , Alexandru Nicolau , Alexander V. Veidenbaum , Constantine D. Polychronopoulos, On the performance potential of different types of speculative thread-level parallelism: The DL version of this paper includes corrections that were not made available in the printed proceedings, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia [doi>10.1145/1183401.1183407]
• 8: SPEC CINT2006. http://www.spec.org/cpu2006/CINT2006.
• 9: K. Karplus , A. Nicolau, Efficient hardware for multiway jumps and pre-fetches, Proceedings of the 18th annual workshop on Microprogramming, p.11-18, December 03-06, 1985, Pacific Grove, California, United States
• 10: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 11: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 12: J. A. Fisher, Trace Scheduling: A Technique for Global Microcode Compaction, IEEE Transactions on Computers, v.30 n.7, p.478-490, July 1981 [doi>10.1109/TC.1981.1675827]
• 13: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 14: Richard Johnson , Michael Schlansker, Analysis techniques for predicated code, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.100-113, December 02-04, 1996, Paris, France
• 15: John W. Sias , Wen-Mei W. Hwu , David I. August, Accurate and efficient predicate analysis with binary decision diagrams, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.112-123, December 2000, Monterey, California, United States [doi>10.1145/360128.360141]
• 16: L. Shen, Z. Wang, and J. Lu. Predicate analysis based on path information. In Advanced Parallel Processing Technologies, LNCS, 2834, pages 147--151, 2003.
• 17: J. R. Allen , Ken Kennedy , Carrie Porterfield , Joe Warren, Conversion of control dependence to data dependence, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.177-189, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567085]
• 18: J. Park and M. Schlansker. On predicated execution. Technical Report 58--91, Hewlett Packard Laboratories, 1991.
• 19: D. N. Pnevmatikatos , G. S. Sohi, Guarded execution and branch prediction in dynamic ILP processors, ACM SIGARCH Computer Architecture News, v.22 n.2, p.120-129, April 1994
• 20: David M. Gillies , Dz-ching Roy Ju , Richard Johnson , Michael Schlansker, Global predicate analysis and its application to register allocation, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.114-125, December 02-04, 1996, Paris, France
• 21: R. Fitzgerald, T. B. Knoblock, E. Ruf, B. Steensgaard, and D. Tarditi. Marmot: an optimizing compiler for Java. Technical report, Microsoft, November 1998.
• 22: Jonathan Aldrich , Craig Chambers , Emin Gün Sirer , Susan J. Eggers, Static Analyses for Eliminating Unnecessary Synchronization from Java Programs, Proceedings of the 6th International Symposium on Static Analysis, p.19-38, September 22-24, 1999
• 23: Allan Heydon , Marc Najork, Performance limitations of the Java core libraries, Proceedings of the ACM 1999 conference on Java Grande, p.35-41, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304092]
• 24: Jeff Bogda , Urs Hölzle, Removing unnecessary synchronization in Java, ACM SIGPLAN Notices, v.34 n.10, p.35-46, Oct. 1999
• 25: David F. Bacon , Ravi Konuru , Chet Murthy , Mauricio J. Serrano, Thin locks: featherweight Synchronization for Java, ACM SIGPLAN Notices, v.39 n.4, April 2004 [doi>10.1145/989393.989452]
• 26: Srinivas Sridharan , Arun Rodrigues , Peter Kogge, Evaluating synchronization techniques for light-weight multithreaded/multicore architectures, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248388]
• 27: Weirong Zhu , Vugranam C Sreedhar , Ziang Hu , Guang R. Gao, Synchronization state buffer: supporting efficient fine-grain synchronization on many-core architectures, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 28: Arun Kejariwal , Hideki Saito , Xinmin Tian , Milind Girkar , Wel Li , Utpal Banerjee , Alexandru Nicolau , Constantine D. Polychronopoulos, Lightweight lock-free synchronization methods for multithreading, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia [doi>10.1145/1183401.1183452]
• 29: Zahira Ammarguellat , W. L. Harrison, III, Automatic recognition of induction variables and recurrence relations by abstract interpretation, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.283-295, June 1990, White Plains, New York, United States
• 30: W. M. Pottenger. Induction variable substitution and reduction recognition in the Polaris parallelizing compiler. Master's thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, 1995.
• 31: Michael P. Gerlek , Eric Stoltz , Michael Wolfe, Beyond induction variables: detecting and classifying sequences using a demand-driven SSA form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.1, p.85-122, Jan. 1995 [doi>10.1145/200994.201003]
• 32: Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic analysis for parallelizing compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.477-518, July 1996 [doi>10.1145/233561.233568]
• 33: Peng Wu , Albert Cohen , Jay Hoeflinger , David Padua, Monotonic evolution: an alternative to induction variable substitution for dependence analysis, Proceedings of the 15th international conference on Supercomputing, p.78-91, June 2001, Sorrento, Italy [doi>10.1145/377792.377809]
• 34: David Gries, Compiler Construction for Digital Computers, John Wiley & Sons, Inc., New York, NY, 1971
• 35: A. V. Aho and J. D. Ullman. The theory of parsing, translation and compiling. In Compiling. Prentice-Hall, Englewood Cliffs, NJ, 1973.
• 36: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• 37: R. Cytron and J. Ferrante. What's in a name? or the value of renaming for parallelism detection and storage allocation. In Proceedings of the 1987 International Conference on Parallel Processing, St. Charles, IL, August 1987.
• 38: S. Weatherford. High level pattern matching extension to C++ for fortran program manipulation in Polaris. Master's thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, May 1994.
• 39: Wine. http://sourceforge.net/project/showfiles.php?group id=6241.
• 40: SPEC CPU2006. http://www.spec.org/cpu2006.
• 41: MySQL: The world's most popular open source database. http://www.mysql.com/.
• 42: A. Kejariwal and A. Nicolau. Reading list of mutual exclusion, locking, synchronization and concurrent objects. http://www.ics.uci.edu/-akejariw/ConcurrentExecutionReadingList.pdf.
• 43: R. Cytron. Doacross: Beyond vectorization for multiprocessors. In Proceedings of the 1986 International Conference on Parallel Processing, pages 836--844, St. Charles, IL, August 1986.
• 44: S. Midkiff and D. Padua. Compiler generated synchronization for DO loops. In Proceedings of the 1986 International Conference on Parallel Processing, pages 544--551, St. Charles, IL, August 1986.
• 45: H. Kasahara, H. Honda, M. Iwata, and M. Hirota. A compilation scheme for macro-dataow computation on hierarchical multiprocessor systems. In Proceedings of the International Conference on Parallel Processing, pages II294--II295, Urbana-Champaign, IL, August 1990.
• 46: Milind Baburao Girkar, Functional parallelism: theoretical foundations and implementation, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
• 47: R. Cytron , M. Hind , W. Hsieh, Automatic generation of DAG parallelism, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.54-68, June 19-23, 1989, Portland, Oregon, United States
• 48: V. Sarkar, Instruction reordering for fork-join parallelism, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.322-336, June 1990, White Plains, New York, United States
• 49: W. N. Scherer III and M. L. Scott. Nonblocking concurrent objects with condition synchronization. In Proceedings of the 18th International Symposium on Distributed Computing, Amsterdam, The Netherlands, Oct 2004.
• 50: F. Fich, D. Hendler, and N. Shavit. On the inherent weakness of conditional synchronization primitives. http://www.cs.tau.ac.il/-afek/Handler-conditionals.pdf.
• 51: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 52: Pedro Diniz , Martin Rinard, Synchronization transformations for parallel computing, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.187-200, January 15-17, 1997, Paris, France [doi>10.1145/263699.263718]
• 53: Pedro C. Diniz , Martin C. Rinard, Lock coarsening: eliminating lock overhead in automatically parallelized object-based programs, Journal of Parallel and Distributed Computing, v.49 n.2, p.218-244, March 15, 1998 [doi>10.1006/jpdc.1998.1441]
• 54: Martin C. Rinard, Effective fine-grain synchronization for automatically parallelized programs using optimistic synchronization primitives, ACM Transactions on Computer Systems (TOCS), v.17 n.4, p.337-371, Nov. 1999 [doi>10.1145/329466.329486]
• 55: Chau-Wen Tseng, Compiler optimizations for eliminating barrier synchronization, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.144-155, July 19-21, 1995, Santa Barbara, California, United States
• 56: S. S. Bhattacharyya, S. Sriram, and E. A. Lee. Resynchronization of multiprocessor schedules Part I: Fundamental concepts and unbounded latency analysis. Memorandum UCB/ERL M96/55, Electronics Research Laboratory, U. C. Berkeley, October 1996.
• 57: Ding-Kai Chen , Pen-Chung Yew, Redundant Synchronization Elimination for DOACROSS Loops, IEEE Transactions on Parallel and Distributed Systems, v.10 n.5, p.459-470, May 1999 [doi>10.1109/71.770138]
• 58: Alexandru Nicolau , Roni Potasman , Haigeng Wang, Register Allocation, Renaming and Their Impact on Fine-Grain Parallelism, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.218-235, August 07-09, 1991
• 59: Andreas Moshovos , Gurindar S. Sohi, Streamlining inter-operation memory communication via data dependence prediction, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.235-245, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 60: Gary S. Tyson , Todd M. Austin, Memory Renaming: Fast, Early and Accurate Processing of Memory Communication, International Journal of Parallel Programming, v.27 n.5, p.357-380, Oct. 1999 [doi>10.1023/A:1018734923512]
• 61: Glenn Reinman , Brad Calder , Dean Tullsen , Gary Tyson , Todd Austin, Classifying load and store instructions for memory renaming, Proceedings of the 13th international conference on Supercomputing, p.399-407, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305218]
• 62: K. Knobe and V. Sarkar. Array SSA form and its use in parallelization. pages 107--120, San Diego, CA, 1998.
• 63: Jean-Francois Collard, Array SSA for Explicitly Parallel Programs, Proceedings of the 5th International Euro-Par Conference on Parallel Processing, p.383-390, August 31-September 03, 1999
• 64: Silvius Rus , Guobin He , Christophe Alias , Lawrence Rauchwerger, Region array SSA, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA [doi>10.1145/1152154.1152165]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Performance

Keywords:
code motion, compilers, multithreading, synchronization