Counting networks

ABSTRACT

Many fundamental multi-processor coordination problems can be expressed as counting problems: Processes must cooperate to assign successive values from a given range, such as addresses in memory or destinations on an interconnection network. Conventional solutions to these problems perform poorly because of synchronization bottlenecks and high memory contention.Motivated by observations on the behavior of sorting networks, we offer a new approach to solving such problems, by introducing counting networks, a new class of networks that can be used to count. We give two counting network constructions, one of depth log n(1 + log n)/2 using n log (1 + log n)/4 “gates,” and a second of depth log2 n using n log2 n/2 gates. These networks avoid the sequential bottlenecks inherent to earlier solutions and substantially lower the memory contention.Finally, to show that counting networks are not merely mathematical creatures, we provide experimental evidence that they outperform conventional synchronization techniques under a variety of circumstances.

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: 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
• 4: M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
• 5: ~ANDERSON, T.E. 1989. The performance implications of spin-waiting alternatives for shared- ~memory multiprocessors. Tech. Rep. 89-04-03. Univ. Washington, Seattle, Wash.
• 6: 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]
• 7: ~BATCttER, K.E. 1968. Sorting networks and their applications. In Proceedings of AF1PS Joint ~Computer Conference 32, 338-334.
• 8: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 9: Martin Dowd , Yehoshua Perl , Larry Rudolph , Michael Saks, The periodic balanced sorting network, Journal of the ACM (JACM), v.36 n.4, p.738-757, Oct. 1989 [doi>10.1145/76359.76362]
• 10: Carla Schlatter Ellis , Thomas J. Olson, Algorithms for parallel memory allocation, International Journal of Parallel Programming, v.17 n.4, p.303-345, Aug. 1988 [doi>10.1007/BF01407909]
• 11: ~FELq'ON, E. W., L^MARC^, A., AND LADNER, R. 1993. Building counting networks from larger ~balancers. Tech. Rep. 93-(/4-09. Univ. Washington, Seattle, Wash.
• 12: 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
• 13: ~GAWHCK, D. 1985. Processing "hot spots" in high performance systems. In Proceedings of ~COMPCON'~S5. IEEE, Los Alamitos, Cahf., pp. 249-251.
• 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: ~GOTTLIEB, A., GRISHMAN, R., KRUSK^L, C. P., MCAULIFFE, K. P., RUDOLPH, L., AND SNIR, M. ~1984. The NYU ultracomputer Dcsignmg an mimd parallel computer. IEEE Trans. Conlpttt- ~ers C-32, 2 (Fcb.), 175-189.
• 16: 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]
• 17: ~HARDAVEI,LAS, N., KARAKOS, D., AND MAYRONICOL^S, M. 1993. Notes on sorting and counting ~nctworks. In Proceedings of WDAG'93, to appear.
• 18: 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]
• 19: 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]
• 20: 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]
• 21: D. A. Kranz , R. H. Halstead, Jr. , E. Mohr, Mul-T: a high-performance parallel Lisp, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.81-90, June 19-23, 1989, Portland, Oregon, United States
• 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: 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]
• 24: 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]
• 25: J. M. Mellor-Crummey , M. L. Scott, Algorithms for Scalable Synchronization on Shared-Memory Multiproceessors, University of Rochester, Rochester, NY, 1990
• 26: 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
• 27: John M. Mellor-Crummey , Michael L. Scott, Synchronization without contention, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.269-278, April 08-11, 1991, Santa Clara, California, United States
• 28: ~PELEG, D., AND UPFAL, E. 1986. The token distribution problem. In Proeeedmgs of the 27th ~IEEE Sympostum on Foundaaons of Computer Sctence (Oct.). IEEE, New York.
• 29: ~PF1STER, G. H., ET AL. 1985. The IBM research parallel processor prototype (RP3): Introduc-tion and architecture. In Proceedings of the International Conference on Parallel Processing.
• 30: ~PFIS'rER, G. H., AND NORTON, A. 1985. 'Hot spot' contention and combining m multistage ~mterconnectlon networks. IEEE ;trans. Comput. C-34, 11 (Nov.), 933 938.
• 31: ~STONE, H. S. 1984. Database applications of the fetch-and-add instruction. IEEE Trans ~Comput. C-33, 7 (July), 604-612.
• 32: Uzi Vishkin, A parallel-design distributed-implementation (PDDI) general-purpose computer, Theoretical Computer Science, v.32 n.1-2, p.157-172, July 1984 [doi>10.1016/0304-3975(84)90028-8]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks; Network topology
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Performance

Keywords:
counting networks, hot-sports, network routing, parallel processing