article

Free access

Optimal emulations by butterfly-like networks

Authors:

Eric J. SchwabeAuthors Info & Claims

Journal of the ACM (JACM), Volume 43, Issue 2

Pages 293 - 330

https://doi.org/10.1145/226643.226658

Published: 01 March 1996 Publication History

PDF eReader

References

[1]

AGGARWAL, A. 1984. A comparative study of X-tree, pyramid, and related machines. In Proceedings of the 25th IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 89-99.

Google Scholar

[2]

ANNEXSTEIN, F.S. 1989. Fault tolerance in hypercube-derivative networks. In Proceedings of the 1st ACM Symposium on Parallel Algorithms and Architectures (Santa Fe, N.M., June 18-21). ACM, New York, pp. 179-188.

Crossref

Google Scholar

[3]

ANNEXSTEIN, F. S., BAUMSLAG, M., AND ROSENBERG, A.L. 1990. Group action graphs and parallel architectures. SIAM J. Comput. 19, 544-569.

Digital Library

Google Scholar

[4]

BENE.S, V.E. 1964. Optimal rearrangeable multistage connecting networks. Bell Syst. Tech. J. 43, 1641-1656.

Crossref

Google Scholar

[5]

BHATI, S. N., CHUNG, F. R. K., LEIGHTON, F. T., AND ROSENBERG, A. L. 1992. Efficient embeddings of trees in hypercubes. SIAM J. Comput. 21, 1, 151-162.

Digital Library

Google Scholar

[6]

BHarr, S. N., AND IPSEN, I. 1985. How to embed trees in hypercubes. Yale Univ. Res. Rep. DCS/RR-443. Yale Univ., New Haven, Conn.

Google Scholar

[7]

BHA'Vr, S. N., AND LEIGHTON, F.T. i984. A framework for solving VLSI graph layout problems. 3'. Comput. Syst. Sci. 28, 300-343.

Google Scholar

[8]

CHAN, M. Y. 1988. Dilation-2 embedding of grids into hypercubes. In Proceedings of the 1988 International Conference on Parallel Processing (University Park, Pa.). IEEE, New York, pp. 295-298.

Google Scholar

[9]

CHAN, M.Y. 1991. Embedding of grids into optimal hypercubes. SIAM J. Comput. 20, 834-864.

Digital Library

Google Scholar

[10]

DESPA1N, A. M., AND PATTERSON, D.A. 1978. X-tree~A tree structured muitiprocessor architecture. In Proceedings of the 5th Symposium on Computer Architecture (Palo Alto, Calif.). IEEE, New York, pp. 144-151.

Crossref

Google Scholar

[11]

GANNON, D. 1980. A note on pipelining a mesh-connected multiprocessor for finite element problems by nested dissection. In Proceedings of the 1980 International Conference on Parallel Processing (St. Charles, I11.). IEEE, New York, pp. 197-204.

Google Scholar

[12]

GINOSAR, R., AND EGOZI, D. 1987. Topological comparison of perfect shuffle and hypercube. Typescript, The Technion, Rehovot, Israel.

Google Scholar

[13]

GREENBERG, D. S., HEATH, L. S., AND ROSENBERG, A.L. 1990. Optimal embeddings of butterflylike graphs in the hypercube. Math. Syst. Th. 23, 61-77.

Crossref

Google Scholar

[14]

