Deterministic sorting in nearly logarithmic time on the hypercube and related computers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Deterministic sorting in nearly logarithmic time on the hypercube and related computers

Full text

Pdf (991 KB)

Source

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

Baltimore, Maryland, United States

Pages: 193 - 203

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

R. Cypher	IBM Almaden Research Center, 650 Harry Rd., San Jose, CA
C. G. Plaxton	MIT Lab for Computer Science, 545 Technology Square, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 19, Citation Count: 18

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/100216.100240 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. Koml6s, and E. Szemerddi. An O(n log n) sorting network. Combinatorica, 3:1-19, 1983.
	2	A. D. Aleksandrov, A. N. Kolmogorov, and M. A. Lavrent'ev. Mathematics: Its Content, Methods and Meaning. MIT Press, Cambridge, MA, 1963.
	3	K. E. Batcher. Sorting networks and their applications. In Proceedings of the AFIPS Spring Joint Computer Conference, vol. 32, pages 307- 314, 1968.
	4	Robert Edward Cypher , Lawrence Snyder, Efficient communication in massively parallel computers, 1989
	5	R. E. Cypher. Theoretical aspects of VLSI pin limitations. Technical Report 89-02-01, University of Washington, Department of Computer Science, February 1989.
	6	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]
	7	D. Nassimi and S. Sahni. Data broadcasting in SIMD computers. IEEE Transactions on Computers, C-30:101-107, 1981.
	8	D. Nassimi and S. Sahni. A self-routing Benes network and parallel permutation algorithms. IEEE Transactions on Computers, C-30:332-340, 1981.
	9	D. Nassimi and S. Sahni. Parallel algorithms to set up the Benes permutation network. IEEE Transactions on Computers, C-31:148-154, 1982.
	10	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]
	11	Franco P. Preparata , Jean Vuillemin, The cube-connected cycles: a versatile network for parallel computation, Communications of the ACM, v.24 n.5, p.300-309, May 1981 [doi>10.1145/358645.358660]
	12	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]
	13	Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980 [doi>10.1145/357114.357116]
	14	H. S. Stone. Parallel processing with the perfect shuffle. IEEE Transactions on Computers, C- 20:153-161, 1971.
	15	E. Upfal, An O(logN) deterministic packet routing scheme, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.241-249, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73030]

CITED BY 18

	S. A. Felperin , L. Gravano , G. D. Pifarré , J. L. C. Sanz, Fully-adaptive routing: packet switching performance and wormhole algorithms, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.654-663, November 18-22, 1991, Albuquerque, New Mexico, United States
	Bruce M. Maggs , Berthold Vöcking, Improved routing and sorting on multibutterflies, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.517-530, May 04-06, 1997, El Paso, Texas, 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
	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
	Michael Kaufmann , Jop F. Sibeyn , Torsten Suel, Derandomizing algorithms for routing and sorting on meshes, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.669-679, January 23-25, 1994, Arlington, Virginia, United States
	B. Aiello , F. T. Leighton , B. Maggs , M. Newman, Fast algorithms for bit-serial routing on a hypercube, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.55-64, July 02-06, 1990, Island of Crete, Greece
	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
	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
	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
	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
	Amitava Datta , Subbiah Soundaralakshmi, Fast merging and sorting on a partitioned optical passive stars network, Computer science in perspective, Springer-Verlag New York, Inc., New York, NY, 2003
	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
	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
	P. F. Corbett , I. D. Scherson, Sorting in Mesh Connected Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.3 n.5, p.626-632, September 1992
	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
	Enyue Lu , S. Q. Zheng, Parallel Routing Algorithms for Nonblocking Electronic and Photonic Switching Networks, IEEE Transactions on Parallel and Distributed Systems, v.16 n.8, p.702-713, August 2005
	P. J. Bernhard , D. J. Rosenkrantz, Partitioning Message Patterns for Bundled Omega Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.4, p.353-363, April 1994