A taxonomy of parallel sorting

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A taxonomy of parallel sorting

Full text

Pdf (2.58 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 16 , Issue 3 (September 1984) table of contents

Pages: 287 - 318

Year of Publication: 1984

ISSN:0360-0300

Authors

Dina Bitton	Weizmann Institute, Rehovot, Israel
David J. DeWitt	Univ. of Wisconsin, Madison
David K. Hsaio	The Ohio State Univ., Columbus
Jaishankar Menon	The Ohio State Univ., Columbus

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 22, Downloads (12 Months): 130, Citation Count: 30

Additional Information:

references cited by index terms review 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/2514.2516 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	ALEKSEYEV, V. E. 1969. On certain algorithms for sorting with minimal memory. K~bernettca 5, 5.~
	3	Jayanta Banerjee , David K. Hsiao , Richard I. Baum, Concepts and capabilities of a database computer\, ACM Transactions on Database Systems (TODS), v.3 n.4, p.347-384, Dec. 1978 [doi>10.1145/320289.320292]
	4	BATCHER, K. E. 1968. Sorting networks and their applications. In Proceedings of the 1968 Spring Joint Computer Conference (Atlantic City, N.J., Apr. 30-May 2), vol. 32. AFIPS Press, Reston, Va., pp. 307-314.
	5	BAUDET, G., ANO STEVENSON, D. 1978. Optimal sorting algorithms for parallel computers. IEEE Trans. Comput. C-27, 1 (Jan.).
	6	BENTLEY, J. L., AND KUNG, H. T. 1979. A tree machine for searching problems. In Proceedmgs of the 1979 Internattonal Conference on Parallel Processmg (Aug.).
	7	BILARDi, G., AND PREPARATA, F. P. 1983. A miramum area VLSI architecture for O(log n) time sorting. TR-1006, Computer Science Department, Univ. of illinois at Urbana-Champalgn (Nov.).
	8	Dina Bitton , David J. DeWitt, Duplicate record elimination in large data files, ACM Transactions on Database Systems (TODS), v.8 n.2, p.255-265, June 1983 [doi>10.1145/319983.319987]
	9	BiTTON-FRIEDLAND, D. 1982. Design, analysis and implementation of parallel external sorting algorithms. Ph.D. &ssertation, TR464, Computer Science Department, Univ. of Wmconsin, Madison (Jan.).
	10	A. Borodin , J. E. Hopcroft, Routing, merging and sorting on parallel models of computation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.338-344, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802209]
	11	BRYANT, R. 1980. External sorting m a layered storage architecture. Lecture. IBM Research Center, Yorktown Heights, N.Y.
	12	CHEN, T C., LUM, V. Y., AND TUNG, C. 1978. The rebound sorter: An efficient sort engine for large files. In Proceedings of the 4th Internatwnal Conference on Very Large Data Bases (West Berlin, FRG, Sept. 13-15). IEEE, New York, 312-318.
	13	CHUNG, K., LuccIo, F., AND WONG, C. K. 1980. On the complexity of sorting in magnetic bubble memory systems. IEEE Trans. Comput. C-29 (July).
	14	Yasunori Dohi , Akira Suzuki , Noriyuki Matsui, Hardware sorter and its application to data base machine, Proceedings of the 9th annual symposium on Computer Architecture, p.218-225, April 26-29, 1982, Austin, Texas, United States
	15	Shimon Even, Parallelism in tape-sorting, Communications of the ACM, v.17 n.4, p.202-204, April 1974 [doi>10.1145/360924.360941]
	16	FENG, T.-Y. 1981. A survey of interconnection networks. Computer 14, 12 (Dec.).
	17	FmUSURN, J. P., AND F~NKrL, R. A. 1982. Quotient networks. IEEE Trans Comput C-31, 4 (Apr.).
	18	Fănică Gavril, Merging with parallel processors, Communications of the ACM, v.18 n.10, p.588-591, Oct. 1975 [doi>10.1145/361020.361216]
	19	D. S. Hirschberg, Fast parallel sorting algorithms, Communications of the ACM, v.21 n.8, p.657-661, Aug. 1978 [doi>10.1145/359576.359582]
	20	HslAo, D. C., AND MENON, M. J. 1980. Parallel record-sorting methods for hardware realization. Tech. Rep. OSU-CISRC-TR-80-7, Computer and Science Information Dept., Ohio State Univ., Columbus, Ohio (July).
	21	KNUTH, D. E. 1973. Sorting and searching. In The Art of Computer Prograrnrn~ng, vol. 3 Addmon- Wesley, Reading, Mass
	22	KUMAR, M., AND HIRSCHBERG, D. S. 1983. An efficient implementation of Batcher's odd-even merge algorithm and its application in parallel sorting schemes. IEEE Trans Comput C-32 (Mar.).
	23	LEE, D. T., CHANG, H., AND WONG, K. 1981. An onchip compare/steer bubble sorter. IEEE Trans Comput. C-30 (June).
	24	LEILICH, H. O., STmGE, G, Argo ZEIOLER, H. C. 1978. A search processor for database management systems. In Proceedings of the 4th Conference on Very Large Databases (West Berlin, FRG, Sept. 13-15) IEEE, New York, pp. 280-287.
	25	Charles Eric Leiserson, Area-efficient vlsi computation, 1981
	26	David E. Muller , Franco P. Preparata, Bounds to Complexities of Networks for Sorting and for Switching, Journal of the ACM (JACM), v.22 n.2, p.195-201, April 1975 [doi>10.1145/321879.321882]
	27	NASSlMI, D., ANO SAHNI, S. 1979. Bitomc sort on a mesh connected parallel computer, iEEE Trans. Comput C-27, 1 (Jan.).
	28	NASSlMI, D., ANO SAHNL S. 1982. Parallel algorithms to set up the Benes permutation network. IEEE Trans Comput. C-31, 2 (Feb.).
	29	PEASE, M. C. 1977. The indirect binary n-cube microprocessor array. IEEE Trans Comput C-26, 5 (May).
	30	PREPARATA, F. P. 1978. New parallel sorting schemes. IEEE Trans. Comput. C-27, 7 (July).
	31	PREPARATA, F. P., AND VUILLEMIN, j. 1979. The cube-connected-cycles. In Proceedings of the 20th Symposium on Foundations of Computer Science.
	32	P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
	33	SHILOACtl, ~, AND VISHKIN, U. 1981. Finding the maximum, merging and sorting in a parallel computation model. J Algortthrns 2, 1 (Mar.).
	34	Howard Jay Siegel, The universality of various types of SIMD machine interconnection networks, Proceedings of the 4th annual symposium on Computer architecture, p.70-79, March 23-25, 1977
	35	SIEGEL, $. J. 1979. Interconnection networks for SIMD machines. IEEE Comput 12, 6 (June).
	36	STONE, $. S. 1971 Parallel processing with the perfect shuffle IEEE Trans Cornput C-20, 2 (Feb.).
	37	Clark David Thompson, A complexity theory for vlsi, 1980
	38	THOMPSON, C. D. 1983. The VLSI complexity of sorting. IEEE Trans Comput C-32, 12 (Dec.).
	39	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]
	40	VALIANT, L G. 1975 Parallehsm in comparison problems. SIAM J Cornput 3, 4 (Sept.).
	41	VAN VOORHIS, D. C. 1971. On sorting networks. Ph.D. dissertation, Computer Science Dept., Stanford Umv, Stanford, Calif.
	42	VISHKIN U. 1981 Synchronized parallel computation. Ph.D. dissertation, Computer Science Dept., Technion--israel Institute of Technology, Halfa, Israel.
	43	YASUURA, H., TAKAGI, N., AND YAJIMA, S 1982. The parallel enumeration sorting scheme for VLSI. IEEE Trans Comput C-31, 12 (Dec.).

