Algorithms for scalable synchronization on shared-memory multiprocessors

ABSTRACT

Busy-wait techniques are heavily used for mutual exclusion and barrier synchronization in shared-memory parallel programs. Unfortunately, typical implementations of busy-waiting tend to produce large amounts of memory and interconnect contention, introducing performance bottlenecks that become markedly more pronounced as applications scale. We argue that this problem is not fundamental, and that one can in fact construct busy-wait synchronization algorithms that induce no memory or interconnect contention. The key to these algorithms is for every processor to spin on separate locally-accessible flag variables, and for some other processor to terminate the spin with a single remote write operation at an appropriate time. Flag variables may be locally-accessible as a result of coherent caching, or by virtue of allocation in the local portion of physically distributed shared memory. We present a new scalable algorithm for spin locks that generates 0(1) remote references per lock acquisition, independent of the number of processors attempting to acquire the lock. Our algorithm provides reasonable latency in the absence of contention, requires only a constant amount of space per lock, and requires no hardware support other than a swap-with-memory instruction. We also present a new scalable barrier algorithm that generates 0(1) remote references per processor reaching the barrier, and observe that two previously-known barriers can likewise be cast in a form that spins only on locally-accessible flag variables. None of these barrier algorithms requires hardware support beyond the usual atomicity of memory reads and writes. We compare the performance of our scalable algorithms with other software approaches to busy-wait synchronization on both a Sequent Symmetry and a BBN Butterfly. Our principal conclusion is that contention due to synchronization need not be a problem in large-scale shared-memory multiprocessors. The existence of scalable algorithms greatly weakens the case for costly special-purpose hardware support for synchronization, and provides a case against so-called “dance hall” architectures, in which shared memory locations are equally far from all processors. —From the Authors' Abstract

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: A. Agarwal , M. Cherian, Adaptive backoff synchronization techniques, Proceedings of the 16th annual international symposium on Computer architecture, p.396-406, April 1989, Jerusalem, Israel
• 3: A. Agarwal , R. Simoni , J. Hennessy , M. Horowitz, An evaluation of directory schemes for cache coherence, Proceedings of the 15th Annual International Symposium on Computer architecture, p.280-298, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 4: G. S. Almasi , A. Gottlieb, Highly parallel computing, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1989
• 5: T. E. Anderson, The Performance of Spin Lock Alternatives for Shared-Money Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.6-16, January 1990 [doi>10.1109/71.80120]
• 6: T. E. Anderson , E. D. Lazowska , H. M. Levy, The Performance Implications of Thread Management Alternatives for Shared-Memory Multiprocessors, IEEE Transactions on Computers, v.38 n.12, p.1631-1644, December 1989 [doi>10.1109/12.40843]
• 7: James Archibald , Jean Loup Baer, An economical solution to the cache coherence problem, Proceedings of the 11th annual international symposium on Computer architecture, p.355-362, January 1984
• 8: BBN Laboratories. Butterfly parallel processor overview. Tech. Rep. 6148, version 1, BBN Laboratories, Cambridge, Mass, Mar. 1986.
• 9: Eugene D. Brooks, III, The butterfly barrier, International Journal of Parallel Programming, v.15 n.4, p.295-307, Oct. 1986 [doi>10.1007/BF01407877]
• 10: BZOOKS, E. D., III. The shared memory hypercube. Parallel Comput. 6 (1988), 235-245.
• 11: Helen Davis , John Hennessy, Characterizing the synchronization behavior of parallel programs, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.198-211, July 19-21, 1988, New Haven, Connecticut, United States
• 12: E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
• 13: 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
• 14: 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
• 15: J. R. Goodman , P. J. Woest, The Wisconsin multicube: a new large-scale cache-coherent multiprocessor, Proceedings of the 15th Annual International Symposium on Computer architecture, p.422-431, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 16: GOTTLIEB, A. Scalability, combining and the NYU ultracomputer. Ohio State University Parallel Computing Workshop, Mar. 1990. Invited Lecture.
• 17: GOTTLIEB, A., GRISHMAN, R., KRUSKAL, C. P., McAuLIFFE, K. P., RUDOLPH, L., AND SNIR, M. The NYU Ultracomputer--Designing an MIMD shared memory parallel computer. IEEE Trans. Comput. C-32, 2 (Feb. 1983), 175-189.
• 18: 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]
• 19: Debra Hensgen , Raphael Finkel , Udi Manber, Two algorithms for barrier synchronization, International Journal of Parallel Programming, v.17 n.1, p.1-17, Feb. 1988 [doi>10.1007/BF01379320]
• 20: M. Herlihy, A methodology for implementing highly concurrent data structures, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.197-206, March 14-16, 1990, Seattle, Washington, United States
• 21: JAYASIMHA, D. N. Distributed synchronizers. In Proceedings of the 1988 Internatwnal Conference on Parallel Processing (Aug. 1988), 23-27.
• 22: Clyde P Kruskal , Larry Rudolph , Marc Snir, Efficient synchronization of multiprocessors with shared memory, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.218-228, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10609]
• 23: KUMAR, M., AND PFISTER, G.F. The onset of hot spot contention In Proceedings of the 1986 International Conference on Parallel Processing (1986), 28-34.
• 24: Leslie Lamport, A new solution of Dijkstra's concurrent programming problem, Communications of the ACM, v.17 n.8, p.453-455, Aug. 1974 [doi>10.1145/361082.361093]
• 25: Leslie Lamport, The mutual exclusion problem: part I—a theory of interprocess communication, Journal of the ACM (JACM), v.33 n.2, p.313-326, April 1986 [doi>10.1145/5383.5384]
• 26: Leslie Lamport, A fast mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.1-11, Feb. 1987 [doi>10.1145/7351.7352]
• 27: LEE, C.A. Barrier synchronization over multistage interconnection networks. In Proceedrags of the Second IEEE Symposium on Parallel and Distributed Processing (Dallas, Tex, Dec 1990), 130-133.
• 28: Joonwon Lee , Umakishore Ramachandran, Synchronization with multiprocessor caches, ACM SIGARCH Computer Architecture News, v.18 n.3a, p.27-37, June 1990
• 29: LUBACHEVSK~, B. An approach to automating the verification of compact parallel coordination programs. I Acta Inf. 21 (1984), 125-169.
• 30: LUBACnEVSKY, B. Synchronization barrier and related tools for shared memory parallel programming. In Proceedings of the 1989 International Converence on Parallel Processing (Aug 1989), II-175-II-179.
• 31: Mamoru Maekawa, A N algorithm for mutual exclusion in decentralized systems, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.145-159, May 1985 [doi>10.1145/214438.214445]
• 32: MELLOR-CRUMMEY, J.M. Concurrent queues: Practical fetch-and-~ algorithms. Tech. Rep. 229, Computer Science Dept., Univ. of Rochester, Nov. 1987.
• 33: J. M. Mellor-Crummey , M. L. Scott, Algorithms for Scalable Synchronization on Shared-Memory Multiproceessors, University of Rochester, Rochester, NY, 1990
• 34: John K. Ousterhout , Donald A. Scelza , Pradeep S. Sindhu, Medusa: an experiment in distributed operating system structure, Communications of the ACM, v.23 n.2, p.92-105, Feb. 1980 [doi>10.1145/358818.358823]
• 35: P1596 Working Group of the IEEE Computer Society Microprocessor Standards Committee. SCI (scalable coherent interface): An overview of extended cache-coherence protocols, Feb 5, 1990. Draft 0.59 P1596/Part III-D.
• 36: Gary L. Peterson, A New Solution to Lamport's Concurrent Programming Problem Using Small Shared Variables, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.56-65, Jan. 1983 [doi>10.1145/357195.357199]
• 37: PFISTER, G., BRANTLEY, W. C., GEORGE, D. A., HARVEY, S. L., KLEINFELDER, W. J., McAvLIFFE, K. P., MELTON, T. A., NORTON, V A., AND WEISS, J. The IBM research parallel processor prototype (RP3): Introduction and architecture. In Proceedings of the 1985 International Conference on Parallel Processing (Aug. 1985), 764-771.
• 38: PFISTER, G., AND NORTON, V. A. "Hot spot" contention and combining in multistage interconnection networks. IEEE Trans. Comput. C-34, 10 (Oct. 1985), 943 948.
• 39: Kerry Raymond, A tree-based algorithm for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.7 n.1, p.61-77, Feb. 1989 [doi>10.1145/58564.59295]
• 40: M. Raynal , D. Beeson, Algorithms for mutual exclusion, MIT Press, Cambridge, MA, 1986
• 41: David P. Reed , Rajendra K. Kanodia, Synchronization with eventcounts and sequencers, Communications of the ACM, v.22 n.2, p.115-123, Feb. 1979 [doi>10.1145/359060.359076]
• 42: Randall D. Rettberg , William R. Crowther , Philip P. Carvey , Raymond S. Tomlinson, The Monarch Parallel Processor Hardware Design, Computer, v.23 n.4, p.18-28, 30, April 1990 [doi>10.1109/2.55467]
• 43: Glenn Ricart , Ashok K. Agrawala, An optimal algorithm for mutual exclusion in computer networks, Communications of the ACM, v.24 n.1, p.9-17, Jan. 1981 [doi>10.1145/358527.358537]
• 44: Larry Rudolph , Zary Segall, Dynamic decentralized cache schemes for mimd parallel processors, Proceedings of the 11th annual international symposium on Computer architecture, p.340-347, January 1984
• 45: Beverly A. Sanders, The information structure of distributed mutual exclusion algorithms, ACM Transactions on Computer Systems (TOCS), v.5 n.3, p.284-299, Aug. 1987 [doi>10.1145/24068.28052]
• 46: Fred B. Schneider, Synchronization in Distributed Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.125-148, April 1982 [doi>10.1145/357162.357163]
• 47: M. L. Scott , T. J. LeBlanc , B. D. Marsh, Multi-model parallel programming in psyche, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.70-78, March 14-16, 1990, Seattle, Washington, United States
• 48: TANG, P., AND YEW, P.-C. Processor self-scheduling for multiple-nested parallel loops. In Proceedtngs of the 1986 International Conference on Parallel Processing (Aug. 1986), 528-535.
• 49: TANG, P., AND Y~W, P.-C. Algorithms for distributing hot-spot addressing CSRD Rep. 617, Center for Supercomputing Research and Development, Univ. of Illinois at Urbana- Champaign, Jan. 1987.
• 50: YEW, P.-C. Architecture of the Cedar parallel supercomputer. CSRD Rep 609, Center for Supercomputing Research and Development, Univ. of Illinois at Urbana-Champaign, Aug. 1986.
• 51: P.-C. Yew , N.-F. Tzeng , D. H. Lawrie, Distributing hot-spot addressing in large-scale multiprocessors, IEEE Transactions on Computers, v.36 n.4, p.388-395, April 1987 [doi>10.1109/TC.1987.1676921]
• 52: ZAHORIAN, J., LAZOWSKA, E. D., AND EAGER, D. L. The effect of scheduling discipline on spin overhead in shared memory parallel processors. Tech. Rep. TR-89-07-03, Computer Science Dept., Univ. of Washington, July 1989.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Mutual exclusion
      D.4.2 Storage Management
          Subjects: Storage hierarchies
      D.4.8 Performance
          Subjects: Measurements

General Terms:
Algorithms, Design, Measurement, Performance