Implementations of randomized sorting on large parallel machines

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Implementations of randomized sorting on large parallel machines

Full text

Pdf (881 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: 158 - 167

Year of Publication: 1992

ISBN:0-89791-483-X

Authors

William L. Hightower
Jan F. Prins
John H. Reif

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): 1, Downloads (12 Months): 28, 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.140918 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.

	AH88	A. Aggarwal , M.D. A. Huang, Network complexity of sorting and graph problems and simulating CRCW PRAMS by interconnection networks (preliminary version), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	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]
	AV79	D. Angluin and L.G. Valiant, Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings, Journal of Computer and System Sciences, 18(2):155-193, April 1979.
	AKl85	Selim G. Akl, Parallel Sorting Algorithms, Academic Press, Inc., Orlando, FL, 1990
	BAT68	K. Batcher; Sorting Networks and Their Applications, Proceedings of the AFIPS Spring Joint Computing Conference, vol. 32, pp.307- 314, 1968.
	BS78	G. Baudet and D. Stevenson, Optimal Sorting Algorithms for Parallel Computers, IEEE Transactions on Computers, C-27:84-87, 1978.
	BLE90	Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
	BLM+91	Guy E. Blelloch , Charles E. Leiserson , Bruce M. Maggs , C. Greg Plaxton , Stephen J. Smith , Marco Zagha, A comparison of sorting algorithms for the connection machine CM-2, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.3-16, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113380]
	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
	COLE88	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	CV86	R Cole , U Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.206-219, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12151]
	CLR90	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	CP90	R. Cypher , C. G. Plaxton, Deterministic sorting in nearly logarithmic time on the hypercube and related computers, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.193-203, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100240]
	DNS91	D.J. DeWitt, J.F. Naughton, D.F. Schneider, Parallel Sorting on a Shared-Nothing Architecture using Probabilistic Splitting, Computer Sciences TR#1043, University of Wisconsin - Madison, 1991.
	FKO86	E. Felten, S. Karlin, and S. Otto, Sorting on a Hypercube, Hm 244, Caltech/JPL, 1986.
	FM70	W. D. Frazer , A. C. McKellar, Samplesort: A Sampling Approach to Minimal Storage Tree Sorting, Journal of the ACM (JACM), v.17 n.3, p.496-507, July 1970 [doi>10.1145/321592.321600]
	HOE56	W. Hoeffding, On the Distribution of the Number of Successes in Independent Trials, Annals of Mathematical Statistics, 27:713-721, 1956.
	HC83	J.S. Huang and Y.C. Chow, Parallel Sorting and Data Partitioning by Sampling, Proceedings of the IEEE Computer Society's Seventh International Computer Software and Applications Conference, pp. 627-631, November 1983.
	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]
	KUN88a	M. Kunde, Routing and sorting on mesh-connected arrays (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	KUN88b	M. Kunde, 1-selection and Related Problems on Grids of Processors, Aegan Workshop on Computing: VLSI Algorithms and Architectures, vol. 319 of Lecture Notes in Computer Science, pp. 423-433, Springer- Verlag, NY, 1988.
	LEI865	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]
	LP90	T. Leighton and G. Plaxton, A (Fairly) Simple Circuit That (Usually) Sorts, Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pp. 264-274, October 1990.
	NS82	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 [doi>10.1145/322326.322329]
	PAT90	M.S. Paterson, Improved Sorting Networks with O(log n) Depth, Algorithmica, 5::75-92, 1990.
	PLAX89	C.G. Plaxton, Efficient Computation on Sparse Interconnection Networks, Technical Report STAN-CS-89-1283, Stanford University, Department of Computer Science, September 1989.
	PRIN90	J.F. Prins, Efficient Bitonic Sorting of Large Arrays on the MasPar MP-1, 3rd Symposium on Frontiers of Massively Parallel Processing, 1990; expanded version Technical Report 91- 041, Univ. of North Carolina, 1991.
	QUI89	M. J. Quinn, Analysis and benchmarking of two parallel sorting algorithms: hyperquicksort and quickmerge, BIT, v.29 n.2, p.239-250, 1989 [doi>10.1007/BF01952679]
	RR89	S. Rajasekaran , J. H. Reif, Optimal and sublogarithmic time randomized parallel sorting algorithms, SIAM Journal on Computing, v.18 n.3, p.594-607, June 1989 [doi>10.1137/0218041]
	RV83,87	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]
	REI85	R. Reischuk, Probabilistic Parallel Algorithms for Sorting and Selection, SlAM Journal of Computing, 14(2):396-411, May 1985.
	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]
	SG88	S. R. Seidel , W. L. George, Binsorting on hypercubes with d-port communication, Proceedings of the third conference on Hypercube concurrent computers and applications, p.1455-1461, January 1989, Pasadena, California, United States [doi>10.1145/63047.63102]
	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]
	U83	Jeffrey D Ullma, Computational Aspects of VLSI, W. H. Freeman & Co., New York, NY, 1984
	VD88	P. Varman and K. Doshi, Sorting with Linear Speedup on a Pipelined Hypercube, Technical Report TR-9902, Rice University, Department of Electrical and Computer Engineering, February 1988.
	WAG89	B.A. Wagar, Hyperquicksort: A Fast Sorting Algorithm for Hypercubes, Hypercube Multiprocessors 1987 (Proceedings of the Second Conference on Hypercube Multiprocessors) (ed. M.T. Heath), pp. 292- 299, Philadelphia, PA, 1987. SIAM.
	WAG90	Bruce Alan Wagar, Practical sorting algorithms for hypercube computers, University of Michigan, Ann Arbor, MI, 1991
	WS88	Y. Won and S. Sahni, A Balanced Bin Sort for Hypercube Multicomputers. Journal of Supercomputing, 2:435-448, 1988.

CITED BY 4

	Michael T. Goodrich, Communication-efficient parallel sorting (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.247-256, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Ben H. H. Juurlink , Harry A. G. Wijshoff, A quantitative comparison of parallel computation models, ACM Transactions on Computer Systems (TOCS), v.16 n.3, p.271-318, Aug. 1998
	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
	Jop F. Sibeyn, Faster deterministic sorting through better sampling, Theoretical Computer Science, v.290 n.3, p.1829-1850, 3 January 2003