CITED BY 30

	David Taniar , J. Wenny Rahayu, Parallel database sorting, Information Sciences—Applications: An International Journal, v.146 n.1-4, p.171-219, October 2002
	Mohamed Salehmohamed , W. S. Luk , Joseph G. Peters, Performance evaluation of LAN sorting algorithms, ACM SIGMETRICS Performance Evaluation Review, v.15 n.1, p.226-233, May 1987
	Youran Lan , Magdi A. Mohamed, Parallel Quicksort in hypercubes, Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing: technological challenges of the 1990's, p.740-746, March 1992, Kansas City, Missouri, United States
	Paul Hartono Singgih , Howard B. Demuth , Martin T. Hagan , Roger L. Wainwright, Parallel merge-sort algorithms on the HEP, Proceedings of the 1986 ACM fourteenth annual conference on Computer science, p.237-244, February 1986, Cincinnati, Ohio, United States
	Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.321-359, Nov. 1989
	Mark H. Nodine , Jeffrey Scott Vitter, Greed sort: optimal deterministic sorting on parallel disks, Journal of the ACM (JACM), v.42 n.4, p.919-933, July 1995
	Zen-Cheung Shih , Gen-Huey Chen , R. C. T. Lee, Systolic algorithms to examine all pairs of elements, Communications of the ACM, v.30 n.2, p.161-167, Feb. 1987
	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
	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
	Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993
	Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.229-239, August 11-13, 1986, Calgary, Alberta, Canada
	Edward Omiecinski , Peter Scheuermann, A parallel algorithm for record clustering, ACM Transactions on Database Systems (TODS), v.15 n.4, p.599-624, Dec. 1990
	E. R. Omiecinski, A Parallel Algorithm for Relational Database Normalization, IEEE Transactions on Parallel and Distributed Systems, v.1 n.4, p.415-423, October 1990
	R. S. Francis , I. D. Mathieson, A Benchmark Parallel Sort for Shared Memory Multiprocessors, IEEE Transactions on Computers, v.37 n.12, p.1619-1626, December 1988
	Lasse Natvig, Logarithmic time cost optimal parallel sorting is not yet fast in practice!, Proceedings of the 1990 conference on Supercomputing, p.486-494, October 1990, New York, New York, United States
	P. Heidelberger , A. Norton , John T. Robinson, Parallel Quicksort Using Fetch-And-Add, IEEE Transactions on Computers, v.39 n.1, p.133-138, January 1990
	B Wah , G J Li, Survey on special purpose computer architectures for AI, ACM SIGART Bulletin
	W. S. Luk , Franky Ling, An Analytic/Empirical Study of Distributed Sorting on a Local Area Network, IEEE Transactions on Software Engineering, v.15 n.5, p.575-586, May 1989
	Zhaofang Wen, Multiway Merging in Parallel, IEEE Transactions on Parallel and Distributed Systems, v.7 n.1, p.11-17, January 1996
	Tatsuya Hayashi , Koji Nakano , Stephan Olariu, Work-Time Optimal k-Merge Algorithms on the PRAM, IEEE Transactions on Parallel and Distributed Systems, v.9 n.3, p.275-282, March 1998
	Carl G. Ponder, Parallelism and algorithms for algebraic manipulation: current work, ACM SIGSAM Bulletin, v.22 n.3, p.7-14, July 1988
	Xiaojun Guan , Michael A. Langston, Time-Space Optimal Parallel Merging and Sorting, IEEE Transactions on Computers, v.40 n.5, p.596-602, May 1991
	Stephan Olariu , M. Christina Pinotti , S. Q. Zheng, How to Sort N Items Using a Sorting Network of Fixed I/O Size, IEEE Transactions on Parallel and Distributed Systems, v.10 n.5, p.487-499, May 1999
	Y.-C. Hong , T. H. Payne, Parallel Sorting in a Ring Network of Processors, IEEE Transactions on Computers, v.38 n.3, p.458-464, March 1989
	Timothy Furtak , José Nelson Amaral , Robert Niewiadomski, Using SIMD registers and instructions to enable instruction-level parallelism in sorting algorithms, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	R. A. Lorie , H. C. Young, A low communication sort algorithm for a parallel database machine, Proceedings of the 15th international conference on Very large data bases, p.125-134, July 1989, Amsterdam, The Netherlands
	Jai Menon, A Study of Sort Algorithms for Multiprocessor Database Machines, Proceedings of the 12th International Conference on Very Large Data Bases, p.197-206, August 25-28, 1986
	P. C. Dibble , M. L. Scott, Beyond striping: the bridge multiprocessor file system, ACM SIGARCH Computer Architecture News, v.17 n.5, p.32-39, Sep. 1989
	Nozar Tabrizi , Nader Bagherzadeh, An ASIC design and formal analysis of a novel pipelined and parallel sorting accelerator, Integration, the VLSI Journal, v.41 n.1, p.65-75, January, 2008
	Scott Sirowy , Greg Stitt , Frank Vahid, C is for circuits: capturing FPGA circuits as sequential code for portability, Proceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays, February 24-26, 2008, Monterey, California, USA

INDEX TERMS

Classification:
B. Hardware
B.7 INTEGRATED CIRCUITS
B.7.1 Types and Design Styles
Subjects: Algorithms implemented in hardware

C. Computer Systems Organization
C.1 PROCESSOR ARCHITECTURES
C.1.2 Multiple Data Stream Architectures (Multiprocessors)
Subjects: Parallel processors**
C.2 COMPUTER-COMMUNICATION NETWORKS
C.2.4 Distributed Systems
Subjects: Distributed applications
C.4 PERFORMANCE OF SYSTEMS
Subjects: Design studies

F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Sorting and searching

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

REVIEW

"Colin Whitby-Strevens : Reviewer"

The dry-sounding title belies an excellent survey paper. The paper clarifies parallel sorting techniques into those implemented on sorting networks, those implemented on shared-memory multiprocessors, and those implemented on file stores. Also d more...

Collaborative Colleagues:

Dina Bitton: colleagues

David J. DeWitt: colleagues

David K. Hsaio: colleagues

Jaishankar Menon: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player