Matching the bisection bound for routing and sorting on the mesh

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Matching the bisection bound for routing and sorting on the mesh

Full text

Pdf (1.09 MB)

Source

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

San Diego, California, United States

Pages: 31 - 40

Year of Publication: 1992

ISBN:0-89791-483-X

Authors

Michael Kaufmann
Sanguthevar Rajasekaran
Jop F. Sibeyn

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): 1, Downloads (12 Months): 10, Citation Count: 6

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/140901.140905 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	Angluin, D., and Valiant, L.G., 'Fast Probabilistic Algorithms for Hamiltonian Paths and Matchings,' journal of Computer and Systems Science, 18, 1979, pp. 155-193.
	2	Chernoff, H., 'A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations,' Annals of Mathematical Statistics 23, 1952, pp. 493-507.
	3	Dally, W., 'Wire-efficient VLSI Multiprocessor Communication Networks,' in Advanced Research in VLSI, 1987, pp. 391-415.
	4	Christos Kaklamanis , Danny Krizanc , Lata Narayanan , Thanasis Tsantilas, Randomized sorting and selection on mesh-connected processor arrays (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.17-28, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113381]
	5	Kaufmann, M., and Sibeyn, J., 'Randomized Multi-Packet Routing on Meshes,' Techn. Rep. RUU-CS-91-48, Dep. of CS, Utrecht University, Utrecht, 1991.
	6	Kaufmann, M., and Sibeyn, J., 'Multi Packet Routing in Lightly Loaded Processor Arrays, draft (1991).
	7	D. Krizanc , S. Rajasekaran , T. Tsantilas, Optimal routing algorithms for mesh-connected processor arrays (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	8	M. Kunde , T. Tensi, Multi-packet-routing on mesh connected arrays, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.336-343, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72971]
	9	Manfred Kunde, Concentrated regular data streams on grids: sorting and routing near to the bisection bound, Proceedings of the 32nd annual symposium on Foundations of computer science, p.141-150, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185363]
	10	Kunde, M., 'Routing and Sorting on Grids', Habilitatlon the~i~, Technical University of Munich 1991.
	11	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	12	T. Leighton , F. Makedon , I. G. Tollis, A 2n-2 step algorithm for routing in an nxn array with constant size queues, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.328-335, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72970]
	13	Makedon, F., Simvonis, A., 'On bit Serial packet routing for the mesh and the torus.' Proc. third Symposium on Frontiers of Massively Parallel Computation, 1990, pp. 294-302.
	14	Park, A., and Balasubramanian, K., 'Reducing Communication Costs for Sorting on Mesh- Connected and Linearly Connected Parallel Computers,' J. of Parallel and Distributed Computing, 9, 1990, pp. 318-322.
	15	Sanguthevar Rajasekaran, Randomised algorithms for packet routing on the mesh, Advances in parallel algorithms, John Wiley & Sons, Inc., New York, NY, 1992
	16	Rajasekaran, S., 'k-k Routing, k-k Sorting, and Cut Through Routing on the Mesh,' Technical Report, Department of CIS, University of Pennsylvania, Philadelphia, PA 19104, October 1991.
	17	Sanguthevar Rajasekaran , Richard Overholt, Constant queue routing on a mesh, Proceedings of the 8th annual symposium on Theoretical aspects of computer science, p.444-455, February 1991, Hamburg, Germany
	18	Rajasekaran, S., and Raghavachari, M., 'Optimal Randomized Algorithms for Multipacket and Cut Through Routing on the Mesh,' to be presented in the IEEE Symposium on Parallel and Distributed Processing, Dallas, Texas, Dec. 1991.
	19	Rajasekaran, S., and Sen, S., 'Random Sampling Techniques and Parallel Algorithms Design,' in Synthesis of Parallel Algorithms, editor: Reif, J.H., Morgan-Kaufmann Publishers, San Mateo, California, 1992.
	20	Sanguthevar Rajasekaran , Thanasis Tsantilas, An optimal randomized routing algorithm for the mesh and a class of efficient mesh-like routing networks, Proc. of the seventh conference on Foundations of software technology and theoretical computer science, p.226-241, December 1987, Pune, India
	21	Reischuk, R., 'Probabilistic Parallel Algorithms for Sorting and Selection,' SIAM Journal of Computing, 14(2), 1985, pp. 396-411.
	22	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]
	23	L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]

CITED BY 6

	Stephen Alstrup , Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Direct routing on trees, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.342-349, January 25-27, 1998, San Francisco, California, 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
	Torsten Suel, Improved bounds for routing and sorting on multi-dimensional meshes, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.26-35, June 27-29, 1994, Cape May, New Jersey, United States
	Jop F. Sibeyn, Faster deterministic sorting through better sampling, Theoretical Computer Science, v.290 n.3, p.1829-1850, 3 January 2003
	Sanguthevar Rajasekaran, Mesh Connected Computers with Fixed and Reconfigurable Buses: Packet Routing and Sorting, IEEE Transactions on Computers, v.45 n.5, p.529-539, May 1996
	Sanguthevar Rajasekaran, Out-of-core computing on mesh connected computers, Journal of Parallel and Distributed Computing, v.64 n.11, p.1311-1317, November 2004