Some properties and algorithms for the hyper-torus network | The Journal of Supercomputing Skip to main content
Springer Nature Link
Log in

Some properties and algorithms for the hyper-torus network

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

References

  1. 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

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  6. 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

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

  8. 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

  9. 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–518

    Article  MATH  MathSciNet  Google Scholar 

  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–130

    Article  MATH  Google Scholar 

  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–498

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  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–12

    Article  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  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–1268

    Article  MathSciNet  Google Scholar 

  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–78

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgments

We thank the reviewers for their comments and suggestions which have substantially improved our presentation. This research was supported by Basic Science research program through the National research Foundation of KOREA (NRF) funded by the Ministry of Education, Science and Technology (2012R1A1A4A01014439).

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Rochester, Rochester, NY , 14627, USA

    Jong-Seok Kim

  2. Department of Information and Communication Engineering, Yeungnam University, Gyeongsan, Gyeongbuk, 712-749, South Korea

    Sung Won Kim

  3. Department of Computer science, Brock University, Saint Catharines, ON , L2S 3A1, Canada

    Ke Qiu

  4. Department of Computer Education, Sunchon National University, Sunchon, Chonnam , 540-742, South Korea

    Hyeong-Ok Lee

Authors
  1. Jong-Seok Kim
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Sung Won Kim
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Ke Qiu
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Hyeong-Ok Lee
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Hyeong-Ok Lee.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kim, JS., Kim, S.W., Qiu, K. et al. Some properties and algorithms for the hyper-torus network. J Supercomput 69, 121–138 (2014). https://doi.org/10.1007/s11227-014-1130-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-014-1130-0

Keywords