Randomized sorting and selection on mesh-connected processor arrays (preliminary version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Randomized sorting and selection on mesh-connected processor arrays (preliminary version)

Full text

Pdf (1.09 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the third annual ACM symposium on Parallel algorithms and architectures table of contents

Hilton Head, South Carolina, United States

Pages: 17 - 28

Year of Publication: 1991

ISBN:0-89791-438-4

Authors

Christos Kaklamanis	Aiken Computation Laboratory, Harvard University, Cambridge, MA
Danny Krizanc	Dept. of Computer Science, University of Rochester, Rochester, NY
Lata Narayanan	Dept. of Computer Science, University of Rochester, Rochester, NY
Thanasis Tsantilas	Dept. of Computer Science, Columbia University, New York, NY

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 20, Citation Count: 8

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/113379.113381 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.

	Chl89	B. Chlebus, Sorting within distance bound on a mesh-connected processor array, Proceedings of the international symposium on Optimal algorithms, p.232-238, November 1989, Varna, Bulgaria
	Dal87	W. Dally. Wire-efficient VLSI multiprocessor communication networks. In Advanced Research in VLSI, pages 391- 415, 1987.
	Kun88	M. Kunde, Routing and sorting on mesh-connected arrays (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	Kun89	M. Kunde. 1-selection and related problems on grids of processors. Technical report, Institut fur Informatik, Technische Universitat, Munchen, 1989.
	LMT89	T. Leighton , F. Makedon , I. G. Tollis, A 2n-2 step algorithm for routing in an nxn array with constant size queues, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.328-335, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72970]
	Meg82	N. Megiddo. Parallel algorithms for finding the maximum and median almost surely in constant time. Technical report, Carnegie-Mellon University, 1982.
	Raj90	Sanguthevar Rajasekaran, Randomized parallel selection (extended abstract), Proceedings of the tenth conference on Foundations of software technology and theoretical computer science, p.215-224, November 1990, Bangalore, India
	Rei85	R. Reischuk. Probabilistic parallel algorithms for sorting and selection. SIAM Journal of Computing, 14(2):396-411, May 1985.
	RT91	D. Krizanc , S. Rajasekaran , T. Tsantilas, Optimal routing algorithms for mesh-connected processor arrays (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	RV87	John H. Reif , Leslie G. Valiant, A logarithmic time sort for linear size networks, Journal of the ACM (JACM), v.34 n.1, p.60-76, Jan. 1987 [doi>10.1145/7531.7532]
	SS86	C P Schnorr , A Shamir, An optimal sorting algorithm for mesh connected computers, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.255-263, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12156]
	TK77	C. D. Thompson , H. T. Kung, Sorting on a mesh-connected parallel computer, Communications of the ACM, v.20 n.4, p.263-271, April 1977 [doi>10.1145/359461.359481]
	Val75	L. Valiant. Parallelism in comparison problems. SIAM Journal of Computing, 4:348-355, 1975.

CITED BY 8

	William L. Hightower , Jan F. Prins , John H. Reif, Implementations of randomized sorting on large parallel machines, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.158-167, June 29-July 01, 1992, San Diego, California, United States
	Michael Kaufmann , Jop F. Sibeyn , Torsten Suel, Derandomizing algorithms for routing and sorting on meshes, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.669-679, January 23-25, 1994, Arlington, Virginia, United States
	Torsten Suel, Improved bounds for routing and sorting on multi-dimensional meshes, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.26-35, June 27-29, 1994, Cape May, New Jersey, United States
	Q. P. Gu , J. Gu, Algorithms and Average Time Bounds of Sorting on a Mesh-Connected Computer, IEEE Transactions on Parallel and Distributed Systems, v.5 n.3, p.308-315, March 1994
	Jop F. Sibeyn, Faster deterministic sorting through better sampling, Theoretical Computer Science, v.290 n.3, p.1829-1850, 3 January 2003
	Michael Kaufmann , Sanguthevar Rajasekaran , Jop F. Sibeyn, Matching the bisection bound for routing and sorting on the mesh, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.31-40, June 29-July 01, 1992, San Diego, California, United States
	Christos Kaklamanis , Danny Krizanc, Optimal sorting on mesh-connected processor arrays, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.50-59, June 29-July 01, 1992, San Diego, California, United States
	Hui Li , Kenneth C. Sevcik, Parallel sorting by over partitioning, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.46-56, June 27-29, 1994, Cape May, New Jersey, United States