A comparison of sorting algorithms for the connection machine CM-2

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A comparison of sorting algorithms for the connection machine CM-2

Full text

Pdf (1.68 MB)

Source

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

Hilton Head, South Carolina, United States

Pages: 3 - 16

Year of Publication: 1991

ISBN:0-89791-438-4

Authors

Guy E. Blelloch	Carnegie Mellon University, Pittsburgh, PA
Charles E. Leiserson	MIT, Cambridge, MA
Bruce M. Maggs	NEC Research Institute, Princeton, NJ
C. Greg Plaxton	University of Texas Austin, TX
Stephen J. Smith	Thinking Machines Corp. Cambridge, MA
Marco Zagha	Carnegie Mellon University, Pittsburgh, PA

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): 14, Downloads (12 Months): 83, Citation Count: 55

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/113379.113380 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. 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
	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	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.
	5	K. Batcher. Sorting networks and their applications. In Proceedings of the AFIPS Spring Joint Computing Conference, volume 32, pages 307-314, 1968.
	6	G. Baudet and D. Stevenson. Optimal sorting algorithms for parallel computers. IEEE Transactions on Computers, C- 27:84-87, 1978.
	7	Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
	8	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	9	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]
	10	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	11	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]
	12	E. Felten, S. Karlin, and S. Otto. Sorting on a hypercube. Hm 244, Caltech/JPL, 1986.
	13	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]
	14	W. Hoeffding. On the distribution of the number of successes in independent trials. Annals of Mathematical Statistics, 27:713--721, 1956.
	15	J. S. Huang and Y. C. Chow. Parallel sorting and data partitioning by sampling. In Proceedings of the IEEE Computer Society's Seventh International Computer Software and Applications Conference, pages 627-631, November 1983.
	16	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]
	17	T. Leighton and G. Plaxton. A (fairly) simple circuit that (usually) sorts. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 264-274, October 1990.
	18	P. P. Li. Parallel sorting on Ametek/S14. Technical report, Ametek Computer Research Division, Arcadia, CA, September 1986.
	19	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]
	20	M. S. Paterson. Improved sorting networks with O(log n) depth. Algorithmica, 5:75-92, 1990.
	21	C. G. Plaxton. Efficient computation on sparse interconnection networks. Technical Report STAN-CS-89-1283, Stanford University, Department of Computer Science, September 1989.
	22	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]
	23	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]
	24	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]
	25	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]
	26	P. Varman and K. Doshi. Sorting with linear speedup on a pipelined hypercube. Technical Report TR-8802, Rice University, Department of Electrical and Computer Engineering, February 1988.
	27	B. A. Wagar. Hyperquicksort: A fast sorting algorithm for hypercubes. In M. T. Heath, editor, Hypercube Multiprocessors 1987 (Proceedings of the Second Conference on tlypercube Multiprocessors), pages 292-299, Philadelphia, PAL, 1987. SIAM.
	28	Bruce Alan Wagar, Practical sorting algorithms for hypercube computers, University of Michigan, Ann Arbor, MI, 1991
	29	Y. Won and S. Sahni. A balanced bin sort for hypercube muI- ticomputers. Journal of Supercomputing, 2:435-448, 1988.

