Small-depth counting networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Small-depth counting networks

Full text

Pdf (1.19 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fourth annual ACM symposium on Theory of computing table of contents

Victoria, British Columbia, Canada

Pages: 417 - 428

Year of Publication: 1992

ISBN:0-89791-511-9

Authors

Michael Klugerman	Mathematics Department, Massachusetts Institute of Technology, Cambridge, MA
C. Greg Plaxton	Department of Computer Science, University of Texas at Austin, Austin, TX

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 14, Citation Count: 25

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/129712.129752 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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
	2	M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
	3	N. Alon and J. H. Spencer. The Probabilistic Method. Wiley-Interseience, New York, NY, 1992.
	4	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]
	5	K. E. Butcher. Sorting networks and their applications. In Proceedings of the AFIPS Spring Joint Computer Conference, vol. 32, pages 307- 314, 1968.
	6	V. Chv#tal. Personal communication.
	7	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	8	M. Dowd, Y. Perl, M. Saks, and L. Rudolph. The balanced sorting network. Technical Report DCS-TR-127, Department of Computer Science, Rutgers University, June 1983.
	9	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]
	10	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
	11	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]
	12	M.R. Klugerman. Lecture 17: Counting networks. In F.T. Leighton, C.E. Leiserson, and N. Kahale, editors, Research Seminar Series 15: Advanced Parallel and VLSI Computation, pages 153-161. MIT Press, 1991.
	13	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	14	F. T. Leighton and C. G. Plaxton. A (fairly) simple circuit that (usually)sorts. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 264- 274, October 1990.
	15	C. G. Plaxton. A hypercubic sorting network with nearly logarithmic depth. May 1992.
	16	H.S. Stone. Database applications of the fetchand-add instruction. 1EEE Transactions on Computers, C-33:604-612, 1984.

CITED BY 25

	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
	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
	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
	Nir Shavit , Asaph Zemach, Diffracting trees, ACM Transactions on Computer Systems (TOCS), v.14 n.4, p.385-428, Nov. 1996
	Marios Mavronicolas , Michael Merritt , Gadi Taubenfeld, Sequentially consistent versus linearizable counting networks, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.133-142, May 04-06, 1999, Atlanta, Georgia, United States
	Bhaskar Ghosh , F. T. Leighton , Bruce M. Maggs , S. Muthukrishnan , C. Greg Plaxton , R. Rajaraman , Andréa W. Richa , Robert E. Tarjan , David Zuckerman, Tight analyses of two local load balancing algorithms, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.548-558, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Leonidas Hadjimitsis , Marios Mavronicolas, Contention in balancing networks resolved (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.41-50, June 28-July 02, 1998, Puerto Vallarta, Mexico
	William Aiello , Baruch Awerbuch , Bruce Maggs , Satish Rao, Approximate load balancing on dynamic and asynchronous networks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.632-641, May 16-18, 1993, San Diego, California, United States
	Shlomo Moran , Gadi Taubenfeld, A lower bound on wait-free counting, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.251-259, August 15-18, 1993, Ithaca, New York, United States
	Costas Busch , Marios Mavronicolas, A combinatorial treatment of balancing networks, Journal of the ACM (JACM), v.43 n.5, p.794-839, Sept. 1996
	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
	Hagit Brit , Shlomo Moran, Wait-freedom vs. bounded wait-freedom in public data structures (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.52-60, August 14-17, 1994, Los Angeles, California, United States
	James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks, Journal of the ACM (JACM), v.41 n.5, p.1020-1048, Sept. 1994
	Nancy Lynch , Nir Shavit , Alex Shvartsman , Dan Touitou, Counting networks are practically linearizable, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.280-289, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	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
	Hagit Brit , Shlomo Moran , Gadi Taubenfeld, Public data structures: counters as a special case, Theoretical Computer Science, v.289 n.1, p.401-423, 23 October 2002
	Cynthia Dwork , Maurice Herlihy , Orli Waarts, Contention in shared memory algorithms, Journal of the ACM (JACM), v.44 n.6, p.779-805, Nov. 1997
	Hagit Attiya , Maurice Herlihy , Ophir Rachman, Atomic snapshots using lattice agreement, Distributed Computing, v.8 n.3, p.121-132, March 1995
	Panagiota Fatourou , Maurice Herlihy, Read-modify-write networks, Distributed Computing, v.17 n.1, p.33-46, February 2004
	Eran Aharonson , Hagit Attiya, Counting networks with arbitrary fan-out, Distributed Computing, v.8 n.4, p.163-169, June 1995
	Maurice Herlihy , Nir Shavit , Orli Waarts, Linearizable counting networks, Distributed Computing, v.9 n.4, p.193-203, February 1996
	Maurice Herlihy , Srikanta Tirthapura, Randomized smoothing networks, Journal of Parallel and Distributed Computing, v.66 n.5, p.626-632, May 2006
	Marios Mavronicolas , Thomas Sauerwald, The impact of randomization in smoothing networks, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Tobias Friedrich , Thomas Sauerwald, Near-perfect load balancing by randomized rounding, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Marios Mavronicolas , Thomas Sauerwald, A randomized, o(log w)-depth 2 smoothing network, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Sorting and searching

Additional Classification:
B. Hardware
B.6 LOGIC DESIGN
B.6.1 Design Styles
Subjects: Combinational logic

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

General Terms:
Theory

REVIEW

"James Aspnes : Reviewer"

Counting networks are asynchronous relatives of sorting networks. A counting network divides a set of tokens that enter asynchronously on its input wires as evenly as possible among its output wires, with any excess tokens distributed among more...

Collaborative Colleagues:

Michael Klugerman: colleagues

C. Greg Plaxton: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player