Optimal simulations by Butterfly Networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal simulations by Butterfly Networks

Full text

Pdf (968 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twentieth annual ACM symposium on Theory of computing table of contents

Chicago, Illinois, United States

Pages: 192 - 204

Year of Publication: 1988

ISBN:0-89791-264-0

Authors

Sandeep Bhatt	Department of Computer Science, Yale University, New Haven, CT
Fan Chung	Mathematics, Information Sciences and Operations Research Division, Bell Communications Research, Morristown, NJ
Jia-Wei Hong	Beijing Computer Institute, Beijing 10044, CHINA and Courant Institute of Mathematics, NYU, New York, NY
Arnold Rosenberg	Department of Computer and Information Science, University of Massachusetts, Amherst, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 14, Citation Count: 16

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/62212.62229 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.

	BCLR	S.N. Bhatt, F.R,.K. Chung, F.T. Leighton, A.L. R, osenber$ (1986): Optimal simulations of tree machines. S7th IEEE FOCS Syrup., 274-282.
	BI	S.N. Bhatt and I. Ipsen (1985): Embedding trees in the hypercube. Yale Univ. Rpt, RR-443.
	BL	S.N. Bhatt and P.T. Leighton (1984): A framework for solving VLSI graph layout problems. Y. C$$. 28, 300-343.
	DP	Alvin M. Despain , David A. Patterson, X-Tree: A tree structured multi-processor computer architecture, Proceedings of the 5th annual symposium on Computer architecture, p.144-151, April 03-05, 1978 [doi>10.1145/800094.803041]
	Ga	D. Gannon (:{980): On pipelining a mesh-connected mu}tiprocessor for finite element problems by nested dissection. intl. Conf. on Parallel Processing.
	GHR	David S. Greenberg , Lenwood S. Heath , Arnold L. Rosenberg, Optimal Embeddings of the FFT Graph in the Hypercube, University of Massachusetts, Amherst, MA, 1988
	HR	J.-W. Hong and A.L. R(,senberg (1982): Graphs that are almost binary trees. SIAM d. Uomput. 11, 227-242.
	HZ	E. Horowitz and A. Zorat (1981): The binary tree as an interconnection network: applications to multiprocessor systems and 'JLSI. IEEE Trans. Comp., C-30, 247-253.
	Le	F.T. Leighton (1984): Parallel computation using meshes of trees. 1983 Workshop on Graph-Theoretic Concepts in Computer Science, Trauner Verlag, Linz: pp. 200-218.
	PV	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]

CITED BY 16

	Lenwood S. Heath, Lower bounds for graph embeddings via algebraic topology, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.311-317, June 30-July 02, 1993, Velen, Germany
	Serge Plotkin , Satish Rao , Warren D. Smith, Shallow excluded minors and improved graph decompositions, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.462-470, January 23-25, 1994, Arlington, Virginia, United States
	Bojana Obrenic, An approach to emulating separable graphs (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.159-167, July 21-24, 1991, Hilton Head, South Carolina, United States
	Anja Feldmann , Ming-Yang Kao , Jiří Sgall , Shang-Hua Teng, Optimal online scheduling of parallel jobs with dependencies, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.642-651, May 16-18, 1993, San Diego, California, United States
	R. Koch , T. Leighton , B. Maggs , S. Rao, Work-preserving emulations of fixed-connection networks, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.227-240, May 14-17, 1989, Seattle, Washington, United States
	Z. Miller , D. Pritikin , I. H. Sudborough, Near Embeddings of Hypercubes into Cayley Graphs on the Symmetric Group, IEEE Transactions on Computers, v.43 n.1, p.13-22, January 1994
	Burkhard Monien, Simulating binary trees on X-trees (extended abstract), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.147-158, July 21-24, 1991, Hilton Head, South Carolina, United States
	Friedhelm Meyer auf der Heide , Martin Storch , Rolf Wanka, Optimal trade-offs between size and slowdown for universal parallel networks, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.119-128, June 24-26, 1995, Santa Barbara, California, United States
	D. Greenberg , S. Bhatt, Routing multiple paths in hypercubes, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.45-54, July 02-06, 1990, Island of Crete, Greece
	Kevin J. Rappoport, On the slowdown of efficient simulations of multibutterflies on butterflies and butterfly-derived networks, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.176-182, June 24-26, 1996, Padua, Italy
	Clyde P. Kruskal , Kevin J. Rappoport, Bandwidth-based lower bounds on slowdown for efficient emulations of fixed-connection networks, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.132-139, June 27-29, 1994, Cape May, New Jersey, United States
	Saïd Bettayeb , Bin Cong , Mike Girou , I. Hal Sudborough, Embedding Star Networks into Hypercubes, IEEE Transactions on Computers, v.45 n.2, p.186-194, February 1996
	Ajay K. Gupta , Susanne E. Hambrusch, Embedding Complete Binary Trees Into Butterfly Networks, IEEE Transactions on Computers, v.40 n.7, p.853-863, July 1991
	Kemal Efe , Antonio Fernández, Products of Networks with Logarithmic Diameter and Fixed Degree, IEEE Transactions on Parallel and Distributed Systems, v.6 n.9, p.963-975, September 1995
	T. Leighton , M. Newman , A. G. Ranade , E. Schwabe, Dynamic tree embeddings in butterflies and hypercubes, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.224-234, June 18-21, 1989, Santa Fe, New Mexico, United States
	Peter Cappello, Application-specific Processor Architecture: Then and Now, Journal of Signal Processing Systems, v.53 n.1-2, p.197-215, November 2008