Parallel permutation and sorting algorithms and a new generalized connection network

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel permutation and sorting algorithms and a new generalized connection network

Full text

Pdf (1.33 MB)

Source

Journal of the ACM (JACM) archive
Volume 29 , Issue 3 (July 1982) table of contents

Pages: 642 - 667

Year of Publication: 1982

ISSN:0004-5411

Authors

David Nassimi	Department of Electrical Engineering and Computer Science, North-western University, Evanston, IL
Sartaj Sahni	Department of Computer Science, 136 Lind Hall, University of Minnesota, Minneapolis, MN

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 62, Citation Count: 46

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/322326.322329 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	Eshrat Arjomandi, A study of parallelism in graph theory., 1976
	2	BATCHER, K.E. Sorting networks and their apphcatmn. Proc AFIPS 1968 SJCC, Vol 32, AF{PS Press, Arlington, Va., pp. 307-314.
	3	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	4	CSANKY, L Fast parallel matrix inversion algorithms SlAM J. Comput 5, 4 (Dec. 1976), 618-623.
	5	Denise Marie Eckstein, Parallel graph processing using depth-first search and breadth-first search., 1977
	6	FLYNN, M J. Very high speed computing systems. Proc. IEEE 54 (Dec. 1966), 1901-1909.
	7	D. S. Hirschberg, Parallel algorithms for the transitive closure and the connected component problems, Proceedings of the eighth annual ACM symposium on Theory of computing, p.55-57, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803631]
	8	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]
	9	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	10	LANO, T Interconnections between processors and memory modules using the shuffle-exchange network. IEEE Trans. Comput. C-25, 5 (May 1976), 496-503.
	11	LANG, T., AND STONE, H A shuttle exchange network with stmplified control. IEEE Trans. Comput. C-25, 1 (Jan. 1976), 55-65.
	12	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]
	13	MUNRO, I., AND PATERSON, M. Optimal algorithms for parallel polynomial evaluation. Z Comput. Syst. Set 7 (1973), 189-198
	14	NASSimi, D., AND SAHNI, S. Bttonic sort on a mesh-connected parallel computer 1EEE Trans Comput. C-28, 1 (Jan. 1979), 2-7.
	15	David Nassimi , Sartaj Sahni, An optimal routing algorithm for mesh-connected Parallel computers, Journal of the ACM (JACM), v.27 n.1, p.6-29, Jan. 1980 [doi>10.1145/322169.322172]
	16	NASSIMI, D., AND SAHNI, S, Parallel algorithms to set up the Benes permutation network. IEEE Trans. Comput. C-31, 2 (Feb. 1982), 148-154.
	17	NASSIMI, D., AND SAHNI, S.Data broadcasting m SIMD computers. IEEE Trans. Comput. C-30, 2 (Feb. 1981), 101-107
	18	PR~PA1~.~TA, F.P. New parallel-sorting schemes. IEEE Trans. Comput. C-27, 7 (July 1978), 669--673.
	19	SAVAGE, C Parallel algor, thms for graph theoretic problems Ph D Dtssertauon, Umv of Ilhnom, Urbana, 11\|, Aug. 1978.
	20	STONE, H Parallel processing wtth the perfect shuffle IEEE Trans. Comput C-20, 2 (1971), L53-16t
	21	SWANSON, R C lnterconnections for parallel memories to unscramble p-ordered vectors. IEEE Trans, Comput. C-23, 11 (1974), 1105-1115
	22	THOMPSON, C D. Generahr~ed connection networks for parallel processor mtercommunicatton. IEEE Trans Comput. (7-27, 12 (Dec. 1978), 1119-1125.
	23	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]

