Integrating non-blocking synchronisation in parallel applications: performance advantages and methodologies

ABSTRACT

In this paper we investigate how performance and speedup of applications would be affected by using non-blocking rather than blocking synchronisation in parallel systems. The results obtained show that for many applications, non-blocking synchronisation lead to significant speedups for a fairly large number of processors, while it never slows the applications down. As part of this investigation this paper also provides a set of efficient and simple translations that show how typical blocking operations found in parallel applications, such as simple locks, queues and lock trees can be translated into non-blocking equivalents that use hardware primitives common in modern multiprocessor systems. With these translations this paper clearly demonstrates that it is easy for the application designer/programmer to replace the blocking operations commonly found on with non-blocking equivalents ones. For the empirical results a set of representative applications running on a large-scale ccNUMA machine were used.

REFERENCES

• 1: A. Eichenberger and S. Abraham, Impact of Load Imbalance on the Design of Software Barriers, in Proceedings of the 1995 International Conference on Parallel Processing, pp. 63-72, August 1995.
• 2: M. Galles, Scalable Pipelined Interconnect for Distributed Endpoint Routing: The SGI Spider Chip, in Proceedings of Hot Interconnects IV, pp. 141-146, 1996.
• 3: Pat Hanrahan , David Salzman , Larry Aupperle, A rapid hierarchical radiosity algorithm, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.197-206, July 1991
• 4: A. Gottlieb, R. Grishman, C. P. Kruskal, K. P. McAuliffe, L. Rudolph and M. Snir, The NYU Ultracomputer --- Designing a MIMD Shared-Memory Parallel Machine", IEEE Trans. on Computers, 32(2), p. 175, February 1983.
• 5: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 6: Dongming Jiang , Jaswinder Pal Singh, A methodology and an evaluation of the SGI Origin2000, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.171-181, June 22-26, 1998, Madison, Wisconsin, United States
• 7: Anna R. Karlin , Kai Li , Mark S. Manasse , Susan Owicki, Empirical studies of competitve spinning for a shared-memory multiprocessor, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.41-55, October 13-16, 1991, Pacific Grove, California, United States
• 8: Alain Kägi , Doug Burger , James R. Goodman, Efficient synchronization: let them eat QOLB, Proceedings of the 24th annual international symposium on Computer architecture, p.170-180, June 01-04, 1997, Denver, Colorado, United States
• 9: James Laudon , Daniel Lenoski, The SGI Origin: a ccNUMA highly scalable server, Proceedings of the 24th annual international symposium on Computer architecture, p.241-251, June 01-04, 1997, Denver, Colorado, United States
• 10: D. Lenoski , J. Laudon , T. Joe , D. Nakahira , L. Stevens , A. Gupta , J. Hennessy, The DASH Prototype: Logic Overhead and Performance, IEEE Transactions on Parallel and Distributed Systems, v.4 n.1, p.41-61, January 1993 [doi>10.1109/71.205652 ]
• 11: Beng-Hong Lim , Anant Agarwal, Reactive synchronization algorithms for multiprocessors, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.25-35, October 05-07, 1994, San Jose, California, United States
• 12: Tom Lovett , Russell Clapp, STiNG: a CC-NUMA computer system for the commercial marketplace, Proceedings of the 23rd annual international symposium on Computer architecture, p.308-317, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 13: 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]
• 14: Maged M. Michael , Michael L. Scott, Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors, Journal of Parallel and Distributed Computing, v.51 n.1, p.1-26, May 25, 1998 [doi>10.1006/jpdc.1998.1446 ]
• 15: Jason Nieh , Marc Levoy, Volume rendering on scalable shared-memory MIMD architectures, Proceedings of the 1992 workshop on Volume visualization, p.17-24, October 19-20, 1992, Boston, Massachusetts, United States [doi>10.1145/147130.147141]
• 16: Dimitrios S. Nikolopoulos , Theodore S. Papatheodorou, A quantitative architectural evaluation of synchronization algorithms and disciplines on ccNUMA systems: the case of the SGI Origin2000, Proceedings of the 13th international conference on Supercomputing, p.319-328, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305209]
• 17: D. R. O'Hallaron, Spark98: Sparse Matrix Kernels for Shared Memory and Message Passing Systems, Technical Report CMU-CS-97-178, October 1997.
• 18: Edward Rothberg , Jaswinder Pal Singh , Anoop Gupta, Working sets, cache sizes, and node granularity issues for large-scale multiprocessors, Proceedings of the 20th annual international symposium on Computer architecture, p.14-26, May 16-19, 1993, San Diego, California, United States
• 19: SGI, SGI TechPubs Library, http://techpubs.sgi.com/, 2000.
• 20: Jaswinder Pal Singh , Anoop Gupta , Marc Levoy, Parallel Visualization Algorithms: Performance and Architectural Implications, Computer, v.27 n.7, p.45-55, July 1994 [doi>10.1109/2.299410 ]
• 21: Jaswinder Pal Singh , Wolf-Dietrich Weber , Anoop Gupta, SPLASH: Stanford parallel applications for shared-memory, ACM SIGARCH Computer Architecture News, v.20 n.1, p.5-44, March 1992 [doi>10.1145/130823.130824]
• 22: Philippas Tsigas , Yi Zhang, A simple, fast and scalable non-blocking concurrent FIFO queue for shared memory multiprocessor systems, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.134-143, July 2001, Crete Island, Greece [doi>10.1145/378580.378611]
• 23: Philippas Tsigas , Yi Zhang, Evaluating the performance of non-blocking synchronization on shared-memory multiprocessors, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.320-321, June 2001, Cambridge, Massachusetts, United States
• 24: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy
• 25: Steven Cameron Woo , Jaswinder Pal Singh , John L. Hennessy, The performance advantages of integrating block data transfer in cache-coherent multiprocessors, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.219-229, October 05-07, 1994, San Jose, California, United States
• 26: Kenneth C. Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro, v.16 n.2, p.28-40, April 1996 [doi>10.1109/40.491460 ]
• 27: J. Zahorjan , E. D. Lazowska , D. L. Eager, The Effect of Scheduling Discipline on Spin Overhead in Shared Memory Parallel Systems, IEEE Transactions on Parallel and Distributed Systems, v.2 n.2, p.180-198, April 1991 [doi>10.1109/71.89064 ]