Optimal sorting on mesh-connected processor arrays

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal sorting on mesh-connected processor arrays

Full text

Pdf (913 KB)

Source

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

San Diego, California, United States

Pages: 50 - 59

Year of Publication: 1992

ISBN:0-89791-483-X

Authors

Christos Kaklamanis
Danny Krizanc

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): 4, Downloads (12 Months): 20, Citation Count: 4

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

	AKS83	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]
	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
	Col86	t~. Cole. Parallel merge sort. In Symposium on the Foundations of Computer Science, pages 511-516, 1986.
	Dal87	W. Dally. Wire-efficient vlsi multiprocessot communication networks. In Advanced Research in VLSI, pages 391-415, 1987.
	KKNT91	Christos Kaklamanis , Danny Krizanc , Lata Narayanan , Thanasis Tsantilas, Randomized sorting and selection on mesh-connected processor arrays (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.17-28, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113381]
	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.
	Kun91	Manfred Kunde, Concentrated regular data streams on grids: sorting and routing near to the bisection bound, Proceedings of the 32nd annual symposium on Foundations of computer science, p.141-150, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185363]
	Lei85	Tom Leighton, Tight bounds on the complexity of parallel sorting, IEEE Transactions on Computers, v.34 n.4, p.344-354, April 1985 [doi>10.1109/TC.1985.5009385]
	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]
	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 Computzng, 4:348-355, 1975.

CITED BY 4

	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
	Sanguthevar Rajasekaran, Mesh Connected Computers with Fixed and Reconfigurable Buses: Packet Routing and Sorting, IEEE Transactions on Computers, v.45 n.5, p.529-539, May 1996
	Sanguthevar Rajasekaran , Sartaj Sahni, Randomized Routing, Selection, and Sorting on the OTIS-Mesh, IEEE Transactions on Parallel and Distributed Systems, v.9 n.9, p.833-840, September 1998