CITED BY 46

	David Nassimi, Parallel Algorithms for the Classes of +or-2^b DESCEND and ASCEND Computations on a SIMD Hypercube, IEEE Transactions on Parallel and Distributed Systems, v.4 n.12, p.1372-1381, December 1993
	Hussein M. Alnuweiri , Viktor K. Prasanna, Parallel Architectures and Algorithms for Image Component Labeling, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.10, p.1014-1034, October 1992
	John H. Reif , Leslie G. Valiant, A logarithmic time sort for linear size networks, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.10-16, December 1983
	Malika De , Debasish Das , Mabhin Ghosh , Bhabani P. Sinha, An Efficient Sorting Algorithm on the Multi-Mesh Network, IEEE Transactions on Computers, v.46 n.10, p.1132-1137, October 1997
	Sanguthevar Rajasekaran, A framework for simple sorting algorithms on parallel disk systems (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.88-97, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Z. Fan , K. H. Cheng, A Generalized Simultaneous Access Dictionary Machine, IEEE Transactions on Parallel and Distributed Systems, v.2 n.2, p.149-159, April 1991
	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
	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
	Mounir Hamdi , S. W. Song, Efficient embeddings into the hypercube using matrix transformations, Proceedings of the 9th international conference on Supercomputing, p.280-288, July 03-07, 1995, Barcelona, Spain
	Ernst W. Mayr , Ralph Werchner, Optimal routing of parentheses on the hypercube, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.109-117, June 29-July 01, 1992, San Diego, California, United States
	Hyong S. Kim, Design and performance of Multinet switch: a multistage ATM switch architecture with partially shared buffers, IEEE/ACM Transactions on Networking (TON), v.2 n.6, p.571-580, Dec. 1994
	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
	Alexandros V. Gerbessiotis , Constantinos J. Siniolakis, Architecture independent parallel selection with applications to parallel priority queues, Theoretical Computer Science, v.301 n.1-3, p.119-142, 14 May 2003
	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
	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
	Artur Czumaj , Zvi Galil , Leszek Gąsieniec , Kunsoo Park , Wojciech Plandowski, Work-time-optimal parallel algorithms for string problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.713-722, May 29-June 01, 1995, Las Vegas, Nevada, United States
	P Feldman , J Friedman , N Pippenger, Non-blocking networks, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.247-254, May 28-30, 1986, Berkeley, California, United States
	Danny Dolev , Cynthia Dwork , Nicholas Pippenger , Avi Wigderson, Superconcentrators, generalizers and generalized connectors with limited depth, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.42-51, December 1983
	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
	Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980
	Danny Z. Chen , Mikhail J. Atallah, Optimal Parallel Hypercube Algorithms for Polygon Problems, IEEE Transactions on Computers, v.44 n.7, p.914-922, July 1995
	B. G. Douglass, Rearrangeable Three-Stage Interconnection Networks and Their Routing Properties, IEEE Transactions on Computers, v.42 n.5, p.559-567, May 1993
	Volker Heun , Ernst W. Mayr, Embedding graphs with bounded treewidth into their optimal hypercubes, Journal of Algorithms, v.43 n.1, p.17-50, April 2002
	Yuanyuan Yang , Jianchao Wang, Nonblocking k-Fold Multicast Networks, IEEE Transactions on Parallel and Distributed Systems, v.14 n.2, p.131-141, February 2003
	Olaf Bonorden , Ben Juurlink , Ingo von Otte , Ingo Rieping, The Paderborn University BSP (PUB) library, Parallel Computing, v.29 n.2, p.187-207, February 2003
	Junghoo Cho , Hector Garcia-Molina, Parallel crawlers, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA
	Alok Aggarwal , C. Greg Plaxton, Optimal parallel sorting in multi-level storage, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.659-668, January 23-25, 1994, Arlington, Virginia, United States
	G. D. Pifarré , L. Gravano , S. A. Felperin , J. L. C. Sanz, Fully Adaptive Minimal Deadlock-Free Packet Routing in Hypercubes, Meshes, and other Networks: Algorithms and Simulations, IEEE Transactions on Parallel and Distributed Systems, v.5 n.3, p.247-263, March 1994
	S. Ranka , S. Sahni, Odd Even Shifts in SIMD Hypercubes, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.77-82, January 1990
	R. Miller , Q. F. Stout, Computational geometry on hypercube computers, Proceedings of the third conference on Hypercube concurrent computers and applications, p.1220-1229, January 1989, Pasadena, California, United States
	J. JáJá , K. W. Ryu, Optimal Algorithms on the Pipelined Hypercube and Related Networks, IEEE Transactions on Parallel and Distributed Systems, v.4 n.5, p.582-591, May 1993
	S. Arora , T. Leighton , B. Maggs, On-line algorithms for path selection in a nonblocking network, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.149-158, May 13-17, 1990, Baltimore, Maryland, United States
	Yuanyuan Yang , Jianchao Wang, A New Self-Routing Multicast Network, IEEE Transactions on Parallel and Distributed Systems, v.10 n.12, p.1299-1316, December 1999
	Jianli Sun , E. Cerny , J. Gecsei, Fault Tolerance in a Class of Sorting Networks, IEEE Transactions on Computers, v.43 n.7, p.827-837, July 1994
	Ted H. Szymanski, Design Principles for Practical Self-Routing Nonblocking Switching Networks with O(N · log N) Bit-Complexity, IEEE Transactions on Computers, v.46 n.10, p.1057-1069, October 1997
	Volker Heun , Ernst W. Mayr, Efficient dynamic embeddings of binary trees into hypercubes, Journal of Algorithms, v.43 n.1, p.51-84, April 2002
	M. R. Samatham , D. K. Pradhan, The de Bruijn Multiprocessor Network: A Versatile Parallel Processing and Sorting Network for VLSI, IEEE Transactions on Computers, v.38 n.4, p.567-581, April 1989
	R. Miller , Q. F. Stout, Efficient Parallel Convex Hull Algorithms, IEEE Transactions on Computers, v.37 n.12, p.1605-1618, December 1988
	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
	G. Bilardi , F. P. Preparata, A minimum area VLSI network for O(logn) time sorting, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.64-70, December 1984
	Peter J. Varman , Kshitij Doshi, Sorting with Linear Speedup on a Pipelined Hypercube, IEEE Transactions on Computers, v.41 n.1, p.97-103, January 1992
	M. R. Samatham , D. K. Pradhan, The de Bruijn multiprocessor network: a versatile sorting network, ACM SIGARCH Computer Architecture News, v.13 n.3, p.360-367, June 1985
	Nripendra N. Biswas , S. Srinivas , Trishala Dharanendra, A centrally controlled shuffle network for reconfigurable and fault-tolerant architecture, ACM SIGARCH Computer Architecture News, v.15 n.1, p.81-87, March 1987
	Tsong-Chih Hsu , Sheng-De Wang, A simple architecture for constant time sorting machines, ACM SIGARCH Computer Architecture News, v.23 n.1, p.13-19, March 1995
	C. G. Plaxton, Load balancing, selection sorting on the hypercube, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.64-73, June 18-21, 1989, Santa Fe, New Mexico, United States
	Hung Q. Ngo , Yang Wang , Dazhen Pan, Rearrangeable and nonblocking [w, f] -distributors, IEEE/ACM Transactions on Networking (TON), v.17 n.3, p.990-1001, June 2009