Article

Free access

Layered cross product—a technique to construct interconnection networks

Authors:

Shimon Even,

Ami LitmanAuthors Info & Claims

SPAA '92: Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures

Pages 60 - 69

https://doi.org/10.1145/140901.140908

Published: 01 June 1992 Publication History

PDF eReader

References

[1]

V. Bene~, "Permutation Groups, Complexes, and Rearrangeable Multistage Connecting Network", Bell Sys. Tech. aT., Vol. 43, 1964, pp. 1619-1640.

Crossref

Google Scholar

[2]

A. Waksman, "A Permutation Network", J. of the A CM, Vol. 15, No. 1, 1968, pp. 159-163.

Digital Library

Google Scholar

[3]

E. Upfal, "An O(logg) Deterministic Packet- Routing Scheme", J. of the A CM, Vol. 29, No. 1, 1992, pp. 55-70.

Digital Library

Google Scholar

[4]

N. Pippenger, "Telephone Switching Networks", Proceedings of Symposia in Applied Malhemalics, Vol. 26, American Mathematical Society, 1982, pp. 101-133.

Google Scholar

[5]

G.R. Goke and G.J. Lipovski, "Banyan Networks for Partitioning Multiprocessor Systems", 1st Ann. Syrup. on Computer Architecture, Florida, U.S.A., 1973, pp. 21-28.

Digital Library

Google Scholar

[6]

C.P. Kruskal and M. Snir, "A Unified Theory of Interconnection Network Structure", Theoretical Comp. Sci., Vol. 48, 1986, pp. 75-94.

Digital Library

Google Scholar

[7]

T. Leighton, "Parallel Computation Using Meshes of Trees", Proceedings of the WG'83, International Workshop on Graphtheoretic Concepts in Computer Science, edited by M. Nagl and J. Perl, Trauner Verlag, 1984, pp. 200-218.

Google Scholar

[8]

C.E. Leiserson, "Fat-Trees: Universal Networks for Hardware-Efficient Supercomputing", IEEE Trans. on Comp., Vol. c-34, No. 10, 1985, pp. 892-901.

Digital Library

Google Scholar

[9]

T. Leighton, B. Maggs and S. Rao, "Universal Packet Routing Algorithms", 29lh Annual Syrup. on Foundations of Comp. Sci., IEEE Computer Soc. Press, 1988, pp. 256-269.

Google Scholar

Cited By

View all

Paz A(2011)A theory of decomposition into prime factors of layered interconnection networksDiscrete Applied Mathematics10.1016/j.dam.2010.03.014159:7(628-646)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1016/j.dam.2010.03.014
Calamoneri TDi Ianni M(2006)Interval routing & Layered Cross Product: Compact routing schemes for butterflies, mesh of trees and fat treesEuro-Par’98 Parallel Processing10.1007/BFb0057963(1029-1039)Online publication date: 30-Jun-2006
https://doi.org/10.1007/BFb0057963
Savage J(2005)Extending the Hong-Kung model to memory hierarchiesComputing and Combinatorics10.1007/BFb0030842(270-281)Online publication date: 20-Jun-2005
https://doi.org/10.1007/BFb0030842
Show More Cited By

Index Terms

Layered cross product—a technique to construct interconnection networks
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Interconnection architectures

Recommendations

The Cross Product of Interconnection Networks

We study the cross product as a method for generating and analyzing interconnection network topologies for multiprocessor systems. Consider two interconnection graphs G1 and G2 each with some established properties such as symmetry, low degree and ...
High-radix interconnection networks
Interval routing & layered cross product: compact routing schemes for butterflies, meshes of trees, fat trees and Beneš networks

In this paper we propose compact routing schemes having space and time complexities comparable to a 2-interval routing scheme for the class of networks decomposable as layered cross product (LCP) of rooted trees. As a consequence, we are able to design ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SPAA '92: Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures

June 1992

441 pages

ISBN:089791483X

DOI:10.1145/140901

Chairman:
Lawrence Snyder
Univ. of Washington, Seattle

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 June 1992

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SPAA92

Sponsor:

SPAA92: 4th Annual ACM Symposium on Parallel Algorithms and Architectures

June 29 - July 1, 1992

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
298
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)6

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Paz A(2011)A theory of decomposition into prime factors of layered interconnection networksDiscrete Applied Mathematics10.1016/j.dam.2010.03.014159:7(628-646)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1016/j.dam.2010.03.014
Calamoneri TDi Ianni M(2006)Interval routing & Layered Cross Product: Compact routing schemes for butterflies, mesh of trees and fat treesEuro-Par’98 Parallel Processing10.1007/BFb0057963(1029-1039)Online publication date: 30-Jun-2006
https://doi.org/10.1007/BFb0057963
Savage J(2005)Extending the Hong-Kung model to memory hierarchiesComputing and Combinatorics10.1007/BFb0030842(270-281)Online publication date: 20-Jun-2005
https://doi.org/10.1007/BFb0030842
Calamoneri TMassini A(2005)On three-dimensional layout of interconnection networksGraph Drawing10.1007/3-540-63938-1_51(64-75)Online publication date: 29-Jul-2005
https://doi.org/10.1007/3-540-63938-1_51
Even GEven S(2005)Embedding interconnection networks in grids via the Layered Cross ProductAlgorithms and Complexity10.1007/3-540-62592-5_56(3-12)Online publication date: 3-Jun-2005
https://doi.org/10.1007/3-540-62592-5_56
Calamoneri TMassini A(2004)Efficient algorithms for checking the equivalence of multistage interconnection networksJournal of Parallel and Distributed Computing10.1016/j.jpdc.2003.09.00364:1(135-150)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.1016/j.jpdc.2003.09.003
Calamoneri TDi Ianni M(2003)Interval routing & layered cross productJournal of Parallel and Distributed Computing10.1016/S0743-7315(03)00110-263:11(1017-1025)Online publication date: 1-Nov-2003
https://dl.acm.org/doi/10.1016/S0743-7315%2803%2900110-2
Calamoneri TMassini A(2001)Optimal three-dimensional layout of interconnection networksTheoretical Computer Science10.1016/S0304-3975(99)00287-X255:1-2(263-279)Online publication date: Mar-2001
https://doi.org/10.1016/S0304-3975(99)00287-X
Avior ACalamoneri TEven SLitman ARosenberg ABlelloch G(1996)A tight layout of the butterfly networkProceedings of the eighth annual ACM symposium on Parallel Algorithms and Architectures10.1145/237502.241605(170-175)Online publication date: 24-Jun-1996
https://dl.acm.org/doi/10.1145/237502.241605
Leighton TMaggs BSitaraman R(1992)On the fault tolerance of some popular bounded-degree networksProceedings of the 33rd Annual Symposium on Foundations of Computer Science10.1109/SFCS.1992.267797(542-552)Online publication date: 24-Oct-1992
https://dl.acm.org/doi/10.1109/SFCS.1992.267797

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

The Cross Product of Interconnection Networks

High-radix interconnection networks

Interval routing & layered cross product: compact routing schemes for butterflies, meshes of trees, fat trees and Beneš networks