Routing multiple paths in hypercubes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Routing multiple paths in hypercubes

Full text

Pdf (1.24 MB)

Source

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

Island of Crete, Greece

Pages: 45 - 54

Year of Publication: 1990

ISBN:0-89791-370-1

Authors

D. Greenberg	Department of Computer Science, Yale University, New Haven, CT
S. Bhatt	Department of Computer Science, Yale University, New Haven, CT and Computer Science Department, 256-80 California Institute of Technology, Pasadena, CA

Sponsors

IEEE-CS : Computer Society
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
CTI : Computer Technology Inst.
EATCS : European Association for Theoretical Computer Science
Computer Tech Inst. : Computer Technology Institute

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 28, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/97444.97457 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	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 [doi>10.1145/97444.97459]
	2	R. Aleliunas and A. L. Rosenberg. On embedding rectangular grids in square grids. IEEE Trans. Comp., 31:907-913, 1980.
	3	B. Alspach, J-C. Bermond, and D. Sotteau. Decomposition into cycles i: Hamilton decompositions. Technical Report 87-12, Simon Fraser University, 1987.
	4	Sandeep Bhatt , Fan Chung , Jia-Wei Hong , Arnold Rosenberg, Optimal simulations by Butterfly Networks, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.192-204, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62229]
	5	S.N. Bhatt, F.R.K. Chung, F.T. Leighton, and A.L. Rosenberg. Optimal simulations of tree machines. In 27th Annual Symposium on Foundations of Computer Science, pages 274-282, 1986.
	6	Sandeep N. Bhatt , F. R. K. Chung , F. T. Leighton , Arnold L. Rosenberg, Universal graphs for bounded-degree trees and planar graphs, SIAM Journal on Discrete Mathematics, v.2 n.2, p.145-155, May 1989 [doi>10.1137/0402014]
	7	M.Y. Chan. Dilation--2 embeddings of grids into hypercubes. In Int. Con}. on Parallel Processing, pages 295-298, 1988.
	8	M. Y. Chan, Embedding of d-dimensional grids into optimal hypercubes, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.52-57, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72941]
	9	W. J. Dally. A VLSI architecture for concurrent data structures. Technical Report 5209, California Institute of Technology, 1986.
	10	W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
	11	D. S. Greenberg and S.N. Bhatt. Routing Multiple Paths in Hypercubes. Technical Report 768, Yale University, 1990.
	12	D. S. Greenberg, L. S. Heath, and A. L. Rosenberg. Optimal embeddings of butterfly-like graphs in the hypercube. Math. Syst. Th., to appear, 1990.
	13	I. Havel and P. Liebl. Embedding the polytomic tree into the n-cube. Casopis pro P6stovdn "z matematiky, 98:307-314, 1973.
	14	W D Hillis, The connection machine, MIT Press, Cambridge, MA, 1985
	15	C.-T. Ho and S.L. Johnsson. Spanning balanced trees in boolean cubes. SLAM J. Sci. Statist. Comput., to appear, 1990. also as Yale University Technical Report 508, 1987.
	16	S. Lennart Johnsson, Communication effect basic linear algebra computations on hypercube architectures, Journal of Parallel and Distributed Computing, v.4 n.2, p.133-172, April 1, 1987 [doi>10.1006/jpdc.1997.1353 ]
	17	S. L. Johnsson and C.-T. Ho. Multiplication of arbitrarily shaped matrices on boolean cubes using the full comunications bandwidth. Technical Report 721, Yale University, July 1989.
	18	A R Karlin , E Upfal, Parallel hashing—an efficient implementation of shared memory, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.160-168, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12146]
	19	S. R. Kosarajn and M. J. Atallah. Optimal simulations between mesh-connected arrays of processors. Technical Report 561, Purdue University, September 1986.
	20	F. T. Leighton, B. Maggs, and S. Rao. Universal packet routing algorithms. In 29th Annual Symposium on Foundations of Computer Science, pages 256-269, 1988.
	21	N. Pippenger. Parallel communication with limited buffers, in 25th Annual Symposium on Foundations of Computer Science, pages 127-136, 1984.
	22	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]
	23	M. O. Rabin. Efficient dispersal of information for security, load balancing and fault tolerance. Technical Report 02-87, Harvard University, 1987.
	24	A. G. Ranade. How to emulate shared memory. In 28th Annual Symposium on Foundations o} Computer Science, pages 185-194, 1987.
	25	Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977
	26	Charles L. Seitz, The cosmic cube, Communications of the ACM, v.28 n.1, p.22-33, Jan. 1985 [doi>10.1145/2465.2467]
	27	Q.F. Stout and B. Wagar. Intensive hypercube communication, I" Prearranged communication in link-bound machines. Technical Report 9-87, University of Michigan, 1987.

CITED BY 2

	David Bruce Wilson, Embedding leveled hypercube algorithms into hypercubes (extended abstract), Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.264-270, June 29-July 01, 1992, San Diego, California, United States
	Bill Aiello , Tom Leighton, Coding theory, hypercube embeddings, and fault tolerance, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.125-136, July 21-24, 1991, Hilton Head, South Carolina, United States