An optimal sorting algorithm for mesh connected computers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An optimal sorting algorithm for mesh connected computers

Full text

Pdf (671 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 255 - 263

Year of Publication: 1986

ISBN:0-89791-193-8

Authors

C P Schnorr	Mathematics Dept and Computer Science Dept, University of Frankfurt, W. Germany
A Shamir	Applied Mathematics Dept, The Weizmann Institute, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 59, Citation Count: 29

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/12130.12156 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	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]
	2	Gianfranco Bilardi , Franco P. Preparata, A minimum area VLSI network for O(log n) time sorting, IEEE Transactions on Computers, v.34 n.4, p.336-343, April 1985 [doi>10.1109/TC.1985.5009384]
	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	Kumar and Hirschberg {1983}: "An Efficient Implementation of Batcher's Odd-Even Merge Algorithm and its Application in Parallel Sorting Schemes", IEEE Trans. Computers, Vol. C-32, pp. 254-264.
	5	Lang, Schimmler, Schmeck and Schroder {1985}: "Systolic Sorting on a Mesh-Connected Network", IEEE Trans. Computers, Vol. C-34, pp. 652-658.
	6	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]
	7	Nassimi and Sahni {1979}: "Bitonic Sort on a Mesh- Connected Parallel Computer", IEEE Trans. Computers, Vol. C-27, pp. 2-7.
	8	Scherson, Sen and Shamir {1985}: "Shear Sort: A True Two Dimensional Sorting Technique for VLSI Networks" ,Technical Report, Dept. of electrical and Computer Engineering, The University of California, Santa Barbara.
	9	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]

CITED BY 29

	Geeta Chaudhry , Thomas H. Cormen , Leonard F. Wisniewski, Columnsort lives! an efficient out-of-core sorting program, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.169-178, July 2001, Crete Island, Greece
	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
	Malika De , Debasish Das , Mabhin Ghosh , Bhabani P. Sinha, An Efficient Sorting Algorithm on the Multi-Mesh Network, IEEE Transactions on Computers, v.46 n.10, p.1132-1137, October 1997
	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
	Fillia Makedon , Adonios Simvonis, Many-to-one packet routing on the mesh, Proceedings of the 19th annual conference on Computer Science, p.280-288, April 1991, San Antonio, Texas, 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
	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
	Thomas M. Stricker, Supporting the hypercube programming model on mesh architectures: (a fast sorter for iWarp tori), Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.148-157, June 29-July 01, 1992, San Diego, California, United States
	James D. Fix , Richard E. Ladner, Optimal one-way sorting on a one-dimensional sub-bus array, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.586-594, January 22-24, 1995, San Francisco, California, United States
	Doug Ierardi, 2d-bubblesorting in average time O(√N lg N)*, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.36-45, 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
	Manfred Kunde, Balanced routing: towards the distance bound on grids, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.260-271, July 21-24, 1991, Hilton Head, South Carolina, United States
	Christos Kaklamanis , Giuseppe Persiano, Branch-and-bound and backtrack search on mesh-connected arrays of processors, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.118-126, June 29-July 01, 1992, San Diego, California, United States
	Alok Choudhary , Sanjay Ranka, Mesh and pyramid algorithms for iconic indexing, Proceedings of the 5th international conference on Supercomputing, p.295-303, June 17-21, 1991, Cologne, West Germany
	Hartmut Schmeck , Heiko Schröder , Christoph Starke, Systolic s/sup 2/-Way Merge Sort is Optimal, IEEE Transactions on Computers, v.38 n.7, p.1052-1056, July 1989
	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
	Ilan Newman , Assaf Schuster, Hot-Potato Algorithms for Permutation Routing, IEEE Transactions on Parallel and Distributed Systems, v.6 n.11, p.1168-1176, November 1995
	James D. Fix , Richard E. Ladner, Sorting by Parallel Insertion on a One-Dimensional Subbus Array, IEEE Transactions on Computers, v.47 n.11, p.1267-1281, November 1998
	Alan Roberts , Antonios Symvonis, A General Method for Deflection Worm Routing on Meshes Based on Packet Routing Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.8 n.8, p.781-789, August 1997
	P. F. Corbett , I. D. Scherson, Sorting in Mesh Connected Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.3 n.5, p.626-632, September 1992
	F. Makedon , A. Symvonis, An Efficient Heuristic for Permutation Packet Routing on Meshes with Low Buffer Requirements, IEEE Transactions on Parallel and Distributed Systems, v.4 n.3, p.270-276, March 1993
	Qian-Ping Gu , Jun Gu, Two Packet Routing Algorithms on a Mesh-Connected Computer, IEEE Transactions on Parallel and Distributed Systems, v.6 n.4, p.436-440, April 1995
	Antonio Fernández , Kemal Efe, Generalized Algorithm for Parallel Sorting on Product Networks, IEEE Transactions on Parallel and Distributed Systems, v.8 n.12, p.1211-1225, December 1997
	I. D. Scherson , S. Sen, Parallel Sorting in Two-Dimensional VLSI Models of Computation, IEEE Transactions on Computers, v.38 n.2, p.238-249, February 1989
	Madhusudan Nigam , Sartaj Sahni, Sorting n2 Numbers on n x n Meshes, IEEE Transactions on Parallel and Distributed Systems, v.6 n.12, p.1221-1225, December 1995
	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
	M. Kunde , T. Tensi, Multi-packet-routing on mesh connected arrays, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.336-343, June 18-21, 1989, Santa Fe, New Mexico, United States