CITED BY 55

	Hongzhang Shan , Jaswinder Pal Singh, A Comparison of MPI, SHMEM and Cache-Coherent Shared Address Space Programming Models on a Tightly-Coupled Multiprocessors, International Journal of Parallel Programming, v.29 n.3, p.283-318, June 2001
	Marco Zagha , Guy E. Blelloch, Radix sort for vector multiprocessors, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.712-721, November 18-22, 1991, Albuquerque, New Mexico, United States
	Angelos Bilas , Dongming Jiang , Jaswinder Pal Singh, Accelerating shared virtual memory via general-purpose network interface support, ACM Transactions on Computer Systems (TOCS), v.19 n.1, p.1-35, Feb. 2001
	Angelos Bilas , Cheng Liao , Jaswinder Pal Singh, Using network interface support to avoid asynchronous protocol processing in shared virtual memory systems, ACM SIGARCH Computer Architecture News, v.27 n.2, p.282-293, May 1999
	Dongming Jiang , Jaswinder Pal Singh, A methodology and an evaluation of the SGI Origin2000, ACM SIGMETRICS Performance Evaluation Review, v.26 n.1, p.171-181, June 1998
	Remzi H. Arpaci , Andrea C. Dusseau , Amin M. Vahdat , Lok T. Liu , Thomas E. Anderson , David A. Patterson, The interaction of parallel and sequential workloads on a network of workstations, ACM SIGMETRICS Performance Evaluation Review, v.23 n.1, p.267-278, May 1995
	Hongzhang Shan , Jaswinder Pal Singh, Parallel sorting on cache-coherent DSM multiprocessors, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.40-es, November 14-19, 1999, Portland, Oregon, United States
	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
	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
	Ben Liblit , Alexander Aiken, Type systems for distributed data structures, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.199-213, January 19-21, 2000, Boston, MA, USA
	Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, ACM SIGARCH Computer Architecture News, v.23 n.2, p.24-36, May 1995
	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
	Thomas M. Stricker , Jonathan C. Hardwick, From AAPC algorithms to high performance permutation routing and sorting, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.200-203, June 24-26, 1996, Padua, Italy
	Ben H. H. Juurlink , Harry A. G. Wijshoff, A quantitative comparison of parallel computation models, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.13-24, June 24-26, 1996, Padua, Italy
	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
	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
	V. Puente , J. A. Gregorio , C. Izu , R. Beivide , F. Vallejo, Low-level router design and its impact on supercomputer system performance, Proceedings of the 13th international conference on Supercomputing, p.193-201, June 20-25, 1999, Rhodes, Greece
	Hongzhang Shan , Jaswinder Pal Singh, A comparison of MPI, SHMEM and cache-coherent shared address space programming models on the SGI Origin2000, Proceedings of the 13th international conference on Supercomputing, p.329-338, June 20-25, 1999, Rhodes, Greece
	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
	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
	Steven Cameron Woo , Jaswinder Pal Singh , John L. Hennessy, The performance advantages of integrating block data transfer in cache-coherent multiprocessors, ACM SIGPLAN Notices, v.29 n.11, p.219-229, Nov. 1994
	Sühleyman Cenk Sahinalp , Uzi Vishkin, Symmetry breaking for suffix tree construction, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.300-309, May 23-25, 1994, Montreal, Quebec, Canada
	Daniel Jiménez-González , Juan J. Navarro , Josep-L. Larrba-Pey, Fast parallel in-memory 64-bit sorting, Proceedings of the 15th international conference on Supercomputing, p.114-122, June 2001, Sorrento, Italy
	Xiaohan Qin , Jean-Loup Baer, A performance evaluation of cluster architectures, ACM SIGMETRICS Performance Evaluation Review, v.25 n.1, p.237-247, June 1997
	David E. Culler , Richard M. Karp , David Patterson , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser , Ramesh Subramonian , Thorsten von Eicken, LogP: a practical model of parallel computation, Communications of the ACM, v.39 n.11, p.78-85, Nov. 1996
	Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau , David E. Culler , Joseph M. Hellerstein , David A. Patterson, High-performance sorting on networks of workstations, ACM SIGMOD Record, v.26 n.2, p.243-254, June 1997
	David R. Helman , David A. Bader , Joseph JáJá, Parallel algorithms for personalized communication and sorting with an experimental study (extended abstract), Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.211-222, June 24-26, 1996, Padua, Italy
	Bernard L. Menezes , Frank T. Hady, The Performance of Crossbar-Based Binary Hypercubes, IEEE Transactions on Computers, v.44 n.10, p.1208-1215, October 1995
	Steven Saunders , Lawrence Rauchwerger, ARMI: an adaptive, platform independent communication library, ACM SIGPLAN Notices, v.38 n.10, October 2003
	Jop F. Sibeyn, Faster deterministic sorting through better sampling, Theoretical Computer Science, v.290 n.3, p.1829-1850, 3 January 2003
	Angelos Bilas , Dongming Jiang , Jaswinder Pal Singh, Shared virtual memory clusters: bridging the cost-performance gap between SMPs and hardware DSM systems, Journal of Parallel and Distributed Computing, v.63 n.12, p.1257-1276, December 2003
	Ulana Legedza , William E. Weihl, Reducing synchronization overhead in parallel simulation, ACM SIGSIM Simulation Digest, v.26 n.1, p.86-95, July 1996
	Andrew Sohn , Yuetsu Kodama, Load balanced parallel radix sort, Proceedings of the 12th international conference on Supercomputing, p.305-312, July 1998, Melbourne, Australia
	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
	Andrea C. Dusseau , David E. Culler , Klaus Erik Schauser , Richard P. Martin, Fast Parallel Sorting Under LogP: Experience with the CM-5, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.791-805, August 1996
	David R. Helman , Joseph JáJá , David A. Bader, A new deterministic parallel sorting algorithm with an experimental evaluation, Journal of Experimental Algorithmics (JEA), 3, p.4-es, 1998
	N. P. Manoj , K. V. Manjunath , R. Govindarajan, CAS-DSM: a compiler assisted software distributed shared memory, International Journal of Parallel Programming, v.32 n.2, p.77-122, April 2004
	Apostolos Papadopoulos , Yannis Manolopoulos, Parallel bulk-loading of spatial data, Parallel Computing, v.29 n.10, p.1419-1444, October 2003
	Nathan Thomas , Gabriel Tanase , Olga Tkachyshyn , Jack Perdue , Nancy M. Amato , Lawrence Rauchwerger, A framework for adaptive algorithm selection in STAPL, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA
	David A. Bader , David R. Helman , Joseph JáJá, Practical parallel algorithms for personalized communication and integer sorting, Journal of Experimental Algorithmics (JEA), 1, p.3-es, 1996
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias , Marco Zagha, Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.8 n.9, p.943-958, September 1997
	David A. Bader , Bernard M. E. Moret , Peter Sanders, Algorithm engineering for parallel computation, Experimental algorithmics: from algorithm design to robust and efficient software, Springer-Verlag New York, Inc., New York, NY, 2002
	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
	Joseph JaJa, A Perspective on Quicksort, Computing in Science and Engineering, v.2 n.1, p.43-49, January 2000
	Joseph F. JáJá , Kwan Woo Ryu, The Block Distributed Memory Model, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.830-840, August 1996
	Remzi H. Arpaci-Dusseau, Run-time adaptation in river, ACM Transactions on Computer Systems (TOCS), v.21 n.1, p.36-86, February 2003
	Manjunath Kudlur , R. Govindarajan, Performance analysis of methods that overcome false sharing effects in software DSMs, Journal of Parallel and Distributed Computing, v.64 n.8, p.887-907, August 2004
	Christof Krick , Friedhelm Meyer auf der Heide , Harald Räcke , Berthold Vöcking , Matthias Westermann, Data management in networks: experimental evaluation of a provably good strategy, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.165-174, June 27-30, 1999, Saint Malo, France
	Giuseppe Campobello , Marco Russo, A scalable VLSI speed/area tunable sorting network, Journal of Systems Architecture: the EUROMICRO Journal, v.52 n.10, p.589-602, October 2006
	Jing-Chao Chen, Efficient sample sort and the average case analysis or PEsort, Theoretical Computer Science, v.369 n.1, p.44-66, 15 December 2006
	Qi Yang , Son Dao , Clement Yu , Naphtali Rishe, A Parallel Scheme Using the Divide-and-Conquer Method, Distributed and Parallel Databases, v.5 n.4, p.405-438, Oct. 1997
	Peter P. Puschner, Real-Time Performance of Sorting Algorithms, Real-Time Systems, v.16 n.1, p.63-79, Jan. 1999
	Angelos Bilas , Courtney R. Gibson , Reza Azimi , Rosalia Christodoulopoulou , Peter Jamieson, Using System Emulation to Model Next-Generation Shared Virtual Memory Clusters, Cluster Computing, v.6 n.4, p.325-338, October 2003
	Buǧra Gedik , Rajesh R. Bordawekar , Philip S. Yu, CellSort: high performance sorting on the cell processor, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	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