HAVEL, I., AND LIEBL, P. 1973. Embedding the polytomic tree into the n-cube. (?asopis pro P~stovttni Matematiky 98, 307-314.

Google Scholar

[15]

HONG, J.-W., AND ROSENBERG, A.L. 1982. Graphs that are almost binary trees. SIAM J. Comput. I 1,227-242.

Crossref

Google Scholar

[16]

HOROWlTZ, E., AND ZORAT, A. 1981. The binary tree as an interconnection network: applications to multiprocessor systems and VLSI. IEEE Trans. Comp. C-30, 247-253.

Google Scholar

[17]

Koch, R., LEIGHTON, F. T., MAGGS, B., RAO, S., ROSENBERG, A. L., AND SCHWABE, E.J. 1996. Work-preserving emulations of fixed-connection networks. J. ACM, to appear.

Crossref

Google Scholar

[18]

KRUSrAL, C. P., AnD SNm, M, 1986. A unified theory of interconnection network structure. Theor. Comput. Sci. 48, 75-94.

Crossref

Google Scholar

[19]

LEIGHTON, F. T. 1984. Parallel computation using meshes of trees. In Proceedings of the 1983 Workshop on Graph-Theoretic Concepts in Computer Science. Trauner Verlag, Linz, Austria, pp. 200-218.

Google Scholar

[20]

LEIGHTON, F.T. 1992. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan-Kaufmann, San Mateo, Calif.

Crossref

Google Scholar

[21]

LEIGHTON, F. T., MAGGS, B., AND RAO, S. 1994. Packet routing and job-shop scheduling in O(congestion + dilation) steps. Combinatorica 14, 2, pp. 167-180.

Crossref

Google Scholar

[22]

OaRESI(:, B. 1994. An approach to emulating separable graphs. Math. Syst. Theory 27, 41-63.

Digital Library

Google Scholar

[23]

PREPARATA, F. P., AND VUILLEMIN, J.E. 1981. The cube-connected cycles: A versatile network for parallel computation. Commun.,4CM 24, 300-309.

Crossref

Google Scholar

[24]

ROSENBERG, A.L. 1981. Issues in the study of graph embeddings. In Graph-Theoretic Concepts in Computer Science: Proceedings of the International Workshop WG80, Bad Honnef, Germany, H. Noltemeier, ed. Lecture Notes in Computer Science, vol. 100. Springer-Verlag, New York, pp. 150-176.

Crossref

Google Scholar

[25]

ROSENBERO, A. L. 1992. Product-shuffle networks: Toward reconciling shuffles and butterflies. Discr. Appl. Math. 37/38, 456-488.

Crossref

Google Scholar

[26]

SAAD, Y., A~D SCItULTZ, M.H. 1988. Topological properties of hypercubes. IEEE Trans. Comput. 37, 867-872.

Digital Library

Google Scholar

[27]

SIEGEL, H.J. 1985. Interconnection Networks for Large-Scale Parallel Processing. D.H. Heath and Co., Lexington, Mass.

Crossref

Google Scholar

[28]

VIZlNG, V.G. 1964. On an estimate of the chromatic class of a p-graph (in Russian). Diskret. Analiz 3, 25-30.

Google Scholar

Cited By

View all

Wagh MBendjilali K(2010)Butterfly Automorphisms and Edge FaultsProceedings of the 2010 Ninth International Symposium on Parallel and Distributed Computing10.1109/ISPDC.2010.11(33-40)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1109/ISPDC.2010.11
Heath L(2007)Graph embeddings and simplicial mapsTheory of Computing Systems10.1007/BF0267945330:1(51-65)Online publication date: 30-Jul-2007
https://doi.org/10.1007/BF02679453
Woodruff D(2006)Lower Bounds for Additive Spanners, Emulators, and MoreProceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science10.1109/FOCS.2006.45(389-398)Online publication date: 21-Oct-2006
https://dl.acm.org/doi/10.1109/FOCS.2006.45
Show More Cited By

Index Terms

Optimal emulations by butterfly-like networks

Recommendations

Embedding Complete Binary Trees Into Butterfly Networks

The authors present embeddings of complete binary trees into butterfly networks with or without wrap-around connections. Let m be an even integer and q=m+(log m)-1. The authors show how to embed a 2/sup q+1/-1-node complete binary tree T(q) into a (m+1)...
Embedding Binary X-Trees and Pyramids in Processor Arrays with Spanning Buses

We study the problem of network embeddings in 2-D array architectures in which eachrow and column of processors are interconnected by a bus. These architectures areespecially attractive if optical buses are used that allow simultaneous access by ...
Flattened Butterfly Topology for On-Chip Networks

With the trend towards increasing number of cores in a multicore processors, the on-chip network that connects the cores needs to scale efficiently. In this work, we propose the use of high-radix networks in on-chip networks and describe how the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 43, Issue 2

March 1996

205 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/226643

Editor:
F. T. Leighton
Massachusetts Institute of Technology, Cambridge, MA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 1996

Published in JACM Volume 43, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
658
Total Downloads

Downloads (Last 12 months)65
Downloads (Last 6 weeks)8

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wagh MBendjilali K(2010)Butterfly Automorphisms and Edge FaultsProceedings of the 2010 Ninth International Symposium on Parallel and Distributed Computing10.1109/ISPDC.2010.11(33-40)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1109/ISPDC.2010.11
Heath L(2007)Graph embeddings and simplicial mapsTheory of Computing Systems10.1007/BF0267945330:1(51-65)Online publication date: 30-Jul-2007
https://doi.org/10.1007/BF02679453
Woodruff D(2006)Lower Bounds for Additive Spanners, Emulators, and MoreProceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science10.1109/FOCS.2006.45(389-398)Online publication date: 21-Oct-2006
https://dl.acm.org/doi/10.1109/FOCS.2006.45
Rosenberg A(2006)Changing Challenges for Collaborative AlgorithmicsHandbook of Nature-Inspired and Innovative Computing10.1007/0-387-27705-6_1(1-44)Online publication date: 2006
https://doi.org/10.1007/0-387-27705-6_1
Wagh MGuzide O(2005)Mapping Cycles and Trees on Wrap-Around Butterfly GraphsSIAM Journal on Computing10.1137/S009753979936546235:3(741-765)Online publication date: 1-Sep-2005
https://dl.acm.org/doi/10.1137/S0097539799365462
Rosenberg AYurkewych M(2005)Guidelines for Scheduling Some Common Computation-Dags for Internet-Based ComputingIEEE Transactions on Computers10.1109/TC.2005.6554:4(428-438)Online publication date: 1-Apr-2005
https://dl.acm.org/doi/10.1109/TC.2005.65
OBRENIĆ B(2004)APPROXIMATING HYPERCUBES BY INDEX-SHUFFLE GRAPHS VIA DIRECT-PRODUCT EMULATIONSJournal of Interconnection Networks10.1142/S021926590400125805:04(429-473)Online publication date: Dec-2004
https://doi.org/10.1142/S0219265904001258
Newsome JSong DAkyildiz IEstrin DCuller DSrivastava M(2003)GEMProceedings of the 1st international conference on Embedded networked sensor systems10.1145/958491.958501(76-88)Online publication date: 5-Nov-2003
https://dl.acm.org/doi/10.1145/958491.958501
Liu LChen JChen SJia W(2002)An new representation for interconnection network structuresJournal of Central South University of Technology10.1007/s11771-002-0010-69:1(47-53)Online publication date: Mar-2002
https://doi.org/10.1007/s11771-002-0010-6
Chen JLiu LJia WChen S(2002)An Intuitive and Effective New Representation for Interconnection Network StructuresAlgorithms and Computation10.1007/3-540-40996-3_30(350-361)Online publication date: 29-Jan-2002
https://doi.org/10.1007/3-540-40996-3_30
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Embedding Complete Binary Trees Into Butterfly Networks

Embedding Binary X-Trees and Pyramids in Processor Arrays with Spanning Buses

Flattened Butterfly Topology for On-Chip Networks

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations