Parallel sorting by over partitioning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel sorting by over partitioning

Full text

Pdf (1.05 MB)

Source

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

Cape May, New Jersey, United States

Pages: 46 - 56

Year of Publication: 1994

ISBN:0-89791-671-9

Authors

Hui Li	Department of Computer Science, University of Toronto
Kenneth C. Sevcik	Department of Computer Science, University of Toronto

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
European Comp Soc : European Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 71, 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/181014.192329 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	A. Agarwal, D. Chaiken, K. Johnson, D. Kranz, J. Kubiatowicz, K. Kurihara, B.-H. Lira, G. Maa, and D. Nussbaum. The MIT Alewife Machine: A Large- Scale Distributed-Memory Multiprocessor. In Scalable Shared Memory Architectures. Kluwer Academic Pubfishers, 1991.
	2	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]
	3	Selim G. Akl, Parallel Sorting Algorithms, Academic Press, Inc., Orlando, FL, 1990
	4	Davd H. Bailey , Eric Barzcz , Leonardo Dagum , Horst D. Simon, NAS Parallel Benchmark Results, IEEE Parallel & Distributed Technology: Systems & Technology, v.1 n.1, p.43-51, February 1993 [doi>10.1109/88.219861]
	5	K. Batcher. Sorting networks and their applications. In Proc. of the AFIPS Spring Joint Computer Conference, volume 32, pages 307-314, 1968.
	6	D. T. Blackston and A. Ranade. Snakesort: A family of simple optimal randomized sorting algorithms. In Proc. of 22nd International Conference on Parallel Processing, pages III-201-III-204, August 1993.
	7	Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
	8	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]
	9	A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
	10	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	11	E. Felten, S. Karlin, and S. Otto. Sorting on a hypercube. Technical report, Hm 244, Caltech/JPL, 1986.
	12	Geoffrey C. Fox , Mark A. Johnson , Gregory A. Lyzenga , Steve W. Otto , John K. Salmon , David W. Walker, Solving problems on concurrent processors. Vol. 1: General techniques and regular problems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	13	R. S. Francis and L. J. H. Pannan. A parallel partition for enhanced parallel quicksort. Parallel Computing, 18:543-550, 1992.
	14	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 [doi>10.1145/140901.140918]
	15	J. S. Huang and Y. C. Chow. Parallel sorting and data partitioning by sampling. In Proe. of the IEEE Computer Society's 7th International Computer Software and Applications Conference, pages 627-631, 1983.
	16	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]
	17	L. V. Kal# and S. Krishnan. A comparison based parallel sorting algorithm. In Proc. of 22nd International Conference on Parallel Processing, pages Iii-196-III- 200, August 1993.
	18	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]
	19	Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Wolf-Dietrich Weber , Anoop Gupta , John Hennessy , Mark Horowitz , Monica S. Lam, The Stanford Dash Multiprocessor, Computer, v.25 n.3, p.63-79, March 1992 [doi>10.1109/2.121510]
	20	H. Li and K. C. Sevcik. Parallel sorting by overpartitioning. Technical Report 295, University of Toronto, CSRI. February, 1994.
	21	P. P. Li and Y.-W. Tung. Parallel sorting on Symult 2010. in Proc. of 5th Distributed Memory Computing Conference, pages 224-229, Charleston, SC., April 1990.
	22	Xiaobo Li , Paul Lu , Jonathan Schaeffer , John Shillington , Pok Sze Wong , Hanmao Shi, On the versatility of parallel sorting by regular sampling, Parallel Computing, v.19 n.10, p.1079-1103, Oct. 1993 [doi>10.1016/0167-8191(93)90019-H]
	23	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]
	24	Mark H. Nodine , Jeffrey Scott Vitter, Deterministic distribution sort in shared and distributed memory multiprocessors, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.120-129, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165247]
	25	C. G. Plaxton. Efficient computation on sparse interconnection networks. Technical Report STAN-CS- 89-1283, Stanford University, Department of Computer Scienece, Stanford, CA, September 1989.
	26	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]
	27	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]
	28	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]
	29	Kendall Squre Research. KSR1 Principles of Operation. Waltham, MA, 1991.
	30	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]
	31	Hanmao Shi , Jonathan Schaeffer, Parallel sorting by regular sampling, Journal of Parallel and Distributed Computing, v.14 n.4, p.361-372, April 1992 [doi>10.1016/0743-7315(92)90075-X]
	32	K. Thearling , S. Smith, An improved supercomputer sorting benchmark, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.14-19, November 16-20, 1992, Minneapolis, Minnesota, United States
	33	A. Tridgell and R. P. Brent. An implementation of a general-purpose parallel sorting algorithm. Technical Report TR-CS-93-01, Computer Scienece laboratory, Australian National University, Australia, February 1993.
	34	Zvonko G. Vranesic , Michael Stumm , David M. Lewis , Ron White, Hector: A Hierarchically Structured Shared-Memory Multiprocessor, Computer, v.24 n.1, p.72-79, January 1991 [doi>10.1109/2.67196]
	35	Bruce Alan Wagar, Practical sorting algorithms for hypercube computers, University of Michigan, Ann Arbor, MI, 1991
	36	Y. Won and S. Sahni. A balanced bin sort for hypercube multicomputers. Journal of Supercomputing, 2:435-448, 1988.

CITED BY 4

	Frank Dehne , Xiaotie Deng , Patrick Dymond , Andreas Fabri , Ashfaq A. Khokhar, A randomized parallel 3D convex hull algorithm for coarse grained multicomputers, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.27-33, June 24-26, 1995, Santa Barbara, California, United States
	Anthony LaMarca , Richard E. Ladner, The influence of caches on the performance of sorting, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.370-379, January 05-07, 1997, New Orleans, Louisiana, United States
	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
	Christophe Cerin , Olivier Cozette , Gil Utard , Hazem Fkaier , Mohamed Jemni, Parallel out-of-core sorting and fast accesses to disks, International Journal of High Performance Computing and Networking, v.3 n.2/3, p.188-202, November 2005