Techniques for efficient placement of synchronization primitives

ABSTRACT

Harnessing the hardware parallelism of the emerging multi-cores systems necessitates concurrent software. Unfortunately, most of the existing mainstream software is sequential in nature. Although one could auto-parallelize a given program, the efficacy of this is largely limited to floating-point codes. One of the ways to alleviate the above limitation is to parallelize programs, which cannot be auto-parallelized, via explicit synchronization. In this regard, efficient placement of the synchronization primitives - say, post, wait - plays a key role in achieving high degree of thread-level parallelism (TLP). In this paper, we propose novel compiler techniques for the above. Specifically, given a control flow graph (CFG), the proposed techniques place a post as early as possible and place a wait as late as possible in the CFG, subject to dependences. We demonstrate the efficacy of our techniques, on a real machine, using real codes, specifically, from the industry-standard SPEC CPU benchmarks, the Linux kernel and other widely used open source codes. Our results show that the proposed techniques yield significantly higher levels of TLP than the state-of-the-art.

REFERENCES

• 1: 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]
• 2: James R. Goodman , Mary K. Vernon , Philip J. Woest, Efficient synchronization primitives for large-scale cache-coherent multiprocessors, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.64-75, April 03-06, 1989, Boston, Massachusetts, United States
• 3: Jesús Labarta , Eduard Ayguadé, GTS: Extracting Full Parallelism Out of DO Loops, Proceedings of the Parallel Architectures and Languages Europe, Volume II: Parallel Languages, p.43-54, June 12-16, 1989
• 4: Gary Granunke , Shreekant Thakkar, Synchronization Algorithms for Shared-Memory Multiprocessors, Computer, v.23 n.6, p.60-69, June 1990 [doi>10.1109/2.55501]
• 5: Zhiyuan Li, Compiler algorithms for event variable synchronization, Proceedings of the 5th international conference on Supercomputing, p.85-95, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109051]
• 6: Arvind Krishnamurthy , Katherine Yelick, Optimizing parallel programs with explicit synchronization, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.196-204, June 18-21, 1995, La Jolla, California, United States
• 7: Alexander Aiken , David Gay, Barrier inference, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.342-354, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268974]
• 8: Alain Kagi , James R. Goodman, Mechanisms for efficient shared-memory, lock-based synchronization, The University of Wisconsin - Madison, 1999
• 9: Fast Synchronization on Scalable Cache-Coherent Multiprocessors using Hybrid Primitives, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.711, May 01-05, 2000
• 10: 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]
• 11: 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]
• 12: The Linux Kernel Archives. http://www.kernel.org.
• 13: 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]
• 14: Alexandru Nicolau, Percolation Scheduling: A Parallel Compilation Technique, Cornell University, Ithaca, NY, 1985
• 15: Wen-Mei W. Hwu , Scott A. Mahlke , William Y. Chen , Pohua P. Chang , Nancy J. Warter , Roger A. Bringmann , Roland G. Ouellette , Richard E. Hank , Tokuzo Kiyohara , Grant E. Haab , John G. Holm , Daniel M. Lavery, The superblock: an effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, v.7 n.1-2, p.229-248, May 1993 [doi>10.1007/BF01205185]
• 16: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Optimal code motion: theory and practice, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1117-1155, July 1994 [doi>10.1145/183432.183443]
• 17: Max Hailperin, Cost-optimal code motion, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1297-1322, Nov. 1998 [doi>10.1145/295656.295664]
• 18: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• 19: SPEC CPU Benchmarks. http://www.spec.org/benchmarks.html.
• 20: 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]
• 21: Utpal K. Banerjee, Dependence Analysis, Kluwer Academic Publishers, Norwell, MA, 1996
• 22: SPEC CPU2006. http://www.spec.org/cpu2006.
• 23: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 24: 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
• 25: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 26: SPEC CINT2006. http://www.spec.org/cpu2006/CINT2006.
• 27: Steven Novack , Alexandru Nicolau, A hierarchical approach to instruction-level parallelization, International Journal of Parallel Programming, v.23 n.1, p.35-62, Feb. 1995 [doi>10.1007/BF02577783]
• 28: A. Nicolau. Percolation scheduling. In Proceedings of the 1985 International Conference on Parallel Processing, August 1985.
• 29: K. Ebcioğlu , Toshio Nakatani, A new compilation technique for parallelizing loops with unpredictable branches on a VLIW architecture, Selected papers of the second workshop on Languages and compilers for parallel computing, p.213-229, May 1990, Urbana, Illinois, United States
• 30: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 31: SPEC CPU2000. http://www.spec.org/cpu2000.
• 32: Sendmail. http://www.sendmail.org/.
• 33: Apache. http://download.nextag.com/apache.
• 34: D. A. Padua. Multiprocessors: Discussion of theoritical and practical problems. Technical Report 79-990, Department of Computer Science, University of Illinois at Urbana-Champaign, November 1979.
• 35: J. Davies. Parallel loop constructs for multiprocessors. Technical Report 81-1070, Department of Computer Science, University of Illinois at Urbana-Champaign, May 1981.
• 36: C. Zhu and P. Yew. A synchronization scheme and its applications for large scale multiprocessors. In Proceedings of the Conference on Distributed Computing Systems, pages 486--491, San Francisco, CA, May 1984.
• 37: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 38: Dean M. Tullsen , Jack L. Lo , Susan J. Eggers , Henry M. Levy, Supporting Fine-Grained Synchronization on a Simultaneous Multithreading Processor, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.54, January 09-12, 1999
• 39: 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]
• 40: 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
• 41: 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
• 42: Alexandru Salcianu , Martin Rinard, Pointer and escape analysis for multithreaded programs, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.12-23, June 2001, Snowbird, Utah, United States
• 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: Chen Tian , Vijay Nagarajan , Rajiv Gupta , Sriraman Tallam, Dynamic recognition of synchronization operations for improved data race detection, Proceedings of the 2008 international symposium on Software testing and analysis, July 20-24, 2008, Seattle, WA, USA [doi>10.1145/1390630.1390649]

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
compilers, multithreading, parallelization, performance