Bounds to Complexities of Networks for Sorting and for Switching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Bounds to Complexities of Networks for Sorting and for Switching

Full text

Pdf (489 KB)

Source

Journal of the ACM (JACM) archive
Volume 22 , Issue 2 (April 1975) table of contents

Pages: 195 - 201

Year of Publication: 1975

ISSN:0004-5411

Authors

David E. Muller	Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL
Franco P. Preparata	Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 38, Citation Count: 32

Additional Information:

references cited by index terms 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/321879.321882 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	LEVY, S Y , AND PAVLL, M C. An algebra with applicatmn to sorting algorithms. Proc. Third Princeton Conference on Information Sciences and Systems, Pnnceton U, Princeton, N J, March 1969, pp. 286-291
	2	BATCHER, K. E Sorting networks and their applications. Proc. AFIPS 1968 SJCC, Vol. 32, AFIPS Press, Montvale, N J, pp. 307-313
	3	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
	4	GREEN, M W Some improvements in nonadaptive sorting algorithms Proc Sixth Princeton Conference on Information Sciences and Systems, March 1972, pp 387-391.
	5	:FOSTER, C. C, AND STOCKTON, :F. D Counting responders in an associative memory 1EEE Trans Comput C-ZO, 12 (Dec. 1971), 1580--1583.
	6	MEYER, A R, FISCHER, M. J, AND VILFAN, B The length of formula representations of Boolean functions. Dep Elec Eng., M I T, Cambridge, Mass, 1971 (unpublished manuscript)

CITED BY 32

	Hussein M. Alnuweiri, Optimal bounded-degree VLSI networks for sorting in a constant number of rounds, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.732-739, November 18-22, 1991, Albuquerque, New Mexico, United States
	Prithviraj Banerjee , Jacob A. Abraham, Fault-secure algorithms for multiple-processor systems, ACM SIGARCH Computer Architecture News, v.12 n.3, p.279-287, June 1984
	Leslie Ann Goldberg , Mark Jerrum , Tom Leighton , Satish Rao, A doubly logarithmic communication algorithm for the completely connected optical communication parallel computer, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.300-309, June 30-July 02, 1993, Velen, Germany
	Mohammad Meybodi , Kenneth Williams, Parallel processors applied to string transformations (abstract), Proceedings of the 1986 ACM fourteenth annual conference on Computer science, p.441, February 1986, Cincinnati, Ohio, United States
	Nicholas Pippenger, The realization of monotone Boolean functions (Preliminary Version), Proceedings of the eighth annual ACM symposium on Theory of computing, p.204-210, May 03-05, 1976, Hershey, Pennsylvania, United States
	Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981
	Dina Bitton , David J. DeWitt , David K. Hsaio , Jaishankar Menon, A taxonomy of parallel sorting, ACM Computing Surveys (CSUR), v.16 n.3, p.287-318, Sept. 1984
	David Nassimi , Sartaj Sahni, Parallel permutation and sorting algorithms and a new generalized connection network, Journal of the ACM (JACM), v.29 n.3, p.642-667, July 1982
	J. Cheung , S. Dhall , S. Lakshmivarahan , L. Miller , B. Walker, A new class of two stage parallel sorting schemes, Proceedings of the ACM '82 conference, p.26-29, January 1982
	D. S. Hirschberg, Fast parallel sorting algorithms, Communications of the ACM, v.21 n.8, p.657-661, Aug. 1978
	Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980
	Adam R. Klivans , Rocco A. Servedio, Boosting and Hard-Core Set Construction, Machine Learning, v.51 n.3, p.217-238, June 2003
	R. S. Francis , I. D. Mathieson, A Benchmark Parallel Sort for Shared Memory Multiprocessors, IEEE Transactions on Computers, v.37 n.12, p.1619-1626, December 1988
	Leslie Ann Goldberg , Yossi Matias , Satish Rao, An optical simulation of shared memory, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.257-267, June 27-29, 1994, Cape May, New Jersey, United States
	A Aggarwal, Tradeoffs for VLSI models with subpolynomial delay, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.59-68, May 06-08, 1985, Providence, Rhode Island, United States
	Herman Lam , Chiang Lee , Stanley Y. W. Su, A Special Function Unit for Database Operations (SFU-DB): Design and Performance Evaluation, IEEE Transactions on Computers, v.40 n.3, p.263-275, March 1991
	Kai-Yeung Siu , Vwani P. Roychowdhury , Thomas Kailath, Depth-Size Tradeoffs for Neural Computation, IEEE Transactions on Computers, v.40 n.12, p.1402-1412, December 1991
	Hussein M. Alnuweiri, A New Class of Optimal Bounded-Degree VLSI Sorting Networks, IEEE Transactions on Computers, v.42 n.6, p.746-752, June 1993
	Lisa Hellerstein , Vijay Raghavan, Exact learning of DNF formulas using DNF hypotheses, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	M. V. Chien , A. Yavuz Oruc, Adaptive Binary Sorting Schemes and Associated Interconnection Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.6, p.561-572, June 1994
	Prasanta K. Jana, Multi-mesh of trees with its parallel algorithms, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.4, p.193-206, March 2004
	Paul E. Dunne , Michael Wooldridge , Michael Laurence, The complexity of contract negotiation, Artificial Intelligence, v.164 n.1-2, p.23-46, May 2005
	Lisa Hellerstein , Vijay Raghavan, Exact learning of DNF formulas using DNF hypotheses, Journal of Computer and System Sciences, v.70 n.4, p.435-470, June 2005
	Koji Nakano , Etsuko Takamichi, An image retrieval system using FPGAs, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	M. R. Samatham , D. K. Pradhan, The de Bruijn Multiprocessor Network: A Versatile Parallel Processing and Sorting Network for VLSI, IEEE Transactions on Computers, v.38 n.4, p.567-581, April 1989
	G. Bilardi , F. P. Preparata, A minimum area VLSI network for O(logn) time sorting, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.64-70, December 1984
	M. R. Samatham , D. K. Pradhan, The de Bruijn multiprocessor network: a versatile sorting network, ACM SIGARCH Computer Architecture News, v.13 n.3, p.360-367, June 1985
	Jai Menon, A Study of Sort Algorithms for Multiprocessor Database Machines, Proceedings of the 12th International Conference on Very Large Data Bases, p.197-206, August 25-28, 1986
	Yuzuru Tanaka, Bit-Sliced VLSI Algorithm for Search and Sort, Proceedings of the 10th International Conference on Very Large Data Bases, p.225-234, August 27-31, 1984
	Tsong-Chih Hsu , Sheng-De Wang, A simple architecture for constant time sorting machines, ACM SIGARCH Computer Architecture News, v.23 n.1, p.13-19, March 1995
	Masumeh Damroudi , Mohammad R. Salehnamadi , Kamal Jadidy Aval, ROE sorting on ILLIAC array processor, Proceedings of the WSEAS International Conference on Applied Computing Conference, p.326-330, May 27-30, 2008, Istanbul, Turkey
	Benjamin W. Wah , Y. W. Ma, The architecture of MANIP: a parallel computer system for solving NP-complete problems, Proceedings of the May 4-7, 1981, national computer conference, May 04-07, 1981, Chicago, Illinois