Communication-efficient parallel sorting (preliminary version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Communication-efficient parallel sorting (preliminary version)

Full text

Pdf (1.11 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing table of contents

Philadelphia, Pennsylvania, United States

Pages: 247 - 256

Year of Publication: 1996

ISBN:0-89791-785-5

Author

Michael T. Goodrich

Johns Hopkins University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 34, Citation Count: 9

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/237814.237870 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	Micah Adler , John W. Byers , Richard M. Karp, Parallel sorting with limited bandwidth, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.129-136, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215431]
	2	Alok Aggarwal , Ashok K. Chandra , Marc Snir, Communication complexity of PRAMs, Theoretical Computer Science, v.71 n.1, p.3-28, 13 March 1990 [doi>10.1016/0304-3975(90)90188-N]
	3	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]
	4	Selim G. Akl, Parallel Sorting Algorithms, Academic Press, Inc., Orlando, FL, 1990
	5	K. E. Batcher. Sorting networks and their applications. Proc. 1968 Spring Joint Compul;er Conf., 307-314, Reston, VA, 1968.
	6	Gianfranco Bilardi , Franco P. Preparata, Lower Bounds to Processor-Time Tradeoffs under Bounded-Speed Message Propagation, Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.1-12, August 16-18, 1995
	7	Dina Bitton , David J. DeWitt , David K. Hsaio , Jaishankar Menon, A taxonomy of parallel sorting, ACM Computing Surveys (CSUR), v.16 n.3, p.287-318, Sept. 1984 [doi>10.1145/2514.2516]
	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	V. Chv~tal. Lecture notes on the new AKS sorting network. Report DCS-TR-294, Rutgers Univ., 1992.
	10	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	11	Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
	12	David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
	13	Robert Cypher , Jorge L. C. Sanz, Cubesort: A parallel algorithm for sorting N data items with S-sorters, Journal of Algorithms, v.13 n.2, p.211-234, June, 1992 [doi>10.1016/0196-6774(92)90016-6]
	14	Robert Cypher , C. Greg Plaxton, Deterministic sorting in nearly logarithmic time on the hypercube and related computers, Journal of Computer and System Sciences, v.47 n.3, p.501-548, Dec. 1993 [doi>10.1016/0022-0000(93)90043-V]
	15	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 [doi>10.1145/215399.215410]
	16	Frank Dehne , Andreas Fabri , Andrew Rau-Chaplin, Scalable parallel geometric algorithms for coarse grained multicomputers, Proceedings of the ninth annual symposium on Computational geometry, p.298-307, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161154]
	17	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]
	18	Alexandros V. Gerbessiotis , Leslie G. Valiant, Direct bulk-synchronous parallel algorithms, Journal of Parallel and Distributed Computing, v.22 n.2, p.251-267, Aug. 1994 [doi>10.1006/jpdc.1994.1085]
	19	P. B. Gibbons, A more practical PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.158-168, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72953]
	20	Michael T. Goodrich , S. Rao Kosaraju, Sorting on a parallel pointer machine with applications to set expression evaluation, Journal of the ACM (JACM), v.43 n.2, p.331-361, March 1996 [doi>10.1145/226643.226670]
	21	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]
	22	Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
	23	Richard M. Karp , Michael Luby , Friedhelm Meyer auf der Heide, Efficient PRAM simulation on a distributed memory machine, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.318-326, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129743]
	24	Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	25	Richard M. Karp , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser, Optimal broadcast and summation in the LogP model, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.142-153, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165250]
	26	Clyde P. Kruskal , Larry Rudolph , Marc Snir, A complexity theory of efficient parallel algorithms, Theoretical Computer Science, v.71 n.1, p.95-132, 13 March 1990 [doi>10.1016/0304-3975(90)90192-K]
	27	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]
	28	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	29	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 [doi>10.1145/181014.192329]
	30	Yishay Mansour , Noam Nisan , Uzi Vishkin, Trade-offs between communication throughput and parallel time, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.372-381, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195199]
	31	Kurt Mehlhorn , Uzi Vishkin, Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories, Acta Informatica, v.21 n.4, p.339-374, Nov. 1984
	32	J. M. Nash, P. M. Dew, M. E. Dyer, and J. R. Davy. Parallel algorithm design on the WPRAM model. Report 94.24, School of Comp. Sci., Univ. of Leeds, 1994.
	33	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]
	34	Christos Papadimitriou , Mihalis Yannakakis, Towards an architecture-independent analysis of parallel algorithms, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.510-513, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62262]
	35	M. Paterson. Improved sorting networks with o(logn) depth. Algorithmica, 5(1):75-92, 1990.
	36	Charles Gregory Plaxton , Ernst W. Mayr, Efficient computation on sparse interconnection networks, 1989
	37	John H. Reif, Synthesis of Parallel Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
	38	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]
	39	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]
	40	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
	41	L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991

CITED BY 9

	Chun-Hsi Huang, Grid-enabled parallel divide-and-conquer: theory and practice, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain
	Philip D. MacKenzie , Vijaya Ramachandran, Computational bounds for fundamental problems on general-purpose parallel models, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.152-163, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Chun-Hsi Huang , Xin He, Finding a Hamiltonian paths in tournaments on clusters - a provably communication-efficient approach, Proceedings of the 2001 ACM symposium on Applied computing, p.549-553, March 2001, Las Vegas, Nevada, United States
	Micah Adler , Wolfgang Dittrich , Ben Juurlink , Mirosław Kutyłowski , Ingo Rieping, Communication-optimal parallel minimum spanning tree algorithms (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.27-36, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Micah Adler , Tom Leighton, Compression using efficient multicasting, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.153-162, May 21-23, 2000, Portland, Oregon, United States
	Gianfranco Bilardi , Kieran Herley , Andrea Pietracaprina , Geppino Pucci, On stalling in LogP, Journal of Parallel and Distributed Computing, v.65 n.3, p.307-312, March 2005
	Vijaya Ramachandran , Brian Grayson , Michael Dahlin, Emulations between QSM, BSP and LogP: a framework for general-purpose parallel algorithm design, Journal of Parallel and Distributed Computing, v.63 n.12, p.1175-1192, December 2003
	Albert Chan , Frank Dehne , Prosenjit Bose , Markus Latzel, Coarse grained parallel algorithms for graph matching, Parallel Computing, v.34 n.1, p.47-62, January, 2008
	Edscott Wilson García , Guillermo Morales-Luna, Simulation for bulk synchronous parallel superstep task assignment in desktop grids characterised by gaussian parameter distributions, Multiagent and Grid Systems, v.4 n.2, p.141-166, April 2008