nach oben

The Journal of Supercomputing

Erschienen in:

01.07.2014

Some properties and algorithms for the hyper-torus network

verfasst von: Jong-Seok Kim, Sung Won Kim, Ke Qiu, Hyeong-Ok Lee

Erschienen in: The Journal of Supercomputing | Ausgabe 1/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The hyper-torus network based on a three-dimensional hypercube was introduced recently. The hyper-torus \(QT(m,n)\) performs better than mesh type networks with a similar number of nodes in terms of the network cost. In this paper, we prove that if \(n\) is even, the bisection width of \(QT(m,n)\) is \(6n\), whereas it is \(6n+2\) if it is odd. Second, we show that \(QT(m,n)\) contains a Hamiltonian cycle. In addition, its one-to-all and all-to-all broadcasting algorithms are introduced. All of these broadcasting algorithms are asymptotically optimal.

Vorheriger Artikel A localization algorithm for large scale mobile wireless sensor networks: a learning approach

Nächster Artikel Characterizing and modeling cloud applications/jobs on a Google data center

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Seo JH, Lee HO, Jang MS (2008) Petersen-torus networks for multicomputer systems. In: Proceedings of the 4th international conference on networked computing and advanced, information management, pp 567–571

Dally W, Seitz C (1986) The torus routing chip. Distrib Comput 1:187–196CrossRef

Stojmenovic I (1997) Honeycomb network: topological properties and communication algorithms. IEEE Trans Parallel Distrib Syst 8(10):1036–1042CrossRef

Tang KW, Padubidri SA (1994) Diagonal and toroidal mesh networks. IEEE Trans Comput 43(7):815–826CrossRefMATH

Chen MS, Shin KG (1990) Addressing, routing, and broadcasting in hexagonal mesh multiprocessors. IEEE Trans Comput 39(1):10–18CrossRefMathSciNet

Vaidya AS, Rao PS, Shankar SR (1993) A class of hypercube-like networks, Proceedings of the 5th IEEE symposium on parallel and distributed processing, Dallas, Dec, pp 800–803

Yeh CH, Varvarigos EA, Parhami B (1999) Efficient VLSI layouts of hypercubic networks. In: Proceedings of the 7th symposium on the frontiers of massively parallel computation, Feb., pp 98–105

Ki WS, Lee HO, Oh JC (2009) The new torus network design based on 3-dimensional hypercube. In: Proceedings of the 11th international conference on advanced communication technology, pp 615–620

Bornstein CF, Litman A, Maggs BM, Sitaraman RK, Yatzkar T (2001) On the bisection width and expansion of butterfly networks. Theory Comput Syst 34:491–518CrossRefMATHMathSciNet

10.

Hsu Lh, Lin CK (2008) Graph theory and interconnection networks. CRC Press, Boca Raton

11.

Díaz J, Serna MJ, Wormald MC (2007) Bounds on the bisection width for random \(d\)-regular graphs. Theo Comput Sci 382:120–130CrossRefMATH

12.

Garey MR, Johnson DS (1979) Computers and intractability, a guide to the theory of NP-completeness, Freeman, San Francisco

13.

Monien B, Preis R (2006) Upper bounds on the bisection width of 3- and 4-regular graphs. J Discrete Algorithms 4:475–498CrossRefMATHMathSciNet

14.

Stacho L, Vrt’o I (1998) Bisection width of transposition graphs. Discrete Appl Math 84(1–3):221–235CrossRefMATHMathSciNet

15.

Tang KW, Kamoua R (2007) An upper bound for the bisection width of a diagonal mesh. IEEE Trans Comput 56(3):429–431CrossRefMathSciNet

16.

Zdeborová L, Boettcher S (2010) A conjecture on the maximum cut and bisection width in random regular graphs. J Stat Mech Theory Exp 2010:1–12CrossRef

17.

Rahman MS, Kaykobad M (2005) On Hamiltonian cycles and Hamiltonian paths. Inf Process Lett 94(1):37–41CrossRefMATHMathSciNet

18.

Wang D (2001) Embedding Hamiltonian cycles into folded hypercubes with faulty links. J Parallel Distrib Comput 61(4):545–564CrossRefMATH

19.

Albader B, Bose B, Flahive M (2012) Efficient communication algorithms in hexagonal mesh interconnection networks. IEEE Trans Parallel Distrib Syst 23(1):69–77CrossRef

20.

Farah RN, Othman M (2014) Broadcasting communication in high degree modified chordal rings networks. Appl Math Inf Sci 8(1):229–233CrossRef

21.

Ho CT, Johnsson L (1986) Distributed routing algorithms for broadcasting and personalized communication in hypercubes. In: Proceedings of international conference on Parallel Processing, pp 640–648

22.

Johnson SL, Ho CT (1989) Optimal broadcasting and personalized communication in hypercubes. IEEE Trans Comput 38(9):1249–1268CrossRefMathSciNet

23.

Stewart IA (2014) Interconnection networks of degree three obtained by pruning two-dimensional tori. IEEE Trans Comput (to appear)

24.

Thomson A, Zhou S (2014) Frobenius circulant graphs of valency six, Eisenstein–Jacobi networks, and hexagonal meshes. Eur J Comb 38:61–78CrossRefMATHMathSciNet

Titel: Some properties and algorithms for the hyper-torus network
verfasst von: Jong-Seok Kim
Sung Won Kim
Ke Qiu
Hyeong-Ok Lee
Publikationsdatum: 01.07.2014
Verlag: Springer US
Erschienen in: The Journal of Supercomputing / Ausgabe 1/2014
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-014-1130-0

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 1/2014

A GPU-based heart simulator with mass-spring systems and cellular automaton

Design of 4-disjoint gamma interconnection network layouts and reliability analysis of gamma interconnection Networks

Slot selection algorithms in distributed computing

Concurrent warp execution: improving performance of GPU-likely SIMD architecture by increasing resource utilization

Scalable CAIM discretization on multiple GPUs using concurrent kernels

Characterizing and modeling cloud applications/jobs on a Google data center