Diffracting trees

ABSTRACT

Shared counters are among the most basic coordination structures in multiprocessor conputation, with applications ranging from barrier synchronization to concurrent-data-structure design. This article introduces diffracting trees, novel data structures for share counting and load balancing in a distributed/parallel environment. Empirical evidence, collected on a simulated distributed shared-memory machine and several simulated message-passing architectures, shows that diffracting trees scale better and are more robust than both combining trees and counting networks, currently the most effective known methods for implementing concurrent counters in software. The use of a randomized coordination method together with a combinatorial data structure overcomes the resiliency drawbacks of combining trees. Our simulations show that to handle the same load, diffracting trees and counting networks should have a similar width w, yet the depth of a diffracting tree is O(log w), whereas counting networks have depth O(log2 w). Diffracting trees have already been used to implement highly efficient producer/consumer queues, and we believe diffraction will prove to be an effective alternative paradigm to combining and queue-locking in the design of many concurrent data structures.

REFERENCES

• 1: 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
• 2: A. Agarwal , D. Chaiken , K. Johnson , D. Kranz , J. Kubiatowicz , K. Kurihara , B. H. Lim , G. Maa , D. Nussbaum , M. Parkin , D. Yeung, THE MIT ALEWIFE MACHINE: A LARGE-SCALE DISTRIBUTED-MEMORY MULTIPROCESSOR, Massachusetts Institute of Technology, Cambridge, MA, 1991
• 3: Anant Agarwal , John Kubiatowicz , David Kranz , Beng-Hong Lim , Donald Yeung , Godfrey D'Souza , Mike Parkin, Sparcle: An Evolutionary Processor Design for Large-Scale Multiprocessors, IEEE Micro, v.13 n.3, p.48-61, May 1993 [doi>10.1109/40.216748]
• 4: Eran Aharonson , Hagit Attiya, Counting networks with arbitrary fan-out, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.104-113, September 1992, Orlando, Florida, United States
• 5: William Aiello , Ramarathnam Venkatesan , Moti Yung, Coins, weights and contention in balancing networks, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.193-205, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198090]
• 6: 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]
• 7: James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks and multi-processor coordination, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.348-358, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103421]
• 8: BATCHER, K.E. 1968. Sorting networks and their applications. In Proceedings of the AFIPS Joint Computer Conference. AFIPS, Montvale, N.J., 334-338.
• 9: BLUMOFE, R.D. AND LEISERSON, C.E. 1994. Scheduling multithreaded computations by work stealing. In Proceedings of the 35th Symposium on the Foundations of Computer Science. IEEE, New York, 356-368.
• 10: E. A. Brewer , C. N. Dellarocas , A. Colbrook , W. E. Weihl, PROTEUS: A HIGH-PERFORMANCE PARALLEL-ARCHITECTURE SIMULATOR, Massachusetts Institute of Technology, Cambridge, MA, 1991
• 11: Costas Busch , Marios Mavronicolas, A combinatorial treatment of balancing networks, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.206-215, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198092]
• 12: Costas Busch , Marios Mavronicolas, A logarithmic depth counting network, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.274, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.225012]
• 13: Sarantos Kapidakis , Marios Mavronicolas, Load balancing networks, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.275, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.225013]
• 14: COVINGTON, R.G., DWARKADAS, S., JUMP, J.R., SINCLAIR, J.B., AND MADALA, S. 1991. The efficient simulation of parallel computer systems. Int. J. Comput. Simul. 1, 31-58.
• 15: CRAY. 1996. CRAY T3D system architecture overview. Cray Research, Inc., Mountain View, Calif. Available as http://www.cray.com/public/product-info/mpp/T3D_Architecture_Over.
• 16: DEC. 1994. Alpha System Reference Manual. Digital Equipment Corp., Maynard, Mass.
• 17: Cynthia Dwork , Maurice Herlihy , Orli Waarts, Contention in shared memory algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.174-183, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167145]
• 18: FELTEN, E.W., LAMARCA, A., AND LADNER, R. 1993. Building counting networks from larger balancers. Tech. Rep. 93-04-09, Univ. of Washington, Seattle, Wash.
• 19: Eric Freudenthal , Allan Gottlieb, Process coordination with fetch-and-increment, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.260-268, April 08-11, 1991, Santa Clara, California, United States
• 20: GAWLICK, D. 1985. Processing 'hot spots' in high performance systems. In Proceedings of IEEE COMPCON '85. IEEE, New York.
• 21: 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
• 22: Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983 [doi>10.1145/69624.357206]
• 23: 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]
• 24: 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]
• 25: Maurice Herlihy , Beng-Hong Lim , Nir Shavit, Low contention load balancing on large-scale multiprocessors, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.219-227, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140924]
• 26: Maurice Herlihy , Nir Shavit , Orli Waarts, Low contention linearizable counting, Proceedings of the 32nd annual symposium on Foundations of computer science, p.526-537, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185415]
• 27: Kai Hwang, Advanced Computer Architecture: Parallelism,Scalability,Programmability, McGraw-Hill Higher Education, 1992
• 28: JUMP, J.R. 1994. Netsim Reference Manual. Rice Univ., Houston, Tex. Available via ftp from titan.cs.rice.edu as/public/parallel/sim.tar.Z.
• 29: KIRKPATRICK, S., GELATT, C.D., AND VECCHI, M.P. 1983. Optimization by simulated annealing. Science 220, 671-680.
• 30: Michael Klugerman , C. Greg Plaxton, Small-depth counting networks, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.417-428, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129752]
• 31: 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
• 32: Reinhard Lüling , Burkhard Monien, A dynamic distributed load balancing algorithm with provable good performance, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.164-172, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165252]
• 33: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 34: Nancy A. Lynch , Mark R. Tuttle, Hierarchical correctness proofs for distributed algorithms, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.137-151, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41852]
• 35: Udi Manber, On maintaining dynamic information in a concurrent environment, SIAM Journal on Computing, v.15 n.4, p.1130-1142, Nov. 1986 [doi>10.1137/0215082]
• 36: MIPS. 1994. The MIPS RISC Architecture. MIPS Computer Co., Mountain View, Calif.
• 37: J. M. Mellor-Crummey , T. J. LeBlanc, A software instruction counter, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.78-86, April 03-06, 1989, Boston, Massachusetts, United States
• 38: J. M. Mellor-Crummey , M. L. Scott, Algorithms for Scalable Synchronization on Shared-Memory Multiproceessors, University of Rochester, Rochester, NY, 1990
• 39: PFISTER, G.H. AND NORTON, A. 1985. 'Hot-spot' contention and combining in multistage interconnection networks. IEEE Trans. Comput. C-34, 11 (Nov.), 933-938.
• 40: Larry Rudolph , Miriam Slivkin-Allalouf , Eli Upfal, A simple load balancing scheme for task allocation in parallel machines, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.237-245, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113401]
• 41: Nir Shavit , Dan Touitou, Elimination trees and the construction of pools and stacks: preliminary version, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.54-63, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215419]
• 42: Nir Shavit , Asaph Zemach, Diffracting trees (preliminary version), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.167-176, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181326]
• 43: Nir Shavit , Eli Upfal , Asaph Zemach, A steady state analysis of diffracting trees (extended abstract), Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.33-41, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237505]
• 44: STONE, H.S. 1984. Database applications of the fetch-and-add instruction. IEEE Trans. Comput. C-33, 7 (July), 604-612.
• 45: 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]

INDEX TERMS

Primary Classification:
  E. Data

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
  C.2 COMPUTER-COMMUNICATION NETWORKS

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Design, Performance

Keywords:
contention, counting networks, index distribution, lock free, wait free